ipa.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Raju], commit: 05a381f8b31ae4648e480f1369e911b148216e8b}
// 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/verification_key.hpp"
#include "barretenberg/common/assert.hpp"
#include "barretenberg/common/container.hpp"
#include "barretenberg/common/thread.hpp"
#include "barretenberg/common/throw_or_abort.hpp"
#include "barretenberg/constants.hpp"
#include "barretenberg/ecc/scalar_multiplication/scalar_multiplication.hpp"
#include "barretenberg/stdlib/hash/poseidon2/poseidon2.hpp"
#include "barretenberg/stdlib/honk_verifier/ipa_accumulator.hpp"
#include "barretenberg/stdlib/primitives/circuit_builders/circuit_builders_fwd.hpp"
#include "barretenberg/transcript/transcript.hpp"
#include <cstddef>
#include <numeric>
#include <string>
#include <utility>
#include <vector>
 
namespace bb {
template <typename Curve_, size_t log_poly_length = CONST_ECCVM_LOG_N> class IPA {
  public:
    using Curve = Curve_;
    using Fr = typename Curve::ScalarField;
    using GroupElement = typename Curve::Element;
    using Commitment = typename Curve::AffineElement;
    using CK = CommitmentKey<Curve>;
    using VK = VerifierCommitmentKey<Curve>;
 
    // records the `u_challenges_inv`, the Pederson commitment to the `h` -polynomial, a.k.a. the challenge
    // polynomial, given as ∏_{i ∈ [k]} (1 + u_{len-i}^{-1}.X^{2^{i-1}}), and the running truth value of the IPA
    // accumulation claim.
    using VerifierAccumulator = stdlib::recursion::honk::IpaAccumulator<Curve>;
 
    // Compute the length of the vector of coefficients of a polynomial being opened.
    static constexpr size_t poly_length = 1UL << log_poly_length;
 
// These allow access to internal functions so that we can never use a mock transcript unless it's fuzzing or testing of
// IPA specifically
#ifdef IPA_TEST
    FRIEND_TEST(IPATest, ChallengesAreZero);
    FRIEND_TEST(IPATest, AIsZeroAfterOneRound);
#endif
#ifdef IPA_FUZZ_TEST
    friend class ProxyCaller;
#endif
 
    template <typename Transcript>
    static void compute_opening_proof_internal(const CK& ck,
                                               const ProverOpeningClaim<Curve>& opening_claim,
                                               const std::shared_ptr<Transcript>& transcript)
    {
        const bb::Polynomial<Fr>& polynomial = opening_claim.polynomial;
 
        // Step 1.
        // Done in `add_claim_to_hash_buffer`.
 
        // Step 2.
        // Receive challenge for the auxiliary generator
        const Fr generator_challenge = transcript->template get_challenge<Fr>("IPA:generator_challenge");
 
        if (generator_challenge.is_zero()) {
            throw_or_abort("The generator challenge can't be zero");
        }
 
        // Step 3.
        // Compute auxiliary generator U, which is used to bind together the inner product claim and the commitment.
        // This yields the binding property because we assume it is computationally difficult to find a linear relation
        // between the CRS and `Commitment::one()`.
        // Compute auxiliary generator U, which is used to bind together the inner product claim and the commitment.
        // This yields the binding property because we assume it is computationally difficult to find a linear relation
        // between the CRS and `Commitment::one()`.
        auto aux_generator = Commitment::one() * generator_challenge;
 
        // Checks poly_degree is greater than zero and a power of two
        // In the future, we might want to consider if non-powers of two are needed
        BB_ASSERT((poly_length > 0) && (!(poly_length & (poly_length - 1))) &&
                  "The polynomial degree plus 1 should be positive and a power of two");
 
        // Step 4.
        // Set initial vector a to the polynomial monomial coefficients and load vector G
        // Ensure the polynomial copy is fully-formed
        auto a_vec = polynomial.full();
        std::span<Commitment> srs_elements = ck.get_monomial_points();
        std::vector<Commitment> G_vec_local(poly_length);
 
        if (poly_length > srs_elements.size()) {
            throw_or_abort("potential bug: Not enough SRS points for IPA!");
        }
 
        // Copy the SRS into a local data structure as we need to mutate this vector for every round
        parallel_for_heuristic(
            poly_length, [&](size_t i) { G_vec_local[i] = srs_elements[i]; }, thread_heuristics::FF_COPY_COST);
 
        // Step 5.
        // Compute vector b (vector of the powers of the challenge)
        OpeningPair<Curve> opening_pair = opening_claim.opening_pair;
        std::vector<Fr> b_vec(poly_length);
        parallel_for_heuristic(
            poly_length,
            [&](size_t start, size_t end, BB_UNUSED size_t chunk_index) {
                Fr b_power = opening_pair.challenge.pow(start);
                for (size_t i = start; i < end; i++) {
                    b_vec[i] = b_power;
                    b_power *= opening_pair.challenge;
                }
            },
            thread_heuristics::FF_COPY_COST + thread_heuristics::FF_MULTIPLICATION_COST);
 
        // Iterate for log(poly_degree) rounds to compute the round commitments.
 
        // Allocate space for L_i and R_i elements
        GroupElement L_i;
        GroupElement R_i;
        std::size_t round_size = poly_length;
 
        // Step 6.
        // Perform IPA reduction rounds
        for (size_t i = 0; i < log_poly_length; i++) {
            round_size /= 2;
            // Run scalar products in parallel
            auto inner_prods = parallel_for_heuristic(
                round_size,
                std::pair{ Fr::zero(), Fr::zero() },
                [&](size_t j, std::pair<Fr, Fr>& inner_prod_left_right) {
                    // Compute inner_prod_L := < a_vec_lo, b_vec_hi >
                    inner_prod_left_right.first += a_vec[j] * b_vec[round_size + j];
                    // Compute inner_prod_R := < a_vec_hi, b_vec_lo >
                    inner_prod_left_right.second += a_vec[round_size + j] * b_vec[j];
                },
                thread_heuristics::FF_ADDITION_COST * 2 + thread_heuristics::FF_MULTIPLICATION_COST * 2);
            // Sum inner product contributions computed in parallel and unpack the std::pair
            auto [inner_prod_L, inner_prod_R] = sum_pairs(inner_prods);
            // Step 6.a (using letters, because doxygen automatically converts the sublist counters to letters :( )
            // L_i = < a_vec_lo, G_vec_hi > + inner_prod_L * aux_generator
 
            L_i = scalar_multiplication::pippenger_unsafe<Curve>({ 0, { &a_vec.at(0), /*size*/ round_size } },
                                                                 { &G_vec_local[round_size], round_size });
 
            L_i += aux_generator * inner_prod_L;
 
            // Step 6.b
            // R_i = < a_vec_hi, G_vec_lo > + inner_prod_R * aux_generator
            R_i = scalar_multiplication::pippenger_unsafe<Curve>({ 0, { &a_vec.at(round_size), /*size*/ round_size } },
                                                                 { &G_vec_local[0], /*size*/ round_size });
            R_i += aux_generator * inner_prod_R;
 
            // Step 6.c
            // Send L_i and R_i to the verifier
            std::string index = std::to_string(log_poly_length - i - 1);
            transcript->send_to_verifier("IPA:L_" + index, Commitment(L_i));
            transcript->send_to_verifier("IPA:R_" + index, Commitment(R_i));
 
            // Step 6.d
            // Receive the challenge from the verifier
            const Fr round_challenge = transcript->template get_challenge<Fr>("IPA:round_challenge_" + index);
 
            if (round_challenge.is_zero()) {
                throw_or_abort("IPA round challenge is zero");
            }
            const Fr round_challenge_inv = round_challenge.invert();
 
            // Step 6.e
            // G_vec_new = G_vec_lo + G_vec_hi * round_challenge_inv
            auto G_hi_by_inverse_challenge = GroupElement::batch_mul_with_endomorphism(
                std::span{ G_vec_local.begin() + static_cast<std::ptrdiff_t>(round_size),
                           G_vec_local.begin() + static_cast<std::ptrdiff_t>(round_size * 2) },
                round_challenge_inv);
            GroupElement::batch_affine_add(
                std::span{ G_vec_local.begin(), G_vec_local.begin() + static_cast<std::ptrdiff_t>(round_size) },
                G_hi_by_inverse_challenge,
                G_vec_local);
 
            // Steps 6.e and 6.f
            // Update the vectors a_vec, b_vec.
            // a_vec_new = a_vec_lo + a_vec_hi * round_challenge
            // b_vec_new = b_vec_lo + b_vec_hi * round_challenge_inv
            parallel_for_heuristic(
                round_size,
                [&](size_t j) {
                    a_vec.at(j) += round_challenge * a_vec[round_size + j];
                    b_vec[j] += round_challenge_inv * b_vec[round_size + j];
                },
                thread_heuristics::FF_ADDITION_COST * 2 + thread_heuristics::FF_MULTIPLICATION_COST * 2);
        }
 
        // Step 7
        // Send G_0 to the verifier
        transcript->send_to_verifier("IPA:G_0", G_vec_local[0]);
 
        // Step 8
        // Send a_0 to the verifier
        transcript->send_to_verifier("IPA:a_0", a_vec[0]);
    }
    template <typename Transcript>
    static void add_claim_to_hash_buffer(const CK& ck,
                                         const ProverOpeningClaim<Curve>& opening_claim,
                                         const std::shared_ptr<Transcript>& transcript)
    {
        const bb::Polynomial<Fr>& polynomial = opening_claim.polynomial;
 
        // Step 1.
        // Add the commitment, challenge, and evaluation to the hash buffer.
        // NOTE:
        //      a. This is a bit inefficient, as the prover otherwise doesn't need this commitment.
        //      However, the effect to performance of this MSM (in practice of size 2^16) is tiny.
        //      b. Note that we add these three pieces of information to the hash buffer, as opposed to
        //      calling the `send_to_verifier` method, as the verifier knows them.
 
        const auto commitment = ck.commit(polynomial);
        transcript->add_to_hash_buffer("IPA:commitment", commitment);
        transcript->add_to_hash_buffer("IPA:challenge", opening_claim.opening_pair.challenge);
        transcript->add_to_hash_buffer("IPA:evaluation", opening_claim.opening_pair.evaluation);
    }
 
    static bool reduce_verify_internal_native(const VK& vk, const OpeningClaim<Curve>& opening_claim, auto& transcript)
        requires(!Curve::is_stdlib_type)
    {
        // Step 1
        // Done by `add_claim_to_hash_buffer`.
 
        // Step 2.
        // Receive generator challenge u and compute auxiliary generator
        const Fr generator_challenge = transcript->template get_challenge<Fr>("IPA:generator_challenge");
 
        if (generator_challenge.is_zero()) {
            throw_or_abort("The generator challenge can't be zero");
        }
 
        const Commitment aux_generator = Commitment::one() * generator_challenge;
 
        // Step 3.
        // Compute C' = C + f(\beta) ⋅ U, i.e., the _joint_ commitment of f and f(\beta).
        const GroupElement C_prime = opening_claim.commitment + (aux_generator * opening_claim.opening_pair.evaluation);
 
        const auto pippenger_size = 2 * log_poly_length;
        std::vector<Fr> round_challenges(log_poly_length);
        // the group elements that will participate in our MSM.
        std::vector<Commitment> msm_elements(pippenger_size); // L_{k-1}, R_{k-1}, L_{k-2}, ..., L_0, R_0.
        // the scalars that will participate in our MSM.
        std::vector<Fr> msm_scalars(pippenger_size); // w_{k-1}^{-1}, w_{k-1}, ..., w_{0}^{-1}, w_{0}.
 
        // Step 4.
        // Receive all L_i and R_i and populate msm_elements.
        for (size_t i = 0; i < log_poly_length; i++) {
            std::string index = std::to_string(log_poly_length - i - 1);
            const auto element_L = transcript->template receive_from_prover<Commitment>("IPA:L_" + index);
            const auto element_R = transcript->template receive_from_prover<Commitment>("IPA:R_" + index);
            round_challenges[i] = transcript->template get_challenge<Fr>("IPA:round_challenge_" + index);
            if (round_challenges[i].is_zero()) {
                throw_or_abort("Round challenges can't be zero");
            }
            msm_elements[2 * i] = element_L;
            msm_elements[2 * i + 1] = element_R;
        }
 
        std::vector<Fr> round_challenges_inv = round_challenges;
        Fr::batch_invert(round_challenges_inv);
 
        // populate msm_scalars.
        for (size_t i = 0; i < log_poly_length; i++) {
            msm_scalars[2 * i] = round_challenges_inv[i];
            msm_scalars[2 * i + 1] = round_challenges[i];
        }
 
        // Step 5.
        // Compute C_zero = C' + ∑_{j ∈ [k]} u_j^{-1}L_j + ∑_{j ∈ [k]} u_jR_j
        GroupElement LR_sums = scalar_multiplication::pippenger_unsafe<Curve>(
            { 0, { &msm_scalars[0], /*size*/ pippenger_size } }, { &msm_elements[0], /*size*/ pippenger_size });
        GroupElement C_zero = C_prime + LR_sums;
 
        //  Step 6.
        // Compute b_zero succinctly
        const Fr b_zero = evaluate_challenge_poly(round_challenges_inv, opening_claim.opening_pair.challenge);
 
        // Step 7.
        // Construct vector s
        Polynomial<Fr> s_vec(
            construct_poly_from_u_challenges_inv(std::span(round_challenges_inv).subspan(0, log_poly_length)));
 
        std::span<const Commitment> srs_elements = vk.get_monomial_points();
        if (poly_length > srs_elements.size()) {
            throw_or_abort("potential bug: Not enough SRS points for IPA!");
        }
 
        // Step 8.
        // Compute G_zero
        Commitment G_zero =
            scalar_multiplication::pippenger_unsafe<Curve>(s_vec, { &srs_elements[0], /*size*/ poly_length });
        Commitment G_zero_sent = transcript->template receive_from_prover<Commitment>("IPA:G_0");
        BB_ASSERT_EQ(G_zero, G_zero_sent, "G_0 should be equal to G_0 sent in transcript. IPA verification fails.");
 
        // Step 9.
        // Receive a_zero from the prover
        auto a_zero = transcript->template receive_from_prover<Fr>("IPA:a_0");
 
        // Step 10.
        // Compute C_right. Implicitly, this is an IPA statement for the length 1 vectors <a_0> and <b_0> together with
        // the URS G_0.
        GroupElement right_hand_side = G_zero * a_zero + aux_generator * a_zero * b_zero;
        // Step 11.
        // Check if C_right == C_zero
        return (C_zero.normalize() == right_hand_side.normalize());
    }
 
    template <typename Transcript>
    static void add_claim_to_hash_buffer(const OpeningClaim<Curve>& opening_claim,
                                         const std::shared_ptr<Transcript>& transcript)
    {
 
        // Step 1.
        // Add the commitment, challenge, and evaluation to the hash buffer.
 
        transcript->add_to_hash_buffer("IPA:commitment", opening_claim.commitment);
        transcript->add_to_hash_buffer("IPA:challenge", opening_claim.opening_pair.challenge);
        transcript->add_to_hash_buffer("IPA:evaluation", opening_claim.opening_pair.evaluation);
    }
    static VerifierAccumulator reduce_verify_internal_recursive(const OpeningClaim<Curve>& opening_claim,
                                                                auto& transcript)
        requires Curve::is_stdlib_type
    {
        // Step 1.
        // Done by `add_claim_to_hash_buffer`.
 
        // Step 2.
        // Receive generator challenge u and compute auxiliary generator
        const Fr generator_challenge = transcript->template get_challenge<Fr>("IPA:generator_challenge");
        typename Curve::Builder* builder = generator_challenge.get_context();
 
        auto pippenger_size =
            2 * log_poly_length +
            2; // the only check we perform will involve an MSM. we make the MSM "as big as possible" for efficiency,
               // which is why `pippenger_size` is bigger here than in the native verifier.
        std::vector<Fr> round_challenges(log_poly_length);
        std::vector<Fr> round_challenges_inv(log_poly_length);
        std::vector<Commitment> msm_elements(
            pippenger_size); // L_{k-1}, R_{k-1}, L_{k-2}, ..., L_0, R_0, -G_0, -Commitment::one()
        std::vector<Fr> msm_scalars(pippenger_size); // w_{k-1}^{-1}, w_{k-1}, ..., w_{0}^{-1}, w_{0}, a_0, (a_0 * b_0 -
                                                     // f(\beta)) * generator_challenge
 
        // Step 3.
        // Receive all L_i and R_i and prepare for MSM
        for (size_t i = 0; i < log_poly_length; i++) {
 
            std::string index = std::to_string(log_poly_length - i - 1);
            auto element_L = transcript->template receive_from_prover<Commitment>("IPA:L_" + index);
            auto element_R = transcript->template receive_from_prover<Commitment>("IPA:R_" + index);
            round_challenges[i] = transcript->template get_challenge<Fr>("IPA:round_challenge_" + index);
            round_challenges_inv[i] = round_challenges[i].invert();
 
            msm_elements[2 * i] = element_L;
            msm_elements[2 * i + 1] = element_R;
            msm_scalars[2 * i] = round_challenges_inv[i];
            msm_scalars[2 * i + 1] = round_challenges[i];
        }
 
        // Step 4.
        // Compute b_zero succinctly
        Fr b_zero = evaluate_challenge_poly(round_challenges_inv, opening_claim.opening_pair.challenge);
 
        // Step 5.
        // Receive G_zero from the prover
        Commitment G_zero = transcript->template receive_from_prover<Commitment>("IPA:G_0");
 
        // Step 6.
        // Receive a_zero from the prover
        const auto a_zero = transcript->template receive_from_prover<Fr>("IPA:a_0");
 
        // OriginTag false positive: G_zero and a_zero are fully determined once all round challenges are fixed - the
        // prover must send the correct values or the final relation check fails.
        if constexpr (Curve::is_stdlib_type) {
            const auto last_round_tag = round_challenges.back().get_origin_tag();
            G_zero.set_origin_tag(last_round_tag);
            const_cast<Fr&>(a_zero).set_origin_tag(last_round_tag);
        }
 
        // Step 7.
        // Compute R = C' + ∑_{j ∈ [k]} u_j^{-1}L_j + ∑_{j ∈ [k]} u_jR_j - G₀ * a₀ - (f(\beta) - a₀ * b₀) ⋅ U
        // If everything is correct, then R == -C, as C':= C + f(\beta) ⋅ U
        msm_elements.emplace_back(-G_zero);
        msm_elements.emplace_back(-Commitment::one(builder));
        msm_scalars.emplace_back(a_zero);
        msm_scalars.emplace_back(generator_challenge * a_zero.madd(b_zero, { -opening_claim.opening_pair.evaluation }));
        GroupElement ipa_relation = GroupElement::batch_mul(msm_elements, msm_scalars);
        auto neg_commitment = -opening_claim.commitment;
 
        // the below is the only constraint.
        ipa_relation.assert_equal(neg_commitment);
 
        return { round_challenges_inv, G_zero, ipa_relation.get_value() == -opening_claim.commitment.get_value() };
    }
 
    template <typename Transcript = NativeTranscript>
    static void compute_opening_proof(const CK& ck,
                                      const ProverOpeningClaim<Curve>& opening_claim,
                                      const std::shared_ptr<Transcript>& transcript)
    {
        add_claim_to_hash_buffer(ck, opening_claim, transcript);
        compute_opening_proof_internal(ck, opening_claim, transcript);
    }
 
    template <typename Transcript = NativeTranscript>
    static bool reduce_verify(const VK& vk,
                              const OpeningClaim<Curve>& opening_claim,
                              const std::shared_ptr<Transcript>& transcript)
        requires(!Curve::is_stdlib_type)
    {
        add_claim_to_hash_buffer(opening_claim, transcript);
        return reduce_verify_internal_native(vk, opening_claim, transcript);
    }
 
    static VerifierAccumulator reduce_verify(const OpeningClaim<Curve>& opening_claim, const auto& transcript)
        requires(Curve::is_stdlib_type)
    {
        // The output of `reduce_verify_internal_recursive` consists of a `VerifierAccumulator` and a boolean, recording
        // the truth value of the last verifier-compatibility check. This simply forgets the boolean and returns the
        // `VerifierAccumulator`.
        add_claim_to_hash_buffer(opening_claim, transcript);
        return reduce_verify_internal_recursive(opening_claim, transcript);
    }
 
    static bool full_verify_recursive(const VK& vk, const OpeningClaim<Curve>& opening_claim, auto& transcript)
        requires Curve::is_stdlib_type
    {
        add_claim_to_hash_buffer(opening_claim, transcript);
        VerifierAccumulator verifier_accumulator = reduce_verify_internal_recursive(opening_claim, transcript);
        auto round_challenges_inv = verifier_accumulator.u_challenges_inv;
        auto claimed_G_zero = verifier_accumulator.comm;
 
        // Construct vector s, whose rth entry is ∏ (u_i)^{-1 * r_i}, where (r_i) is the binary expansion of r. This
        // is required to _compute_ G_zero (rather than just passively receive G_zero from the Prover).
        //
        // We implement a linear-time algorithm to optimally compute this vector
        // Note: currently requires an extra vector of size
        // `poly_length / 2` to cache temporaries
        //       this might able to be optimized if we care enough, but the size of this poly shouldn't be large
        //       relative to the builder polynomial sizes
        std::vector<Fr> s_vec_temporaries(poly_length / 2);
        std::vector<Fr> s_vec(poly_length);
 
        Fr* previous_round_s = &s_vec_temporaries[0];
        Fr* current_round_s = &s_vec[0];
        // if number of rounds is even we need to swap these so that s_vec always contains the result
        if constexpr ((log_poly_length & 1) == 0) {
            std::swap(previous_round_s, current_round_s);
        }
        previous_round_s[0] = Fr(1);
        for (size_t i = 0; i < log_poly_length; ++i) {
            const size_t round_size = 1 << (i + 1);
            const Fr round_challenge = round_challenges_inv[i];
            for (size_t j = 0; j < round_size / 2; ++j) {
                current_round_s[j * 2] = previous_round_s[j];
                current_round_s[j * 2 + 1] = previous_round_s[j] * round_challenge;
            }
            std::swap(current_round_s, previous_round_s);
        }
 
        // Compute G_zero
        // In the native verifier, this uses pippenger. Here we were batch_mul.
        const std::vector<Commitment> srs_elements = vk.get_monomial_points();
        Commitment computed_G_zero = Commitment::batch_mul(srs_elements, s_vec);
        // check the computed G_zero and the claimed G_zero are the same.
        claimed_G_zero.assert_equal(computed_G_zero);
        BB_ASSERT_EQ(computed_G_zero.get_value(), claimed_G_zero.get_value(), "G_zero doesn't match received G_zero.");
 
        bool running_truth_value = verifier_accumulator.running_truth_value;
        return running_truth_value;
    }
 
    static OpeningClaim<Curve> reduce_batch_opening_claim(const BatchOpeningClaim<Curve>& batch_opening_claim)
    {
        // Extract batch_mul arguments from the accumulator
        const auto& commitments = batch_opening_claim.commitments;
        const auto& scalars = batch_opening_claim.scalars;
        const Fr& shplonk_eval_challenge = batch_opening_claim.evaluation_point;
        // Compute \f$ C = \sum \text{commitments}_i \cdot \text{scalars}_i \f$
        GroupElement shplonk_output_commitment = GroupElement::batch_mul(commitments, scalars);
        // Output an opening claim, which in practice will be verified by the IPA opening protocol
        return { { shplonk_eval_challenge, Fr(0) }, shplonk_output_commitment };
    }
 
    static bool reduce_verify_batch_opening_claim(const BatchOpeningClaim<Curve>& batch_opening_claim,
                                                  const VK& vk,
                                                  auto& transcript)
        requires(!Curve::is_stdlib_type)
    {
        const auto opening_claim = reduce_batch_opening_claim(batch_opening_claim);
        add_claim_to_hash_buffer(opening_claim, transcript);
        return reduce_verify_internal_native(vk, opening_claim, transcript);
    }
 
    static VerifierAccumulator reduce_verify_batch_opening_claim(const BatchOpeningClaim<Curve>& batch_opening_claim,
                                                                 [[maybe_unused]] const std::shared_ptr<VK>& vk,
                                                                 auto& transcript)
        requires(Curve::is_stdlib_type)
    {
        const auto opening_claim = reduce_batch_opening_claim(batch_opening_claim);
        add_claim_to_hash_buffer(opening_claim, transcript);
        return reduce_verify_internal_recursive(opening_claim, transcript).verifier_accumulator;
    }
 
    static Fr evaluate_challenge_poly(const std::vector<Fr>& u_challenges_inv, Fr r)
    {
        // Runs the obvious algorithm to compute the product ∏_{i ∈ [k]} (1 + u_{len-i}^{-1}.r^{2^{i-1}}) by
        // remembering the current 2-primary power of r.
        Fr challenge_poly_eval = 1;
        Fr r_pow = r;
        // the loop runs to `log_poly_length - 1` because we don't want to superfluously compute r_pow.sqr() in the last
        // round.
        for (size_t i = 0; i < log_poly_length - 1; i++) {
            Fr monomial = u_challenges_inv[log_poly_length - 1 - i] * r_pow;
            challenge_poly_eval *= (Fr(1) + monomial);
            r_pow = r_pow.sqr();
        }
        // same as the body of the loop, without `r_pow = r_pow.sqr()`
        Fr monomial = u_challenges_inv[0] * r_pow;
        challenge_poly_eval *= (Fr(1) + monomial);
        return challenge_poly_eval;
    }
 
    static Fr evaluate_and_accumulate_challenge_polys(std::vector<Fr> u_challenges_inv_1,
                                                      std::vector<Fr> u_challenges_inv_2,
                                                      Fr r,
                                                      Fr alpha)
    {
        auto result =
            evaluate_challenge_poly(u_challenges_inv_1, r) + alpha * evaluate_challenge_poly(u_challenges_inv_2, r);
        return result;
    }
 
    static Polynomial<bb::fq> construct_poly_from_u_challenges_inv(const std::span<const bb::fq>& u_challenges_inv)
    {
 
        // Construct vector s in linear time.
        std::vector<bb::fq> s_vec(poly_length, bb::fq::one());
        std::vector<bb::fq> s_vec_temporaries(poly_length / 2);
 
        bb::fq* previous_round_s = &s_vec_temporaries[0];
        bb::fq* current_round_s = &s_vec[0];
        // if number of rounds is even we need to swap these so that s_vec always contains the result
        if ((log_poly_length & 1) == 0) {
            std::swap(previous_round_s, current_round_s);
        }
        previous_round_s[0] = bb::fq(1);
        for (size_t i = 0; i < log_poly_length; ++i) {
            const size_t round_size = 1 << (i + 1);
            const bb::fq round_challenge = u_challenges_inv[i];
            parallel_for_heuristic(
                round_size / 2,
                [&](size_t j) {
                    current_round_s[j * 2] = previous_round_s[j];
                    current_round_s[j * 2 + 1] = previous_round_s[j] * round_challenge;
                },
                thread_heuristics::FF_MULTIPLICATION_COST * 2);
            std::swap(current_round_s, previous_round_s);
        }
        return { s_vec, poly_length };
    }
 
    static Polynomial<bb::fq> create_challenge_poly(const std::vector<bb::fq>& u_challenges_inv_1,
                                                    const std::vector<bb::fq>& u_challenges_inv_2,
                                                    bb::fq alpha)
    {
        // Always extend each to 1<<log_poly_length length
        Polynomial<bb::fq> challenge_poly(1 << log_poly_length);
        Polynomial challenge_poly_1 = construct_poly_from_u_challenges_inv(u_challenges_inv_1);
        Polynomial challenge_poly_2 = construct_poly_from_u_challenges_inv(u_challenges_inv_2);
        challenge_poly += challenge_poly_1;
        challenge_poly.add_scaled(challenge_poly_2, alpha);
        return challenge_poly;
    }
 
    static std::pair<OpeningClaim<Curve>, HonkProof> accumulate(const CommitmentKey<curve::Grumpkin>& ck,
                                                                auto& transcript_1,
                                                                OpeningClaim<Curve> claim_1,
                                                                auto& transcript_2,
                                                                OpeningClaim<Curve> claim_2)
        requires Curve::is_stdlib_type
    {
        using NativeCurve = curve::Grumpkin;
        // Sanity check that we are not using Grumpkin with MegaCircuitBuilder designed to delegate BN254 ops.
        static_assert(IsAnyOf<typename Curve::Builder, UltraCircuitBuilder>);
        // Step 1: Run the partial verifier for each IPA instance
        VerifierAccumulator verifier_accumulator_1 = reduce_verify(claim_1, transcript_1);
        VerifierAccumulator verifier_accumulator_2 = reduce_verify(claim_2, transcript_2);
 
        // Step 2: Generate the challenges by hashing the pairs
        UltraStdlibTranscript transcript;
        transcript.add_to_hash_buffer("u_challenges_inv_1", verifier_accumulator_1.u_challenges_inv);
        transcript.add_to_hash_buffer("U_1", verifier_accumulator_1.comm);
        transcript.add_to_hash_buffer("u_challenges_inv_2", verifier_accumulator_2.u_challenges_inv);
        transcript.add_to_hash_buffer("U_2", verifier_accumulator_2.comm);
        auto [alpha, r] = transcript.template get_challenges<Fr>(std::array<std::string, 2>{ "IPA:alpha", "IPA:r" });
 
        // Step 3: Compute the new accumulator
        OpeningClaim<Curve> output_claim;
        output_claim.commitment = verifier_accumulator_1.comm + verifier_accumulator_2.comm * alpha;
        output_claim.opening_pair.challenge = r;
        // Evaluate the challenge_poly polys at r and linearly combine them with alpha challenge
        output_claim.opening_pair.evaluation = evaluate_and_accumulate_challenge_polys(
            verifier_accumulator_1.u_challenges_inv, verifier_accumulator_2.u_challenges_inv, r, alpha);
 
        // Step 4: Compute the new challenge polynomial natively
        std::vector<bb::fq> native_u_challenges_inv_1;
        std::vector<bb::fq> native_u_challenges_inv_2;
        for (Fr u_inv_i : verifier_accumulator_1.u_challenges_inv) {
            native_u_challenges_inv_1.push_back(bb::fq(u_inv_i.get_value()));
        }
        for (Fr u_inv_i : verifier_accumulator_2.u_challenges_inv) {
            native_u_challenges_inv_2.push_back(bb::fq(u_inv_i.get_value()));
        }
 
        Polynomial<bb::fq> challenge_poly =
            create_challenge_poly(native_u_challenges_inv_1, native_u_challenges_inv_2, bb::fq(alpha.get_value()));
 
        // Compute proof for the claim
        auto prover_transcript = std::make_shared<NativeTranscript>();
        const OpeningPair<NativeCurve> opening_pair{ bb::fq(output_claim.opening_pair.challenge.get_value()),
                                                     bb::fq(output_claim.opening_pair.evaluation.get_value()) };
 
        BB_ASSERT_EQ(challenge_poly.evaluate(opening_pair.challenge),
                     opening_pair.evaluation,
                     "Opening claim does not hold for challenge polynomial.");
 
        IPA<NativeCurve, log_poly_length>::compute_opening_proof(
            ck, { challenge_poly, opening_pair }, prover_transcript);
        BB_ASSERT_EQ(challenge_poly.evaluate(bb::fq(output_claim.opening_pair.challenge.get_value())),
                     bb::fq(output_claim.opening_pair.evaluation.get_value()),
                     "Opening claim does not hold for challenge polynomial.");
 
        output_claim.opening_pair.evaluation.self_reduce();
        return { output_claim, prover_transcript->export_proof() };
    }
 
    static std::pair<OpeningClaim<Curve>, HonkProof> create_random_valid_ipa_claim_and_proof(
        UltraCircuitBuilder& builder)
        requires Curve::is_stdlib_type
    {
        using NativeCurve = curve::Grumpkin;
        using Builder = typename Curve::Builder;
        using Curve = stdlib::grumpkin<Builder>;
        auto ipa_transcript = std::make_shared<NativeTranscript>();
        CommitmentKey<NativeCurve> ipa_commitment_key(poly_length);
        size_t n = poly_length;
        auto poly = Polynomial<bb::fq>(n);
        for (size_t i = 0; i < n; i++) {
            poly.at(i) = bb::fq::random_element();
        }
        bb::fq x = bb::fq::random_element();
        bb::fq eval = poly.evaluate(x);
        auto commitment = ipa_commitment_key.commit(poly);
        const OpeningPair<NativeCurve> opening_pair = { x, eval };
        IPA<NativeCurve>::compute_opening_proof(ipa_commitment_key, { poly, opening_pair }, ipa_transcript);
 
        auto stdlib_comm = Curve::Group::from_witness(&builder, commitment);
        auto stdlib_x = Curve::ScalarField::from_witness(&builder, x);
        auto stdlib_eval = Curve::ScalarField::from_witness(&builder, eval);
        OpeningClaim<Curve> stdlib_opening_claim{ { stdlib_x, stdlib_eval }, stdlib_comm };
 
        return { stdlib_opening_claim, ipa_transcript->export_proof() };
    }
};
 
} // namespace bb