Trustless faster catchup using State Proofs

[algoanne]

Problem

It is critical to the safety of the network that participating nodes use a trustless catchup - otherwise they may be working off an incorrect ledger.

A trustless catchup currently involves getting all historical blocks starting at the Genesis round and verifying them one by one. Unfortunately, the current block-by-block catchup process is quite slow.

A trust-ful alternative is "fast catchup", which some people use. This is much faster, because it simply provides the node a snapshot of the ledger from a recent round.

A faster trustless solution would increase the security of the network by making it easier for node runners to use the trustless option. With the rise in participators in the ecosystem, this is doubly important at this juncture.

Solution

We are currently introducing State Commitments (separate from this work), which is a a commitment to the ledger state each round. The State Commitments (the hash of the root of the trie) is included in the block, which is included in the State Proof.

Now instead of validating block by block, a SP-based catchup could validate State Proof by State Proof, starting with the first State Proof that includes a State Commitment. Then a snapshot of the ledger at a recent round can be verified against the State Commitment for that round.

This should be much faster than regular catchup, while remaining entirely trustless. Part of the speed up is that State Proofs are every 256 rounds. Another part is that block-based catchup requires updating the database after verification, before being able to verify the next block. SP verification can just go one after the other. This also doesn't require downloading all the blocks, only 1/256 of them.

We expect this to become the new standard catchup for participation nodes. For nodes used to populate Indexers (or in general for those wishing to get a record of all historical transactions), the slower catchup will still be useful.

Additional Considerations/Notes

We also want this catchup to be post quantum secure.

This new catchup will require starting at a new initial round. Instead of the Genesis round, it will be roughly the first round that includes State Commitments (EDIT: could be any round starting from the first block that has State Proofs). This is an equivalent trust assumption.

Note also that this SP-based catchup will grow slower the more rounds there are, just like the block-by-block catchup.

State Proofs attest to every 256 rounds. However, the State Proofs are not necessarily included in precisely every 256th block. For this new SP-based catchup, we will need either some kind of Indexer finding the next State Proof round, or just a list/file of them in S3. The historical blocks don't have to come from nodes, they can come from anywhere since there is no trust as long as the first one is the right one.