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/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;
    rhos.reserve(num_powers);
    if (num_powers >= 1) {
        rhos.emplace_back(Fr(1));
    }
    for (size_t j = 1; 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)
        size_t actual_data_size_ = 0; // max end_index across all polynomials (actual data extent)
 
        Polynomial batched_unshifted;            // linear combination of unshifted polynomials
        Polynomial batched_to_be_shifted_by_one; // linear combination of to-be-shifted polynomials
 
        // Batched tails: small polynomials covering only the tail region (e.g. last NUM_MASKED_ROWS positions).
        // Populated during compute_batched if tails are registered.
        Polynomial batched_unshifted_tail_;
        Polynomial batched_shifted_tail_;
 
      public:
        RefVector<Polynomial> unshifted;            // set of unshifted polynomials
        RefVector<Polynomial> to_be_shifted_by_one; // set of polynomials to be left shifted by 1
 
        // Tails: small polynomials (e.g. masking values) to be batched with the same rho scalar
        // as their corresponding base polynomial. Pairs of (index in unshifted/shifted list, tail poly).
        std::vector<std::pair<size_t, Polynomial>> unshifted_tails_;
        std::vector<std::pair<size_t, Polynomial>> shifted_tails_;
 
        PolynomialBatcher(const size_t full_batched_size, const size_t actual_data_size = 0)
            : full_batched_size(full_batched_size)
            , actual_data_size_(actual_data_size == 0 ? full_batched_size : actual_data_size)
            , batched_unshifted(actual_data_size_, full_batched_size)
            , batched_to_be_shifted_by_one(Polynomial::shiftable(actual_data_size_, 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; }
 
        // 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 add_unshifted_tail(size_t batcher_index, Polynomial&& tail)
        {
            unshifted_tails_.emplace_back(batcher_index, std::move(tail));
        }
        void add_shifted_tail(size_t batcher_index, Polynomial&& tail)
        {
            shifted_tails_.emplace_back(batcher_index, std::move(tail));
        }
 
        Polynomial compute_batched(const Fr& challenge)
        {
            BB_BENCH_NAME("compute_batched");
            Fr running_scalar(1);
 
            // Batch base polynomials via a single fused parallel_for over the destination range,
            // amortising N× parallel_for startup overhead into 1×. Updates running_scalar in place.
            auto batch = [&](Polynomial& batched, const RefVector<Polynomial>& polynomials_to_batch) {
                const size_t n = polynomials_to_batch.size();
                std::vector<PolynomialSpan<const Fr>> sources;
                std::vector<Fr> scalars;
                sources.reserve(n);
                scalars.reserve(n);
                for (size_t i = 0; i < n; ++i) {
                    sources.emplace_back(polynomials_to_batch[i]);
                    scalars.push_back(running_scalar);
                    running_scalar *= challenge;
                }
                add_scaled_batch(
                    batched, std::span<const PolynomialSpan<const Fr>>(sources), std::span<const Fr>(scalars));
            };
 
            // Batch tails into a small accumulator with the correct rho power per tail.
            // Tails are small (e.g. 3 elements), kept separate to avoid extending the main batched
            // poly to full_batched_size. Each tail's scalar is base_scalar * rho^idx.
            auto batch_tails = [&](Polynomial& batched_tail,
                                   const std::vector<std::pair<size_t, Polynomial>>& tail_list,
                                   const Fr& base_scalar) {
                for (const auto& [idx, tail] : tail_list) {
                    if (batched_tail.is_empty()) {
                        batched_tail = Polynomial(tail.size(), tail.virtual_size(), tail.start_index());
                    }
                    batched_tail.add_scaled(tail, base_scalar * challenge.pow(idx));
                }
            };
 
            Polynomial full_batched(full_batched_size);
 
            Fr unshifted_base(1);
            if (has_unshifted()) {
                batch(batched_unshifted, unshifted);
                full_batched += batched_unshifted;
            }
            batch_tails(batched_unshifted_tail_, unshifted_tails_, unshifted_base);
            if (!batched_unshifted_tail_.is_empty()) {
                full_batched += batched_unshifted_tail_;
            }
 
            Fr shifted_base = running_scalar;
            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();
            }
            batch_tails(batched_shifted_tail_, shifted_tails_, shifted_base);
            if (!batched_shifted_tail_.is_empty()) {
                full_batched += batched_shifted_tail_.shifted();
            }
 
            return full_batched;
        }
 
        std::pair<Polynomial, Polynomial> compute_partially_evaluated_batch_polynomials(const Fr& r_challenge)
        {
            Polynomial A_0_pos(actual_data_size_, full_batched_size);
 
            if (has_unshifted()) {
                A_0_pos += batched_unshifted;
            }
            if (!batched_unshifted_tail_.is_empty()) {
                Polynomial A_0_extended(A_0_pos, full_batched_size - A_0_pos.start_index());
                A_0_extended += batched_unshifted_tail_;
                A_0_pos = std::move(A_0_extended);
            }
 
            Polynomial A_0_neg = A_0_pos;
 
            Fr r_inv = r_challenge.invert();
            if (has_to_be_shifted_by_one()) {
                A_0_pos.add_scaled(batched_to_be_shifted_by_one, r_inv);
                A_0_neg.add_scaled(batched_to_be_shifted_by_one, -r_inv);
            }
            if (!batched_shifted_tail_.is_empty()) {
                A_0_pos.add_scaled(batched_shifted_tail_, r_inv);
                A_0_neg.add_scaled(batched_shifted_tail_, -r_inv);
            }
 
            return { A_0_pos, A_0_neg };
        };
    };
 
    static std::vector<Polynomial> compute_fold_polynomials(const size_t log_n,
                                                            std::span<const Fr> multilinear_challenge,
                                                            const Polynomial& A_0);
 
    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(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
    {
        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);
 
        // 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();
 
            eval_pos_prev = eval_pos;
            fold_pos_evaluations.emplace_back(eval_pos_prev);
        }
 
        std::reverse(fold_pos_evaluations.begin(), fold_pos_evaluations.end());
 
        return fold_pos_evaluations;
    }
};
 
} // namespace bb