Map STARK

Map Stark processes operations from the formula. The expressions come from the front request in Reverse Polish notation.

Now we can process the formula with 128 maximum stack depth. At the output we get the result from the formula. There is also a main formula and a filter formula, that is, if the filter formula is executed (logical formula), then we execute the main formula, the filter formula is an option.

Map stark consists of the following starks:

• Map stark processes each operation from the formula, throwing it into additional task stars and obtaining the result;

• Arithmetic stark works with mathematics, operations +, -, *, /, ==;

• Logic stark performs binary arithmetic;

• Input stark is data from the Extract stark;

• Output stark is the date provided to the next stage.

These all starks are connected with cross table lookup (CTL), which is also verified later to confirm the correctness of data used in the scheme.

The scheme generates a set of polynomial values and sets the public values: the hash of the previous & current blocks, formula hash. This scheme also checks the obtained proof from the previous step. The output of this step is a set of values: polynomial values, public values, input & output traces.

The next step is to commit the obtained polynomial values from the previous step.

Then we generate proofs using polynomial values, committed data and CTL. The output is a set of stark proofs, public values, CTL, input & output traces.

The obtained stark proofs are provided to the verification algorithm, which generates a plonky2 proof to confirm all stark proofs correctness.

Implementation:

https://github.com/proxima-one/map-stark/tree/master

Fig. 11 — Map stark proving scheme