Index Mathematics Conjectures nbv lettuce Widgets

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