elliptic_relation.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Luke, Raju], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
#include "barretenberg/ecc/curves/bn254/bn254.hpp"
#include "barretenberg/ecc/curves/grumpkin/grumpkin.hpp"
#include "barretenberg/relations/relation_types.hpp"
 
namespace bb {
 
template <typename FF_> class EllipticRelationImpl {
  public:
    using FF = FF_;
 
    static constexpr std::array<size_t, 2> SUBRELATION_PARTIAL_LENGTHS{
        6, // x-coordinate sub-relation
        6, // y-coordinate sub-relation
    };
 
    template <typename AllEntities> inline static bool skip(const AllEntities& in)
    {
        return in[AllEntities::EntityId::q_elliptic].is_zero();
    }
 
    static constexpr FF get_curve_b()
    {
        if constexpr (FF::modulus == bb::fq::modulus) {
            return bb::g1::curve_b;
        } else if constexpr (FF::modulus == grumpkin::fq::modulus) {
            return grumpkin::g1::curve_b;
        } else {
            static_assert(!std::is_same_v<FF, FF>, "Unsupported field type for elliptic relation");
        }
    }
 
    template <typename ContainerOverSubrelations, typename AllEntities, typename Parameters>
    inline static void accumulate(ContainerOverSubrelations& accumulators,
                                  const AllEntities& in,
                                  const Parameters&,
                                  const FF& scaling_factor)
    {
        using Accumulator = typename std::tuple_element_t<0, ContainerOverSubrelations>;
        using CoefficientAccumulator = typename Accumulator::CoefficientAccumulator;
        auto x_3_m = CoefficientAccumulator(in[AllEntities::EntityId::w_r_shift]);
        auto y_1_m = CoefficientAccumulator(in[AllEntities::EntityId::w_o]);
        auto y_2_m = CoefficientAccumulator(in[AllEntities::EntityId::w_4_shift]);
 
        auto x_1_m = CoefficientAccumulator(in[AllEntities::EntityId::w_r]);
        auto x_2_m = CoefficientAccumulator(in[AllEntities::EntityId::w_l_shift]);
        auto y_3_m = CoefficientAccumulator(in[AllEntities::EntityId::w_o_shift]);
        auto q_elliptic_m = CoefficientAccumulator(in[AllEntities::EntityId::q_elliptic]);
        auto q_is_double_m = CoefficientAccumulator(in[AllEntities::EntityId::q_m]);
        auto q_sign_m = CoefficientAccumulator(in[AllEntities::EntityId::q_l]);
 
        // We efficiently construct the following:
        auto x2_sub_x1_m = (x_2_m - x_1_m);                         // (x2 - x1)
        auto x1_mul_3_m = (x_1_m + x_1_m + x_1_m);                  // (3*x1)
        auto x3_sub_x1_m = x_3_m - x_1_m;                           // (x3 - x1)
        auto x3_plus_two_x1_m = x3_sub_x1_m + x1_mul_3_m;           // (x3 - x1 + 3*x1) = (x3 + 2*x1)
        auto x3_plus_x2_plus_x1_m = x3_plus_two_x1_m + x2_sub_x1_m; // (x3 + 2*x1 + x2 - x1) = (x3 + x2 + x1)
        Accumulator x3_plus_x2_plus_x1(x3_plus_x2_plus_x1_m);
        Accumulator x3_sub_x1(x3_sub_x1_m);
        Accumulator x1_mul_3(x1_mul_3_m);
        Accumulator x3_plus_two_x1(x3_plus_two_x1_m);
 
        // Contribution (1) point addition, x-coordinate check:
        // q_elliptic * (q_is_double - 1) * (x3 + x2 + x1)(x2 - x1)(x2 - x1) - y2^2 - y1^2 + 2(y2y1)*q_sign = 0
        auto y2_sqr_m = y_2_m.sqr();
        auto y1_sqr_m = y_1_m.sqr();
        auto y2_mul_q_sign_m = y_2_m * q_sign_m;
        auto x_add_identity = x3_plus_x2_plus_x1 * Accumulator(x2_sub_x1_m.sqr()) - Accumulator(y2_sqr_m + y1_sqr_m) +
                              Accumulator(y2_mul_q_sign_m + y2_mul_q_sign_m) * Accumulator(y_1_m);
 
        auto q_elliptic_by_scaling_m = q_elliptic_m * scaling_factor;                   // a * q_elliptic
        auto q_elliptic_q_double_scaling_m = (q_elliptic_by_scaling_m * q_is_double_m); // a * q_elliptic * q_is_double
        Accumulator q_elliptic_q_double_scaling(q_elliptic_q_double_scaling_m);
        // (a * q_elliptic * q_is_double - a * q_elliptic) = a * q_elliptic * (q_is_double - 1)
        auto neg_q_elliptic_not_double_scaling = Accumulator(q_elliptic_q_double_scaling_m - q_elliptic_by_scaling_m);
        std::get<0>(accumulators) -= x_add_identity * neg_q_elliptic_not_double_scaling;
 
        // Contribution (2) point addition, x-coordinate check:
        // q_elliptic *  (q_is_double - 1) * (y1 + y3)(x2 - x1) + (x3 - x1)(q_sign * y2 - y1) = 0
        auto y1_plus_y3_m = y_1_m + y_3_m;       // (y1 + y3)
        auto y_diff_m = y2_mul_q_sign_m - y_1_m; // (q_sign * y2 - y1)
        auto y_diff = Accumulator(y_diff_m);
        auto y_add_identity = Accumulator(y1_plus_y3_m * x2_sub_x1_m) + (x3_sub_x1)*y_diff;
        std::get<1>(accumulators) -= y_add_identity * neg_q_elliptic_not_double_scaling;
 
        // Contribution (3) point doubling, x-coordinate check
        // (x3 + x1 + x1) (4*y1*y1) - 9 * x1 * x1 * x1 * x1 = 0
        // N.B. we're using the equivalence x1^3 === y1^2 - curve_b to reduce degree by 1
        const auto curve_b = get_curve_b();
        auto x_pow_4_mul_3 = (Accumulator(y1_sqr_m - curve_b)) * x1_mul_3;
        auto y1_sqr_mul_4_m = y1_sqr_m + y1_sqr_m;
        y1_sqr_mul_4_m += y1_sqr_mul_4_m;
        auto x1_pow_4_mul_9 = x_pow_4_mul_3 + x_pow_4_mul_3 + x_pow_4_mul_3;
        auto x_double_identity = x3_plus_two_x1 * Accumulator(y1_sqr_mul_4_m) - x1_pow_4_mul_9;
        std::get<0>(accumulators) += x_double_identity * q_elliptic_q_double_scaling;
 
        // Contribution (4) point doubling, y-coordinate check
        // (y1 + y3) (2*y1) - (3 * x1 * x1)(x1 - x3) = 0
        auto x1_sqr_mul_3 = Accumulator(x1_mul_3_m * x_1_m);
        auto neg_y_double_identity = x1_sqr_mul_3 * (x3_sub_x1) + Accumulator((y_1_m + y_1_m) * (y1_plus_y3_m));
        std::get<1>(accumulators) -= neg_y_double_identity * q_elliptic_q_double_scaling;
    };
};
 
template <typename FF> using EllipticRelation = Relation<EllipticRelationImpl<FF>>;
} // namespace bb