The purpose of this thread is to discuss and gather information about fraud proofs.

I am still working through and trying to wrap my head around many of these concepts, so I intend this thread to be a sort of work in progress. Hopefully others may find this useful, and can share ideas and information about fraud proofs.

I’m hoping to better understand and develop ideas such as:

Also relevant are @deadalnix’s proposals on Merklix Trees:

http://www.deadalnix.me/2016/09/24/introducing-merklix-tree-as-an-unordered-merkle-tree-on-steroid/

http://www.deadalnix.me/2016/09/29/using-merklix-tree-to-checkpoint-an-utxo-set/#more-455

http://www.deadalnix.me/2016/11/06/using-merklix-tree-to-shard-block-validation/

And some discussion in @deadalnix’s BUIP037 proposal thread: https://bitco.in/forum/threads/buip037-hardfork-segwit.1591/

---------------------------

Many of the data structures in Bitcoin revolve around proving things:

The data structure of the block chain can also be used to prove things to others who do not have all the blockchain data. For example, the existence of a transaction in the block chain can be proven to exist with only the block headers and a Merkle path pointing to the transaction. SPV clients currently use this method to check that their relevant data is included in the block chain.

Other things are more difficult to prove. For example, proving that a particular piece of data is absent from the block chain is more difficult. If a miner wanted to include a transaction in a block where the input did not exist, the only way to prove this fraud, with the current block chain, would be to scan the entire block chain to to show that the input is absent. SPV wallets rely on the fact that other full nodes are checking the validity of the blocks that are mined to have confidence that this type of fraud is not occurring.

The concept of Compact Fraud Proofs is to be able to prove, as efficiently and possible, all the different types of fraud to clients who do not have a full copy of the block chain. The reason to do this is to create an asymmetric advantage for honesty over fraud.

Currently the security of SPV clients relies on the assumption that the majority of has power is honest. This is a fairly strong security guarantee, a collusion between the majority of miners seems unlikely. But with compact fraud proofs we can do even better. In a world where compact fraud proofs are in use, the light nodes only rely on the assumption that one honest node exists who can provide the compact fraud proofs.

Two things need to be done to move toward a system where Compact Fraud Proofs are practically implemented:

I am still working through and trying to wrap my head around many of these concepts, so I intend this thread to be a sort of work in progress. Hopefully others may find this useful, and can share ideas and information about fraud proofs.

I’m hoping to better understand and develop ideas such as:

- What is the purpose of fraud proofs, what are the goals to aim for
- Looking at different options for changes to the protocol would be best to enable better fraud proof capabilities
- How can they be incentivised, are there business models that can be enabled to provide fraud proof services to light nodes

Also relevant are @deadalnix’s proposals on Merklix Trees:

http://www.deadalnix.me/2016/09/24/introducing-merklix-tree-as-an-unordered-merkle-tree-on-steroid/

http://www.deadalnix.me/2016/09/29/using-merklix-tree-to-checkpoint-an-utxo-set/#more-455

http://www.deadalnix.me/2016/11/06/using-merklix-tree-to-shard-block-validation/

And some discussion in @deadalnix’s BUIP037 proposal thread: https://bitco.in/forum/threads/buip037-hardfork-segwit.1591/

---------------------------

Many of the data structures in Bitcoin revolve around proving things:

- The proof of work proves that real-world resources were expended associated with a block header hash
- The hash chain of block headers proves that all blocks in the chain are linked with the proof of work of the chain tip
- The merkle tree of transactions in a block can be used to prove, in compact way, that a particular transaction exists within that block.
- The signature data associated with a transaction proves that the creator of the transaction has control of the necessary private key

The data structure of the block chain can also be used to prove things to others who do not have all the blockchain data. For example, the existence of a transaction in the block chain can be proven to exist with only the block headers and a Merkle path pointing to the transaction. SPV clients currently use this method to check that their relevant data is included in the block chain.

Other things are more difficult to prove. For example, proving that a particular piece of data is absent from the block chain is more difficult. If a miner wanted to include a transaction in a block where the input did not exist, the only way to prove this fraud, with the current block chain, would be to scan the entire block chain to to show that the input is absent. SPV wallets rely on the fact that other full nodes are checking the validity of the blocks that are mined to have confidence that this type of fraud is not occurring.

The concept of Compact Fraud Proofs is to be able to prove, as efficiently and possible, all the different types of fraud to clients who do not have a full copy of the block chain. The reason to do this is to create an asymmetric advantage for honesty over fraud.

Currently the security of SPV clients relies on the assumption that the majority of has power is honest. This is a fairly strong security guarantee, a collusion between the majority of miners seems unlikely. But with compact fraud proofs we can do even better. In a world where compact fraud proofs are in use, the light nodes only rely on the assumption that one honest node exists who can provide the compact fraud proofs.

Two things need to be done to move toward a system where Compact Fraud Proofs are practically implemented:

- Make changes to the Bitcoin block chain and/or add consensus rules to make all the necessary types of compact fraud proofs possible.
- Add mechanisms to enable a market of fraud protection providers and consumers.

- Different data structures to enable compact fraud proofs (eg Merklix trees)
- How to enable a market for fraud protection and compact fraud proofs
- How fraud proofs, or similar concepts, can help nodes with data pruning and sharding
- The relationship between compact fraud proof capabilities and UTXO. Do we need better fraud proof capabilities before implementing UTXO commitments, or do UTXO commitments provide many similar benefits as Compact Fraud Proofs
- Different types of fraud, and how this influences incentives. For example, there is a difference between proving that the individual coins are properly controlled by an individual user of the system, versus proving that the overall system preserves monetary properties such as scarcity.

Last edited: