Fraud provable staking

[adlerjohn]

Summary

The staking logic for the Celestia app (i.e. the PoS logic for the Celestia chain) must be fraud-provable with known-bounded cost. The Celestia specifications propose a simple state model to allow for this, however the current Cosmos SDK staking module does not allow for bounded-cost fraud proofs and is quite different.

Proposal

Modify the Cosmos SDK staking module to conform to as much of the specification as needed so as to be bounded-cost fraud-provable. Specifically, a linked list of the priority queue of validators must be implemented. In addition, anything else that involves iteration over an unbounded number of entries must be removed.

Tasks

• Update to upstream Update from upstream #27
• Implement linked list (add next field for linked list to validator struct, manage head) Initial work on fraud provable staking #29
• Modify validator, delegation, and account structs to fully match spec
• SMT migration Replace IAVL+ with SMT #6
• Intermediate state roots Keep track of and return intermediate state roots to be included in the block #8