0xPolygonMiden / miden-vm

STARK-based virtual machine
MIT License
612 stars 150 forks source link

Add procedures to initialize the hasher state #1311

Open hackaugusto opened 2 months ago

hackaugusto commented 2 months ago

We often write padw padw padw to initialize the hasher state on the stack. It would make the code easier to read and maintain if instead we had hasher::initialize.

Ideally we would have a initializer for each of the supported hashers in the stdlib. And a procedure to take care of initialize the state if the input requires padding.

bobbinth commented 2 months ago

The no-padding case is pretty simple to handle (as you have done in #1313). The case when the number of elements is not a multiple of 8 (i.e., not a multiple of the rate), is more tricky and will actually differ between RPO and RPX. But the procedure could look something like:

#! Input: [num_elements]
#! Ouptut: [num_permutations, PERM, PERM, PERM, ...]
export.init_state

The idea is that it will take the number of elements to hash as input, set up the initial state correctly, and then return the state together with the number of permutations needed to hash the inputs. This num_permutations can then be used for a condition of a loop to absorb the input into the state (which we frequently do in practice).

hackaugusto commented 2 months ago

For reference, here is an implementation along these lines, but instead of number of elements it uses number of words