Bitcoin: A peer-to-peer electronic cash system

Summary. A pure peer-to-peer version of electronic cash would make it possible to send online payments directly from one party to another without having to go through a financial institution. Digital signatures provide part of the solution, but the main benefits are lost if a trusted third party is still required to prevent double-spending. We propose a solution to the problem of double spending in a peer-to-peer network. The network timestamps transactions by including them in an ongoing chain of hash-based proof-of-work. The longest chain not only serves as proof of the observed sequence of events, but also as proof that it comes from the largest pool of CPU power. As long as the majority of CPU power is controlled by nodes that do not cooperate to attack the network, they will create the longest chain and outperform the attackers. The network itself requires only a minimal structure. Messages are spread to the best of their knowledge and belief, and nodes can leave and rejoin the network at will, with the longest proof-of-work chain serving as proof of what happened in their absence.

Satoshi Nakamoto
[email protected]
www.bitcoin.org

1. Introduction

Internet commerce relations almost exclusively on financial institutions that act as trusted third parties to process electronic payments. Although this system works well enough for most transactions, it still suffers from the inherent weaknesses of the trust-based model. Completely irreversible transactions are not really possible, as financial institutions cannot avoid settling disputes. The cost of arbitration increases transaction costs, limits the practical minimum size of transactions, and limits the opportunity for small casual transactions. With the possibility of reversal, the need for trust grows. Merchants need to be cautious of their customers and ask them for more information than they would otherwise need. A certain percentage of fraud is accepted as inevitable. These costs and payment uncertainties can be avoided by using physical money, but there is no mechanism to make payments through a communication channel without a trusted party.

What is needed is an electronic payment system based on cryptographic evidence rather than trust, allowing any two parties to transact directly with each other without the need for a trusted third party. Transactions that are computationally irreversible would protect sellers from fraud, and routine escrow mechanisms could easily be set up to protect buyers. In this post, we propose a solution to the double-spending problem that uses a distributed peer-to-peer timestamp server to create computational proof of the chronological order of transactions. The system is secure as long as honest nodes collectively control more CPU power than a cooperating group of attacker nodes.

2: Transactions.

We define an electronic coin as a chain of digital signatures. Each owner transfers the coin to the next by digitally signing a hash of the previous transaction and the public key of the next owner and attaching it to the end of the coin. A payee can verify the signatures to verify the chain of ownership.

The problem, of course, is that the payee can't verify that one of the owners didn't double-spend the coin. A common solution is to introduce a trusted central authority or mint that checks each transaction for double-spending. After each transaction, the coin must be returned to the mint to issue a new coin, and only coins issued directly by the mint are guaranteed not to be issued twice. The problem with this solution is that the fate of the entire monetary system depends on the company that operates the mint, and that every transaction must go through it like a bank.

The payee must know that the previous owners have not signed any previous transactions. For our purposes, the earliest transaction is the one that counts, so later attempts to spend money twice are indifferent to us. The only way to confirm the absence of a transaction is to know all transactions. In the coinage-based model, the mint can know about all transactions and decide which comes first. To achieve this without a trusted party, the transactions must be publicly disclosed [1], and we need a system that allows participants to agree on a single history of the order of their receipt. The payee needs proof that at the time of each transaction, the majority of nodes have agreed to be the first to receive it.

3. Timestamp server

The solution we propose starts with a timestamp server. A timestamp server works with a hash of a block of items to be timestamped and publishes the hash on a large scale, such as in a newspaper or Usenet post [2-5]. The timestamp proves that the data must have existed at the time to be included in the hash. Each timestamp includes the previous timestamp in its hash, thus forming a chain, with each additional timestamp reinforcing the previous ones.

Proof-of-Work

To implement a peer-to-peer distributed timestamp server, we need to use a proof-of-work system similar to Adam Back's Hashcash [6], and not newspaper or Usenet posts. The proof of work is to look for a value whose hash value, as in SHA-256, starts with a number of zero bits. The average workload is exponential to the number of zero bits required and can be verified by executing a single hash.

