multi_ed25519 - [mainnet]

Exports MultiEd25519 multi-signatures in Move. This module has the exact same interface as the Ed25519 module.

use 0x1::bcs;
use 0x1::ed25519;
use 0x1::error;
use 0x1::features;
use 0x1::hash;
use 0x1::option;

Constants

The native functions have not been rolled out yet.

const E_NATIVE_FUN_NOT_AVAILABLE: u64 = 4;

Wrong number of bytes were given as input when deserializing an Ed25519 public key.

const E_WRONG_PUBKEY_SIZE: u64 = 1;

Wrong number of bytes were given as input when deserializing an Ed25519 signature.

const E_WRONG_SIGNATURE_SIZE: u64 = 2;

The identifier of the MultiEd25519 signature scheme, which is used when deriving Aptos authentication keys by hashing it together with an MultiEd25519 public key.

const SIGNATURE_SCHEME_ID: u8 = 1;

When serializing a MultiEd25519 signature, the bitmap that indicates the signers will be encoded using this many bytes.

const BITMAP_NUM_OF_BYTES: u64 = 4;

The threshold must be in the range [1, n], where n is the total number of signers.

const E_INVALID_THRESHOLD_OR_NUMBER_OF_SIGNERS: u64 = 3;

The size of an individual Ed25519 public key, in bytes. (A MultiEd25519 public key consists of several of these, plus the threshold.)

const INDIVIDUAL_PUBLIC_KEY_NUM_BYTES: u64 = 32;

The size of an individual Ed25519 signature, in bytes. (A MultiEd25519 signature consists of several of these, plus the signer bitmap.)

const INDIVIDUAL_SIGNATURE_NUM_BYTES: u64 = 64;

Max number of ed25519 public keys allowed in multi-ed25519 keys

const MAX_NUMBER_OF_PUBLIC_KEYS: u64 = 32;

When serializing a MultiEd25519 public key, the threshold k will be encoded using this many bytes.

const THRESHOLD_SIZE_BYTES: u64 = 1;

Structs

`UnvalidatedPublicKey`

An unvalidated, k out of n MultiEd25519 public key. The bytes field contains (1) several chunks of ed25519::PUBLIC_KEY_NUM_BYTES bytes, each encoding a Ed25519 PK, and (2) a single byte encoding the threshold k. Unvalidated means there is no guarantee that the underlying PKs are valid elliptic curve points of non-small order.

struct UnvalidatedPublicKey has copy, drop, store

Fields

bytes: vector<u8>

`ValidatedPublicKey`

A validated k out of n MultiEd25519 public key. Validated means that all the underlying PKs will be elliptic curve points that are NOT of small-order. It does not necessarily mean they will be prime-order points. This struct encodes the public key exactly as UnvalidatedPublicKey.

For now, this struct is not used in any verification functions, but it might be in the future.

struct ValidatedPublicKey has copy, drop, store

Fields

bytes: vector<u8>

`Signature`

A purported MultiEd25519 multi-signature that can be verified via signature_verify_strict or signature_verify_strict_t. The bytes field contains (1) several chunks of ed25519::SIGNATURE_NUM_BYTES bytes, each encoding a Ed25519 signature, and (2) a BITMAP_NUM_OF_BYTES-byte bitmap encoding the signer identities.

struct Signature has copy, drop, store

Fields

bytes: vector<u8>

Functions

`new_unvalidated_public_key_from_bytes`

Parses the input 32 bytes as an unvalidated MultiEd25519 public key.

NOTE: This function could have also checked that the # of sub-PKs is > 0, but it did not. However, since such invalid PKs are rejected during signature verification (see bugfix_unvalidated_pk_from_zero_subpks) they will not cause problems.

We could fix this API by adding a new one that checks the # of sub-PKs is > 0, but it is likely not a good idea to reproduce the PK validation logic in Move. We should not have done so in the first place. Instead, we will leave it as is and continue assuming UnvalidatedPublicKey objects could be invalid PKs that will safely be rejected during signature verification.

public fun new_unvalidated_public_key_from_bytes(bytes: vector<u8>): multi_ed25519::UnvalidatedPublicKey

Implementation

public fun new_unvalidated_public_key_from_bytes(bytes: vector<u8>): UnvalidatedPublicKey {
    let len = bytes.length();
    let num_sub_pks = len / INDIVIDUAL_PUBLIC_KEY_NUM_BYTES;

    assert!(num_sub_pks <= MAX_NUMBER_OF_PUBLIC_KEYS, error::invalid_argument(E_WRONG_PUBKEY_SIZE));
    assert!(len % INDIVIDUAL_PUBLIC_KEY_NUM_BYTES == THRESHOLD_SIZE_BYTES, error::invalid_argument(E_WRONG_PUBKEY_SIZE));
    UnvalidatedPublicKey { bytes }
}

`new_validated_public_key_from_bytes`

DEPRECATED: Use new_validated_public_key_from_bytes_v2 instead. See public_key_validate_internal comments.

(Incorrectly) parses the input bytes as a validated MultiEd25519 public key.

public fun new_validated_public_key_from_bytes(bytes: vector<u8>): option::Option<multi_ed25519::ValidatedPublicKey>

Implementation

public fun new_validated_public_key_from_bytes(bytes: vector<u8>): Option<ValidatedPublicKey> {
    // Note that `public_key_validate_internal` will check that `vector::length(&bytes) / INDIVIDUAL_PUBLIC_KEY_NUM_BYTES <= MAX_NUMBER_OF_PUBLIC_KEYS`.
    if (bytes.length() % INDIVIDUAL_PUBLIC_KEY_NUM_BYTES == THRESHOLD_SIZE_BYTES &&
        public_key_validate_internal(bytes)) {
        option::some(ValidatedPublicKey {
            bytes
        })
    } else {
        option::none<ValidatedPublicKey>()
    }
}

`new_validated_public_key_from_bytes_v2`

Parses the input bytes as a validated MultiEd25519 public key (see public_key_validate_internal_v2).

public fun new_validated_public_key_from_bytes_v2(bytes: vector<u8>): option::Option<multi_ed25519::ValidatedPublicKey>

Implementation

public fun new_validated_public_key_from_bytes_v2(bytes: vector<u8>): Option<ValidatedPublicKey> {
    if (!features::multi_ed25519_pk_validate_v2_enabled()) {
        abort(error::invalid_state(E_NATIVE_FUN_NOT_AVAILABLE))
    };

    if (public_key_validate_v2_internal(bytes)) {
        option::some(ValidatedPublicKey {
            bytes
        })
    } else {
        option::none<ValidatedPublicKey>()
    }
}

`new_signature_from_bytes`

Parses the input bytes as a purported MultiEd25519 multi-signature.

public fun new_signature_from_bytes(bytes: vector<u8>): multi_ed25519::Signature

Implementation

public fun new_signature_from_bytes(bytes: vector<u8>): Signature {
    assert!(
        bytes.length() % INDIVIDUAL_SIGNATURE_NUM_BYTES == BITMAP_NUM_OF_BYTES, error::invalid_argument(E_WRONG_SIGNATURE_SIZE));
    Signature { bytes }
}

`public_key_to_unvalidated`

Converts a ValidatedPublicKey to an UnvalidatedPublicKey, which can be used in the strict verification APIs.

public fun public_key_to_unvalidated(pk: &multi_ed25519::ValidatedPublicKey): multi_ed25519::UnvalidatedPublicKey

Implementation

public fun public_key_to_unvalidated(pk: &ValidatedPublicKey): UnvalidatedPublicKey {
    UnvalidatedPublicKey {
        bytes: pk.bytes
    }
}

`public_key_into_unvalidated`

Moves a ValidatedPublicKey into an UnvalidatedPublicKey, which can be used in the strict verification APIs.

public fun public_key_into_unvalidated(pk: multi_ed25519::ValidatedPublicKey): multi_ed25519::UnvalidatedPublicKey

Implementation

public fun public_key_into_unvalidated(pk: ValidatedPublicKey): UnvalidatedPublicKey {
    UnvalidatedPublicKey {
        bytes: pk.bytes
    }
}

`unvalidated_public_key_to_bytes`

