small_subgroup_ipa.cpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Planned, auditors: [Khashayar], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#include "barretenberg/commitment_schemes/small_subgroup_ipa/small_subgroup_ipa.hpp"
#include "barretenberg/commitment_schemes/utils/test_settings.hpp"
#include "barretenberg/constants.hpp"
#include "barretenberg/ecc/curves/bn254/bn254.hpp"
#include "barretenberg/eccvm/eccvm_flavor.hpp"
#include "barretenberg/eccvm/eccvm_short_monomial_flavor.hpp"
#include "barretenberg/eccvm/eccvm_translation_data.hpp"
#include "barretenberg/ext/starknet/flavor/ultra_starknet_zk_flavor.hpp"
#include "barretenberg/flavor/mega_zk_flavor.hpp"
#include "barretenberg/flavor/ultra_keccak_zk_flavor.hpp"
#include "barretenberg/flavor/ultra_zk_flavor.hpp"
#include "barretenberg/polynomials/polynomial.hpp"
#include "barretenberg/polynomials/univariate.hpp"
#include "barretenberg/stdlib/primitives/curves/grumpkin.hpp"
#include "barretenberg/sumcheck/zk_sumcheck_data.hpp"
#include "barretenberg/translator_vm/translator_flavor.hpp"
 
#include <array>
#include <type_traits>
#include <vector>
 
