Bitcoin White Paper

Esteban Suárez

Bitcoin: A User-to-User Electronic Cash System

Satoshi Nakamoto

satoshin@gmx.com

www.bitcoin.org

Summary

A purely electronic version of cash would allow online payments to be sent directly, from one entity to another. All this without having to go through a financial institution. Digital signatures provide part of the solution to the problem, but the main benefits are lost if a trusted third party has to exist to prevent double spending. We propose a solution to the double spending problem using a user-to-user network.

The network timestamps the transactions it enters in a continuous chain of proofs of work based on hash calculations. This creates a record that cannot be changed without recreating the entire proof of work. The longest chain not only serves as a witness and proof of the sequence of events. It also ensures that it’s coming from the pool with the largest CPU processing.

As long as most of the CPU processing power is under the control of nodes that do not cooperate to attack the network. In this way they will generate the longest chain and will give attackers an advantage. The network itself requires minimal structure. Messages are sent on a least-effort basis, and nodes can leave and rejoin the network as they see fit. Always accepting the longest chain of proof of work, as proof of what happened during your absence.

Introduction

Internet commerce has come to rely exclusively on financial institutions, which serve as trusted third parties, for the processing of 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, because financial institutions cannot avoid mediating disputes.

The cost of mediation increases transaction costs. This limits the practical minimum size per transaction and eliminates the possibility of making small casual transactions, with a higher cost for this loss and the impossibility of making non-reversible payments for non-reversible services. With the possibility of reversal, the need for trust expands. Merchants must beware of their customers by pestering them by asking for more information than would otherwise be needed.

A certain percentage of fraud is accepted as unavoidable. These costs and uncertainties in payments can be avoided if the person uses physical money. But there is no mechanism to make payments for a communication channel without a trusted third party. What is needed is an electronic payment system that is based on cryptographic evidence rather than trust. This seeks to allow the two interested parties to carry out transactions directly without the need for a trusted third party. Transactions that are computationally infeasible to reverse would protect sellers from fraud. And similarly routine escrow mechanisms could easily be put in place to protect buyers.

In this paper, we propose a solution to the double spending problem using a distributed user-to-user timestamp server to generate a computational proof of the chronological order of transactions. The system is secure as long as the honest nodes collectively control more processing power (CPU) than any group of attacking nodes.

Transactions

We define an electronic currency 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 next owner’s public key and appending both to the end of the coin. A beneficiary can verify signatures to verify the chain of ownership.

Transacciones

The problem is that the beneficiary cannot verify if any of the previous owners did not double spend the currency. The common solution is to introduce a trusted central authority. A kind of mint, which would check if each transaction has double spending or not. After each transaction, the coin must be returned to the mint to generate a new coin. In this way, only the coins generated directly by this mint are trusted not to have double-spending.

The problem with this solution is that the fate of the entire monetary system depends on the company that runs the mint. With all transactions having to go through them, just like a bank would. Therefore, we need to find a way for the beneficiary to know that the previous owners did not sign any previous transactions.

For our purposes, the latest or earliest transaction is the one that counts. So we won’t mind further double-spending attempts later. The only way to confirm the absence of a transaction is to be aware of all existing transactions. In the mint model, it was the mint that was aware of all transactions and would decide which came first. To achieve this without a trusted third party, transactions must be publicly announced [1], and we will need a system of participants agreeing on a single history, of the order in which these transactions were received. The beneficiary needs to know that at the time of each transaction, the majority of nodes agreed on which one was received first.

timestamp server

The solution we propose starts with a timestamp server. A timestamp server works by hashing a block of data to be dated and publishing it widely, just as you would in a newspaper or Usenet post [2-5]. The timestamp proves that the data obviously must have existed at that time in order to be included in the hash. Each timestamp hashes the previous timestamp into a chain, so that each additional timestamp reinforces those before a given one.

Marcas de tiempo

Work test

To implement a timestamp server following a user-to-user scheme, we will need to use a proof-of-work system similar to Adam Back’s Hashcash [6], rather than using a newspaper or Usenet posting. Proof-of-work involves scanning for a value, such that when calculating a hash, such as SHA-256, it starts with a given number of zero-valued bits. The average work required will be exponential to the number of bits required with value zero but can be verified by running a single hash.

For our timestamp network, we implement the proof of work by incrementing the value of a nonce field, belonging to the block, until a value is found that gives the required number of zero-value bits for the block hash. Once the CPU effort has been expended to satisfy the proof of work, the block cannot be changed without redoing all the work. As more blocks are chained after a given one, the work to change a block would include redoing all blocks after it.

Prueba de Trabajo

