aptos_sdk/crypto/

multi_key.rs

//! `MultiKey` signature scheme implementation.
//!
//! `MultiKey` enables M-of-N threshold signatures with mixed key types.
//! Unlike `MultiEd25519`, each key can be a different signature scheme
//! (Ed25519, Secp256k1, Secp256r1, etc.).

use crate::error::{AptosError, AptosResult};
use serde::{Deserialize, Serialize};
use std::fmt;

/// Maximum number of keys in a multi-key account.
pub const MAX_NUM_OF_KEYS: usize = 32;

// Compile-time assertion: MAX_NUM_OF_KEYS must fit in u8 for bitmap operations
const _: () = assert!(MAX_NUM_OF_KEYS <= u8::MAX as usize);

/// Minimum threshold (at least 1 signature required).
pub const MIN_THRESHOLD: u8 = 1;

/// Supported signature schemes for multi-key.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[repr(u8)]
pub enum AnyPublicKeyVariant {
    /// Ed25519 public key.
    Ed25519 = 0,
    /// Secp256k1 ECDSA public key.
    Secp256k1 = 1,
    /// Secp256r1 (P-256) ECDSA public key.
    Secp256r1 = 2,
    /// Keyless public key.
    Keyless = 3,
}

impl AnyPublicKeyVariant {
    /// Get the variant from a byte.
    ///
    /// # Errors
    ///
    /// Returns [`AptosError::InvalidPublicKey`] if the byte value is not a valid variant (0-3).
    pub fn from_byte(byte: u8) -> AptosResult<Self> {
        match byte {
            0 => Ok(Self::Ed25519),
            1 => Ok(Self::Secp256k1),
            2 => Ok(Self::Secp256r1),
            3 => Ok(Self::Keyless),
            _ => Err(AptosError::InvalidPublicKey(format!(
                "unknown public key variant: {byte}"
            ))),
        }
    }

    /// Get the byte representation.
    pub fn as_byte(&self) -> u8 {
        *self as u8
    }
}

/// A public key that can be any supported signature scheme.
#[derive(Clone, PartialEq, Eq)]
pub struct AnyPublicKey {
    /// The signature scheme variant.
    pub variant: AnyPublicKeyVariant,
    /// The raw public key bytes.
    pub bytes: Vec<u8>,
}

impl AnyPublicKey {
    /// Creates a new `AnyPublicKey`.
    pub fn new(variant: AnyPublicKeyVariant, bytes: Vec<u8>) -> Self {
        Self { variant, bytes }
    }

    /// Creates an Ed25519 public key.
    #[cfg(feature = "ed25519")]
    pub fn ed25519(public_key: &crate::crypto::Ed25519PublicKey) -> Self {
        Self {
            variant: AnyPublicKeyVariant::Ed25519,
            bytes: public_key.to_bytes().to_vec(),
        }
    }

    /// Creates a Secp256k1 public key.
    /// Uses the 65-byte SEC1 uncompressed encoding so the chain's
    /// `bcs::to_bytes(&AnyPublicKey::Secp256k1Ecdsa)` re-serialisation produces
    /// the same bytes during auth-key derivation. The SDK and chain therefore
    /// agree on the address.
    #[cfg(feature = "secp256k1")]
    pub fn secp256k1(public_key: &crate::crypto::Secp256k1PublicKey) -> Self {
        Self {
            variant: AnyPublicKeyVariant::Secp256k1,
            bytes: public_key.to_uncompressed_bytes(),
        }
    }

    /// Creates a Secp256r1 public key.
    /// Uses 65-byte SEC1 uncompressed encoding (see `secp256k1` for rationale).
    #[cfg(feature = "secp256r1")]
    pub fn secp256r1(public_key: &crate::crypto::Secp256r1PublicKey) -> Self {
        Self {
            variant: AnyPublicKeyVariant::Secp256r1,
            bytes: public_key.to_uncompressed_bytes(),
        }
    }

    /// Serializes to BCS format: `variant_byte` || ULEB128(length) || bytes
    ///
    /// This is the correct BCS serialization format for `AnyPublicKey` used
    /// in authentication key derivation: `SHA3-256(BCS(AnyPublicKey) || scheme_id)`
    pub fn to_bcs_bytes(&self) -> Vec<u8> {
        let mut result = Vec::with_capacity(1 + 1 + self.bytes.len());
        result.push(self.variant.as_byte());
        // BCS uses ULEB128 for vector lengths
        result.extend(uleb128_encode(self.bytes.len()));
        result.extend_from_slice(&self.bytes);
        result
    }

    /// Parses BCS `AnyPublicKey` bytes (`variant` || `ULEB128(len)` || raw key bytes).
    ///
    /// # Errors
    ///
    /// Returns [`AptosError::InvalidPublicKey`] if the slice is empty, the variant byte is
    /// unknown, the length prefix is malformed, the payload is truncated, or trailing bytes
    /// remain after the declared key bytes.
    pub fn from_bcs_bytes(bytes: &[u8]) -> AptosResult<Self> {
        if bytes.is_empty() {
            return Err(AptosError::InvalidPublicKey(
                "AnyPublicKey BCS empty".into(),
            ));
        }
        let variant = AnyPublicKeyVariant::from_byte(bytes[0])?;
        let (len, len_bytes) = uleb128_decode(&bytes[1..]).ok_or_else(|| {
            AptosError::InvalidPublicKey("AnyPublicKey BCS invalid length prefix".into())
        })?;
        let start = 1 + len_bytes;
        let end = start.checked_add(len).ok_or_else(|| {
            AptosError::InvalidPublicKey("AnyPublicKey BCS length overflow".into())
        })?;
        if end > bytes.len() {
            return Err(AptosError::InvalidPublicKey(
                "AnyPublicKey BCS truncated payload".into(),
            ));
        }
        if end != bytes.len() {
            return Err(AptosError::InvalidPublicKey(
                "AnyPublicKey BCS trailing bytes".into(),
            ));
        }
        Ok(Self::new(variant, bytes[start..end].to_vec()))
    }

    /// Verifies a signature against a message.
    ///
    /// # Errors
    ///
    /// This function will return an error if:
    /// - The signature variant doesn't match the public key variant
    /// - The public key bytes are invalid for the variant
    /// - The signature bytes are invalid for the variant
    /// - Signature verification fails
    /// - Verification is not supported for the variant
    #[allow(unused_variables)]
    pub fn verify(&self, message: &[u8], signature: &AnySignature) -> AptosResult<()> {
        if signature.variant != self.variant {
            return Err(AptosError::InvalidSignature(format!(
                "signature variant {:?} doesn't match public key variant {:?}",
                signature.variant, self.variant
            )));
        }

        match self.variant {
            #[cfg(feature = "ed25519")]
            AnyPublicKeyVariant::Ed25519 => {
                let pk = crate::crypto::Ed25519PublicKey::from_bytes(&self.bytes)?;
                let sig = crate::crypto::Ed25519Signature::from_bytes(&signature.bytes)?;
                pk.verify(message, &sig)
            }
            #[cfg(feature = "secp256k1")]
            AnyPublicKeyVariant::Secp256k1 => {
                // Public key can be either compressed (33 bytes) or uncompressed (65 bytes)
                let pk = crate::crypto::Secp256k1PublicKey::from_bytes(&self.bytes)?;
                let sig = crate::crypto::Secp256k1Signature::from_bytes(&signature.bytes)?;
                pk.verify(message, &sig)
            }
            #[cfg(feature = "secp256r1")]
            AnyPublicKeyVariant::Secp256r1 => {
                // Public key can be either compressed (33 bytes) or uncompressed (65 bytes)
                let pk = crate::crypto::Secp256r1PublicKey::from_bytes(&self.bytes)?;
                let sig = crate::crypto::Secp256r1Signature::from_bytes(&signature.bytes)?;
                pk.verify(message, &sig)
            }
            #[allow(unreachable_patterns)]
            _ => Err(AptosError::InvalidPublicKey(format!(
                "verification not supported for variant {:?}",
                self.variant
            ))),
        }
    }
}

impl fmt::Debug for AnyPublicKey {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "AnyPublicKey({:?}, {})",
            self.variant,
            const_hex::encode_prefixed(&self.bytes)
        )
    }
}

impl fmt::Display for AnyPublicKey {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "{:?}:{}",
            self.variant,
            const_hex::encode_prefixed(&self.bytes)
        )
    }
}

/// A signature that can be any supported signature scheme.
#[derive(Clone, PartialEq, Eq)]
pub struct AnySignature {
    /// The signature scheme variant.
    pub variant: AnyPublicKeyVariant,
    /// The raw signature bytes.
    pub bytes: Vec<u8>,
}

impl AnySignature {
    /// Creates a new `AnySignature`.
    pub fn new(variant: AnyPublicKeyVariant, bytes: Vec<u8>) -> Self {
        Self { variant, bytes }
    }

    /// Creates an Ed25519 signature.
    #[cfg(feature = "ed25519")]
    pub fn ed25519(signature: &crate::crypto::Ed25519Signature) -> Self {
        Self {
            variant: AnyPublicKeyVariant::Ed25519,
            bytes: signature.to_bytes().to_vec(),
        }
    }

    /// Creates a Secp256k1 signature.
    #[cfg(feature = "secp256k1")]
    pub fn secp256k1(signature: &crate::crypto::Secp256k1Signature) -> Self {
        Self {
            variant: AnyPublicKeyVariant::Secp256k1,
            bytes: signature.to_bytes().to_vec(),
        }
    }

    /// Creates a Secp256r1 signature.
    #[cfg(feature = "secp256r1")]
    pub fn secp256r1(signature: &crate::crypto::Secp256r1Signature) -> Self {
        Self {
            variant: AnyPublicKeyVariant::Secp256r1,
            bytes: signature.to_bytes().to_vec(),
        }
    }

    /// Serializes to BCS `AnySignature` bytes.
    ///
    /// Most variants use `variant_byte` || `ULEB128(len)` || `payload`.
    ///
    /// On Aptos, discriminant `2` is shared by bare `Secp256r1Ecdsa` signatures (64-byte
    /// payload) and the `WebAuthn` variant, which embeds a `PartialAuthenticatorAssertionResponse`
    /// struct **without** an outer `ULEB128` length prefix after the enum tag. When this struct
    /// is present, the first payload byte is `0x00` (`AssertionSignature::Secp256r1Ecdsa`).
    /// For that shape we serialize as `0x02 || payload` to match the chain and
    /// [`crate::account::WebAuthnAccount`].
    pub fn to_bcs_bytes(&self) -> Vec<u8> {
        if self.variant == AnyPublicKeyVariant::Secp256r1 && self.bytes.len() != 64 {
            let mut result = Vec::with_capacity(1 + self.bytes.len());
            result.push(self.variant.as_byte());
            result.extend_from_slice(&self.bytes);
            return result;
        }
        let mut result = Vec::with_capacity(1 + 1 + self.bytes.len());
        result.push(self.variant.as_byte());
        // BCS uses ULEB128 for vector lengths
        result.extend(uleb128_encode(self.bytes.len()));
        result.extend_from_slice(&self.bytes);
        result
    }

    /// Parses BCS `AnySignature` bytes from the wire.
    ///
    /// For variants other than `Secp256r1` (`2`), this expects
    /// `variant` || `ULEB128(len)` || `payload`.
    ///
    /// For discriminant `2`, Aptos uses two layouts:
    ///
    /// - Bare ECDSA: `0x02` || `ULEB128(64)` || 64-byte signature. The length prefix always
    ///   begins with `0x40` when `64` is encoded as a single ULEB128 byte.
    /// - WebAuthn: `0x02` || BCS(`PartialAuthenticatorAssertionResponse`), which begins with
    ///   `0x00` (`AssertionSignature::Secp256r1Ecdsa`) — **no** outer `ULEB128` wrapping the
    ///   struct.
    ///
    /// # Errors
    ///
    /// Returns [`AptosError::InvalidSignature`] if the slice is empty, the variant byte is
    /// unknown, the length prefix is malformed, the payload is truncated, or trailing bytes
    /// remain after the declared signature bytes.
    pub fn from_bcs_bytes(bytes: &[u8]) -> AptosResult<Self> {
        if bytes.is_empty() {
            return Err(AptosError::InvalidSignature(
                "AnySignature BCS empty".into(),
            ));
        }
        let variant = AnyPublicKeyVariant::from_byte(bytes[0]).map_err(|e| {
            AptosError::InvalidSignature(format!("AnySignature BCS bad variant: {e}"))
        })?;
        if variant == AnyPublicKeyVariant::Secp256r1 && bytes.len() > 1 && bytes[1] == 0x00 {
            return Ok(Self::new(variant, bytes[1..].to_vec()));
        }
        let (len, len_bytes) = uleb128_decode(&bytes[1..]).ok_or_else(|| {
            AptosError::InvalidSignature("AnySignature BCS invalid length prefix".into())
        })?;
        let start = 1 + len_bytes;
        let end = start.checked_add(len).ok_or_else(|| {
            AptosError::InvalidSignature("AnySignature BCS length overflow".into())
        })?;
        if end > bytes.len() {
            return Err(AptosError::InvalidSignature(
                "AnySignature BCS truncated payload".into(),
            ));
        }
        if end != bytes.len() {
            return Err(AptosError::InvalidSignature(
                "AnySignature BCS trailing bytes".into(),
            ));
        }
        Ok(Self::new(variant, bytes[start..end].to_vec()))
    }
}

/// Encodes a value as `ULEB128` (unsigned `LEB128`).
/// BCS uses `ULEB128` for encoding vector/sequence lengths.
/// For typical sizes (< 128), this returns a single byte.
#[allow(clippy::cast_possible_truncation)] // value & 0x7F is always <= 127
#[inline]
pub(crate) fn uleb128_encode(mut value: usize) -> Vec<u8> {
    // Pre-allocate for common case: values < 128 need 1 byte, < 16384 need 2 bytes
    let mut result = Vec::with_capacity(if value < 128 { 1 } else { 2 });
    loop {
        let byte = (value & 0x7F) as u8;
        value >>= 7;
        if value == 0 {
            result.push(byte);
            break;
        }
        result.push(byte | 0x80);
    }
    result
}

/// Decodes a `ULEB128` value from bytes, returning `(value, bytes_consumed)`.
fn uleb128_decode(bytes: &[u8]) -> Option<(usize, usize)> {
    let mut result: usize = 0;
    let mut shift = 0;
    for (i, &byte) in bytes.iter().enumerate() {
        result |= ((byte & 0x7F) as usize) << shift;
        if byte & 0x80 == 0 {
            return Some((result, i + 1));
        }
        shift += 7;
        if shift >= 64 {
            return None; // Overflow
        }
    }
    None
}

impl fmt::Debug for AnySignature {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "AnySignature({:?}, {} bytes)",
            self.variant,
            self.bytes.len()
        )
    }
}

/// A multi-key public key supporting mixed signature schemes.
///
/// This allows M-of-N threshold signing where each key can be a different type.
#[derive(Clone, PartialEq, Eq)]
pub struct MultiKeyPublicKey {
    /// The individual public keys.
    public_keys: Vec<AnyPublicKey>,
    /// The required threshold (M in M-of-N).
    threshold: u8,
}

impl MultiKeyPublicKey {
    /// Creates a new multi-key public key.
    ///
    /// # Arguments
    ///
    /// * `public_keys` - The individual public keys (can be mixed types)
    /// * `threshold` - The number of signatures required (M in M-of-N)
    ///
    /// # Errors
    ///
    /// Returns [`AptosError::InvalidPublicKey`] if:
    /// - No public keys are provided
    /// - More than 32 public keys are provided
    /// - Threshold is 0
    /// - Threshold exceeds the number of keys
    pub fn new(public_keys: Vec<AnyPublicKey>, threshold: u8) -> AptosResult<Self> {
        if public_keys.is_empty() {
            return Err(AptosError::InvalidPublicKey(
                "multi-key requires at least one public key".into(),
            ));
        }
        if public_keys.len() > MAX_NUM_OF_KEYS {
            return Err(AptosError::InvalidPublicKey(format!(
                "multi-key supports at most {} keys, got {}",
                MAX_NUM_OF_KEYS,
                public_keys.len()
            )));
        }
        if threshold < MIN_THRESHOLD {
            return Err(AptosError::InvalidPublicKey(
                "threshold must be at least 1".into(),
            ));
        }
        if threshold as usize > public_keys.len() {
            return Err(AptosError::InvalidPublicKey(format!(
                "threshold {} exceeds number of keys {}",
                threshold,
                public_keys.len()
            )));
        }
        Ok(Self {
            public_keys,
            threshold,
        })
    }

