Filter STARK

Filters receipts according to address and topic. The scheme verifies receipt structure and correctness of hashes, provides the indexes of the beginning of the necessary event logs for the next stage, i.e. “hints” on where filtered entries are located.

Note, that some receipts will not be included in output at all.

Filter stark consists of the following starks:

• Filter stark to filter receipts;

• Input stark is data from the Bloom stark;

• Keccak permutation & sponge stark to check hashes;

• Logic XOR stark is the part of keccak function;

• 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.

Fig. 8 – Scheme of generating traces

The scheme generates a set of polynomial values and sets the public values: the hash of the previous & current blocks, address and topic. 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/filter-stark/tree/master

Fig. 9 — Filter stark proving scheme