zk_sumcheck_data.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Khashayar], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
 
#include "barretenberg/common/assert.hpp"
#include "barretenberg/constants.hpp"
#include "barretenberg/ecc/curves/bn254/bn254.hpp"
#include "barretenberg/polynomials/polynomial.hpp"
#include "barretenberg/polynomials/univariate.hpp"
#include <array>
#include <tuple>
#include <vector>
 
namespace bb {
 
template <typename Flavor> struct ZKSumcheckData {
    using Curve = typename Flavor::Curve;
    using FF = typename Curve::ScalarField;
    using Commitment = typename Curve::AffineElement;
 
    static constexpr size_t SUBGROUP_SIZE = Curve::SUBGROUP_SIZE;
 
    static constexpr FF subgroup_generator = Curve::subgroup_generator;
 
    // The size of the LibraUnivariates.
    static constexpr size_t LIBRA_UNIVARIATES_LENGTH = Curve::LIBRA_UNIVARIATES_LENGTH;
 
    static constexpr FF one_half = FF(1) / FF(2);
 
    // Container for the evaluations of Libra Univariates that have to be proven.
    using ClaimedLibraEvaluations = std::vector<FF>;
 
    FF constant_term;
 
    EvaluationDomain<FF> bn_evaluation_domain = EvaluationDomain<FF>();
    std::array<FF, SUBGROUP_SIZE> interpolation_domain;
    // to compute product in lagrange basis
    Polynomial<FF> libra_concatenated_lagrange_form;
    Polynomial<FF> libra_concatenated_monomial_form;
    Commitment libra_concatenation_commitment;
 
    std::vector<Polynomial<FF>> libra_univariates{};
    size_t log_circuit_size{ 0 };
    FF libra_scaling_factor{ 1 };
    FF libra_challenge;
    FF libra_total_sum;
    FF libra_running_sum;
    ClaimedLibraEvaluations libra_evaluations;
 
    size_t univariate_length;
    // Default constructor
    ZKSumcheckData() = default;
 
    // Main constructor
    ZKSumcheckData(const size_t multivariate_d,
                   std::shared_ptr<typename Flavor::Transcript> transcript = nullptr,
                   const typename Flavor::CommitmentKey& commitment_key = typename Flavor::CommitmentKey())
        : constant_term(FF::random_element())
        , libra_concatenated_monomial_form(SUBGROUP_SIZE + WITNESS_MASKING_TERM_LENGTH)
        , libra_univariates(generate_libra_univariates(multivariate_d, LIBRA_UNIVARIATES_LENGTH))
        , log_circuit_size(multivariate_d)
        , univariate_length(LIBRA_UNIVARIATES_LENGTH)
 
    {
        // transcript defaults to nullptr but is dereferenced unconditionally below.
        BB_ASSERT(transcript != nullptr, "ZKSumcheckData: transcript must not be null");
 
        create_interpolation_domain();
 
        compute_concatenated_libra_polynomial();
 
        // If prover_instance is provided, commit to the concatenated and masked libra polynomial
        if (commitment_key.initialized()) {
            libra_concatenation_commitment = commitment_key.commit(libra_concatenated_monomial_form);
            transcript->send_to_verifier("Libra:concatenation_commitment", libra_concatenation_commitment);
        }
        // Compute the total sum of the Libra polynomials
        std::tie(libra_total_sum, libra_scaling_factor) = compute_libra_total_sum(libra_univariates, constant_term);
 
        // Send the Libra total sum to the transcript
        transcript->send_to_verifier("Libra:Sum", libra_total_sum);
 
        // Receive the Libra challenge from the transcript
        libra_challenge = transcript->template get_challenge<FF>("Libra:Challenge");
 
        // Initialize the Libra running sum
        libra_running_sum = libra_total_sum * libra_challenge;
 
        // Prepare the Libra data for the first round of sumcheck
 
        setup_auxiliary_data(libra_univariates, libra_scaling_factor, libra_challenge, libra_running_sum);
    }
 
    ZKSumcheckData(const size_t multivariate_d, const size_t univariate_length)
        : constant_term(FF::random_element())
        , libra_univariates(generate_libra_univariates(multivariate_d, univariate_length))
        , log_circuit_size(multivariate_d)
        , libra_challenge(FF::random_element())
        , univariate_length(univariate_length)
 
    {
        std::tie(libra_total_sum, libra_scaling_factor) = compute_libra_total_sum(libra_univariates, constant_term);
        libra_running_sum = libra_total_sum * libra_challenge;
        setup_auxiliary_data(libra_univariates, libra_scaling_factor, libra_challenge, libra_running_sum);
    }
    static std::vector<Polynomial<FF>> generate_libra_univariates(const size_t number_of_polynomials,
                                                                  const size_t univariate_length)
    {
        std::vector<Polynomial<FF>> libra_full_polynomials(number_of_polynomials);
 
        for (auto& libra_polynomial : libra_full_polynomials) {
            libra_polynomial = Polynomial<FF>::random(univariate_length);
        };
        return libra_full_polynomials;
    };
 
    static std::pair<FF, FF> compute_libra_total_sum(const std::vector<Polynomial<FF>>& libra_univariates,
                                                     const FF& constant_term)
    {
        FF total_sum = 0;
        FF scaling_factor = one_half;
 
        for (auto& univariate : libra_univariates) {
            total_sum += univariate.at(0) + univariate.evaluate(FF(1));
            scaling_factor *= 2;
        }
        total_sum *= scaling_factor;
 
        return { total_sum + constant_term * (1UL << libra_univariates.size()), scaling_factor };
    }
 
    static void setup_auxiliary_data(auto& libra_univariates,
                                     FF& libra_scaling_factor,
                                     const FF& libra_challenge,
                                     FF& libra_running_sum)
    {
        libra_scaling_factor *= libra_challenge; // \rho * 2^{d-1}
        for (auto& univariate : libra_univariates) {
            univariate *= libra_scaling_factor;
        };
        // subtract the contribution of the first libra univariate from libra total sum
        libra_running_sum += -libra_univariates[0].at(0) - libra_univariates[0].evaluate(FF(1));
        libra_running_sum *= one_half;
    }
 
    void create_interpolation_domain()
    {
        if constexpr (std::is_same_v<Curve, curve::BN254>) {
            bn_evaluation_domain = EvaluationDomain<FF>(SUBGROUP_SIZE, SUBGROUP_SIZE);
            if (bn_evaluation_domain.size > 0) {
                bn_evaluation_domain.compute_lookup_table();
            }
        }
 
        interpolation_domain[0] = FF{ 1 };
        for (size_t idx = 1; idx < SUBGROUP_SIZE; idx++) {
            interpolation_domain[idx] = interpolation_domain[idx - 1] * subgroup_generator;
        }
    }
 
    void compute_concatenated_libra_polynomial()
    {
        BB_ASSERT_LT(log_circuit_size * LIBRA_UNIVARIATES_LENGTH + 1,
                     SUBGROUP_SIZE,
                     "Concatenated Libra polynomial does not fit in the SmallSubgroupIPA subgroup");
        std::array<FF, SUBGROUP_SIZE> coeffs_lagrange_subgroup;
        coeffs_lagrange_subgroup[0] = constant_term;
 
        for (size_t idx = 1; idx < SUBGROUP_SIZE; idx++) {
            coeffs_lagrange_subgroup[idx] = FF{ 0 };
        }
 
        for (size_t poly_idx = 0; poly_idx < log_circuit_size; poly_idx++) {
            for (size_t idx = 0; idx < LIBRA_UNIVARIATES_LENGTH; idx++) {
                size_t idx_to_populate = 1 + poly_idx * LIBRA_UNIVARIATES_LENGTH + idx;
                coeffs_lagrange_subgroup[idx_to_populate] = libra_univariates[poly_idx].at(idx);
            }
        }
 
        libra_concatenated_lagrange_form = Polynomial<FF>(coeffs_lagrange_subgroup);
 
        bb::Univariate<FF, 2> masking_scalars = bb::Univariate<FF, 2>::get_random();
 
        Polynomial<FF> libra_concatenated_monomial_form_unmasked(SUBGROUP_SIZE);
        if constexpr (!std::is_same_v<Curve, curve::BN254>) {
            libra_concatenated_monomial_form_unmasked =
                Polynomial<FF>(interpolation_domain, coeffs_lagrange_subgroup, SUBGROUP_SIZE);
        } else {
            std::vector<FF> coeffs_lagrange_subgroup_ifft(SUBGROUP_SIZE);
            polynomial_arithmetic::ifft(
                coeffs_lagrange_subgroup.data(), coeffs_lagrange_subgroup_ifft.data(), bn_evaluation_domain);
            libra_concatenated_monomial_form_unmasked = Polynomial<FF>(coeffs_lagrange_subgroup_ifft);
        }
 
        for (size_t idx = 0; idx < SUBGROUP_SIZE; idx++) {
            libra_concatenated_monomial_form.at(idx) = libra_concatenated_monomial_form_unmasked.at(idx);
        }
 
        for (size_t idx = 0; idx < masking_scalars.size(); idx++) {
            libra_concatenated_monomial_form.at(idx) -= masking_scalars.value_at(idx);
            libra_concatenated_monomial_form.at(SUBGROUP_SIZE + idx) += masking_scalars.value_at(idx);
        }
    }
 
    void update_zk_sumcheck_data(const FF& round_challenge, const size_t round_idx)
    {
        static constexpr FF two_inv = FF(1) / FF(2);
        BB_ASSERT(round_idx < this->libra_univariates.size(), "update_zk_sumcheck_data: round_idx out of range");
        // when round_idx = d - 1, the update is not needed
        if (round_idx < this->log_circuit_size - 1) {
            for (auto& univariate : this->libra_univariates) {
                univariate *= two_inv;
            };
            // compute the evaluation \f$ \rho \cdot 2^{d-2-i} \çdot g_i(u_i) \f$
            const FF libra_evaluation = this->libra_univariates[round_idx].evaluate(round_challenge);
            BB_ASSERT(round_idx + 1 < this->libra_univariates.size(),
                      "update_zk_sumcheck_data: round_idx + 1 out of range");
            const auto& next_libra_univariate = this->libra_univariates[round_idx + 1];
            // update the running sum by adding g_i(u_i) and subtracting (g_i(0) + g_i(1))
            this->libra_running_sum += -next_libra_univariate.at(0) - next_libra_univariate.evaluate(FF(1));
            this->libra_running_sum *= two_inv;
 
            this->libra_running_sum += libra_evaluation;
            this->libra_scaling_factor *= two_inv;
 
            this->libra_evaluations.emplace_back(libra_evaluation / this->libra_scaling_factor);
        } else {
            // compute the evaluation of the last Libra univariate at the challenge u_{d-1}
            const FF libra_evaluation =
                this->libra_univariates[round_idx].evaluate(round_challenge) / this->libra_scaling_factor;
            // place the evalution into the vector of Libra evaluations
            this->libra_evaluations.emplace_back(libra_evaluation);
        };
    }
};
 
} // namespace bb