Reduce STARK

Reduce Stark performs the function of accumulator summation. The MapReduce main task is to process large amounts of data in parallel. Map Stark transforms some formulas, Reduce reduces all data together.

Reduce stark consists of the following starks:

• Reduce stark accumulates data;

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

• Input stark is data from the Map 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. 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/reduce-stark/tree/master

Fig. 12 — Reduce stark proving scheme