Trait Algorithm

pub trait Algorithm: BasicSnippet {
    // Required methods
    fn rust_shadow(
        &self,
        stack: &mut Vec<BFieldElement>,
        memory: &mut HashMap<BFieldElement, BFieldElement>,
        nondeterminism: &NonDeterminism,
    );
    fn pseudorandom_initial_state(
        &self,
        seed: [u8; 32],
        bench_case: Option<BenchmarkCase>,
    ) -> AlgorithmInitialState;

    // Provided methods
    fn preprocess<T: BFieldCodec>(
        _meta_input: T,
        _nondeterminism: &mut NonDeterminism,
    ) { ... }
    fn corner_case_initial_states(&self) -> Vec<AlgorithmInitialState> { ... }
}

An Algorithm can modify memory and take ND_input.

An Algorithm is a piece of tasm code that can modify memory even at addresses below the dynamic memory allocator, and can take nondeterministic input. It cannot read from standard in or write to standard out.

See also: closure, function, procedure, accessor, mem_preserver, read_only_algorithm

Required Methods

fn rust_shadow( &self, stack: &mut Vec<BFieldElement>, memory: &mut HashMap<BFieldElement, BFieldElement>, nondeterminism: &NonDeterminism, )

fn pseudorandom_initial_state( &self, seed: [u8; 32], bench_case: Option<BenchmarkCase>, ) -> AlgorithmInitialState

Provided Methods

fn preprocess<T: BFieldCodec>( _meta_input: T, _nondeterminism: &mut NonDeterminism, )

Take a object about which something is being proven in order to extract out the right nondeterminism. Update the mutably referenced non-determism argument.

For example:

• When proving the correct verification of a proof, you might want to pull all digests out of the authentication structures and put them in the digests field of the non-determinism. This way the VM can avoid the processing required by authentication structures and just divine in the right digests as it walks up the Merkle trees.
• When proving the correct sorting of a list, the VM ought to avoid running a sorting algorithm; instead it should divine the sorted list and then prove that the two lists are equal. The preprocessing step in this case would take the unsorted list, sort it, and use the sorted list to populate the non- determinism.
• When verifying a Falcon signature, at some point the NTT of a vector is needed. The VM should not compute the NTT because expensive; instead it should divine the NTT-transformed vector and verify that it satisfies the right relation. In this case the preprocessor calculates the NTT and populates the non-determinism with the transformed vector.

fn corner_case_initial_states(&self) -> Vec<AlgorithmInitialState>

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl Algorithm for SwapUnchecked