ecdsa_impl.hpp

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: }
// =====================
 
#pragma once
 
#include "barretenberg/crypto/sha256/sha256.hpp"
#include "barretenberg/ecc/groups/precomputed_generators_secp256r1_impl.hpp"
#include "barretenberg/stdlib/encryption/ecdsa/ecdsa.hpp"
#include "barretenberg/stdlib/primitives/curves/secp256k1.hpp"
 
namespace bb::stdlib {
 
namespace {
auto& engine = numeric::get_debug_randomness();
}
 
template <typename Builder, typename Curve, typename Fq, typename Fr, typename G1>
bool_t<Builder> ecdsa_verify_signature(const stdlib::byte_array<Builder>& hashed_message,
                                       const G1& public_key,
                                       const ecdsa_signature<Builder>& sig)
{
    BB_ASSERT_EQ(Fr::modulus.get_msb() + 1, 256UL, "The implementation assumes that the bit-length of Fr is 256 bits.");
 
    // Fetch the context
    Builder* builder = hashed_message.get_context();
    builder = validate_context(builder, public_key.get_context());
    builder = validate_context(builder, sig.get_context());
    BB_ASSERT_EQ(builder != nullptr, true, "At least one of the inputs should be non-constant.");
 
    // Turn the hashed message into an element of Fr
    // Note that we don't need to trim the length of the output of the hash function because the bit length of the
    // scalar fields we work with (secp256k1, secp256r1) is equal to 256.
    Fr z(hashed_message);
 
    // Step 1.
    public_key.assert_coordinates_in_field(
        "ECDSA input validation: coordinate(s) of the public key bigger than the base field modulus."); // x < q, y < q
 
    // Step 2.
    public_key.validate_on_curve("ECDSA input validation: the public key is not a point on the elliptic curve.");
 
    // Step 3.
    public_key.is_point_at_infinity().assert_equal(bool_t<Builder>(false),
                                                   "ECDSA input validation: the public key is the point at infinity.");
 
    // Step 4.
    Fr r(sig.r);
    r.assert_is_in_field("ECDSA input validation: the r component of the signature is bigger than the order of the "
                         "elliptic curve.");                                                                // r < n
    r.assert_is_not_equal(Fr::zero(), "ECDSA input validation: the r component of the signature is zero."); // 0 < r
 
    // Step 5.
    Fr s(sig.s);
    s.assert_less_than(
        (Fr::modulus + 1) / 2,
        "ECDSA input validation: the s component of the signature is bigger than (Fr::modulus + 1)/2."); // s < (n+1)/2
    s.assert_is_not_equal(Fr::zero(), "ECDSA input validation: the s component of the signature is zero."); // 0 < s
 
    // Step 6.
    Fr u1 = z.div_without_denominator_check(s);
    Fr u2 = r.div_without_denominator_check(s);
 
    G1 result;
    if constexpr (Curve::type == bb::CurveType::SECP256K1) {
        result = G1::secp256k1_ecdsa_mul(public_key, u1, u2);
    } else {
        // This error comes from the lookup tables used in batch_mul. We could get rid of it by setting with_edgecase =
        // true. However, this would increase the gate count, and it would handle a case that should not appear in
        // general: someone using plus or minus the generator as a public key.
        if ((public_key.get_value().x == Curve::g1::affine_one.x) && (!builder->failed())) {
            builder->failure("ECDSA input validation: the public key is equal to plus or minus the generator point.");
        }
        result = G1::batch_mul({ G1::one(builder), public_key }, { u1, u2 });
    }
 
    // Step 7.
    auto result_is_infinity = result.is_point_at_infinity();
    result_is_infinity.assert_equal(
        bool_t<Builder>(false), "ECDSA validation: the result of the batch multiplication is the point at infinity.");
 
    // Step 8.
    // We reduce result.x() to 2^s, where s is the smallest s.t. 2^s > q. It is cheap in terms of constraints, and
    // avoids possible edge cases
    result.x().reduce_mod_target_modulus();
 
    // Transfer Fq value result.x() to Fr (this is just moving from a C++ class to another)
    Fr result_x_mod_r = Fr::unsafe_construct_from_limbs(result.x().binary_basis_limbs[0].element,
                                                        result.x().binary_basis_limbs[1].element,
                                                        result.x().binary_basis_limbs[2].element,
                                                        result.x().binary_basis_limbs[3].element);
    // Copy maximum limb values from Fq to Fr: this is needed by the subtraction happening in the == operator
    for (size_t idx = 0; idx < 4; idx++) {
        result_x_mod_r.binary_basis_limbs[idx].maximum_value = result.x().binary_basis_limbs[idx].maximum_value;
    }
 
    // Check result.x() = r mod n AND result is not point at infinity
    bool_t<Builder> x_matches = result_x_mod_r == r;
    bool_t<Builder> is_not_infinity = !result_is_infinity;
    bool_t<Builder> is_signature_valid = x_matches && is_not_infinity;
 
    // Logging
    if (is_signature_valid.get_value()) {
        vinfo("ECDSA signature verification succeeded.");
    } else {
        vinfo("ECDSA signature verification failed");
    }
 
    return is_signature_valid;
}
 
template <typename Builder> void generate_ecdsa_verification_test_circuit(Builder& builder, size_t num_iterations)
{
    using Curve = stdlib::secp256k1<Builder>;
 
    // Native types
    using FrNative = typename Curve::fr;
    using FqNative = typename Curve::fq;
    using G1Native = typename Curve::g1;
 
    // Stdlib types
    using Fr = typename Curve::bigfr_ct;
    using Fq = typename Curve::fq_ct;
    using G1 = typename Curve::g1_bigfr_ct;
 
    std::string message_string = "Instructions unclear, ask again later.";
 
    crypto::ecdsa_key_pair<FrNative, G1Native> account;
    for (size_t i = 0; i < num_iterations; i++) {
        // Generate unique signature for each iteration
        account.private_key = FrNative::random_element(&engine);
        account.public_key = G1Native::one * account.private_key;
 
        crypto::ecdsa_signature signature =
            crypto::ecdsa_construct_signature<crypto::Sha256Hasher, FqNative, FrNative, G1Native>(message_string,
                                                                                                  account);
 
        bool native_verification = crypto::ecdsa_verify_signature<crypto::Sha256Hasher, FqNative, FrNative, G1Native>(
            message_string, account.public_key, signature);
        BB_ASSERT_EQ(native_verification, true, "Native ECDSA verification failed while generating test circuit.");
 
        std::vector<uint8_t> rr(signature.r.begin(), signature.r.end());
        std::vector<uint8_t> ss(signature.s.begin(), signature.s.end());
 
        G1 public_key = G1::from_witness(&builder, account.public_key);
 
        ecdsa_signature<Builder> sig{ byte_array<Builder>(&builder, rr), byte_array<Builder>(&builder, ss) };
 
        // Compute H(m) natively and pass as witness (mirrors ACIR which takes pre-hashed message)
        auto hash_arr = crypto::sha256(std::vector<uint8_t>(message_string.begin(), message_string.end()));
        stdlib::byte_array<Builder> hashed_message(&builder, std::vector<uint8_t>(hash_arr.begin(), hash_arr.end()));
 
        // Verify ecdsa signature
        bool_t<Builder> result =
            stdlib::ecdsa_verify_signature<Builder, Curve, Fq, Fr, G1>(hashed_message, public_key, sig);
        result.assert_equal(bool_t<Builder>(true));
    }
}
 
} // namespace bb::stdlib