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)

Technology
21

That’s purely an issue of notation, not semantics. I was using the notation from Groth’s paper (which was convenient because [BKSV2020] also uses additive notation). Everything in my comment could be trivially rewritten multiplicatively.

(Actually, EIP 197 does use additive notation for the verification equation, it just writes \mathtt{log\_P1(a1)} in place of [\mathtt{a1}]_1.)

That is case b) in my comment.

1 Like
22

Except it’s verified as multiplication inside it’s implementation used by more than 90% of nodes. To me it seems doing +1 is different from doing ×1. The difference between the 2 is that the pairing is fully nullified in the later case…

Hence why pairing that contains point at infinity are completely skipped as an optimization :

if a[i].p.IsInfinity() || b[i].p.IsInfinity() {
    continue
}
23

Multiplicative vs additive is just notation. “+1” is exactly the same as doing x1, though in additive notation that’s usually written as +0.

1 Like
24

Yep, but in my post the otpimal ate pairing of point at infinity is 1, not 0.

if a[i].p.IsInfinity() || b[i].p.IsInfinity() {
    continue // omit that pairing
}
25

Yes. That doesn’t change anything. The pairing of point at infinity is the identity element of the extension prime field, whatever you write it as.

1 Like
26

Ok. It’s possible to use a degenerate proof only if the original proof is truely genuine when there’s public inputs. But does that means it’s possible to verify the proof along it’s public inputs using only 3 pairings instead of 4 ?

I’m not saying this should be done of course.

27

It’s already clear from the verification equation that you don’t need four pairings, even before any optimizations. (Btw where were you getting the e(vk.alpha1, vk.alpha2) term from? That’s not in [Groth16].)

The number of operations needed for verification is given by Appendix B.2 of the Zcash protocol spec.

Let \ell be the number of public input elements. We neglect some cheap operations.

Non-batched verification of a single proof takes:

  • 2 point decompressions in \mathbb{G}_1, and 1 in \mathbb{G}_2;
  • 2 subgroup checks in \mathbb{G}_1 (if it is not prime-order), and 1 in \mathbb{G}_2 (always);
  • 3 Miller Loops, two of which have fixed second input;
  • a fixed-base multiscalar mul in \mathbb{G}_1 with \ell+1 scalars (if verification can be variable-time, these are the width of the actual inputs);
  • one final exponentiation.

Batched verification of N proofs takes:

  • 2N point decompressions in \mathbb{G}_1, and N in \mathbb{G}_2;
  • 2N subgroup checks in \mathbb{G}_1 (if it is not prime-order), and N in \mathbb{G}_2 (always);
  • N + 2 Miller Loops, two of which have fixed second input;
  • a variable-base multiscalar mul in \mathbb{G}_1 with N 128-bit scalars;
  • a fixed-base multiscalar mul in \mathbb{G}_1 with \ell+1 full-width scalars;
  • one full-width exponentiation in \mathbb{G}_T;
  • one final exponentiation.
1 Like