    /// Returns the number of public keys.
    pub fn num_keys(&self) -> usize {
        self.public_keys.len()
    }

    /// Returns the threshold.
    pub fn threshold(&self) -> u8 {
        self.threshold
    }

    /// Returns the individual public keys.
    pub fn public_keys(&self) -> &[AnyPublicKey] {
        &self.public_keys
    }

    /// Returns the key at the given index.
    pub fn get(&self, index: usize) -> Option<&AnyPublicKey> {
        self.public_keys.get(index)
    }

    /// Serializes to bytes for authentication key derivation.
    ///
    /// Format: `num_keys` || `pk1_bcs` || `pk2_bcs` || ... || threshold
    #[allow(clippy::cast_possible_truncation)] // public_keys.len() <= MAX_NUM_OF_KEYS (32)
    pub fn to_bytes(&self) -> Vec<u8> {
        // Pre-allocate: 1 byte num_keys + estimated key size (avg ~35 bytes per key) + 1 byte threshold
        let estimated_size = 2 + self.public_keys.len() * 36;
        let mut bytes = Vec::with_capacity(estimated_size);

        // Number of keys (1 byte, validated in new())
        bytes.push(self.public_keys.len() as u8);

        // Each public key in BCS format
        for pk in &self.public_keys {
            bytes.extend(pk.to_bcs_bytes());
        }

        // Threshold (1 byte)
        bytes.push(self.threshold);

        bytes
    }

    /// Creates from bytes.
    ///
    /// # Errors
    ///
    /// Returns [`AptosError::InvalidPublicKey`] if:
    /// - The bytes are empty
    /// - The number of keys is invalid (0 or > 32)
    /// - The bytes are too short for the expected structure
    /// - Any public key variant byte is invalid
    /// - Any public key length or data is invalid
    /// - The threshold is invalid
    pub fn from_bytes(bytes: &[u8]) -> AptosResult<Self> {
        // SECURITY: Limit individual key size to prevent DoS via large allocations
        // Largest supported key is uncompressed secp256k1/secp256r1 at 65 bytes
        const MAX_KEY_SIZE: usize = 128;

        if bytes.is_empty() {
            return Err(AptosError::InvalidPublicKey("empty bytes".into()));
        }

        let num_keys = bytes[0] as usize;
        if num_keys == 0 || num_keys > MAX_NUM_OF_KEYS {
            return Err(AptosError::InvalidPublicKey(format!(
                "invalid number of keys: {num_keys}"
            )));
        }

        let mut offset = 1;
        let mut public_keys = Vec::with_capacity(num_keys);

        for _ in 0..num_keys {
            if offset >= bytes.len() {
                return Err(AptosError::InvalidPublicKey("bytes too short".into()));
            }

            let variant = AnyPublicKeyVariant::from_byte(bytes[offset])?;
            offset += 1;

            // Decode ULEB128 length
            let (len, len_bytes) = uleb128_decode(&bytes[offset..]).ok_or_else(|| {
                AptosError::InvalidPublicKey("invalid ULEB128 length encoding".into())
            })?;
            offset += len_bytes;

            if len > MAX_KEY_SIZE {
                return Err(AptosError::InvalidPublicKey(format!(
                    "key size {len} exceeds maximum {MAX_KEY_SIZE}"
                )));
            }

            if offset + len > bytes.len() {
                return Err(AptosError::InvalidPublicKey(
                    "bytes too short for key".into(),
                ));
            }

            let key_bytes = bytes[offset..offset + len].to_vec();
            offset += len;

            public_keys.push(AnyPublicKey::new(variant, key_bytes));
        }

        if offset >= bytes.len() {
            return Err(AptosError::InvalidPublicKey(
                "bytes too short for threshold".into(),
            ));
        }

        let threshold = bytes[offset];

        Self::new(public_keys, threshold)
    }

    /// Derives the account address for this multi-key public key.
    pub fn to_address(&self) -> crate::types::AccountAddress {
        crate::crypto::derive_address(&self.to_bytes(), crate::crypto::MULTI_KEY_SCHEME)
    }

    /// Derives the authentication key for this public key.
    pub fn to_authentication_key(&self) -> [u8; 32] {
        crate::crypto::derive_authentication_key(&self.to_bytes(), crate::crypto::MULTI_KEY_SCHEME)
    }

    /// Verifies a multi-key signature against a message.
    ///
    /// # Errors
    ///
    /// This function will return an error if:
    /// - The number of signatures is less than the threshold
    /// - Any individual signature verification fails
    /// - A signer index is out of bounds
    pub fn verify(&self, message: &[u8], signature: &MultiKeySignature) -> AptosResult<()> {
        // Check that we have enough signatures
        if signature.num_signatures() < self.threshold as usize {
            return Err(AptosError::SignatureVerificationFailed);
        }

        // Verify each signature
        for (index, sig) in signature.signatures() {
            if *index as usize >= self.public_keys.len() {
                return Err(AptosError::InvalidSignature(format!(
                    "signer index {} out of bounds (max {})",
                    index,
                    self.public_keys.len() - 1
                )));
            }
            let pk = &self.public_keys[*index as usize];
            pk.verify(message, sig)?;
        }

        Ok(())
    }
}

impl fmt::Debug for MultiKeyPublicKey {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "MultiKeyPublicKey({}-of-{} keys)",
            self.threshold,
            self.public_keys.len()
        )
    }
}

impl fmt::Display for MultiKeyPublicKey {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(&const_hex::encode_prefixed(self.to_bytes()))
    }
}

/// A multi-key signature containing signatures from multiple signers.
#[derive(Clone, PartialEq, Eq)]
pub struct MultiKeySignature {
    /// Individual signatures with their signer index.
    signatures: Vec<(u8, AnySignature)>,
    /// Bitmap indicating which keys signed (up to 4 bytes for 32 keys). Bits are
    /// set MSB-first within each byte (big-endian bit order): signer index 0 is
    /// bit 7 of byte 0, index 7 is bit 0 of byte 0, and so on. This matches
    /// aptos-core's `aptos_bitvec::BitVec` (`0b1000_0000 >> pos`); see `new`.
    bitmap: [u8; 4],
}

impl MultiKeySignature {
    /// Creates a new multi-key signature from individual signatures.
    ///
    /// # Arguments
    ///
    /// * `signatures` - Vec of (`signer_index`, signature) pairs
    ///
    /// # Errors
    ///
    /// Returns [`AptosError::InvalidSignature`] if:
    /// - No signatures are provided
    /// - More than 32 signatures are provided
    /// - A signer index is out of bounds (>= 32)
    /// - Duplicate signer indices are present
    pub fn new(mut signatures: Vec<(u8, AnySignature)>) -> AptosResult<Self> {
        if signatures.is_empty() {
            return Err(AptosError::InvalidSignature(
                "multi-key signature requires at least one signature".into(),
            ));
        }
        if signatures.len() > MAX_NUM_OF_KEYS {
            return Err(AptosError::InvalidSignature(format!(
                "too many signatures: {} (max {})",
                signatures.len(),
                MAX_NUM_OF_KEYS
            )));
        }

        // Sort by index
        signatures.sort_by_key(|(idx, _)| *idx);

        // Check for duplicates and bounds, build bitmap
        let mut bitmap = [0u8; 4];
        let mut last_index: Option<u8> = None;

        for (index, _) in &signatures {
            if *index as usize >= MAX_NUM_OF_KEYS {
                return Err(AptosError::InvalidSignature(format!(
                    "signer index {} out of bounds (max {})",
                    index,
                    MAX_NUM_OF_KEYS - 1
                )));
            }
            if last_index == Some(*index) {
                return Err(AptosError::InvalidSignature(format!(
                    "duplicate signer index {index}"
                )));
            }
            last_index = Some(*index);

            // Set bit in bitmap
            // Aptos uses MSB-first ordering within each bitmap byte
            // (matches `aptos_bitvec::BitVec::set`: `0b1000_0000 >> pos`).
            // index 0 -> bit 7 of byte 0, index 7 -> bit 0 of byte 0, etc.
            let byte_index = (index / 8) as usize;
            let bit_in_byte = index % 8;
            bitmap[byte_index] |= 0b1000_0000u8 >> bit_in_byte;
        }

        Ok(Self { signatures, bitmap })
    }