Serializes an UnvalidatedPublicKey struct to 32-bytes.

public fun unvalidated_public_key_to_bytes(pk: &multi_ed25519::UnvalidatedPublicKey): vector<u8>

Implementation

public fun unvalidated_public_key_to_bytes(pk: &UnvalidatedPublicKey): vector<u8> {
    pk.bytes
}

`validated_public_key_to_bytes`

Serializes a ValidatedPublicKey struct to 32-bytes.

public fun validated_public_key_to_bytes(pk: &multi_ed25519::ValidatedPublicKey): vector<u8>

Implementation

public fun validated_public_key_to_bytes(pk: &ValidatedPublicKey): vector<u8> {
    pk.bytes
}

`signature_to_bytes`

Serializes a Signature struct to 64-bytes.

public fun signature_to_bytes(sig: &multi_ed25519::Signature): vector<u8>

Implementation

public fun signature_to_bytes(sig: &Signature): vector<u8> {
    sig.bytes
}

`public_key_validate`

DEPRECATED: Use public_key_validate_v2 instead. See public_key_validate_internal comments.

Takes in an unvalidated public key and attempts to validate it. Returns Some(ValidatedPublicKey) if successful and None otherwise.

public fun public_key_validate(pk: &multi_ed25519::UnvalidatedPublicKey): option::Option<multi_ed25519::ValidatedPublicKey>

Implementation

public fun public_key_validate(pk: &UnvalidatedPublicKey): Option<ValidatedPublicKey> {
    new_validated_public_key_from_bytes(pk.bytes)
}

`public_key_validate_v2`

Takes in an unvalidated public key and attempts to validate it. Returns Some(ValidatedPublicKey) if successful and None otherwise.

public fun public_key_validate_v2(pk: &multi_ed25519::UnvalidatedPublicKey): option::Option<multi_ed25519::ValidatedPublicKey>

Implementation

public fun public_key_validate_v2(pk: &UnvalidatedPublicKey): Option<ValidatedPublicKey> {
    new_validated_public_key_from_bytes_v2(pk.bytes)
}

`signature_verify_strict`

Verifies a purported MultiEd25519 multisignature under an unvalidated public_key on the specified message. This call will validate the public key by checking it is NOT in the small subgroup.

public fun signature_verify_strict(multisignature: &multi_ed25519::Signature, public_key: &multi_ed25519::UnvalidatedPublicKey, message: vector<u8>): bool

Implementation

public fun signature_verify_strict(
    multisignature: &Signature,
    public_key: &UnvalidatedPublicKey,
    message: vector<u8>
): bool {
    signature_verify_strict_internal(multisignature.bytes, public_key.bytes, message)
}

`signature_verify_strict_t`

This function is used to verify a multi-signature on any BCS-serializable type T. For now, it is used to verify the proof of private key ownership when rotating authentication keys.

public fun signature_verify_strict_t<T: drop>(multisignature: &multi_ed25519::Signature, public_key: &multi_ed25519::UnvalidatedPublicKey, data: T): bool

Implementation

public fun signature_verify_strict_t<T: drop>(multisignature: &Signature, public_key: &UnvalidatedPublicKey, data: T): bool {
    let encoded = ed25519::new_signed_message(data);

    signature_verify_strict_internal(multisignature.bytes, public_key.bytes, bcs::to_bytes(&encoded))
}

`unvalidated_public_key_to_authentication_key`

Derives the Aptos-specific authentication key of the given Ed25519 public key.

public fun unvalidated_public_key_to_authentication_key(pk: &multi_ed25519::UnvalidatedPublicKey): vector<u8>

Implementation

public fun unvalidated_public_key_to_authentication_key(pk: &UnvalidatedPublicKey): vector<u8> {
    public_key_bytes_to_authentication_key(pk.bytes)
}

`unvalidated_public_key_num_sub_pks`

Returns the number n of sub-PKs in an unvalidated t-out-of-n MultiEd25519 PK. If this UnvalidatedPublicKey would pass validation in public_key_validate, then the returned # of sub-PKs can be relied upon as correct.

We provide this API as a cheaper alternative to calling public_key_validate and then validated_public_key_num_sub_pks when the input pk is known to be valid.