The proof of work also solves the problem of determining how to represent majority decision. If this majority were based on a vote per IP address, it could be altered by someone capable of assigning many IPs. Proof-of-work essentially amounts to “one-CPU-one-vote”. The decision of the majority is represented by the longest chain, which has the proof of work with the most effort invested.

If most of the CPU power is controlled by honest nodes, the honest chain will grow faster and outrun any other competing chain. To modify a block in the past, an attacker would have to redo the proof-of-work of the block and all subsequent blocks, and then catch up with and beat the work of honest nodes.

We will then show that the probability that a slower attacker can catch up to the longer chain decreases exponentially as more subsequent blocks are added.

To compensate for increased hardware speed and the varying interest of running nodes over time, proof-of-work difficulty is determined by a moving average driven by an average number of blocks per hour. If these are generated too quickly, the difficulty increases.

The net

The steps that the network executes are the following:

  1. New transactions are issued to all nodes.
  2. Each node collects new transactions in a block.
  3. Each node works on finding a hard proof of work for its block.
  4. When a node finds a proof of work, it broadcasts the block to all nodes.
  5. The block is accepted by the nodes if all transactions in the block have been validated and not spent.
  6. Nodes express their acceptance of the block by working to create the next block in the chain, using the hash of the accepted block as the previous hash.

The longest chain is always considered the correct one and they start working on extending it. If two nodes issue different versions of the next block simultaneously, some nodes may receive one or the other first. In that case, they work on the first one they receive but save the other branch in case it gets longer. The tie is broken when the next proof of work is found and a branch becomes longer; nodes that were working on the other branch subsequently switch to the now longer one.

Broadcasts of new transactions do not necessarily need to reach all nodes. By the time they reach many nodes, they will end up entering a block before too long. The emission of the blocks is also tolerant to message loss. If a node does not receive a block, it will ask for it when it receives the next block and realizes that it has lost one.

Incentive

By convention, the first transaction in the block is a special transaction that generates a new coin owned by the creator of the block. This adds an incentive for nodes to support the network, and provides an initial way to distribute and circulate coins, since there is no authority to create them. This stable addition of a constant amount of new coins is analogous to gold miners spending resources to put it into circulation. In our case, the resources are the CPU time and electricity that are spent.

The incentive can also be established with transaction costs. If the output value of a transaction is less than the input, the difference will be a transaction fee that will be added to the incentive value of the containing block. Once a predetermined number of coins have entered circulation, the incentive can evolve entirely into transaction fees and be completely inflation-free.

The incentive can also help encourage nodes to stay honest. If a selfish attacker is able to gather more CPU power than all the honest nodes, he would have to choose between using it to defraud people by stealing their payments, or using it to generate new coins. He should find it more profitable to play by the rules, as they will favor him with more coins than all other nodes combined, than undermine the system and the validity of his own wealth. Reclaiming Disk Space

Once the last transaction is buried under enough blocks, the transactions spent before it can be discarded to save disk space. To facilitate this without breaking the block hash, transactions are checked against a Merkle tree [7] [2] [5], with only the root included in the block hash. Old blocks can be compacted by removing branches from the tree. The inner hashes do not need to be saved.

Espacio en discos

The header of a block without transactions will be about 80 bytes. If we assume that each block is generated every 10 minutes, then 80 bytes * 6 * 24 * 365 = 4.2MB per year. With computers generally shipping with 2GB of RAM in 2008, and Moore’s Law predicting current growth of 1.2GB per year, storage should not be an issue even if block headers must remain in memory.

Simplified Payment Verification

It is possible to verify payments without running a full network node. A user need only keep a copy of the block headers of the longest proof-of-work chain, which can be obtained by searching the network nodes until they are convinced they have the longest chain, and obtain the branch of the Merkle tree, which links the transaction to the block in which it has been dated. Although he cannot verify the transaction himself, by linking it somewhere in the chain, he can see that some node in the network has accepted it, so the blocks added later would further confirm this acceptance by the network.

Verificacion de Pagos

As such, verification is reliable as long as honest nodes control the network, but becomes more vulnerable if the network is taken over by an attacker. While network nodes can verify transactions themselves, the simplified method can be fooled by transactions fabricated by an attacker as long as the attacker can dominate the network. One strategy to protect yourself is to accept alerts from network nodes when they detect an invalid block, asking the user to download the entire block and the alerted transactions to confirm the inconsistency. Businesses that frequently receive payments will want to run their own nodes for more independent security and faster verification. Combining and Dividing Value