    /// Returns the number of signatures.
    pub fn num_signatures(&self) -> usize {
        self.signatures.len()
    }

    /// Returns the individual signatures with their indices.
    pub fn signatures(&self) -> &[(u8, AnySignature)] {
        &self.signatures
    }

    /// Returns the signer bitmap.
    pub fn bitmap(&self) -> &[u8; 4] {
        &self.bitmap
    }

    /// Checks if a particular index signed.
    pub fn has_signature(&self, index: u8) -> bool {
        if index as usize >= MAX_NUM_OF_KEYS {
            return false;
        }
        let byte_index = (index / 8) as usize;
        let bit_in_byte = index % 8;
        (self.bitmap[byte_index] & (0b1000_0000u8 >> bit_in_byte)) != 0
    }

    /// Serializes to bytes, matching the on-chain BCS layout of
    /// `MultiKeyAuthenticator { signatures: Vec<AnySignature>, signatures_bitmap: BitVec }`.
    ///
    /// Wire layout: `ULEB128(num_sigs) || BCS(AnySignature)... || BCS(BitVec)`
    /// where `BCS(BitVec) = ULEB128(num_bitmap_bytes) || bitmap_bytes`.
    #[allow(clippy::cast_possible_truncation)] // signatures.len() <= MAX_NUM_OF_KEYS (32)
    pub fn to_bytes(&self) -> Vec<u8> {
        // Pre-allocate: 1 byte num_sigs + estimated sig size (~68 bytes per sig)
        // + 1 byte bitmap length prefix + 4 bytes bitmap.
        let estimated_size = 1 + self.signatures.len() * 68 + 1 + 4;
        let mut bytes = Vec::with_capacity(estimated_size);

        // ULEB128(num_signatures). num_sigs <= 32 fits in a single byte.
        bytes.push(self.signatures.len() as u8);

        // Each AnySignature in BCS format (ordered by signer index).
        for (_, sig) in &self.signatures {
            bytes.extend(sig.to_bcs_bytes());
        }

        // BitVec BCS prefix: ULEB128(4).
        bytes.push(4);
        // Bitmap bytes.
        bytes.extend_from_slice(&self.bitmap);

        bytes
    }

    /// Creates from bytes.
    ///
    /// # Errors
    ///
    /// Returns [`AptosError::InvalidSignature`] if:
    /// - The bytes are too short (fewer than 6 bytes: 1 `num_sigs` byte + a
    ///   1-byte `BitVec` ULEB128 length prefix + 4 bitmap bytes)
    /// - The number of signatures is invalid (0 or > 32)
    /// - The bitmap doesn't match the number of signatures
    /// - The bytes are too short for the expected structure
    /// - Any signature variant byte is invalid
    /// - Any signature length or data is invalid
    pub fn from_bytes(bytes: &[u8]) -> AptosResult<Self> {
        // SECURITY: Limit individual signature size to prevent DoS via large allocations
        // Largest supported signature is ~72 bytes for ECDSA DER format
        const MAX_SIGNATURE_SIZE: usize = 128;

        // Wire layout (matches `to_bytes`):
        //   ULEB128(num_sigs) || sigs... || ULEB128(4) || 4 bitmap bytes
        // Minimum length is 1 (num_sigs) + 1 (BitVec length prefix) + 4 (bitmap) = 6.
        if bytes.len() < 6 {
            return Err(AptosError::InvalidSignature("bytes too short".into()));
        }

        let num_sigs = bytes[0] as usize;
        if num_sigs == 0 || num_sigs > MAX_NUM_OF_KEYS {
            return Err(AptosError::InvalidSignature(format!(
                "invalid number of signatures: {num_sigs}"
            )));
        }

        // Read bitmap from the end. Last 4 bytes are the bitmap bytes; the byte
        // just before is the ULEB128(4) length prefix from BCS(BitVec).
        let bitmap_start = bytes.len() - 4;
        let mut bitmap = [0u8; 4];
        bitmap.copy_from_slice(&bytes[bitmap_start..]);
        let bitvec_prefix_idx = bitmap_start.checked_sub(1).ok_or_else(|| {
            AptosError::InvalidSignature("MultiKeySignature too short for BitVec prefix".into())
        })?;
        if bytes[bitvec_prefix_idx] != 4 {
            return Err(AptosError::InvalidSignature(
                "MultiKeySignature: expected BCS BitVec length prefix = 4".into(),
            ));
        }

        // Parse signatures
        let mut offset = 1;
        let mut signatures = Vec::with_capacity(num_sigs);

        // MSB-first bit order (matches aptos-core's `aptos_bitvec::BitVec`).
        let mut signer_indices = Vec::new();
        #[allow(clippy::cast_possible_truncation)]
        for bit_pos in 0..(MAX_NUM_OF_KEYS as u8) {
            let byte_idx = (bit_pos / 8) as usize;
            let bit_in_byte = bit_pos % 8;
            if (bitmap[byte_idx] & (0b1000_0000u8 >> bit_in_byte)) != 0 {
                signer_indices.push(bit_pos);
            }
        }

        if signer_indices.len() != num_sigs {
            return Err(AptosError::InvalidSignature(
                "bitmap doesn't match number of signatures".into(),
            ));
        }

        // Signatures occupy the range `[1, bitvec_prefix_idx)` -- everything
        // between the leading num_sigs byte and the BCS BitVec length prefix.
        let sigs_end = bitvec_prefix_idx;
        for &index in &signer_indices {
            if offset >= sigs_end {
                return Err(AptosError::InvalidSignature("bytes too short".into()));
            }

            let variant = AnyPublicKeyVariant::from_byte(bytes[offset])?;
            offset += 1;

            // Decode ULEB128 length
            let (len, len_bytes) = uleb128_decode(&bytes[offset..sigs_end]).ok_or_else(|| {
                AptosError::InvalidSignature("invalid ULEB128 length encoding".into())
            })?;
            offset += len_bytes;

            if len > MAX_SIGNATURE_SIZE {
                return Err(AptosError::InvalidSignature(format!(
                    "signature size {len} exceeds maximum {MAX_SIGNATURE_SIZE}"
                )));
            }

            if offset + len > sigs_end {
                return Err(AptosError::InvalidSignature(
                    "bytes too short for signature".into(),
                ));
            }

            let sig_bytes = bytes[offset..offset + len].to_vec();
            offset += len;

            signatures.push((index, AnySignature::new(variant, sig_bytes)));
        }

        Ok(Self { signatures, bitmap })
    }
}

impl fmt::Debug for MultiKeySignature {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "MultiKeySignature({} signatures, bitmap={:?})",
            self.signatures.len(),
            self.bitmap
        )
    }
}

impl fmt::Display for MultiKeySignature {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(&const_hex::encode_prefixed(self.to_bytes()))
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_any_public_key_variant_from_byte() {
        assert_eq!(
            AnyPublicKeyVariant::from_byte(0).unwrap(),
            AnyPublicKeyVariant::Ed25519
        );
        assert_eq!(
            AnyPublicKeyVariant::from_byte(1).unwrap(),
            AnyPublicKeyVariant::Secp256k1
        );
        assert_eq!(
            AnyPublicKeyVariant::from_byte(2).unwrap(),
            AnyPublicKeyVariant::Secp256r1
        );
        assert_eq!(
            AnyPublicKeyVariant::from_byte(3).unwrap(),
            AnyPublicKeyVariant::Keyless
        );
        assert!(AnyPublicKeyVariant::from_byte(4).is_err());
        assert!(AnyPublicKeyVariant::from_byte(255).is_err());
    }

