Index Mathematics Conjectures nbv lettuce Widgets

Standard library

Every .nbv file under stdlib/ is a function named after the file, available to every program without an import. Functions in a directory named after a field (milli, mersenne61, dilithium) are only loaded when compiling for that field; a name can exist in several field directories but not also in a shared one. This reference is generated from the sources by cargo run -p nbv-docs.

stdlib

calloc(k)get a vector of length `k` initialized with zeroes
copy_into(from, mut to, i)copy the elements of `from` into `to` starting at index `i` of `to`
extend_to(target_len, input)Extend a vector to a target length by appending zeroes.
inner_prod(lhs, rhs)Take two vectors.
is_zero(v)does the structure contain nothing but `0` elements? outputs `0` or `1`
mat_index(mat_vec, i, j, width)
mat_transpose(static width, mat)
mat_vec_mul(mat, vec)
negone()lol
pow(static pow, v)TODO: use logarithmic complexity for exponentiation
pow11(v)
pow17(v)
pow5(v)
pow5_static(v)
reverse_static(input)
shift(static k, input)Circularly shift the elements of a vector by index to input_i = input_{i - k mod (len! input)}
size_cyclic(l, v)given a vector `v`, extend to length `l` by repetition, or truncate if `l` is shorter than `len! v`.
slice(v, start_i, len)get the `len` elements of `v` from `start_i` e.g.
slice_from_start(v, len)get the first `len` elements of `v` e.g.
slice_to_end(v, start_i)get the elements of `v` after `start_i` e.g.
split_at(split_i, input)Split a vector in two at an index.
sum(input)sum a vector of length T of dimension >= 1
sym_mat_index(static i, static j, diag, triag)access an element in a symmetric matrix input matrix must be square
valloc(k, v)get a vector of length `k` initialized with element `v`

stdlib/bdlop

bdlop_lattice(static N, static msg_len)standardized A_1 and A_2 matrices (lattice bases) for BDLOP commitments and arguments
bdlop_linear_nizk_comm(static N, static msg_len, let arg)extract the commitment elements from an nizk arg
bdlop_linear_nizk_verify(static N, static msg_len, let state, let g, let arg)arg should be the vectorized BDLOPLinearNIZK struct
bdlop_milli_config(N, msg_len)page 10 and 22 of more efficient vector commitments lettuce/src/commitments/bdlop/spec.pdf https://eprint.iacr.org/2016/997
bdlop_r1cs_verify(static N, static r_a, static r_b, static r_c, let w, let s, let wtns_arg, let crossterm_arg, let state)number of polynomials to represent wtns

stdlib/bits

