claim_batcher.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/ref_vector.hpp"
#include "barretenberg/common/zip_view.hpp"
#include <optional>
 
namespace bb {
 
template <typename Curve> struct ClaimBatcher_ {
    using Fr = typename Curve::ScalarField;
    using Commitment = typename Curve::AffineElement;
 
    struct Batch {
        RefVector<Commitment> commitments;
        RefVector<Fr> evaluations;
        // scalar used for batching the claims, excluding the power of batching challenge \rho
        Fr scalar = 0;
    };
 
    std::optional<Batch> unshifted; // commitments and evaluations of unshifted polynomials
    std::optional<Batch> shifted;   // commitments of to-be-shifted-by-1 polys, evals of their shifts
 
    Batch get_unshifted() { return (unshifted) ? *unshifted : Batch{}; }
    Batch get_shifted() { return (shifted) ? *shifted : Batch{}; }
 
    Fr get_unshifted_batch_scalar() const { return unshifted ? unshifted->scalar : Fr{ 0 }; }
 
    void compute_scalars_for_each_batch(std::span<const Fr> inverted_vanishing_evals,
                                        const Fr& nu_challenge,
                                        const Fr& r_challenge)
    {
        const Fr& inverse_vanishing_eval_pos = inverted_vanishing_evals[0];
        const Fr& inverse_vanishing_eval_neg = inverted_vanishing_evals[1];
 
        if (unshifted) {
            // (1/(z−r) + ν/(z+r))
            unshifted->scalar = inverse_vanishing_eval_pos + nu_challenge * inverse_vanishing_eval_neg;
        }
        if (shifted) {
            // r⁻¹ ⋅ (1/(z−r) − ν/(z+r))
            //
            // This scalar is the verifier-side to-be-shifted-by-one PCS contract: every commitment in
            // `shifted.commitments` is required to be a commitment to a polynomial with constant term zero.
            // A commitment to a polynomial with poly[0] != 0 opens to G(r)/r = poly[0]/r + G_shift(r) on
            // the commitment side, whereas the claimed MLE evaluation poly_shift(u) reconstructs to
            // G_shift(r) at the Gemini challenge. The two sides differ by poly[0]/r, the Shplonk quotient
            // is then not a polynomial, and the KZG pairing check rejects with overwhelming probability
            // over the FS challenges.
            // Regression: commitment_schemes/shplonk/shplemini.test.cpp::ToBeShiftedNonZeroConstantTermRejected.
            shifted->scalar =
                r_challenge.invert() * (inverse_vanishing_eval_pos - nu_challenge * inverse_vanishing_eval_neg);
        }
    }
    void update_batch_mul_inputs_and_batched_evaluation(std::vector<Commitment>& commitments,
                                                        std::vector<Fr>& scalars,
                                                        Fr& batched_evaluation,
                                                        const Fr& rho)
    {
        size_t num_powers = 0;
        num_powers += unshifted.has_value() ? unshifted->commitments.size() : 0;
        num_powers += shifted.has_value() ? shifted->commitments.size() : 0;
 
        Fr rho_power = Fr(1);
        size_t power_idx = 0;
 
        // Append the commitments/scalars from a given batch to the corresponding containers; update the batched
        // evaluation and the running batching challenge in place
        auto aggregate_claim_data_and_update_batched_evaluation = [&](const Batch& batch) {
            for (auto [commitment, evaluation] : zip_view(batch.commitments, batch.evaluations)) {
                commitments.emplace_back(std::move(commitment));
                scalars.emplace_back(-batch.scalar * rho_power);
                batched_evaluation += evaluation * rho_power;
                power_idx++;
                if (power_idx < num_powers) {
                    rho_power *= rho;
                }
            }
        };
 
        // Incorporate the claim data from each batch of claims that is present in the vectors of commitments and
        // scalars for the batch mul
        if (unshifted) {
            // i-th Unshifted commitment will be multiplied by ρ^i and (1/(z−r) + ν/(z+r))
            aggregate_claim_data_and_update_batched_evaluation(*unshifted);
        }
        if (shifted) {
            // i-th shifted commitments will be multiplied by ρ^{num_unshifted + i} and r⁻¹ ⋅ (1/(z−r) − ν/(z+r))
            aggregate_claim_data_and_update_batched_evaluation(*shifted);
        }
 
        BB_ASSERT_EQ(power_idx, num_powers);
    }
};
 
} // namespace bb