Home Edition #2

Proposal: An Algebraic Framework for Universal and Updatable zkSNARKs

Moderator: Mary Maller
Presenters: Arantxa Zapico

Authors:

  • Carla Ràfols
  • Arantxa Zapico

To be presented on 2021-04-20.

Resources:

Real-time notes

Note taker: Anaïs Querol

SLIDES:

State of the art:
Interactive Proof Systems -> ZK proofs for all NP -> succinct arguments without PCPs -> qaps -> pinnocchio -> zerocash -> most efficient zksnark groth16

Problem? Trusted Setup. Multiparty computation (inefficient ceremony)

Idea: Updatable and Universal SNARKs ("trusted" but any participant can rerandomize and not tied to one single circuit)

Comparison between ZK constructions difficult.

Common Design Principle:
Information theoretical object (holographic proof normally) + polynomial commitment = compiled into zk SNARK

Holographic?
Indexer that computes some polynomials that describe the circuit, the relation
Also the prover messages include polynomials
And verifier has oracle access to both sets of polynomials, can do degree checks on them and polynomial checks of some type.
State of the art: Sonic, Plonk, Marlin, Lunar, Claymore

Motivation (this proposal)
Can we break down the information theoretical model even more? YES

  1. Break circuit satisfiability in 3 main algebraic components:
  • Hadamard Product
  • Inner Product
  • Verifiable subspace sampling
  1. Definition of verifiable subspace sampling

Groth16: example
What can we reuse from this?

  • The constraint system
  • Argument has also 2 main building blocks
    • Hadamard product: Universal SRS
    • BUT Linear relations: circuit dependent srs

Main tool: compressed linear algebra
m : number of multiplication gates
define interpolation polynomial in the set
define vanishing polynomial for the set
Linear algebra world -> Polynomial world

Universal SRS constraint system
Ai left inputs, Bi right inputs, Ci outputs (mult gate i)
Hadamard prod: a o b = c (can be expressed as matrix mult)
Linear relations can be represented as a = F c and b = G c or equivalently
(I 0 -F)(a b c) = 0 and (0 I -G)(a b c) = 0

W = I 0 -F , 0 I -G and check that W (a b c) = 0

Equivalent to: exist polynomial deg leq m-2 such that w(x)(a(x),b(x),c(x)) vanishes on all set

w can be computed by indexer, but 2m inner product because of the shape of w, want to compress this

=> Verifiable subspace sampling:
alternatively: sample a random vector d in the rowspace of the matrix
check one inner product d (a,b,c) = 0

Need an encoding of the vector: D(X) = P(X,x) + Sample(x) W \lamda(X)
Who samples x?
Indexer: x needs to be secret, resulting in a quadratic SRS (groth et al 18)
Prover: no soundness
Verifier: cool but who does the partial evaluation? because linear computation/memory.

Offline phase: indexer outputs polynomials describing matrix W
Online phase:

  1. Sampling (prover will send encoding on x)
  2. Prove sampling: accept or reject
    Decission phase

Common strategy:

  • Setup universal SRS
  • Preprocessing phase we get a set of polynomials related to W
  • Online phase
    • Sampling Phase: verifier sends x
      verifier sends another challenge
      then prover sends poly eval on two points
      ∏ is a proof that P(y,x) is correctly evaluated

State of the art in Verifieable subspace sampling:

  • Sonic:
    • VSSampling proof grows with size of decomposition of W as permutation
    • Amortized VSSampling
  • Marlin & Lunar
    • Needs a multiplicative subgroup of size sparsity of matrix relatively large SRS
  • Our work (soon on eprint)
    • Extended vandermonde sampling
    • reduce srs size drastically by decomposing marlins vssampling into simpler building blocks

ZOOM SIDE CHAT:

Daira Hopwood:
also very difficult to respond to security flaws! I would almost say that's a showstopper for circuit-specific trusted setup in block chain applications, at least (we only did it for Zcash Sprout and Sapling because we had no choice at that time)
question for later: is it possible to unify AHPs with IOPs?
this seems to be Sonic's arithmetization, but the arithmetization is part of the difference in efficiency between, say, Sonic and PLONK is the approach generalizable to other arithmetizations?

