Extract STARK

Extract stark extracts data from RLP serialization of receipts: token ID and token value etc.

Extract stark consists of the following starks:

• Extract stark to extract data parameters;

• Keccak permutation & sponge stark to check that the hash from the receipts, which we process, is the same as from the Input stark;

• Logic XOR stark is the part of keccak function;

• Search stark searches parameters in RLP;

• Input stark is data from the Filter 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/extract-stark/tree/master

Fig. 10 — Extract stark proving scheme