Bitcoin P2P e-cash paper

>Satoshi Nakamoto wrote:
>> I've been working on a new electronic cash system that's fully
>> peer-to-peer, with no trusted third party.
>>
>> The paper is available at:
>> http://www.bitcoin.org/bitcoin.pdf
>
>We very, very much need such a system, but the way I understand your
>proposal, it does not seem to scale to the required size.
>
>For transferable proof of work tokens to have value, they must have
>monetary value. To have monetary value, they must be transferred within
>a very large network - for example a file trading network akin to
>bittorrent.
>
>To detect and reject a double spending event in a timely manner, one
>must have most past transactions of the coins in the transaction, which,
> naively implemented, requires each peer to have most past
>transactions, or most past transactions that occurred recently. If
>hundreds of millions of people are doing transactions, that is a lot of
>bandwidth - each must know all, or a substantial part thereof.
>


Long before the network gets anywhere near as large as that, it would be safe for users to use Simplified Payment Verification (section 8) to check for double spending, which only requires having the chain of block headers, or about 12KB per day. Only people trying to create new coins would need to run network nodes. At first, most users would run network nodes, but as the network grows beyond a certain point, it would be left more and more to specialists with server farms of specialized hardware. A server farm would only need to have one node on the network and the rest of the LAN connects with that one node.

The bandwidth might not be as prohibitive as you think. A typical transaction would be about 400 bytes (ECC is nicely compact). Each transaction has to be broadcast twice, so lets say 1KB per transaction. Visa processed 37 billion transactions in FY2008, or an average of 100 million transactions per day. That many transactions would take 100GB of bandwidth, or the size of 12 DVD or 2 HD quality movies, or about $18 worth of bandwidth at current prices.

If the network were to get that big, it would take several years, and by then, sending 2 HD movies over the Internet would probably not seem like a big deal.

Satoshi Nakamoto

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

>[Lengthy exposition of vulnerability of a systm to use-of-force
>monopolies ellided.]
>
>You will not find a solution to political problems in cryptography.

Yes, but we can win a major battle in the arms race and gain a new territory of freedom for several years.

Governments are good at cutting off the heads of a centrally controlled networks like Napster, but pure P2P networks like Gnutella and Tor seem to be holding their own.

Satoshi


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