public fun unvalidated_public_key_num_sub_pks(pk: &multi_ed25519::UnvalidatedPublicKey): u8

Implementation

public fun unvalidated_public_key_num_sub_pks(pk: &UnvalidatedPublicKey): u8 {
    let len = pk.bytes.length();

    ((len / INDIVIDUAL_PUBLIC_KEY_NUM_BYTES) as u8)
}

`unvalidated_public_key_threshold`

Returns the number t of sub-PKs in an unvalidated t-out-of-n MultiEd25519 PK (i.e., the threshold) or None if bytes does not correctly encode such a PK.

public fun unvalidated_public_key_threshold(pk: &multi_ed25519::UnvalidatedPublicKey): option::Option<u8>

Implementation

public fun unvalidated_public_key_threshold(pk: &UnvalidatedPublicKey): Option<u8> {
    check_and_get_threshold(pk.bytes)
}

`validated_public_key_to_authentication_key`

Derives the Aptos-specific authentication key of the given Ed25519 public key.

public fun validated_public_key_to_authentication_key(pk: &multi_ed25519::ValidatedPublicKey): vector<u8>

Implementation

public fun validated_public_key_to_authentication_key(pk: &ValidatedPublicKey): vector<u8> {
    public_key_bytes_to_authentication_key(pk.bytes)
}

`validated_public_key_num_sub_pks`

Returns the number n of sub-PKs in a validated t-out-of-n MultiEd25519 PK. Since the format of this PK has been validated, the returned # of sub-PKs is guaranteed to be correct.

public fun validated_public_key_num_sub_pks(pk: &multi_ed25519::ValidatedPublicKey): u8

Implementation

public fun validated_public_key_num_sub_pks(pk: &ValidatedPublicKey): u8 {
    let len = pk.bytes.length();

    ((len / INDIVIDUAL_PUBLIC_KEY_NUM_BYTES) as u8)
}

`validated_public_key_threshold`

Returns the number t of sub-PKs in a validated t-out-of-n MultiEd25519 PK (i.e., the threshold).

public fun validated_public_key_threshold(pk: &multi_ed25519::ValidatedPublicKey): u8

Implementation

public fun validated_public_key_threshold(pk: &ValidatedPublicKey): u8 {
    let len = pk.bytes.length();
    let threshold_byte = pk.bytes[len - 1];

    threshold_byte
}

`check_and_get_threshold`

Checks that the serialized format of a t-out-of-n MultiEd25519 PK correctly encodes 1 <= n <= 32 sub-PKs. (All ValidatedPublicKey objects are guaranteed to pass this check.) Returns the threshold t <= n of the PK.

public fun check_and_get_threshold(bytes: vector<u8>): option::Option<u8>

Implementation

public fun check_and_get_threshold(bytes: vector<u8>): Option<u8> {
    let len = bytes.length();
    if (len == 0) {
        return option::none<u8>()
    };

    let threshold_num_of_bytes = len % INDIVIDUAL_PUBLIC_KEY_NUM_BYTES;
    let num_of_keys = len / INDIVIDUAL_PUBLIC_KEY_NUM_BYTES;
    let threshold_byte = bytes[len - 1];

    if (num_of_keys == 0 || num_of_keys > MAX_NUMBER_OF_PUBLIC_KEYS || threshold_num_of_bytes != 1) {
        return option::none<u8>()
    } else if (threshold_byte == 0 || threshold_byte > (num_of_keys as u8)) {
        return option::none<u8>()
    } else {
        return option::some(threshold_byte)
    }
}

`public_key_bytes_to_authentication_key`

Derives the Aptos-specific authentication key of the given Ed25519 public key.

fun public_key_bytes_to_authentication_key(pk_bytes: vector<u8>): vector<u8>

Implementation

fun public_key_bytes_to_authentication_key(pk_bytes: vector<u8>): vector<u8> {
    pk_bytes.push_back(SIGNATURE_SCHEME_ID);
    std::hash::sha3_256(pk_bytes)
}

`public_key_validate_internal`

DEPRECATED: Use public_key_validate_internal_v2 instead. This function was NOT correctly implemented:

