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/commitment_schemes/claim.hpp"
#include "barretenberg/common/assert.hpp"
#include "barretenberg/common/ref_vector.hpp"
#include "barretenberg/common/zip_view.hpp"
#include <algorithm>
#include <cstddef>
#include <optional>
#include <span>
#include <utility>
#include <vector>
 
namespace bb {
 
template <typename Curve> struct ProverOpeningClaimBatcher {
    using Commitment = typename Curve::AffineElement;
    using ProverClaim = ProverOpeningClaim<Curve>;
    using VerifierClaim = OpeningClaim<Curve>;
 
    std::vector<ProverClaim> prover_claims;
    std::vector<VerifierClaim> verifier_claims;
 
    void add(ProverClaim prover_claim, Commitment commitment)
    {
        verifier_claims.push_back({ prover_claim.opening_pair, commitment });
        prover_claims.push_back(std::move(prover_claim));
    }
};
 
template <typename Fr> inline std::vector<Fr> batching_scalars(const Fr& challenge, const size_t count)
{
    std::vector<Fr> scalars;
    scalars.reserve(count);
    Fr scalar = Fr::one();
    for (size_t idx = 0; idx < count; ++idx) {
        scalars.emplace_back(scalar);
        scalar *= challenge;
    }
    return scalars;
}
 
template <typename Curve>
typename Curve::ScalarField batch_evaluations(std::span<const typename Curve::ScalarField> evaluations,
                                              std::span<const typename Curve::ScalarField> scalars)
{
    using Fr = typename Curve::ScalarField;
    BB_ASSERT_EQ(evaluations.size(), scalars.size());
    if (evaluations.empty()) {
        return Fr::zero();
    }
    if constexpr (Curve::is_stdlib_type) {
        constexpr size_t max_products = 16;
        Fr result;
        for (size_t start = 0; start < evaluations.size(); start += max_products) {
            const size_t len = std::min(max_products, evaluations.size() - start);
            std::vector<Fr> scalar_chunk(scalars.begin() + static_cast<std::ptrdiff_t>(start),
                                         scalars.begin() + static_cast<std::ptrdiff_t>(start + len));
            std::vector<Fr> evaluation_chunk(evaluations.begin() + static_cast<std::ptrdiff_t>(start),
                                             evaluations.begin() + static_cast<std::ptrdiff_t>(start + len));
            result = (start == 0) ? Fr::mult_madd(scalar_chunk, evaluation_chunk, {})
                                  : Fr::mult_madd(scalar_chunk, evaluation_chunk, { result });
        }
        return result;
    } else {
        Fr result = Fr::zero();
        for (size_t idx = 0; idx < evaluations.size(); ++idx) {
            result += scalars[idx] * evaluations[idx];
        }
        return result;
    }
}
 
template <typename Curve>
typename Curve::AffineElement batch_commitments(std::span<const typename Curve::AffineElement> commitments,
                                                std::span<const typename Curve::ScalarField> scalars)
{
    using Fr = typename Curve::ScalarField;
    using Commitment = typename Curve::AffineElement;
    using GroupElement = typename Curve::Element;
    BB_ASSERT_EQ(commitments.size(), scalars.size());
    BB_ASSERT_GT(commitments.size(), 0UL);
 
    std::vector<Fr> scalars_copy(scalars.begin(), scalars.end());
    if constexpr (Curve::is_stdlib_type) {
        return GroupElement::batch_mul(std::vector<Commitment>(commitments.begin(), commitments.end()), scalars_copy);
    } else {
        return Commitment::batch_mul(commitments, std::span<Fr>(scalars_copy));
    }
}
 
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