Carla Rafols salvador
we have chosen this for clarity purposes in the presentation, we really use R1CS lite, from lunar

Daira Hopwood
got it

Jonathan Bootle
About the AHPs and IOPs…you can define a general IOP with different types of queries (linear, polynomial, point or other functions). In an AHP, each point that the verifier can query is an algebraic function of the witness. Couldn't those functions just become the IOP queries that you're allowed to make?

ZKProof Standards
My suggestion: to continue this discussion in the context of the reference document until the framework matures and its benefits are made clear when applied to descriptions of several (or most) schemes that it applies to.

DISCUSSION

  • Daira: Should unify AHP with IOPs?
  • Arantxa: Perhaps need a general definition that is flexible enough to represent both
  • Daira: Is this something we do first the model and then we build constructions based on them or we have the construction and then create a model that nicely represents it in a more abstract model?
  • Carla: We wanted to understand the nuances between all notions out there and this proposal was a way to do it. Also to think about the algebraic part involved in these constructions.
  • Mary Maller: what do we think is the best proving system strategy?
  • Daira: in zcash we think most of our circuits work best with plonk and r1cs (merkle trees, etc). Need to consider concrete efficiency. In plonk you have a tradeoff between number of rows and cols.
  • Bootle: general IOP with different types of queries?
  • Ariel: polynomial IOP in DARK and AHP in Marlin. Is it completely equivalent?

  • Bootle: pretty close

  • Daira: is there any other reason that we get different names than having been written in parallel?

  • Anaïs: for sure when works are being developed in parallel and in a fastly growing area, one can clearly find similar ideas in different papers but it is important to understand what differences exist between one notion and the other and why this was chosen this way for the particular scheme. In Lunar modelling messages as field elements rather than deg0 polys allows us to model a more fine grained type of zero knowledge that we use in our zksnarks.
  • Daniel Benarroch: right, perhaps it is a bit too soon to standardize some notions, but it is good to have these discussions as an effort to systematize knowledge and understand the current differences as Carla was pointing out.

Daira: it is interesting to point out at what extent do constructions depend on certain polynomial commitments

Mary: is this generalization general enough to
Arantxa: we were still not able to prove if our generalization covers plonk as well
Ariel: This doesn't capture PLONK. Before polynomial IOP/AHP, we were stuck with degree two, because we had a secret point in the exponent, and we only have degree 2 homomorphic evaluation (from pairings). But using the polynomial IOP approach, in PLONK, instead of a secret point, we're doing a random verifier points. That's how we can move from degree 2, to degree 4 or 5 or 6.
Ariel: if care about constants, then yes the degree matters. easier to capture permutation arguments than some linear relations.
Carla: I think plonk does not really fit, but plonk and marlin have something in common which is to have a really efficient system, you need some stick to a type of matrix (kind of a limitation). We want to generalize this.
Mary: somehow this is inherited, you cannot escape the addition gates, cannot preprocess them
Carla: why would this be a limitation for the verifier?
Mary: verifier at some point needs to process all the relation. if universal cant really preprocess because it is universal.
Ariel:
Daira: this is what we do for the security of Halo

DO WE WANT TO INTEGRATE THIS IN THE COMMUNITY REFERENCE DOCUMENT?

  • Ulrich: how different is the vssampling from lunar and marlin?

  • Daira: perhaps this is a long question to address now

  • Carla: I think the flow is very similar but the differences lie in some nuances to make the proof a bit shorter

  • Anaïs: perhaps we can take that offline because there are many details that need to be explained, but yes, the idea is quite similar

  • Mary: seems like we didnt converge on what the standard should look like

  • Daniel: this document is in an early stage, perhaps the area is still not ready yet for a formal standardization, but could be interesting to explain the types of notions there are here now.

  • Eran: would like to see this integrated as a reference doc until framework keeps maturing

Mary: interest in creating a working group? looks like so

Carla: some things are the same with different names and this should be explained somewhere for reference when reading the works

Select a repo