[137186] in cryptography@c2.net mail archive
Re: Bitcoin P2P e-cash paper
daemon@ATHENA.MIT.EDU (Satoshi Nakamoto)
Sun Nov 9 14:13:24 2008
Date: Sun, 09 Nov 2008 09:58:48 +0800
From: "Satoshi Nakamoto" <satoshi@vistomail.com>
Reply-To: satoshi@vistomail.com
To: hal@finney.org
Cc: cryptography@metzdowd.com
Hal Finney wrote:
> it is mentioned that if a broadcast transaction does not reach all nod=
es,
> it is OK, as it will get into the block chain before long. How does th=
is
> happen - what if the node that creates the "next" block (the first nod=
e
> to find the hashcash collision) did not hear about the transaction,
> and then a few more blocks get added also by nodes that did not hear
> about that transaction? Do all the nodes that did hear it keep that
> transaction around, hoping to incorporate it into a block once they ge=
t
> lucky enough to be the one which finds the next collision?
Right, nodes keep transactions in their working set until they get into =
a block. If a transaction reaches 90% of nodes, then each time a new bl=
ock is found, it has a 90% chance of being in it.
> Or for example, what if a node is keeping two or more chains around as
> it waits to see which grows fastest, and a block comes in for chain A
> which would include a double-spend of a coin that is in chain B? Is th=
at
> checked for or not? (This might happen if someone double-spent and two
> different sets of nodes heard about the two different transactions wit=
h
> the same coin.)
That does not need to be checked for. The transaction in whichever bran=
ch ends up getting ahead becomes the valid one, the other is invalid. I=
f someone tries to double spend like that, one and only one spend will a=
lways become valid, the others invalid.
Receivers of transactions will normally need to hold transactions for pe=
rhaps an hour or more to allow time for this kind of possibility to be r=
esolved. They can still re-spend the coins immediately, but they should=
wait before taking an action such as shipping goods. =20
> I also don't understand exactly how double-spending, or cancelling
> transactions, is accomplished by a superior attacker who is able to mu=
ster
> more computing power than all the honest participants. I see that he c=
an
> create new blocks and add them to create the longest chain, but how ca=
n
> he erase or add old transactions in the chain? As the attacker sends o=
ut
> his new blocks, aren't there consistency checks which honest nodes can
> perform, to make sure that nothing got erased? More explanation of thi=
s
> attack would be helpful, in order to judge the gains to an attacker fr=
om
> this, versus simply using his computing power to mint new coins honest=
ly.
The attacker isn't adding blocks to the end. He has to go back and redo=
the block his transaction is in and all the blocks after it, as well as=
any new blocks the network keeps adding to the end while he's doing tha=
t. He's rewriting history. Once his branch is longer, it becomes the n=
ew valid one.
This touches on a key point. Even though everyone present may see the s=
henanigans going on, there's no way to take advantage of that fact.=20
It is strictly necessary that the longest chain is always considered the=
valid one. Nodes that were present may remember that one branch was th=
ere first and got replaced by another, but there would be no way for the=
m to convince those who were not present of this. We can't have subfact=
ions of nodes that cling to one branch that they think was first, others=
that saw another branch first, and others that joined later and never s=
aw what happened. The CPU power proof-of-work vote must have the final =
say. The only way for everyone to stay on the same page is to believe t=
hat the longest chain is always the valid one, no matter what.
> As far as the spending transactions, what checks does the recipient of=
a
> coin have to perform? Does she need to go back through the coin's enti=
re
> history of transfers, and make sure that every transaction on the list=
is
> indeed linked into the "timestamp" block chain? Or can she just do the
> latest one?=20
The recipient just needs to verify it back to a depth that is sufficient=
ly far back in the block chain, which will often only require a depth of=
2 transactions. All transactions before that can be discarded.
> Do the timestamp nodes check transactions, making sure that
> the previous transaction on a coin is in the chain, thereby enforcing
> the rule that all transactions in the chain represent valid coins?
Right, exactly. When a node receives a block, it checks the signatures =
of every transaction in it against previous transactions in blocks. Blo=
cks can only contain transactions that depend on valid transactions in p=
revious blocks or the same block. Transaction C could depend on transac=
tion B in the same block and B depends on transaction A in an earlier bl=
ock.
> Sorry about all the questions, but as I said this does seem to be a
> very promising and original idea, and I am looking forward to seeing
> how the concept is further developed. It would be helpful to see a mor=
e
> process oriented description of the idea, with concrete details of the
> data structures for the various objects (coins, blocks, transactions),
> the data which is included in messages, and algorithmic descriptions
> of the procedures for handling the various events which would occur in
> this system. You mentioned that you are working on an implementation,
> but I think a more formal, text description of the system would be a
> helpful next step.
I appreciate your questions. I actually did this kind of backwards. I =
had to write all the code before I could convince myself that I could so=
lve every problem, then I wrote the paper. I think I will be able to re=
lease the code sooner than I could write a detailed spec. You're alread=
y right about most of your assumptions where you filled in the blanks.
Satoshi Nakamoto
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
