State Proofs

Today, I wish to summarize the latest piece of technology available on Algorand: State Proofs.

The Goal. State proofs enable our blockchain to digitally sign any given message in a way that is easily verifiable by everyone. This is clearly a fundamental ability for a blockchain.

Wait a moment! I understand that a wallet 𝓌 can signify its approval of a message M via its own digital signature of M, SIG𝓌(M). But: what does it mean for the Algorand blockchain to digitally sign M?

Centralized Approaches. In a totally centralized blockchain, the chain’s digital signature of a message M can be chosen to be the digital signature for M of the “chain authority”. In a slightly less centralized chain, it may consist of the signatures for M of a small set of “chain authorities.”

Such centralized approaches are trivial to implement, but also insecure, because hacking one or a few authorities is far from impossible. Moreover, in a world where centralization is increasingly questioned, having one or a few authorities sign messages on behalf of the whole chain is simply not acceptable.

Our Approach. Algorand’s approach, as usual, is one of true decentralization. Namely, no matter the task, not only all who are willing to participate in it are allowed to do so, but they are also made technologically capable of doing so. For instance, even an ordinary computer can, if it so chooses, join our consensus process. Indeed, Algorand’s consensus has no computational hurdles and no elite clubs; rather, it is open to all willing participants. In state proofs, we take the same approach.

Our Notion. Our notion of a “blockchain signature” is conceptually so explained. Every wallet, willing to digitally sign messages on behalf of the whole chain, posts on chain a separate public verification key, and keeps private a matching, secret, signing key.

Let W be the set of such willing wallets and S𝓌 the stake collectively owned by all wallets in W. Every willing wallet 𝓌 in W approving the message M produces, as usual, its own individual signature of M, SIG𝓌(M). A collection of such signatures is a state proof for M if the wallets signing M collectively own a sufficient fraction of the total stake S𝓌.

The Problem. Of course, representing so much stake might require very many digital signatures, which would make state proofs unwieldy. For instance, if W consisted of a billion wallets, each owning a handful of algos, then a state proof would comprise hundreds of millions of signatures.

Our Solution. To solve the above problem, we dramatically reduce the number of signatures in a state proof for a message M, while keeping its ability to vouch that M is indeed backed by a sufficient fraction of S𝓌.

Assume that we want to prove that 70% of the total stake S𝓌 backs the message M. Then, we collect a larger set of signatures for M so that, collectively, indicate that a slightly larger percentage of S𝓌, for instance 80% of S𝓌 ,approves M. At this point, a special, cryptographic, selection process determines, in a provable way, which signatures of this larger set M become part of a special sample. This cryptographic selection process cannot be faked, even by an enemy who owns the computational resources of the entire planet Earth. The resulting special sample is indeed quite small. In fact, no matter how many signatures for M may be necessary to represent 70% of the total stake S𝓌, the sample contains at most 1400 digital signatures for M, each with its own proof of having passed the specified cryptographic selection.

In a sense, the 1400 selection proofs guarantee that, even though not all signatures are included, there indeed exist all the signatures necessary to prove that M is indeed backed by 70% of S𝓌.

In sum, a state proof is quite compact, secure, and super easy to verify.

Our Applications. State proofs are extremely useful. In particular, as we shall soon see, they enable

• the Algorand blockchain to become safe against quantum attacks,
• the construction of decentralized bridges between Algorand and other blockchains, and
• new nodes to join our consensus process without having to trust any “initializing” information.

Stay tuned!

Our Commitment. As mentioned above, state proofs underlie a host of new technologies. At the same time, they are themselves enabled by other technologies, such as Falcon, that we have already made available on our chain and to the entire ecosystem. Developing such a tight tapestry of technologies is as beautiful as it is necessary. The Blockchain is a worthy aspiration. But this aspiration must be sustained and realized by true technology.

Rest assured that, at Algorand, we are committed to providing the best technology for powering the greenest, most secure, most decentralized, and most efficient, public blockchain.

GO ALGORAND!

More? If you are interested in learning more about state proofs and how they fit in Algorand’s Technology Park, here are some suggested readings and materials:

• Algorand State Proofs; Noah Grossman, Sr Product Manager Blog
• Compact Certificates of Collective Knowledge; Micali et al. IEEE S&P 2021 Paper
• Post Quantum Algorand and State Proofs; MIT Bitcoin Expo 2022; Chris Peikert -Head of Cryptography Presentation
• Compact Certificates of Common Knowledge; IEEE S&P 2021; Riad S. Wahby — Cryptography Researcher Presentation
• Algorand State Proofs; ETH Denver 2022; Rotem Hemo — Director of PM Presentation
• Securing Cross Chain Bridges With Algorand State Proofs; Consensus 2022; Noah Grossman, Sr PM Presentation
• Subset-Sum Hash Specification Specification
• Subset-Sum Cryptanalysis Cryptanalysis