    #[test]
    fn test_any_public_key_variant_as_byte() {
        assert_eq!(AnyPublicKeyVariant::Ed25519.as_byte(), 0);
        assert_eq!(AnyPublicKeyVariant::Secp256k1.as_byte(), 1);
        assert_eq!(AnyPublicKeyVariant::Secp256r1.as_byte(), 2);
        assert_eq!(AnyPublicKeyVariant::Keyless.as_byte(), 3);
    }

    #[test]
    fn test_any_public_key_new() {
        let pk = AnyPublicKey::new(AnyPublicKeyVariant::Ed25519, vec![0x11; 32]);
        assert_eq!(pk.variant, AnyPublicKeyVariant::Ed25519);
        assert_eq!(pk.bytes.len(), 32);
        assert_eq!(pk.bytes[0], 0x11);
    }

    #[test]
    fn test_any_public_key_to_bcs_bytes() {
        let pk = AnyPublicKey::new(AnyPublicKeyVariant::Ed25519, vec![0xaa; 32]);
        let bcs = pk.to_bcs_bytes();

        // Format: variant_byte || ULEB128(length) || bytes
        assert_eq!(bcs[0], 0); // Ed25519 variant
        assert_eq!(bcs[1], 32); // ULEB128(32) = 0x20 (since 32 < 128)
        assert_eq!(bcs[2], 0xaa); // first byte of key
        assert_eq!(bcs.len(), 1 + 1 + 32); // variant + length + bytes
    }

    #[test]
    fn test_any_public_key_debug() {
        let pk = AnyPublicKey::new(AnyPublicKeyVariant::Secp256k1, vec![0xbb; 33]);
        let debug = format!("{pk:?}");
        assert!(debug.contains("Secp256k1"));
        assert!(debug.contains("0x"));
    }

    #[test]
    fn test_any_signature_new() {
        let sig = AnySignature::new(AnyPublicKeyVariant::Ed25519, vec![0xcc; 64]);
        assert_eq!(sig.variant, AnyPublicKeyVariant::Ed25519);
        assert_eq!(sig.bytes.len(), 64);
    }

    #[test]
    fn test_any_signature_to_bcs_bytes() {
        let sig = AnySignature::new(AnyPublicKeyVariant::Ed25519, vec![0xdd; 64]);
        let bcs = sig.to_bcs_bytes();

        // Format: variant_byte || ULEB128(length) || bytes
        assert_eq!(bcs[0], 0); // Ed25519 variant
        assert_eq!(bcs[1], 64); // ULEB128(64) = 0x40 (since 64 < 128)
        assert_eq!(bcs[2], 0xdd); // first byte of signature
        assert_eq!(bcs.len(), 1 + 1 + 64); // variant + length + bytes
    }

    #[test]
    fn test_any_signature_secp256r1_bare_bcs_roundtrip() {
        let inner = vec![0x42u8; 64];
        let mut wire = vec![0x02, 0x40];
        wire.extend_from_slice(&inner);
        let sig = AnySignature::from_bcs_bytes(&wire).expect("parse bare Secp256r1");
        assert_eq!(sig.variant, AnyPublicKeyVariant::Secp256r1);
        assert_eq!(sig.bytes, inner);
        assert_eq!(sig.to_bcs_bytes(), wire);
    }

    #[test]
    fn test_any_signature_webauthn_style_bcs_roundtrip() {
        // Synthetic PAAR-shaped payload: starts with AssertionSignature::Secp256r1Ecdsa (0x00)
        // and is not exactly 64 bytes so `to_bcs_bytes` uses WebAuthn framing.
        let mut paar = vec![0x00u8, 0x40];
        paar.extend(vec![0x11u8; 64]);
        let mut wire = vec![0x02];
        wire.extend_from_slice(&paar);
        let sig = AnySignature::from_bcs_bytes(&wire).expect("parse WebAuthn-style");
        assert_eq!(sig.variant, AnyPublicKeyVariant::Secp256r1);
        assert_eq!(sig.bytes, paar);
        assert_eq!(sig.to_bcs_bytes(), wire);
    }

    #[test]
    fn test_any_signature_debug() {
        let sig = AnySignature::new(AnyPublicKeyVariant::Secp256r1, vec![0xee; 64]);
        let debug = format!("{sig:?}");
        assert!(debug.contains("Secp256r1"));
        assert!(debug.contains("64 bytes"));
    }

    #[test]
    fn test_any_public_key_verify_mismatched_variant() {
        let pk = AnyPublicKey::new(AnyPublicKeyVariant::Ed25519, vec![0; 32]);
        let sig = AnySignature::new(AnyPublicKeyVariant::Secp256k1, vec![0; 64]);

        let result = pk.verify(b"message", &sig);
        assert!(result.is_err());
        assert!(result.unwrap_err().to_string().contains("variant"));
    }

    #[test]
    fn test_multi_key_signature_insufficient_sigs() {
        // Empty signatures should fail
        let result = MultiKeySignature::new(vec![]);
        assert!(result.is_err());
    }

    #[test]
    fn test_multi_key_signature_duplicate_indices() {
        let sig1 = AnySignature::new(AnyPublicKeyVariant::Ed25519, vec![0; 64]);
        let sig2 = AnySignature::new(AnyPublicKeyVariant::Ed25519, vec![1; 64]);

        // Duplicate index should fail
        let result = MultiKeySignature::new(vec![(0, sig1.clone()), (0, sig2)]);
        assert!(result.is_err());
    }

    #[test]
    fn test_multi_key_signature_index_out_of_range() {
        let sig = AnySignature::new(AnyPublicKeyVariant::Ed25519, vec![0; 64]);

        // Index 32 is out of range (0-31)
        let result = MultiKeySignature::new(vec![(32, sig)]);
        assert!(result.is_err());
    }

    #[test]
    fn test_multi_key_signature_basic() {
        let sig1 = AnySignature::new(AnyPublicKeyVariant::Ed25519, vec![0xaa; 64]);
        let sig2 = AnySignature::new(AnyPublicKeyVariant::Ed25519, vec![0xbb; 64]);

        let multi_sig = MultiKeySignature::new(vec![(0, sig1), (5, sig2)]).unwrap();

        assert_eq!(multi_sig.num_signatures(), 2);
        assert!(multi_sig.has_signature(0));
        assert!(!multi_sig.has_signature(1));
        assert!(multi_sig.has_signature(5));
    }

