Fraud Proofs Prototype

[tzdybal]

This is a tracking issue for everything related to fraud proofs. I'll link issues below.

ADR:

• Create ADR describing Single Round State Fraud Proofs  #617

Discussion:

• ISRs, fraud proofs in Cosmos SDK and deferred execution #132

Rollmint:

• Generate Fraud Proof after trigger #499
• Add fraud proof verification entrypoint in rollmint  #408
• Verify headers of Fraud Proofs in Light Clients #387
• Verify merkle proofs embedded in Fraud Proof state witnesses in Light Clients #388
• Investigate how optimint setups up a new proxy app connection #389
• Compare generated ISRs to block producer ISRs #385
• Trigger block fraud proof generation on state root mismatch #438
• Create tests for Fraud Proofs #335
• Define Fraud Proof data type #10
• Fraud proofs gossiping #4
• Fraud proof generation #6
• Gossip Fraud Proofs to P2P network after generation when needed #552

Cosmos-SDK:

• Add ability to generate block fraud proofs celestiaorg/cosmos-sdk#195
• Initialize state store using state witnesses in a block fraud proof celestiaorg/cosmos-sdk#196
• Import all SMT files into cosmos-sdk without any build errors celestiaorg/cosmos-sdk#231
• Implement a Single Round Fraudproof as a minimal integration test celestiaorg/cosmos-sdk#245
• Implement fraudproof generation mode in cosmos-sdk celestiaorg/cosmos-sdk#249
• Test stateless execution for cosmos-sdk baseapp using SMT-based fraudproofs  celestiaorg/cosmos-sdk#252
• Add fraudproof verification on a store level celestiaorg/cosmos-sdk#253
• Add fraudproof verification on a substore level celestiaorg/cosmos-sdk#255
• Export minimal pre-execution state from a fraudulent block instead of a post-execution state celestiaorg/cosmos-sdk#257
• Implement domain-specific trace writers for SMT multistore celestiaorg/cosmos-sdk#258
• Optimize state reversion in a SMT multistore celestiaorg/cosmos-sdk#259
• Transition fraud proof prototype from block fraud proofs to fraud proof with ISRs celestiaorg/cosmos-sdk#265
• Initialize the new app with a deep SMT instead of populating the empty SMT celestiaorg/cosmos-sdk#266
• Downgrade tendermint version to 0.34.21 since Tendermint v0.35 got dropped celestiaorg/cosmos-sdk#269
• Add new ABCI methods needed for Fraud Proof Generation celestiaorg/cosmos-sdk#271
• Add ABCI method needed for Fraud Proof Verification celestiaorg/cosmos-sdk#273
• Fraud Proof generation and partial verification using IAVL store cosmos-sdk-old#2
• Fraud Proof Verification using IAVL Deep Subtrees cosmos-sdk-old#5
• Move tracing to IAVL tree substore for Fraud Proof implementation cosmos-sdk-old#9
• Add expected valid app hash to Fraud Proof cosmos-sdk-old#11

Tendermint:

• Add ABCI methods for Fraud Proof Generation tendermint#4
• Modify Fraud Proof ABCI Interface to combine Trigger and Generate tendermint#62
• Add ABCI method needed for Fraud Proof Verification tendermint#68
• Modify Witness Data to have multiple trace operations and corresponding proofs tendermint#190