lattice_assert_canonical
stdlib/lattice/lattice_assert_canonical.nbv
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. Without it a value with two representations (0 in Mersenne61 is also the all-ones pattern) would let a prover choose between two lattice states.
Mersenne61 and Milli have cheap rules, every other field uses the generic comparison against p - 1.
- Calls
bits/and_bits,fields/assert_mersenne61,fields/assert_milli32,bits/lte_negone,slice,sum,bits/to_bits_exact- Precompiles
assert_eq!,clone!,constrain_eq!,field_bit_width!,if_eq!,len!,loop!- Used by
lattice/lattice_bits
Source
# 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. Without it a
# value with two representations (0 in Mersenne61 is also the all-ones pattern) would let a
# prover choose between two lattice states.
#
# Mersenne61 and Milli have cheap rules, every other field uses the generic comparison
# against p - 1.
(bits)
static e = field_bit_width!
assert_eq! e, len! bits
static mut handled = 0
if_eq! e, 61 {
# p = 2^61 - 1: the only pattern at or above p is all ones, so e - sum(bits) >= 1
static _ = assert_mersenne61()
let _ = to_bits_exact(e - 1 - sum(clone! bits), 6)
handled = 1
}
if_eq! e, 32 {
# p = 2^32 - 2^20 + 1: when bits 20..32 are all set the low 20 bits must be clear
static _ = assert_milli32()
let mut top = bits[20]
loop! 11, i {
top = and_bits(top, bits[21 + i])
}
constrain_eq! 0, top * sum(slice((clone! bits), 0, 20))
handled = 1
}
if_eq! handled, 0 {
constrain_eq! 1, lte_negone(clone! bits)
}
0