Updates to Blockchain Commons Crypto Stack

Wolf McNally
Blockchain Commons

February 3, 2025

Revised: February 28, 2025

All the changes described in this document been made in the Rust stack, and have not yet been propagated to our Swift stack. Except where noted, pains have been taken to ensure backward-compatibility with all existing serialized structures.

The most relevant crates along with their most recent version numbers:

• bc-components 0.17.0
• bc-envelope 0.23.0
• provenance-mark 0.5.0
• bc-xid 0.5.0
• gstp 0.5.0

Adoption of Post-Quantum Methods

Our stack has been updated to incorporate a new method of encryption: ML-KEM (Module Lattice Key Encapsulation Method, NIST FIPS 203), and a new method of signing: ML-DSA (Module Lattice Digital Signature Algorithm, NIST FIPS 204). Both of these methods are designed to be resistant to future attacks from quantum algorithms.

Note: These versions represent the transition from the previousm post-quantum algorithms Dilithium and Kyber to the updated algorithms ML-DSA and ML-KEM. This is a BREAKING CHANGE, and the signatures and encrypted messages created with the old algorithms are not compatible with the new algorithms.

We support three levels of each:

• NKDSA44, MLDSA65, and MLDSA87
• MLKEM512, MLKEM768, and MLKEM1024

In general these methods require much larger keys and require more compute, storage, and bandwidth to deploy, and are thus are overkill for all applications but those needing highly sensitive data to survive state of the art attack for the next 10-50 years.

API Implications of adopting Post-Quantum Methods

All of the previous public key cryptography algorithms we have used in our stack allow the private key to be generated from user-supplied seed material (PrivateKeyBase) and generate from that the specific private and public keys for various signature and encryption algorithms.

In contrast to this, both the pqcrypto-mlkem and pqcrypto-mldsa crates we have adopted have very opinionated APIs that require that a private/public keypair be generated internally and delivered as a tuple. While we're sure we could subvert this to create deterministic tests and examples, and derivation of public from private keys, we decided to make this paradigm available (and recommended) throughout our stack, without removing the ability to generate private and public keys separately for classical algorithms.

Changed Type Names

AgreementPrivateKey -> X25519PrivateKey

AgreementPublicKey -> X25519PublicKey

The term "key agreement" in our stack has become a bit problematic, because the reason we are using the X25519 algorithm is solely to securely transmit an ephemeral symmetric key (the "content key") from a sender to a recipient. This is done via a SealedMessage. The technical name for this technique is "key encapsulation" and this is the term ML-KEM uses. Again, rather than contradict this terminology we decided to adopt it, introducing a generic set of Encapsulation keys that can contain X25519 or ML-KEM keys. So renaming the Agreement keys to X25519 made the algorithm they use explicit.

pub enum EncapsulationPrivateKey {
    X25519(X25519PrivateKey),
    MLKEM(MLKEMPrivateKey),
}

pub enum EncapsulationPublicKey {
    X25519(X25519PublicKey),
    MLKEM(MLKEMPublicKey),
}

The actual encapsulated key now has its own type:

pub enum EncapsulationCiphertext {
    X25519(X25519PublicKey),
    MLKEM(MLKEMCiphertext)
}

And this is the type that is encoded in a SealedMessage:

pub struct SealedMessage {
    message: EncryptedMessage,
    encapsulated_key: EncapsulationCiphertext,
}

Note that the serialization of an EncapsulatedCiphertext is either a X25519PublicKey or a MLKEMCiphertext, which is binary-compatible with older implementations always expecting an X25519PublicKey (formerly AgreementPublicKey) in this position. All CBOR tags and encoding remain the same unless you are using ML-KEM.

PublicKeyBase -> PublicKeys

This was to bring it in line with its actual function, and allow a new type to be introduced, PrivateKeys with the analogous function of storing a private keys for signing and encryption as a single unit.

pub struct PublicKeys {
    signing_public_key: SigningPublicKey,
    encapsulation_public_key: EncapsulationPublicKey,
}

For PublicKeys (formerly PublicKeyBase) the CBOR tag and UR type remain the same: ur:crypto-pubkeys.

ur:crypto-prvkeys -> ur:crypto-prvkey-base

This is a textual change to the UR type only: the CBOR tag for a PrivateKeyBase remains the same, however existing URs with the old type will need to be renamed, and our Rust stack and Research repo have already been updated.

PrivateKeyBase still exists and operates the same as it always has: as a store of key material from which specific private and public keys can be derived– for algorithms that let us do that, but not all do.

Introducing PrivateKeys

The previous change gives us the namespace opening we need to introduce a new definition of ur:crypto-prvkeys which is fully analogous to ur:crypto-pubkeys, along with a new CBOR tag, the previously-unassigned #6.40013.

pub struct PrivateKeys {
    signing_private_key: SigningPrivateKey,
    encapsulation_private_key: EncapsulationPrivateKey,
}

This is to make how we handle key pair handling consistent throughout our stack, and accomodate the opinionated API of the ML-DSA and ML-KEM implementations.

