Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

A description of known problems in Satoshi Nakamoto's paper, "Bitcoin: A Peer-to-Peer Electronic Cash System", as well as notes on terminology changes and how Bitcoin's implementation differs from that described in the paper.

Abstract

The longest chain not only serves as proof of the sequence of events witnessed, but proof that it came from the largest pool of CPU power.

  • Implementation detail: If each link in the chain (called "blocks" in Bitcoin) was built using the same amount of Proof Of Work (POW), the longest chain would be the one backed by the largest pool of computational power. However, Bitcoin was implemented in such a way that the amount of POW can vary between blocks, so it became important not to check for the "the longest chain" but rather "the chain demonstrating the most POW"; this is often shortened to "strongest chain".

    The change from checking for the longest chain to checking for the most-work chain occurred in July 2010, long after Bitcoin's initial release:

    -    if (pindexNew->nHeight > nBestHeight)
    +    if (pindexNew->bnChainWork > bnBestChainWork)
  • Terminology change: General CPUs were used to generate the POW for the earliest Bitcoin blocks but POW generation today is mostly performed by specialist Application Specific Integrated Circuits (ASICs), so instead of saying "CPU power" it is perhaps more correct to say "computational power" or, simply, "hash rate" for the hashing used in generating the POW.

As long as a majority of CPU power is controlled by nodes that are not cooperating to attack the network, they'll generate the longest chain and outpace attackers.

  • Terminology change: The term "nodes" today is used to refer to full validation nodes, which are programs that enforce all the rules of the system. Programs (and hardware) that extend the chain today are called "miners" based on Nakamoto's analogy to gold miners in section 6 of the paper. Nakamoto expected all miners to be nodes but the software he released did not require all nodes to be miners. Today it is the case that the overwhelming number of nodes are not miners and that many individuals who own mining hardware do not use it with their own nodes (and even those that do often mine for short periods of time on top of newly discovered blocks without ensuring their node considers the new block valid). The early parts of the paper where "nodes" is mostly used without modification refer to mining using a full validation node; the later parts of the paper which refer to "network nodes" is mainly about what nodes can do even if they aren't mining.

  • Post-publication discovery: When a new block is produced, the miner who produces that block can begin working on its sequel immediately but all other miners must wait for that new block to propagate across the network to them. This gives miners who produce many blocks an edge over miners who produce fewer blocks, and this can be exploited in what's known as the selfish mining attack to allow an attacker with around 30% of total network hash rate to make other miners less profitable, perhaps driving them into following the attacking miner's policy. So instead of saying "a majority of CPU power is controlled by nodes that are not cooperating to attack the network" it is perhaps more correct to say "as long as nodes cooperating to attack the network control less than about 30% of the network".

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.

  • Implementation detail: Bitcoin implements a more general version of this system where digital signatures are not used directly but rather a "deterministic expression" is used instead. Just as a signature that matches a know public key can be used to enable a payment, the data that satisfies an known expression can also enable a payment. Generically, the expression that must be satisfied in Bitcoin in order to spend a coin is known as an "encumbrance". Almost all encumbrances in Bitcoin to date require providing at least one signature. So instead of saying "a chain of digital signatures" it is more correct to say "a chain of encumbrances".

4. Proof-of-Work

we implement the 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.

  • Implementation detail: Adam Back's Hashcash implementation requires finding a hash with the required number of leading zero bits. Bitcoin treats the hash as a integer and requires that it be less than a specified integer, which effectively allows a fractional number of bits to be specified.

Proof-of-work is essentially one-CPU-one-vote.

  • Important note: the vote here is not on the rules of the system but merely on the ordering of the transactions in order to provide assurances that an "electronic coin" cannot be easily double spent. This is described in more detail in section 11 of the paper where it says, "We consider the scenario of an attacker trying to generate an alternate chain faster than the honest chain. Even if this is accomplished, it does not throw the system open to arbitrary changes, such as creating value out of thin air or taking money that never belonged to the attacker. Nodes are not going to accept an invalid transaction as payment, and honest nodes will never accept a block containing them."