For our timestamp network, we implement proof-of-work by incrementing a nonce in the block until a value is found that gives the block's hash the required zero bits. Once the CPU effort has been applied to fulfill the proof-of-work, the block cannot be changed without doing the work again. Since later blocks are concatenated after it, the work of changing the block would involve repeating all subsequent blocks.

The proof-of-work also solves the problem of representation in majority decisions. If the majority were determined on the basis of "one IP address - one vote", it could be undermined by anyone who is able to allocate many IPs. Proof-of-Work is essentially a CPU - a voice. The majority decision is represented by the longest chain in which the greatest proof-of-work effort has been invested. If the majority of CPU power is controlled by honest nodes, the honest chain will grow fastest and overtake all competing chains. To change a past block, an attacker would have to recreate the proof-of-work of the block and all subsequent blocks, and then catch up and outperform the work of the honest nodes. We'll show later that the likelihood of a slower attacker catching up decreases exponentially as more blocks are added.

To compensate for the increasing speed of the hardware and the fluctuating interest in running nodes over time, the proof-of-work difficulty is determined by a moving average targeting an average number of blocks per hour. If they are generated too fast, the difficulty increases.

5. Network

The steps to operate the network are as follows:

1. New transactions are sent to all nodes.
2. Each node collects new transactions in a block.
3. Each node is working to find a difficult proof-of-work for its block.
4. When a node finds a proof-of-work, it sends the block to all nodes.
5. The nodes only accept the block if all transactions contained therein are valid and not yet consumed.
6. The nodes express their acceptance of the block by working on creating the next block in the chain, using the hash of the accepted block as the previous hash.

The knots always consider the longest chain as the right one and continue to work on its extension. If two nodes send different versions of the next block at the same time, some nodes may receive one or the other version first. In this case, they work on the version received first, but save the other branch in case it gets longer. The tie is resolved when the next proof-of-work is found and one branch becomes longer; the nodes that worked on the other branch then move to the longer branch.

New transaction transfers do not necessarily have to reach all nodes. As long as they reach many nodes, they will soon get into a block. Block broadcasts are also tolerant of lost messages. If a node does not receive a block, it requests it when it receives the next block and finds that it has missed one.

6. Incentive

Conventionally, the first transaction in a block is a special transaction that starts a new coin owned by the creator of the block. This creates an incentive for the nodes to support the network and provides a way to put coins into circulation as there is no central authority to issue them. The steady addition of a constant amount of new coins is comparable to gold miners spending resources to put gold into circulation. In our case, it is CPU time and power that are spent.

The incentive can also be funded by transaction fees. If the output value of a transaction is less than its input value, the difference is added as a transaction fee to the incentive value of the block containing the transaction. Once a certain number of coins have been put into circulation, the incentive can be fully converted into transaction fees and is then completely inflation-free.

The incentive can help encourage nodes to stay honest. If a greedy attacker is able to gather more CPU power than all honest nodes, he would have to decide whether to use it for fraud by stealing back his payments, or whether to use it to generate new coins. It may be more profitable for him to abide by the rules that favor him with more new coins than all the others put together than to undermine the system and the validity of his own wealth.

7. Recovery of storage space

Once the last transaction of a coin is buried under a sufficient number of blocks, the transactions in front of it can be discarded to save storage space. To facilitate this without destroying the hash of the block, the transactions are hashed in a Merkle tree [7][2][5], only the root being included in the hash of the block. Old blocks can then be compacted by cutting off branches of the tree. The inner hashes do not need to be stored.

A block header without transactions would be about 80 bytes. If we assume that blocks are generated every 10 minutes, the result is 80 bytes * 6 * 24 * 365 = 4.2 MB per year. Since computer systems are typically sold with 2 GB of memory as of 2008 and Moore's Law predicts growth of 1.2 GB per year, storage should not be a problem even if the block headers need to be kept in memory.

8. Simplified payment verification

