Improving the ability of SPV clients to detect invalid chains

fraud proofs.md

SPV clients lack the ability of full nodes to detect whether or not a chain provided to them by another source complies with the rules of the Bitcoin protocol.

SPV clients can connect to multiple full nodes in the hope that at least one of the nodes is honest and will provide them with the best valid chain, however situations may arise where the non-compliant chain contains more proof of work than the compliant chain. In this situation, there is no way for the honest full node to signal to an SPV client that it should disregard the chain with more proof of work.

Fraud proofs are a technique which provide honest full nodes the capability to conclusively demonstrate that chain is invalid regardless of the amount of proof of work backing the invalid chain.

If Bitcoin nodes implement the ability to create, propagate, and verify fraud proofs, the security of SPV clients will be improved.

Assumptions and Definitions

Validity criteria

The various criteria that determine whether or not a given block in the block chain is compliant with the Bitcoin protocol can be grouped into the following categories:

• Block header criteria
• Transaction criteria

Block header criteria includes whether the block is constructed with proper syntax, and if it contains the specified proof of work.

In addition to having a valid header, each transaction in a block must be individually valid. The criteria that determine transaction validity can be grouped into the following categories:

• Stateless criteria
• Stateful criteria

Stateless criteria consider the transaction in isolation, with no outside context. Examples of these criteria include:

• Correct syntax
• All input script conditions satisfied
• Total output value less than or equal to total input value

Stateful criteria require examining the transaction in a larger context to determine its validity. Stateful criteria consist of:

• All inputs in the transaction exist in the block chain
• None of the inputs in the transaction have been spent by an earlier transaction
• (generation transactions only) Total output value is less than or equal to the sum of the block reward and transaction fees in the block

Proof participants

Prover

An entity with a complete copy of the block chain and the ability to validate all protocol rules

Verifier

An entity which relies on verifies and acts on the proofs provided by the prover.

For the purposes of the proofs described here, the verifier is assumed to have the following resources and capabilities:

• A complete set of block headers from the genesis block to the block being proved
• The ability to independently verify all block header criteria
• The ability to independently verify all stateless transaction criteria
• The ability to parse a complete block

Proofs possible within the existing Bitcoin protocol

Block header criteria violation

No fraud proof is required in this situation, because the verifier should be capable of detecting this without the assistance of the prover.

Invalid transaction (stateless criteria violation)

If a block contains a transaction that is violates one of the stateless criteria, a prover constructs a fraud proof consisting of the following:

• The header of the invalid block
• The invalid transaction
• A subset of the invalid block's merkle tree containing the minimum of number nodes which demonstrate that the invalid transaction exists in the tree (existence proof)

The verifier determines that the block in question is invalid if it observes the following properties are true for the proof:

• The transaction violates a Bitcoin protocol rule
• The existence proof includes the invalid transaction
• The root hash of the existence proof matches the merkle root in the block header

Invalid transaction (input already spent)

If a block contains a transaction which spends an input which has already been spent by a transaction appearing earlier in the block chain, a prover constructs a fraud proof consisting of the following:

• The header of the invalid block (b1)
• The invalid transaction (t1)
• An existence proof demonstrating that t1 is included in b1 (e1)
• The header of the block containing the original spend of the double-spent input(b2)
• The original spending transaction (t2)
• An existence proof demonstrating that t2 is included in b2 (e2)

The verifier determines that the block in question is invalid if it observes the following properties are true for the proof:

• e1 includes t1
• b1 references the root hash of e1
• e2 includes t2
• b2 references the root hash of e2
• b2 is an ancestor of b1
• t1 and t2 have at least one input in common

If b1 and b2 are the same block, a variation of this proof is used which shows that t2 is to the left of t1 in the merkle tree.

Invalid transaction (incorrect generation output value)

If a block is invalid because the generation transaction output is too high, the fraud proof is the block itself.

A verifer determines the block is invalid if the total output value of the generation transaction exceeds the difference between the sum of all outputs in the block and the sum of all inputs in the block by more than the specified block reward.

Invalid transaction (input does not exist)

If a block is invalid because it contains a transaction spending an input that does not exist in the block chain, the fraud proof is the entire block chain. No shorter proof is possible within the confines of the existing Bitcoin protocol.

Proofs requiring additions to the Bitcoin protocol

In order to reduce the size of the fraud proof needed to show that a transaction input does not exist, additional information must be added to Bitcoin blocks to indicate the block which is the source of each outpoint used by every transaction in the block.

Proof tree

The structure of a Bitcoin block is modified as follows:

1. The merkle tree as it is currently specified is called the "transaction tree"
2. A second tree containing source block information is called the "proof tree"
3. The merkle root of a block is defined by the node whose left child is the transaction tree, and whose right child is the proof tree.

Leaf nodes in the proof tree consist of (outpoint, block hash) tuples, where outpoints are (transaction hash, output index) tuples and block hashes identify the block containing the specified transaction hash.

