The nbv language
nbv ("nothing but vectors") is a small imperative language for writing
arithmetic circuits. A program describes a computation over the elements of a
prime field, and the compiler nbvc turns it into a rank-1
constraint system (R1CS) together with a witness: an assignment of field
elements to variables that satisfies every constraint. The R1CS can then be
argued about with a proof system (slip, bdlop,
bons22).
Every value is a vector of field elements of a length known at compile time. Control flow is resolved entirely at compile time: loops are unrolled and conditionals choose between blocks based on compile time values. What remains are linear combinations and products of witness values, and those become the constraints.
Every example on this page and on the precompile pages is compiled and run by the test suite of the documentation, in the Milli field (p = 232 - 220 + 1 = 4293918721). Examples with a red border show an error.
A first program
This program takes two inputs and returns x * y + x:
(let x, let y) let z = x * y + x z
The first line is the function header naming the inputs. Each following
line is a statement, and the last line is the final expression, which is the
value the function returns. Compiling it produces one constraint,
x * y = t for a new witness variable t. The addition
is free: t + x is a linear combination, and linear combinations
are carried along without constraints until something needs them.
Programs and files
Each .nbv file is one function, named after the file:
stdlib/sum.nbv defines sum. There is no import
statement. When a program calls sum(v), the compiler looks for a
file named sum.nbv in its include paths and in the
standard library, which is bundled into the
compiler. Function names must be unique across all of them.
A file is made of, in order:
- An optional function header: a parenthesized, comma-separated list of
argument names, each optionally prefixed by
staticorletand thenmut. A header may span several lines. - Statements, one per line.
- An optional final expression, which is the return value. A function
without one returns the scalar
0. A final expression of the form(a, b)returns a tuple.
Newlines end statements, so each statement sits on its own line, except
inside parentheses, vector literals and blocks, which may span lines where the
grammar allows it. Only spaces count as whitespace: a tab is a syntax error.
Comments start with # and run to the end of the line.
The function a program starts from is the entrypoint. Its arguments are the
inputs of the program and are always witness values: an entrypoint argument
declared static is an error. Every argument passed to a function
must be named in its header. The values returned by the entrypoint become the
outputs of the program.
Values and literals
All values are vectors of field elements with a length fixed at compile
time. A vector of length 1 is a scalar, and there is no separate scalar type:
the input x above is a vector of length 1.
- Number literals
- Decimal (
42) or hexadecimal (0x2a), reduced modulo the field characteristic. There is no unary minus: write0 - 1for -1. - Vector literals
- Square brackets around static scalar expressions, separated by spaces,
commas or newlines:
[1 2 3],[1, 2, 0x3]. Every entry must be a compile time value. - String literals
"text"encodes the bytes of the string into field elements, as one element holding the byte length followed by the bytes, packed little endian, as many per element as the field allows:"ab"is[2 25185], 25185 being0x6261.
(let x) static v = [1 2, 3 0x10] static minus_one = 0 - 1 # p + 1 reduces to 1 static big = 4293918722 concat! x + v[3], minus_one, x * big
(let x) static s = "ab" static n = len! s valloc(n, x) * s
A field element has no sign and no order. Comparisons, integer division
and bit manipulation are available for compile time values through
precompiles, and for witness values
through standard library functions that decompose values into bits, such as
to_bits_exact.
Variables: static and let
Every variable has a location, decided when it is declared:
static- A compile time value. Its value is known while the circuit is being built, it never appears in the R1CS, and it can drive loops, conditionals, lengths and indices.
let- A witness value. It is a linear combination of witness variables, whose values are only known when a witness is computed for concrete inputs.
A let variable may be initialized with a static value, which
is lifted into a constant witness linear combination. A static
variable can not be initialized from a witness value:
(let x) static y = x
Variables are immutable unless declared mut. Assigning to a
mutable variable with name = expr requires the new value to have
the same length, and a static variable can not be assigned a witness value.
Declaring a variable again with the same name shadows the old one, and the
new declaration may have a different length or location.
(let x) let mut acc = x loop! 3 { acc = acc + x } acc
A vector can be declared without a value by giving its length in brackets.
It starts out as zeros and must be mut. Its entries are then set
by index:
(let x) let mut v[3] v[1] = x v
Moves and copies
Using a vector variable by name moves it: afterwards the name is gone. This keeps large vectors from being duplicated by accident. Scalars are copied instead of moved.
(let v) let w = v v + w
Use clone! to keep a
vector around. Reading an entry with an index does not move the vector, and an
operation whose two operands are the same variable (v * v) clones
it automatically:
(let v) let w = clone! v let first = v[0] v * v + w * w
Function arguments are moved into the callee the same way, which is why
standard library code is full of (clone! x).
Operators
The arithmetic operators are +, -,
* and /, with the usual precedence (*
and / bind tighter, all are left associative) and parentheses
for grouping. They act element-wise and require both operands to have the
same length; scalars are not broadcast. To combine a vector with a scalar,
build a vector of the right length first, e.g. with
valloc.
(let v, let x) v * x
(let v, let x) static n = len! v (clone! v) * valloc(n, x) + v
/ is division in the field, multiplication by the inverse of
the right hand side, not integer division (see
div_floor! for that).
Both operands must be compile time values. To divide a witness value by a
constant, multiply it by the static inverse:
(let x) # 3 / 2 in the field is (p + 3) / 2 static half = 1 / 2 x * half
Operations between compile time values are evaluated by the compiler. Addition, subtraction and multiplication or division by a constant of witness values produce linear combinations without constraints. Only multiplying two witness values adds a constraint, see below.
The grammar contains comparison operators (==,
!=, <, >), but they are not
reachable from any expression and are not supported. Use the
if_*! and
assert_*!
precompiles for compile time comparisons.
Indexing
v[i] reads entry i of a named variable as a
scalar, and v[i] = x sets it on a mut variable. The
index must be a compile time value and in bounds. Only named variables can be
indexed: index the result of an expression by assigning it to a variable
first, or use slice!.
(let v, let i) v[i]
Selecting an entry by a witness index is a circuit of its own, for example
an inner product with a one-hot vector from
one_hot_bits.
Function calls
name(arg1, arg2) calls the function in name.nbv.
Calls are inlined: the callee runs at the call site with its own scope, and
its constraints become part of the caller's circuit.
A header argument declared static requires a compile time
value, one declared let lifts a static value to a witness, and an
argument without a location keeps the location of the value passed in. That
makes most standard library functions usable with both static and witness
inputs.
Spaces are allowed between a name and its parenthesis, so
name (x) is also a call. Inside a vector literal or anywhere a
variable is followed by a parenthesized expression, this turns the variable
into a call: [width (len! a)] fails with "unknown function
width".
(let v) concat! sum(clone! v), inner_prod((clone! v), v)
Tuples
A function can return several values with a parenthesized final
expression, (a, b). Tuples are not values: they only move
variables out of a function, and are unpacked immediately by a tuple
assignment. Each name in the assignment is either a new declaration
(let or static, optionally mut) or an
existing variable, which must keep its length and location. An entrypoint that
returns a tuple has one output per entry.
(let v) (let head, let tail) = split_at(2, v) (tail * tail, head)
A tuple can also be spread into the arguments of a call with
...:
(let v) inner_prod(...split_at(2, v))
Precompiles
Precompiles are operations built into the compiler, invoked with an
exclamation mark: name! arg1, arg2. Some take a block:
name! arg1, arg2 { ... }. They provide everything the arithmetic
operators do not: vector manipulation (len!,
slice!, concat!), loops (loop!,
loop_flat_map!), compile time conditionals (if_eq!),
integer arithmetic on compile time values (div_floor!), explicit
constraints (constrain_eq!) and more. See the
precompile reference.
Some precompiles are statements (they return nothing and stand on their own line), some are expressions, and a few can be both. A precompile used as a statement must not return a witness value.
The arguments of a precompile extend to the end of the line, separated by commas. A precompile nested inside the arguments of another precompile or of a function call therefore takes all the remaining arguments with it, and must be wrapped in parentheses:
(let v) # without the parentheses clone! would take all three arguments let w = slice((clone! v), 1, 2) w * w
A few names are accepted by the grammar but have no implementation, and
fail at compile time: read_input!, write_output! and
input_len!.
Blocks and scopes
Blocks, the { ... } bodies of precompiles such as
loop! and if_eq!, open a new scope. Variables
declared inside a block are gone when it ends, and the block can read, move
and assign the variables of the enclosing scopes. Precompiles that use the
value of their block, like loop_flat_map!, take it from the
block's final expression.
(let x) let mut total = x loop! 2 { let doubled = x + x total = total + doubled - x } let squares = loop_flat_map! 2, i { # i is a static counter, starting at 0 x * x + i } concat! total, squares
(let x) loop! 2 { let inner = x } inner
Compile time evaluation
The compiler runs the program to build the circuit. Everything that is static is evaluated during that run, so all control flow has to be decided by compile time values:
- Loops (
loop!,loop_flat_map!, ...) take a static iteration count and are unrolled. - Conditionals (
if_eq!,if_ne!,if_lt!,if_lte!) compare static values and either run their block or skip it. - Lengths, indices and the arguments of most precompiles must be static.
Static values are computed with the same language. A function called with
static arguments runs on static values and returns static values, without
adding constraints. static_eval!
runs a block with every variable treated as static, which allows running code
written for witness values, such as a hash function, on compile time
inputs.
(let x) static s = static_eval! { let a = [1 2 3] sum(a) } x + s
Compile time assertions (assert_eq!, assert_lt!,
...) stop the compilation when they fail. They check static values only and
add nothing to the circuit.
Constraints and witnesses
The circuit is an R1CS: rows of the form
(A w) * (B w) = (C w) over a witness vector w whose
first entry is the constant 1. The program decides which rows and witness
entries exist:
- Inputs occupy the first witness entries.
- Linear operations on witness values (
+,-, multiplication by a constant) build linear combinations and add nothing. - The product of two witness linear combinations adds one witness entry holding the product and one row constraining it.
constrain_eq!adds a row asserting two values are equal, andconstrain_mul!a row assertinga * b = cwithout materializing the product.wtns!materializes a linear combination as a new witness entry with one row, which keeps long linear combinations from growing.- Some precompiles compute a witness value that is not constrained at all,
a hint:
to_bits_unconstrained!, anddiv_floor!ormodulo!on witness values. Hints are cheap ways to compute values that are hard to express as field arithmetic, and the program must add constraints that pin them down, asto_bits_exactdoes for bit decompositions. An unconstrained hint is a soundness bug. - The values returned by the entrypoint are materialized as witness entries and become the outputs.
The same program runs in two modes. Compiling for a circuit only tracks which witness entries exist, while computing a witness also evaluates them for concrete inputs. Both produce the same R1CS.
(let x, let y) let p = x * y # one more row: x * y = 12, without a new witness entry constrain_mul! x, y, 12 p
Fields
Programs are compiled for a prime field chosen by the caller of the
compiler. The standard library can provide field specific implementations:
functions in a directory named after a field (milli for
p = 232 - 220 + 1, mersenne61 for
p = 261 - 1, dilithium for p = 8380417) are only loaded
when compiling for that field. The same name may exist in several field
directories (mldsa_reduce has a Milli and a Mersenne61 version),
but not both in a field directory and in a shared one.
Calling a function that only exists for another field is an error naming the
fields that have it. field_bit_width!
gives the bit width of the current field.
Keep field sizes in mind for integer arithmetic: a 32-bit word does not fit in a Milli element (p < 232), let alone in the dilithium field (p < 223). The ChaCha, BLAKE3 and Keccak implementations of the standard library work on bit vectors and limbs for that reason.
Running programs
The nbvc binary compiles a function from the current directory
and the standard library, in the Milli field:
nbvc <function> [bdlop | bons22 | ns22 | slip] [-i 1,2,3] [-v 0-5 | --verbose]
Without an argument name it compiles the function, computes the witness for
the comma-separated input -i, and prints the witness, the R1CS
and the outputs. With an argument name it also constructs and verifies a
proof with that argument system.
From Rust, nbvc::NBVProgram compiles and runs a source string:
use nbvc::*;
let src = "(let x, let y)\nx * y\n";
let input = vec![vec![MilliScalarMont::from(3u64)].into(), vec![MilliScalarMont::from(4u64)].into()];
// compile, compute the witness, check the R1CS and return the outputs
let outputs = NBVProgram::<MilliScalarMont>::try_run(src, input.clone()).await?;
// or get the R1CS, the witness and the witness indices of the outputs
let program = NBVProgram::<MilliScalarMont>::new(src, vec![1, 1]);
let (r1cs, wtns, output_indices) = program.eval(input).await?;
Limitations
- No data dependent control flow: every branch and loop bound is a compile time value.
/only divides compile time values. Multiply a witness value by a static inverse to divide it by a constant. Dividing by a witness value needs the inverse as a hint, constrained byx * inv = 1.- No comparison operators and no unary minus.
- Vector literals can only contain compile time values.
- Only named variables can be indexed, and only by compile time indices.
- A mutable variable keeps its length.
- A program has to add at least one constraint. One that only returns its inputs or constants produces an R1CS without rows, which the proof backend can not construct (it currently panics).