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 = { 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)
        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
 
      public:
        RefVector<Polynomial> unshifted;            // set of unshifted polynomials
        RefVector<Polynomial> to_be_shifted_by_one; // set of polynomials to be left shifted by 1
 
        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; }
 
        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
            }
 
            return full_batched;
        }
 
        std::pair<Polynomial, Polynomial> compute_partially_evaluated_batch_polynomials(const Fr& r_challenge)
        {
            // Initialize A₀₊ with only the actual data extent; virtual zeroes cover the rest
            Polynomial A_0_pos(actual_data_size_, 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 };
        };
    };
 
    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::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
    {
        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();
 
            // 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