This PR will enable STARKs for computations that have multiple iterations of the same transition function/constraints over different inputs. This will be useful for something like proving Merkle tree membership.
The basic idea is that instead of specifying just a single set of inputs, a user will be able to specify multiple sets of inputs (in powers of 2), and this will define the number of iterations the computation will run for. For example, a STARK can be defined to prove correctness of a computation of a single element of Merkle tree proof. Then, a Merkle proof branch can be provided as a set of inputs, and the STARK will iterate over this set.
The plan is:
[x] Make steps parameter a part of STARK config.
[x] Implement multi-row inputs
[x] Create an example STARK to compute hash preimages of 8 values.
This PR will enable STARKs for computations that have multiple iterations of the same transition function/constraints over different inputs. This will be useful for something like proving Merkle tree membership.
The basic idea is that instead of specifying just a single set of inputs, a user will be able to specify multiple sets of inputs (in powers of 2), and this will define the number of iterations the computation will run for. For example, a STARK can be defined to prove correctness of a computation of a single element of Merkle tree proof. Then, a Merkle proof branch can be provided as a set of inputs, and the STARK will iterate over this set.
The plan is:
stepsparameter a part of STARK config.