It is possible to verify payments without running a complete network node. A user only needs to keep a copy of the block headers of the longest proof-of-work chain that they can obtain by querying network nodes until they are convinced that they have the longest chain and get the Merkle branch that connects the transaction to the block in which it is timestamped. He cannot verify the transaction himself, but by linking it to a point in the chain, he can see that a network node has accepted it, and blocks added thereafter confirm that the network has accepted it.

Therefore, verification is reliable as long as honest nodes control the network, but it becomes more vulnerable if the network is overwhelmed by an attacker. While network nodes can verify transactions themselves, the simplified method can be deceived by an attacker's fraudulent transactions as long as the attacker is able to control the network. One strategy to protect against this would be for network nodes to accept alerts when they discover an invalid block and prompt the user's software to download the full block and the flagged transactions in order to confirm the inconsistency. Businesses that frequently receive payments will likely still want to run their own nodes to achieve more independent security and faster verification.

9. Combining and dividing values

Although it would be possible to handle coins individually, it would be unwieldy to make a separate transaction for every cent of a transfer. In order for values to be shared and combined, transactions contain multiple inputs and outputs. Normally there is either a single entry from a larger previous transaction or multiple entries combining smaller amounts and at most two exits: one for payment and one that returns the change, if any, to the sender.

It should be noted that a fan-out, in which one transaction depends on several transactions and these in turn depend on many more transactions, is not a problem here. There is never a need to extract a complete, self-contained copy of the history of a transaction.

10. Data protection

The traditional banking model achieves a certain level of privacy by limiting access to information to the parties involved and the trusted person. The need to publicly disclose all transactions precludes this method, but privacy can still be preserved by disrupting the flow of information elsewhere: through the anonymity of public keys. The public can see that someone is sending an amount to another person, but with no information linking the transaction to anyone. This is similar to the information issued by the exchanges, where the timing and scope of each transaction, the "tape", is published, without, however, stating who the parties were.

As an additional firewall, a new key pair should be used for each transaction to prevent them from being linked to a common owner. A certain level of linkage is unavoidable in multi-entry transactions, as they inevitably reveal that their entrances belong to the same owner. The risk is that if the owner of a key is disclosed, the link could reveal other transactions that belonged to the same owner.

11. Calculations

We consider the scenario in which an attacker attempts to generate an alternative chain faster than the honest chain. Even if this succeeds, the system is not vulnerable to arbitrary changes, such as creating value out of thin air or taking funds that never belonged to the attacker. Nodes will not accept an invalid transaction as a valid payment, and honest nodes will never accept a block containing such a transaction. An attacker can only attempt to alter one of their own transactions in order to recover money that they have recently spent.

The race between the honest chain and an attacker chain can be characterized as a binomial random walk. The success event is the extension of the honest chain by one block, increasing its lead by +1, and the failure event is the extension of the attacker's chain by one block, decreasing the gap by -1.

The likelihood of an attacker catching up on a given backlog is analogous to the Gambler's Ruin problem. Let's say a player with unlimited funds starts with a deficit and plays a potentially infinite number of attempts to break even. The probability that he will ever reach breakeven or that an attacker will catch up with the honest chain can be calculated as follows [8]:

p = probability that an honest node will find the next block
q = probability that the attacker will find the next block
qz = probability that the attacker will ever make up a backlog of z blocks

Assuming p > q, the probability decreases exponentially as the number of blocks the attacker needs to catch up increases. If the attacker does not make a happy leap forward early on, his chances become vanishingly small the further he falls behind.

We now look at how long the recipient of a new transaction has to wait before they can be sufficiently sure that the sender cannot change the transaction. We assume that the sender is an attacker who wants to pretend to the recipient that he paid him for a while, then after some time to change the transaction and pay himself. The recipient will be warned if this happens, but the sender hopes it will be too late.

The recipient creates a new key pair and passes the public key to the sender just before signing. This prevents the sender from preparing a chain of blocks in advance by continuously working on it until they are lucky enough to be far enough ahead and then executing the transaction at that moment. Once the transaction is submitted, the dishonest sender secretly begins working on a parallel chain containing an alternative version of their transaction.

