Is there a risk of allowing degeneracy of bilinear pairings in the case of the Groth16 zk‑snark system when the prover is free to set A B and C to arbitrary valid points directly ? (remember this can be done by allowing point at infinity)

The non degeneracy criteria is there’s no billenear pairing resulting in the finite field element 1 equivalent.

In the case of the optimal ate pairing, this can happen if one of the point of the pairing is the point at infinity : then whatever is the other point in the key, the result will always be 1.
For that reason, Zcash makes this a requirement and provide no encodings for the point at infinity.

But what would happen if it would be the cases as it’s happening on some implementation using Ethereum’s ᴇɪᴘ‐197 precompile ? Are there security risk when public inputs are used and if yes how this can be done ? In the case I’m studying, the prover is free to set A B and C to arbitrary values as long as they are on curves unlike Zcash.
Or is it only a problem for other Zk‐Snark systems and not Groth16 with public inputs ?

I’m especially thinking about snarkjs/templates/verifier_groth16.sol.ejs at a483c5d3b089659964e10531c4f2e22648cf5678 · iden3/snarkjs · GitHub snarkjs/templates/verifier_groth16.sol.ejs at a483c5d3b089659964e10531c4f2e22648cf5678 · iden3/snarkjs · GitHub

2 Likes

Yes, or we could just say that there’s no need for such encodings. If they were allowed but happened with negligible probability, that would not cause any difficulty, I think.

2 Likes

I didn’t understand anything. But this proves that Zcash is more complex than I imagined.

2 Likes

CHAT GPT:

The question about the degeneracy of bilinear pairings in the Groth16 zk-SNARK system, as mentioned in the Zcash community forum, involves considerations of security and the functioning of bilinear pairings, which are fundamental for creating cryptographic proofs.

Degeneracy in Bilinear Pairings

  1. Definition of Degeneracy: In the context of bilinear pairing, degeneracy occurs when the result of pairing two points yields a finite field element that does not provide the desired security. The example given is that if one of the points in the pairing is the “point at infinity,” the result of the pairing will always be 1, which would compromise the security of the proof.

  2. Non-Degeneracy Requirements: Zcash has an explicit requirement to disallow encodings that result in degeneracy, particularly because this can lead to vulnerabilities. The concern is that allowing the point at infinity could enable an attacker to manipulate public inputs to obtain results that do not genuinely represent the proof that should be made.

  3. Comparison with Other Implementations: The author of the post mentions implementations using Ethereum’s EIP-197 precompile, where degeneracy can occur. The question raised is whether this poses a security risk when public inputs are used, and if so, how this could be exploited. Although the degeneracy problem is more critical for other implementations, as suggested, it could still have implications for Groth16.

  4. Probability of Degeneracy: The discussion concludes that if degeneracy occurs with negligible probability, it might not cause significant difficulties. However, Zcash’s stance is clear in avoiding such scenarios, ensuring that there is no room for degeneracy in the proofs.

Implications

  • Security: Allowing degeneracy could open doors to attacks, such as proof forgery. Therefore, Zcash adopts a conservative approach, ensuring that all pairings used in proofs are non-degenerate.

  • System Design: The design of the Groth16 zk-SNARK system is intended to avoid situations where security could be compromised, which is a critical aspect of constructing proof systems and cryptography.

In summary, degeneracy in bilinear pairings represents a significant potential risk, and Zcash’s position to avoid this degeneracy is an essential security measure to ensure the integrity of zk-SNARK proofs.

2 Likes

In layman’s terms, Zcash Sapling uses the Groth16 proving system. One of the steps of verification requires checking that some secret values are products of each other.

Checking that secret values are sums is common. If a and b are such that c = a + b, the public points for a, b, c have the same relation. C = A + B. That is not true if c = a*b. The pairing is a mathematical construction where you can check that multiplicative equality in zero-knowledge.

However, a value is “degenerate”, meaning that the equality holds true trivially: Like a x 1 = a, regardless of a. You want to avoid getting into that situation. But it is not a problem for Zcash because the prover cannot choose a and b. They are the results of the previous steps. So, the probability that a = 1 or b = 1 is negligible.

3 Likes

