This blog post begins a series exploring the differences between three major cryptographic proof systems used to verify computations in blockchain applications: Groth16, PLONK, and STARK. To present their differences, we sketch instances of these proof systems to prove the knowledge of a solution for the Discrete Logarithm Problem (DLP) — a well-known computational problem whose assumed hardness is the base for the security of many cryptographic applications.
The first section provides a brief overview of proof systems and compares modern systems to earlier generations. This section also serves as an introduction to the structure of upcoming blog posts. The second section examines proof system properties relevant to blockchain applications, highlighting which features are present in Groth16, PLONK, and STARK. Readers already familiar with cryptographic proofs and their blockchain applications may skip these sections.
In the next blog post from this series, we define the DLP and present a naive protocol to prove the knowledge of the solution for any instance. This naive protocol is then compiled into a Groth16 proof with some modifications to enable Zero-Knowledge. We contextualize how each other property described in the second section of this first blog is guaranteed in this example. The following two blogs describe PLONK and STARK counterparts of this Groth16 proof.
Cryptographic proof systems are protocols that help one party, the Prover, convince another party, the Verifier, that a particular solution to a computational problem is valid. Early proof systems were designed to validate solutions for specific problems, meaning properties that define correct solutions were hardcoded into the system. Modern proof systems, however, can validate solutions to any problem by encoding these properties as inputs to the system. To help distinguish from the hardcoding approach, proof systems with this flexibility are called universal.
Both classic and universal proof systems can be seen as protocol versions of validation algorithms. The final proof convinces the Verifier by showing that each step of the underlying validation algorithm can be executed correctly. In order to show the correctness of these validation steps, a universal proof system requires them to be translated to a high-level language before being input to the protocol. In this blog series, we call this the encoding language.
After the validation algorithm for a problem has been written in an encoding language compatible with some proof system, the next step on the universal proving procedure is to translate this description to a low-level language. This language is designed to represent the validation algorithm as some well-defined mathematical problem. This translation process is known as arithmetization, and therefore we call this second language the arithmetization language.
Once validation algorithm and valid solution have been properly encoded and input to the proof system, the arithmetization process prepares their correspondence for mathematical evaluation. While this evaluation concludes the execution of the proof system, it may require one last translation procedure to condense the arithmetized problem into an object that can be efficiently verified. In this blog series, we call this final mathematical object the evaluation statement.
We say the proof system is complete when valid solutions produce valid evaluation statements, leading the Verifier to accept the proof; and say it is sound when invalid solutions produce invalid evaluation statements, causing the Verifier to reject the proof. The success probability of a proof system is given by its completeness and soundness probabilities, which naturally depends on completeness and soundness properties of encoding, arithmetization and evaluation procedures.
Completeness is easier to guarantee than soundness because the Prover produce valid proofs for valid solutions by design. Invalid solutions, on the other hand, might be used to generate valid proofs (breaking soundness) if malicious Provers deliberately modify the proving procedure to this end. To prevent such attacks, proof systems typically reduce validation algorithms (and valid solutions) to conjectured-hard computational problems. This approach improves verification accuracy as creating fake proofs requires breaking well-accepted cryptographic assumptions.
The table below shows encoding language, arithmetization language, and evaluation statement of each proof system covered in this blog series. Detailed descriptions of these techniques will be provided in the following blog posts, along with an analysis of their conjectured soundness. The next section explores additional properties of proof systems used in blockchain applications.
Cryptographic proof systems can be applied to blockchain in a number of ways but, in general, the Prover always runs off-chain and the Verifier runs on-chain. This model forces blockchain-focused proof systems to concentrate most of the validation complexity on the Prover, due to the high maintenance cost of the Verifier smart contract. For this reason, the goal of any combination of the properties described in this section is to optimize this trade-off for some use-case.
Although reducing verification complexity is perhaps the main goal for most blockchain-focused proof systems, reducing proof size can be an equally important requirement. These goals might conflict as compressing the proof leads to more intense post-processing for the Verifier, as well as more intense pre-processing from the Prover. As previously stated, Prover pre-processing is not our main concern, so we focus on proof compression and Verifier post-processing.
When the proof is short enough, we say the proof system is succinct. Rigorously, a proof system is considered succinct if the resulting proof size is polylogarithmic on the size of the original solution (see Gennaro et. al), Meaning proofs of size \( O(\log^k(n)) \) for solutions of size \( n \). When the Verifier is fast enough, we say the proof system is scalable. Rigorously, a proof system is considered scalable if the resulting verification time is quasilinear on the time of the validation time (see Ben-Sasson et. al), meaning verification times \( O(n \cdot \log^k(n)) \) for validation times \( n \).
While succinctness and scalability are the main quantitative requirements for blockchain-focused proof system, there are qualitative requirements these proof systems must attend depending on context. For instance, as mentioned in the previous section, soundness relies on computational problems. These problems might be number-theoretic (based on mathematical problems for which no efficient algorithm is known) and statistical (based on hash function collisions).
Proof systems whose security is based on mathematical problems are instantiated by trusted parties responsible for choosing secret random parameters. If a trusted party is not trustworthy, it might compromise soundness by providing a backdoor to the Prover. Proof systems based on hash-collisions, on the other hand, do not allow backdoors as they do not depend on secret parameters. For this reason, hash-based proof systems are also called transparent.
Another application of hash functions on proof systems is to avoid interaction. Interactive proof systems achieve soundness by letting the Verifier choose random values used by the Prover. Non-interactive proof systems, on the other hand, achieve soundness by sampling randomness from a hash function the Verifier trusts. The hashes are computed from variables included in the proof as specified by the system, which can be viewed as a commitment to that proving instance.
This technique works on the Random Oracle Model, which assumes uniform distribution for outputs of a particular hash function. This hypothesis, known as the Fiat-Shamir Heuristic, is widely accepted but cannot be demonstrated as uniformity of hash outputs cannot be proved. Back to using randomness to achieve soundness, a useful side-effect is verifying the Prover knows some value it claims to know (a.k.a. knowledge-soundness). Unless the Prover finds a backdoor or a hash collision, it can only generate the proof if it knows a solution to the problem.
This property is proven by showing that the existence of an all-powerful party who does know a backdoor (or can crack the hash function) implies it can extract knowledge from a valid proof. Proof systems to which the existence of such a party implies knowledge extraction are called proofs-of-knowledge or arguments-of-knowledge, depending on the extraction assumption (argument-extractors can solve NP problems while proof-extractors are conceptual oracles).
Another knowledge-related property is preventing leakage of information about valid solutions. This property can be proved by an approach similar to the one above: showing that a powerful party can produce fake proofs that the Verifier cannot distinguish from valid ones. Because such a fake proof is produced without a secret solution but still looks like a valid proof, the valid proof leaks no knowledge. Proof systems featuring this property are called Zero-Knowledge (ZK).
Finally, to contextualize the properties described in this section in the context of this blog series, the table below presents which properties hold for Groth16, PLONK, and STARK. In general, universal proof systems are classified as Succinct and Non-Interactive Arguments-of-Knowledge (SNARKs) or Scalable and Transparent Arguments-of-Knowledge (STARKs). It is easy to see PLONK and Groth16 are considered SNARKs, while STARK belongs to the homonymous category.
This blog post begins a series exploring the differences between three major cryptographic proof systems used to verify computations in blockchain applications: Groth16, PLONK, and STARK. To present their differences, we sketch instances of these proof systems to prove the knowledge of a solution for the Discrete Logarithm Problem (DLP) — a well-known computational problem whose assumed hardness is the base for the security of many cryptographic applications.
The first section provides a brief overview of proof systems and compares modern systems to earlier generations. This section also serves as an introduction to the structure of upcoming blog posts. The second section examines proof system properties relevant to blockchain applications, highlighting which features are present in Groth16, PLONK, and STARK. Readers already familiar with cryptographic proofs and their blockchain applications may skip these sections.
In the next blog post from this series, we define the DLP and present a naive protocol to prove the knowledge of the solution for any instance. This naive protocol is then compiled into a Groth16 proof with some modifications to enable Zero-Knowledge. We contextualize how each other property described in the second section of this first blog is guaranteed in this example. The following two blogs describe PLONK and STARK counterparts of this Groth16 proof.
Cryptographic proof systems are protocols that help one party, the Prover, convince another party, the Verifier, that a particular solution to a computational problem is valid. Early proof systems were designed to validate solutions for specific problems, meaning properties that define correct solutions were hardcoded into the system. Modern proof systems, however, can validate solutions to any problem by encoding these properties as inputs to the system. To help distinguish from the hardcoding approach, proof systems with this flexibility are called universal.
Both classic and universal proof systems can be seen as protocol versions of validation algorithms. The final proof convinces the Verifier by showing that each step of the underlying validation algorithm can be executed correctly. In order to show the correctness of these validation steps, a universal proof system requires them to be translated to a high-level language before being input to the protocol. In this blog series, we call this the encoding language.
After the validation algorithm for a problem has been written in an encoding language compatible with some proof system, the next step on the universal proving procedure is to translate this description to a low-level language. This language is designed to represent the validation algorithm as some well-defined mathematical problem. This translation process is known as arithmetization, and therefore we call this second language the arithmetization language.
Once validation algorithm and valid solution have been properly encoded and input to the proof system, the arithmetization process prepares their correspondence for mathematical evaluation. While this evaluation concludes the execution of the proof system, it may require one last translation procedure to condense the arithmetized problem into an object that can be efficiently verified. In this blog series, we call this final mathematical object the evaluation statement.
We say the proof system is complete when valid solutions produce valid evaluation statements, leading the Verifier to accept the proof; and say it is sound when invalid solutions produce invalid evaluation statements, causing the Verifier to reject the proof. The success probability of a proof system is given by its completeness and soundness probabilities, which naturally depends on completeness and soundness properties of encoding, arithmetization and evaluation procedures.
Completeness is easier to guarantee than soundness because the Prover produce valid proofs for valid solutions by design. Invalid solutions, on the other hand, might be used to generate valid proofs (breaking soundness) if malicious Provers deliberately modify the proving procedure to this end. To prevent such attacks, proof systems typically reduce validation algorithms (and valid solutions) to conjectured-hard computational problems. This approach improves verification accuracy as creating fake proofs requires breaking well-accepted cryptographic assumptions.
The table below shows encoding language, arithmetization language, and evaluation statement of each proof system covered in this blog series. Detailed descriptions of these techniques will be provided in the following blog posts, along with an analysis of their conjectured soundness. The next section explores additional properties of proof systems used in blockchain applications.
Cryptographic proof systems can be applied to blockchain in a number of ways but, in general, the Prover always runs off-chain and the Verifier runs on-chain. This model forces blockchain-focused proof systems to concentrate most of the validation complexity on the Prover, due to the high maintenance cost of the Verifier smart contract. For this reason, the goal of any combination of the properties described in this section is to optimize this trade-off for some use-case.
Although reducing verification complexity is perhaps the main goal for most blockchain-focused proof systems, reducing proof size can be an equally important requirement. These goals might conflict as compressing the proof leads to more intense post-processing for the Verifier, as well as more intense pre-processing from the Prover. As previously stated, Prover pre-processing is not our main concern, so we focus on proof compression and Verifier post-processing.
When the proof is short enough, we say the proof system is succinct. Rigorously, a proof system is considered succinct if the resulting proof size is polylogarithmic on the size of the original solution (see Gennaro et. al), Meaning proofs of size \( O(\log^k(n)) \) for solutions of size \( n \). When the Verifier is fast enough, we say the proof system is scalable. Rigorously, a proof system is considered scalable if the resulting verification time is quasilinear on the time of the validation time (see Ben-Sasson et. al), meaning verification times \( O(n \cdot \log^k(n)) \) for validation times \( n \).
While succinctness and scalability are the main quantitative requirements for blockchain-focused proof system, there are qualitative requirements these proof systems must attend depending on context. For instance, as mentioned in the previous section, soundness relies on computational problems. These problems might be number-theoretic (based on mathematical problems for which no efficient algorithm is known) and statistical (based on hash function collisions).
Proof systems whose security is based on mathematical problems are instantiated by trusted parties responsible for choosing secret random parameters. If a trusted party is not trustworthy, it might compromise soundness by providing a backdoor to the Prover. Proof systems based on hash-collisions, on the other hand, do not allow backdoors as they do not depend on secret parameters. For this reason, hash-based proof systems are also called transparent.
Another application of hash functions on proof systems is to avoid interaction. Interactive proof systems achieve soundness by letting the Verifier choose random values used by the Prover. Non-interactive proof systems, on the other hand, achieve soundness by sampling randomness from a hash function the Verifier trusts. The hashes are computed from variables included in the proof as specified by the system, which can be viewed as a commitment to that proving instance.
This technique works on the Random Oracle Model, which assumes uniform distribution for outputs of a particular hash function. This hypothesis, known as the Fiat-Shamir Heuristic, is widely accepted but cannot be demonstrated as uniformity of hash outputs cannot be proved. Back to using randomness to achieve soundness, a useful side-effect is verifying the Prover knows some value it claims to know (a.k.a. knowledge-soundness). Unless the Prover finds a backdoor or a hash collision, it can only generate the proof if it knows a solution to the problem.
This property is proven by showing that the existence of an all-powerful party who does know a backdoor (or can crack the hash function) implies it can extract knowledge from a valid proof. Proof systems to which the existence of such a party implies knowledge extraction are called proofs-of-knowledge or arguments-of-knowledge, depending on the extraction assumption (argument-extractors can solve NP problems while proof-extractors are conceptual oracles).
Another knowledge-related property is preventing leakage of information about valid solutions. This property can be proved by an approach similar to the one above: showing that a powerful party can produce fake proofs that the Verifier cannot distinguish from valid ones. Because such a fake proof is produced without a secret solution but still looks like a valid proof, the valid proof leaks no knowledge. Proof systems featuring this property are called Zero-Knowledge (ZK).
Finally, to contextualize the properties described in this section in the context of this blog series, the table below presents which properties hold for Groth16, PLONK, and STARK. In general, universal proof systems are classified as Succinct and Non-Interactive Arguments-of-Knowledge (SNARKs) or Scalable and Transparent Arguments-of-Knowledge (STARKs). It is easy to see PLONK and Groth16 are considered SNARKs, while STARK belongs to the homonymous category.
