Spartan: zkSNARKS without trusted setup
In previous posts I gave a brief summary of the functionality of zkSNARKs and a potential application (anonymized commit-reveal scheme) that could benefit from their characteristics. However, one of the main drawbacks of using zkSNARKs is the fact of requiring a trusted setup that generates the toxic waste. Indeed, this has been one of the biggest criticism that protocols featuring zkSNARKS (e.g.Zcash [2]) have suffered.
The recently published Spartan [1] paper describes a “transparent” zkSNARK, i.e., a zkSNARK protocol that does not require a trusted setup. In this post, I will try to summarize the key ideas that are discussed on it to achieve the aforementioned goal.
Definitions
Arithmetic circuit satisfiability: Given an artithmetic circuit C (composed of gates), a public input x and apublic output y, the decision problem of checking whether exists a non-deterministic input w such that C(x,w)=y.
Satisfying assignment : a vector of values (one per gate in C), with the constraint that values assigned to input/output gates are consistent with x and y, and that values assigned to each non-input gate are consistent with the evaluation (addition or multiplication) of their neighbors (2 each). If such a satisfying assignment exists, then there exists a witness w such that C(x,w)=y.
Low degree polynomial: A multivariate polynomial over a finite field F whose degree is small compared to F.
Low-degree extension: If g is a function mapping m bit elements to an element of F, g is a low-degree m-variate polynomial if there exists a polynomial extension g’ such that g(x) = g’(x). Additionally, if g’ is a multilinear polynomial (degree at most 1), then its called a multilinear polynomial extension.
The sum-check protocol
Given a m-variate low-degree polynomial G mapping m bit elements to F, imagine the verifier has to verify the following claim.
Of course given the description of G the verifier could evaluate the entire boolean hypercube space. The sum-check technique does not require the verifier to evaluate the entire boolean hypercube to verify the claim. Instead, random points (r1, r2, …, rm) are selected in an interactive protocol giving probabilistic guarantees. Upon sufficient success rounds, the verifier accepts the claim to be correct.
However, note that the sum-check protocol requires O(C) communication and verification costs. Spartan makes use of a succint version of the sum-check protocol by making the verification computational cost be sub-linear in the cost of evaluating a low degree polynomial.
Sub-linear verification and communication costs in Spartan
Spartan divides the problem of achieving the succint property, key characteristic of zkSNARKs, into 3:
- 1. Identification of a low-degree multivariate polynomial fitting in the structure of the sum-check protocol, i.e., a m-variate low-degree polynomial that sums to a value only if the circuit is satisfiable. This is necessary to achieve the following two goals.
- 3. Make the verifiers cost to participate sublinear, which as we will see its closely related to finding the low-degree multivariate polynomial.
- 3. Make the communication costs sublinear
The low-degree multivariate polynomial is achieved by relying on a these 4 different functions, where a, b and c are circuit gate identifiers:
- add(a, b, c) : true if a adds b and c.
- mul(a, b, c): true if a multiplies b and c.
- io(a, b, c): true if a is public input/output and c,b are correct neighbors (e.g. 0 in case of a being a public input)
- I_{x,y}(a) =x_a or y_a if a is an input/output gate.
The following linear combination of them satisfies the properties of sum to zero only if the circuit is satisfiable:
where Z (satisfiability assigment) is simply a function that maps the identifier of a gate to its value. Spartan uses the low-degree polynomial extension (denoted as ~) of the aforementioned function as follows for the check-sum protocol:
The key factor that Spartan takes advatange of is that if one can use multilinear extensions of the aforementioned functions (i.e., add, io and Z), the cost of evaluating of the polynomial that encodes the satisfying assigment becomes sub-linear [3].
As for the sublinear communication cost, polynomial commitment schemes are used, thanks to which the prover sends a commitment to a polynomial to the verifier before the check-sum protocol [4]. The prover thus can not commit to a polynomial and then decommit evaluations at a different polynomial at the points asked by the verifier. Note that the former only applies to multilinear polynomials, but this is not a problem as the multilinear extension of Z can be used. Polynomial commitment schemes are divided into 4 algorithms:
- PolyGen: which produces the public parameters taking into account the size of the evaluation vector upon which commitments will be made.
- PolyCommit: which takes the input public parameters and the evaluation vector and produces a commitment to the multilinear extension of Z.
- PolyEval: which takes as input the public parameters, the satisfiability assigment and a point on which the polynomial needs to be evaluated. Outputs the evaluation, and a proof of correct evaluation.
- PolyEvalVerify: which takes as input the evaluation, proof and commitment and outputs whether the polynomial was correctly evaluated or not.
As proven in [91], polynomial commitment schemes substantially reduce the proof size and evaluation cost, thus achieving the succint property.
The protocol
With the aforementioned pieces, Spartan utilizes the following protocol:
In summary, the prover who wants to prove knowledge of a satisfying assigment Z to the circuit commits to evaluations of a multilinear extension of Z. Aftet that the sum-check protocol is executed at random points selected by the verifier. The prover executes the PolyEval algorithm at these points, outputing proofs and evaluation of those proofs. The verifier checks the validity of these and either rejects or accepts the evaluation.
Achieving non-interactivity and zero knowldege
One would observe that the previous sections were far from providing zero-knowledge and non-interaction. Luckily, a zero knowledge variant for the sum-check protocol was studied in [3]. Similarly, non-interaction can be achieved by assuming random oracle security model using Fiat-Shamir heuristic technique [5]. These, combined with the succint characteristic achieved, make Spartan suitable for usage as a zkSNARK algorithm.
Implications
zkSNARKs have gained a lot of traction in the last years, perhaps even more in decentralized protocols were preserving anonymity with untrusted parties needs to be a core characteristic. However, the fact of requiring a trusted setup has always been food for critics. Not in vain, peers have to trust that the toxic waste has indeed been eliminated to ensure secrecy. Spartan goes a step further by proposing a protocol in which toxic waste does not need to be generated. Exiciting times ahead!.
References
[1] Spartan: Efficient and general-purpose zkSNARKs without trusted setup
[2] Zcash
[3] Doubly-efficient zkSNARKs without trusted setup
[4] Constant-size commitments to polynomials and their applications
[5] How to prove yourself: Practical solutions to identification and signature problems
Thanks you for taking the time to read!
Please let us know if you have any questions or comments below. You can follow Witnet or myself on Twitter and stay up to date on our blog.