proof-of-work difficulty is determined by a moving average targeting an average number of blocks per hour.

  • Implementation detail: A moving average is not used. Instead, every 2,016th block has its reported generation time compared to the generation time for an earlier block, and the difference between them is used to calculate the average used for adjustment.

    Further, the average implemented in Bitcoin targets an average number of blocks per two weeks (not per hour as might be implied by the text). Other implemented rules may further slow adjustments, such as a rule that the adjustment can not increase block production speed by more than 300% per period, nor slow it by more than 75%.

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

  • Possible post-publication discovery: Although the Merkle Tree structure described in this section can prove a transaction was included in a particular block, there is currently no way in Bitcoin to prove that a transaction has not been spent except to process all subsequent data in the blockchain. This means the method described here cannot be universally used for reclaiming disk space among all nodes, as all new nodes will need to process all transactions.

8. Simplified Payment Verification

One strategy to protect against this would be to accept alerts from network nodes when they detect an invalid block, prompting the user's software to download the full block and alerted transactions to confirm the inconsistency.

  • Important Note: although software has been produced that implements some parts of this section and calls that Simplified Payment Verification (SPV), none of these programs currently accepts alerts from network nodes (full validation nodes) when invalid blocks have been detected. This has placed bitcoins in so-called SPV wallets at risk in the past.

10. Privacy

Some linking is still unavoidable with multi-input transactions, which necessarily reveal that their inputs were owned by the same owner

  • Post-publication invention: the revelation of a common owner for different inputs isn't necessary if owners often mix their inputs with inputs belonging to other owners. For example, there's no public difference between Alice and Bob each contributing one of their inputs towards paying Charlie and Dan than there is between just Alice contributing two of her inputs towards paying Charlie and Dan.

    This technique is known today as CoinJoin and software implementing it has been in use since 2015.

11. Calculations

The receiver generates a new key pair and gives the public key to the sender shortly before signing. This prevents the sender from preparing a chain of blocks ahead of time by working on it continuously until he is lucky enough to get far enough ahead, then executing the transaction at that moment.

  • Post-publication discovery: nothing about the receiver generating a public key shortly before the spender signs a transaction prevents the spender from preparing a chain of blocks ahead of time. Early Bitcoin user Hal Finney discovered this attack and described it: "Suppose the attacker is generating blocks occasionally. in each block he generates, he includes a transfer from address A to address B, both of which he controls.

    "To cheat you, when he generates a block, he doesn't broadcast it. Instead, he runs down to your store and makes a payment to your address C with his address A. You wait a few seconds, don't hear anything, and transfer the goods. He broadcasts his block now, and his transaction will take precedence over yours."

    The attack works for any number of confirmations, and is sometimes named the Finney Attack.


Disclaimer: the author of this document was not the first person to identify any of the problems described here---he has merely collected them into a single document.

Updates:

  • 2018-06-14: Link to the commit where Nakamoto changed the consensus convergence mechanism from greatest-height to most-work. Credit for commit archaeology to Gregory Maxwell.

  • 2018-06-14: A moving average is not used. Mentioned on an IRC channel where logging is disallowed.

  • 2018-06-14: Late key distribution does not prevent attackers from preparing forks, e.g. the Finney Attack. Mentioned by Kalle Rosenbaum on Twitter.

  • 2018-06-14: Inputs being spent in the same transaction does not necessarily lead to a privacy degradation thanks to Coinjoin. Mentioned by Chris Belcher in a GitHub comment.

@chris-belcher

This comment has been minimized.

Copy link

@chris-belcher chris-belcher commented Jan 29, 2017

Also:

10. Privacy

Some linking is still unavoidable with multi-input transactions, which necessarily reveal that their inputs were owned by the same owner

Multiple owners can co-operate to produce a single bitcoin transaction with multiple inputs owned by each of them. This is what coinjoin is based on and is used to improve bitcoin privacy today.

@zerotraction

This comment has been minimized.

Copy link

@zerotraction zerotraction commented Jun 28, 2018

Annotate the white paper or run a blackline.

@Janaka-Steph

This comment has been minimized.

Copy link

@Janaka-Steph Janaka-Steph commented Jan 6, 2019

Nakamoto expected all miners to be nodes but the software he released did not require all nodes to be miners.

This sentence could be clearer imo.

@andronoob

This comment has been minimized.

Copy link

@andronoob andronoob commented Dec 20, 2019

Although the Merkle Tree structure described in this section can prove a transaction was included in a particular block, there is currently no way in Bitcoin to prove that a transaction has not been spent except to process all subsequent data in the blockchain. This means the method described here cannot be universally used for reclaiming disk space among all nodes, as all new nodes will need to process all transactions.

