Support Multisig in Sui

[joyqvq]

Motivation

Currently, Sui supports single signature for executing transaction with supported scheme Ed25519, Secp256k1, Secp256r1. This RFC provides standard for signatures format for multisig and address encoding. This benefits wallet providers and custody applications with more complex authorization path for transactions with native multisig support.

Goals

• Support k-of-n multisig transaction verification in Sui. Each signature can use any single signature scheme (Ed25519, Secp256k1, Secp256r1).
• Basic Client CLI and SDK support:
  • Combine single signatures into one multisig.
  • Generate multisig address. Each public key can have its own defined weight.

Non-Goals

• Support account abstraction or any generic authenticator on chain.
• Allow BLS to participate in multisig.
• Allow add/remove participating parties, change threshold, adjust weights.
• Dynamically change the max signers for the multisig.

Current Implementation (for Single Signature)

• User submits a serialized signature scheme || signature || pubkey via [endpoint](https://docs.sui.io/sui-jsonrpc#sui_executeTransactionSerializedSig)
• Sui is defined with trait SuiSignature that assumes encoding scheme || sig || pubkey

#[enum_dispatch]
pub enum Signature {
    Ed25519SuiSignature,
    Secp256k1SuiSignature,
    Secp256r1SuiSignature,
}

pub struct Ed25519SuiSignature(
    #[schemars(with = "Base64")]
    #[serde_as(as = "Readable<Base64, Bytes>")]
    [u8; Ed25519PublicKey::LENGTH + Ed25519Signature::LENGTH + 1],
);

• Authority verifies using trait

    fn verify_secure<T>(&self, value: &IntentMessage<T>, author: SuiAddress) -> Result<(), SuiError>
    where
        T: Serialize,
    {
        let message = bcs::to_bytes(&value).expect("Message serialization should not fail");
        let (sig, pk) = &self.get_verification_inputs(author)?;
        pk.verify(&message[..], sig)
            .map_err(|e| SuiError::InvalidSignature {
                error: format!("{}", e),
            })
    }

Proposal: Mixed-Signing-Scheme Weighted Multisig

We want to support multisig that individual signature uses different signing schemes where each signature corresponds to a weight.

Example: A 2-of-3 multisig can have one signature is provided as Secp256r1 (issued from the user device enclave) and another one signature is provided as Ed25519 issued from a trusted custodian.

Client Side

• User submits a serialized MultiSignature, consisting of signatures and public keys, the MultiPublicKey of all the participating public keys and its weights, the threshold.

pub struct MultiSignature {
    /// The plain signature encoded with signature scheme.
    sigs: Vec<CompressedSignature>,
    /// A bitmap that indicates the position of which public key the signature should be authenticated with.
    bitmap: RoaringBitmap,
    /// The public key encoded with each public key with its signature scheme used along with the corresponding weight.
    multi_pk: MultiPublicKey,
}

pub struct MultiPublicKey {
    /// A list of public key and its corresponding weight.
    pk_map: Vec<(PublicKey, WeightUnit)>,
    /// If the total weight of the public keys corresponding to verified signatures is larger than threshold, the multisig is verified.
    threshold: ThresholdUnit,
}

The types are defined as:

pub type WeightUnit = u8;
pub type ThresholdUnit = u16;
pub const MAX_SIGNER_IN_MULTISIG: usize = 10; // Hardcoded for now, a value can be considered to increase in the future

The verification algorithm

• If the number of public keys is larger than 10, fail to verify.
• Check if len(pks) > len(sigs) > k > 0 If not, fail to verify.
• Check if the sender address field is the hash of derived from public keys (defined from below). If not, fail to verify.
• Keep track of the total sum.
• Iterate through each signature flag_i || sig_i use bitmap to find its verifying public key i If pk_i.verify(sig_i, msg) passes, add weight to sum.
• If sum of weight larger than threshold, execute transaction.

Multisig Address

A k-of-n Multisig address is the first 20 bytes of SHA3-256 of k || pk_1 || weight_1 || ... || pk_n || weight_n of all participating public keys and its weight.

impl From<MultiPublicKey> for SuiAddress {
    fn from(multi_pk: MultiPublicKey) -> Self {
        let mut hasher = Sha3_256::default();
        hasher.update(multi_pk.threshold().to_le_bytes());
        multi_pk.pubkeys().iter().for_each(|(pk, w)| {
            hasher.update(pk.as_ref());
            hasher.update(w.to_le_bytes());
        });
        let g_arr = hasher.finalize();

        let mut res = [0u8; SUI_ADDRESS_LENGTH];
        res.copy_from_slice(&AsRef::<[u8]>::as_ref(&g_arr)[..SUI_ADDRESS_LENGTH]);
        SuiAddress(res)
    }
}

Serialization

[struct MultiSignature] is serialized as the multisig flag (0x03) concat with the bcs serialized bytes of [struct MultiSignature] i.e. flag || bcs_bytes(multisig).

The serialization for [enum Signature] (i.e. single signature) is unchanged, ported from ToFromBytes impl for enum Signature as flag || sig || pk.

let signature = GenericSignature::from_bytes(encoded_bytes)?;
let txn = Transaction::from_generic_sig_data(tx_data, Intent::default(), signature);

Rationale Due to the incompatibility of [enum Signature] (which dispatches a trait that assumes signature and pubkey bytes for verification), we add a wrapper enum where member can just implement a lightweight [trait AuthenticatorTrait]. This way Multisig (and future novel Authenticators) can implement its own verify without worrying about trait SuiSignature and trait SuiSignatureInner that are specific to single signature verification.

#[enum_dispatch]
pub trait AuthenticatorTrait {
    fn verify_secure_generic<T>(&self,value: &IntentMessage<T>,author: SuiAddress) -> Result<(), SuiError> where T: Serialize;
}

#[enum_dispatch(AuthenticatorTrait)]
pub enum GenericSignature {
    MultiSignature,
    Signature,
}

CLI Utility

1. Generate multisig address with all public keys and their weights, along with the threshold.

target/debug/sui keytool multi-sig-address 
  --pks AgJTS++o+mJKX63fZ3UCNfijUFitIRm6clhno8rnp+XEJw== 
     AGVvsLi5Q5mXUQf0ljzUn0iA3nLogSzLO3JMkPiuragt 
     AO6fjfh1RYv+NZq/BbtPhx9ZaSlD34nCzjFYGyWrhf1s 
  --weights 1 2 3 
  --threshold 3

2. Sign with selected key in sui.keystore to create partial signatures. This already exists and no different from single signature signing.

sui keytool sign --data=$RAWTX --address=$ADDRESS

3. Combine signatures to a signed transaction

target/debug/sui keytool multi-sig-combine-partial-sig 
--pks AgJTS++o+mJKX63fZ3UCNfijUFitIRm6clhno8rnp+XEJw== 
          AGVvsLi5Q5mXUQf0ljzUn0iA3nLogSzLO3JMkPiuragt 
          AO6fjfh1RYv+NZq/BbtPhx9ZaSlD34nCzjFYGyWrhf1s 
--weights 1 2 3 
--threshold 3 
--sigs AjkAc6TuY7i8SnJuC4Z/7ZU7zUn9FlOUOUc9rVRq6s3GYhDlHuSKoSwvOOPHGq0rN0VnwtveMylmpahjLiMfcL8AAlNL76j6Ykpfrd9ndQI1+KNQWK0hGbpyWGejyuen5cQn
AOo7dgCi6eQ4Oc9C8w2o7QbIGg4UURNUH+Q9npL4jXf7/m13ATRRHQVsv1VhnKT8maog0PhpNMSXuAdvN+GNBAtlb7C4uUOZl1EH9JY81J9IgN5y6IEsyztyTJD4rq2oLQ==

4. Execute a multisig transaction. This is no different from existing execute_transactionSerializedSig because it can understand the generic signature for both multisig and single sig and runs verify_secure_generic.

target/debug/sui client execute-signed-tx 
--tx-bytes AAMyrDFLZaPr800/r0UrCcHSWuK0TwBR2TUgCOvdvTvCFjK/tLeXwre+wHT35cbYTvMbfsLrFbrtUBv8DGw4AgAAAAAAAAAgI8C4QJ833DStV/181e9NEUHmHz+4FaVMhHU59s/101oBAAAAAAAAAOgDAAAAAAAA 
--signature AwICQTkAc6TuY7i8SnJuC4Z/7ZU7zUn9FlOUOUc9rVRq6s3GYhDlHuSKoSwvOOPHGq0rN0VnwtveMylmpahjLiMfcL8AAEDqO3YAounkODnPQvMNqO0GyBoOFFETVB/kPZ6S+I13+/5tdwE0UR0FbL9VYZyk/JmqIND4aTTEl7gHbzfhjQQLFDowAAABAAAAAAABABAAAAAAAAEAAzBBZ0pUUysrbyttSktYNjNmWjNVQ05maWpVRml0SVJtNmNsaG5vOHJucCtYRUp3PT0BLEFHVnZzTGk1UTVtWFVRZjBsanpVbjBpQTNuTG9nU3pMTzNKTWtQaXVyYWd0AixBTzZmamZoMVJZditOWnEvQmJ0UGh4OVphU2xEMzRuQ3pqRllHeVdyaGYxcwMDAA==

Improvements

• Instead of sending all pubkeys when combining signatures, store all pubkeys in an immutable object onchain as a state. This is considered to save payload, but veto-ed for now to avoid a stateful implementation.

• Consider Account Abstraction for new authentication schemes such that verify is ran via the MoveVM. So new authentication schemes can be implemented on-chain. This way we can enable updates to a multisig participating parties (add/remove pubkeys, update weights and threshold etc). We can also meters gas cost for verification accurately. This is out of scope here and deserves a design doc by its own in the future.

• Add typescript support same as the CLI.

• With this implementation the signature length and verification time grows linearly with the number of users in the subgroup.

Main implementation: https://github.com/MystenLabs/sui/pull/7110

[JackyWYX]

Two questions considering the design:

1. Where does the max number of public keys (10) comes from? Will this effect specific use cases where more than 10 signatures are engaged? E.g. DAO with multiple operators operating on a DAO treasury fund.
2. How does the current implementation support update of the owner permissions? E.g. Add/remove owner, change threshold, adjust weights?

[joyqvq]

Two questions considering the design:

1. Where does the max number of public keys (10) comes from? Will this effect specific use cases where more than 10 signatures are engaged? E.g. DAO with multiple operators operating on a DAO treasury fund.
2. How does the current implementation support update of the owner permissions? E.g. Add/remove owner, change threshold, adjust weights?

Addressed them in the proposal - we will start with 10 as the max number of participating pubkeys and will be easy to increase in the future. This implementation does not allow updating since it is pinned to the address. If we consider account abstraction in the future, we will share a separate design.

[elonkusk]

Dear team! I see this feature is supported on CLI. But how about Typescript SDK ? I can't see it! Many thanks!