Bitcoin: A Peer-to-Peer Electronic Cash System

1. Introduction

Commerce on the Internet has come to rely almost exclusively on financial institutions serving as trusted third parties to process electronic payments. While the system works well enough for most transactions, it still suffers from the inherent weaknesses of the trust-based model. Completely non-reversible transactions are not really possible, since financial institutions cannot avoid mediating disputes. The cost of mediation increases transaction costs, limiting the minimum practical transaction size and cutting off the possibility for small casual transactions.

What is needed is an electronic payment system based on cryptographic proof instead of trust, allowing any two willing parties to transact directly with each other without the need for a trusted third party. Transactions that are computationally impractical to reverse would protect sellers from fraud, and routine escrow mechanisms could easily be implemented to protect buyers. In this paper, we propose a solution to the double-spending problem using a peer-to-peer distributed timestamp server to generate computational proof of the chronological order of transactions.

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 adding these to the end of the coin. A payee can verify the signatures to verify the chain of ownership.

The problem, of course, is the payee can't verify that one of the owners did not double-spend the coin. A common solution is to introduce a trusted central authority, or mint, that checks every transaction for double-spending. To accomplish this without a trusted party, transactions must be publicly announced, and we need a system for participants to agree on a single history of the order in which they were received.

3. Timestamp Server

The solution we propose begins with a timestamp server. A timestamp server works by taking a hash of a block of items to be timestamped and widely publishing the hash. Each timestamp includes the previous timestamp in its hash, forming a chain, with each additional timestamp reinforcing the ones before it.

4. Proof-of-Work

To implement a distributed timestamp server on a peer-to-peer basis, we will need to use a proof-of-work system. The proof-of-work involves scanning for a value that, when hashed, such as with SHA-256, the hash begins with a number of zero bits. Once the CPU effort has been expended to satisfy the proof-of-work, the block cannot be changed without redoing the work.

The proof-of-work also solves the problem of determining representation in majority decision-making. The majority decision is represented by the longest chain, which has the greatest proof-of-work effort invested in it. If a majority of CPU power is controlled by honest nodes, the honest chain will grow the fastest and outpace any competing chains.

5. Network

The steps to run the network are as follows:

• New transactions are broadcast to all nodes.
• Each node collects new transactions into a block.
• Each node works on finding a difficult proof-of-work for its block.
• When a node finds a proof-of-work, it broadcasts the block to all nodes.
• Nodes accept the block only if all transactions in it are valid and not already spent.
• Nodes express their acceptance of the block by working on creating the next block in the chain.

6. Incentive

By convention, the first transaction in a block is a special transaction that starts a new coin owned by the creator of the block. This adds an incentive for nodes to support the network, and provides a way to initially distribute coins into circulation. The incentive can also be funded with transaction fees.

7. Reclaiming Disk Space

Once the latest transaction in a coin is buried under enough blocks, the spent transactions before it can be discarded to save disk space. Transactions are hashed in a Merkle Tree, with only the root included in the block's hash. Old blocks can then be compacted by stubbing off branches of the tree.

8. Simplified Payment Verification

It is possible to verify payments without running a full network node. A user only needs to keep a copy of the block headers of the longest proof-of-work chain and obtain the Merkle branch linking the transaction to the block it's timestamped in. Verification is reliable as long as honest nodes control the network.

9. Combining and Splitting Value

To allow value to be split and combined, transactions contain multiple inputs and outputs. Normally, there will be either a single input from a larger previous transaction or multiple inputs combining smaller amounts, and at most two outputs: one for the payment, and one returning the change back to the sender.

10. Privacy

Privacy can still be maintained by keeping public keys anonymous. A new key pair should be used for each transaction to prevent them from being linked to a common owner. Some linking is unavoidable with multi-input transactions, which reveal that their inputs were owned by the same owner.

11. Calculations

We consider the scenario of an attacker trying to generate an alternate chain faster than the honest chain. The race between the honest chain and an attacker chain can be characterized as a Binomial Random Walk. The probability of an attacker catching up from a given deficit drops exponentially as the number of blocks increases.

12. Conclusion

We have proposed a system for electronic transactions without relying on trust. Nodes vote with their CPU power, expressing acceptance of valid blocks by working on extending them and rejecting invalid blocks by refusing to work on them. Any needed rules and incentives can be enforced with 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," 1999.
[3] S. Haber, W.S. Stornetta, "How to time-stamp a digital document," Journal of Cryptology, 1991.
[4] D. Bayer, S. Haber, W.S. Stornetta, "Improving the efficiency of digital time-stamping," 1993.
[5] S. Haber, W.S. Stornetta, "Secure names for bit-strings," 1997.
[6] A. Back, "Hashcash - a denial of service counter-measure," 2002.
[7] R.C. Merkle, "Protocols for public key cryptosystems," 1980.
[8] W. Feller, "An introduction to probability theory and its applications," 1957.