Module hash_based_sig 

XMSS signature verification.

The scheme is the one leanVM-b’s xmss crate implements. Every parameter, every tweak and every step of verification is the same, so a signature is the same construction:

• a Winternitz one-time signature over V chains of length CHAIN_LENGTH, with a target-sum encoding and no checksum chains,
• whose chain ends hash into a Merkle leaf,
• which an authentication path links to the committed root.

The tweakable hash under it is the one thing that differs, and differs twice over: BLAKE3 rather than BLAKE2s, keyed rather than prefixed. The reference hashes the byte string tweak | pp | payload; here pp | tweak is the BLAKE3 key and the payload is the whole message. The two are 32 bytes together, exactly a key, so the domain fits it with nothing left to pad. Digests therefore do not agree with the reference’s — the schemes are the same, the instantiations are not.

Keying also takes the domain out of the payload, which is what makes the message encoding one compression rather than two. A native verification is a constant 143:

1 (encoding) + 99 (chains, fixed by the target sum) + 11 (leaf) + 32 (path) = 143

In circuit the chain work is not the 99 steps a verifier walks but every one of the V * (CHAIN_LENGTH - 1) = 294: each step’s tweak is a circuit constant, so a chain has to evaluate all of its steps and take the hashed value only past its digit. The target sum buys encoding validity here rather than verifier work.

Those 294 run two chains to a core, as the two 32-bit lanes of one paired BLAKE3 compression, so they cost 147 cores beside the 44 lone compressions of the encoding, the leaf and the path.

Example

Sign a message and verify it, out of circuit:

use binius_circuits::hash_based_sig::{MESSAGE_LEN, xmss};
use rand::{Rng, SeedableRng, rngs::StdRng};

let mut rng = StdRng::seed_from_u64(0);
let mut message = [0u8; MESSAGE_LEN];
rng.fill_bytes(&mut message);

let epoch = 42;
let (public_key, signature) = xmss::generate_signature(&mut rng, &message, epoch);
xmss::xmss_verify(&public_key, &message, &signature, epoch).unwrap();

// The same signature at any other epoch is not a signature.
assert!(xmss::xmss_verify(&public_key, &message, &signature, epoch + 1).is_err());

xmss::circuit_xmss_verify is the in-circuit form of that check, and aggregate::circuit_xmss_multisig runs it for several signers over one message.

CREDIT: https://github.com/leanEthereum/leanVM-b (XMSS construction).

Modules

aggregate

Aggregation of XMSS signatures on a common message.

hashing

The XMSS hash layer: tweak_hash is the BLAKE3 keyed hash of the payload under pp | tweak, truncated to 16 bytes, for chain steps, Merkle nodes, WOTS public keys and message encodings alike.

wots

WOTS (Winternitz one-time signature) with target-sum encoding.

xmss

XMSS: a Merkle tree of 2^LOG_LIFETIME WOTS public-key hashes.

Constants

CHAIN_LENGTH

Chain length: a digit selects one of 2^W positions.

DIGEST_LEN

Digest length in bytes: n = 128 bits.

DIGEST_WIRES

A digest as 64-bit little-endian wires.

LOG_LIFETIME

Merkle tree height: a key is valid for up to 2^LOG_LIFETIME epochs.

MESSAGE_LEN

The message to sign: a 256-bit message hash.

MESSAGE_WIRES

Wires holding a message.

NUM_CHAIN_HASHES

Chain hashes the verifier walks, summed over all chains: sum(CHAIN_LENGTH - 1 - e_i).

PUBLIC_PARAM_LEN

Public parameter length in bytes. The parameter separates users.

PUBLIC_PARAM_WIRES

Wires holding a public parameter.

RANDOMNESS_LEN

Signature randomness length in bytes, ground until the encoding is valid.

RANDOMNESS_WIRES

Wires holding the randomness.

TARGET_SUM

A WOTS encoding (e_0, .., e_{V-1}) is valid exactly when every e_i < CHAIN_LENGTH, the digits sum to this, and the two leftover digest bits are zero.

V

Number of Winternitz hash chains.

W

Bits per encoding digit.

Type Aliases

Digest

A 128-bit digest.

Message

The message to sign.

PublicParam

A per-signer public parameter.

Randomness

Signature randomness.