claim_batcher.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: not started, auditors: [], date: YYYY-MM-DD }
// external_1:  { status: not started, auditors: [], date: YYYY-MM-DD }
// external_2:  { status: not started, auditors: [], date: YYYY-MM-DD }
// =====================
 
#pragma once
#include "barretenberg/common/ref_vector.hpp"
#include "barretenberg/common/throw_or_abort.hpp"
#include "barretenberg/common/zip_view.hpp"
#include "barretenberg/numeric/bitop/get_msb.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;
    };
    struct InterleavedBatch {
        std::vector<RefVector<Commitment>> commitments_groups;
        RefVector<Fr> evaluations;
        std::vector<Fr> scalars_pos;
        std::vector<Fr> scalars_neg;
        Fr shplonk_denominator;
    };
 
    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
    std::optional<Batch> right_shifted_by_k;     // commitments of to-be-right-shifted-by-k polys, evals of their shifts
    std::optional<InterleavedBatch> interleaved; // commitments to groups of polynomials to be combined by interleaving
                                                 // and evaluations of the resulting interleaved polynomials
 
    Batch get_unshifted() { return (unshifted) ? *unshifted : Batch{}; }
    Batch get_shifted() { return (shifted) ? *shifted : Batch{}; }
    Batch get_right_shifted_by_k() { return (right_shifted_by_k) ? *right_shifted_by_k : Batch{}; }
    InterleavedBatch get_interleaved() { return (interleaved) ? *interleaved : InterleavedBatch{}; }
    uint32_t get_groups_to_be_interleaved_size()
    {
        return (interleaved) ? static_cast<uint32_t>(interleaved->commitments_groups[0].size()) : 0;
    }
 
    uint32_t k_shift_magnitude = 0; // magnitude of right-shift-by-k (assumed even)
 
    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))
            shifted->scalar =
                r_challenge.invert() * (inverse_vanishing_eval_pos - nu_challenge * inverse_vanishing_eval_neg);
        }
        if (right_shifted_by_k) {
            // r^k ⋅ (1/(z−r) + ν/(z+r))
            right_shifted_by_k->scalar = r_challenge.pow(k_shift_magnitude) *
                                         (inverse_vanishing_eval_pos + nu_challenge * inverse_vanishing_eval_neg);
        }
 
        if (interleaved) {
            const size_t interleaving_denominator_index = 2 * numeric::get_msb(get_groups_to_be_interleaved_size());
 
            if (get_groups_to_be_interleaved_size() % 2 != 0) {
                throw_or_abort("Interleaved groups size must be even");
            }
 
            Fr r_shift_pos = Fr(1);
            Fr r_shift_neg = Fr(1);
            interleaved->shplonk_denominator = inverted_vanishing_evals[interleaving_denominator_index];
            for (size_t i = 0; i < get_groups_to_be_interleaved_size(); i++) {
                interleaved->scalars_pos.push_back(r_shift_pos);
                interleaved->scalars_neg.push_back(r_shift_neg);
                if (i < get_groups_to_be_interleaved_size() - 1) {
                    // to avoid unnecessary multiplication gates in a circuit
                    r_shift_pos *= r_challenge;
                    r_shift_neg *= (-r_challenge);
                }
            }
        }
    }
    void update_batch_mul_inputs_and_batched_evaluation(std::vector<Commitment>& commitments,
                                                        std::vector<Fr>& scalars,
                                                        Fr& batched_evaluation,
                                                        const Fr& rho,
                                                        Fr& rho_power,
                                                        Fr shplonk_batching_pos = { 0 },
                                                        Fr shplonk_batching_neg = { 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, Fr& rho_power) {
            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;
                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, rho_power);
        }
        if (shifted) {
            // i-th shifted commitments will be multiplied by p^{k+i} and r⁻¹ ⋅ (1/(z−r) − ν/(z+r))
            aggregate_claim_data_and_update_batched_evaluation(*shifted, rho_power);
        }
        if (right_shifted_by_k) {
            // i-th right-shifted-by-k commitments will be multiplied by ρ^{k+m+i} and r^k ⋅ (1/(z−r) + ν/(z+r))
            aggregate_claim_data_and_update_batched_evaluation(*right_shifted_by_k, rho_power);
        }
        if (interleaved) {
            if (get_groups_to_be_interleaved_size() % 2 != 0) {
                throw_or_abort("Interleaved groups size must be even");
            }
 
            size_t group_idx = 0;
            for (size_t j = 0; j < interleaved->commitments_groups.size(); j++) {
                for (size_t i = 0; i < get_groups_to_be_interleaved_size(); i++) {
                    // The j-th commitment in group i is multiplied by ρ^{k+m+i} and ν^{n+1} \cdot r^j + ν^{n+2} ⋅(-r)^j
                    //  where k is the number of unshifted, m is number of shifted and n is the log_circuit_size
                    //  (assuming to right-shifted-by-k commitments in this example)
                    commitments.emplace_back(std::move(interleaved->commitments_groups[j][i]));
                    scalars.emplace_back(-rho_power * interleaved->shplonk_denominator *
                                         (shplonk_batching_pos * interleaved->scalars_pos[i] +
                                          shplonk_batching_neg * interleaved->scalars_neg[i]));
                }
                batched_evaluation += interleaved->evaluations[group_idx] * rho_power;
                if (j != interleaved->commitments_groups.size() - 1) {
                    rho_power *= rho;
                }
                group_idx++;
            }
        }
    }
};
 
} // namespace bb