4
$\begingroup$

I am reading this explanation of zkSnarks written by Maksym Petkus - Why and How zk-SNARK Works

They work through the concept of zkSnarks using a polynomial which the prover knows & he has to convince the verifier that he knows it. The verifier knows that the polynomial has 2 factors ($x = 1$ & $x = 2$), he doesn't know the other factors.

The polynomial used in the examples are something like the one below

$p(x) = x^3 - 3x^2 + 2x$

The verifier knows 2 factors, i.e. he knows

$t(x) = (x-1)(x-2) = x^2 - 3x + 2$

The unknown part of the polynomial which only the prover knows is

$h(x) = x$

$p(x) = h(x) \cdot t(x)$

I am trying to understand how this example corelates with how zkSnarks are used in reality & have a few questions regarding the same.

  • In real use cases on the blockchain, how long would these polynomials which the provers prove be? i.e. how many factors would the polynomial have in total approximately - just asking about the range - i.e. would it be in 100s of factors, 1000s, millions or what? What would be the degree of the polynomial?

  • Out of this, how many factors would the verifier know? is it like 1% of the factors, 10% of the factors, 50% of the factors or what?

  • In the toy example, the factors are in $\mathbb Z$, but in the real use cases are these factors still in $\mathbb Z$, or would they be in $\mathbb Q$ or $\mathbb R$ or $\mathbb C$?

$\endgroup$

2 Answers 2

5
+50
$\begingroup$
  • Circuit (polynomial) sizes in deployed zkSNARKs. Multiple projects apply zkSNARKSs (e.g., mainly Groth16 or Plonk) in production. The degree of the polynomial slightly depends on the applied poly-IOP protocol. Still, roughly it has the same degree as the number of multiplication gates (if you prefer to think of your computation as an arithmetic circuit). In the case of Plonk, $𝑑=3𝐶+𝐼$, where $C$ is the number of multiplication gates and $𝐼$ is the number of (public and private) inputs of the computation. The most notable examples support the following polynomial sizes. To be more precise, the sizes of the following common reference strings correspond to the maximum degree of the committed polynomials. These maximum degrees can be easily transformed to the maximum size of the circuit depending on the applied poly-IOP protocol; see the example of Plonk above.

    1. Zcash: The current Zcash common-reference string (CRS) supports arithmetic circuits with up to $2^{21}$ multiplication gates. See it here.
    2. Perpetual Powers-of-Tau: The perpetual powers-of-tau crs by the Semaphore team is (re)used (updated or copied) by multiple projects, for example, Aztec, Tornado Cash, Filecoin etc. It has a size of $2^{29}-1$, i.e., it supports computations with $2^{28}$ multiplication gates. This means that $2^{28}$ would be also the maximum size of the polynomial.
    3. Proto-Danksharding: The Ethereum Foundation plans to run a smaller trusted setup ceremony for its upcoming Proto-DankSharding and DankSharding upgrades. These smaller trusted setups will support circuit sizes of $2^{12}, 2^{13}, 2^{14}, 2^{15}$.
  • Most modern zkSNARKs apply the polynomial IOP (interactive oracle proof) paradigm. This means that the verifier does not see any polynomials during the proof, only commitments to these polynomials and opening proofs at random points of these polynomials. The verifier cannot read the polynomial encoding the computation because it does not have time to do so; that is, we want a succinct verifier that runs in polylogarithmic time in the degree of the polynomial. Typically, the verifier only sees a commitment to this polynomial. Therefore it does not know the factors of it.

The most notable polynomial commitment scheme is the KZG polynomial commitment scheme. A notable instantiation of the polynomial IOP paradigm is the PLONK proving system.

  • In a real-world use case, factors would be in a finite field $\mathbb{F}_p$ for some prime $p$ (with length $\approx256-381$ bits). The two most popular pairing-friendly curves used in zkSNARKs are the BN256 and the BLS12-381 curves.
