Re: Open Timestamps

On Sat, Sep 17, 2016 at 12:53:55AM +0200, Melvin Carvalho wrote:
> On 17 September 2016 at 00:04, S. Matthew English <
> s.matthew.english@gmail.com> 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.
> >
> 
> This is correct timestamps are just approximate, they can be several
> minutes out.  In fact, in rare cases they can come out of sequence.  But
> that's not an issue because the block height is another factor which
> enables the ordering.  In fact, bitcoin timestamps cycle round an round, if
> left to go long enough, so the block height becomes an extra vector on top
> of that.

So, under the hood the Bitcoin protocol requires that block timestamps meet two
requirements for the block to be valid:

1) nTime < current time, as measured by the node + 2 hrs
2) nTime > median time of the past 11 blocks

The first rule isn't directly relevant to timestamping. From the point of view
of a timestamp a miner who creates a block with a timestamp in the future isn't
doing any direct harm to the validity of the timestamp, as the timestamp is
only proving that data existed at some moment; forward dating the timestamp is
a strictly less powerful proof. The first rule is however indirectly relevant
to timestamping, in that it's what prevents miners from forward dating their
blocks to drive the difficulty down; if that first rule didn't exist Bitcoin
would be insecure.

The second rule means that every block will have a median time >= the previous
block, and that periods where blocks have median times == the previous block
are short-lived. This rule is very relevant to timestamping: it's what prevents
miners from backdating their blocks. If not for this rule, I could create a
block with a nTime well into the past, and use it to create a fake timestamp.

The problem is, interpreting the median time rule is quite tricky! For example,
if all miners choose to they could eaily conspire to produce blocks that always
had nTime set to the minimum possible, which after a few blocks is the previous
block's nTime + 1

However, if miners do this they (eventually) push the difficulty up, decreasing
their revenue. Meanwhile if only a minority of miners do this - with the rest
of the mining community setting nTime honestly - that minority's attempts to
create backdated timestamps is still limited by the median time rule.

I haven't fully figured out the details, but basically a reasonable
interpretation of the nTime would be to do something like assume the dishonest
minority has x% of the hashing power, then use the average of the last N nTime
fields, taking into account the probabilities of the dishonest x% finding what
% of those N blocks. This all gets very complex, very quickly! But at least all
the data's there for people to improve these estimates in the future - the
timestamping scheme itself doesn't need to be modified as this is better
understood.

Additionally, the Bitcoin network is watched pretty closely by a lot of people,
so if there ever was a time when miners started screwing around with timestamps
on blocks, it's highly likely that many people would notice this and raise the
alarm. That's not a perfect protection, but I don't think there's much risk of
fake timestamps being created in the main Bitcoin chain that are off by more
than a few hours without a lot of people noticing.


Secondly, because later timestamps are strictly less powerful proofs than
earlier ones, it'd be reasonable to use both a trusted signature based
timestamp(s) on top of a Bitcoin block timestamp, where the meaning of the two
combined is interpreted as proof that the message existed prior to the maximum
of the Bitcoin timestamp and the trusted signature timestamp. The proof is only
invalid if both the trusted signer(s) and Bitcoin miner(s) conspire; if neither
conspire at worst we've made the proof a little less powerful than it could
have been. Doing this could be a good way to ensure in a formalized, automated,
way that Bitcoin miners aren't conspiring to backdate timestamps.

The ideal implementation of this idea is probably for the trusted signatures to
be random beacon(s), and then mix in the hash digests of those signatures with
the digest that's getting timestamped in a Bitcoin tx, thus proving that the
block was created after the random beacon(s).

> The important thing about bitcoin is not the timestamp, but the ordering.
> I think bitcoin transactions themselves dont have a timestamp at all, only
> the block does.

That's correct.

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