From: p2p-hackers@zgp.org (Lucas Gonze)
Date: Tue Jul 2 10:18:02 2002
Subject: [p2p-hackers] Distributed Timestamping Service

Brad Neuberg wrote:
> >>In a sense it sounds like your idea is to create very long certificate 
> >>chains.  As time "clicks" on and the directed graph of nodes signing 
> >>nodes grows, won't it get longer and longer to "authenticate" that time, 
> >>or do I have a misunderstanding?

You're right, given that the maximum length of the chain depends on the
amount of time between two events.   However there can be a minimal path
which is shorter.  

Let's say 
A->B, B->C, ..., Y->Z == 25 hops.   
But also, 
A->Y, Y->Z == 2 hops.

You could probably do that with standard topological tools like Chord, so
that the maximum path between two clicks would be log N.   

You have a chain A...Z with intermediaries B...Y.  How do you find the
shortest path { A->Y, Y->Z }, starting with Z?   You look up Y, X has two
signatures { W->X, A->X }, then you jump from X back to A.

On the other hand you may not be able to find the shortest path.  Let's
say there are two paths from A...E -- A->B->C->E and A->D->E.   From E's
perspective, there's no way to tell whether C or D will lead to the
shorter path.

A neat thing is that you could also work out the maximum length of a
verifiable sequence, because it's a function of the network half life. 

- Lucas