Fraud proofs for SPV using spend tree synchronization

In a previous article, we saw how Bitcrust uses a spend tree for order verification which can improve concurrency and performance during peak load. Here we explore the possibility of adding Fraud Proofs to SPV using synchronization of this same spend tree.

SPV and Fraud Proofs

The Bitcoin paper introduces Simplified Payment Verification (SPV) as method of scaling Bitcoin, by allowing nodes to operate securely without the need for full blocks.

The trick is the Merkle Tree: This allows verifying the inclusion of a transaction in a block by downloading and verifying only the branch of the tree containing the transaction. The mechanism is well explained in the paper

The paper also alludes to protecting against invalid blocks by the use of alerts, later dubbed Fraud Proofs. If honest miners detect an invalid block, they could proof the invalidity to SPV nodes which would bring their security on par with full nodes.

Unfortunately, Fraud Proofs have been proven tricky and without them, the SPV method of scaling bitcoin is widely considered insecure and has mostly been abandoned. Although I do not agree with this assessment (as explained below), I would like to propose a "Fraud Proof SPV Node" or "FSPV" that could solve the Fraud Proof problem with a small additional overhead.

Synchronizing the Spend Tree

To allow for Fraud Proofs, FSPV nodes will synchronize and verify the spend tree. The spend tree is a data structure that Bitcrust uses to track the full transaction graph of the blockchain. It contains a pointer to each transaction, and for each input being spent, a pointer to the output.

The on-disk structure that Bitcrust uses, relies on locally valid file pointers. To synchronize it between nodes, we need to use full transaction IDs. To minimize bandwidth we can use a compression scheme like the one used in BIP 152 Compact Blocks to compress the TXIDs of spend output transactions. The TXID of the transactions in the block cannot be compressed as TXID compression relies on the TXID already being known by the node.

This will allow synchronizing a typical block for about ~80kb.

Without using input or output scripts, an FSPV can then cheaply verify order and the merkle root.

Transactions as Fraud Proofs

FSPV nodes do not verify the transaction signature scripts, syntax or amounts except for the transactions they are interested in.

If honest miners detect an invalid transaction in a block they can simply broadcast the invalid set of transaction to FSPV nodes using ordinary protocol messages (possibly amended with an !important flag). These transactions proof invalidity of the block and allows the FSPV node to reject it.

With this method, most invalid blocks can be detected and proofed, including wrong Coinbase block rewards, invalid syntax and invalid signatures.

Absent Transaction Attack

The tricky frauds to proof, are not covered this way. An attacker can include a TXID of a non-existent transaction in the block. Such absence cannot be proofed as there is no invalid transaction to broadcast.

Such attack can be mitigated using Fraud Hints; an honest miner can simply broadcast the TXID as a missing transaction.

With ordinary SPV, such hints are infeasible as they are cheaply faked and require the SPV node to download the full block to verify the hint. This way SPV nodes can be trivially forced to download all full blocks, removing their advantage.

This is where the spend tree of FSPV comes to rescue: As an FSPV maintains the full transaction graph, all it needs to do on retrieval of a Fraud Hint is taint the tree. It can simply mark the transaction with a simple bit-flag in the spend tree, and propagate the taint-bit through all its descendants. Whenever an FSPV node retrieves a tainted transaction, it knows it needs the corresponding Fraud Hinted transaction in order to consider it valid.

The power of FSPV lies in the fact that processing a hint is virtually cost free, and disproving it comes at the cost of only a single transaction. This means that prevention of DoS through excessive false Fraud Hints can be dealt with simply by banning nodes using the banscore per peer model that is also used for other DoS protection.

A more sophisticated model is also possible and planned for Bitcrust. Instead of a banscore, the node can maintain a more general cost/benefit model for each peer. With such model it is possible to weight Fraud Hints and ensure that a lonely Fraud Hint from an otherwise worthless or unknown peer can be treated as insufficient for tainting.

Do we need Fraud Proofs?

Contrary to popular believe, Fraud Proof SPV and Full Nodes are not significantly more secure then SPV nodes.

Full Node Security and Fraud Proofs protect against the mining majority including and accepting blocks with invalid transactions as they reject them and happily follow the valid minority chain.

Unfortunately, this is a rather false sense of security as the minority chain is not secure. The attacking majority can trivially attack the chain by withholding/releasing blocks, making every transaction a gamble regardless of confirmations, and making everything for sale for Bitcoin trivially up for grabs. In the scenario where the most-worked chain is invalid, securely transacting is no longer possible, and Bitcoin will be worthless.

The minority chain ever being more valuable is almost impossible as a withholding/releasing attack does not reduce a miner's bitcoin income, so in that scenario, attacking the minority chain would actually increase their income.

Even a change of PoW function would provide little help, for if we cannot rely on the multi-million dollar incentives of the miners of this PoW, why would anybody give a dime for a Bitcoin with another PoW, which would be much cheaper to compromise?

Bitcoin cannot function with the mining majority acting against it; there is no PoW security without reliance on the financial incentives of the mining majority no matter how centralized it may be.

Once we understand and embrace Bitcoin's powerful security model, we can also see the strength of ordinary SPV: The only thing that matters for a user is whether his transaction is stored in a block (verified by the merkle branch), and whether it is buried under enough PoW (verified using the headers). Any other verification, is mostly redundant with Bitcoin having value in the first place!

I am afraid that the current stagnation and abandonment of Bitcoin's original scaling model (well explained in Satoshi's first answer), is not induced by the absence of Fraud Proofs, but instead by a misunderstanding of Bitcoin's security and scaling model.

Conclusions

This article does not aim to structurally cover the full attack surface, nor does it provide detailed solutions; it should serve as an initial exploration of the possibilities of Fraud Proof SPV nodes using the spend tree.

I am hoping that this exploration puts more nails in the coffin of the fallacy that Bitcoin cannot scale on-chain using the original plan.

Maybe this can trigger us to finally stand together behind removing or structurally solving (with one of the many good dynamic proposals) the max_block_size issue, that is holding back Bitcoin's growth, blocking further developments like malleability fixes, and splitting the community.