translator_non_native_field_relation_impl.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/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 FF shift = FF(uint256_t(1) << NUM_LIMB_BITS);
    static FF shiftx2 = FF(uint256_t(1) << (NUM_LIMB_BITS * 2));
    static FF shiftx3 = FF(uint256_t(1) << (NUM_LIMB_BITS * 3));
    static uint512_t MODULUS_U512 = uint512_t(curve::BN254::BaseField::modulus);
    static uint512_t BINARY_BASIS_MODULUS = uint512_t(1) << (NUM_LIMB_BITS << 2);
    static 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)
    };
 
    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];
    // for j < 4,  v_i_j is the j-th limb of v^{1+i}
    // v_i_4 is v^{1+i} in the native field
    const auto& v_0_0 = params.batching_challenge_v[0][0];
    const auto& v_0_1 = params.batching_challenge_v[0][1];
    const auto& v_0_2 = params.batching_challenge_v[0][2];
    const auto& v_0_3 = params.batching_challenge_v[0][3];
    const auto& v_0_4 = params.batching_challenge_v[0][4];
    const auto& v_1_0 = params.batching_challenge_v[1][0];
    const auto& v_1_1 = params.batching_challenge_v[1][1];
    const auto& v_1_2 = params.batching_challenge_v[1][2];
    const auto& v_1_3 = params.batching_challenge_v[1][3];
    const auto& v_1_4 = params.batching_challenge_v[1][4];
    const auto& v_2_0 = params.batching_challenge_v[2][0];
    const auto& v_2_1 = params.batching_challenge_v[2][1];
    const auto& v_2_2 = params.batching_challenge_v[2][2];
    const auto& v_2_3 = params.batching_challenge_v[2][3];
    const auto& v_2_4 = params.batching_challenge_v[2][4];
    const auto& v_3_0 = params.batching_challenge_v[3][0];
    const auto& v_3_1 = params.batching_challenge_v[3][1];
    const auto& v_3_2 = params.batching_challenge_v[3][2];
    const auto& v_3_3 = params.batching_challenge_v[3][3];
    const auto& v_3_4 = params.batching_challenge_v[3][4];
 
    const auto& op = View(in.op);
    const auto& p_x_low_limbs = View(in.p_x_low_limbs);
    const auto& p_y_low_limbs = View(in.p_y_low_limbs);
    const auto& p_x_high_limbs = View(in.p_x_high_limbs);
    const auto& p_y_high_limbs = 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_low_limbs = View(in.z_low_limbs);
    const auto& z_high_limbs = View(in.z_high_limbs);
    const auto& quotient_low_binary_limbs = View(in.quotient_low_binary_limbs);
    const auto& quotient_high_binary_limbs = View(in.quotient_high_binary_limbs);
    const auto& p_x_low_limbs_shift = View(in.p_x_low_limbs_shift);
    const auto& p_y_low_limbs_shift = View(in.p_y_low_limbs_shift);
    const auto& p_x_high_limbs_shift = View(in.p_x_high_limbs_shift);
    const auto& p_y_high_limbs_shift = View(in.p_y_high_limbs_shift);
    const auto& accumulators_binary_limbs_0_shift = View(in.accumulators_binary_limbs_0_shift);
    const auto& accumulators_binary_limbs_1_shift = View(in.accumulators_binary_limbs_1_shift);
    const auto& accumulators_binary_limbs_2_shift = View(in.accumulators_binary_limbs_2_shift);
    const auto& accumulators_binary_limbs_3_shift = View(in.accumulators_binary_limbs_3_shift);
    const auto& z_low_limbs_shift = View(in.z_low_limbs_shift);
    const auto& z_high_limbs_shift = View(in.z_high_limbs_shift);
    const auto& quotient_low_binary_limbs_shift = View(in.quotient_low_binary_limbs_shift);
    const auto& quotient_high_binary_limbs_shift = View(in.quotient_high_binary_limbs_shift);
    const auto& relation_wide_limbs = View(in.relation_wide_limbs);
    const auto& relation_wide_limbs_shift = View(in.relation_wide_limbs_shift);
    const auto& lagrange_even_in_minicircuit = View(in.lagrange_even_in_minicircuit);
 
    // Contribution (1) Computing the mod 2²⁷² relation over lower 136 bits
    // clang-format off
        // the index-0 limb
        auto tmp = accumulators_binary_limbs_0_shift * evaluation_input_x_0
                   + op
                   + p_x_low_limbs     * v_0_0
                   + p_y_low_limbs     * v_1_0
                   + z_low_limbs       * v_2_0
                   + z_low_limbs_shift * v_3_0
                   + quotient_low_binary_limbs * NEGATIVE_MODULUS_LIMBS[0]
                   - accumulators_binary_limbs_0;
 
        // the index-1 limb
        tmp += (accumulators_binary_limbs_1_shift   * evaluation_input_x_0
                   + accumulators_binary_limbs_0_shift * evaluation_input_x_1
                   + p_x_low_limbs       * v_0_1
                   + p_x_low_limbs_shift * v_0_0
                   + p_y_low_limbs       * v_1_1
                   + p_y_low_limbs_shift * v_1_0
                   + z_low_limbs         * v_2_1
                   + z_high_limbs        * v_2_0
                   + z_low_limbs_shift   * v_3_1
                   + z_high_limbs_shift  * v_3_0
                   + quotient_low_binary_limbs       * NEGATIVE_MODULUS_LIMBS[1]
                   + quotient_low_binary_limbs_shift * NEGATIVE_MODULUS_LIMBS[0]
                   - accumulators_binary_limbs_1)
                * shift ;
    // clang-format on
    // subtract large value; vanishing shows the desired relation holds on low 136-bit limb
    tmp -= relation_wide_limbs * shiftx2;
    tmp *= lagrange_even_in_minicircuit * op;
    tmp *= scaling_factor;
    std::get<0>(accumulators) += tmp;
 
    // Contribution (2) Computing the 2²⁷² relation over higher 136 bits
    // why declare another temporary?
    // clang-format off
        // the index-2 limb, with a carry from the previous calculation
        tmp = relation_wide_limbs
              + accumulators_binary_limbs_2_shift * evaluation_input_x_0
              + accumulators_binary_limbs_1_shift * evaluation_input_x_1
              + accumulators_binary_limbs_0_shift * evaluation_input_x_2
              + p_x_high_limbs      * v_0_0
              + p_x_low_limbs_shift * v_0_1
              + p_x_low_limbs       * v_0_2
              + p_y_high_limbs      * v_1_0
              + p_y_low_limbs_shift * v_1_1
              + p_y_low_limbs       * v_1_2
              + z_high_limbs        * v_2_1
              + z_low_limbs         * v_2_2
              + z_high_limbs_shift  * v_3_1
              + z_low_limbs_shift   * v_3_2
              + quotient_high_binary_limbs      * NEGATIVE_MODULUS_LIMBS[0]
              + quotient_low_binary_limbs_shift * NEGATIVE_MODULUS_LIMBS[1]
              + quotient_low_binary_limbs       * NEGATIVE_MODULUS_LIMBS[2]
              - accumulators_binary_limbs_2;
 
        // the index-2 limb
        tmp += (accumulators_binary_limbs_3_shift   * evaluation_input_x_0
                   + accumulators_binary_limbs_2_shift   * evaluation_input_x_1
                   + accumulators_binary_limbs_1_shift * evaluation_input_x_2
                   + accumulators_binary_limbs_0_shift * evaluation_input_x_3
                   + p_x_high_limbs_shift * v_0_0
                   + p_x_high_limbs       * v_0_1
                   + p_x_low_limbs_shift  * v_0_2
                   + p_x_low_limbs        * v_0_3
                   + p_y_high_limbs_shift * v_1_0
                   + p_y_high_limbs       * v_1_1
                   + p_y_low_limbs_shift  * v_1_2
                   + p_y_low_limbs        * v_1_3
                   + z_high_limbs         * v_2_2
                   + z_low_limbs          * v_2_3
                   + z_high_limbs_shift   * v_3_2
                   + z_low_limbs_shift    * v_3_3
                   + quotient_high_binary_limbs_shift * NEGATIVE_MODULUS_LIMBS[0]
                   + quotient_high_binary_limbs       * NEGATIVE_MODULUS_LIMBS[1]
                   + quotient_low_binary_limbs_shift  * NEGATIVE_MODULUS_LIMBS[2]
                   + quotient_low_binary_limbs        * NEGATIVE_MODULUS_LIMBS[3]
                   - accumulators_binary_limbs_3)
                * shift;
    // clang-format on
    // subtract large value; vanishing shows the desired relation holds on high 136-bit limb
    tmp -= relation_wide_limbs_shift * shiftx2;
    tmp *= lagrange_even_in_minicircuit * op;
    tmp *= scaling_factor;
    std::get<1>(accumulators) += tmp;
 
    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;
    };
 
    // Reconstructing native versions of values
    auto reconstructed_p_x =
        reconstruct_from_four(p_x_low_limbs, p_x_low_limbs_shift, p_x_high_limbs, p_x_high_limbs_shift);
    auto reconstructed_p_y =
        reconstruct_from_four(p_y_low_limbs, p_y_low_limbs_shift, p_y_high_limbs, p_y_high_limbs_shift);
    auto reconstructed_previous_accumulator = reconstruct_from_four(accumulators_binary_limbs_0_shift,
                                                                    accumulators_binary_limbs_1_shift,
                                                                    accumulators_binary_limbs_2_shift,
                                                                    accumulators_binary_limbs_3_shift);
    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_low_limbs, z_high_limbs);
    auto reconstructed_z2 = reconstruct_from_two(z_low_limbs_shift, z_high_limbs_shift);
    auto reconstructed_quotient = reconstruct_from_four(quotient_low_binary_limbs,
                                                        quotient_low_binary_limbs_shift,
                                                        quotient_high_binary_limbs,
                                                        quotient_high_binary_limbs_shift);
 
    // Contribution (3). Evaluating integer relation over native field
    // clang-format off
        // the native limb index is 4
        tmp = reconstructed_previous_accumulator * evaluation_input_x_4
                     + op
                     + reconstructed_p_x * v_0_4
                     + reconstructed_p_y * v_1_4
                     + reconstructed_z1  * v_2_4
                     + reconstructed_z2  * v_3_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