The recipient waits until the transaction has been added to a block and z blocks have been linked to it. He does not know the exact progress that the attacker has made, but assuming that the honest blocks have taken the average expected time per block, the potential progress of the attacker will be a Poisson distribution with expected value:

To get the probability that the attacker could still catch up now, we multiply the Poisson density for each progress he could have made by the probability that he could catch up from that point on:

In order not to sum up the infinite tail of the distribution, it is rearranged...

Converting to C code...

 #include <math.h>
double AttackerSuccessProbability(double q, int z)
{
     double p = 1.0 - q;
     double lambda = z * (q / p);
     double sum = 1.0;
     int i, k;
     for (k = 0; k <= z; k++)
     {
          double poisson = exp(-lambda);
          for (i = 1; i <= k; i++)
               poisson *= lambda / i;
          sum -= poisson * (1 - pow(q / p, z - k));
     }
     return sum;
}

Based on some results, we can see that the probability decreases exponentially with e.g.

q=0.1
z=0    P=1.0000000
z=1    P=0.2045873
z=2    P=0.0509779
z=3    P=0.0131722
z=4    P=0.0034552
z=5    P=0.0009137
z=6    P=0.0002428
z=7    P=0.0000647
z=8    P=0.0000173
z=9    P=0.0000046
z=10   P=0.0000012

q=0.3
z=0    P=1.0000000
z=5    P=0.1773523
z=10   P=0.0416605
z=15   P=0.0101008
z=20   P=0.0024804
z=25   P=0.0006132
z=30   P=0.0001522
z=35   P=0.0000379
z=40   P=0.0000095
z=45   P=0.0000024
z=50   P=0.0000006

Solving for P less than 0.1%...

P < 0.001
q=0.10   z=5
q=0.15   z=8
q=0.20   z=11
q=0.25   z=15
q=0.30   z=24
q=0.35   z=41
q=0.40   z=89
q=0.45   z=340

12. Conclusion

We have proposed a system for electronic transactions that does not rely on trust. We began with the conventional framework of coins made up of digital signatures, which provides strong control over ownership but is incomplete because it offers no way to prevent double-spending. To solve this problem, we proposed a peer-to-peer network that uses a proof-of-work mechanism to record a public history of transactions. This history quickly becomes computationally impractical for an attacker to alter, provided that honest nodes control the majority of CPU power. The network is robust due to its unstructured simplicity. Nodes operate simultaneously with very little coordination. They do not need to be identified, since messages are not routed to any particular location and only need to be delivered on a best-effort basis. Nodes can leave and rejoin the network at will, accepting the proof-of-work chain as proof of what occurred while they were away. They vote with their CPU power by accepting valid blocks and working to extend them, while rejecting invalid blocks by refusing to work on them. Any required rules and incentives can be enforced through this consensus mechanism.

References

[1] W. Dai, "b-money," http://www.weidai.com/bmoney.txt, 1998.

[2] H. Massias, X.S. Avila, and J.-J. Quisquater, "Design of a secure timestamping service with minimal

trust requirements," In 20th Symposium on Information Theory in the Benelux, May 1999.

[3] S. Haber, W.S. Stornetta, “How to time-stamp a digital document,” In Journal of Cryptology, vol 3, no

2, pages 99-111, 1991.

[4] D. Bayer, S. Haber, W.S. Stornetta, "Improving the efficiency and reliability of digital time-stamping,"

In Sequences II: Methods in Communication, Security and Computer Science, pages 329-334, 1993.

[5] S. Haber, W.S. Stornetta, "Secure names for bit strings," In Proceedings of the 4th ACM Conference

on Computer and Communications Security, pages 28-35, April 1997.

[6] A. Back, "Hashcash - a denial of service counter-measure,"

http://www.hashcash.org/papers/hashcash.pdf, 2002.

[7] R.C. Merkle, "Protocols for public key cryptosystems," In Proc. 1980 Symposium on Security and

Privacy, IEEE Computer Society, pages 122-133, April 1980.

[8] W. Feller, "An introduction to probability theory and its applications," 1957.