    #[test]
    fn test_multi_key_signature_debug_display() {
        let sig = AnySignature::new(AnyPublicKeyVariant::Ed25519, vec![0; 64]);
        let multi_sig = MultiKeySignature::new(vec![(0, sig)]).unwrap();

        let debug = format!("{multi_sig:?}");
        let display = format!("{multi_sig}");

        assert!(debug.contains("MultiKeySignature"));
        assert!(display.starts_with("0x"));
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_multi_key_public_key_creation() {
        use crate::crypto::Ed25519PrivateKey;

        let keys: Vec<_> = (0..3)
            .map(|_| AnyPublicKey::ed25519(&Ed25519PrivateKey::generate().public_key()))
            .collect();

        // Valid 2-of-3
        let multi_pk = MultiKeyPublicKey::new(keys.clone(), 2).unwrap();
        assert_eq!(multi_pk.num_keys(), 3);
        assert_eq!(multi_pk.threshold(), 2);

        // Invalid: threshold > num_keys
        assert!(MultiKeyPublicKey::new(keys.clone(), 4).is_err());

        // Invalid: threshold = 0
        assert!(MultiKeyPublicKey::new(keys.clone(), 0).is_err());

        // Invalid: empty keys
        assert!(MultiKeyPublicKey::new(vec![], 1).is_err());
    }

    #[test]
    #[cfg(all(feature = "ed25519", feature = "secp256k1"))]
    fn test_multi_key_mixed_types() {
        use crate::crypto::{Ed25519PrivateKey, Secp256k1PrivateKey};

        // Create mixed key types
        let ed_key = AnyPublicKey::ed25519(&Ed25519PrivateKey::generate().public_key());
        let secp_key = AnyPublicKey::secp256k1(&Secp256k1PrivateKey::generate().public_key());

        let multi_pk = MultiKeyPublicKey::new(vec![ed_key, secp_key], 2).unwrap();
        assert_eq!(multi_pk.num_keys(), 2);
        assert_eq!(
            multi_pk.get(0).unwrap().variant,
            AnyPublicKeyVariant::Ed25519
        );
        assert_eq!(
            multi_pk.get(1).unwrap().variant,
            AnyPublicKeyVariant::Secp256k1
        );
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_multi_key_sign_verify() {
        use crate::crypto::Ed25519PrivateKey;

        let private_keys: Vec<_> = (0..3).map(|_| Ed25519PrivateKey::generate()).collect();
        let public_keys: Vec<_> = private_keys
            .iter()
            .map(|k| AnyPublicKey::ed25519(&k.public_key()))
            .collect();

        let multi_pk = MultiKeyPublicKey::new(public_keys, 2).unwrap();
        let message = b"test message";

        // Sign with keys 0 and 2 (2-of-3)
        let sig0 = AnySignature::ed25519(&private_keys[0].sign(message));
        let sig2 = AnySignature::ed25519(&private_keys[2].sign(message));

        let multi_sig = MultiKeySignature::new(vec![(0, sig0), (2, sig2)]).unwrap();

        // Verify should succeed
        assert!(multi_pk.verify(message, &multi_sig).is_ok());

        // Wrong message should fail
        assert!(multi_pk.verify(b"wrong message", &multi_sig).is_err());
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_multi_key_bytes_roundtrip() {
        use crate::crypto::Ed25519PrivateKey;

        let keys: Vec<_> = (0..3)
            .map(|_| AnyPublicKey::ed25519(&Ed25519PrivateKey::generate().public_key()))
            .collect();
        let multi_pk = MultiKeyPublicKey::new(keys, 2).unwrap();

        let bytes = multi_pk.to_bytes();
        let restored = MultiKeyPublicKey::from_bytes(&bytes).unwrap();

        assert_eq!(multi_pk.threshold(), restored.threshold());
        assert_eq!(multi_pk.num_keys(), restored.num_keys());
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_multi_key_signature_bytes_roundtrip() {
        use crate::crypto::Ed25519PrivateKey;

        let private_keys: Vec<_> = (0..3).map(|_| Ed25519PrivateKey::generate()).collect();
        let message = b"test";

        let sig0 = AnySignature::ed25519(&private_keys[0].sign(message));
        let sig2 = AnySignature::ed25519(&private_keys[2].sign(message));

        let multi_sig = MultiKeySignature::new(vec![(0, sig0), (2, sig2)]).unwrap();

        let bytes = multi_sig.to_bytes();
        let restored = MultiKeySignature::from_bytes(&bytes).unwrap();

        assert_eq!(multi_sig.num_signatures(), restored.num_signatures());
        assert_eq!(multi_sig.bitmap(), restored.bitmap());
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_signature_bitmap() {
        use crate::crypto::Ed25519PrivateKey;

        let private_keys: Vec<_> = (0..5).map(|_| Ed25519PrivateKey::generate()).collect();
        let message = b"test";

        // Sign with indices 1, 3, 4
        let signatures: Vec<_> = [1, 3, 4]
            .iter()
            .map(|&i| {
                (
                    i,
                    AnySignature::ed25519(&private_keys[i as usize].sign(message)),
                )
            })
            .collect();

        let multi_sig = MultiKeySignature::new(signatures).unwrap();

        assert!(!multi_sig.has_signature(0));
        assert!(multi_sig.has_signature(1));
        assert!(!multi_sig.has_signature(2));
        assert!(multi_sig.has_signature(3));
        assert!(multi_sig.has_signature(4));
        assert!(!multi_sig.has_signature(5));
    }

    #[test]
    fn test_multi_key_public_key_empty_keys() {
        let result = MultiKeyPublicKey::new(vec![], 1);
        assert!(result.is_err());
        assert!(result.unwrap_err().to_string().contains("at least one"));
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_multi_key_public_key_threshold_zero() {
        use crate::crypto::Ed25519PrivateKey;

        let keys: Vec<_> = (0..2)
            .map(|_| AnyPublicKey::ed25519(&Ed25519PrivateKey::generate().public_key()))
            .collect();
        let result = MultiKeyPublicKey::new(keys, 0);
        assert!(result.is_err());
        assert!(result.unwrap_err().to_string().contains("at least 1"));
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_multi_key_public_key_threshold_exceeds() {
        use crate::crypto::Ed25519PrivateKey;

        let keys: Vec<_> = (0..2)
            .map(|_| AnyPublicKey::ed25519(&Ed25519PrivateKey::generate().public_key()))
            .collect();
        let result = MultiKeyPublicKey::new(keys, 5);
        assert!(result.is_err());
        assert!(result.unwrap_err().to_string().contains("exceed"));
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_multi_key_signature_empty() {
        let result = MultiKeySignature::new(vec![]);
        assert!(result.is_err());
        assert!(result.unwrap_err().to_string().contains("at least one"));
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_multi_key_signature_duplicate_index() {
        use crate::crypto::Ed25519PrivateKey;

        let private_key = Ed25519PrivateKey::generate();
        let sig = AnySignature::ed25519(&private_key.sign(b"test"));

        let result = MultiKeySignature::new(vec![(0, sig.clone()), (0, sig)]);
        assert!(result.is_err());
        assert!(result.unwrap_err().to_string().contains("duplicate"));
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_multi_key_public_key_accessors() {
        use crate::crypto::Ed25519PrivateKey;

        let keys: Vec<_> = (0..3)
            .map(|_| AnyPublicKey::ed25519(&Ed25519PrivateKey::generate().public_key()))
            .collect();
        let multi_pk = MultiKeyPublicKey::new(keys, 2).unwrap();

        assert_eq!(multi_pk.threshold(), 2);
        assert_eq!(multi_pk.num_keys(), 3);
        assert_eq!(multi_pk.public_keys().len(), 3);
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_multi_key_signature_accessors() {
        use crate::crypto::Ed25519PrivateKey;

        let private_key = Ed25519PrivateKey::generate();
        let sig0 = AnySignature::ed25519(&private_key.sign(b"test"));
        let sig2 = AnySignature::ed25519(&private_key.sign(b"test"));

        let multi_sig = MultiKeySignature::new(vec![(0, sig0), (2, sig2)]).unwrap();

        assert_eq!(multi_sig.num_signatures(), 2);
        assert_eq!(multi_sig.signatures().len(), 2);
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_multi_key_public_key_debug() {
        use crate::crypto::Ed25519PrivateKey;

        let keys: Vec<_> = (0..2)
            .map(|_| AnyPublicKey::ed25519(&Ed25519PrivateKey::generate().public_key()))
            .collect();
        let multi_pk = MultiKeyPublicKey::new(keys, 2).unwrap();

        let debug = format!("{multi_pk:?}");
        assert!(debug.contains("MultiKeyPublicKey"));
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_multi_key_signature_debug() {
        use crate::crypto::Ed25519PrivateKey;

        let private_key = Ed25519PrivateKey::generate();
        let sig = AnySignature::ed25519(&private_key.sign(b"test"));
        let multi_sig = MultiKeySignature::new(vec![(0, sig)]).unwrap();

        let debug = format!("{multi_sig:?}");
        assert!(debug.contains("MultiKeySignature"));
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_multi_key_public_key_display() {
        use crate::crypto::Ed25519PrivateKey;

        let keys: Vec<_> = (0..2)
            .map(|_| AnyPublicKey::ed25519(&Ed25519PrivateKey::generate().public_key()))
            .collect();
        let multi_pk = MultiKeyPublicKey::new(keys, 2).unwrap();

        let display = format!("{multi_pk}");
        assert!(display.starts_with("0x"));
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_multi_key_signature_display() {
        use crate::crypto::Ed25519PrivateKey;

        let private_key = Ed25519PrivateKey::generate();
        let sig = AnySignature::ed25519(&private_key.sign(b"test"));
        let multi_sig = MultiKeySignature::new(vec![(0, sig)]).unwrap();

        let display = format!("{multi_sig}");
        assert!(display.starts_with("0x"));
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_multi_key_public_key_to_address() {
        use crate::crypto::Ed25519PrivateKey;

        let keys: Vec<_> = (0..2)
            .map(|_| AnyPublicKey::ed25519(&Ed25519PrivateKey::generate().public_key()))
            .collect();
        let multi_pk = MultiKeyPublicKey::new(keys, 2).unwrap();

        let address = multi_pk.to_address();
        assert!(!address.is_zero());
    }

    #[test]
    fn test_any_public_key_variant_debug() {
        let variant = AnyPublicKeyVariant::Ed25519;
        let debug = format!("{variant:?}");
        assert!(debug.contains("Ed25519"));
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_any_public_key_ed25519_debug() {
        use crate::crypto::Ed25519PrivateKey;

        let pk = AnyPublicKey::ed25519(&Ed25519PrivateKey::generate().public_key());
        let debug = format!("{pk:?}");
        assert!(debug.contains("Ed25519"));
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_any_signature_ed25519_debug() {
        use crate::crypto::Ed25519PrivateKey;

        let private_key = Ed25519PrivateKey::generate();
        let sig = AnySignature::ed25519(&private_key.sign(b"test"));
        let debug = format!("{sig:?}");
        assert!(debug.contains("Ed25519"));
    }

    #[test]
    #[cfg(feature = "ed25519")]
    fn test_multi_key_insufficient_signatures() {
        use crate::crypto::Ed25519PrivateKey;

        let private_keys: Vec<_> = (0..3).map(|_| Ed25519PrivateKey::generate()).collect();
        let public_keys: Vec<_> = private_keys
            .iter()
            .map(|k| AnyPublicKey::ed25519(&k.public_key()))
            .collect();

        let multi_pk = MultiKeyPublicKey::new(public_keys, 2).unwrap();
        let message = b"test message";

        // Only provide 1 signature when threshold is 2
        let sig0 = AnySignature::ed25519(&private_keys[0].sign(message));
        let multi_sig = MultiKeySignature::new(vec![(0, sig0)]).unwrap();

        // Verify should fail
        let result = multi_pk.verify(message, &multi_sig);
        assert!(result.is_err());
    }

    // ---- AnyPublicKey::from_bcs_bytes ----

    #[test]
    fn test_any_public_key_from_bcs_bytes_roundtrip() {
        let pk = AnyPublicKey::new(AnyPublicKeyVariant::Ed25519, vec![0x7c; 32]);
        let wire = pk.to_bcs_bytes();
        let parsed = AnyPublicKey::from_bcs_bytes(&wire).unwrap();
        assert_eq!(parsed, pk);
    }

    #[test]
    fn test_any_public_key_from_bcs_bytes_empty() {
        let err = AnyPublicKey::from_bcs_bytes(&[]).unwrap_err();
        assert!(matches!(err, AptosError::InvalidPublicKey(_)));
        assert!(err.to_string().contains("empty"));
    }

    #[test]
    fn test_any_public_key_from_bcs_bytes_bad_variant() {
        let err = AnyPublicKey::from_bcs_bytes(&[9, 0]).unwrap_err();
        assert!(matches!(err, AptosError::InvalidPublicKey(_)));
        assert!(err.to_string().contains("unknown public key variant"));
    }

    #[test]
    fn test_any_public_key_from_bcs_bytes_invalid_length_prefix() {
        // 0x80 is an unterminated ULEB128 continuation byte.
        let err = AnyPublicKey::from_bcs_bytes(&[0, 0x80]).unwrap_err();
        assert!(err.to_string().contains("invalid length prefix"));
    }

    #[test]
    fn test_any_public_key_from_bcs_bytes_length_overflow() {
        // variant byte + ULEB128(usize::MAX): start (1 + len_bytes) + len overflows.
        let mut wire = vec![0u8];
        wire.extend(uleb128_encode(usize::MAX));
        let err = AnyPublicKey::from_bcs_bytes(&wire).unwrap_err();
        assert!(err.to_string().contains("length overflow"));
    }

    #[test]
    fn test_any_public_key_from_bcs_bytes_truncated() {
        // declares 64 bytes but only 2 present.
        let err = AnyPublicKey::from_bcs_bytes(&[0, 0x40, 1, 2]).unwrap_err();
        assert!(err.to_string().contains("truncated"));
    }

    #[test]
    fn test_any_public_key_from_bcs_bytes_trailing() {
        // declares 1 byte but 2 payload bytes present.
        let err = AnyPublicKey::from_bcs_bytes(&[0, 0x01, 0xaa, 0xbb]).unwrap_err();
        assert!(err.to_string().contains("trailing"));
    }

    // ---- AnyPublicKey::verify additional paths ----

    #[test]
    #[cfg(feature = "secp256r1")]
    fn test_any_public_key_verify_secp256r1_ok() {
        use crate::crypto::Secp256r1PrivateKey;

        let sk = Secp256r1PrivateKey::from_bytes(&[9u8; 32]).unwrap();
        let pk = AnyPublicKey::secp256r1(&sk.public_key());
        let message = b"secp256r1 verify path";
        let sig = AnySignature::secp256r1(&sk.sign(message));
        assert!(pk.verify(message, &sig).is_ok());
        assert!(pk.verify(b"different", &sig).is_err());
    }

    #[test]
    fn test_any_public_key_verify_keyless_unsupported() {
        // Keyless has no verification arm; matching variants still hit the
        // "verification not supported" fallthrough.
        let pk = AnyPublicKey::new(AnyPublicKeyVariant::Keyless, vec![0u8; 32]);
        let sig = AnySignature::new(AnyPublicKeyVariant::Keyless, vec![0u8; 64]);
        let err = pk.verify(b"msg", &sig).unwrap_err();
        assert!(err.to_string().contains("verification not supported"));
    }

    #[test]
    fn test_any_public_key_display() {
        let pk = AnyPublicKey::new(AnyPublicKeyVariant::Secp256r1, vec![0xab; 4]);
        let display = format!("{pk}");
        assert_eq!(display, "Secp256r1:0xabababab");
    }

    // ---- AnySignature::from_bcs_bytes ----

    #[test]
    fn test_any_signature_from_bcs_bytes_empty() {
        let err = AnySignature::from_bcs_bytes(&[]).unwrap_err();
        assert!(matches!(err, AptosError::InvalidSignature(_)));
        assert!(err.to_string().contains("empty"));
    }

    #[test]
    fn test_any_signature_from_bcs_bytes_bad_variant() {
        let err = AnySignature::from_bcs_bytes(&[9, 0]).unwrap_err();
        assert!(err.to_string().contains("bad variant"));
    }

    #[test]
    fn test_any_signature_from_bcs_bytes_invalid_length_prefix() {
        let err = AnySignature::from_bcs_bytes(&[0, 0x80]).unwrap_err();
        assert!(err.to_string().contains("invalid length prefix"));
    }

    #[test]
    fn test_any_signature_from_bcs_bytes_length_overflow() {
        let mut wire = vec![0u8];
        wire.extend(uleb128_encode(usize::MAX));
        let err = AnySignature::from_bcs_bytes(&wire).unwrap_err();
        assert!(err.to_string().contains("length overflow"));
    }

    #[test]
    fn test_any_signature_from_bcs_bytes_truncated() {
        let err = AnySignature::from_bcs_bytes(&[0, 0x40, 1, 2]).unwrap_err();
        assert!(err.to_string().contains("truncated"));
    }

    #[test]
    fn test_any_signature_from_bcs_bytes_trailing() {
        let err = AnySignature::from_bcs_bytes(&[0, 0x01, 0xaa, 0xbb]).unwrap_err();
        assert!(err.to_string().contains("trailing"));
    }

    // ---- uleb128_decode error branches ----

    #[test]
    fn test_uleb128_decode_overflow() {
        // Ten continuation bytes push the shift past 64 bits.
        assert_eq!(uleb128_decode(&[0x80; 10]), None);
    }

    #[test]
    fn test_uleb128_decode_unterminated() {
        // A single continuation byte with no terminator exhausts the slice.
        assert_eq!(uleb128_decode(&[0x80]), None);
    }

    #[test]
    fn test_uleb128_decode_roundtrip_multibyte() {
        let (value, consumed) = uleb128_decode(&uleb128_encode(300)).unwrap();
        assert_eq!(value, 300);
        assert_eq!(consumed, 2);
    }

    // ---- MultiKeyPublicKey::new bounds ----

    #[test]
    fn test_multi_key_public_key_too_many_keys() {
        let keys: Vec<_> = (0..=MAX_NUM_OF_KEYS)
            .map(|_| AnyPublicKey::new(AnyPublicKeyVariant::Ed25519, vec![0u8; 32]))
            .collect();
        let err = MultiKeyPublicKey::new(keys, 1).unwrap_err();
        assert!(err.to_string().contains("at most"));
    }

    // ---- MultiKeyPublicKey::from_bytes error branches ----

    #[test]
    fn test_multi_key_public_key_from_bytes_empty() {
        let err = MultiKeyPublicKey::from_bytes(&[]).unwrap_err();
        assert!(err.to_string().contains("empty bytes"));
    }

    #[test]
    fn test_multi_key_public_key_from_bytes_zero_keys() {
        let err = MultiKeyPublicKey::from_bytes(&[0]).unwrap_err();
        assert!(err.to_string().contains("invalid number of keys"));
    }

    #[test]
    fn test_multi_key_public_key_from_bytes_too_many_keys() {
        let err = MultiKeyPublicKey::from_bytes(&[33]).unwrap_err();
        assert!(err.to_string().contains("invalid number of keys"));
    }

    #[test]
    fn test_multi_key_public_key_from_bytes_too_short_for_key_header() {
        // Declares 1 key but no bytes follow the count.
        let err = MultiKeyPublicKey::from_bytes(&[1]).unwrap_err();
        assert!(err.to_string().contains("bytes too short"));
    }

    #[test]
    fn test_multi_key_public_key_from_bytes_bad_variant() {
        let err = MultiKeyPublicKey::from_bytes(&[1, 9]).unwrap_err();
        assert!(err.to_string().contains("unknown public key variant"));
    }

    #[test]
    fn test_multi_key_public_key_from_bytes_invalid_uleb() {
        let err = MultiKeyPublicKey::from_bytes(&[1, 0, 0x80]).unwrap_err();
        assert!(err.to_string().contains("invalid ULEB128"));
    }

    #[test]
    fn test_multi_key_public_key_from_bytes_key_too_large() {
        // ULEB128(200) exceeds the 128-byte MAX_KEY_SIZE cap.
        let mut wire = vec![1u8, 0u8];
        wire.extend(uleb128_encode(200));
        let err = MultiKeyPublicKey::from_bytes(&wire).unwrap_err();
        assert!(err.to_string().contains("exceeds maximum"));
    }

    #[test]
    fn test_multi_key_public_key_from_bytes_too_short_for_key() {
        // Declares a 64-byte key but no payload follows.
        let err = MultiKeyPublicKey::from_bytes(&[1, 0, 0x40]).unwrap_err();
        assert!(err.to_string().contains("bytes too short for key"));
    }

    #[test]
    fn test_multi_key_public_key_from_bytes_too_short_for_threshold() {
        // A single zero-length key parses, but no threshold byte remains.
        let err = MultiKeyPublicKey::from_bytes(&[1, 0, 0]).unwrap_err();
        assert!(err.to_string().contains("bytes too short for threshold"));
    }

    // ---- MultiKeyPublicKey::verify index out of bounds ----

    #[test]
    fn test_multi_key_verify_signer_index_out_of_bounds() {
        let pk = AnyPublicKey::new(AnyPublicKeyVariant::Ed25519, vec![0u8; 32]);
        let multi_pk = MultiKeyPublicKey::new(vec![pk], 1).unwrap();
        // A signature claiming signer index 5 while only one key exists.
        let sig = AnySignature::new(AnyPublicKeyVariant::Ed25519, vec![0u8; 64]);
        let multi_sig = MultiKeySignature::new(vec![(5, sig)]).unwrap();
        let err = multi_pk.verify(b"msg", &multi_sig).unwrap_err();
        assert!(err.to_string().contains("out of bounds"));
    }

    // ---- MultiKeySignature::new / has_signature bounds ----

    #[test]
    fn test_multi_key_signature_too_many_signatures() {
        let sigs: Vec<_> = (0..=MAX_NUM_OF_KEYS)
            .map(|i| {
                (
                    i as u8,
                    AnySignature::new(AnyPublicKeyVariant::Ed25519, vec![0u8; 64]),
                )
            })
            .collect();
        let err = MultiKeySignature::new(sigs).unwrap_err();
        assert!(err.to_string().contains("too many signatures"));
    }

    #[test]
    fn test_multi_key_signature_has_signature_out_of_bounds() {
        let sig = AnySignature::new(AnyPublicKeyVariant::Ed25519, vec![0u8; 64]);
        let multi_sig = MultiKeySignature::new(vec![(0, sig)]).unwrap();
        assert!(!multi_sig.has_signature(255));
        assert!(!multi_sig.has_signature(MAX_NUM_OF_KEYS as u8));
    }

    // ---- MultiKeySignature::from_bytes error branches ----

    #[test]
    fn test_multi_key_signature_from_bytes_too_short() {
        let err = MultiKeySignature::from_bytes(&[1, 2, 3]).unwrap_err();
        assert!(err.to_string().contains("bytes too short"));
    }

    #[test]
    fn test_multi_key_signature_from_bytes_zero_sigs() {
        let err = MultiKeySignature::from_bytes(&[0, 4, 0, 0, 0, 0]).unwrap_err();
        assert!(err.to_string().contains("invalid number of signatures"));
    }

    #[test]
    fn test_multi_key_signature_from_bytes_too_many_sigs() {
        let err = MultiKeySignature::from_bytes(&[33, 4, 0, 0, 0, 0]).unwrap_err();
        assert!(err.to_string().contains("invalid number of signatures"));
    }

    #[test]
    fn test_multi_key_signature_from_bytes_bad_bitvec_prefix() {
        // BitVec length prefix must be 4; here it is 5.
        let err = MultiKeySignature::from_bytes(&[1, 5, 0, 0, 0, 0]).unwrap_err();
        assert!(err.to_string().contains("BitVec length prefix"));
    }

    #[test]
    fn test_multi_key_signature_from_bytes_bitmap_mismatch() {
        // Declares 2 signatures but the bitmap has no bits set.
        let err = MultiKeySignature::from_bytes(&[2, 4, 0, 0, 0, 0]).unwrap_err();
        assert!(err.to_string().contains("bitmap doesn't match"));
    }

    #[test]
    fn test_multi_key_signature_from_bytes_too_short_for_sig() {
        // num_sigs=1, bitmap bit 0 set, but no room for the signature body.
        let err = MultiKeySignature::from_bytes(&[1, 4, 0x80, 0, 0, 0]).unwrap_err();
        assert!(err.to_string().contains("bytes too short"));
    }

    #[test]
    fn test_multi_key_signature_from_bytes_bad_sig_variant() {
        // [num_sigs=1][variant=9][len=0][bitvec prefix=4][bitmap index0]
        let err = MultiKeySignature::from_bytes(&[1, 9, 0, 4, 0x80, 0, 0, 0]).unwrap_err();
        assert!(err.to_string().contains("unknown public key variant"));
    }

    #[test]
    fn test_multi_key_signature_from_bytes_invalid_sig_uleb() {
        // [num_sigs=1][variant=0][0x80 unterminated][prefix=4][bitmap]
        let err = MultiKeySignature::from_bytes(&[1, 0, 0x80, 4, 0x80, 0, 0, 0]).unwrap_err();
        assert!(err.to_string().contains("invalid ULEB128"));
    }

    #[test]
    fn test_multi_key_signature_from_bytes_sig_too_large() {
        // ULEB128(200) exceeds the 128-byte MAX_SIGNATURE_SIZE cap.
        let err = MultiKeySignature::from_bytes(&[1, 0, 0xC8, 0x01, 4, 0x80, 0, 0, 0]).unwrap_err();
        assert!(err.to_string().contains("exceeds maximum"));
    }

    #[test]
    fn test_multi_key_signature_from_bytes_too_short_for_sig_body() {
        // Declares a 64-byte signature but the body is absent.
        let err = MultiKeySignature::from_bytes(&[1, 0, 0x40, 4, 0x80, 0, 0, 0]).unwrap_err();
        assert!(err.to_string().contains("bytes too short for signature"));
    }
}