binius_circuits/hash_based_sig/
mod.rs

1// Copyright 2026 The Binius Developers
2// Copyright (c) 2026 leanEthereum
3//! XMSS signature verification.
4//!
5//! The scheme is the one leanVM-b's `xmss` crate implements. Every parameter, every tweak and
6//! every step of verification is the same, so a signature is the same construction:
7//!
8//! - a Winternitz one-time signature over [`V`] chains of length [`CHAIN_LENGTH`], with a
9//!   target-sum encoding and no checksum chains,
10//! - whose chain ends hash into a Merkle leaf,
11//! - which an authentication path links to the committed root.
12//!
13//! The tweakable hash under it is the one thing that differs, and differs twice over: BLAKE3
14//! rather than BLAKE2s, keyed rather than prefixed. The reference hashes the byte string
15//! `tweak | pp | payload`; here `pp | tweak` is the BLAKE3 key and the payload is the whole
16//! message. The two are 32 bytes together, exactly a key, so the domain fits it with nothing left
17//! to pad. Digests therefore do not agree with the reference's — the schemes are the same, the
18//! instantiations are not.
19//!
20//! Keying also takes the domain out of the payload, which is what makes the message encoding one
21//! compression rather than two. A native verification is a constant 143:
22//!
23//! ```text
24//! 1 (encoding) + 99 (chains, fixed by the target sum) + 11 (leaf) + 32 (path) = 143
25//! ```
26//!
27//! In circuit the chain work is not the 99 steps a verifier walks but every one of the
28//! `V * (CHAIN_LENGTH - 1) = 294`: each step's tweak is a circuit constant, so a chain has to
29//! evaluate all of its steps and take the hashed value only past its digit. The target sum buys
30//! encoding validity here rather than verifier work.
31//!
32//! Those 294 run two chains to a core, as the two 32-bit lanes of one paired BLAKE3 compression,
33//! so they cost 147 cores beside the 44 lone compressions of the encoding, the leaf and the path.
34//!
35//! # Example
36//!
37//! Sign a message and verify it, out of circuit:
38//!
39//! ```
40//! use binius_circuits::hash_based_sig::{MESSAGE_LEN, xmss};
41//! use rand::{Rng, SeedableRng, rngs::StdRng};
42//!
43//! let mut rng = StdRng::seed_from_u64(0);
44//! let mut message = [0u8; MESSAGE_LEN];
45//! rng.fill_bytes(&mut message);
46//!
47//! let epoch = 42;
48//! let (public_key, signature) = xmss::generate_signature(&mut rng, &message, epoch);
49//! xmss::xmss_verify(&public_key, &message, &signature, epoch).unwrap();
50//!
51//! // The same signature at any other epoch is not a signature.
52//! assert!(xmss::xmss_verify(&public_key, &message, &signature, epoch + 1).is_err());
53//! ```
54//!
55//! [`xmss::circuit_xmss_verify`] is the in-circuit form of that check, and
56//! [`aggregate::circuit_xmss_multisig`] runs it for several signers over one message.
57//!
58//! CREDIT: <https://github.com/leanEthereum/leanVM-b> (XMSS construction).
59
60pub mod aggregate;
61pub mod hashing;
62pub mod wots;
63pub mod xmss;
64
65/// Digest length in bytes: n = 128 bits.
66pub const DIGEST_LEN: usize = 16;
67
68/// A digest as 64-bit little-endian wires.
69pub const DIGEST_WIRES: usize = DIGEST_LEN / 8;
70
71/// Public parameter length in bytes. The parameter separates users.
72pub const PUBLIC_PARAM_LEN: usize = 16;
73
74/// Wires holding a public parameter.
75pub const PUBLIC_PARAM_WIRES: usize = PUBLIC_PARAM_LEN / 8;
76
77/// Signature randomness length in bytes, ground until the encoding is valid.
78pub const RANDOMNESS_LEN: usize = 24;
79
80/// Wires holding the randomness.
81pub const RANDOMNESS_WIRES: usize = RANDOMNESS_LEN / 8;
82
83/// The message to sign: a 256-bit message hash.
84pub const MESSAGE_LEN: usize = 32;
85
86/// Wires holding a message.
87pub const MESSAGE_WIRES: usize = MESSAGE_LEN / 8;
88
89/// Number of Winternitz hash chains.
90pub const V: usize = 42;
91
92/// Bits per encoding digit.
93pub const W: usize = 3;
94
95/// Chain length: a digit selects one of `2^W` positions.
96pub const CHAIN_LENGTH: usize = 1 << W;
97
98/// Chain hashes the verifier walks, summed over all chains: `sum(CHAIN_LENGTH - 1 - e_i)`.
99///
100/// Constant because the encoding sum is fixed to [`TARGET_SUM`].
101pub const NUM_CHAIN_HASHES: usize = 99;
102
103/// A WOTS encoding `(e_0, .., e_{V-1})` is valid exactly when every `e_i < CHAIN_LENGTH`, the
104/// digits sum to this, and the two leftover digest bits are zero.
105///
106/// The signer grinds the randomness until the encoding is valid, which is what replaces the
107/// checksum chains. 195 sits above the mean of 147 so the verifier walks fewer chain steps.
108pub const TARGET_SUM: usize = V * (CHAIN_LENGTH - 1) - NUM_CHAIN_HASHES;
109
110/// Merkle tree height: a key is valid for up to `2^LOG_LIFETIME` epochs.
111pub const LOG_LIFETIME: usize = 32;
112
113/// A 128-bit digest.
114pub type Digest = [u8; DIGEST_LEN];
115
116/// A per-signer public parameter.
117pub type PublicParam = [u8; PUBLIC_PARAM_LEN];
118
119/// Signature randomness.
120pub type Randomness = [u8; RANDOMNESS_LEN];
121
122/// The message to sign.
123pub type Message = [u8; MESSAGE_LEN];
124
125// The encoding uses V*W = 126 of the digest's 128 bits; the 2 leftover top bits are ground to
126// zero, so the digest decomposes exactly into the digits.
127const _: () = assert!(V * W + 2 == DIGEST_LEN * 8);
128
129// The target sum is what fixes the verifier's chain work.
130const _: () = assert!(TARGET_SUM == 195);
binius_circuits/hash_based_sig/mod.rs

binius_circuits/hash_based_sig/
mod.rs
