Bitcoin Forum

Bitcoin => Bitcoin Discussion => Topic started by: mcqueenorama on May 18, 2011, 05:14:29 PM

Title: Proof of Work as Distributed Timestamp Server
Post by: mcqueenorama on May 18, 2011, 05:14:29 PM
Can somebody make this more clear?  The need for a distributed timestamp server is evident and fits into the argument very well, but the next step of the case is, "To implement a distributed timestamp server on a peer-to-peer basis, we will need to use a proof-of-work system ..."  That step is not immediately obvious. 

Title: Re: Proof of Work as Distributed Timestamp Server
Post by: theymos on May 18, 2011, 05:17:55 PM

Title: Re: Proof of Work as Distributed Timestamp Server
Post by: dvide on May 18, 2011, 05:34:42 PM
This is from Satoshi himself ( It might help you understand it.

The proof-of-work chain is a solution to the Byzantine Generals' Problem.  I'll
try to rephrase it in that context.

A number of Byzantine Generals each have a computer and want to attack the
King's wi-fi by brute forcing the password, which they've learned is a certain
number of characters in length.  Once they stimulate the network to generate a
packet, they must crack the password within a limited time to break in and
erase the logs, otherwise they will be discovered and get in trouble.  They
only have enough CPU power to crack it fast enough if a majority of them attack
at the same time.

They don't particularly care when the attack will be, just that they all agree.
 It has been decided that anyone who feels like it will announce a time, and
whatever time is heard first will be the official attack time.  The problem is
that the network is not instantaneous, and if two generals announce different
attack times at close to the same time, some may hear one first and others hear
the other first.

They use a proof-of-work chain to solve the problem.  Once each general
receives whatever attack time he hears first, he sets his computer to solve an
extremely difficult proof-of-work problem that includes the attack time in its
hash.  The proof-of-work is so difficult, it's expected to take 10 minutes of
them all working at once before one of them finds a solution.  Once one of the
generals finds a proof-of-work, he broadcasts it to the network, and everyone
changes their current proof-of-work computation to include that proof-of-work
in the hash they're working on.  If anyone was working on a different attack
time, they switch to this one, because its proof-of-work chain is now longer.

After two hours, one attack time should be hashed by a chain of 12
proofs-of-work.  Every general, just by verifying the difficulty of the
proof-of-work chain, can estimate how much parallel CPU power per hour was
expended on it and see that it must have required the majority of the computers
to produce that much proof-of-work in the allotted time.  They had to all have
seen it because the proof-of-work is proof that they worked on it.  If the CPU
power exhibited by the proof-of-work chain is sufficient to crack the password,
they can safely attack at the agreed time.

The proof-of-work chain is how all the synchronisation, distributed database
and global view problems you've asked about are solved.

Title: Re: Proof of Work as Distributed Timestamp Server
Post by: unk on May 18, 2011, 05:47:11 PM
i was just going to post the same message! i agree that it's the clearest explanation of the concept. conceiving the problem through the attack vectors against an unreliable distributed timestamp (e.g., one based on simple assertion) is the easiest way to understand the problem.

Title: Re: Proof of Work as Distributed Timestamp Server
Post by: mcqueenorama on May 18, 2011, 07:33:13 PM
Nice one guys!

A question from the linked page:

" "Length" is calculated as total combined difficulty of that chain, not number of blocks..."

So there is a txn-length of the chain, and a difficulty-length of the chain.

Is this the vector for the "more than 51% computing power" bitcoin attack?  I could make a txn-shorter chain and make it difficulty-longer but jacking up the difficulty and using better puters to easily achieve the desired dificulty?  That would allow me to truncate a chain and get my txn in, if I had superior computing power.  I could suddenly produce valid, but extremely difficult blocks, making my chain difficulty-longer, allowing me to make my chain the new authoritative source.

Title: Re: Proof of Work as Distributed Timestamp Server
Post by: unk on May 18, 2011, 07:38:57 PM
not quite, because it's the total difficulty that matters. it's probably easiest to think of it as 'length of the block chain, according to the protocol's rules about when difficulty periodically increases'.

thus, the attack you're describing would require that you surpass the combined difficulty for the whole block chain. if someone suddenly entered with massively speedier hardware than what we see now, the attack you're describing would be possible in concept (modulo checkpointing, which is potentially crass and fragile). but as an implementation detail, the attacker would have to re-run roughly the same amount of hashing work to produce earlier, lower-numbered blocks to be 'bitcoin' rather than just some alternative proof of work.