Introducing SignatureScheme

All the changes above have enable us to unify our signing API throughout our stack. The new type SignatureScheme enumerates all the signature types we now support, including ML-DSA.

pub enum SignatureScheme {
    #[default]
    Schnorr,
    Ecdsa,
    Ed25519,
    NKDSA44,
    MLDSA65,
    MLDSA87,
    SshEd25519,
    SshDsa,
    SshEcdsaP256,
    SshEcdsaP384,
}

Every signature scheme can easily generate a key pair. Both the private and public keys must be stored and managed; this paradigm does not permit deriving the public key from the private key later.

let (private_key, public_key) = SignatureScheme::Ed25519.keypair();

Signing is done with the private key:

let signature = private_key.sign(MESSAGE)?;

The paired public key is the only key that will verify the message:

assert!(public_key.verify(&signature, MESSAGE));

Using a different scheme like ML-DSA is just the same:

let (private_key, public_key) = SignatureScheme::NKDSA44.keypair();
let signature = private_key.sign(MESSAGE)?;
assert!(public_key.verify(&signature, MESSAGE));

Note that the SSH schemes require additional parameters, so the sign_with_options method must be used for those.

As noted in the enum, Schnorr (BIP-340) is the default, so you can simply write:

let (private_key, public_key) = SignatureScheme::default().keypair();

Introducing EncapsulationScheme

Like SignatureScheme, the new EncapsulationScheme type unifies all the key encapsulation methods we support. Formerly we only supported X25519 and now we additionally support all three levels of ML-KEM:

pub enum EncapsulationScheme {
    #[default]
    X25519,
    MLKEM512,
    MLKEM768,
    MLKEM1024,
}

Our default is X25519, so a key pair is created like this:

let (private_key, public_key) = EncapsulationScheme::default().keypair();

For a ML-KEM key pair:

let (private_key, public_key) = EncapsulationScheme::MLKEM512.keypair();

To use the key pair, the sender uses the receiver's public key to generate a secret (returned as a SymmetricKey) and the ciphertext (returned as an EncapsulationCiphertext):

let (content_key, ciphertext) = public_key.encapsulate_new_shared_secret();

Using the content key, the sender encrypts the payload into an EncryptedMessage and sends it along with the ciphertext in a SealedMessage. This is typically done with a Gordian Envelope.

The receiver uses their private key to decrypt the ciphertext back into the content key and uses it to decrypt the payload

let content_key = private_key.decapsulate_shared_secret(&ciphertext)?;

Introducing the top-level keypair() and keypair_opt()

The bc-components crate has new top-level functions used to create PrivateKeys/PublicKeys pairs, each of which contains a signing key and an encapsulation key. To create a keypair with the default BIP-340 Schnorr scheme for signing and an X25519 key for encryption:

let (private_key, public_key) = keypair();

To fully-customize the schemes for signing and encryption, use keypair_opt():

let (sender_private_keys, sender_public_keys) = keypair_opt(
    SignatureScheme::NKDSA44,
    EncapsulationScheme::MLKEM512
);

Impact on Gordian Envelope

Previous methods of signing and encrypting Gordian Envelopes all still work, but have been extended to support SignatureScheme and EncapsulationScheme.

So for signing:

// Signer
let (private_key, public_key) = SignatureScheme::NKDSA44.keypair()
let envelope = hello_envelope()
    .sign(&private_key)?;

// Verifier
envelope.verify(&public_key)?;

And for encryption:

// Receiver
let (private_key, public_key) = EncapsulationScheme::MLKEM512.keypair();

// Sender
let envelope = hello_envelope();
let encrypted_envelope = envelope
    .encrypt_to_recipient(&public_key)?;

// Receiver
let decrypted_envelope = encrypted_envelope
    .decrypt_to_recipient(&private_key)?;

Note that the keypair functions introduced earlier can be used for both signing and encryption:

// Sender generates their keys
let (sender_private_keys, sender_public_keys) = keypair_opt(
    SignatureScheme::NKDSA44,
    EncapsulationScheme::MLKEM512
);

// Recipient generates their keys
let (recipient_private_keys, recipient_public_key) = keypair_opt(
    SignatureScheme::NKDSA44,
    EncapsulationScheme::MLKEM512
);

// Sender and Recipient exchange public keys.

// Sender sends a signed and encrypted message to Recipient:
let sealed_envelope = hello_envelope()
    .seal(sender_private_key, recipient_public_key);

// Recipient decrypts the envelope and verifies Sender's signature
let unsealed_envelope = sealed_envelope
    .unseal(recipient_private_key, sender_public_key)?;

Impact on XID and GSTP

The main thing is that the keys you use to create XID documents and GSTP messages generally have moved away from PrivateKeyBase and toward PrivateKeys and PublicKeys. The bc-envelope, bc-xid, and gstp crates all now have unit tests that demonstrate their used with both classical and post-quantum algorithms, and we recommend giving them a look, just search the codebases for MLDSA and MLKEM.