ZK-Snarks
In this we will outline the theory of the Pinocchio protocol in particular as an example
Last updated
In this we will outline the theory of the Pinocchio protocol in particular as an example
Last updated
Linear Interactive Proofs (LIP)
In LIPs, the prover and verifier engage in an interaction, where:
Polynomial Encoding:
The prover encodes their secret witness as the values of polynomials A(x),B(x), and C(x) at a secret point s.
Verification:
The verifier issues random challenges, and based on the responses, verifies if the prover knows the polynomial without revealing the specific value of s or the polynomial evaluations at s.
Structured Reference String (SRS)
Secret s chosen by the Prover:
In our earlier discussions on zk-SNARKs, there is a phase where the prover chooses a secret
s to evaluate their polynomials. This secret evaluation demonstrates to the verifier that the prover knows the polynomial without revealing any specifics about it.
The prover hides the evaluation at this secret point to prove they genuinely know the whole polynomial.
Structured Reference String (SRS):
The SRS, which includes commitments to powers of τ, is part of the setup phase of zk-SNARKs and is a separate concept from the secret s chosen by the prover. The "Powers of Tau" setup is a method to create an SRS for zk-SNARKs. During this process, a secret value τ is chosen and then discarded after the setup. It's crucial that
τ remains secret, and no one should ever know it. The generated SRS, however, is public and is used by all participants in the protocol.The SRS provides public parameters that every prover and verifier in the system can use for their proofs and verifications. It is a common "reference" for all zk-SNARK proofs in a particular system.
Why do we need both?:
The secret s chosen by the prover is used to convince the verifier that they know a polynomial without revealing it. It's a dynamic value, chosen fresh for each proof instance.
The SRS is a static set of parameters. Think of it as a "foundation" or "infrastructure" for the zk-SNARK system. Every prover and verifier uses the same SRS for their proofs and verifications, but the individual proofs will still have their unique aspects (like the secret s).
In essence, zk-SNARKs require both a common reference (the SRS) for everyone in the system and individual secret values (like s) for each proof to ensure both the consistency of the system and the privacy/integrity of individual proofs.
Breakdown of Srs
Let's break down the use of the Structured Reference String (SRS) in the context of zk-SNARKs and the polynomials we discussed earlier.
1. SRS Generation: "Powers of Tau" setup
During the setup phase, an SRS is generated using a method like the "Powers of Tau." This involves:
Selecting a secret random value τ.
Computing powers of τ based on the degree of the polynomials, i.e., τ0, τ1, τ2,...,τd.
Creating commitments to these powers using a group G1. This results in:
srs=[τ^0]G1,[τ^1]G1,...,[τ^d]G1
These commitments are the public parameters available to all provers and verifiers, while τ itself remains a secret and is discarded.
2. Using the SRS in zk-SNARKs
Given the polynomials A(x),B(x), and C(x) that the prover possesses:
Evaluation Commitments: The prover evaluates these polynomials at a secret point s and then creates commitments to these evaluations using the SRS.For example, for A(x), the commitment might look like:
[A(s)]G1
The commitment effectively hides the value of
A(s) while still allowing for certain operations thanks to the properties of the group G1.
Verifier's Checks:
The verifier can then perform certain checks using the commitments received from the prover and the public SRS, without needing to know the exact values of the polynomial evaluations.
For instance, one such check might be to ensure that:
A(s)⋅B(s)−C(s)=Z(s)⋅H(s)
This becomes a pairing equation in the elliptic curve setting, like:
e([A(s)]1,[B(s)]2)−e([C(s)]1,[1]2)=e([Z(s)]1,[H(s)]2)
The verifier can verify this equation without knowing A(s),B(s), or C(s), using only the commitments and the SRS.
Benefits of the SRS:
The SRS, when used in the above manner, offers several advantages:
Hiding Information:
The SRS allows provers to hide specific information (like the secret evaluations of the polynomials) while still allowing verifiers to check the validity of certain claims.
Consistency Across Proofs:
The same SRS can be used across multiple proofs, ensuring consistency in the system.
Efficiency:
The SRS-based commitments and checks are efficient, allowing for quick proofs and verifications.
In summary, the SRS serves as a consistent set of public parameters that enable zk-SNARK proofs to be both private (hiding specific details like polynomial evaluations) and verifiable (allowing verifiers to check proof validity).
Necessity of SRS in zk-SNARKs
Non-interactivity: zk-SNARKs stand for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge. To achieve the non-interactive feature, certain common reference parameters are required for the prover and verifier. SRS provides these parameters.
Randomness without Interaction: In traditional interactive proofs, randomness is introduced through challenges by the verifier. With zk-SNARKs, this randomness is inherently provided by the SRS, thus removing the need for an interactive challenge.
Security:
The SRS acts as a commitment scheme. It binds the prover to a specific statement without revealing the underlying secrets, ensuring the zero-knowledge property is maintained.
Efficiency:
The existence of a pre-established SRS accelerates the proof generation and verification process.
Usage of SRS in zk-SNARKs
The SRS is employed in two primary phases:
Proof Generation: The prover utilizes the SRS to generate commitments to their polynomial evaluations. These commitments are sent to the verifier.
Proof Verification:
The verifier, equipped with the SRS, performs pairing-based checks on the received commitments to validate the proof without the need for interactive challenges.
Conclusion
The Structured Reference String (SRS) is a cornerstone in the zk-SNARKs architecture, enabling non-interactivity, security, and efficiency in the proof systems. The "Powers of Tau" setup ensures that the SRS is generated in a universally trusted manner, forming a reliable foundation for zk-SNARKs operations.