It does not check that the # of sub public keys is > 0, which leads to invalid ValidatedPublicKey objects against which no signature will verify, since signature_verify_strict_internal will reject such invalid PKs. This is not a security issue, but a correctness issue. See bugfix_validated_pk_from_zero_subpks.
It charges too much gas: if the first sub-PK is invalid, it will charge for verifying all remaining sub-PKs.

DEPRECATES:

new_validated_public_key_from_bytes
public_key_validate

Return true if the bytes in public_key can be parsed as a valid MultiEd25519 public key: i.e., all underlying PKs pass point-on-curve and not-in-small-subgroup checks. Returns false otherwise.

fun public_key_validate_internal(bytes: vector<u8>): bool

Implementation

native fun public_key_validate_internal(bytes: vector<u8>): bool;

`public_key_validate_v2_internal`

Return true if the bytes in public_key can be parsed as a valid MultiEd25519 public key: i.e., all underlying sub-PKs pass point-on-curve and not-in-small-subgroup checks. Returns false otherwise.

fun public_key_validate_v2_internal(bytes: vector<u8>): bool

Implementation

native fun public_key_validate_v2_internal(bytes: vector<u8>): bool;

`signature_verify_strict_internal`

Return true if the MultiEd25519 multisignature on message verifies against the MultiEd25519 public_key. Returns false if either:

The PKs in public_key do not all pass points-on-curve or not-in-small-subgroup checks,
The signatures in multisignature do not all pass points-on-curve or not-in-small-subgroup checks,
the multisignature on message does not verify.

fun signature_verify_strict_internal(multisignature: vector<u8>, public_key: vector<u8>, message: vector<u8>): bool

Implementation

native fun signature_verify_strict_internal(
    multisignature: vector<u8>,
    public_key: vector<u8>,
    message: vector<u8>
): bool;

Specification

`new_unvalidated_public_key_from_bytes`

public fun new_unvalidated_public_key_from_bytes(bytes: vector<u8>): multi_ed25519::UnvalidatedPublicKey

include NewUnvalidatedPublicKeyFromBytesAbortsIf;
ensures result == UnvalidatedPublicKey { bytes };

schema NewUnvalidatedPublicKeyFromBytesAbortsIf {
    bytes: vector<u8>;
    let length = len(bytes);
    aborts_if length / INDIVIDUAL_PUBLIC_KEY_NUM_BYTES > MAX_NUMBER_OF_PUBLIC_KEYS;
    aborts_if length % INDIVIDUAL_PUBLIC_KEY_NUM_BYTES != THRESHOLD_SIZE_BYTES;
}

`new_validated_public_key_from_bytes`

public fun new_validated_public_key_from_bytes(bytes: vector<u8>): option::Option<multi_ed25519::ValidatedPublicKey>

aborts_if false;
let cond = len(bytes) % INDIVIDUAL_PUBLIC_KEY_NUM_BYTES == THRESHOLD_SIZE_BYTES
    && spec_public_key_validate_internal(bytes);
ensures cond ==> result == option::spec_some(ValidatedPublicKey{bytes});
ensures !cond ==> result == option::spec_none<ValidatedPublicKey>();

`new_validated_public_key_from_bytes_v2`

public fun new_validated_public_key_from_bytes_v2(bytes: vector<u8>): option::Option<multi_ed25519::ValidatedPublicKey>

let cond = spec_public_key_validate_v2_internal(bytes);
ensures cond ==> result == option::spec_some(ValidatedPublicKey{bytes});
ensures !cond ==> result == option::spec_none<ValidatedPublicKey>();

`new_signature_from_bytes`

public fun new_signature_from_bytes(bytes: vector<u8>): multi_ed25519::Signature

include NewSignatureFromBytesAbortsIf;
ensures result == Signature { bytes };

schema NewSignatureFromBytesAbortsIf {
    bytes: vector<u8>;
    aborts_if len(bytes) % INDIVIDUAL_SIGNATURE_NUM_BYTES != BITMAP_NUM_OF_BYTES;
}

`unvalidated_public_key_num_sub_pks`