Hal Finney wrote:
> it is mentioned that if a broadcast transaction does not reach all nodes,
> it is OK, as it will get into the block chain before long. How does this
> happen - what if the node that creates the "next" block (the first node
> 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 get
> 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 block 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 that
> checked for or not? (This might happen if someone double-spent and two
> different sets of nodes heard about the two different transactions with
> the same coin.)

That does not need to be checked for. The transaction in whichever branch ends up getting ahead becomes the valid one, the other is invalid. If someone tries to double spend like that, one and only one spend will always become valid, the others invalid.

Receivers of transactions will normally need to hold transactions for perhaps an hour or more to allow time for this kind of possibility to be resolved. They can still re-spend the coins immediately, but they should wait before taking an action such as shipping goods.


> I also don't understand exactly how double-spending, or cancelling
> transactions, is accomplished by a superior attacker who is able to muster
> more computing power than all the honest participants. I see that he can
> create new blocks and add them to create the longest chain, but how can
> he erase or add old transactions in the chain? As the attacker sends out
> his new blocks, aren't there consistency checks which honest nodes can
> perform, to make sure that nothing got erased? More explanation of this
> attack would be helpful, in order to judge the gains to an attacker from
> this, versus simply using his computing power to mint new coins honestly.

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 that. He's rewriting history. Once his branch is longer, it becomes the new valid one.

This touches on a key point. Even though everyone present may see the shenanigans going on, there's no way to take advantage of that fact.

It is strictly necessary that the longest chain is always considered the valid one. Nodes that were present may remember that one branch was there first and got replaced by another, but there would be no way for them to convince those who were not present of this. We can't have subfactions 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 saw 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 that 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 entire
> 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?

The recipient just needs to verify it back to a depth that is sufficiently 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. Blocks can only contain transactions that depend on valid transactions in previous blocks or the same block. Transaction C could depend on transaction B in the same block and B depends on transaction A in an earlier block.


> 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 more
> 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 solve every problem, then I wrote the paper. I think I will be able to release the code sooner than I could write a detailed spec. You're already 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 at metzdowd.com

James A. Donald wrote:
>OK, suppose one node incorporates a bunch of
>transactions in its proof of work, all of them honest
>legitimate single spends and another node incorporates a
>different bunch of transactions in its proof of
>work, all of them equally honest legitimate single
>spends, and both proofs are generated at about the same
>time.
>
>What happens then?

They both broadcast their blocks. All nodes receive them and keep both, but only work on the one they received first. We'll suppose exactly half received one first, half the other.

In a short time, all the transactions will finish propagating so that everyone has the full set. The nodes working on each side will be trying to add the transactions that are missing from their side. When the next proof-of-work is found, whichever previous block that node was working on, that branch becomes longer and the tie is broken. Whichever side it is, the new block will contain the other half of the transactions, so in either case, the branch will contain all transactions. Even in the unlikely event that a split happened twice in a row, both sides of the second split would contain the full set of transactions anyway.

It's not a problem if transactions have to wait one or a few extra cycles to get into a block.

Satoshi Nakamoto



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

James A. Donald wrote:
> So what happened to the coin that lost the race?
>
> ... it is a bit harsh if the guy who came second
> is likely to lose his coin.

When there are multiple double-spent versions of the same transaction, one and only one will become valid.

The receiver of a payment must wait an hour or so before believing that it's valid. The network will resolve any possible double-spend races by then.

The guy who received the double-spend that became invalid never thought he had it in the first place. His software would have shown the transaction go from "unconfirmed" to "invalid". If necessary, the UI can be made to hide transactions until they're sufficiently deep in the block chain.


> Further, your description of events implies restrictions
> on timing and coin generation - that the entire network
> generates coins slowly compared to the time required for
> news of a new coin to flood the network

Sorry if I didn't make that clear. The target time between blocks will probably be 10 minutes.

Every block includes its creation time. If the time is off by more than 36 hours, other nodes won't work on it. If the timespan over the last 6*24*30 blocks is less than 15 days, blocks are being generated too fast and the proof-of-work difficulty doubles. Everyone does the same calculation with the same chain data, so they all get the same result at the same link in the chain.


> We want spenders to have certainty that their
> transaction is valid at the time it takes a spend to
> flood the network, not at the time it takes for branch
> races to be resolved.

Instantant non-repudiability is not a feature, but it's still much faster than existing systems. Paper cheques can bounce up to a week or two later. Credit card transactions can be contested up to 60 to 180 days later. Bitcoin transactions can be sufficiently irreversible in an hour or two.


> If one node is ignoring all spends that it does not
> care about, it suffers no adverse consequences.

With the transaction fee based incentive system I recently posted, nodes would have an incentive to include all the paying transactions they receive.

Satoshi Nakamoto

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

Hal Finney wrote:
> I think it is necessary that nodes keep a separate
> pending-transaction list associated with each candidate chain.
> ... One might also ask ... how many candidate chains must
> a given node keep track of at one time, on average?

Fortunately, it's only necessary to keep a pending-transaction pool for the current best branch. When a new block arrives for the best branch, ConnectBlock removes the block's transactions from the pending-tx pool. If a different branch becomes longer, it calls DisconnectBlock on the main branch down to the fork, returning the block transactions to the pending-tx pool, and calls ConnectBlock on the new branch, sopping back up any transactions that were in both branches. It's expected that reorgs like this would be rare and shallow.

With this optimisation, candidate branches are not really any burden. They just sit on the disk and don't require attention unless they ever become the main chain.


> Or as James raised earlier, if the network broadcast
> is reliable but depends on a potentially slow flooding
> algorithm, how does that impact performance?

Broadcasts will probably be almost completely reliable. TCP transmissions are rarely ever dropped these days, and the broadcast protocol has a retry mechanism to get the data from other nodes after a while. If broadcasts turn out to be slower in practice than expected, the target time between blocks may have to be increased to avoid wasting resources. We want blocks to usually propagate in much less time than it takes to generate them, otherwise nodes would spend too much time working on obsolete blocks.

I'm planning to run an automated test with computers randomly sending payments to each other and randomly dropping packets.


> 3. The bitcoin system turns out to be socially useful and valuable, so
> that node operators feel that they are making a beneficial contribution
> to the world by their efforts (similar to the various "@Home" compute
> projects where people volunteer their compute resources for good causes).
>
> In this case it seems to me that simple altruism can suffice to keep the
> network running properly.

It's very attractive to the libertarian viewpoint if we can explain it properly. I'm better with code than with words though.

Satoshi Nakamoto

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

Ray Dillinger wrote:
> One way to do this would be
> to have the person recieving the coin generate an asymmetric
> key pair, and then have half of it published with the
> transaction. In order to spend the coin later, s/he must
> demonstrate posession of the other half of the asymmetric
> key pair, probably by using it to sign the key provided by
> the new seller.

Right, it's ECC digital signatures. A new key pair is used for every
transaction.

It's not pseudonymous in the sense of nyms identifying people, but it
is at least a little pseudonymous in that the next action on a coin
can be identified as being from the owner of that coin.


> Mmmm. I don't know if I'm comfortable with that. You're saying
> there's no effort to identify and exclude nodes that don't
> cooperate? I suspect this will lead to trouble and possible DOS
> attacks.

There is no reliance on identifying anyone. As you've said, it's
futile and can be trivially defeated with sock puppets.

The credential that establishes someone as real is the ability to
supply CPU power.


> Until.... until what? How does anybody know when a transaction
> has become irrevocable? Is "a few" blocks three? Thirty? A
> hundred? Does it depend on the number of nodes? Is it logarithmic
> or linear in number of nodes?

Section 11 calculates the worst case under attack. Typically, 5 or
10 blocks is enough for that. If you're selling something that
doesn't merit a network-scale attack to steal it, in practice you
could cut it closer.


> But in the absence of identity, there's no downside to them
> if spends become invalid, if they've already received the
> goods they double-spent for (access to website, download,
> whatever). The merchants are left holding the bag with
> "invalid" coins, unless they wait that magical "few blocks"
> (and how can they know how many?) before treating the spender
> as having paid.
>
> The consumers won't do this if they spend their coin and it takes
> an hour to clear before they can do what they spent their coin on.
> The merchants won't do it if there's no way to charge back a
> customer when they find the that their coin is invalid because
> the customer has doublespent.

This is a version 2 problem that I believe can be solved fairly
satisfactorily for most applications.

The race is to spread your transaction on the network first. Think 6
degrees of freedom -- it spreads exponentially. It would only take
something like 2 minutes for a transaction to spread widely enough
that a competitor starting late would have little chance of grabbing
very many nodes before the first one is overtaking the whole network.
During those 2 minutes, the merchant's nodes can be watching for a
double-spent transaction. The double-spender would not be able to
blast his alternate transaction out to the world without the merchant
getting it, so he has to wait before starting.

If the real transaction reaches 90% and the double-spent tx reaches
10%, the double-spender only gets a 10% chance of not paying, and 90%
chance his money gets spent. For almost any type of goods, that's
not going to be worth it for the scammer.

Information based goods like access to website or downloads are
non-fencible. Nobody is going to be able to make a living off
stealing access to websites or downloads. They can go to the file
sharing networks to steal that. Most instant-access products aren't
going to have a huge incentive to steal.

If a merchant actually has a problem with theft, they can make the
customer wait 2 minutes, or wait for something in e-mail, which many
already do. If they really want to optimize, and it's a large
download, they could cancel the download in the middle if the
transaction comes back double-spent. If it's website access,
typically it wouldn't be a big deal to let the customer have access
for 5 minutes and then cut off access if it's rejected. Many such
sites have a free trial anyway.

Satoshi Nakamoto


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com