Trait o1vm::interpreters::keccak::interpreter::KeccakInterpreter

pub trait KeccakInterpreter<F: One + Debug + Zero>where
    Self: Interpreter<F> + LogupHelpers<F> + BoolHelpers<F> + ArithHelpers<F>,{
    // Provided methods
    fn constraints(&mut self, step: Steps) { ... }
    fn constrain_flags(&mut self, step: Steps)
       where Self: Interpreter<F> { ... }
    fn constrain_booleanity(&mut self, step: Steps)
       where Self: Interpreter<F> { ... }
    fn constrain_sponge(&mut self, step: Steps) { ... }
    fn constrain_absorb(&mut self, step: Steps) { ... }
    fn constrain_padding(&mut self, step: Steps) { ... }
    fn constrain_squeeze(&mut self, step: Steps) { ... }
    fn constrain_round(&mut self, step: Steps) { ... }
    fn constrain_theta(&mut self, step: Steps) -> Vec<Vec<Vec<Self::Variable>>> { ... }
    fn constrain_pirho(
        &mut self,
        step: Steps,
        state_e: Vec<Vec<Vec<Self::Variable>>>
    ) -> Vec<Vec<Vec<Self::Variable>>> { ... }
    fn constrain_chi(
        &mut self,
        step: Steps,
        state_b: Vec<Vec<Vec<Self::Variable>>>
    ) -> Vec<Vec<Vec<Self::Variable>>> { ... }
    fn constrain_iota(
        &mut self,
        step: Steps,
        state_f: Vec<Vec<Vec<Self::Variable>>>
    ) { ... }
    fn lookups(&mut self, step: Steps) { ... }
    fn lookup_syscall_preimage(&mut self, step: Steps) { ... }
    fn lookup_syscall_hash(&mut self, step: Steps) { ... }
    fn lookup_steps(&mut self, step: Steps) { ... }
    fn lookups_sponge(&mut self, step: Steps) { ... }
    fn lookups_round_theta(&mut self, step: Steps) { ... }
    fn lookups_round_pirho(&mut self, step: Steps) { ... }
    fn lookups_round_chi(&mut self, step: Steps) { ... }
    fn lookups_round_iota(&mut self, step: Steps) { ... }
    fn is_sponge(&self, step: Steps) -> Self::Variable { ... }
    fn is_absorb(&self, step: Steps) -> Self::Variable { ... }
    fn is_squeeze(&self, step: Steps) -> Self::Variable { ... }
    fn is_root(&self, step: Steps) -> Self::Variable { ... }
    fn is_pad(&self, step: Steps) -> Self::Variable { ... }
    fn is_round(&self, step: Steps) -> Self::Variable { ... }
    fn mode_absorb(&self, step: Steps) -> Self::Variable { ... }
    fn mode_squeeze(&self, step: Steps) -> Self::Variable { ... }
    fn mode_root(&self, step: Steps) -> Self::Variable { ... }
    fn mode_pad(&self, step: Steps) -> Self::Variable { ... }
    fn mode_rootpad(&self, step: Steps) -> Self::Variable { ... }
    fn mode_round(&self, step: Steps) -> Self::Variable { ... }
    fn from_shifts(
        shifts: &[Self::Variable],
        i: Option<usize>,
        y: Option<usize>,
        x: Option<usize>,
        q: Option<usize>
    ) -> Self::Variable { ... }
    fn from_quarters(
        quarters: &[Self::Variable],
        y: Option<usize>,
        x: usize
    ) -> Self::Variable { ... }
    fn round(&self) -> Self::Variable { ... }
    fn pad_length(&self) -> Self::Variable { ... }
    fn two_to_pad(&self) -> Self::Variable { ... }
    fn in_padding(&self, idx: usize) -> Self::Variable { ... }
    fn pad_suffix(&self, idx: usize) -> Self::Variable { ... }
    fn bytes_block(&self, idx: usize) -> Vec<Self::Variable> { ... }
    fn pad_bytes_flags(&self) -> [Self::Variable; 136] { ... }
    fn flags_block(&self, idx: usize) -> Vec<Self::Variable> { ... }
    fn block_in_padding(&self, idx: usize) -> Self::Variable { ... }
    fn round_constants(&self) -> [Self::Variable; 4] { ... }
    fn old_state(&self, idx: usize) -> Self::Variable { ... }
    fn new_state(&self, idx: usize) -> Self::Variable { ... }
    fn xor_state(&self, idx: usize) -> Self::Variable { ... }
    fn sponge_zeros(&self) -> [Self::Variable; 32] { ... }
    fn vec_sponge_shifts(&self) -> [Self::Variable; 400] { ... }
    fn sponge_shifts(&self, idx: usize) -> Self::Variable { ... }
    fn sponge_bytes(&self) -> [Self::Variable; 200] { ... }
    fn sponge_byte(&self, idx: usize) -> Self::Variable { ... }
    fn state_a(&self, y: usize, x: usize, q: usize) -> Self::Variable { ... }
    fn vec_shifts_c(&self) -> [Self::Variable; 80] { ... }
    fn shifts_c(&self, i: usize, x: usize, q: usize) -> Self::Variable { ... }
    fn vec_dense_c(&self) -> [Self::Variable; 20] { ... }
    fn dense_c(&self, x: usize, q: usize) -> Self::Variable { ... }
    fn vec_quotient_c(&self) -> [Self::Variable; 5] { ... }
    fn quotient_c(&self, x: usize) -> Self::Variable { ... }
    fn vec_remainder_c(&self) -> [Self::Variable; 20] { ... }
    fn remainder_c(&self, x: usize, q: usize) -> Self::Variable { ... }
    fn vec_dense_rot_c(&self) -> [Self::Variable; 20] { ... }
    fn dense_rot_c(&self, x: usize, q: usize) -> Self::Variable { ... }
    fn vec_expand_rot_c(&self) -> [Self::Variable; 20] { ... }
    fn expand_rot_c(&self, x: usize, q: usize) -> Self::Variable { ... }
    fn vec_shifts_e(&self) -> [Self::Variable; 400] { ... }
    fn shifts_e(&self, i: usize, y: usize, x: usize, q: usize) -> Self::Variable { ... }
    fn vec_dense_e(&self) -> [Self::Variable; 100] { ... }
    fn dense_e(&self, y: usize, x: usize, q: usize) -> Self::Variable { ... }
    fn vec_quotient_e(&self) -> [Self::Variable; 100] { ... }
    fn quotient_e(&self, y: usize, x: usize, q: usize) -> Self::Variable { ... }
    fn vec_remainder_e(&self) -> [Self::Variable; 100] { ... }
    fn remainder_e(&self, y: usize, x: usize, q: usize) -> Self::Variable { ... }
    fn vec_dense_rot_e(&self) -> [Self::Variable; 100] { ... }
    fn dense_rot_e(&self, y: usize, x: usize, q: usize) -> Self::Variable { ... }
    fn vec_expand_rot_e(&self) -> [Self::Variable; 100] { ... }
    fn expand_rot_e(&self, y: usize, x: usize, q: usize) -> Self::Variable { ... }
    fn vec_shifts_b(&self) -> [Self::Variable; 400] { ... }
    fn shifts_b(&self, i: usize, y: usize, x: usize, q: usize) -> Self::Variable { ... }
    fn vec_shifts_sum(&self) -> [Self::Variable; 400] { ... }
    fn shifts_sum(
        &self,
        i: usize,
        y: usize,
        x: usize,
        q: usize
    ) -> Self::Variable { ... }
    fn state_g(&self, idx: usize) -> Self::Variable { ... }
    fn hash_index(&self) -> Self::Variable { ... }
    fn block_index(&self) -> Self::Variable { ... }
    fn step_index(&self) -> Self::Variable { ... }
    fn input(&self) -> [Self::Variable; 100] { ... }
    fn input_of_step(&self) -> Vec<Self::Variable> { ... }
    fn output(&self) -> [Self::Variable; 100] { ... }
    fn output_of_step(&self) -> Vec<Self::Variable> { ... }
}

Provided Methods

fn constraints(&mut self, step: Steps)

Creates all 879 constraints/checks to the environment:

• 733 constraints of degree 1
• 146 constraints of degree 2 Where:
• if Steps::Round(_) -> only 389 constraints added
• if Steps::Sponge::Absorb::First -> only 332 constraints added (232 + 100)
• if Steps::Sponge::Absorb::Middle -> only 232 constraints added
• if Steps::Sponge::Absorb::Last -> only 374 constraints added (232 + 136 + 6)
• if Steps::Sponge::Absorb::Only -> only 474 constraints added (232 + 136 + 100 + 6)
• if Steps::Sponge::Squeeze -> only 16 constraints added So:
• At most, 474 constraints are added per row In particular, after folding:
• 136 columns should be added for the degree-2 constraints of the flags
• 5 columns should be added for the degree-2 constraints of the round
• 10 columns should be added for the degree-2 constraints of the sponge
  • for each of the 5 constraints, 2 columns are added for block_in_padding

fn constrain_flags(&mut self, step: Steps)where Self: Interpreter<F>,

Constrains 136 checks of correctness of mode flags

• 136 constraints of degree 2 Of which:
• 136 constraints are added only if is_pad() holds

fn constrain_booleanity(&mut self, step: Steps)where Self: Interpreter<F>,

Constrains 136 checks of booleanity for some mode flags.

• 136 constraints of degree 2 Of which,
• 136 constraints are added only if is_pad() holds

fn constrain_sponge(&mut self, step: Steps)

Constrains 354 checks of sponge steps

• 349 of degree 1
• 5 of degree 2 Of which:
• 232 constraints are added only if is_absorb() holds
• 100 constraints are added only if is_root() holds
• 6 constraints are added only if is_pad() holds
• 16 constraints are added only if is_squeeze() holds

fn constrain_absorb(&mut self, step: Steps)

Constrains 332 checks of absorb sponges

• 332 of degree 1 Of which:
• 232 constraints are added only if is_absorb() holds
• 100 constraints are added only if is_root() holds

fn constrain_padding(&mut self, step: Steps)

Constrains 6 checks of padding absorb sponges

• 1 of degree 1
• 5 of degree 2 Of which:
• 6 constraints are added only if is_pad() holds

fn constrain_squeeze(&mut self, step: Steps)

Constrains 16 checks of squeeze sponges

• 16 of degree 1 Of which:
• 16 constraints are added only if is_squeeze() holds

fn constrain_round(&mut self, step: Steps)

Constrains 389 checks of round steps

• 384 constraints of degree 1
• 5 constraints of degree 2 Of which:
• 389 constraints are added only if is_round() holds

fn constrain_theta(&mut self, step: Steps) -> Vec<Vec<Vec<Self::Variable>>>

Constrains 35 checks of the theta algorithm in round steps

• 30 constraints of degree 1
• 5 constraints of degree 2

fn constrain_pirho( &mut self, step: Steps, state_e: Vec<Vec<Vec<Self::Variable>>> ) -> Vec<Vec<Vec<Self::Variable>>>

Constrains 150 checks of the pirho algorithm in round steps

• 150 of degree 1

fn constrain_chi( &mut self, step: Steps, state_b: Vec<Vec<Vec<Self::Variable>>> ) -> Vec<Vec<Vec<Self::Variable>>>

Constrains 200 checks of the chi algorithm in round steps

• 200 of degree 1

fn constrain_iota( &mut self, step: Steps, state_f: Vec<Vec<Vec<Self::Variable>>> )

Constrains 4 checks of the iota algorithm in round steps

• 4 of degree 1

fn lookups(&mut self, step: Steps)

Creates all possible lookups to the Keccak constraints environment:

• 2225 lookups for the step row
• 2 lookups for the inter-step channel
• 136 lookups for the syscall channel (preimage bytes)
• 1 lookups for the syscall channel (hash) Of which:
• 1623 lookups if Step::Round (1621 + 2)
• 537 lookups if Step::Absorb::First (400 + 1 + 136)
• 538 lookups if Step::Absorb::Middle (400 + 2 + 136)
• 539 lookups if Step::Absorb::Last (401 + 2 + 136)
• 538 lookups if Step::Absorb::Only (401 + 1 + 136)
• 602 lookups if Step::Squeeze (600 + 1 + 1)

fn lookup_syscall_preimage(&mut self, step: Steps)

When in Absorb mode, reads Lookups containing the 136 bytes of the block of the preimage

• if is_absorb, adds 136 lookups
• otherwise, adds 0 lookups

fn lookup_syscall_hash(&mut self, step: Steps)

When in Squeeze mode, writes a Lookup containing the 31byte output of the hash (excludes the MSB)

• if is_squeeze, adds 1 lookup
• otherwise, adds 0 lookups NOTE: this is excluding the MSB (which is then substituted with the file descriptor).

fn lookup_steps(&mut self, step: Steps)

Reads a Lookup containing the input of a step and writes a Lookup containing the output of the next step

• if is_root, only adds 1 lookup
• if is_squeeze, only adds 1 lookup
• otherwise, adds 2 lookups

fn lookups_sponge(&mut self, step: Steps)

Adds the 601 lookups required for the sponge

• 400 lookups if is_sponge()
• 200 extra lookups if is_squeeze()
• 1 extra lookup if is_pad()

fn lookups_round_theta(&mut self, step: Steps)

Adds the 120 lookups required for Theta in the round

fn lookups_round_pirho(&mut self, step: Steps)

Adds the 700 lookups required for PiRho in the round

fn lookups_round_chi(&mut self, step: Steps)

Adds the 800 lookups required for Chi in the round

fn lookups_round_iota(&mut self, step: Steps)

Adds the 1 lookup required for Iota in the round

fn is_sponge(&self, step: Steps) -> Self::Variable

SELECTOR OPERATIONS /// Returns a degree-2 variable that encodes whether the current step is a sponge (1 = yes)

fn is_absorb(&self, step: Steps) -> Self::Variable

Returns a variable that encodes whether the current step is an absorb sponge (1 = yes)

fn is_squeeze(&self, step: Steps) -> Self::Variable

Returns a variable that encodes whether the current step is a squeeze sponge (1 = yes)

fn is_root(&self, step: Steps) -> Self::Variable

Returns a variable that encodes whether the current step is the first absorb sponge (1 = yes)

fn is_pad(&self, step: Steps) -> Self::Variable

Returns a degree-1 variable that encodes whether the current step is the last absorb sponge (1 = yes)

fn is_round(&self, step: Steps) -> Self::Variable

Returns a variable that encodes whether the current step is a permutation round (1 = yes)

fn mode_absorb(&self, step: Steps) -> Self::Variable

Returns a variable that encodes whether the current step is an absorb sponge (1 = yes)

fn mode_squeeze(&self, step: Steps) -> Self::Variable

Returns a variable that encodes whether the current step is a squeeze sponge (1 = yes)

fn mode_root(&self, step: Steps) -> Self::Variable

Returns a variable that encodes whether the current step is the first absorb sponge (1 = yes)

fn mode_pad(&self, step: Steps) -> Self::Variable

Returns a degree-1 variable that encodes whether the current step is the last absorb sponge (1 = yes)

fn mode_rootpad(&self, step: Steps) -> Self::Variable

Returns a degree-1 variable that encodes whether the current step is the first and last absorb sponge (1 = yes)

fn mode_round(&self, step: Steps) -> Self::Variable

Returns a variable that encodes whether the current step is a permutation round (1 = yes)

fn from_shifts( shifts: &[Self::Variable], i: Option<usize>, y: Option<usize>, x: Option<usize>, q: Option<usize> ) -> Self::Variable

COLUMN OPERATIONS /// This function returns the composed sparse variable from shifts of any correct length:

• When the length is 400, two index configurations are possible:
  • If i is Some, then this sole index could range between [0..400)
  • If i is None, then y, x and q must be Some and
    • y must range between [0..5)
    • x must range between [0..5)
    • q must range between [0..4)
• When the length is 80, both i and y should be None, and x and q must be Some with:
  • x must range between [0..5)
  • q must range between [0..4)

fn from_quarters( quarters: &[Self::Variable], y: Option<usize>, x: usize ) -> Self::Variable

This function returns the composed variable from dense quarters of any correct length:

• When y is Some, then the length must be 100 and:
  • y must range between [0..5)
  • x must range between [0..5)
• When y is None, then the length must be 20 and:
  • x must range between [0..5)

fn round(&self) -> Self::Variable

Returns a variable that encodes the current round number [0..24)

fn pad_length(&self) -> Self::Variable

Returns a variable that encodes the bytelength of the padding if any [0..136)

fn two_to_pad(&self) -> Self::Variable

Returns a variable that encodes the value 2^pad_length

fn in_padding(&self, idx: usize) -> Self::Variable

Returns a variable that encodes whether the idx-th byte of the new block is involved in the padding (1 = yes)

fn pad_suffix(&self, idx: usize) -> Self::Variable

Returns a variable that encodes the idx-th chunk of the padding suffix

• if idx = 0, then the length is 12 bytes at most
• if idx = [1..5), then the length is 31 bytes at most

fn bytes_block(&self, idx: usize) -> Vec<Self::Variable>

Returns a variable that encodes the idx-th block of bytes of the new block by composing the bytes variables, with idx in [0..5)

fn pad_bytes_flags(&self) -> [Self::Variable; 136]

Returns the 136 flags indicating which bytes of the new block are involved in the padding, as variables

fn flags_block(&self, idx: usize) -> Vec<Self::Variable>

Returns a vector of pad bytes flags as variables, with idx in [0..5)

• if idx = 0, then the length of the block is at most 12
• if idx = [1..5), then the length of the block is at most 31

fn block_in_padding(&self, idx: usize) -> Self::Variable

This function returns a degree-2 variable that is computed as the accumulated value of the operation byte * flag * 2^8 for each byte block and flag block of the new block. This function will be used in constraints to determine whether the padding is located at the end of the preimage data, as consecutive bits that are involved in the padding.

fn round_constants(&self) -> [Self::Variable; 4]

Returns the 4 expanded quarters that encode the round constant, as variables

fn old_state(&self, idx: usize) -> Self::Variable

Returns the idx-th old state expanded quarter, as a variable

fn new_state(&self, idx: usize) -> Self::Variable

Returns the idx-th new state expanded quarter, as a variable

fn xor_state(&self, idx: usize) -> Self::Variable

Returns the output of an absorb sponge, which is the XOR of the old state and the new state

fn sponge_zeros(&self) -> [Self::Variable; 32]

Returns the last 32 terms that are added to the new block in an absorb sponge, as variables which should be zeros

fn vec_sponge_shifts(&self) -> [Self::Variable; 400]

Returns the 400 terms that compose the shifts of the sponge, as variables

fn sponge_shifts(&self, idx: usize) -> Self::Variable

Returns the idx-th term of the shifts of the sponge, as a variable

fn sponge_bytes(&self) -> [Self::Variable; 200]

Returns the 200 bytes of the sponge, as variables

fn sponge_byte(&self, idx: usize) -> Self::Variable

Returns the idx-th byte of the sponge, as a variable

fn state_a(&self, y: usize, x: usize, q: usize) -> Self::Variable

Returns the (y,x,q)-th input of the theta algorithm, as a variable

fn vec_shifts_c(&self) -> [Self::Variable; 80]

Returns the 80 variables corresponding to ThetaShiftsC

fn shifts_c(&self, i: usize, x: usize, q: usize) -> Self::Variable

Returns the (i,x,q)-th variable of ThetaShiftsC

fn vec_dense_c(&self) -> [Self::Variable; 20]

Returns the 20 variables corresponding to ThetaDenseC

fn dense_c(&self, x: usize, q: usize) -> Self::Variable

Returns the (x,q)-th term of ThetaDenseC, as a variable

fn vec_quotient_c(&self) -> [Self::Variable; 5]

Returns the 5 variables corresponding to ThetaQuotientC

fn quotient_c(&self, x: usize) -> Self::Variable

Returns the (x)-th term of ThetaQuotientC, as a variable

fn vec_remainder_c(&self) -> [Self::Variable; 20]

Returns the 20 variables corresponding to ThetaRemainderC

fn remainder_c(&self, x: usize, q: usize) -> Self::Variable

Returns the (x,q)-th variable of ThetaRemainderC

fn vec_dense_rot_c(&self) -> [Self::Variable; 20]

Returns the 20 variables corresponding to ThetaDenseRotC

fn dense_rot_c(&self, x: usize, q: usize) -> Self::Variable

Returns the (x,q)-th variable of ThetaDenseRotC

fn vec_expand_rot_c(&self) -> [Self::Variable; 20]

Returns the 20 variables corresponding to ThetaExpandRotC

fn expand_rot_c(&self, x: usize, q: usize) -> Self::Variable

Returns the (x,q)-th variable of ThetaExpandRotC

fn vec_shifts_e(&self) -> [Self::Variable; 400]

Returns the 400 variables corresponding to PiRhoShiftsE

fn shifts_e(&self, i: usize, y: usize, x: usize, q: usize) -> Self::Variable

Returns the (i,y,x,q)-th variable of PiRhoShiftsE

fn vec_dense_e(&self) -> [Self::Variable; 100]

Returns the 100 variables corresponding to PiRhoDenseE

fn dense_e(&self, y: usize, x: usize, q: usize) -> Self::Variable

Returns the (y,x,q)-th variable of PiRhoDenseE

fn vec_quotient_e(&self) -> [Self::Variable; 100]

Returns the 100 variables corresponding to PiRhoQuotientE

fn quotient_e(&self, y: usize, x: usize, q: usize) -> Self::Variable

Returns the (y,x,q)-th variable of PiRhoQuotientE

fn vec_remainder_e(&self) -> [Self::Variable; 100]

Returns the 100 variables corresponding to PiRhoRemainderE

fn remainder_e(&self, y: usize, x: usize, q: usize) -> Self::Variable

Returns the (y,x,q)-th variable of PiRhoRemainderE

fn vec_dense_rot_e(&self) -> [Self::Variable; 100]

Returns the 100 variables corresponding to PiRhoDenseRotE

fn dense_rot_e(&self, y: usize, x: usize, q: usize) -> Self::Variable

Returns the (y,x,q)-th variable of PiRhoDenseRotE

fn vec_expand_rot_e(&self) -> [Self::Variable; 100]

Returns the 100 variables corresponding to PiRhoExpandRotE

fn expand_rot_e(&self, y: usize, x: usize, q: usize) -> Self::Variable

Returns the (y,x,q)-th variable of PiRhoExpandRotE

fn vec_shifts_b(&self) -> [Self::Variable; 400]

Returns the 400 variables corresponding to ChiShiftsB

fn shifts_b(&self, i: usize, y: usize, x: usize, q: usize) -> Self::Variable

Returns the (i,y,x,q)-th variable of ChiShiftsB

fn vec_shifts_sum(&self) -> [Self::Variable; 400]

Returns the 400 variables corresponding to ChiShiftsSum

fn shifts_sum(&self, i: usize, y: usize, x: usize, q: usize) -> Self::Variable

Returns the (i,y,x,q)-th variable of ChiShiftsSum

fn state_g(&self, idx: usize) -> Self::Variable

Returns the idx-th output of a round step as a variable

fn hash_index(&self) -> Self::Variable

Returns the hash index as a variable

fn block_index(&self) -> Self::Variable

Returns the block index as a variable

fn step_index(&self) -> Self::Variable

Returns the step index as a variable

fn input(&self) -> [Self::Variable; 100]

Returns the 100 step input variables, which correspond to the:

• State A when the current step is a permutation round
• Old state when the current step is a non-root sponge

fn input_of_step(&self) -> Vec<Self::Variable>

Returns a slice of the input variables of the current step including the current hash index and step index

fn output(&self) -> [Self::Variable; 100]

Returns the 100 step output variables, which correspond to the:

• State G when the current step is a permutation round
• Xor state when the current step is an absorb sponge

fn output_of_step(&self) -> Vec<Self::Variable>

Returns a slice of the output variables of the current step (= input of next step) including the current hash index and step index

Implementors

impl<F: Field> KeccakInterpreter<F> for o1vm::interpreters::keccak::constraints::Env<F>

impl<F: Field> KeccakInterpreter<F> for o1vm::interpreters::keccak::witness::Env<F>