@hanh So bilinear pairing is what makes Zcash exist? Are the principles of bilinear pairing what brings all the privacy of transactions? I confess that I had never heard of bilinear pairing (I never heard of it in high school or college), it’s new to me.

well, it is part of it but it is not required. Halo 2 doesn’t use pairings.

2 Likes

It’s very unlikely to hear about pairings unless you’ve studied math or cryptography.

They are neat and I’m super sad that new constructions don’t use them anymore :smiling_face_with_tear:

2 Likes

Ok I understand.

In my case the prover is free to Choose A and B and C to arbitrary values as long as they are on curves. But chosing the value of public inputs (and thus the pairing resulting from public inputs) remains impossible.
Would it be a problem to allow points at infinity in such a case?

Bilinear pairings were initially created as a tool to attempt to solve discrete logarithms since it’s easier to solve discrete logarithms in finite fields than curves over finite fields.

But while still being pairing friendly in the case of Zcash, the finite field’s degree required to get the same suborder than the curves is currently too large.

Their traces are large too which could avoid generalized pairing inversion if fully chosing values was possible (unless I’m wrong on optimal ate pairings).

Beside, don’t beleive those who say full automation of tasks because of llm will ever happen. If you want to start learning about those things for free, succeed to compile a recent version of SageMath and play with the high level functions being provided to see how they works.

1 Like

But what if there’re no restrictions if curves points are directly sent to the pairings from prover inputs? (and thus the only check is they are on curves) snarkjs/templates/verifier_groth16.sol.ejs at a483c5d3b089659964e10531c4f2e22648cf5678 · iden3/snarkjs · GitHub snarkjs/templates/verifier_groth16.sol.ejs at a483c5d3b089659964e10531c4f2e22648cf5678 · iden3/snarkjs · GitHub (the function being called directly by the prover but withoit being able to set the public inputs part)

I strongly recommend not using current LLM-based AI systems to summarize or restate properties of cryptographic protocols. They are not up to the task.

No. Zcash doesn’t define the encoding of the point at infinity in Groth16 proofs, simply because the point at infinity cannot occur in those proofs. It would be redundant to define an encoding for a case that can’t occur.

I’ve never analysed whether the security of Groth16 depends on that. Why would I have needed to analyse a case that can’t occur? There are a bunch of other cases like this elsewhere in the Zcash protocol, that we exclude not because they are known to be potential vulnerabilities, but because they’re unnecessary and we don’t want to have to even think about those cases.

Ethereum is in a different position because it’s trying to provide somewhat general-purpose primitives rather than implementations of specific cryptographic schemes. There are downsides to that approach because it requires more cryptographic engineering expertise from direct users of those primitives.

The right way to approach this, IMHO, is simply to ask “Am I implementing Groth16 as described in the paper and consistently with other implementations that have received cryptographic review?” It’s really no different from implementing Groth16 using a general cryptographic pairing library in any other context. You can definitely use the primitives provided by Ethereum to do that (for the pairings that it supports, which is currently only BN-254 but I believe will soon include BLS12-381). Please note that if you’re asking for cryptographic engineering review of some proposed protocol or implementation, you need to be explicit that that’s what you’re asking for. This is just an informal comment.

ChatGPT had no basis on which to make this statement. It just made it up. It may or may not be true. You could pay a cryptographer to tell you whether this is true, or you could ask them nicely to spend a bunch of time thinking about it (more than I have available right now). Don’t ask ChatGPT.

5 Likes

My problem of course is not being able to implement it in a basic working ways but thinking about the librariry I intended to use suffered basic security breachs in the past. (like not even verifying for inputs being over the value of the prime in the JavaScript version and many other later issues that got fixed silentely)

Hence why I’m questionning the need of some security requirements/proprieties. So in my case, I’m especially thinking about allowing the prover to hace parirings that return the 1 polynomial. I’m noticing this allows to make some part of the verifying values irrelevant. As a result, I actually do have clear examples in mind regarding the paper about when no public inputs are used or they are allowed to be all set to 0 but understanding the case about the public inputs requires to understand how proving works whereas the proving key can even be completely thrown away in the former scenario.

