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.
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 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.
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.
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
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
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.
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)
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.
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.
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.
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
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).
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)
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.
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
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.
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.
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.
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).
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.
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.
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.
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
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
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
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.
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.
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.
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.
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.
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.
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.
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:
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.
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.