Index Mathematics Conjectures nbv lettuce Widgets

xor_bits_vec_wtns

stdlib/bits/xor_bits_vec_wtns.nbv

xor_bits_vec_wtns(lhs, rhs)

xor of two equal length vectors of bits, element-wise, as fresh witness bits. Same single row per element as xor_bits_vec, plus one witness entry, but the output does not carry the linear combinations of the inputs, so it can be chained without the combinations growing.

Calls
valloc
Precompiles
clone!, constrain_mul!, len!, modulo!
Used by
blake3/blake3_compress, blake3/blake3_g, chacha/chacha_quarter_round, typed/typed_lex_chacha

Source

# xor of two equal length vectors of bits, element-wise, as fresh witness
# bits. Same single row per element as xor_bits_vec, plus one witness entry,
# but the output does not carry the linear combinations of the inputs, so it
# can be chained without the combinations growing.
(lhs, rhs)

static n = len! lhs
# the field inverse of 2, not integer division
static half = 1 / 2
let sum = (clone! lhs) + (clone! rhs)
let out = modulo! (clone! sum), valloc(n, 2)
# lhs * rhs = (lhs + rhs - out) / 2 forces out = lhs ^ rhs for bit inputs
constrain_mul! lhs, rhs, (sum - (clone! out)) * valloc(n, half)
out