Block STARK

Block stark aims to verify the validity of blocks.

The scheme consists of a set of different starks, connected with cross table lookup (CTL):

• Keccak stark is used to prove the correctness of SHA-3 (Keccak) permutation.

• Keccak sponge stark is used to prove the correctness of SHA-3 (Keccak) sponge.

• Logic stark is used to prove logical connectives such as AND, OR and XOR.

• Block stark is used to verify correctness of the block, constructed tree, bloom filter and correspondence with the Output stark.

• Search stark is used to check that the hash from the previous node is included in the hashing data for the next one.

• Output stark is needed to obtain the data that will be checked during aggregation with the next stage. That the output of the current stage is the same as the input of the next one.

Fig. 1 – Input data in Block stark

Firstly, the scheme generates traces for all the leaves in a trie. This step creates traces for block, keccak permutation and keccak sponge elements of the scheme and, additionally, generates traces for logic XOR since it is used in Keccak function.

The next step is to make traces for receipt root and block hash, i.e. set block traces. Scheme also generates traces for logs bloom filter and sets them to output traces.

Fig. 2 – Scheme of generating traces

Based on these results, the scheme generates a set of polynomial values and sets the hash of the previous & current blocks as public values. The output of this step is a set of values: polynomial values, public values and 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 result contains proofs for all types of polynomial values, i.e. keccak permutation, keccak sponge, logic etc., public values and output traces.

Fig. 3 – General scheme of proving starks

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/block-stark/tree/master

Fig. 4 – Detailed scheme of the proving algorithm