Re: Open Timestamps

On Sat, Sep 17, 2016 at 12:04:07AM +0200, S. Matthew English wrote:
> When you study the transactions in the blocks in Bitcoin you can see the
> timestamps are quite messed up, i.e. not ordered chronologically.
> 
> Isn't one of the fundamental attributes of a distributed system the lack of
> a global clock?
> 
> Recently I'm starting to think that the Bitcoin blockchain only provides a
> very fuzzy notion of time stampedness. To me the blockchain is more about a
> rough sequencing of events.

Ah, with regard to that, you just made me realise something:

Assume that q of the hashing power is honest, and creates blocks with accurate
timestamps. Now suppose you want to ensure that with p probability, your
Bitcoin-based timestamp is valid and thus does not falsely have a timestamp
less than the actual time.

With n blocks, the probability of the dishonest hashing power finding all n
blocks is q^n. Thus if we define the timestamp as simply being the maximum
nTime for all n blocks _after_ the timestamp transaction is confirmed
(we can include the block containing the transaction), the probability of the
dishonest miners failing to create a invalid timestamp is 1-q^n. Solving for n
we get:

    p = 1 - q^n -> n = log(1 - p) / log(q)

Secondly, if the dishonest miners have a majority, we're completely screwed
anyway, as they can reject the blocks of the honest miners. So let's set q=0.5
as the worst possible case, and set p = 99%:

    n = log(0.01) / log(0.5) = 6.64

So basically, taking the largest nTime of the 7 blocks confirming the timestamp
transaction (the block containing the timestamp, and the next 6 blocks) gives
you a 99% chance of the timestamp being valid, so long as Bitcoin wasn't broken
at the time the timestamp was created. Similarly, 99.999999% probability is
just 27 confirmations (4.5hrs avg), at which point other factors are probably
more likely to create an invalid timestamp than the above model.

Also, note that "honest" miners may have their clocks set wrong - assuming that
at least half the miners have reasonably correctly set clocks is probably a
reasonable assumption. Adding on another hour or two to account for mistakes
like daylight savings misconfigurations is probably not a bad idea,
particularly since daylight savings is the kind of misconfiguration that could
happen on a wide-scale.


Note that for technical reasons, miners often set nTime greater than the current
time (nTime-nonce-rolling). As far as I know, no miner implements
nTime-nonce-rolling in a way that would ever set nTime to less than the current
time, but it's worth keeping an eye out in case that changes in the future.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org