$\endgroup$
8
  • 1
    $\begingroup$ for the non expert like me in ZKSNARKS, can you point out the relationship [if simple enough] between circuit size and polynomial degree? $\endgroup$
    – kodlu
    Commented Dec 22, 2022 at 20:28
  • $\begingroup$ What would be the degree of the polynomial approximately? And how many of the factors would the Verifier know? $\endgroup$
    – user93353
    Commented Dec 23, 2022 at 6:02
  • $\begingroup$ The degree of the polynomial slightly depends on the applied poly-IOP protocol. Still, roughly it has the same degree as the number of multiplication gates (if you prefer to think of your computation as an arithmetic circuit). In the case of Plonk, $d=3C+I$, where C is the number of multiplication gates and $I$ is the number of inputs of the computation. $\endgroup$ Commented Dec 24, 2022 at 9:25
  • $\begingroup$ The verifier cannot read the polynomial encoding the computation because it does not have time to do so, that is, we want a succinct verifier that runs in polylogarithmic time in the degree of the polynomial. Typically, the verifier only sees a commitment to this polynomial. Therefore it does not know the factors of it. $\endgroup$ Commented Dec 24, 2022 at 9:25
  • $\begingroup$ @IstvánAndrásSeres - I have seen/read several explanations of SNARKS/PLONKS & all of them seem to split the polynomial into two parts - i.e. p(x) = t(x).h(x) - One of them is known to both the prover & the verifier & the other is known only to the prover. You can check the linked document I have provided in the question. Or this video of PLONK - youtube.com/watch?v=qCGsfeSaMZo David calls the part which is known only to the prover as the vanishing polynomial & the other as the quotient polynomail. If one of the parts is known, that also would contain factors, right? $\endgroup$
    – user93353
    Commented Dec 26, 2022 at 10:04
1
$\begingroup$

1: Polynomial $t(x)$ is of degree the number of equations (constraints) of the R1CS system we are building a proof for. Consider an R1CS system of $n$ equations. The way groth16 works (Lagrange interpolation), $p(x)$ would of degree $2(n-1)$. So the dividend $h(x)$ would be of degree $(n-2)$. The real question is, how large is the R1CS system for a case like ZCash verification.

2: Factors of $t(x)$ are arbitrary field elements, plaintext, assigned for each R1CS equation. There are secrets "mixed-in" polynomials $h()$ and $p()$, so they only available for verifier as group elements (not as a plaintext). To be more specific here, polynomials are effectively evaluated at a random point served as a challenge (called "toxic waste", probably to make it easy to understand).

3: To hide $h()$ and $p()$ from verifier, pairing operation on elliptic curve is used, so R1CS system is over a finite field of cardinality the group order. They call it scalar field, hopefully easy to understand.

Selling Sudoku solution was presented at Financial Crypto 2016 Bitcoin workshop, an extremely interested case of "easy" grade with snarks. The scenario is selling a secret solution for a known staring position on bitcoin blockchain. The problem is, both seller and buyer are at risk doing the first move: if the seller sends his solution first nothing prevents the buyer from not responding at all. And if the buyer sends his coins first, he might get some random bytes. The problem was solved as a transaction of HTLC type (pay-to-script actually) and a snark proof that (1) a ciphertext was correctly produced from a secret Sudoku solution and a secret key; (2) the solution above is valid for the initial position; (3) the key was correctly hashed to some value the buyer would initiate HTLC with. Basically, the seller can only spend this UTXO by providing the valid key,a hash pre-image.

The shameless part:

An alternative R1CS circuit verifying just Sudoku solution validity was introduced starting from polynomial set representation, presented at IEEE ATIT 2019. A longer (more detailed) was submitted for ISCOPT 2019, in case you would read Russian:

https://github.com/vadym-f/Sudoku_solvability_proof/tree/master/doc

https://github.com/vadym-f/Sudoku_solvability_proof/tree/master/IEEE_ATIT_2019

Both conferences were cautious enough, doing their best to avoid formally publishing that actually.

For an $N^2 \times N^2$ initial Sudoku position, this R1CS system is roughly (asymptotically) $5 N^4$ equations, so you could get $p()$ and $h()$ degrees.

The idea of verifying polynomials at a random point (that helps to smile at "toxic waste" jargon) was introduced for extending Schnorr proofs into higher-degree polynomials in challenge of verifier:

https://eprint.iacr.org/2008/363

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.