Join Log in
Score:4
avatar Crypto

What would be the degree (or range of the degree) of the polynomial used in real life zkSnarks as used in blockchains?

et flag
user93353

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$?

206
2 + 0
Score:5
István András Seres avatar Crypto
cf flag
István András Seres

  • 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.
+ 8
kodlu avatar
sa flag
kodlu
for the non expert like me in ZKSNARKS, can you point out the relationship [if simple enough] between circuit size and polynomial degree?
1
Reply
et flag
user93353
What would be the degree of the polynomial approximately? And how many of the factors would the Verifier know?
0
Reply
István András Seres avatar
cf flag
István András Seres
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.
0
Reply
István András Seres avatar
cf flag
István András Seres
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.
0
Reply
et flag
user93353
@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 - https://www.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?
0
Reply
István András Seres avatar
cf flag
István András Seres
Yes, you're right. To make the discussion concrete, let's stick with PLONK. In the case of PLONK, the computation is encoded in p(x) in such a way that it encodes the left/right inputs of gates and the output gate at the powers of a primitive root w. If any of the public inputs are 0, then the verifier knows that they divide p(x); Likewise, typically, the output of the computation is also 0. A precise answer would depend on the chosen SNARK and the computation you want to prove. Asymptotically, the number of factors of p(x) known by the verifier should be O(log(d)), where d is the degree of p.
0
Reply
et flag
user93353
Thank you. Just one more part of the original question - - 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$? What is the field/ring in which the polynomial is defined?
0
Reply
István András Seres avatar
cf flag
István András Seres
It's defined over a finite field, typically $\mathbb{F}_p$ for a few hundred (256-381) bit prime; see the last part of the answer. If your computation takes place in another ring or (in/finite) field, then proving it in a zkSNARK becomes pretty tricky since you need to mirror the arithmetics "inside" $\mathbb{F}_p$.
0
Reply
Score:1
Vadym Fedyukovych avatar Crypto
in flag
Vadym Fedyukovych

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

+ 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.