gemini.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/commitment_schemes/claim.hpp"
#include "barretenberg/commitment_schemes/claim_batcher.hpp"
#include "barretenberg/common/bb_bench.hpp"
#include "barretenberg/common/thread.hpp"
#include "barretenberg/polynomials/polynomial.hpp"
#include "barretenberg/transcript/transcript.hpp"
 
namespace bb {
 
namespace gemini {
template <class Fr> inline std::vector<Fr> powers_of_rho(const Fr& rho, const size_t num_powers)
{
    std::vector<Fr> rhos = { Fr(1), rho };
    rhos.reserve(num_powers);
    for (size_t j = 2; j < num_powers; j++) {
        rhos.emplace_back(rhos[j - 1] * rho);
    }
    return rhos;
};
 
template <class Fr> inline std::vector<Fr> powers_of_evaluation_challenge(const Fr& r, const size_t num_squares)
{
    std::vector<Fr> squares = { r };
    squares.reserve(num_squares);
    for (size_t j = 1; j < num_squares; j++) {
        squares.emplace_back(squares[j - 1].sqr());
    }
    return squares;
};
} // namespace gemini
 
template <typename Curve> class GeminiProver_ {
    using Fr = typename Curve::ScalarField;
    using Commitment = typename Curve::AffineElement;
    using Polynomial = bb::Polynomial<Fr>;
    using Claim = ProverOpeningClaim<Curve>;
 
  public:
    class PolynomialBatcher {
 
        size_t full_batched_size = 0; // size of the full batched polynomial (generally the circuit size)
 
        Polynomial batched_unshifted;            // linear combination of unshifted polynomials
        Polynomial batched_to_be_shifted_by_one; // linear combination of to-be-shifted polynomials
        Polynomial batched_interleaved;          // linear combination of interleaved polynomials
        // linear combination of the groups to be interleaved where polynomial i in the batched group is obtained by
        // linearly combining the i-th polynomial in each group
        std::vector<Polynomial> batched_group;
 
      public:
        RefVector<Polynomial> unshifted;                             // set of unshifted polynomials
        RefVector<Polynomial> to_be_shifted_by_one;                  // set of polynomials to be left shifted by 1
        RefVector<Polynomial> interleaved;                           // the interleaved polynomials used in Translator
        std::vector<RefVector<Polynomial>> groups_to_be_interleaved; // groups of polynomials to be interleaved
 
        PolynomialBatcher(const size_t full_batched_size)
            : full_batched_size(full_batched_size)
            , batched_unshifted(full_batched_size)
            , batched_to_be_shifted_by_one(Polynomial::shiftable(full_batched_size))
        {}
 
        bool has_unshifted() const { return unshifted.size() > 0; }
        bool has_to_be_shifted_by_one() const { return to_be_shifted_by_one.size() > 0; }
        bool has_interleaved() const { return interleaved.size() > 0; }
 
        // Set references to the polynomials to be batched
        void set_unshifted(RefVector<Polynomial> polynomials) { unshifted = polynomials; }
        void set_to_be_shifted_by_one(RefVector<Polynomial> polynomials) { to_be_shifted_by_one = polynomials; }
 
        void set_interleaved(RefVector<Polynomial> results, std::vector<RefVector<Polynomial>> groups)
        {
            // Ensure the Gemini subprotocol for interleaved polynomials operates correctly
            if (groups[0].size() % 2 != 0) {
                throw_or_abort("Group size must be even ");
            }
            interleaved = results;
            groups_to_be_interleaved = groups;
        }
 
        Polynomial compute_batched(const Fr& challenge)
        {
            Fr running_scalar(1);
            BB_BENCH_NAME("compute_batched");
            // lambda for batching polynomials; updates the running scalar in place
            auto batch = [&](Polynomial& batched, const RefVector<Polynomial>& polynomials_to_batch) {
                for (auto& poly : polynomials_to_batch) {
                    batched.add_scaled(poly, running_scalar);
                    running_scalar *= challenge;
                }
            };
 
            Polynomial full_batched(full_batched_size);
 
            // compute the linear combination F of the unshifted polynomials
            if (has_unshifted()) {
                batch(batched_unshifted, unshifted);
                full_batched += batched_unshifted; // A₀ += F
            }
 
            // compute the linear combination G of the to-be-shifted polynomials
            if (has_to_be_shifted_by_one()) {
                batch(batched_to_be_shifted_by_one, to_be_shifted_by_one);
                full_batched += batched_to_be_shifted_by_one.shifted(); // A₀ += G/X
            }
 
            // compute the linear combination of the interleaved polynomials and groups
            if (has_interleaved()) {
                batched_interleaved = Polynomial(full_batched_size);
                for (size_t i = 0; i < groups_to_be_interleaved[0].size(); ++i) {
                    batched_group.push_back(Polynomial(full_batched_size));
                }
 
                for (size_t i = 0; i < groups_to_be_interleaved.size(); ++i) {
                    batched_interleaved.add_scaled(interleaved[i], running_scalar);
                    // Use parallel chunking for the batching operations
                    parallel_for([this, running_scalar, i](const ThreadChunk& chunk) {
                        for (size_t j = 0; j < groups_to_be_interleaved[0].size(); ++j) {
                            batched_group[j].add_scaled_chunk(chunk, groups_to_be_interleaved[i][j], running_scalar);
                        }
                    });
                    running_scalar *= challenge;
                }
 
                full_batched += batched_interleaved;
            }
 
            return full_batched;
        }
 
        std::pair<Polynomial, Polynomial> compute_partially_evaluated_batch_polynomials(const Fr& r_challenge)
        {
            // Initialize A₀₊ and compute A₀₊ += F as necessary
            Polynomial A_0_pos(full_batched_size); // A₀₊
 
            if (has_unshifted()) {
                A_0_pos += batched_unshifted; // A₀₊ += F
            }
 
            Polynomial A_0_neg = A_0_pos;
 
            if (has_to_be_shifted_by_one()) {
                Fr r_inv = r_challenge.invert();       // r⁻¹
                batched_to_be_shifted_by_one *= r_inv; // G = G/r
 
                A_0_pos += batched_to_be_shifted_by_one; // A₀₊ += G/r
                A_0_neg -= batched_to_be_shifted_by_one; // A₀₋ -= G/r
            }
 
            return { A_0_pos, A_0_neg };
        };
        std::pair<Polynomial, Polynomial> compute_partially_evaluated_interleaved_polynomial(const Fr& r_challenge)
        {
            Polynomial P_pos(batched_group[0]);
            Polynomial P_neg(batched_group[0]);
 
            Fr current_r_shift_pos = r_challenge;
            Fr current_r_shift_neg = -r_challenge;
            for (size_t i = 1; i < batched_group.size(); i++) {
                // Add r^i * Pᵢ(X) to P₊(X)
                P_pos.add_scaled(batched_group[i], current_r_shift_pos);
                // Add (-r)^i * Pᵢ(X) to P₋(X)
                P_neg.add_scaled(batched_group[i], current_r_shift_neg);
                // Update the current power of r
                current_r_shift_pos *= r_challenge;
                current_r_shift_neg *= -r_challenge;
            }
 
            return { P_pos, P_neg };
        }
 
        size_t get_group_size() { return batched_group.size(); }
    };
 
    static std::vector<Polynomial> compute_fold_polynomials(const size_t log_n,
                                                            std::span<const Fr> multilinear_challenge,
                                                            const Polynomial& A_0,
                                                            const bool& has_zk = false);
 
    static std::pair<Polynomial, Polynomial> compute_partially_evaluated_batch_polynomials(
        const size_t log_n,
        PolynomialBatcher& polynomial_batcher,
        const Fr& r_challenge,
        const std::vector<Polynomial>& batched_groups_to_be_concatenated = {});
 
    static std::vector<Claim> construct_univariate_opening_claims(const size_t log_n,
                                                                  Polynomial&& A_0_pos,
                                                                  Polynomial&& A_0_neg,
                                                                  std::vector<Polynomial>&& fold_polynomials,
                                                                  const Fr& r_challenge);
 
    template <typename Transcript>
    static std::vector<Claim> prove(size_t circuit_size,
                                    PolynomialBatcher& polynomial_batcher,
                                    std::span<Fr> multilinear_challenge,
                                    const CommitmentKey<Curve>& commitment_key,
                                    const std::shared_ptr<Transcript>& transcript,
                                    bool has_zk = false);
 
}; // namespace bb
 
template <typename Curve> class GeminiVerifier_ {
    using Fr = typename Curve::ScalarField;
    using Commitment = typename Curve::AffineElement;
 
  public:
    static std::vector<Commitment> get_fold_commitments(const size_t virtual_log_n, auto& transcript)
    {
        std::vector<Commitment> fold_commitments;
        fold_commitments.reserve(virtual_log_n - 1);
        for (size_t i = 1; i < virtual_log_n; ++i) {
            const Commitment commitment =
                transcript->template receive_from_prover<Commitment>("Gemini:FOLD_" + std::to_string(i));
            fold_commitments.emplace_back(commitment);
        }
        return fold_commitments;
    }
 
    static std::vector<Fr> get_gemini_evaluations(const size_t virtual_log_n, auto& transcript)
    {
        std::vector<Fr> gemini_evaluations;
        gemini_evaluations.reserve(virtual_log_n);
 
        for (size_t i = 1; i <= virtual_log_n; ++i) {
            const Fr evaluation = transcript->template receive_from_prover<Fr>("Gemini:a_" + std::to_string(i));
            gemini_evaluations.emplace_back(evaluation);
        }
        return gemini_evaluations;
    }
 
    static std::vector<Fr> compute_fold_pos_evaluations(std::span<const Fr> padding_indicator_array,
                                                        const Fr& batched_evaluation,
                                                        std::span<const Fr> evaluation_point, // size = virtual_log_n
                                                        std::span<const Fr> challenge_powers, // size = virtual_log_n
                                                        std::span<const Fr> fold_neg_evals,   // size = virtual_log_n
                                                        Fr p_neg = Fr(0))
    {
        const size_t virtual_log_n = evaluation_point.size();
 
        std::vector<Fr> evals(fold_neg_evals.begin(), fold_neg_evals.end());
 
        Fr eval_pos_prev = batched_evaluation;
 
        std::vector<Fr> fold_pos_evaluations;
        fold_pos_evaluations.reserve(virtual_log_n);
 
        // Add the contribution of P-((-r)ˢ) to get A_0(-r), which is 0 if there are no interleaved polynomials
        evals[0] += p_neg;
        // Solve the sequence of linear equations
        for (size_t l = virtual_log_n; l != 0; --l) {
            // Get r²⁽ˡ⁻¹⁾
            const Fr& challenge_power = challenge_powers[l - 1];
            // Get uₗ₋₁
            const Fr& u = evaluation_point[l - 1];
            // Get A₍ₗ₋₁₎(−r²⁽ˡ⁻¹⁾)
            const Fr& eval_neg = evals[l - 1];
            // Compute the numerator
            Fr eval_pos = ((challenge_power * eval_pos_prev * 2) - eval_neg * (challenge_power * (Fr(1) - u) - u));
            // Divide by the denominator
            eval_pos *= (challenge_power * (Fr(1) - u) + u).invert();
 
            // If current index is bigger than log_n, we propagate `batched_evaluation` to the next
            // round.  Otherwise, current `eval_pos` A₍ₗ₋₁₎(r²⁽ˡ⁻¹⁾) becomes `eval_pos_prev` in the round l-2.
            eval_pos_prev =
                padding_indicator_array[l - 1] * eval_pos + (Fr{ 1 } - padding_indicator_array[l - 1]) * eval_pos_prev;
            // If current index is bigger than log_n, we emplace 0, which is later multiplied against
            // Commitment::one().
            fold_pos_evaluations.emplace_back(padding_indicator_array[l - 1] * eval_pos_prev);
        }
 
        std::reverse(fold_pos_evaluations.begin(), fold_pos_evaluations.end());
 
        return fold_pos_evaluations;
    }
};
 
} // namespace bb