How are Algorand State Proofs any different from Tendermint's IBC/Light Clients?

Hello Algorand Community,

How are Algorand State Proofs any different from Tendermint’s Light Clients and IBC in how they work? So far this is how Tendermint’s light client algorithm works:

1. Node gets the header of the block containing the transaction to be verified. Let’s call it H
2.If H is already verified, go to step 9. Verified H → H’
3.Retrieve the previous header of H, i.e Previous Header to H → Hp
4.Obtain the block’s validator set data, which is part of the previous state, from the/a full node i.e Previous State’s block validator set data → Sp. This is necessary to calculate the validity and stake of the votes cast on H. These calculations will require not only a list of the validators, but also their mandates, ban status, and imprisonment records(Optional - depends on the chain)
5.Collect votes for H (pre-commit in Tendermint). Let’s call it C. Voting is done for a particular block, and because it is signed with a private key, it is not possible to tamper with which validator voted for which block. This can be simply verified with the public key and vote summary, so it doesn’t even matter where or who you received it from. If you combine the signature value, the voting source (or information that can deduce it), and the voter’s public key as C, then C is verified as is. Let’s call this C’. In the case of CodeChain, we put C in the next block header. As explained, C is verified just by its existence, so the next block header that corresponds to the source does not need to be verified, even if the block is fake. (C can be retrieved from literally anywhere.).
6.Hp is verified by recursion of all of these processes. Let’s call it Hp’.
7.Use Hp’ to verify Sp. Let’s call this Sp’. This is simple. Since the header contains the merkle root regarding the entire state, you can retrieve the merkle proof from the full node to verify it.
8.Use Hp ’, Sp’, and C ’to verify H. Let’s call this H’. Similar to PoW, after checking the basics of the header and the previous hash, the combination of Sp ‘and C’ verifies that the members of the valid validator set voted on H and verifies that more than 2/3 of the total when the stakes are counted. The important thing here is that you don’t have to know the staking rules for each chain, for example, when to ban and when to send to jail, and when and how to elect validators. That’s because Sp has been provided by the full node with all of those changes already applied and verified by Hp’.
9.If the header of the block containing the transaction/state that the node wanted to verify first is H’, go to step 10. If not, return recursion to step 6.
10.Let T be the transaction/state that the node wants to verify. In the final step, ask the full node for the Merkle proof needed to verify T.
11.Now the final step: calculate T and its Merkle proof to see if it is the same as the Merkle root written on H’.

What I consistently see from Algorand’s talk in the research channels is the idea of it using compact certs to verify state, but these compact certs in my understanding are just signatures using more verification compute. Another change is that, just swapping Tendermint’s voting process for Algorand’s Voting process shows there is nothing new with Algorand State Proofs. Although Codechain’s implementation for Tendermint(On Cosmos) blockchains still has overhead, they recently implemented a snapshot feature that reduces compute overhead. Or are there any unique features that come with Algorand State Proofs?

2 Likes

Is there a paper for Tendermint’s solution?

1 Like

Snapshot in Cosmos is similar Fast Sync in Algorand. I didn’t read through the Algorand State Proofs, I suppose this is a light client for Algorand.

Although both on the surface may accomplish the same thing, the inner-workings are completely different unless IBC also uses post-quantum Falcon signatures and State Proofs, which I doubt since Algorand participated in foundational development of Falcon signature scheme dating back to over a decade ago with foundational research of Chris Peikert (currently Head of Cryptography at Algorand) and more recently Zhenfei Zhang (ex-Algorand researcher). Flow as I understand it is Falcon signatures > State Proof (sign) > Compact Certificate > State Proof (verify). Falcon signatures and State Proofs offer post-quantum security at balanced compactness and processing speed.

Don’t discount the inner-workings. All cars have wheels (the idea is thousands years old since the invention of the wheel) but vehicles on wheels are all different and serve different purpose.

More resources:

Falcon Signatures: 1. https://falcon-sign.info/ 2. https://pqshield.com/falcon-a-post-quantum-signature-scheme/ 3. NIST Announces First Four Quantum-Resistant Cryptographic Algorithms | NIST
State Proofs: Algorand State Proofs Overview - Algorand Developer Portal
Compact Certificates: https://people.csail.mit.edu/nickolai/papers/micali-compactcert.pdf

2 Likes