Although it would be possible to manipulate currencies individually, it would be unwieldy to make separate transactions for each cent of a transfer. To allow value to be split and combined, transactions contain multiple inputs and outputs. There will normally be either a single entry, from a previous larger transaction, or multiple entries combining smaller amounts, and at least two exits: one for payment, and one for returning the change, if any, back to the sender.

Transacciones

Keep in mind that this system is open in a fan, so that a transaction can depend on several transactions, and these in turn depend on many more, which is not a problem. There is never a need to extract a single complete copy of the transaction history.

Privacy

The traditional banking model achieves its level of privacy by limiting access to information to the parties involved and the trusted third party. The need to announce all transactions publicly precludes this approach, but privacy can still be maintained by breaking the flow of information elsewhere: by keeping public keys anonymous. Publicly it can be seen that someone is sending a certain amount to another person, but without information linking the transaction to anyone in particular. This is similar to the level of information displayed on stock exchanges, where the timing and size of individual transactions, the “tape”, are public, but without saying who the parties are.

Privacidad

As an additional firewall, a new key pair must be used for each transaction so that they can be associated with a common owner. Some types of association with multi-entry transactions are unavoidable, which may reveal that your entries belong to the same owner. The risk would be that if the owner of a key is revealed, then the link could reveal other transactions that belonged to the same owner. calculations

We consider the scenario where an attacker attempts to generate an alternate chain faster than the honest chain. Even if this were achieved, it would not open the system to arbitrary changes, such as creating value out of thin air or taking money that never belonged to the attacker. Nodes will not accept an invalid transaction as payment, and honest nodes will never accept a block containing them. An attacker can only try to change only his own transactions to get back money that he has recently spent.

The race between an honest chain and an attacker’s chain is characterized as a Binomial Random Walk. The success event is the honest chain extending by one additional block and increasing its lead by +1, and the failure event being the attacker’s chain extending by one block reducing the distance by -1.

The probability that an attacker can reach us, from a given deficit, is analogous to the Player Ruin problem. Suppose a player with unlimited credit starts at a deficit and plays potentially an infinite number of tries to try to break even. We can calculate the probability that he will break even, or that he will catch up with the honest chain, as follows [8]:

p = probability that an honest node will find the next block

q = probability that the attacker will find the next block q

qz = probability that the attacker will reach from z blocks behind.

Ecuacion

Given our assumption that p > q, the probability drops exponentially as the number of blocks the attacker must reach increases. With the odds stacked against you, if you don’t make a lucky move early on, your chances become extremely small the farther behind you fall.

Now consider how long the beneficiary needs to wait for a new transaction before being sufficiently certain that the issuer cannot change it. We assume that the sender is an attacker who wants to make the payee believe that he was paid for a while, then change the transaction to pay himself back after some time has passed. The payee will be alerted when this happens, but the sender hopes it is too late.

The recipient generates a new key pair and delivers the public key to the sender shortly after signing. This prevents the issuer from setting up a blockchain ahead of time, and being able to continually work on it until he is lucky enough to get ahead of himself, and then execute the transaction at that point. Once the transaction is sent, the rogue sender secretly starts working on a parallel chain that contains an alternate version of his transaction.

The beneficiary waits for the transaction to be added to a block and for z blocks to be linked after the transaction. You won’t need to know the exact amount of progress the attacker has made, but assuming the honest blocks took the expected average per block, the attacker’s potential progress will be a Poisson distribution with an expected value of:

Ecuacion

To get the probability that the attacker can still reach us now, we multiply the Poisson density by the amount of progress he could have made times the probability that he could reach that point:

Ecuacion

We rearrange to avoid the sum of the infinite tail of the distribution…

Ecuacion

Convertimos a código en C…

 

 #include 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; 
     }

We run some results, we can see that the probability drops off exponentially with z.

   
 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

We solve 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

Conclusions

We have proposed a system of electronic transactions that do not depend on trust. We start with the usual framework of currencies made based on the use of digital signatures, which provides strong ownership control, but is incomplete if there is no way to prevent double spending. To fix this, we propose a user-to-user network that uses proof-of-work to record a public transaction history and quickly becomes computationally unsolvable to an attacker who wants to change it, if honest nodes control most of the CPU power.

A robust network for its unstructured simplicity. The nodes can all work at the same time with little coordination. They do not need to be identified, as messages are not routed to any particular location and only need to be delivered on a best-effort basis. Nodes can go to and from the network at will, accepting the proof-of-work chain as proof of what happened while they were away. They vote with their CPU power, expressing their acceptance of valid blocks by working on extending and rejecting invalid blocks by reusing working on them. Any necessary rules or incentives can be enforced with this consensus mechanism.

References

[1] W. Dai, “b-money,” https://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,” https://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.