Skip to content

Instantly share code, notes, and snippets.

@harding
Last active November 1, 2024 16:48
Show Gist options
  • Save harding/dabea3d83c695e6b937bf090eddf2bb3 to your computer and use it in GitHub Desktop.
Save harding/dabea3d83c695e6b937bf090eddf2bb3 to your computer and use it in GitHub Desktop.

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. In the the original software, a simple menu item in the node GUI allowed toggling the mining function or or off.

    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 mine with their own nodes 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 known 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". Given that transactions often have more than one input and more than one output, the structure is not very chain-like; it's more accurately described as a directed acyclic graph (DAG).

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 an 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.

License: this errata document is released under the CC0 1.0 Universal Public Domain Dedication

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.

  • 2023-08-01: clarified a sentence about nodes not needing to be miners. Mentioned by Janaka-Steph in a GitHub comment.

  • 2023-08-01: the "chain of encumbrances" is more accurately described as a DAG. Mentioned by Mark "Murch" Erhardt in a GitHub comment.

@chris-belcher
Copy link

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
Copy link

Annotate the white paper or run a blackline.

@Janaka-Steph
Copy link

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
Copy link

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
Copy link

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
Copy link

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.

@andronoob
Copy link

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.

@carnhofdaki
Copy link

  1. Proof of Work
    a integeran integer?

@lurch
Copy link

lurch commented Nov 7, 2021

matches a know public key -> matches a known public key ?

@carnhofdaki
Copy link

@lurch thanks! - the last two typo fixes are already incorporated at https://gist.github.com/carnhofdaki/b70aa9638eeac75417c69142c853a7ff

@murchandamus
Copy link

One could also mention here that since transactions may have multiple inputs and output, the graph in which coins get moved forward is rather a directed acyclic graph of encumbrances than a "chain" of encumbrances. At least to me, chain implies that there is only one element at each height.

@ozomer
Copy link

ozomer commented Feb 28, 2022

satisfies an known expression -> satisfies a known expression

@SergioDemianLerner
Copy link

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.

In the pre-release of the Bitcoin code the block header field nBits actually counted the number of zero bits in the block hash. It was changed in the first release of the Bitcoin code.

@SergioDemianLerner
Copy link

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.

Bitcoin was launched with the addition of ExtraNonce rolling. Currently other methods to change the header are also used, such as nTime or nVersion rolling.

@LarryRuane
Copy link

This comment is about the white paper itself, not your errata.

Big-blockers love to quote the last few lines of the white paper (Conclusion, section 12):

They [nodes] vote with their CPU power, expressing their 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.

(I'm assuming that "CPU power" means PoW hashing.)

Big-blockers say this means only mining nodes matter.

Satoshi was vague or wrong here; a non-mining node also accepts blocks (adds them to its local copy of the blockchain) or rejects blocks -- and this matters because it allows the node's owner to know if they have been paid what they consider "real" bitcoin!

Also, miners could be said to "vote" among multiple valid branches, but not between valid and invalid branches. If 99% of the miners "vote" for BTC by extending its chain, while 1% of miners likewise "vote" for BCH, that "vote" is meaningless, it has no effect. This state of affairs is actually a reflection of the economic majority, a result, not the cause of anything.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment