Skip to main content

shift_operator_table

binius_prover::protocols::shift::monster

Function shift_operator_table 

Source 
pub fn shift_operator_table<F, P: PackedField<Scalar = F>, A: Allocator>(
    alloc: &A,
    psi: &[F],
) -> FieldVec<P, A>
where
    F: BinaryField,
Expand description

Pushes one weight vector through every shift.

A shift indicator says whether an output bit reads a given input bit at a given amount. This contracts it on the output index, against the supplied weights:

    T[psi](j, s, o) = sum_k psi(k) * shift-ind_op(o)(k, j, s)

At most one input bit feeds each output bit. So a slice at fixed (s, o) is the weights moved by that shift, not a matrix applied to them.

The reduction contracts the indicator once per slot of a shift sequence. Both contractions are this operator:

  • the first carries the oblong weights to the bits of the intermediate word;
  • the second carries that result down to the witness bit.

§Returns

One multilinear over SHIFT_OPERATOR_LOG_LEN variables, indexed from the low variables up:

    low     Word::LOG_BITS             the bit position
    middle  Word::LOG_BITS             the shift amount
    high    LOG_SHIFT_VARIANT_COUNT    the shift variant

§Performance

Every entry is one copy or one accumulation. So the whole table costs O(2^15) field operations, and a single slice O(2^6). A caller needing one slice rather than the whole table calls shift_operator_row itself.

§Panics

Panics unless the weights hold one entry per bit position of a word.