multisig.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 <algorithm>
#include <cstdint>
#include <numeric>
#include <optional>
#include <utility>
#include <vector>
 
#include "barretenberg/serialize/msgpack.hpp"
 
#include "proof_of_possession.hpp"
#include "schnorr.hpp"
 
namespace bb::crypto {
 
template <typename G1, typename HashRegNon, typename HashSig = Blake2sHasher> class schnorr_multisig {
 
    // ensure that a different hash function is used for signature and proof of possession/nonce.
    // we can apply domain separation for HashRegNon but not for HashSig, so this ensures all hash functions
    // are modeled as different random oracles.
    static_assert(!std::is_same_v<HashRegNon, HashSig>);
 
  public:
    using Fq = typename G1::Fq;
    using Fr = typename G1::Fr;
    using affine_element = typename G1::affine_element;
    using element = typename G1::element;
    using key_pair = crypto::schnorr_key_pair<Fr, G1>;
 
    struct MultiSigPublicKey {
        typedef uint8_t const* in_buf;
        typedef uint8_t const* vec_in_buf;
        typedef uint8_t* out_buf;
        typedef uint8_t** vec_out_buf;
 
        affine_element public_key = G1::affine_point_at_infinity;
        // proof of knowledge of the secret_key for public_key
        SchnorrProofOfPossession<G1, HashRegNon> proof_of_possession;
 
        // For serialization, update with any new fields
        MSGPACK_FIELDS(public_key, proof_of_possession);
        // restore default constructor to enable deserialization
        MultiSigPublicKey() = default;
        // create a MultiSigPublicKey with a proof of possession associated with public_key of account
        MultiSigPublicKey(const key_pair& account)
            : public_key(account.public_key)
            , proof_of_possession(account)
        {}
        // Needed to appease MSGPACK_FIELDS
        MultiSigPublicKey(const affine_element& public_key,
                          const SchnorrProofOfPossession<G1, HashRegNon>& proof_of_possession)
            : public_key(public_key)
            , proof_of_possession(proof_of_possession)
        {}
    };
 
    struct RoundOnePrivateOutput {
        using in_buf = const uint8_t*;
        using out_buf = uint8_t*;
 
        Fr r;
        Fr s;
        // For serialization, update with any new fields
        MSGPACK_FIELDS(r, s);
    };
 
    struct RoundOnePublicOutput {
        using in_buf = const uint8_t*;
        using vec_in_buf = const uint8_t*;
        using out_buf = uint8_t*;
        using vec_out_buf = uint8_t**;
 
        // R = r⋅G
        affine_element R;
        // S = s⋅G
        affine_element S;
        // For serialization, update with any new fields
        MSGPACK_FIELDS(R, S);
        // for std::sort
        bool operator<(const RoundOnePublicOutput& other) const
        {
            return ((R < other.R) || ((R == other.R) && S < (other.S)));
        }
 
        bool operator==(const RoundOnePublicOutput& other) const { return (R == other.R) && (S == other.S); }
    };
    // corresponds to z = r + as - ex,
    using RoundTwoPublicOutput = Fr;
 
  private:
    static bool valid_round1_nonces(const std::vector<RoundOnePublicOutput>& round1_public_outputs)
    {
        for (size_t i = 0; i < round1_public_outputs.size(); ++i) {
            auto& [R_user, S_user] = round1_public_outputs[i];
            if (!R_user.on_curve() || R_user.is_point_at_infinity()) {
                info("Round 1 commitments contains invalid R at index ", i);
                return false;
            }
            if (!S_user.on_curve() || S_user.is_point_at_infinity()) {
                info("Round 1 commitments contains invalid S at index ", i);
                return false;
            }
        }
        if (auto duplicated = duplicated_indices(round1_public_outputs); duplicated.size() > 0) {
            info("Round 1 commitments contains duplicate values at indices ", duplicated);
            return false;
        }
        return true;
    }
 
    static Fr generate_nonce_challenge(const std::string& message,
                                       const affine_element& aggregate_pubkey,
                                       const std::vector<RoundOnePublicOutput>& round_1_nonces)
    {
        // Domain separation for H_non
        const std::string domain_separator_nonce("h_nonce");
 
        // compute nonce challenge
        // H('domain_separator_nonce', G, X, "m_start", m.size(), m, "m_end", {(R1, S1), ..., (Rn, Sn)})
        std::vector<uint8_t> nonce_challenge_buffer;
        // write domain separator
        std::copy(
            domain_separator_nonce.begin(), domain_separator_nonce.end(), std::back_inserter(nonce_challenge_buffer));
 
        // write the group generator
        write(nonce_challenge_buffer, G1::affine_one);
 
        // write X
        write(nonce_challenge_buffer, aggregate_pubkey);
 
        // we slightly deviate from the protocol when including 'm', since the length of 'm' is variable
        // by writing a prefix and a suffix, we prevent the message from being interpreted as coming from a different
        // session.
 
        // write "m_start"
        const std::string m_start = "m_start";
        std::copy(m_start.begin(), m_start.end(), std::back_inserter(nonce_challenge_buffer));
        // write m.size()
        write(nonce_challenge_buffer, static_cast<uint32_t>(message.size()));
        // write message
        std::copy(message.begin(), message.end(), std::back_inserter(nonce_challenge_buffer));
        // write "m_end"
        const std::string m_end = "m_end";
        std::copy(m_end.begin(), m_end.end(), std::back_inserter(nonce_challenge_buffer));
 
        // write  {(R1, S1), ..., (Rn, Sn)}
        for (const auto& nonce : round_1_nonces) {
            write(nonce_challenge_buffer, nonce.R);
            write(nonce_challenge_buffer, nonce.S);
        }
 
        // uses the different hash function for proper domain separation
        auto nonce_challenge_raw = HashRegNon::hash(nonce_challenge_buffer);
        // this results in a slight bias
        Fr nonce_challenge = Fr::serialize_from_buffer(&nonce_challenge_raw[0]);
        return nonce_challenge;
    }
 
    static affine_element construct_multisig_nonce(const Fr& a, const std::vector<RoundOnePublicOutput>& round_1_nonces)
    {
        element R_sum = round_1_nonces[0].R;
        element S_sum = round_1_nonces[0].S;
        for (size_t i = 1; i < round_1_nonces.size(); ++i) {
            const auto& [R, S] = round_1_nonces[i];
            R_sum += R;
            S_sum += S;
        }
        affine_element R(R_sum + S_sum * a);
        return R;
    }
 
    template <typename T> static std::vector<size_t> duplicated_indices(const std::vector<T>& input)
    {
        const size_t num_inputs = input.size();
        // indices = [0,1,..., num_inputs-1]
        std::vector<size_t> indices(num_inputs);
        std::iota(indices.begin(), indices.end(), 0);
 
        // sort indices according to input.
        // input[indices[i-1]] <= input[indices[i]]
        std::sort(indices.begin(), indices.end(), [&](size_t a, size_t b) { return input[a] < input[b]; });
 
        // This loop will include multiple copies of the same index if an element appears more than twice.
        std::vector<size_t> duplicates;
        for (size_t i = 1; i < num_inputs; ++i) {
            const size_t idx1 = indices[i - 1];
            const size_t idx2 = indices[i];
            if (input[idx1] == input[idx2]) {
                duplicates.push_back(idx1);
                duplicates.push_back(idx2);
            }
        }
        return duplicates;
    }
 
  public:
    static std::optional<affine_element> validate_and_combine_signer_pubkeys(
        const std::vector<MultiSigPublicKey>& signer_pubkeys)
    {
        std::vector<affine_element> points;
        for (const auto& [public_key, proof_of_possession] : signer_pubkeys) {
            points.push_back(public_key);
        }
 
        if (auto duplicated = duplicated_indices(points); duplicated.size() > 0) {
            info("Duplicated public keys at indices ", duplicated);
            return std::nullopt;
        }
 
        element aggregate_pubkey_jac = G1::point_at_infinity;
        for (size_t i = 0; i < signer_pubkeys.size(); ++i) {
            const auto& [public_key, proof_of_possession] = signer_pubkeys[i];
            if (!public_key.on_curve() || public_key.is_point_at_infinity()) {
                info("Multisig signer pubkey not a valid point at index ", i);
                return std::nullopt;
            }
            if (!proof_of_possession.verify(public_key)) {
                info("Multisig proof of posession invalid at index ", i);
                return std::nullopt;
            }
            aggregate_pubkey_jac += public_key;
        }
 
        // This would prevent accidentally creating an aggregate key for the point at inifinity,
        // with the trivial secret key.
        // While it shouldn't happen, it is a cheap check.
        affine_element aggregate_pubkey(aggregate_pubkey_jac);
        if (aggregate_pubkey.is_point_at_infinity()) {
            info("Multisig aggregate public key is invalid");
            return std::nullopt;
        }
        return aggregate_pubkey;
    }
 
    static std::pair<RoundOnePublicOutput, RoundOnePrivateOutput> construct_signature_round_1()
    {
        // r_user ← 𝔽
        // TODO: securely erase `r_user`
        Fr r_user = Fr::random_element();
        // R_user ← r_user⋅G
        affine_element R_user = G1::one * r_user;
 
        // s_user ← 𝔽
        // TODO: securely erase `s_user`
        Fr s_user = Fr::random_element();
        // S_user ← s_user⋅G
        affine_element S_user = G1::one * s_user;
 
        RoundOnePublicOutput pubOut{ R_user, S_user };
        RoundOnePrivateOutput privOut{ r_user, s_user };
        return { pubOut, privOut };
    }
 
    static std::optional<RoundTwoPublicOutput> construct_signature_round_2(
        const std::string& message,
        const key_pair& signer,
        const RoundOnePrivateOutput& signer_round_1_private_output,
        const std::vector<MultiSigPublicKey>& signer_pubkeys,
        const std::vector<RoundOnePublicOutput>& round_1_nonces)
    {
        const size_t num_signers = signer_pubkeys.size();
        if (round_1_nonces.size() != num_signers) {
            info("Multisig mismatch round_1_nonces and signers");
            return std::nullopt;
        }
 
        // check that round_1_nonces does not contain duplicates and that all points are valid
        if (!valid_round1_nonces(round_1_nonces)) {
            return std::nullopt;
        }
 
        // compute aggregate key X = X_1 + ... + X_n
        auto aggregate_pubkey = validate_and_combine_signer_pubkeys(signer_pubkeys);
        if (!aggregate_pubkey.has_value()) {
            // previous call has failed
            return std::nullopt;
        }
 
        // compute nonce challenge H_non(G, X, "m_start", m, "m_end", {(R1, S1), ..., (Rn, Sn)})
        Fr a = generate_nonce_challenge(message, *aggregate_pubkey, round_1_nonces);
 
        // compute aggregate nonce R = R1 + ... + Rn + S1 * a + ... + Sn * a
        affine_element R = construct_multisig_nonce(a, round_1_nonces);
 
        // Now we have the multisig nonce, compute schnorr challenge e (termed `c` in the speedyMuSig paper)
        auto e_buf = schnorr_generate_challenge<HashSig, G1>(message, *aggregate_pubkey, R);
        Fr e = Fr::serialize_from_buffer(&e_buf[0]);
 
        // output of round 2 is z
        Fr z = signer_round_1_private_output.r + signer_round_1_private_output.s * a - signer.private_key * e;
        return z;
    }
 
    static std::optional<schnorr_signature> combine_signatures(
        const std::string& message,
        const std::vector<MultiSigPublicKey>& signer_pubkeys,
        const std::vector<RoundOnePublicOutput>& round_1_nonces,
        const std::vector<RoundTwoPublicOutput>& round_2_signature_shares)
    {
        const size_t num_signers = signer_pubkeys.size();
        if (round_1_nonces.size() != num_signers) {
            info("Invalid number of round1 messages");
            return std::nullopt;
        }
        if (round_2_signature_shares.size() != num_signers) {
            info("Invalid number of round2 messages");
            return std::nullopt;
        }
        if (!valid_round1_nonces(round_1_nonces)) {
            return std::nullopt;
        }
 
        // compute aggregate key X = X_1 + ... + X_n
        auto aggregate_pubkey = validate_and_combine_signer_pubkeys(signer_pubkeys);
        if (!aggregate_pubkey.has_value()) {
            // previous call has failed
            return std::nullopt;
        }
 
        // compute nonce challenge H(X, m, {(R1, S1), ..., (Rn, Sn)})
        Fr a = generate_nonce_challenge(message, *aggregate_pubkey, round_1_nonces);
 
        // compute aggregate nonce R = R1 + ... + Rn + S1 * a + ... + Sn * a
        affine_element R = construct_multisig_nonce(a, round_1_nonces);
 
        auto e_buf = schnorr_generate_challenge<HashSig, G1>(message, *aggregate_pubkey, R);
 
        schnorr_signature sig;
        // copy e as its raw bit representation (without modular reduction)
        std::copy(e_buf.begin(), e_buf.end(), sig.e.begin());
 
        Fr s = 0;
        for (auto& z : round_2_signature_shares) {
            s += z;
        }
        // write s, which will always produce an integer < r
        Fr::serialize_to_buffer(s, &sig.s[0]);
 
        // verify the final signature before returning
        if (!schnorr_verify_signature<HashSig, Fq, Fr, G1>(message, *aggregate_pubkey, sig)) {
            return std::nullopt;
        }
 
        return sig;
    }
};
} // namespace bb::crypto