Cambrian Explosion of Cryptographic Proofs
The transformative potential for scalability, transparency, and privacy
TL;DR
- Cryptographic proofs validate computations and improve transaction integrity in blockchain networks.
- Layer-two (L2) blockchains use cryptographic proofs for scalability by generating verifiable proofs of aggregated transactions.
- Zero-Knowledge Proofs (ZKPs) verify truth without revealing extra information, but their use for privacy varies.
- Cryptographic proofs involve technical aspects like arithmetization and low-degreeness enforcement.
- With blockchain technology’s maturation, one type of cryptographic proof is likely to become dominant, promoting scalability, transparency, and privacy.
Note: This article is based on a talk by Professor Eli Ben-Sasson, co-founder and president of StarkWare, at the 13th Bar Ilan (BIU) Winter School on Cryptography. The BIU Winter School focused on recent advances in cryptography and blockchain technology. The lecture given by Professor Eli Ben-Sasson can be found here.
Integrity was defined by C.S. Lewis as the act of “doing the right things even when no one is watching.” In the context of blockchains, cryptographic proofs are used to ensure the exact same thing — making sure that some computational processes were done right even when no one was watching.
In this article, we’ll look at cryptographic proofs — what they are, how they are used in blockchain, and some of the significant differences between implementations. Let’s start with a definition.
What are cryptographic proofs?
Cryptographic proofs are a set of mathematical and cryptographic protocols that can be used to assert the integrity of computations.
A beautiful example of the kind of things that cryptographic proofs can do is described in the fundamental 1991 paper titled “Checking Computations in Polylogarithmic Time” by L. Babai, L. Fortnow, L.A. Lewin, and M. Szegedy, the authors presented a protocol in which “a single PC can monitor the operation of a herd of supercomputers with powerful but unreliable software and untested hardware.” This means that a machine with limited computational capacity can assert the integrity of computations made by a set of computers with far greater computational power, even if the party controlling those computers is malicious, or incentivized to misreport the output of those computations.
How are cryptographic proofs used in blockchains?
The past decade has witnessed a Cambrian explosion of semi-practical and practical proof systems, with various applications that ensure privacy, security, and integrity of computation. And, although integrity is needed in web2 as much as its needed in web3, for various reasons all products that use general purpose cryptographic proof systems can be found within web3, on blockchains, due to the open and transparent nature of blockchains and their preference for mathematical integrity over human-based integrity. To understand how proofs help scale blockchains we need to first recall how blockchains work.
Today, when we send a transaction on a blockchain like Solana, Ethereum, or Cosmos, each and every validator in the network receives the transaction and executes it. This quickly becomes inefficient. As decentralization grows, the compute resources used for including every transaction in the network’s history increases linearly with the number of active validators.
Several projects (such as Aztec, Starknet) aim to solve this scalability problem using cryptographic proofs. They are known as Layer 2 Validity Rollups because they sit on top of the Layer 1 blockchain (e.g Ethereum). The idea behind these L2 rollups is that they rely on cryptographic proofs to confirm the integrity of computations done off-chain, and the validity of updates to state and transaction sets. The ability for a long computation to be verified to have been executed with integrity represents a fundamental paradigm shift in throughput for distributed networks. Instead of naively re-executing each computational step, a network of many machines can simply verify them. There is no need for supercomputers — these can be regular weak computers.
This verification of the integrity of vast computations is performed by the reliable nodes of the Layer 1 network (such as Ethereum). In this case, and using the prophetic words of the 1991 paper mentioned above, the validators in the L1 network take the role of the “single reliable PC,” and the L2 prover is a supercomputer of sorts that, remarkably, achieves utter integrity and reliability despite being executed on untested hardware and possibly unreliable software.
The Cambrian explosion of cryptographic proofs is about the ever-increasing usage of these systems in blockchains, and the proliferation of different cryptographic protocols that implement these proofs. Below we can see a visualization of many projects currently being used in web3.
The above projects use only a tiny fraction of cryptographic proof systems that are known to us (at least in theoretical implementations).
Comparing Systems
Because there are so many options, it’s important to understand the pros and cons of each implementation. Many of the details are highly technical, but understanding them is important to understanding which ones may lead to the next generation of blockchains and L2s.
Zero-Knowledge Proofs: Scalability versus Privacy
You’ve probably heard (quite often) projects throwing around the term “Zero-Knowledge” proofs (or ZKPs). For all the catchiness of the phrase, and the potential of zero-knowledge proofs for privacy preserving blockchains, most web3 L2 validity rollups do not use proofs that have the cryptographic property known as “zero knowledge”, but rather rely on the scalability attributes of cryptographic proofs. Let’s talk briefly about privacy and scalability in cryptographic proofs.
ZKPs are proofs that allow a party to verify that a particular computation was executed correctly, without revealing the inputs that were consumed by that computation (e.g., passwords, financial details of transactions, medical data, etc.) As a result, on top of a significantly reduced cost of verification (inherited from the properties of cryptographic proofs), we gain privacy.
It’s important to understand exactly what a project means when they say they use ZKPs. While most blockchain-based projects built on cryptographic proofs claim their technology is “based on ZKPs,” in reality, their solution has no privacy considerations in play.
In a modified visualization of the above image, we can see that most of the projects are more focused on scalability than privacy.
Let’s next explore three more technical concepts all of the proofs use: arithmetization, enforcement of low-degreeness, and cryptographic assumptions.
What is arithmetization?
When looking at a set of computations that a system needs to prove, it makes sense to convert these computational problems into algebraic problems. Arithmetization in cryptographic proofs refers to the process of representing mathematical concepts and operations using arithmetic operations on finite fields.
At a high level, this means representing any statement as an algebraic equation, i.e., a polynomial. The process of converting computational problems into such algebraic problems is known as a “reduction” in the lingo of computer science, and an illustration is given in the following figure.
The reason arithmetization helps with scalability is that we can boost the likelihood of catching a breach of integrity once things are phrased with algebra and polynomials. To understand the magic of polynomials and their usefulness in proofs, best to work out the STARK 101 course or read this post.
Surveying the different proof systems out there, one differentiating factor is the way they perform arithmetization. Some may use modular arithmetic over integer rings (RSA rings), others may use elliptic curves and/or more complex methodologies (lattice-based cryptography, code-based cryptography, and multivariate polynomials).
Low-degreeness
All cryptographic proof systems have some form of low-degreeness enforcement, which is a crucial differentiating factor among them.
Low-degreeness enforcement refers to the process of ensuring that the polynomials (algebraic equations that are generated as part of the arithmetization process) are of a degree less than a certain threshold. (Just a reminder that the degree in a polynomial is equal to the largest power of a term appearing in it.)
Low-degreeness enforcement is necessary for integrity and security. As described above, the probability of erroneously accepting a false proof is related to the degree of polynomials chosen. Moreover, low-degree polynomials are used in these systems because they have some nice mathematical properties that make them more efficient.
A polynomial commitment scheme (PCS) is a cryptographic protocol that allows for efficient and verifiable computation on polynomials. It enables one party, called the committer, to commit to a polynomial without revealing its full details, while another party, called the verifier, can later verify the properties of the polynomial commitment.
Different proof systems use different PCSs to create and verify proof. STARKs and Risc0 use the Fast Reed-Solomon Interactive Oracle Proof (“FRI”) commitment scheme, while Groth16 and PLONK use the KZG commitment scheme. Generally, the differentiating factors between these commitment schemes are the cost of creating the proof, verifying the proof, and the size of the proof.
See the above image for the pros and cons of the different systems. The STARK proof system uses the FRI protocol to enforce low-degree polynomials. Under this system, the prover iteratively interacts with the verifier and commits to new polynomials such that the degree of each new polynomial is half the previous one. The PLONK system uses polynomial commitments based on elliptic curve mathematics (for example, KZG).
Moreover, some systems may require a trusted setup. A trusted setup is an arrangement under which specific secret parameters are to be generated. The challenge in these cases is that the pre-image of these parameters must remain private. If not, then the whole proof system is vulnerable, and the generation of a false proof becomes possible.
Generally, special trusted setup “ceremonies” are organized in which multiple parties privately create random elements combined to get the final parameters. If even a single party from these successfully destroys the random elements it submitted, then the setup can be considered secure.
Cryptographic Assumptions
Finally, any other cryptographic assumptions these systems use are also essential to track.
For instance, some of these uses rely on elliptic curve mathematics (such as BulletProofs and Halos) or “knowledge of exponent” (such as Groth16, PLONK, etc.), which are quantum-computer breakable.
On the other hand, others use collision-resistant hashes which are quantum-computer resistant (such as STARKs, ZKBoo, etc.).
Conclusion
As we can see from the above discussion, a vast array of cryptographic proofs can be used to achieve scalability and transparency (or privacy). While some proofs might be very convenient in use for short proofs (such as Groth16), some other systems are better off in large computations (such as STARKs, in the opinion of Prof. Ben-Sasson). However, as the ecosystem matures, we will see one type of cryptographic proof used extensively.
May the best system win!
