Barretenberg: src/barretenberg/relations/translator_vm/translator_non_native_field_short_relation_impl.hpp Source 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_short_relation.hpp"

#include "barretenberg/translator_vm/translator_circuit_builder.hpp"


namespace bb {

template <typename FF>

template <typename ContainerOverSubrelations, typename AllEntities, typename Parameters>


void TranslatorNonNativeFieldShortRelationImpl<FF>::accumulate(ContainerOverSubrelations& accumulators,

                                                               const AllEntities& in,

                                                               const Parameters& params,

                                                               const FF& scaling_factor)

{


    using Accumulator = std::tuple_element_t<0, ContainerOverSubrelations>;

    using View = TranslatorShortMonomialView<Accumulator>;


    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 const std::array<FF, 5> NEGATIVE_MODULUS_LIMBS =

        TranslatorCircuitBuilder::compute_negative_modulus_limbs<FF>();


    // 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);

    const auto even_op_selector_scaled = Accumulator(lagrange_even_in_minicircuit * (op * scaling_factor));


    // 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;

    std::get<0>(accumulators) += Accumulator(tmp) * even_op_selector_scaled;


    // 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;

    std::get<1>(accumulators) += Accumulator(tmp) * even_op_selector_scaled;


    // 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

    std::get<2>(accumulators) += Accumulator(tmp) * even_op_selector_scaled;

};


} // namespace bb

FF
bb::field< bb::Bn254FrParams > FF
Definition field.cpp:24

bb::TranslatorNonNativeFieldShortRelationImpl::accumulate
static void accumulate(ContainerOverSubrelations &accumulators, const AllEntities &in, const Parameters &params, const FF &scaling_factor)
Expression for the computation of Translator accumulator in integers through 68-bit limbs and native ...
Definition translator_non_native_field_short_relation_impl.hpp:79

bb::TranslatorNonNativeFieldShortRelationImpl::FF
FF_ FF
Definition translator_non_native_field_short_relation.hpp:16

bb::numeric::uint256_t
Definition uint256.hpp:32

bb
Entry point for Barretenberg command-line interface.
Definition api.hpp:5

bb::TranslatorShortMonomialView
typename Accumulator::CoefficientAccumulator TranslatorShortMonomialView
Definition translator_short_monomial_relation_utils.hpp:11

std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13

translator_circuit_builder.hpp

translator_non_native_field_short_relation.hpp