Struct KeccakVmAir

pub struct KeccakVmAir {
    pub execution_bridge: ExecutionBridge,
    pub memory_bridge: MemoryBridge,
    pub bitwise_lookup_bus: BitwiseOperationLookupBus,
    pub ptr_max_bits: usize,
    /* private fields */
}

Fields

execution_bridge: ExecutionBridge

memory_bridge: MemoryBridge

bitwise_lookup_bus: BitwiseOperationLookupBus

Bus to send 8-bit XOR requests to.

ptr_max_bits: usize

Maximum number of bits allowed for an address pointer

Implementations

impl KeccakVmAir

pub fn new( execution_bridge: ExecutionBridge, memory_bridge: MemoryBridge, bitwise_lookup_bus: BitwiseOperationLookupBus, ptr_max_bits: usize, offset: usize, ) -> Self

Constructs a new KeccakVmAir.

impl KeccakVmAir

pub fn eval_keccak_f<AB: AirBuilder>(&self, builder: &mut AB)

Evaluate the keccak-f permutation constraints.

WARNING: The keccak-f AIR columns must be the first columns in the main AIR.

pub fn constrain_consistency_across_rounds<AB: AirBuilder>( &self, builder: &mut AB, local: &KeccakVmCols<AB::Var>, next: &KeccakVmCols<AB::Var>, )

Many columns are expected to be the same between rounds and only change per-block.

pub fn constrain_block_transition<AB: AirBuilder>( &self, builder: &mut AB, local: &KeccakVmCols<AB::Var>, next: &KeccakVmCols<AB::Var>, start_write_timestamp: AB::Expr, )

pub fn constrain_padding<AB: AirBuilder>( &self, builder: &mut AB, local: &KeccakVmCols<AB::Var>, next: &KeccakVmCols<AB::Var>, )

Keccak follows the 10*1 padding rule. See Section 5.1 of https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf Note this is the ONLY difference between Keccak and SHA-3

Constrains padding constraints and length between rounds and between blocks. Padding logic is tied to constraints on is_new_start.

pub fn constrain_absorb<AB: InteractionBuilder>( &self, builder: &mut AB, local: &KeccakVmCols<AB::Var>, next: &KeccakVmCols<AB::Var>, )

Constrain state transition between keccak-f permutations is valid absorb of input bytes. The end-state in last round is given by a_prime_prime_prime() in u16 limbs. The pre-state is given by preimage also in u16 limbs. The input block_bytes will be given as bytes.

We will XOR block_bytes with a_prime_prime_prime() and constrain to be next.preimage. This will be done using 8-bit XOR lookup in a separate AIR via interactions. This will require decomposing u16 into bytes. Note that the XOR lookup automatically range checks its inputs to be bytes.

We use the following trick to keep u16 limbs and avoid changing the keccak-f AIR itself: if we already have a 16-bit limb x and we also provide a 8-bit limb hi = x >> 8, assuming x and hi have been range checked, we can use the expression lo = x - hi * 256 for the low byte. If lo is range checked to 8-bits, this constrains a valid byte decomposition of x into hi, lo. This means in terms of trace cells, it is equivalent to provide x, hi versus hi, lo.

pub fn eval_instruction<AB: InteractionBuilder>( &self, builder: &mut AB, local: &KeccakVmCols<AB::Var>, register_aux: &[MemoryReadAuxCols<AB::Var, RV32_REGISTER_NUM_LIMBS>; 3], ) -> AB::Expr

Receive the instruction itself on program bus. Send+receive on execution bus. Then does memory read in addr space 1 to get dst, src, len from memory.

Adds range check interactions for the most significant limbs of the register values using BitwiseOperationLookupBus.

Returns start_read_timestamp which is only relevant when local.instruction.is_enabled. Note that start_read_timestamp is a linear expression.

pub fn constrain_input_read<AB: InteractionBuilder>( &self, builder: &mut AB, local: &KeccakVmCols<AB::Var>, start_read_timestamp: AB::Expr, mem_aux: &[MemoryReadAuxCols<AB::Var, KECCAK_WORD_SIZE>; 34], ) -> AB::Expr

Constrain reading the input as block_bytes from memory. Reads input based on is_padding_byte. Constrains timestamp transitions between blocks if input crosses blocks.

Expects start_read_timestamp to be a linear expression. Returns the start_write_timestamp which is the timestamp to start from for writing digest to memory.

pub fn constrain_output_write<AB: InteractionBuilder>( &self, builder: &mut AB, local: &KeccakVmCols<AB::Var>, start_write_timestamp: AB::Expr, mem_aux: &[MemoryWriteAuxCols<AB::Var, KECCAK_WORD_SIZE>; 8], )

pub fn timestamp_change<T: AbstractField>(len: impl Into<T>) -> T

Amount to advance timestamp by after execution of one opcode instruction. This is an upper bound dependant on the length len operand, which is unbounded.

Trait Implementations

impl<AB: InteractionBuilder> Air<AB> for KeccakVmAir

fn eval(&self, builder: &mut AB)

impl<F> BaseAir<F> for KeccakVmAir

fn width(&self) -> usize

The number of columns (a.k.a. registers) in this AIR.

fn preprocessed_trace(&self) -> Option<DenseMatrix<F>>

impl<F> BaseAirWithPublicValues<F> for KeccakVmAir

fn num_public_values(&self) -> usize

impl Clone for KeccakVmAir

fn clone(&self) -> KeccakVmAir

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for KeccakVmAir

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<F> PartitionedBaseAir<F> for KeccakVmAir

fn cached_main_widths(&self) -> Vec<usize>

By default, an AIR has no cached main trace.

fn common_main_width(&self) -> usize

By default, an AIR has only one private main trace.

impl Copy for KeccakVmAir