public fun unvalidated_public_key_num_sub_pks(pk: &multi_ed25519::UnvalidatedPublicKey): u8

let bytes = pk.bytes;
include PkDivision;

`unvalidated_public_key_threshold`

public fun unvalidated_public_key_threshold(pk: &multi_ed25519::UnvalidatedPublicKey): option::Option<u8>

aborts_if false;
ensures result == spec_check_and_get_threshold(pk.bytes);

`validated_public_key_num_sub_pks`

public fun validated_public_key_num_sub_pks(pk: &multi_ed25519::ValidatedPublicKey): u8

let bytes = pk.bytes;
include PkDivision;

`validated_public_key_threshold`

public fun validated_public_key_threshold(pk: &multi_ed25519::ValidatedPublicKey): u8

aborts_if len(pk.bytes) == 0;
ensures result == pk.bytes[len(pk.bytes) - 1];

`check_and_get_threshold`

public fun check_and_get_threshold(bytes: vector<u8>): option::Option<u8>

aborts_if false;
ensures result == spec_check_and_get_threshold(bytes);

schema PkDivision {
    bytes: vector<u8>;
    result: u8;
    aborts_if len(bytes) / INDIVIDUAL_PUBLIC_KEY_NUM_BYTES > MAX_U8;
    ensures result == len(bytes) / INDIVIDUAL_PUBLIC_KEY_NUM_BYTES;
}

`public_key_bytes_to_authentication_key`

fun public_key_bytes_to_authentication_key(pk_bytes: vector<u8>): vector<u8>

pragma opaque;
aborts_if false;
ensures [abstract] result == spec_public_key_bytes_to_authentication_key(pk_bytes);

`public_key_validate_internal`

fun public_key_validate_internal(bytes: vector<u8>): bool

pragma opaque;
aborts_if false;
ensures (len(bytes) / INDIVIDUAL_PUBLIC_KEY_NUM_BYTES > MAX_NUMBER_OF_PUBLIC_KEYS) ==> (result == false);
ensures result == spec_public_key_validate_internal(bytes);

`public_key_validate_v2_internal`

fun public_key_validate_v2_internal(bytes: vector<u8>): bool

pragma opaque;
ensures result == spec_public_key_validate_v2_internal(bytes);

`signature_verify_strict_internal`

fun signature_verify_strict_internal(multisignature: vector<u8>, public_key: vector<u8>, message: vector<u8>): bool

pragma opaque;
aborts_if false;
ensures result == spec_signature_verify_strict_internal(multisignature, public_key, message);

Helper functions

fun spec_check_and_get_threshold(bytes: vector<u8>): Option<u8> {
   let len = len(bytes);
   if (len == 0) {
       option::none<u8>()
   } else {
       let threshold_num_of_bytes = len % INDIVIDUAL_PUBLIC_KEY_NUM_BYTES;
       let num_of_keys = len / INDIVIDUAL_PUBLIC_KEY_NUM_BYTES;
       let threshold_byte = bytes[len - 1];
       if (num_of_keys == 0 || num_of_keys > MAX_NUMBER_OF_PUBLIC_KEYS || len % INDIVIDUAL_PUBLIC_KEY_NUM_BYTES != 1) {
           option::none<u8>()
       } else if (threshold_byte == 0 || threshold_byte > (num_of_keys as u8)) {
           option::none<u8>()
       } else {
           option::spec_some(threshold_byte)
       }
   }
}

fun spec_signature_verify_strict_internal(
   multisignature: vector<u8>,
   public_key: vector<u8>,
   message: vector<u8>
): bool;

fun spec_public_key_validate_internal(bytes: vector<u8>): bool;

fun spec_public_key_validate_v2_internal(bytes: vector<u8>): bool;

fun spec_public_key_bytes_to_authentication_key(pk_bytes: vector<u8>): vector<u8>;

fun spec_signature_verify_strict_t<T>(signature: Signature, public_key: UnvalidatedPublicKey, data: T): bool {
   let encoded = ed25519::new_signed_message<T>(data);
   let message = bcs::serialize(encoded);
   spec_signature_verify_strict_internal(signature.bytes, public_key.bytes, message)
}