Verify proper construction of the aggregate Goblin ECC op queue polynomials T_j, j = 1,2,3,4.
Let \(l_j\), \(r_j\), \(m_j\) be three vectors. The Merge wants to convince the verifier that the polynomials l_j, r_j, m_j for which they have sent commitments [l_j], [r_j], [m_j] satisfy
- m_j(X) = l_j(X) + X^l r_j(X) (1)
- deg(l_j(X)) < k (2) where k = shift_size.
To check condition (1), the verifier samples a challenge kappa and request from the prover a proof that the polynomial p_j(X) = l_j(kappa) + kappa^k r_j(kappa) - m_j(kappa) opens to 0 at kappa.
To check condition (2), the verifier requests from the prover the commitment to a polynomial g_j, and then requests proofs that l_j(1/kappa) = c g_j(kappa) = d Then, they verify c * kappa^{k-1} = d, which implies, up to negligible probability, that g_j(X) = X^{l-1} l_j(1/X), which means that deg(l_j(X)) < l.
The verifier must therefore check 12 opening claims: p_j(kappa) = 0, l_j(1/kappa), g_j(kappa) We use Shplonk to verify the claims with a single MSM (instead of computing [p_j] from [l_j], [r_j], [m_j] and then open it). We initialize the Shplonk verifier with the following commitments: [l_1], [r_1], [m_1], [g_1], ..., [l_4], [r_4], [m_4], [g_4] Then, we verify the various claims:
- p_j(kappa) = 0: The commitment to p_j is constructed from the commitments to l_j, r_j, m_j, so the claim passed to the Shplonk verifier specifies the indices of these commitments in the above vector: {4 * (j-1), 4 * (j-1) + 1, 4 * (j-1) + 2}, the coefficients reconstructing p_j from l_j, r_j, m_j: {1, kappa^k, -1}, and the claimed evaluation: 0.
- l_j(1/kappa) = v_j: The index in this case is {4 * (j-1)}, the coefficient is { 1 }, and the evaluation is v_j.
- g_j(kappa) = w_j: The index is {3 + 4 * (j-1)}, the coefficient is { 1 }, and the evaluation is w_j. The claims are passed in the following order: {kappa, 0}, {kappa, 0}, {kappa, 0}, {kappa, 0}, {1/kappa, v_1}, {kappa, w_1}, .., {1/kappa, v_4}, {kappa, w_4}
In the Goblin scenario, we have:
- \(l_j = t_j, r_j = T_{prev,j}, m_j = T_j\) if we are prepending the subtable
- \(l_j = T_{prev,j}, r_j = t_j, m_j = T_j\) if we are appending the subtable
- Parameters
-
| proof | |
| inputs_commitments | The commitments used by the Merge verifier |
- Returns
- std::pair<bool, TableCommitments> Pair of verification result and the commitments to the merged tables as read from the proof
Definition at line 62 of file merge_verifier.cpp.
1.9.8