namespace bb {
 
// Default constructor to initialize all common members.
template <typename Flavor>
SmallSubgroupIPAProver<Flavor>::SmallSubgroupIPAProver(const std::shared_ptr<typename Flavor::Transcript>& transcript,
                                                       typename Flavor::CommitmentKey commitment_key)
    : interpolation_domain{}
    , concatenated_polynomial(MASKED_CONCATENATED_WITNESS_LENGTH)
    , concatenated_lagrange_form(SUBGROUP_SIZE)
    , challenge_polynomial(SUBGROUP_SIZE)
    , challenge_polynomial_lagrange(SUBGROUP_SIZE)
    , grand_sum_polynomial_unmasked(SUBGROUP_SIZE)
    , grand_sum_polynomial(MASKED_GRAND_SUM_LENGTH)
    , grand_sum_identity_polynomial(GRAND_SUM_IDENTITY_LENGTH)
    , grand_sum_identity_quotient(QUOTIENT_LENGTH)
    , transcript(transcript)
{
    // Reallocate the commitment key if necessary. This is an edge case with SmallSubgroupIPA since it has
    // polynomials that may exceed the circuit size.
    if (commitment_key.srs_size < MASKED_GRAND_SUM_LENGTH) {
        commitment_key = typename Flavor::CommitmentKey(MASKED_GRAND_SUM_LENGTH);
    };
    this->commitment_key = commitment_key;
};
 
template <typename Flavor>
SmallSubgroupIPAProver<Flavor>::SmallSubgroupIPAProver(ZKSumcheckData<Flavor>& zk_sumcheck_data,
                                                       const std::vector<FF>& multivariate_challenge,
                                                       const FF claimed_inner_product,
                                                       const std::shared_ptr<typename Flavor::Transcript>& transcript,
                                                       const typename Flavor::CommitmentKey& commitment_key)
    : SmallSubgroupIPAProver(transcript, commitment_key)
{
    this->claimed_inner_product = claimed_inner_product;
    interpolation_domain = zk_sumcheck_data.interpolation_domain;
    concatenated_polynomial = zk_sumcheck_data.libra_concatenated_monomial_form;
    concatenated_lagrange_form = zk_sumcheck_data.libra_concatenated_lagrange_form;
    witness_commitments[0] = zk_sumcheck_data.libra_concatenation_commitment;
 
    label_prefix = "Libra:";
    // Extract the evaluation domain computed by ZKSumcheckData
    if constexpr (std::is_same_v<Curve, curve::BN254>) {
        bn_evaluation_domain = std::move(zk_sumcheck_data.bn_evaluation_domain);
    }
 
    // Construct the challenge polynomial in Lagrange basis, compute its monomial coefficients
    compute_challenge_polynomial(multivariate_challenge);
}
 
template <typename Flavor>
SmallSubgroupIPAProver<Flavor>::SmallSubgroupIPAProver(TranslationData<typename Flavor::Transcript>& translation_data,
                                                       const FF evaluation_challenge_x,
                                                       const FF batching_challenge_v,
                                                       const std::shared_ptr<typename Flavor::Transcript>& transcript,
                                                       const typename Flavor::CommitmentKey& commitment_key)
    : SmallSubgroupIPAProver(transcript, commitment_key)
 
{
    // TranslationData is Grumpkin-specific
    if constexpr (std::is_base_of_v<ECCVMFlavor, Flavor> || std::is_same_v<Flavor, GrumpkinSettings>) {
        label_prefix = "Translation:";
        interpolation_domain = translation_data.interpolation_domain;
        concatenated_polynomial = translation_data.masked_concatenated_polynomial;
        concatenated_lagrange_form = translation_data.concatenated_polynomial_lagrange;
        witness_commitments[0] = translation_data.masked_concatenated_commitment;
 
        // Construct the challenge polynomial in Lagrange basis, compute its monomial coefficients
        compute_eccvm_challenge_polynomial(evaluation_challenge_x, batching_challenge_v);
 
        // The prover computes the inner product of the challenge polynomial and the concatenation of
        // the masking terms. This value is used to "denoise" the masked batched evaluation of
        // `translation_polynomials` contained in `translation_data`.
        claimed_inner_product = compute_claimed_translation_inner_product(translation_data);
        transcript->send_to_verifier(label_prefix + "masking_term_eval", claimed_inner_product);
    }
}
 
template <typename Flavor> void SmallSubgroupIPAProver<Flavor>::prove()
{
 
    // Construct unmasked grand sum polynomial in Lagrange basis, compute its monomial coefficients and mask it
    compute_grand_sum_polynomial();
 
    // Send masked commitment [A + Z_H * R] to the verifier, where R is of degree 2
    witness_commitments[1] = commitment_key.commit(grand_sum_polynomial);
    transcript->send_to_verifier(label_prefix + "grand_sum_commitment", witness_commitments[1]);
 
    // Compute C(X)
    compute_grand_sum_identity_polynomial();
 
    // Compute Q(X)
    compute_grand_sum_identity_quotient();
 
    // Send commitment [Q] to the verifier
    witness_commitments[2] = commitment_key.commit(grand_sum_identity_quotient);
    transcript->send_to_verifier(label_prefix + "quotient_commitment", witness_commitments[2]);
}
 
template <typename Flavor>
void SmallSubgroupIPAProver<Flavor>::compute_challenge_polynomial(const std::vector<FF>& multivariate_challenge)
{
    std::vector<FF> coeffs_lagrange_basis =
        compute_challenge_polynomial_coeffs<typename Flavor::Curve>(multivariate_challenge);
 
    challenge_polynomial_lagrange = Polynomial<FF>(coeffs_lagrange_basis);
 
    // Compute monomial coefficients
    challenge_polynomial =
        compute_monomial_coefficients(coeffs_lagrange_basis, interpolation_domain, bn_evaluation_domain);
}
template <typename Flavor>
void SmallSubgroupIPAProver<Flavor>::compute_eccvm_challenge_polynomial(const FF evaluation_challenge_x,
                                                                        const FF batching_challenge_v)
{
 
    std::vector<FF> coeffs_lagrange_basis = compute_eccvm_challenge_coeffs<typename Flavor::Curve>(
        evaluation_challenge_x, batching_challenge_v, NUM_TRANSLATION_EVALUATIONS, NUM_DISABLED_ROWS_IN_SUMCHECK);
 
    challenge_polynomial_lagrange = Polynomial<FF>(coeffs_lagrange_basis);
 
    // Compute monomial coefficients
    challenge_polynomial = Polynomial<FF>(interpolation_domain, coeffs_lagrange_basis, SUBGROUP_SIZE);
}
template <typename Flavor> void SmallSubgroupIPAProver<Flavor>::compute_grand_sum_polynomial()
{
    // The masking accumulation below (`+=`) relies on the constructor's zero-initialization of
    // grand_sum_polynomial, so this must run exactly once per instance.
    grand_sum_lagrange_coeffs[0] = 0;
 
    // Compute the grand sum coefficients recursively
    for (size_t idx = 1; idx < SUBGROUP_SIZE; idx++) {
        size_t prev_idx = idx - 1;
        grand_sum_lagrange_coeffs[idx] =
            grand_sum_lagrange_coeffs[prev_idx] +
            challenge_polynomial_lagrange.at(prev_idx) * concatenated_lagrange_form.at(prev_idx);
    };
 
    //  Get the coefficients in the monomial basis
    grand_sum_polynomial_unmasked =
        compute_monomial_coefficients(grand_sum_lagrange_coeffs, interpolation_domain, bn_evaluation_domain);
 
    //  Generate random masking_term of degree 2
    auto masking_term = bb::Univariate<FF, GRAND_SUM_MASKING_TERM_LENGTH>::get_random();
 
    grand_sum_polynomial += grand_sum_polynomial_unmasked;
    // Since Z_H(X) = X^|H| - 1, its product with the masking term R(X) is given by X^{H}*R(X) - R(X). Therefore
    // to mask A, we subtract the coefficients of R from the first GRAND_SUM_MASKING_TERM_LENGTH coefficients
    // of A and by set the coefficients A_{i+SUBGROUP_SIZE} to be equal to R_i
    for (size_t idx = 0; idx < GRAND_SUM_MASKING_TERM_LENGTH; idx++) {
        grand_sum_polynomial.at(idx) -= masking_term.value_at(idx);
        grand_sum_polynomial.at(idx + SUBGROUP_SIZE) += masking_term.value_at(idx);
    }
};
 
template <typename Flavor> void SmallSubgroupIPAProver<Flavor>::compute_grand_sum_identity_polynomial()
{
    // The accumulations below (`+=` / `-=`) rely on the constructor's zero-initialization of
    // grand_sum_identity_polynomial, so this must run exactly once per instance.
    // Compute shifted grand sum polynomial A(gX)
    Polynomial<FF> shifted_grand_sum(MASKED_GRAND_SUM_LENGTH);
 
    for (size_t idx = 0; idx < MASKED_GRAND_SUM_LENGTH; idx++) {
        shifted_grand_sum.at(idx) = grand_sum_polynomial.at(idx) * interpolation_domain[idx % SUBGROUP_SIZE];
    }
 
    const auto& [lagrange_first, lagrange_last] =
        compute_lagrange_first_and_last(interpolation_domain, bn_evaluation_domain);
 
    // Compute -F(X)*G(X), the negated product of challenge_polynomial and concatenated_polynomial
    for (size_t i = 0; i < MASKED_CONCATENATED_WITNESS_LENGTH; ++i) {
        for (size_t j = 0; j < SUBGROUP_SIZE; ++j) {
            grand_sum_identity_polynomial.at(i + j) -= concatenated_polynomial.at(i) * challenge_polynomial.at(j);
        }
    }
 
    // Compute - F(X) * G(X) + A(gX) - A(X)
    for (size_t idx = 0; idx < MASKED_GRAND_SUM_LENGTH; idx++) {
        grand_sum_identity_polynomial.at(idx) += shifted_grand_sum.at(idx) - grand_sum_polynomial.at(idx);
    }
 
    // Multiply -F(X) * G(X) + A(gX) - A(X) by X - g^{-1}:
    // 1. Multiply by X
    for (size_t idx = GRAND_SUM_IDENTITY_LENGTH - 1; idx > 0; idx--) {
        grand_sum_identity_polynomial.at(idx) = grand_sum_identity_polynomial.at(idx - 1);
    }
    grand_sum_identity_polynomial.at(0) = FF(0);
    // 2. Subtract g^{-1}(A(gX) - A(X) - F(X) * G(X)).
    for (size_t idx = 0; idx < GRAND_SUM_IDENTITY_LENGTH - 1; idx++) {
        grand_sum_identity_polynomial.at(idx) -=
            grand_sum_identity_polynomial.at(idx + 1) * interpolation_domain[SUBGROUP_SIZE - 1];
    }
 
    // Add (L_1 + L_{|H|}) * A(X) to the result
    for (size_t i = 0; i < MASKED_GRAND_SUM_LENGTH; ++i) {
        for (size_t j = 0; j < SUBGROUP_SIZE; ++j) {
            grand_sum_identity_polynomial.at(i + j) +=
                grand_sum_polynomial.at(i) * (lagrange_first.at(j) + lagrange_last.at(j));
        }
    }
    // Subtract L_{|H|} * s
    for (size_t idx = 0; idx < SUBGROUP_SIZE; idx++) {
        grand_sum_identity_polynomial.at(idx) -= lagrange_last.at(idx) * claimed_inner_product;
    }
}
template <typename Flavor>
std::array<Polynomial<typename Flavor::Curve::ScalarField>, 2> SmallSubgroupIPAProver<
    Flavor>::compute_lagrange_first_and_last(const std::array<FF, SUBGROUP_SIZE>& interpolation_domain,
                                             const EvaluationDomain<FF>& bn_evaluation_domain)
{
    // Compute the monomial coefficients of L_1
    std::array<FF, SUBGROUP_SIZE> lagrange_coeffs;
    lagrange_coeffs[0] = FF(1);
    for (size_t idx = 1; idx < SUBGROUP_SIZE; idx++) {
        lagrange_coeffs[idx] = FF(0);
    }
 
    Polynomial<FF> lagrange_first_monomial =
        compute_monomial_coefficients(lagrange_coeffs, interpolation_domain, bn_evaluation_domain);
 
    // Compute the monomial coefficients of L_{|H|}, the last Lagrange polynomial
    lagrange_coeffs[0] = FF(0);
    lagrange_coeffs[SUBGROUP_SIZE - 1] = FF(1);
 
    Polynomial<FF> lagrange_last_monomial =
        compute_monomial_coefficients(lagrange_coeffs, interpolation_domain, bn_evaluation_domain);
 
    return { lagrange_first_monomial, lagrange_last_monomial };
}
 
template <typename Flavor> void SmallSubgroupIPAProver<Flavor>::compute_grand_sum_identity_quotient()
{
 
    auto remainder = grand_sum_identity_polynomial;
    for (size_t idx = GRAND_SUM_IDENTITY_LENGTH - 1; idx >= SUBGROUP_SIZE; idx--) {
        grand_sum_identity_quotient.at(idx - SUBGROUP_SIZE) = remainder.at(idx);
        remainder.at(idx - SUBGROUP_SIZE) += remainder.at(idx);
    }
}
 
template <typename Flavor>
typename Flavor::Curve::ScalarField SmallSubgroupIPAProver<Flavor>::compute_claimed_inner_product(
    ZKSumcheckData<Flavor>& zk_sumcheck_data,
    const std::vector<FF>& multivariate_challenge,
    const size_t& log_circuit_size)
{
    const FF libra_challenge_inv = zk_sumcheck_data.libra_challenge.invert();
    // Compute claimed inner product similarly to the SumcheckProver
    FF claimed_inner_product = FF{ 0 };
    size_t idx = 0;
    for (const auto& univariate : zk_sumcheck_data.libra_univariates) {
        claimed_inner_product += univariate.evaluate(multivariate_challenge[idx]);
        idx++;
    }
    // Libra univariates are multiplied by the Libra challenge in setup_auxiliary_data(), which needs to be undone.
    claimed_inner_product *= libra_challenge_inv / FF(1 << (log_circuit_size - 1));
    claimed_inner_product += zk_sumcheck_data.constant_term;
    return claimed_inner_product;
}
 
template <typename Flavor>
typename Flavor::Curve::ScalarField SmallSubgroupIPAProver<Flavor>::compute_claimed_translation_inner_product(
    TranslationData<typename Flavor::Transcript>& translation_data)
{
    FF claimed_inner_product{ 0 };
    if constexpr (std::is_base_of_v<ECCVMFlavor, Flavor> || std::is_same_v<Flavor, GrumpkinSettings>) {
        for (size_t idx = 0; idx < SUBGROUP_SIZE; idx++) {
            claimed_inner_product +=
                translation_data.concatenated_polynomial_lagrange.at(idx) * challenge_polynomial_lagrange.at(idx);
        }
    }
    return claimed_inner_product;
}
 
template <typename Flavor>
Polynomial<typename Flavor::Curve::ScalarField> SmallSubgroupIPAProver<Flavor>::compute_monomial_coefficients(
    std::span<FF> lagrange_coeffs,
    const std::array<FF, SUBGROUP_SIZE>& interpolation_domain,
    const EvaluationDomain<FF>& bn_evaluation_domain)
{
    using FF = typename Flavor::Curve::ScalarField;
    if constexpr (!std::is_same_v<typename Flavor::Curve, curve::BN254>) {
        return Polynomial<FF>(interpolation_domain, lagrange_coeffs, SUBGROUP_SIZE);
    } else {
        std::vector<FF> lagrange_last_ifft(SUBGROUP_SIZE);
        polynomial_arithmetic::ifft<FF>(lagrange_coeffs.data(), lagrange_last_ifft.data(), bn_evaluation_domain);
        return Polynomial<FF>(lagrange_last_ifft);
    }
}
 
// Instantiate with ZK Flavors
template class SmallSubgroupIPAProver<ECCVMFlavor>;
template class SmallSubgroupIPAProver<ECCVMShortMonomialFlavor>;
template class SmallSubgroupIPAProver<TranslatorFlavor>;
template class SmallSubgroupIPAProver<TranslatorShortMonomialFlavor>;
template class SmallSubgroupIPAProver<MegaZKFlavor>;
template class SmallSubgroupIPAProver<UltraZKFlavor>;
template class SmallSubgroupIPAProver<UltraKeccakZKFlavor>;
#ifdef STARKNET_GARAGA_FLAVORS
template class SmallSubgroupIPAProver<UltraStarknetZKFlavor>;
#endif
 
// Instantiations used in tests
template class SmallSubgroupIPAProver<BN254Settings>;
template class SmallSubgroupIPAProver<GrumpkinSettings>;
 
} // namespace bb