- Generated by
1.9.8
|
Barretenberg
The ZK-SNARK library at the core of Aztec
|
An efficient verifier for the evaluation proofs of multilinear polynomials and their shifts. More...
#include <shplemini.hpp>
Static Public Member Functions | |
| template<typename Transcript > | |
| static BatchOpeningClaim< Curve > | compute_batch_opening_claim (std::span< const Fr > padding_indicator_array, ClaimBatcher &claim_batcher, const std::vector< Fr > &multivariate_challenge, const Commitment &g1_identity, const std::shared_ptr< Transcript > &transcript, const RepeatedCommitmentsData &repeated_commitments={}, const bool has_zk=false, bool *consistency_checked=nullptr, const std::array< Commitment, NUM_LIBRA_COMMITMENTS > &libra_commitments={}, const Fr &libra_univariate_evaluation=Fr{ 0 }, const std::vector< Commitment > &sumcheck_round_commitments={}, const std::vector< std::array< Fr, 3 > > &sumcheck_round_evaluations={}) |
| Non-padding version of compute_batch_opening_claim. Used by all native verifiers and by recursive Translator and ECCVM verifiers. | |
| static void | batch_gemini_claims_received_from_prover (std::span< const Fr > padding_indicator_array, const std::vector< Commitment > &fold_commitments, std::span< const Fr > gemini_neg_evaluations, std::span< const Fr > gemini_pos_evaluations, std::span< const Fr > inverse_vanishing_evals, std::span< const Fr > shplonk_batching_challenge_powers, std::vector< Commitment > &commitments, std::vector< Fr > &scalars, Fr &constant_term_accumulator) |
Place fold polynomial commitments to commitments and compute the corresponding scalar multipliers. | |
| static void | remove_repeated_commitments (std::vector< Commitment > &commitments, std::vector< Fr > &scalars, const RepeatedCommitmentsData &repeated_commitments, bool has_zk) |
| Combines scalars of repeating commitments to reduce the number of scalar multiplications performed by the verifier. | |
| static void | add_zk_data (const size_t virtual_log_n, std::vector< Commitment > &commitments, std::vector< Fr > &scalars, Fr &constant_term_accumulator, const std::array< Commitment, NUM_LIBRA_COMMITMENTS > &libra_commitments, const std::array< Fr, NUM_SMALL_IPA_EVALUATIONS > &libra_evaluations, const Fr &gemini_evaluation_challenge, const std::vector< Fr > &shplonk_batching_challenge_powers, const Fr &shplonk_evaluation_challenge) |
| Add the opening data corresponding to Libra masking univariates to the batched opening claim. | |
| static void | batch_sumcheck_round_claims (std::vector< Commitment > &commitments, std::vector< Fr > &scalars, Fr &constant_term_accumulator, const std::vector< Fr > &multilinear_challenge, const std::vector< Fr > &shplonk_batching_challenge_powers, const Fr &shplonk_evaluation_challenge, const std::vector< Commitment > &sumcheck_round_commitments, const std::vector< std::array< Fr, 3 > > &sumcheck_round_evaluations) |
| Adds the Sumcheck data into the Shplemini BatchOpeningClaim. | |
Private Types | |
| using | Fr = typename Curve::ScalarField |
| using | GroupElement = typename Curve::Element |
| using | Commitment = typename Curve::AffineElement |
| using | VK = VerifierCommitmentKey< Curve > |
| using | ShplonkVerifier = ShplonkVerifier_< Curve > |
| using | GeminiVerifier = GeminiVerifier_< Curve > |
| using | ClaimBatcher = ClaimBatcher_< Curve > |
An efficient verifier for the evaluation proofs of multilinear polynomials and their shifts.
This Verifier combines verifiers from four protocols:
Important Observation: From step 1 to step 4, the Verifier is not required to hash any results of its group operations. Therefore, they could be performed at the very end, i.e. by the opening protocol of a chosen univariate PCS. Because of this and the shape of the pairing check in Shplonk, various batch_mul calls could be reduced to a single batch_mul call. This way we minimize the number of gates in the resulting recursive verifier circuits and save some group operations in the native setting.
The method compute_batch_opening_claim receives commitments to all prover polynomials, their claimed evaluations, the sumcheck challenge, the group element \( [1]_1 \), and a pointer to the transcript. Its logic could be divided into several steps:
\[ \text{batch_mul} (\text{commitments},\ \text{scalars}) = \text{shplonk_opening_claim}.\text{point} \]
and the sizes of 'commitments' and 'scalars' are equal to:\[ \#\text{claimed_evaluations} + \text{log_n} + 2 \]
The output triple is either fed to the corresponding KZG method or IPA method. In the case of KZG, we reduce \( 6 \) batch_mul calls needed for the verification of the multivariate evaluation claims to the single batch_mul described above. In the case of IPA, the total number of batch_mul calls needed to verify the multivariate evaluation claims is reduced by \( 5 \).
Definition at line 189 of file shplemini.hpp.
|
private |
Definition at line 196 of file shplemini.hpp.
|
private |
Definition at line 192 of file shplemini.hpp.
|
private |
Definition at line 190 of file shplemini.hpp.
|
private |
Definition at line 195 of file shplemini.hpp.
|
private |
Definition at line 191 of file shplemini.hpp.
|
private |
Definition at line 194 of file shplemini.hpp.
|
private |
Definition at line 193 of file shplemini.hpp.
|
inlinestatic |
Add the opening data corresponding to Libra masking univariates to the batched opening claim.
After verifying ZK Sumcheck, the verifier has to validate the claims about the evaluations of Libra univariates used to mask Sumcheck round univariates. To minimize the overhead of such openings, we continue the Shplonk batching started in Gemini, i.e. we add new claims multiplied by a suitable power of the Shplonk batching challenge and re-use the evaluation challenge sampled to prove the evaluations of Gemini polynomials.
| commitments | |
| scalars | |
| libra_commitments | |
| libra_univariate_evaluations | |
| multivariate_challenge | |
| shplonk_batching_challenge | |
| shplonk_evaluation_challenge |
Definition at line 591 of file shplemini.hpp.
|
inlinestatic |
Place fold polynomial commitments to commitments and compute the corresponding scalar multipliers.
Once the commitments to Gemini "fold" polynomials \( A_i \) and their negative evaluations, i.e. \( A_i(-r^{2^i}) \), for \( i = 1, \ldots, d - 1 \), are obtained, and the verifier has reconstructed the positive fold evaluation \( A_i(r^{2^i}) \) for \( i=1, \ldots, d- 1 \), it performs the following operations:
\[ \left( \text{com}(A_1), \text{com}(A_2), \ldots, \text{com}(A_{d-1}) \right) \]
to the 'commitments' vector.\begin{align} \frac{\nu^2}{z - r^2} + \frac{\nu^3}{z + r^2}, \frac{\nu^4}{z - r^4} + \frac{\nu^5}{z + r^4}, \ldots, \frac{\nu^{2 \cdot d} } {z - r^{2^{d-1}}} + \frac{\nu^{2 \cdot d + 1}}{z + r^{2^{d-1}}} \end{align}
and multiplies them against the entries ofpadding_indicator_array. The commitments \( [A_1]_1, \ldots,
[A_{d-1}]_1 \) are multiplied by these scalars in the final batch_mul perfomed by KZG or IPA. Since padding_indicator_array[i] = 1 for i < log_n, and 0 otherwise, it ensures that the contributions from "dummy" rounds do not affect the final batch mul.\begin{align} \frac{\nu^{2 i} \cdot A_i\left(r^{2^i} \right)}{z - r^{2^i}} + \frac{\nu^{2 \cdot i+1} \cdot A_i\left(-r^{2^i}\right)}{z+ r^{2^i}} \end{align}
for \( i = 1, \ldots, d-1 \) and adds them to the 'constant_term_accumulator'.| padding_indicator_array | An array with first log_n entries equal to 1, and the remaining entries are 0. |
| fold_commitments | A vector containing the commitments to the Gemini fold polynomials \( A_i \). |
| gemini_neg_evaluations | The evaluations of Gemini fold polynomials \( A_i \) at \( -r^{2^i} \) for \( i = 0, \ldots, d - 1 \). |
| gemini_pos_evaluations | The evaluations of Gemini fold polynomials \( A_i \) at \( r^{2^i} \) for \( i = 0, \ldots, d - 1 \) |
| inverse_vanishing_evals |
iline 453 \( 1/(z − r), 1/(z + r), 1/(z - r^2), 1/(z + r^2), \ldots, 1/(z - r^{2^{d-1}}), 1/(z + r^{2^{-1}}) \)
| shplonk_batching_challenge_powers | A vector of powers of \( \nu \) used to batch all univariate claims. |
| commitments | Output vector where the commitments to the Gemini fold polynomials will be stored. |
| scalars | Output vector where the computed scalars will be stored. |
| constant_term_accumulator | The accumulator for the summands of the Shplonk constant term. |
Definition at line 459 of file shplemini.hpp.
|
inlinestatic |
Adds the Sumcheck data into the Shplemini BatchOpeningClaim.
This method computes denominators for the evaluations of Sumcheck Round Unviariates, combines them with powers of the Shplonk batching challenge ( \(\nu\)), and appends the resulting batched scalar factors to scalars. It also updates commitments with Sumcheck's round commitments. The constant_term_accumulator is incremented by each round's constant term contribution.
Specifically, for round \(i\) (with Sumcheck challenge \(u_i\)), we define:
\[ \alpha_i^0 = \frac{\nu^{k+3i}}{z}, \quad \alpha_i^1 = \frac{\nu^{k+3i+1}}{z - 1}, \quad \alpha_i^2 = \frac{\nu^{k+3i+2}}{z - u_i}, \]
where \( z\) is the Shplonk evaluation challenge, \(\nu\) is the batching challenge, and \(k\) is an offset exponent equal to num_gemini_claims + NUM_INTERLEAVING_CLAIMS + NUM_LIBRA_EVALATIONS, where num_gemini_claims = 2 * log_n. Then:
scalars is \[ \text{batched_scaling_factor}_i \;=\; -\bigl(\alpha_i^0 + \alpha_i^1 + \alpha_i^2\bigr). \]
\[ \text{const_term_contribution}_i \;=\; \alpha_i^0 \cdot S_i(0) + \alpha_i^1 \cdot S_i(1) + \alpha_i^2 \cdot S_i\bigl(u_i\bigr), \]
where \(S_i(x)\) denotes the Sumcheck round- \(i\) univariate polynomial. This contribution is added toconstant_term_accumulator.| log_n | |
| commitments | |
| scalars | |
| constant_term_accumulator | |
| multilinear_challenge | |
| shplonk_batching_challenge | |
| shplonk_evaluation_challenge | |
| sumcheck_round_commitments | |
| sumcheck_round_evaluations |
Definition at line 675 of file shplemini.hpp.
|
inlinestatic |
Non-padding version of compute_batch_opening_claim. Used by all native verifiers and by recursive Translator and ECCVM verifiers.
Definition at line 205 of file shplemini.hpp.
|
inlinestatic |
Combines scalars of repeating commitments to reduce the number of scalar multiplications performed by the verifier.
The Shplemini verifier gets the access to multiple groups of commitments, some of which are duplicated because they correspond to polynomials whose shifts also evaluated or used in concatenation groups in Translator. This method combines the scalars associated with these repeating commitments, reducing the total number of scalar multiplications required during the verification.
More specifically, the Shplemini verifier receives two or three groups of commitments: get_unshifted() and get_to_be_shifted() in the case of Ultra, Mega, and ECCVM Flavors; and get_unshifted_without_interleaved(), get_to_be_shifted(), and get_groups_to_be_interleaved() in the case of the TranslatorFlavor. The commitments are then placed in this specific order in a BatchOpeningClaim object containing a vector of commitments and a vector of scalars. The ranges with repeated commitments belong to the Flavors. This method iterates over these ranges and sums the scalar multipliers corresponding to the same group element. After combining the scalars, we erase corresponding entries in both vectors.
Definition at line 514 of file shplemini.hpp.
1.9.8