auxiliary_relation.hpp

#pragma once
#include "barretenberg/numeric/uint256/uint256.hpp"
#include "barretenberg/relations/relation_types.hpp"
 
namespace proof_system {
 
template <typename FF_> class AuxiliaryRelationImpl {
  public:
    using FF = FF_;
    /*
     * TODO(https://github.com/AztecProtocol/barretenberg/issues/757): Investigate optimizations.
     * It seems that we could have:
     *     static constexpr std::array<size_t, 6> SUBRELATION_PARTIAL_LENGTHS{
     *     5 // auxiliary sub-relation;
     *     6 // ROM consistency sub-relation 1
     *     6 // ROM consistency sub-relation 2
     *     6 // RAM consistency sub-relation 1
     *     5 // RAM consistency sub-relation 2
     *     5 // RAM consistency sub-relation 3
     * };
     *
     * and
     *
     *     static constexpr std::array<size_t, 6> TOTAL_LENGTH_ADJUSTMENTS{
     *     6, // auxiliary sub-relation
     *     0, // ROM consistency sub-relation 1
     *     0, // ROM consistency sub-relation 2
     *     3, // RAM consistency sub-relation 1
     *     0, // RAM consistency sub-relation 2
     *     1  // RAM consistency sub-relation 3
     * };
     */
 
    static constexpr std::array<size_t, 6> SUBRELATION_PARTIAL_LENGTHS{
        6, // auxiliary sub-relation;
        6, // ROM consistency sub-relation 1
        6, // ROM consistency sub-relation 2
        6, // RAM consistency sub-relation 1
        6, // RAM consistency sub-relation 2
        6  // RAM consistency sub-relation 3
    };
 
    static constexpr std::array<size_t, 6> TOTAL_LENGTH_ADJUSTMENTS{
        6, // auxiliary sub-relation
        6, // ROM consistency sub-relation 1
        6, // ROM consistency sub-relation 2
        6, // RAM consistency sub-relation 1
        6, // RAM consistency sub-relation 2
        6  // RAM consistency sub-relation 3
    };
 
    template <typename ContainerOverSubrelations, typename AllEntities, typename Parameters>
    inline static void accumulate(ContainerOverSubrelations& accumulators,
                                  const AllEntities& in,
                                  const Parameters& params,
                                  const FF& scaling_factor)
    {
 
        // All subrelations have the same length so we use the same length view for all calculations
        using Accumulator = typename std::tuple_element_t<0, ContainerOverSubrelations>;
        using View = typename Accumulator::View;
        using ParameterView = GetParameterView<Parameters, View>;
 
        const auto& eta = ParameterView(params.eta);
 
        auto w_1 = View(in.w_l);
        auto w_2 = View(in.w_r);
        auto w_3 = View(in.w_o);
        auto w_4 = View(in.w_4);
        auto w_1_shift = View(in.w_l_shift);
        auto w_2_shift = View(in.w_r_shift);
        auto w_3_shift = View(in.w_o_shift);
        auto w_4_shift = View(in.w_4_shift);
 
        auto q_1 = View(in.q_l);
        auto q_2 = View(in.q_r);
        auto q_3 = View(in.q_o);
        auto q_4 = View(in.q_4);
        auto q_m = View(in.q_m);
        auto q_c = View(in.q_c);
        auto q_arith = View(in.q_arith);
        auto q_aux = View(in.q_aux);
 
        const FF LIMB_SIZE(uint256_t(1) << 68);
        const FF SUBLIMB_SHIFT(uint256_t(1) << 14);
 
        auto limb_subproduct = w_1 * w_2_shift + w_1_shift * w_2;
        auto non_native_field_gate_2 = (w_1 * w_4 + w_2 * w_3 - w_3_shift);
        non_native_field_gate_2 *= LIMB_SIZE;
        non_native_field_gate_2 -= w_4_shift;
        non_native_field_gate_2 += limb_subproduct;
        non_native_field_gate_2 *= q_4;
 
        limb_subproduct *= LIMB_SIZE;
        limb_subproduct += (w_1_shift * w_2_shift);
        auto non_native_field_gate_1 = limb_subproduct;
        non_native_field_gate_1 -= (w_3 + w_4);
        non_native_field_gate_1 *= q_3;
 
        auto non_native_field_gate_3 = limb_subproduct;
        non_native_field_gate_3 += w_4;
        non_native_field_gate_3 -= (w_3_shift + w_4_shift);
        non_native_field_gate_3 *= q_m;
 
        auto non_native_field_identity = non_native_field_gate_1 + non_native_field_gate_2 + non_native_field_gate_3;
        non_native_field_identity *= q_2;
 
        // ((((w2' * 2^14 + w1') * 2^14 + w3) * 2^14 + w2) * 2^14 + w1 - w4) * qm
        // deg 2
        auto limb_accumulator_1 = w_2_shift * SUBLIMB_SHIFT;
        limb_accumulator_1 += w_1_shift;
        limb_accumulator_1 *= SUBLIMB_SHIFT;
        limb_accumulator_1 += w_3;
        limb_accumulator_1 *= SUBLIMB_SHIFT;
        limb_accumulator_1 += w_2;
        limb_accumulator_1 *= SUBLIMB_SHIFT;
        limb_accumulator_1 += w_1;
        limb_accumulator_1 -= w_4;
        limb_accumulator_1 *= q_4;
 
        // ((((w3' * 2^14 + w2') * 2^14 + w1') * 2^14 + w4) * 2^14 + w3 - w4') * qm
        // deg 2
        auto limb_accumulator_2 = w_3_shift * SUBLIMB_SHIFT;
        limb_accumulator_2 += w_2_shift;
        limb_accumulator_2 *= SUBLIMB_SHIFT;
        limb_accumulator_2 += w_1_shift;
        limb_accumulator_2 *= SUBLIMB_SHIFT;
        limb_accumulator_2 += w_4;
        limb_accumulator_2 *= SUBLIMB_SHIFT;
        limb_accumulator_2 += w_3;
        limb_accumulator_2 -= w_4_shift;
        limb_accumulator_2 *= q_m;
 
        auto limb_accumulator_identity = limb_accumulator_1 + limb_accumulator_2;
        limb_accumulator_identity *= q_3; //  deg 3
 
        auto memory_record_check = w_3 * eta;
        memory_record_check += w_2;
        memory_record_check *= eta;
        memory_record_check += w_1;
        memory_record_check *= eta;
        memory_record_check += q_c;
        auto partial_record_check = memory_record_check; // used in RAM consistency check; deg 1 or 4
        memory_record_check = memory_record_check - w_4;
 
        auto index_delta = w_1_shift - w_1;
        auto record_delta = w_4_shift - w_4;
 
        auto index_is_monotonically_increasing = index_delta * index_delta - index_delta; // deg 2
 
        auto adjacent_values_match_if_adjacent_indices_match = (index_delta * FF(-1) + FF(1)) * record_delta; // deg 2
 
        std::get<1>(accumulators) +=
            adjacent_values_match_if_adjacent_indices_match * (q_1 * q_2) * (q_aux * scaling_factor); // deg 5
        std::get<2>(accumulators) +=
            index_is_monotonically_increasing * (q_1 * q_2) * (q_aux * scaling_factor); // deg 5
        auto ROM_consistency_check_identity = memory_record_check * (q_1 * q_2);        // deg 3 or 7
 
        auto access_type = (w_4 - partial_record_check);             // will be 0 or 1 for honest Prover; deg 1 or 4
        auto access_check = access_type * access_type - access_type; // check value is 0 or 1; deg 2 or 8
 
        // TODO(https://github.com/AztecProtocol/barretenberg/issues/757): If we sorted in
        // reverse order we could re-use `partial_record_check`  1 -  ((w3' * eta + w2') * eta + w1') * eta
        // deg 1 or 4
        auto next_gate_access_type = w_3_shift * eta;
        next_gate_access_type += w_2_shift;
        next_gate_access_type *= eta;
        next_gate_access_type += w_1_shift;
        next_gate_access_type *= eta;
        next_gate_access_type = w_4_shift - next_gate_access_type;
 
        auto value_delta = w_3_shift - w_3;
        auto adjacent_values_match_if_adjacent_indices_match_and_next_access_is_a_read_operation =
            (index_delta * FF(-1) + FF(1)) * value_delta * (next_gate_access_type * FF(-1) + FF(1)); // deg 3 or 6
 
        // We can't apply the RAM consistency check identity on the final entry in the sorted list (the wires in the
        // next gate would make the identity fail).  We need to validate that its 'access type' bool is correct. Can't
        // do  with an arithmetic gate because of the  `eta` factors. We need to check that the *next* gate's access
        // type is  correct, to cover this edge case
        // deg 2 or 4
        auto next_gate_access_type_is_boolean = next_gate_access_type * next_gate_access_type - next_gate_access_type;
 
        // Putting it all together...
        std::get<3>(accumulators) +=
            adjacent_values_match_if_adjacent_indices_match_and_next_access_is_a_read_operation * (q_arith) *
            (q_aux * scaling_factor); // deg 5 or 8
        std::get<4>(accumulators) += index_is_monotonically_increasing * (q_arith) * (q_aux * scaling_factor); // deg 4
        std::get<5>(accumulators) +=
            next_gate_access_type_is_boolean * (q_arith) * (q_aux * scaling_factor); // deg 4 or 6
        auto RAM_consistency_check_identity = access_check * (q_arith);              // deg 3 or 9
 
        auto timestamp_delta = w_2_shift - w_2;
        auto RAM_timestamp_check_identity = (index_delta * FF(-1) + FF(1)) * timestamp_delta - w_3; // deg 3
 
        auto memory_identity = ROM_consistency_check_identity;         // deg 3 or 6
        memory_identity += RAM_timestamp_check_identity * (q_4 * q_1); // deg 4
        memory_identity += memory_record_check * (q_m * q_1);          // deg 3 or 6
        memory_identity += RAM_consistency_check_identity;             // deg 3 or 9
 
        // (deg 3 or 9) + (deg 4) + (deg 3)
        auto auxiliary_identity = memory_identity + non_native_field_identity + limb_accumulator_identity;
        auxiliary_identity *= (q_aux * scaling_factor); // deg 4 or 10
        std::get<0>(accumulators) += auxiliary_identity;
    };
};
 
template <typename FF> using AuxiliaryRelation = Relation<AuxiliaryRelationImpl<FF>>;
} // namespace proof_system