ecdsa_constraints.cpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Federico], commit: 05a381f8b31ae4648e480f1369e911b148216e8b}
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#include "barretenberg/dsl/acir_format/ecdsa_constraints.hpp"
#include "barretenberg/dsl/acir_format/utils.hpp"
#include "barretenberg/stdlib/encryption/ecdsa/ecdsa.hpp"
#include "barretenberg/stdlib/primitives/curves/secp256k1.hpp"
#include "barretenberg/stdlib/primitives/curves/secp256r1.hpp"
 
namespace acir_format {
 
using namespace bb;
 
template <typename Curve>
void create_ecdsa_verify_constraints(typename Curve::Builder& builder, const EcdsaConstraint& input)
{
    using Builder = Curve::Builder;
 
    using Fq = Curve::fq_ct;
    using Fr = Curve::bigfr_ct;
    using G1 = Curve::g1_bigfr_ct;
 
    using field_ct = bb::stdlib::field_t<Builder>;
    using bool_ct = bb::stdlib::bool_t<Builder>;
    using byte_array_ct = bb::stdlib::byte_array<Builder>;
 
    // Define builder variables based on the witness indices
    std::vector<field_ct> hashed_message_fields = fields_from_witnesses(builder, input.hashed_message);
    std::vector<field_ct> r_fields = fields_from_witnesses(builder, std::span(input.signature.begin(), 32));
    std::vector<field_ct> s_fields = fields_from_witnesses(builder, std::span(input.signature.begin() + 32, 32));
    std::vector<field_ct> pub_x_fields = fields_from_witnesses(builder, input.pub_x_indices);
    std::vector<field_ct> pub_y_fields = fields_from_witnesses(builder, input.pub_y_indices);
    field_ct result_field = field_ct::from_witness_index(&builder, input.result);
    bool_ct predicate(to_field_ct(input.predicate, builder)); // Constructor enforces predicate = 0 or 1
 
    if (builder.is_write_vk_mode()) {
        // Fill builder variables in case of empty witness assignment
        create_dummy_ecdsa_constraint<Curve>(
            builder, hashed_message_fields, r_fields, s_fields, pub_x_fields, pub_y_fields, result_field);
    }
 
    // Step 1: Conditionally assign field values when predicate is false
    if (!predicate.is_constant()) {
        // Set r = s = H(m) = 1 when the predicate is false
        for (size_t idx = 0; idx < 32; idx++) {
            r_fields[idx] = field_ct::conditional_assign(predicate, r_fields[idx], field_ct(idx == 0 ? 1 : 0));
            s_fields[idx] = field_ct::conditional_assign(predicate, s_fields[idx], field_ct(idx == 0 ? 1 : 0));
            hashed_message_fields[idx] =
                field_ct::conditional_assign(predicate, hashed_message_fields[idx], field_ct(idx == 0 ? 1 : 0));
        }
 
        // Set public key to 2*generator when predicate is false
        // The choice of 2*generator is arbitrary; it just needs to be a valid point on the curve and different from G
        // or (-G). For secp256r1, the batch multiplication requires that the two points do not have the same x
        // coordinate (so as to create a valid lookup table).
        // Compute as native type to get byte representation
        typename Curve::AffineElementNative default_point_native(Curve::g1::one + Curve::g1::one);
        std::array<uint8_t, 32> default_x_bytes;
        std::array<uint8_t, 32> default_y_bytes;
        Curve::fq::serialize_to_buffer(default_point_native.x, default_x_bytes.data());
        Curve::fq::serialize_to_buffer(default_point_native.y, default_y_bytes.data());
 
        for (size_t i = 0; i < 32; ++i) {
            pub_x_fields[i] = field_ct::conditional_assign(predicate, pub_x_fields[i], field_ct(default_x_bytes[i]));
            pub_y_fields[i] = field_ct::conditional_assign(predicate, pub_y_fields[i], field_ct(default_y_bytes[i]));
        }
    } else {
        BB_ASSERT(input.predicate.value, "Creating ECDSA constraints with a constant predicate equal to false.");
    }
 
    // Step 2: Convert conditionally-assigned fields to byte arrays (adds range constraints on the correct values)
    byte_array_ct hashed_message = fields_to_bytes(builder, hashed_message_fields);
    byte_array_ct pub_x_bytes = fields_to_bytes(builder, pub_x_fields);
    byte_array_ct pub_y_bytes = fields_to_bytes(builder, pub_y_fields);
    byte_array_ct r = fields_to_bytes(builder, r_fields);
    byte_array_ct s = fields_to_bytes(builder, s_fields);
    bool_ct result(result_field); // Constructor enforces result = 0 or 1
 
    // Step 3: Construct public key from byte arrays
    Fq pub_x(pub_x_bytes);
    Fq pub_y(pub_y_bytes);
    // This constructor sets the infinity flag of public_key to false. This is OK because the point at infinity is not a
    // point on the curve and we check tha public_key is on the curve in the ecdsa verification circuit.
    G1 public_key(pub_x, pub_y, /*assert_on_curve=*/false);
 
    // Step 4.
    bool_ct signature_result =
        stdlib::ecdsa_verify_signature<Builder, Curve, Fq, Fr, G1>(hashed_message, public_key, { r, s });
 
    // Step 5.
    // Ensure the circuit is satisfied when predicate is witness false
    signature_result.assert_equal(bool_ct::conditional_assign(predicate, result, signature_result));
}
 
template <typename Curve>
void create_dummy_ecdsa_constraint(typename Curve::Builder& builder,
                                   const std::vector<stdlib::field_t<typename Curve::Builder>>& hashed_message_fields,
                                   const std::vector<stdlib::field_t<typename Curve::Builder>>& r_fields,
                                   const std::vector<stdlib::field_t<typename Curve::Builder>>& s_fields,
                                   const std::vector<stdlib::field_t<typename Curve::Builder>>& pub_x_fields,
                                   const std::vector<stdlib::field_t<typename Curve::Builder>>& pub_y_fields,
                                   const stdlib::field_t<typename Curve::Builder>& result_field)
{
    using FqNative = Curve::fq;
    using G1Native = Curve::g1;
 
    // Vector of 32 copies of bb::fr::zero()
    std::vector<bb::fr> mock_zeros(32, bb::fr::zero());
 
    // Hashed message
    populate_fields(builder, hashed_message_fields, mock_zeros);
 
    // Signature
    populate_fields(builder, r_fields, mock_zeros);
    populate_fields(builder, s_fields, mock_zeros);
 
    // Pub key
    std::array<uint8_t, 32> buffer_x;
    std::array<uint8_t, 32> buffer_y;
    std::vector<bb::fr> mock_pub_x;
    std::vector<bb::fr> mock_pub_y;
    FqNative::serialize_to_buffer(G1Native::one.x, &buffer_x[0]);
    FqNative::serialize_to_buffer(G1Native::one.y, &buffer_y[0]);
    for (auto [byte_x, byte_y] : zip_view(buffer_x, buffer_y)) {
        mock_pub_x.emplace_back(bb::fr(byte_x));
        mock_pub_y.emplace_back(bb::fr(byte_y));
    }
    populate_fields(builder, pub_x_fields, mock_pub_x);
    populate_fields(builder, pub_y_fields, mock_pub_y);
 
    // Result
    builder.set_variable(result_field.get_witness_index(), bb::fr::one());
}
 
template void create_ecdsa_verify_constraints<stdlib::secp256k1<UltraCircuitBuilder>>(UltraCircuitBuilder& builder,
                                                                                      const EcdsaConstraint& input);
template void create_ecdsa_verify_constraints<stdlib::secp256k1<MegaCircuitBuilder>>(MegaCircuitBuilder& builder,
                                                                                     const EcdsaConstraint& input);
template void create_ecdsa_verify_constraints<stdlib::secp256r1<UltraCircuitBuilder>>(UltraCircuitBuilder& builder,
                                                                                      const EcdsaConstraint& input);
template void create_ecdsa_verify_constraints<stdlib::secp256r1<MegaCircuitBuilder>>(MegaCircuitBuilder& builder,
                                                                                     const EcdsaConstraint& input);
 
template void create_dummy_ecdsa_constraint<stdlib::secp256k1<UltraCircuitBuilder>>(
    UltraCircuitBuilder&,
    const std::vector<stdlib::field_t<UltraCircuitBuilder>>&,
    const std::vector<stdlib::field_t<UltraCircuitBuilder>>&,
    const std::vector<stdlib::field_t<UltraCircuitBuilder>>&,
    const std::vector<stdlib::field_t<UltraCircuitBuilder>>&,
    const std::vector<stdlib::field_t<UltraCircuitBuilder>>&,
    const stdlib::field_t<UltraCircuitBuilder>&);
 
template void create_dummy_ecdsa_constraint<stdlib::secp256r1<UltraCircuitBuilder>>(
    UltraCircuitBuilder&,
    const std::vector<stdlib::field_t<UltraCircuitBuilder>>&,
    const std::vector<stdlib::field_t<UltraCircuitBuilder>>&,
    const std::vector<stdlib::field_t<UltraCircuitBuilder>>&,
    const std::vector<stdlib::field_t<UltraCircuitBuilder>>&,
    const std::vector<stdlib::field_t<UltraCircuitBuilder>>&,
    const stdlib::field_t<UltraCircuitBuilder>&);
 
} // namespace acir_format