mock_witness_generator.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/commitment_schemes/commitment_key.hpp"
#include "barretenberg/commitment_schemes/gemini/gemini.hpp"
#include "barretenberg/commitment_schemes/shplonk/shplemini.hpp"
#include "barretenberg/commitment_schemes/utils/test_utils.hpp"
#include "barretenberg/ecc/curves/bn254/bn254.hpp"
#include "barretenberg/polynomials/polynomial.hpp"
#include "barretenberg/transcript/transcript.hpp"
 
namespace bb {
template <typename Curve> struct MockClaimGenerator {
  public:
    using CommitmentKey = bb::CommitmentKey<Curve>;
    using Fr = typename Curve::ScalarField;
    using Commitment = typename Curve::AffineElement;
    using Polynomial = bb::Polynomial<Fr>;
    using PolynomialBatcher = bb::GeminiProver_<Curve>::PolynomialBatcher;
    using ClaimBatcher = ClaimBatcher_<Curve>;
    using ClaimBatch = ClaimBatcher::Batch;
    using InterleavedBatch = ClaimBatcher::InterleavedBatch;
 
    CommitmentKey ck;
 
    struct ClaimData {
        std::vector<Polynomial> polys;
        std::vector<Commitment> commitments;
        std::vector<Fr> evals;
    };
 
    ClaimData unshifted;
    ClaimData to_be_shifted;
 
    std::vector<Fr> const_size_mle_opening_point;
 
    PolynomialBatcher polynomial_batcher;
    ClaimBatcher claim_batcher;
 
    // Containers for mock Sumcheck data
    std::vector<bb::Polynomial<Fr>> round_univariates;
    std::vector<Commitment> sumcheck_commitments;
    std::vector<std::array<Fr, 3>> sumcheck_evaluations;
 
    struct InterleaveData {
        std::vector<std::vector<Polynomial>> groups;
        std::vector<Polynomial> polys;
        std::vector<Fr> evaluations;
        std::vector<std::vector<Commitment>> group_commitments;
    };
    InterleaveData interleave_data;
 
    MockClaimGenerator(const size_t poly_size,
                       const size_t num_polynomials,
                       const size_t num_to_be_shifted,
                       const std::vector<Fr>& mle_opening_point,
                       const CommitmentKey& commitment_key,
                       size_t num_interleaved = 0,
                       size_t num_to_be_interleaved = 0)
 
        : ck(commitment_key) // Initialize the commitment key
        , polynomial_batcher(poly_size)
 
    {
        size_t log_size = numeric::get_msb(poly_size);
        // If the size of the opening point is bigger than the log of the poly size, we assume that the prover is
        // extending all of its polynomials by zero outside of the hypercube of size 2^{log_size}.
        bool has_virtual_rounds = (mle_opening_point.size() > log_size);
 
        std::span<const Fr> challenge;
 
        if (has_virtual_rounds) {
            // The evaluation on the full domain can be obtain by scaling by extension-by-zero factor `ebz_factor`
            // computed below.
            challenge = std::span<const Fr>(mle_opening_point).subspan(0, log_size);
        } else {
            challenge = std::span<const Fr>(mle_opening_point);
        }
 
        BB_ASSERT_GTE(num_polynomials, num_to_be_shifted);
        const size_t num_not_to_be_shifted = num_polynomials - num_to_be_shifted;
 
        Fr ebz_factor = 1;
 
        for (size_t idx = log_size; idx < mle_opening_point.size(); idx++) {
            ebz_factor *= (Fr(1) - mle_opening_point[idx]);
        }
 
        // Construct claim data for polynomials that are NOT to be shifted
        for (size_t idx = 0; idx < num_not_to_be_shifted; idx++) {
            Polynomial poly = Polynomial::random(poly_size);
            unshifted.commitments.push_back(ck.commit(poly));
            unshifted.evals.push_back(poly.evaluate_mle(challenge) * ebz_factor);
            unshifted.polys.push_back(std::move(poly));
        }
 
        // Construct claim data for polynomials that are to-be-shifted
        for (size_t idx = 0; idx < num_to_be_shifted; idx++) {
            Polynomial poly = Polynomial::random(poly_size, /*shiftable*/ 1);
            Commitment commitment = ck.commit(poly);
            to_be_shifted.commitments.push_back(commitment);
            to_be_shifted.evals.push_back(poly.shifted().evaluate_mle(challenge) * ebz_factor);
            to_be_shifted.polys.push_back(poly.share());
            // Populate the unshifted counterpart in the unshifted claims
            unshifted.commitments.push_back(commitment);
            unshifted.evals.push_back(poly.evaluate_mle(challenge) * ebz_factor);
            unshifted.polys.push_back(std::move(poly));
        }
 
        polynomial_batcher.set_unshifted(RefVector(unshifted.polys));
        polynomial_batcher.set_to_be_shifted_by_one(RefVector(to_be_shifted.polys));
 
        claim_batcher =
            ClaimBatcher{ .unshifted = ClaimBatch{ RefVector(unshifted.commitments), RefVector(unshifted.evals) },
                          .shifted =
                              ClaimBatch{ RefVector(to_be_shifted.commitments), RefVector(to_be_shifted.evals) } };
        if (num_interleaved > 0) {
            interleave_data =
                generate_interleaving_inputs(mle_opening_point, num_interleaved, num_to_be_interleaved, ck);
            polynomial_batcher.set_interleaved(RefVector(interleave_data.polys),
                                               to_vector_of_ref_vectors(interleave_data.groups));
 
            claim_batcher.interleaved =
                InterleavedBatch{ .commitments_groups = to_vector_of_ref_vectors(interleave_data.group_commitments),
                                  .evaluations = RefVector(interleave_data.evaluations) };
        }
    }
 
    // Generate zero polynomials to test edge cases in PCS
    MockClaimGenerator(const size_t n, const size_t num_zero_polynomials)
        : polynomial_batcher(n)
    {
        for (size_t idx = 0; idx < num_zero_polynomials; idx++) {
            unshifted.polys.emplace_back(n);
            unshifted.commitments.push_back(Commitment::infinity());
            unshifted.evals.push_back(Fr(0));
        }
 
        polynomial_batcher.set_unshifted(RefVector(unshifted.polys));
 
        claim_batcher =
            ClaimBatcher{ .unshifted = ClaimBatch{ RefVector(unshifted.commitments), RefVector(unshifted.evals) } };
    }
 
    // Generates mock claims by using the custom polynomials provided as input instead of random polynomials. Used for
    // the high degree attack tests.
    MockClaimGenerator(const size_t poly_size,
                       const std::vector<Polynomial> custom_unshifted,
                       const std::vector<Fr>& custom_unshifted_evals,
                       const CommitmentKey& commitment_key)
 
        : ck(commitment_key)
        , polynomial_batcher(poly_size)
    {
 
        //  ---------- Unshifted ----------
        for (size_t i = 0; i < custom_unshifted.size(); ++i) {
            auto& p = custom_unshifted[i];
            unshifted.commitments.push_back(ck.commit(p));
            unshifted.evals.push_back(custom_unshifted_evals[i]);
            unshifted.polys.push_back(std::move(p));
        }
 
        polynomial_batcher.set_unshifted(RefVector(unshifted.polys));
 
        claim_batcher =
            ClaimBatcher{ .unshifted = ClaimBatch{ RefVector(unshifted.commitments), RefVector(unshifted.evals) } };
    }
 
    InterleaveData generate_interleaving_inputs(const std::vector<Fr>& u_challenge,
                                                const size_t num_interleaved,
                                                const size_t group_size,
                                                const CommitmentKey& ck)
    {
 
        size_t N = 1 << u_challenge.size();
        size_t MINI_CIRCUIT_N = N / group_size; // size of chunks
 
        // Polynomials "chunks" that are interleaved in the PCS
        std::vector<std::vector<Polynomial>> groups;
 
        // Concatenated polynomials
        std::vector<Polynomial> interleaved_polynomials;
 
        // Evaluations of interleaved polynomials
        std::vector<Fr> c_evaluations;
 
        // For each polynomial to be interleaved
        for (size_t i = 0; i < num_interleaved; ++i) {
            std::vector<Polynomial> group;
            Polynomial interleaved_polynomial(N);
            for (size_t j = 0; j < group_size; j++) {
                Polynomial chunk_polynomial(N);
                // Fill the chunk polynomial with random values and appropriately fill the space in
                // interleaved_polynomial
                for (size_t k = 0; k < MINI_CIRCUIT_N; k++) {
                    // Chunks should be shiftable
                    auto tmp = Fr(0);
                    if (k > 0) {
                        tmp = Fr::random_element();
                    }
                    chunk_polynomial.at(k) = tmp;
                    interleaved_polynomial.at(k * group_size + j) = tmp;
                }
                group.emplace_back(chunk_polynomial);
            }
            // Store chunks
            groups.emplace_back(group);
            // Store interleaved polynomial
            interleaved_polynomials.emplace_back(interleaved_polynomial);
            // Get evaluation
            c_evaluations.emplace_back(interleaved_polynomial.evaluate_mle(u_challenge));
        }
 
        // Compute commitments of all polynomial chunks
        std::vector<std::vector<Commitment>> groups_commitments;
        for (size_t i = 0; i < num_interleaved; ++i) {
            std::vector<Commitment> group_commitment;
            for (size_t j = 0; j < group_size; j++) {
                group_commitment.emplace_back(ck.commit(groups[i][j]));
            }
            groups_commitments.emplace_back(group_commitment);
        }
 
        return { groups, interleaved_polynomials, c_evaluations, groups_commitments };
    }
 
    template <typename Flavor>
    void compute_sumcheck_opening_data(const size_t log_n,
                                       const size_t sumcheck_univariate_length,
                                       std::vector<Fr>& challenge,
                                       const CommitmentKey& ck)
    {
        // Generate valid sumcheck polynomials of given length
        auto mock_sumcheck_polynomials = ZKSumcheckData<Flavor>(log_n, sumcheck_univariate_length);
 
        for (size_t idx = 0; idx < log_n; idx++) {
            bb::Polynomial<Fr> round_univariate = mock_sumcheck_polynomials.libra_univariates[idx];
 
            round_univariate.at(0) += mock_sumcheck_polynomials.libra_running_sum;
 
            sumcheck_commitments.push_back(ck.commit(round_univariate));
 
            sumcheck_evaluations.push_back({ round_univariate.at(0),
                                             round_univariate.evaluate(Fr(1)),
                                             round_univariate.evaluate(challenge[idx]) });
 
            mock_sumcheck_polynomials.update_zk_sumcheck_data(challenge[idx], idx);
            round_univariates.push_back(round_univariate);
        }
    }
};
 
} // namespace bb