Leaf nodes in the proof tree are ordered first by transaction hash, then by output index.

One additional validity criteria is added to the transaction tree:

Leaf nodes in the transaction tree are ordered by transaction hash.

The addition of a proof tree to the block means the proof of non-existence for a transaction input can is at most the size of a single block rather than the size of the entire block chain.

Invalid transaction (input does not exist) (old blocks)

If a block is invalid because it contains a transaction spending an input that does not exist in the block chain, a prover constructs a fraud proof consisting of the following:

• The header of the invalid block (b1)
• The invalid transaction (t1)
• An existence proof showing that b1 contains t1 (e1)
• An existence proof showing that b1 contains the proof tree leaf node corresponding to the non-existent input (e2)
• The block referenced by the proof tree, if it exists (b2)

The verifier determines that the block in question is invalid if it observes the following properties are true for the proof:

• e1 includes t1
• b1 references the root hash of e1
• The root hash of e1 is the same as the root hash of e2
• The leaf node contained in e2 is one of the outpoints referenced by t1
• The outpoint referenced in e2 does not exist in b2, OR
• b2 is not an ancestor of b1

Invalid transaction (input does not exist) (new blocks)

Proving that a transaction does not exist in a block which contains a proof tree does not require the contents of the entire block.

Since transactions in those blocks must be ordered by their hash, an existence proof containing two adjacent transaction, one with a hash less than than the non-existent transaction, and one with a hash greater than than the non-existent transactions is sufficient

Missing proof tree item

If a block is invalid because a required item is not located in the specified position, a prover constructs a fraud proof consisting of the following:

• The header of the invalid block (b1)
• The transaction for which a proof tree node is missing (t1)
• An indication of which input in t1 is missing from the proof tree (o1)
• An existence proof showing that b1 contains t1 (e1)
• An existence proof showing that the proof tree contains two adjacent leaf nodes, one with outpoint less than o1, and one with an outpoint greater than than o1. (e2)

The verifier determines that the block in question is invalid if it observes the following properties are true for the proof:

• e1 includes t1
• b1 references the root hash of e1
• The root hash of e1 is the same as the root hash of e2
• o1 is one of the inputs of t1
• The lowest leaf node in e2 is lower than o1
• The highest leaf node in e2 is greater than o1
• o1 is not one of the leaf nodes in e2

A similar proof can be constructed to demonstrate that the transaction in the transaction tree are not properly ordered.

Alternate proof tree implementation

Although changing the merkle structure of Bitcoin blocks to add proof trees results in the smallest proofs, this is a very intrusive change that would require a mandatory update of all software which parses Bitcoin blocks.

The proof tree root can be committed into blocks via a backwards-compatible way by specifying that the first output of each generation transaction must use an OP_RETURN script to push the merkle root of the proof tree.

Blocks adhering to these rules are valid Bitcoin blocks under current rules, so deploying fraud proofs via this method is easier to implement.

The fraud proofs described above would require the following modifications:

• Every proof that requires a block header would also require the generation transaction in addition to the block header
• Existence proofs would need to be extended to cover both the generation transaction and the transaction of interest in the specified block

Where does this idea "a dishonest chain with more proof of work" come from? It seems to run counter to the whole value proposition of Bitcoin. The presumption is that proof of work creates honesty... right?

It seems to me that this proof tree is very expensive to make. It would mean that every full node must reconstruct the full proof tree with every UTXO for every block.

It might make sense to use a "fillfactor" for the proof tree, and allow empty spots.

This makes the proofs larger, but the recomputation less intensive.

The presumption is that proof of work creates honesty... right?

Looks like he changed the wording already, but proof of work does not prove honesty. An attacker can build up 50% of the hashpower and wreak havoc on the system. Proof of work is only proof of work, not proof of honesty.

In any case, the majority chain doesn't need to be dishonest for it to be a problem. Let's say bcash was able to convince a majority of miners to switch to it. In that case, SPV clients would all implicitly follow that chain, even tho the owners of those clients might not want to. Their clients wouldn't know the rules have been changed. Fraud proofs can allow honest nodes to inform other nodes that the majority chain is breaking the rules. This is absolutely critical if we want it to be safe for a large proportion of bitcoin users to only use SPV clients.

For example, if 90% of users used SPV clients and a majority bcash split happened, some large percentage of economic activity (probably less than but close to 90%) would start happening on the bcash chain. Users would be selling products and services and receiving bcash in return rather than btc (which is what they expect to receive). This would put a lot of pressure on people to just accept bcash as the new norm and accept any loss of security that entails. Automatic rule changes like that should be prevented - rule changes must be a manually opted into process on an individual level. That's the only way to escape the occasional tyranny and stupidity of the majority.

There is also stateful criteria for block headers. For example, the previous block hash. Also more importantly, the total size of the transactions in the block is stateful - since an SPV node won't have that set. You need some way to prove the block is within size limits.