grand_product_library.test.cpp

Go to the documentation of this file.

#include "barretenberg/honk/library/grand_product_library.hpp"
#include "barretenberg/ecc/curves/bn254/bn254.hpp"
#include "barretenberg/flavor/ultra_flavor.hpp"
 
#include <gtest/gtest.h>
using namespace bb;
 
template <class FF> class GrandProductTests : public testing::Test {
 
    using Polynomial = bb::Polynomial<FF>;
 
  public:
    void SetUp() { bb::srs::init_file_crs_factory(bb::srs::bb_crs_path()); }
 
    static void populate_span(auto& polynomial_view, const auto& polynomial)
    {
        ASSERT_LE(polynomial_view.size(), polynomial.size());
        for (size_t idx = 0; idx < polynomial.size(); idx++) {
            polynomial_view[idx] = polynomial[idx];
        }
    };
 
    template <typename Flavor> static void test_permutation_grand_product_construction()
    {
        using ProverPolynomials = typename Flavor::ProverPolynomials;
 
        // Set a mock circuit size
        static const size_t circuit_size = 8;
 
        // Construct a ProverPolynomials object with completely random polynomials
        ProverPolynomials prover_polynomials;
        for (auto& poly : prover_polynomials.get_to_be_shifted()) {
            poly = Polynomial::random(circuit_size, /*shiftable*/ 1);
        }
        for (auto& poly : prover_polynomials.get_all()) {
            if (poly.is_empty()) {
                poly = Polynomial::random(circuit_size);
            }
        }
        // Zero out z_perm — compute_grand_product will fill the active region and expects
        // z_perm[gp_start] = 0 as the initial value of the running product.
        prover_polynomials.z_perm = Polynomial::shiftable(circuit_size, circuit_size);
 
        // Get random challenges
        auto beta = FF::random_element();
        auto gamma = FF::random_element();
 
        RelationParameters<FF> params{
            .eta = 0,
            .beta = beta,
            .gamma = gamma,
            .public_input_delta = 1,
        };
 
        compute_grand_product<Flavor, typename bb::UltraPermutationRelation<FF>>(prover_polynomials, params);
 
        // Method 2: Compute z_perm locally using the simplest non-optimized syntax possible. The comment below,
        // which describes the computation in 4 steps, is adapted from a similar comment in
        // compute_grand_product_polynomial.
        /*
         * Assume Flavor::NUM_WIRES 3. Z_perm may be defined in terms of its values
         * on X_i = 0,1,...,n-1 as Z_perm[0] = 0 and for i = 1:n-1
         *
         *                  (w_1(j) + β⋅id_1(j) + γ) ⋅ (w_2(j) + β⋅id_2(j) + γ) ⋅ (w_3(j) + β⋅id_3(j) + γ)
         * Z_perm[i] = ∏ --------------------------------------------------------------------------------
         *                  (w_1(j) + β⋅σ_1(j) + γ) ⋅ (w_2(j) + β⋅σ_2(j) + γ) ⋅ (w_3(j) + β⋅σ_3(j) + γ)
         *
         * where ∏ := ∏_{j=0:i-1} and id_i(X) = id(X) + n*(i-1). These evaluations are constructed over the
         * course of three steps. For expositional simplicity, write Z_perm[i] as
         *
         *                A_1(j) ⋅ A_2(j) ⋅ A_3(j)
         * Z_perm[i] = ∏ --------------------------
         *                B_1(j) ⋅ B_2(j) ⋅ B_3(j)
         *
         * Step 1) Compute the 2*Flavor::NUM_WIRES length-n polynomials A_i and B_i
         * Step 2) Compute the 2*Flavor::NUM_WIRES length-n polynomials ∏ A_i(j) and ∏ B_i(j)
         * Step 3) Compute the two length-n polynomials defined by
         *          numer[i] = ∏ A_1(j)⋅A_2(j)⋅A_3(j), and denom[i] = ∏ B_1(j)⋅B_2(j)⋅B_3(j)
         * Step 4) Compute Z_perm[i+1] = numer[i]/denom[i] (recall: Z_perm[0] = 1)
         */
 
        // Grand product starts after disabled rows (for flavors with row-disabling polynomial)
        constexpr size_t gp_start = Flavor::TRACE_OFFSET;
        constexpr size_t active_size = circuit_size - gp_start;
 
        // Make scratch space for the numerator and denominator accumulators.
        std::array<std::array<FF, active_size>, Flavor::NUM_WIRES> numerator_accum;
        std::array<std::array<FF, active_size>, Flavor::NUM_WIRES> denominator_accum;
 
        auto wires = prover_polynomials.get_wires();
        auto sigmas = prover_polynomials.get_sigmas();
        auto ids = prover_polynomials.get_ids();
        // Step (1)
        for (size_t i = 0; i < active_size; ++i) {
            const size_t poly_idx = i + gp_start;
            for (size_t k = 0; k < Flavor::NUM_WIRES; ++k) {
                numerator_accum[k][i] = wires[k][poly_idx] + (ids[k][poly_idx] * beta) + gamma;
                denominator_accum[k][i] = wires[k][poly_idx] + (sigmas[k][poly_idx] * beta) + gamma;
            }
        }
 
        // Step (2)
        for (size_t k = 0; k < Flavor::NUM_WIRES; ++k) {
            for (size_t i = 0; i < active_size - 1; ++i) {
                numerator_accum[k][i + 1] *= numerator_accum[k][i];
                denominator_accum[k][i + 1] *= denominator_accum[k][i];
            }
        }
 
        // Step (3)
        for (size_t i = 0; i < active_size; ++i) {
            for (size_t k = 1; k < Flavor::NUM_WIRES; ++k) {
                numerator_accum[0][i] *= numerator_accum[k][i];
                denominator_accum[0][i] *= denominator_accum[k][i];
            }
        }
 
        // Step (4)
        Polynomial z_permutation_expected(circuit_size);
        for (size_t i = 0; i < active_size - 1; ++i) {
            z_permutation_expected.at(gp_start + i + 1) = numerator_accum[0][i] / denominator_accum[0][i];
        }
 
        // Check consistency between locally computed z_perm and the one computed by the prover library.
        // Only compare the active region (after disabled rows); masking values at rows 1..3 are random.
        for (size_t i = gp_start; i < circuit_size; ++i) {
            EXPECT_EQ(prover_polynomials.z_perm[i], z_permutation_expected[i]) << "Mismatch at index " << i;
        }
    };
};
 
using FieldTypes = testing::Types<bb::fr>;
TYPED_TEST_SUITE(GrandProductTests, FieldTypes);
 
TYPED_TEST(GrandProductTests, GrandProductPermutation)
{
    TestFixture::template test_permutation_grand_product_construction<UltraFlavor>();
}