Index Mathematics Conjectures nbv lettuce Widgets

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:

  1. An optional function header: a parenthesized, comma-separated list of argument names, each optionally prefixed by static or let and then mut. A header may span several lines.
  2. Statements, one per line.
  3. 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: write 0 - 1 for -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 being 0x6261.
(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:

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:

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