The Merkle proof of a transaction cannot prove the validity of that transaction either, especially whether it's spending coins that never existed at all, which is equivalent to creating inflation out of thin air. Once everyone had "pruned" a lot of historical transactions, such invalid transactions will be indistinguishable with valid ones which had spent valid coins.

I saw that "proof (of spending a non-existing input) requires scanning the entire blockchain history" at first time here: https://en.bitcoin.it/wiki/User:Gmaxwell/features#Proofs
So, it's not my discovery...

@andronoob

This comment has been minimized.

Copy link

@andronoob andronoob commented Dec 20, 2019

In his whitepaper, Satoshi also wrote:

The incentive may help encourage nodes to stay honest. If a greedy attacker is able to assemble more CPU power than all the honest nodes, he would have to choose between using it to defraud people by stealing back his payments, or using it to generate new coins.

It's not explicit why the supposed attacker can only steal back his payments.

Once there's no honest full node (which kept the comlete blockchain data containing all historical transactions. whether this node is mining or not is irrelevant) any more, the attacker will be in fact able to alter the rules of bitcoin arbitrarily, including creating inflation (considering the issue described in my comment above).

Even if there're still honest full nodes (same definition as above), the attacker is still able to do more things than "stealing back payments", for example, he could stop bitcoin from functioning by refusing to include any transaction in his blocks. Once there's an extremely powerful entity who wishes so strongly that "bitcoin must die", it could become a real concern.

The attacker can also attempt to impose unwanted new rule set on bitcoin users by stopping/killing the original blockchain with such "empty block" attack. (considering the difference between soft-fork and hard-fork, there might also be different thresholds, since a hard-fork change requires the attacker to keep the victim chain "choked" with his "malicious empty block chain" and his supported chain functioning at same time) It's still not very clear how the bitcoin ecosystem could handle this situation. It's not very clear how the rule set of bitcoin should be updated either. In other words, it might be subjective that whether a fork of bitcoin blockchain is the "original" chain or "malicious" chain.

@andronoob

This comment has been minimized.

Copy link

@andronoob andronoob commented Dec 21, 2019

Just as a signature that matches a know public key can be used to enable a payment, the data that satisfies an known expression can also enable a payment.

Not really, as far as I know, a transaction without a signature (hash) covering the critical data (like recipients) could be easily tampered, for example, to change the recipient, since anyone else would be unable to distinguish between the original one and the tampered one.

In other words, once a "coin" (UTXO) became "unlocked" (valid TxIn), the bitcoin system does not provide any mechanism to restrict where could this coin go, unless the "destination" (TxOut) was covered by the signature (hash) of TxIn.

As far as I could remember, the "Pay-to-Hash" script was once useless before it was redefined into Pay-to-Script-Hash (P2SH), exactly due to this reason.

If you want to send some coins to a special address that has "predefined restrictions about where its coins could be spent to", as far as I know, it's not currently possible in bitcoin system.

There was also a proposal called "bitcoin covenants" which aimed to provide such missing functionality.

@jonatack

This comment has been minimized.

Copy link

@jonatack jonatack commented Jul 7, 2020

Great doc, Dave.

A few nits:
s/Application Specific Integrated Circuits/Application-Specific Integrated Circuits/
s/matches a know public key/matches a known public key/
s/satisfies an known expression/satisfies a known expression/
s/the adjustment can not/the adjustment cannot/

@andronoob

This comment has been minimized.

Copy link

@andronoob andronoob commented Sep 29, 2020

Although the Merkle Tree structure described in this section can prove a transaction was included in a particular block, there is currently no way in Bitcoin to prove that a transaction has not been spent except to process all subsequent data in the blockchain

Actually I think this description is confusing.

  1. What's "all subsequent data"? A blockchain is never complete, miners will always continue to extend the chain as long as there's any incentive. It seems that the "must process all subsequent data" requirement only makes sense in some case like validating proof-of-fund.

  2. Spent transaction can't be pruned directly either, unless all antecedent transactions are also fully spent. (https://bitcoin.stackexchange.com/questions/96600/is-merkle-tree-pruning-described-in-the-whitepaper-feasible-useful-if-not-woul) In this case it's actually all antecedent data (rather than all subsequent data) which must be processed to ensure that there's no malicious/inconsistent Merkle tree branch picking.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.