add32_bits(sum, static terms)Word-wise sum mod 2^32 of `terms` equal length vectors of 32-bit words, each word 32 little-endian bits, passed as their element-wise sum `sum` (e.g.
and_bits(lhs, rhs)
bytes_to_bits(bytes)Constrain a vector of bytes to 8 little-endian bits each and return all of the bits, byte i at 8 i ..
bytes_to_bits_static(static bytes)Little-endian bits of a vector of static byte values, byte i at 8 i ..
from_bits(bits)combine little-endian bits into a single element works for both static and witness bits
from_bits_static(input)
lt_bits(lhs, rhs)return 1 if lhs is less than rhs lhs and rhs should both be vectors of bits
lte_bits(lhs, rhs)return 1 if lhs is less than or equal to rhs lhs and rhs should both be vectors of bits
lte_negone(input)return 1 if input is less than or equal to negative 1 input should be a vector of bits
one_hot_bits(bits, scale)One-hot encoding of the value of little-endian `bits`, scaled by `scale`.
or_bits(lhs, rhs)0 + 0 - 0 * 0 = 0 1 + 0 - 1 * 0 = 1 0 + 1 - 0 * 1 = 1 1 + 1 - 1 * 1 = 1
rotl32_bits(words, static r)Rotate each 32-bit word of a vector of little-endian bits left by `r`, as a slice of the doubled word
to_bits(input)convert an element into a constrained vector of bits
to_bits_exact(input, bitlen)convert an element to an exact number of bits constraining equality
to_bits_exact_static(input, bitlen)convert an element to an exact number of bits constraining equality
u32_bits_static(static x)32 little-endian bits of a static value, which must be below the field characteristic.
xor_bits(lhs, rhs)1 + 0 - 2 * 1 * 0 = 1 0 + 1 - 2 * 0 * 1 = 1 1 + 1 - 2 * 1 * 1 = 0 0 + 0 - 2 * 0 * 0 = 0
xor_bits_vec(lhs, rhs)xor of two equal length vectors of bits, element-wise.
xor_bits_vec_wtns(lhs, rhs)xor of two equal length vectors of bits, element-wise, as fresh witness bits.

stdlib/blake3

BLAKE3 on bit vectors: blake3 (hash), blake3_keyed and blake3_derive_key, all with extended output, on top of blake3_core.

Words are 32 little-endian bits, added in 16-bit limbs (add32_bits) so the arithmetic is sound in every field nbv supports. blake3_compress works on a batch of inputs, so all full chunks compress together block by block, each level of parents is one call and so are the extended output blocks. One compression is about 15.7k rows.

Witness inputs only, like chacha: a static key (the IV of the plain hash) is materialized once with wtns! (256 rows) so no word addition is entirely static.

blake3(input, static out_len)BLAKE3 hash of `input` bits (whole bytes, least significant bit of each byte first), returning `out_len` bits.
blake3_compress(cv, block, params, static out_words, static fresh)The BLAKE3 compression function on a batch of B inputs.
blake3_core(key, static flags, input, static out_len)BLAKE3 hash tree over `input` bits with a 256-bit `key` (the IV for the plain hash) and the mode `flags` (0, KEYED_HASH = 16, DERIVE_KEY_CONTEXT = 32 or DERIVE_KEY_MATERIAL = 64), returning `out_len` bits of extended output.
blake3_derive_key(context, material, static out_len)BLAKE3 key derivation: the `context` string bits are hashed into a context key, which keys the hash of the `material` bits.
blake3_g(state, mx, my)The BLAKE3 G function on every column of a batch of states.
blake3_keyed(key, input, static out_len)BLAKE3 keyed hash of `input` bits under a 256-bit `key`, returning `out_len` bits.
blake3_rotate_rows(state, static kb, static kc, static kd)Rotate the words of rows b, c and d of a batch of BLAKE3 states (see blake3_g) left by `kb`, `kc` and `kd` words.
blake3_rotate_words(row, static k)Rotate the 4 words of every 128-bit group of `row` left by `k` words, k in 1..4

stdlib/chacha

ChaCha20 and ChaCha8 block functions on bit vectors (chacha20_block, chacha8_block, both thin wrappers around chacha_block).

Words are 32 little-endian bits. A 32-bit word does not fit in every field nbv supports (Milli has p < 2^32, the dilithium field q < 2^24), so word additions are done in two 16-bit limbs (add32_bits), xors with xor_bits_vec_wtns and rotations as free slices. The four quarter rounds of a column or diagonal round run in parallel on whole 128-bit rows.

Witness inputs only: add32_bits uses to_bits_exact, which does not accept static values, so a block can't be evaluated with static_eval!.

chacha20_block(key, iv)ChaCha20 block function, see chacha_block.
chacha8_block(key, iv)ChaCha8 block function, see chacha_block.
chacha_block(static rounds, key, iv)ChaCha block function with `rounds` rounds (20 for ChaCha20, 8 for ChaCha8) on bit vectors, returning the 512-bit keystream block.
chacha_quarter_round(state)Four ChaCha quarter rounds in parallel on a 512-bit state, word i at bits 32 i ..

stdlib/dilithium/ext

ext_degree()Degree D of the binomial extension Z_q[x] / (x^D - c) of the Dilithium field used for the SLIP sumcheck challenges (dags DilithiumScalar::EXT_DEGREE): q^6 is about 2^138
ext_nonresidue()The constant c of the extension Z_q[x] / (x^D - c) of the Dilithium field, D = ext_degree() (dags DilithiumScalar::EXT_NONRESIDUE): the smallest c >= 2 that is neither a square nor a cube, so x^6 - c is irreducible

stdlib/dilithium/lattice

lattice_kappa()State width of the lattice sponge in the Dilithium field (dags LatticeBlake3 KAPPA): the smallest state of at least 256 bits of 22
lattice_output_len()Output elements of the lattice sponge squeeze in the Dilithium field (dags LatticeBlake3)
lattice_permutation(state)The squeeze of the lattice sponge in the Dilithium field, BLAKE3 in place of a Poseidon permutation (dags LatticeBlake3): `state` is laid out as lattice_squeeze builds it, the output lanes, then the lattice state and the absorbed length.
lattice_t()Squeeze state width of the lattice sponge in the Dilithium field: the output lanes, the lattice state and the length tag, with no spare lanes (BLAKE3 has no permutation width)

stdlib/dilithium/mldsa

mldsa44_verify(pk, msg, sig)ML-DSA-44 signature verification (FIPS 204 Algorithms 3 and 8) with an empty context string, in the field Z_q itself (q = 8380417).
mldsa44_verify_static(static pk, static msg, sig)ML-DSA-44 signature verification (FIPS 204 Algorithms 3 and 8) with an empty context string, in the field Z_q itself, for a public key and message known at compile time.
mldsa44_w_approx(a_hat, v_bits, c, t1)w_approx = NTT^-1(A_hat NTT(z) - NTT(c) NTT(2^13 t1)) for ML-DSA-44 in the field Z_q itself (FIPS 204 Algorithm 8, step 7).
mldsa44_w_approx_static(static a_hat, v_bits, c, static t_hat)w_approx = NTT^-1(A_hat NTT(z) - NTT(c) t_hat) for ML-DSA-44 in the field Z_q itself (FIPS 204 Algorithm 8, step 7), with A_hat and t_hat known at compile time.
mldsa_intt_native(y)NTT^-1 over Z_q (FIPS 204 Algorithm 42) in the field Z_q itself, where it is a linear map.
mldsa_ntt_native(u, static f)NTT over Z_q (FIPS 204 Algorithm 41) of polynomials scaled by f, in the field Z_q itself, where it is a linear map.
mldsa_zeta_table_native(static f)Static table of f * zeta^e for e in 0..512 in the field Z_q itself, where zeta = 1753 is the primitive 512th root of unity used by ML-DSA

stdlib/ext

Arithmetic in the binomial extension F = Z_q[x] / (x^D - c) of the field used for the SLIP sumcheck challenges (dags Ext<E>, FieldScalar::EXT_DEGREE and EXT_NONRESIDUE). D and c come from the field namespace shims stdlib/<field>/ext/ext_degree and ext_nonresidue:

| field | D | c | field size | |------------|---|----|------------| | Mersenne61 | 3 | 5 | ~2^183 | | Milli | 6 | 19 | ~2^192 | | Dilithium | 6 | 7 | ~2^138 |

An element is a vector of its D coefficients, low to high; a vector of elements is their concatenation, so element i is at D i .. D i + D.

The functions work on static and witness values alike. A product of two witness elements costs D^2 base products, a product by a base element D, additions are vector additions. ext_eq_table, ext_eq_eval and ext_mle_eval are the multilinear extension helpers of the dags sumcheck (slip/sumcheck.rs), used by the SLIP verifier. mle_eq_table is the base field eq table.

ext_eq_eval(rho, r)eq(rho, r) = prod_j (r_j (2 rho_j - 1) + 1 - rho_j) for a base field point `rho` and an extension point `r` of the same length (dags slip eq_eval)
ext_eq_table(r)eq(r, l) for every l in [2^len(r)] over the extension, bit j of l matched with r_j (dags slip eq_table_ext): a vector of 2^len(r) elements, D coefficients each
ext_from_base(v)A base field scalar as an element of the extension
ext_mle_eval(table, eq)Multilinear extension of a base field `table` at the point whose extension eq vector is `eq`: <table, eq> over the first len(table) elements of eq (dags slip mle_eval).
ext_mul(a, b)Product of two elements of the extension, schoolbook reduced with x^D = c (dags Ext::mul): D^2 base products.
ext_mul_base(a, s)Product of an element of the extension by a base field scalar `s` (dags Ext::mul_base): D base products
ext_one()The one of the extension
ext_poly_eval(coeffs, t)A polynomial over the extension given by its coefficients (low to high, one element each) evaluated at the element `t`, by Horner's rule (dags slip poly_eval)
ext_recompose(rows)sum_i 2^i rows_i for a vector of extension elements (dags slip recompose_bits): the value of a bit decomposed witness block from the evaluations of its rows.
ext_sum(vec)Sum of a vector of extension elements; the empty vector sums to zero
ext_vec_mul(vec, c)Every element of a vector of extension elements times the element `c`
ext_zero()The zero of the extension
mle_eq_table(rho)eq(rho, l) for every l in [2^len(rho)] over the base field, bit j of l matched with rho_j (dags slip eq_table): the weights of the multilinear extension at rho

stdlib/fields

assert_dilithium()prime field of cardinality 2^23 - 2^13 + 1, the ML-DSA modulus
assert_mersenne61()prime field of cardinality 2^61 - 1
assert_milli32()prime field of cardinality 2^32 - ~1mil

stdlib/keccak

keccak_f1600(state)Keccak-f[1600] permutation on a vector of 1600 bits.
keccak_sponge_shake(static rate, input, static out_len)SHAKE sponge over Keccak-f[1600] on bit vectors.
shake128(input, static out_len)SHAKE128 of a vector of bits, returning `out_len` bits
shake256(input, static out_len)SHAKE256 of a vector of bits, returning `out_len` bits

stdlib/lattice

The lattice transcript sponge of dags (dags/src/commitments/lattice_hash/spec.pdf, LatticeSponge<H>) as nbv functions, so a circuit can replay a Fiat-Shamir transcript in any field with a Poseidon instance.

Absorption is an Ajtai hash on the bits of the canonical values: the pending elements are cut into blocks of lattice_rate (64) elements, padded with 1, 0, ... to the block boundary, and each block is folded into a state of lattice_kappa (8) elements through the public matrix a_absorb (kappa x e (kappa + rate) for e = field_bit_width!). A squeeze runs the state through the field's Poseidon permutation (lattice_permutation) with the number of absorbed elements as a tag and reads lattice_output_len elements. Long challenge vectors are expanded from one squeeze through the second matrix a_exp (kappa x e (output_len + 1)), kappa elements per block, in counter mode.

The matrices are public and expanded from fixed seeds by dags (LatticeSponge::<H>::matrices()); pass them in as statics. Every absorbed witness element costs e binary rows for its bits, one row for the recomposition and a few rows for the canonical check (lattice_bits). The products by the matrices are linear.

lattice_oraccle_* mirror the dags Oraccle<LatticeSponge<H>>: the oracle state is the vector of pending elements, a squeeze hashes everything pending (the previous squeeze output first) and the output becomes the new state.

Field specific pieces live in stdlib/<field>/lattice: lattice_permutation, lattice_output_len and lattice_t (Milli: PoseidonMilli32_16, Mersenne61: PoseidonMersenne61_16_8).

lattice_absorb(state_bits, block_bits, static a_absorb)One compression of the lattice sponge: the new state `a_absorb (state_bits || block_bits)` for the bits of the current state followed by the bits of a block of `lattice_rate` elements.
lattice_assert_canonical(bits)Constrain `field_bit_width!` little-endian bits to encode a value below the field characteristic, so that the bit decomposition of a field element is unique.
lattice_bits(v)The `field_bit_width!` little-endian bits of the canonical value of a witness scalar, constrained to be bits, to recompose to the value and to be below the field characteristic (see lattice_assert_canonical).
lattice_bits_static(static v)The `field_bit_width!` little-endian bits of a static scalar
lattice_bits_vec(v)lattice_bits of every element of a witness vector, element i at e i ..
lattice_digest(pending, static a_absorb)The lattice state after absorbing `pending` and padding (dags LatticeSponge::digest): the elements are cut into blocks of `lattice_rate`, the last block is padded with a 1 and zeros (a whole new block when the buffer is full), and every block is compressed with lattice_absorb.
lattice_expand(seed, static len, static a_exp)A challenge vector of `len` elements from one squeeze output `seed` (dags LatticeSponge::sample_vector): up to `lattice_output_len` elements are the seed itself, longer vectors are the counter mode expansion `a_exp (bits(seed) || bits(i))`, `lattice_kappa` elements per block i.
lattice_oraccle_commit(input, state)Append elements to a lattice transcript oracle.
lattice_oraccle_init()A transcript oracle over the lattice sponge (dags Oraccle<LatticeSponge<H>>).
lattice_oraccle_sample(state, static a_absorb)Sample one uniform element from a lattice transcript oracle (dags Oraccle::sample_uniform): the first element of a squeeze.
lattice_oraccle_sample_vec(static len, state, static a_absorb, static a_exp)Sample `len` uniform elements from a lattice transcript oracle (dags Oraccle::sample_uniform_vector): one squeeze, expanded with lattice_expand.
lattice_oraccle_squeeze(state, static a_absorb)Squeeze a lattice transcript oracle: hash everything pending with lattice_squeeze.
lattice_rate()Elements absorbed per block of the lattice sponge (dags LATTICE_SPONGE_RATE)
lattice_squeeze(pending, static a_absorb)One squeeze of a fresh lattice sponge over `pending` (dags LatticeSponge::squeeze_safe): the padded digest is placed after the `lattice_output_len` output lanes of the Poseidon state, followed by the number of absorbed elements as a tag and zeros, the permutation is applied and the output lanes are returned.

stdlib/mersenne61/ext

ext_degree()Degree D of the binomial extension Z_q[x] / (x^D - c) of Mersenne61 used for the SLIP sumcheck challenges (dags Mersenne61Scalar::EXT_DEGREE): q^3 is about 2^183
ext_nonresidue()The constant c of the extension Z_q[x] / (x^D - c) of Mersenne61, D = ext_degree() (dags Mersenne61Scalar::EXT_NONRESIDUE): the cubic non-residue

stdlib/mersenne61/lattice

lattice_kappa()State width of the lattice sponge in field elements (dags LATTICE_SPONGE_KAPPA for the Poseidon squeeze)
lattice_output_len()Output lanes of the lattice sponge permutation in Mersenne61 (PoseidonMersenne61_16_8)
lattice_permutation(state)The Poseidon permutation of the lattice sponge in Mersenne61: PoseidonMersenne61_16_8, a state of lattice_t() = 24 elements
lattice_t()State width of the lattice sponge permutation in Mersenne61 (PoseidonMersenne61_16_8)

stdlib/mersenne61/mldsa

mldsa44_verify(pk, msg, sig)ML-DSA-44 signature verification (FIPS 204 Algorithms 3 and 8) with an empty context string, in the 61 bit Mersenne field.
mldsa44_w_approx(a_hat, v_bits, c, t1)w_approx = NTT^-1(A_hat NTT(z) - NTT(c) NTT(2^13 t1)) for ML-DSA-44 in the 61 bit Mersenne field (FIPS 204 Algorithm 8, step 7).
mldsa_intt(y)NTT^-1 over Z_q (FIPS 204 Algorithm 42) as a matrix product, in the 61 bit Mersenne field.
mldsa_ntt_q(u, static u_max, static negate, static offset, static scale)NTT over Z_q (FIPS 204 Algorithm 41) of polynomials w = s u + a, scaled by f, as a matrix product followed by one reduction per output.
mldsa_pointwise(a, z_hat, c_hat, t_hat, static k)y = A_hat z_hat - c_hat t_hat in the NTT domain (FIPS 204 Algorithm 8, step 7), in the 61 bit Mersenne field.
mldsa_reduce(x, static x_max, static canonical)Reduce x modulo q = 8380417 in the 61 bit Mersenne field.

stdlib/mersenne61/poseidon

poseidon_mersenne61(let input, static INPUT_LEN, static OUTPUT_LEN, static ALPHA, static N_ROUNDS_F, static N_ROUNDS_P, static MDS_MATRIX, static ROUND_CONSTANTS)
poseidon_mersenne61_16_8(input)
poseidon_mersenne61_16_8_config()poseidon permutation config for 16 inputs and 8 outputs targeting 256 bits of security.
poseidon_mersenne61_state(mut state, INPUT_LEN, OUTPUT_LEN, ALPHA, N_ROUNDS_F, N_ROUNDS_P, MDS_MATRIX, ROUND_CONSTANTS)make sure our input is non-constant witness variables
poseidon_mersenne61_state_16_8(state)

stdlib/milli/ext

ext_degree()Degree D of the binomial extension Z_q[x] / (x^D - c) of Milli used for the SLIP sumcheck challenges (dags MilliScalarMont::EXT_DEGREE): q^3 is only about 2^96, q^6 about 2^192
ext_nonresidue()The constant c of the extension Z_q[x] / (x^D - c) of Milli, D = ext_degree() (dags MilliScalarMont::EXT_NONRESIDUE): the smallest c >= 2 that is neither a square nor a cube, so x^6 - c is irreducible

stdlib/milli/lattice

lattice_kappa()State width of the lattice sponge in field elements (dags LATTICE_SPONGE_KAPPA for the Poseidon squeeze)
lattice_output_len()Output lanes of the lattice sponge permutation in Milli (PoseidonMilli32_16)
lattice_permutation(state)The Poseidon permutation of the lattice sponge in Milli: PoseidonMilli32_16, a state of lattice_t() = 48 elements, through the cached precompile
lattice_t()State width of the lattice sponge permutation in Milli (PoseidonMilli32_16)

stdlib/milli/mldsa

mldsa44_verify(pk, msg, sig)ML-DSA-44 signature verification (FIPS 204 Algorithms 3 and 8) with an empty context string, in the 32 bit milli field.
mldsa44_w_approx(a_hat, v_bits, c, t1)w_approx = NTT^-1(A_hat NTT(z) - NTT(c) NTT(2^13 t1)) for ML-DSA-44 in the 32 bit milli field (FIPS 204 Algorithm 8, step 7).
mldsa_ct1(c, t1)Negacyclic products c * t1_i computed over the native field.
mldsa_intt_sub(y, ct)w = NTT^-1(y) - 2^13 ct mod q (FIPS 204 Algorithm 8, step 7).
mldsa_ntt_z(v0, v1)NTT over Z_q of the polynomials z_j = gamma1 - v_j (FIPS 204 Algorithm 41 applied to the signature response).
mldsa_pointwise(a, z_hat, static k)Products A_hat * z_hat in the NTT domain (FIPS 204 Algorithm 8, step 7).
mldsa_reduce(x, static x_max, static canonical)Reduce X = sum(x[t] * 2^(10 t)) modulo q = 8380417.

stdlib/milli/poseidon

poseidon_milli(let input, static INPUT_LEN, static OUTPUT_LEN, static ALPHA, static N_ROUNDS_F, static N_ROUNDS_P, static MDS_MATRIX, static ROUND_CONSTANTS)
poseidon_milli_16_1(input)
poseidon_milli_16_16(input)
poseidon_milli_16_16_config()poseidon permutation config for 16 inputs and 16 outputs targeting 256 bits of security.
poseidon_milli_16_1_config()poseidon permutation config for 16 inputs and 1 outputs targeting 256 bits of security.
poseidon_milli_32_16(input)
poseidon_milli_32_16_config()poseidon permutation config for 32 inputs and 16 outputs targeting 256 bits of security.
poseidon_milli_40_16_config()poseidon permutation config for 40 inputs and 16 outputs targeting 256 bits of security.
poseidon_milli_config()16 input, 16 output poseidon_milli_16_16_config()
poseidon_milli_state(mut state, INPUT_LEN, OUTPUT_LEN, ALPHA, N_ROUNDS_F, N_ROUNDS_P, MDS_MATRIX, ROUND_CONSTANTS)make sure our input is non-constant witness variables
poseidon_milli_state_32_16(state)
poseidon_two_one(input)

stdlib/mldsa

mldsa44_finish(mu, w, h, ctilde)Final steps of ML-DSA-44 verification (FIPS 204 Algorithm 8): apply the hint to w_approx (23 bits per canonical coefficient) and constrain H(mu || w1Encode(w1)) to equal ctilde.
mldsa44_mu(pk_bits, msg_bits)mu = H(H(pk) || 0 || 0 || msg) for ML-DSA-44 with an empty context string (FIPS 204 Algorithms 3 and 8).
mldsa44_parse(pk, sig)Decode an ML-DSA-44 public key and signature (FIPS 204 Algorithms 23 and 27) given as byte values, and check the signature response norm.
mldsa44_parse_sig(sig)Decode an ML-DSA-44 signature (FIPS 204 Algorithm 27) given as byte values, and check the signature response norm.
mldsa_assert_below_q(r_bits)Constrain the value of 23 little-endian bits to be at most q - 1 = 0x7FE000: if bits 13..22 are all set, bits 0..12 must be clear.
mldsa_brv8(static k)bit reversal of an 8 bit static value
mldsa_div_rem_q(x)Long division of X = sum(x[t] * 1024^t) by q = 8380417, using only values below 2^31 so it works in fields of 32 bits or more even when X is larger than the field.
mldsa_expand_a(rho, static k, static l)ExpandA (FIPS 204 Algorithm 32) for a k x l matrix.
mldsa_hint_unpack(y)HintBitUnpack for ML-DSA-44 (FIPS 204 Algorithm 21), omega = 80, k = 4.
mldsa_limbs(bits)Group little-endian bits into base 2^10 limbs (the last limb may be shorter).
mldsa_mulmod_static(static a, static b)a * b mod q for static a, b < q, evaluated at compile time
mldsa_rej_ntt_poly(seed)RejNTTPoly (FIPS 204 Algorithm 30): sample a polynomial with uniform coefficients below q from SHAKE128(seed).
mldsa_sample_in_ball(ctilde)SampleInBall for ML-DSA-44 (FIPS 204 Algorithm 29), tau = 39.
mldsa_static_limbs(static v)Base 2^10 limbs [l0, l1, l2] of a static value below 2^23
mldsa_use_hint(r_bits, h)UseHint(h, r) for ML-DSA-44 (FIPS 204 Algorithms 36 and 40), gamma2 = (q - 1) / 88.
mldsa_zeta_table(static f)Static table of f * zeta^e mod q for e in 0..512, where zeta = 1753 is the primitive 512th root of unity used by ML-DSA

stdlib/oraccle

oraccle_commit(input, state)ingest the elements
oraccle_init()initialize an instance of a transcript oracle.
oraccle_sample_ternary_vec(static len, let state)number of bits necessary to sample an element in discrete gaussian distribution with 3 elements
oraccle_sample_uniform(let state)Sample a single element.
oraccle_sample_uniform_vec(static out_len, let state)
oraccle_squeeze(let mut pending_elements)

stdlib/polynomial

bit_reverse_indices(let mut input)take a vector and move each element from it's original index to the index equal to the bit reversal of the original index
intt_negacyclic(input)apply an inverse negacyclic number theoretic transform to a vector of coefficients.
intt_negacyclic_vec(N, input)apply a negacyclic number theoretic transform to a vector of polynomials
mat_poly_compose_horizontal(static N, let lhs, let rhs)
mat_poly_compose_vertical(static N, lhs, rhs)
mat_poly_iden(static N, static size)get an identity matrix of polynomial ring elements
mat_poly_mul_vec(static N, mat, vec)multiply a matrix of polynomials by a vector of polys all inputs should be in eval representation
ntt(let input, root_powers)apply a number theoretic transform to a vector of elements
ntt_negacyclic(input)apply a negacyclic number theoretic transform to a vector of coefficients.
ntt_negacyclic_mat(N, mat)apply a negacyclic number theoretic transform to a matrix of polynomials
ntt_negacyclic_vec(N, input)apply a negacyclic number theoretic transform to a vector of polynomials
poly_norm_inf(N, poly, static bitlen)returns the coefficient with the largest norm
poly_norm_inf_lt(N, poly, static bound)returns the coefficient with the largest norm
poly_norm_l1(N, poly)returns the sum of the coefficients in the integers here we check that we don't overflow the field this impl only supports l1 norms < E::Q / 2
polynomial_coef_mul(lhs, rhs)multiply two polynomials, each in coefficient form
vec_poly_scalar_mul(static N, lhs, rhs)multiple a vector of polynomials by a single polynomial.
vec_polynomial_coef_mul(static N, lhs, rhs)multiply two vectors of polynomials.

stdlib/r1cs

r1cs_assert_field(static wtns_len, static r_a, static r_b, static r_c)asserts that an R1CS has a quadratic constraint between -1 and 1: -1 * -1 = 1
r1cs_compose_vertical(static width, l_r_a, l_r_b, l_r_c, r_r_a, r_r_b, r_r_c)combine two R1CS vertically.
r1cs_eval(r1cs, wtns)given an r1cs and a witness vector evaluate the r1cs.
r1cs_field_constraint(wtns_len)get a R1CS with a single constraint constraining -1 * -1 = 1
r1cs_from_output(wtns_len, output, indices)take some outputs and some witness indices and construct an R1CS that constrains the witness accordingly
r1cs_from_vec(vec)
r1cs_into_output(static wtns_len, static r_a, static r_b, static r_c)
r1cs_with_output(output, indices, wtns_len, r_a, r_b, r_c)

stdlib/recurse

nothing_up_my_sleeve()

stdlib/slip

slip_mask_transcript(static mask)transcript encoding of a static bit mask (dags BitMask::transcript_elements): the length, then four 16 bit chunks of every 64 bit word
slip_placements(static mask, static n, static c)place the entries of a masked sequence into blocks (dags BitMask::placements): entries with mask 0 fill the decomposed blocks and entries with mask 1 the as-is blocks, each in order, with `n` columns per block.
slip_r1cs_arg_verify(static wtns_len, static r_a, static r_b, static r_c, static kappa, static k, static k_gamma, static transcript_id, static a_s, static a_l, static la_absorb, static la_exp, vec)Verifier of the dags SLIP R1CS argument (sumcheck version, dags slip/spec.pdf sections "Protocol", "R1CS" and "As-Is Binary Regions", binary opening challenges) as an nbv program, for recursion.

stdlib/typed

Typed byte strings in postcard's encoding: a flat concatenation of fields, as postcard serializes a tuple or struct, whose layout is fixed by a static schema. The value types loosely follow anondb's.

| tag | type | encoding | lens[i] | | --- | ----- | -------- | --------- | | 0 | bool | one byte, 0 or 1 | 0 | | 1 | u8 | one byte | 0 | | 2-5 | u16, u32, u64, u128 | LEB128 varint, shortest form | varint length | | 6 | bytes (Vec<u8>, String) | varint length, then the bytes | length | | 7 | option marker | one byte, then the inner value when 1 | 0 or 1 | | 8 | byte array ([u8; N]) | the bytes | N |

The schema is two static vectors, types (a tag per field) and lens (a parameter per field), and determines the total length and every field offset. Because nbv lengths are static, the varint length of every integer, the length of every bytes field and the presence of every option are public. An option is a marker entry followed by the entries of the inner value when present.

typed_bytes_check constrains the bytes to that structure: bools are 0 or 1, option markers and length prefixes equal the schema, and varints have their continuation bits in place, no redundant trailing byte and no bits above their type. That is exactly what the postcard serializer writes (its decoder also accepts longer varints). Strings are not checked to be UTF-8.

typed_bytes_lattice proves that a lattice sponge hash (dags LatticeSponge<H>, see stdlib/lattice) is of bytes with that structure: the bytes are packed like FieldScalar::from_unsafe_byte_stream (the byte length, then ceil(e / 8) - 1 bytes per element), absorbed by the Ajtai hash and squeezed through the field's Poseidon permutation. The packed elements reuse the constrained byte bits, so a 1 KB document costs about 13k rows in Milli. The absorption matrix is a static, e.g.

(types, lens, n, let bytes)
static a_absorb = [...]
static types = into_public_static! types
static lens = into_public_static! lens
static n = into_public_static! n
assert_eq! n, len! bytes
typed_bytes_lattice(bytes, types, lens, a_absorb)

whose outputs are the schema, the byte length and the hash (16 elements in Milli). The Rust side (nbvc::typed) generates this program (typed_lattice_src), encodes tuples into its inputs and nbvc::TypedLatticeArg wraps the whole thing as an argument.

Sealing

typed_lex_chacha20 encrypts a typed byte string with ChaCha20 and reveals selected fields, a programmatic commitment: its outputs are the lattice sponge hash of the key (ChaCha20 alone is not key committing), the ciphertext under the public nonce and the plaintext bytes of the revealed fields. It uses anondb's lexicographic encoding (typed_lex_check, typed_lex_width): fixed width fields only (bool, u8..u128 big-endian, byte arrays), so the layout does not depend on the values. About 22k rows per 64 byte block. nbvc::TypedSealedArg wraps it; it is not hiding while the argument is not zero knowledge.

Not supported: signed integers, floats, maps, sequences other than bytes.

typed_bytes_check(bytes, static types, static lens)Constrain `bytes` to be a typed byte string in postcard's encoding with the static schema `types` (one type tag per field, see typed_width) and `lens` (each field's parameter): the fields concatenated as postcard serializes a tuple or struct.
typed_bytes_lattice(bytes, static types, static lens, static a_absorb)Lattice sponge hash of the typed byte string `bytes` with the static schema `types` and `lens`, after constraining its structure with typed_bytes_check: dags `LatticeSponge<H>` with `append_bytes(bytes)` then `squeeze_safe()`, returning `lattice_output_len` elements of the field's Poseidon permutation.
typed_lattice_digest_bits(pending_bits, static a_absorb)lattice_digest (see stdlib/lattice) over elements given by their `field_bit_width!` little-endian bits instead of their values, for elements whose bits are already constrained (e.g.
typed_lex_chacha(static rounds, bytes, key, static nonce, static types, static lens, static reveal, static a_absorb)ChaCha encryption (`rounds` 20 for ChaCha20, 8 for ChaCha8) of a typed byte string in anondb's lexicographic encoding (see typed_lex_check) with selected fields revealed, a programmatic commitment to the plaintext:
typed_lex_chacha20(bytes, key, static nonce, static types, static lens, static reveal, static a_absorb)typed_lex_chacha with ChaCha20
typed_lex_check(bytes, static types, static lens)Constrain `bytes` to be a typed byte string in anondb's lexicographic encoding with the static schema `types` and `lens` (see typed_lex_width): fixed width fields concatenated with no separators.
typed_lex_width(static t, static n)Byte width of a field of a typed byte string in anondb's lexicographic encoding, fixed width types only.
typed_varint_len(static n)Number of bytes in the postcard (LEB128) varint of a static `n`: 7 bits per byte, least significant group first, the top bit of every byte but the last set.
typed_varint_static(static n)The postcard (LEB128) varint bytes of a static `n`, see typed_varint_len.
typed_width(static t, static n)Byte width of a field of a typed byte string with type tag `t` and parameter `n`, in postcard's encoding.