translator_non_native_field_relation_impl.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Planned, auditors: [], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
#include "barretenberg/relations/translator_vm/translator_non_native_field_relation.hpp"
 
namespace bb {
template <typename FF>
template <typename ContainerOverSubrelations, typename AllEntities, typename Parameters>
void TranslatorNonNativeFieldRelationImpl<FF>::accumulate(ContainerOverSubrelations& accumulators,
                                                          const AllEntities& in,
                                                          const Parameters& params,
                                                          const FF& scaling_factor)
{
 
    using Accumulator = std::tuple_element_t<0, ContainerOverSubrelations>;
    using View = typename Accumulator::View;
 
    static constexpr size_t NUM_LIMB_BITS = 68;
    static const FF shift = FF(uint256_t(1) << NUM_LIMB_BITS);
    static const FF shiftx2 = FF(uint256_t(1) << (NUM_LIMB_BITS * 2));
    static const FF shiftx3 = FF(uint256_t(1) << (NUM_LIMB_BITS * 3));
    static constexpr uint512_t MODULUS_U512 = uint512_t(curve::BN254::BaseField::modulus);
    static constexpr uint512_t BINARY_BASIS_MODULUS = uint512_t(1) << (NUM_LIMB_BITS << 2);
    static constexpr uint512_t NEGATIVE_PRIME_MODULUS = BINARY_BASIS_MODULUS - MODULUS_U512;
    static const std::array<FF, 5> NEGATIVE_MODULUS_LIMBS = {
        FF(NEGATIVE_PRIME_MODULUS.slice(0, NUM_LIMB_BITS).lo),
        FF(NEGATIVE_PRIME_MODULUS.slice(NUM_LIMB_BITS, NUM_LIMB_BITS * 2).lo),
        FF(NEGATIVE_PRIME_MODULUS.slice(NUM_LIMB_BITS * 2, NUM_LIMB_BITS * 3).lo),
        FF(NEGATIVE_PRIME_MODULUS.slice(NUM_LIMB_BITS * 3, NUM_LIMB_BITS * 4).lo),
        -FF(curve::BN254::BaseField::modulus)
    };
 
    // Limbs of evaluation challenge x
    const auto& evaluation_input_x_0 = params.evaluation_input_x[0];
    const auto& evaluation_input_x_1 = params.evaluation_input_x[1];
    const auto& evaluation_input_x_2 = params.evaluation_input_x[2];
    const auto& evaluation_input_x_3 = params.evaluation_input_x[3];
    const auto& evaluation_input_x_4 = params.evaluation_input_x[4];
 
    // Limbs of batching challenge v
    const auto& v_0 = params.batching_challenge_v[0][0];
    const auto& v_1 = params.batching_challenge_v[0][1];
    const auto& v_2 = params.batching_challenge_v[0][2];
    const auto& v_3 = params.batching_challenge_v[0][3];
    const auto& v_4 = params.batching_challenge_v[0][4];
 
    // Limbs of batching challenge v²
    const auto& v_sqr_0 = params.batching_challenge_v[1][0];
    const auto& v_sqr_1 = params.batching_challenge_v[1][1];
    const auto& v_sqr_2 = params.batching_challenge_v[1][2];
    const auto& v_sqr_3 = params.batching_challenge_v[1][3];
    const auto& v_sqr_4 = params.batching_challenge_v[1][4];
 
    // Limbs of batching challenge v³
    const auto& v_cube_0 = params.batching_challenge_v[2][0];
    const auto& v_cube_1 = params.batching_challenge_v[2][1];
    const auto& v_cube_2 = params.batching_challenge_v[2][2];
    const auto& v_cube_3 = params.batching_challenge_v[2][3];
    const auto& v_cube_4 = params.batching_challenge_v[2][4];
 
    // Limbs of batching challenge v⁴
    const auto& v_quad_0 = params.batching_challenge_v[3][0];
    const auto& v_quad_1 = params.batching_challenge_v[3][1];
    const auto& v_quad_2 = params.batching_challenge_v[3][2];
    const auto& v_quad_3 = params.batching_challenge_v[3][3];
    const auto& v_quad_4 = params.batching_challenge_v[3][4];
 
    // Fetch witness values
    // Pₓ = (Pₓ,₃ || Pₓ,₂ || Pₓ,₁ || Pₓ,₀)
    // Pᵧ = (Pᵧ,₃ || Pᵧ,₂ || Pᵧ,₁ || Pᵧ,₀)
    // z₁ = (z₁,₁ || z₁,₀)
    // z₂ = (z₂,₁ || z₂,₀)
    // Q  = (q₃ || q₂ || q₁ || q₀)
    const auto& op = View(in.op);
    const auto& p_x_limb_0 = View(in.p_x_low_limbs);
    const auto& p_y_limb_0 = View(in.p_y_low_limbs);
    const auto& p_x_limb_2 = View(in.p_x_high_limbs);
    const auto& p_y_limb_2 = View(in.p_y_high_limbs);
    const auto& accumulators_binary_limbs_0 = View(in.accumulators_binary_limbs_0);
    const auto& accumulators_binary_limbs_1 = View(in.accumulators_binary_limbs_1);
    const auto& accumulators_binary_limbs_2 = View(in.accumulators_binary_limbs_2);
    const auto& accumulators_binary_limbs_3 = View(in.accumulators_binary_limbs_3);
    const auto& z_first_limb_0 = View(in.z_low_limbs);
    const auto& z_first_limb_1 = View(in.z_high_limbs);
    const auto& quotient_binary_limbs_0 = View(in.quotient_low_binary_limbs);
    const auto& quotient_binary_limbs_1 = View(in.quotient_low_binary_limbs_shift);
    const auto& p_x_limb_1 = View(in.p_x_low_limbs_shift);
    const auto& p_y_limb_1 = View(in.p_y_low_limbs_shift);
    const auto& p_x_limb_3 = View(in.p_x_high_limbs_shift);
    const auto& p_y_limb_3 = View(in.p_y_high_limbs_shift);
    const auto& prev_accumulators_binary_limbs_0 = View(in.accumulators_binary_limbs_0_shift);
    const auto& prev_accumulators_binary_limbs_1 = View(in.accumulators_binary_limbs_1_shift);
    const auto& prev_accumulators_binary_limbs_2 = View(in.accumulators_binary_limbs_2_shift);
    const auto& prev_accumulators_binary_limbs_3 = View(in.accumulators_binary_limbs_3_shift);
    const auto& z_second_limb_0 = View(in.z_low_limbs_shift);
    const auto& z_second_limb_1 = View(in.z_high_limbs_shift);
    const auto& quotient_binary_limbs_2 = View(in.quotient_high_binary_limbs);
    const auto& quotient_binary_limbs_3 = View(in.quotient_high_binary_limbs_shift);
    const auto& relation_wide_limbs_lo = View(in.relation_wide_limbs);
    const auto& relation_wide_limbs_hi = View(in.relation_wide_limbs_shift);
    const auto& lagrange_even_in_minicircuit = View(in.lagrange_even_in_minicircuit);
 
    // clang-format off
        // T₀: Limb 0 contribution (all products contributing at weight 2⁰)
        auto tmp = prev_accumulators_binary_limbs_0 * evaluation_input_x_0
                   + op
                   + p_x_limb_0 * v_0
                   + p_y_limb_0 * v_sqr_0
                   + z_first_limb_0 * v_cube_0
                   + z_second_limb_0 * v_quad_0
                   + quotient_binary_limbs_0 * NEGATIVE_MODULUS_LIMBS[0]
                   - accumulators_binary_limbs_0;
 
        // T₁: Limb 1 contribution (all cross-products contributing at weight 2⁶⁸)
        tmp += (prev_accumulators_binary_limbs_1      * evaluation_input_x_0
                   + prev_accumulators_binary_limbs_0 * evaluation_input_x_1
                   + p_x_limb_0 * v_1
                   + p_x_limb_1 * v_0
                   + p_y_limb_0 * v_sqr_1
                   + p_y_limb_1 * v_sqr_0
                   + z_first_limb_0 * v_cube_1
                   + z_first_limb_1 * v_cube_0
                   + z_second_limb_0 * v_quad_1
                   + z_second_limb_1 * v_quad_0
                   + quotient_binary_limbs_0 * NEGATIVE_MODULUS_LIMBS[1]
                   + quotient_binary_limbs_1 * NEGATIVE_MODULUS_LIMBS[0]
                   - accumulators_binary_limbs_1)
                * shift ;
    // clang-format on
    // Subtract 2¹³⁶·c_lo: if the result is zero, lower 136 bits are correct
    tmp -= relation_wide_limbs_lo * shiftx2;
    tmp *= lagrange_even_in_minicircuit * op;
    tmp *= scaling_factor;
    std::get<0>(accumulators) += tmp;
 
    // clang-format off
        // T₂: Limb 2 contribution (with carry from lower 136 bits)
        tmp = relation_wide_limbs_lo
              + prev_accumulators_binary_limbs_2 * evaluation_input_x_0
              + prev_accumulators_binary_limbs_1 * evaluation_input_x_1
              + prev_accumulators_binary_limbs_0 * evaluation_input_x_2
              + p_x_limb_2 * v_0
              + p_x_limb_1 * v_1
              + p_x_limb_0 * v_2
              + p_y_limb_2 * v_sqr_0
              + p_y_limb_1 * v_sqr_1
              + p_y_limb_0 * v_sqr_2
              + z_first_limb_1 * v_cube_1
              + z_first_limb_0 * v_cube_2
              + z_second_limb_1 * v_quad_1
              + z_second_limb_0 * v_quad_2
              + quotient_binary_limbs_2 * NEGATIVE_MODULUS_LIMBS[0]
              + quotient_binary_limbs_1 * NEGATIVE_MODULUS_LIMBS[1]
              + quotient_binary_limbs_0 * NEGATIVE_MODULUS_LIMBS[2]
              - accumulators_binary_limbs_2;
 
        // T₃: Limb 3 contribution (all cross-products contributing at weight 2²⁰⁴)
        tmp += (prev_accumulators_binary_limbs_3      * evaluation_input_x_0
                   + prev_accumulators_binary_limbs_2 * evaluation_input_x_1
                   + prev_accumulators_binary_limbs_1 * evaluation_input_x_2
                   + prev_accumulators_binary_limbs_0 * evaluation_input_x_3
                   + p_x_limb_3 * v_0
                   + p_x_limb_2 * v_1
                   + p_x_limb_1 * v_2
                   + p_x_limb_0 * v_3
                   + p_y_limb_3 * v_sqr_0
                   + p_y_limb_2 * v_sqr_1
                   + p_y_limb_1 * v_sqr_2
                   + p_y_limb_0 * v_sqr_3
                   + z_first_limb_1 * v_cube_2
                   + z_first_limb_0 * v_cube_3
                   + z_second_limb_1 * v_quad_2
                   + z_second_limb_0 * v_quad_3
                   + quotient_binary_limbs_3 * NEGATIVE_MODULUS_LIMBS[0]
                   + quotient_binary_limbs_2 * NEGATIVE_MODULUS_LIMBS[1]
                   + quotient_binary_limbs_1 * NEGATIVE_MODULUS_LIMBS[2]
                   + quotient_binary_limbs_0 * NEGATIVE_MODULUS_LIMBS[3]
                   - accumulators_binary_limbs_3)
                * shift;
    // clang-format on
    // Subtract 2¹³⁶·c_hi: if the result is zero, higher 136 bits are correct
    tmp -= relation_wide_limbs_hi * shiftx2;
    tmp *= lagrange_even_in_minicircuit * op;
    tmp *= scaling_factor;
    std::get<1>(accumulators) += tmp;
 
    // Helper functions to reconstruct field elements from limbs
    const auto reconstruct_from_two = [](const auto& l0, const auto& l1) { return l0 + l1 * shift; };
 
    const auto reconstruct_from_four = [](const auto& l0, const auto& l1, const auto& l2, const auto& l3) {
        return l0 + l1 * shift + l2 * shiftx2 + l3 * shiftx3;
    };
 
    // Reconstruct native 𝔽ᵣ representations from binary limbs
    auto reconstructed_p_x = reconstruct_from_four(p_x_limb_0, p_x_limb_1, p_x_limb_2, p_x_limb_3);
    auto reconstructed_p_y = reconstruct_from_four(p_y_limb_0, p_y_limb_1, p_y_limb_2, p_y_limb_3);
    auto reconstructed_previous_accumulator = reconstruct_from_four(prev_accumulators_binary_limbs_0,
                                                                    prev_accumulators_binary_limbs_1,
                                                                    prev_accumulators_binary_limbs_2,
                                                                    prev_accumulators_binary_limbs_3);
    auto reconstructed_current_accumulator = reconstruct_from_four(accumulators_binary_limbs_0,
                                                                   accumulators_binary_limbs_1,
                                                                   accumulators_binary_limbs_2,
                                                                   accumulators_binary_limbs_3);
    auto reconstructed_z1 = reconstruct_from_two(z_first_limb_0, z_first_limb_1);
    auto reconstructed_z2 = reconstruct_from_two(z_second_limb_0, z_second_limb_1);
    auto reconstructed_quotient = reconstruct_from_four(
        quotient_binary_limbs_0, quotient_binary_limbs_1, quotient_binary_limbs_2, quotient_binary_limbs_3);
 
    // clang-format off
        // Compute accumulation formula using native 𝔽ᵣ arithmetic (limb index 4)
        tmp = reconstructed_previous_accumulator * evaluation_input_x_4
                     + op
                     + reconstructed_p_x * v_4
                     + reconstructed_p_y * v_sqr_4
                     + reconstructed_z1  * v_cube_4
                     + reconstructed_z2  * v_quad_4
                     + reconstructed_quotient * NEGATIVE_MODULUS_LIMBS[4]
                     - reconstructed_current_accumulator;
    // clang-format on
    tmp *= lagrange_even_in_minicircuit * op;
    tmp *= scaling_factor;
    std::get<2>(accumulators) += tmp;
};
} // namespace bb