In Ethereum, assuming there’s no public inputs, it’s checked as e(A,B)\times e(vk,alpha1,vk.alpha2)\times e(C,vk.delta2)==1 So if C is the point at infinity a part of the Groth16 verification key will cancel out.

1 Like

The caller is supposed to check. It’s the same as point multiplication. 0.G = 0. You want to avoid using a secret key of 0.

Yes I know and it’s very obvious when public inputs aren’t used or allowed to be null, but my problem is when using public inputs : does the possibility of e(C,vk.delta2)==1 or instead even e(A,B)==1 would allow to forge public inputs while still having e(A,B)\times e(vk.alpha1,vk.alpha2)\times e(public\_inputs,vk.gamma)\times e(C,vk.delta2) ==1 given vk.X values are the verification key and the public_inputs G1’s point can’t be the point at infinity since it’s computed by the verifier ?

Is it safe in the case of Groth16 if the caller doesn’t check ?

If you don’t know, then just do the check.

Hi, my real point is I found a large implementation that don’t do the check. If there’s a risk, the only way to move funds would be to hack it again.I’m meaning to find a set of point A and B

It’s obvious how to hack it if the equation can be turned into e(A,B)\times e(vk.alpha1,vk.alpha2)==1 but since there’s public inputs it’s : e(A,B)\times e(vk.alpha1,vk.alpha2)\times e(public\_inputs,vk.gamma)==1

1 Like

Ok you nerdsniped me :sweat_smile:

The proof verification equation (from section 3.2 of [Groth2016]) is:

  • [A]_1 \cdot [B]_2 = [\alpha]_1 \cdot [\beta]_2 + \sum_{i=0}^{\ell} a_i \left[ \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma} \right]_1 \cdot [\gamma]_2 + [C]_1 \cdot [\delta]_2

The notation here is additive, i.e. it is in terms of the indices of points in the relevant groups (shown by the subscript, e.g. for a , [A]_1 means the index of A in \mathbb{G}_1).

Call a Groth16 proof proof \pi = (A, B, C) with any of A, B, or C a point at infinity “degenerate”. We can prove that degenerate proofs do not help to break soundness.

Partition the cases of degenerate proofs as follows:
a) [A]_1 = 0 and/or [B]_2 = 0 (so the LHS of the verification equation in additive form is 0).
b) [C]_1 = 0 and [A]_1 \neq 0.

In case a), for the proof to be valid we would need 0 = [\alpha]_1 \cdot [\beta]_2 + \sum_{i=0}^{\ell} a_i \left[ \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma} \right]_1 \cdot [\gamma]_2 + [C]_1 \cdot [\delta]_2.

It is infeasible to find a satisfying C given that \alpha, \beta, \gamma, and \delta are chosen as random group elements with unknown discrete logarithms.

In case b), we can make use of the rerandomizability property of Groth16 stated in [BKSV2020]. Let p be the group order. For any r_1, r_2 \in \mathbb{Z}^*_p, there is a “rerandomized” proof that is valid whenever the input proof is. Figure 1 of [BKSV2020] gives the rerandomization algorithm. With minor changes in notation, it is:

\mathsf{Rand}(\sigma, \pi = (A, B, C)):
\hspace{1em} r_1, r_2 \leftarrow^{\kern-0.85em\small\$} \mathbb{Z}^*_p
\hspace{1em} a := (1/r_1) A;\; b := r_1 B + r_1 r_2 [\delta]_2;\; c := C + r_2 a
\hspace{1em} \textbf{return } (a, b, c)

Note that r_1 and r_2 need not actually be random. So in case b), where C = \mathcal{O}_1 and A \neq \mathcal{O}_1, choose r_1 = 1 and any r_2 such that B \neq -r_2 [\delta]_2. This gives a nondegenerate proof that is valid when the input proof is. Therefore, if the proof system allowing degenerate proofs is unsound, then so is the proof system disallowing them. This means that the system allowing degenerate proofs is just as secure for soundness as the system that disallows them.


Note that I am not recommending that points at infinity be allowed in proofs. There is still no good reason to allow them. In particular, just because the idealized proof system with correct handling of exceptional cases is still sound, does not mean that any particular implementation will correctly handle those cases.

1 Like