Score:1

How many pairings are needed to verify beta term in GGPR13 zk-snark? Pinocchio paper says 3 but I count 4

in flag

The Pinocchio paper contains a description of the GGPR protocol (Protocol 1), and states that verification requires "8 pairings for the $\alpha$ terms, and 3 for the $\beta$ term". However I can't figure out how to verify the $\beta$ term with 3 pairings, it seems to require 4.

For context, the proof is given as:

$$ ( g^{v_{mid}}, g^w, g^y, g^h, g^{\alpha v_{mid}}, g^{\alpha w}, g^{\alpha y}, g^{\alpha h}, g^{\beta_v v_{mid} + \beta_w w + \beta_y y} ) $$

Where $v_{mid}, w, y, h$ are polynomials evaluated at point $s$.

The verifier key is given as

$$ (g^1, g^\alpha, g^\gamma, g^{\beta_v \gamma}, g^{\beta_w \gamma}, g^{\beta_y \gamma}, ... ) $$

For bilinear map $e$, the 8 pairings for the $\alpha$ terms are clear, in the form of 4 pairs like $e(g^w, g^\alpha) = e(g^{\alpha w}, g)$, with one pair for each of $v_{mid}, w, y, h$. For the $\beta$ term I would expect verification to occur using the following 4 pairings:

$$ e(g^{\beta_v v_{mid} + \beta_w w + \beta_y y}, g^{\gamma}) = e(g^{v_{mid}}, g^{\beta_v \gamma})e(g^{w}, g^{\beta_w \gamma})e(g^{y}, g^{\beta_y \gamma}) $$

Am I missing something that would allow this $\beta$ term to be verified in only 3 pairings?

For additional context, the GGPR paper itself doesn't even mention the use of pairings here, it instead says (page 51):

"Using the quadratic root detection, V confirms that ... $\gamma Z - (\beta_v \gamma)v_{mid} - (\beta_w \gamma)w - (\beta_y \gamma)y = 0$"

where $Z = \beta_v v_{mid} + \beta_w w + \beta_y y$

Thanks!

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.