STARK Proving

The process by which a single prover is able to certify that it conducted Creditcoin Oracle tasks faithfully. Otherwise these tasks would need to be completed by the entire validator set.

An introduction to STARK proving

STARK proving describes the process by which a single prover is able to certify that it conducted the Creditcoin Oracle tasks faithfully. These proof make use of the STARK (Scalable Transparent ARgument of Knowledge) proof system, which allows for computations performed by any prover to be verified trustlessly by any other member of the validator set. This way, we can compute a proof once and share its result without having to recompute its value, and without needing to trust the sender.

Proof Generation

The STARK proof system is used to allow the off-chain creation of oracle query proofs. This is handled by a special program known as a STARK prover. This prover has access to the data it needs to generate the proof, which it gets by following the state of any source chain it is generating proofs for. Currently, only Ethereum is supported.

Proof Verification

Once a STARK proof has been generated, it is checked by a STARK verifier. This verifier is able to check the validity of a proof, and therefore the computation it is proving, by only having access to the proof itself. In this way, STARK proofs can be viewed as a succinct proof of the correct execution of any Turing-complete program, allowing us to verify the validity of an arbitrarily complicated system. We use this in the case of Creditcoin to allow for the creation query proofs on a single machine (the prover) without the risk of having it submit bogus results or intentionally mislead Creditcoin Validators, since this would result in an invalid proof and would be detected during proof verification.

Cairo

One way to use this proof system to verify the unaltered execution of an algorithm is by expressing it in a domain specific language called Cairo. This program is then compiled and run in a virtual machine known as the CairoVM, which is responsible for generating a trace of the program's execution along with a mathematical proof of this execution. Together with the trace, this proof can be used to trustlessly verify the correct execution of said program. Our current implementation uses “Cairo Zero“.

📚 For a more in-depth introduction to STARK proving, check out this article.

STARK Proving in Creditcoin

We use STARK proving in Creditcoin to verify the truthfulness of two main offchain processes:

1. Continuity proofs, which validates the fact that a proof's query follows the state of the source chain as it has been attested to so far on Creditcoin. STARKs certify that continuity proving was conducted faithfully.

2. Merkel proofs, which validate that a transaction is part of the block which is being queried as part of the proof. STARKs certify that merkle proving was conducted faithfully.

Pre-processing

Some additional work has to be done to prepare the input data to be passed to the prover or verifier:

• query data layout: query data offsets and sizes that were merged/compressed and then ordered

• attestation chain segments: Merkle roots of the attestation chain up to and including the tail parent digest as computed by the Creditcoin Attestors.

• transaction tree: sequential Merkle tree of all transactions and their receipts of the queried block

• transaction path: determine all siblings along the path to the transaction specified by the queried index

Proof Inputs

Once we are finished with the pre-processing step of our STARK proving, we can move on to supply the actual proof inputs. Currently, booth continuity proofs and merkle proofs are generated using the same Cairo program, which receives the following inputs:

• the query metadata, which includes the chain id, block height, transaction index, and data layout

• the queried block's transaction tree parameters, like its arity, height and root hash

• the queried indexes transaction path including all sibling hashes

• the raw transaction data itself, corresponding to the hashed leaf in the Merkle path

• the relevant attestation chain segments to construct continuity proof to validate current attestation chain

• the out-of-bounds flag, a boolean flag that indicates that the transaction index queried is outside of the bounds of the block

Proof Processing

Once all the requires inputs have been gathered, we can start generating the proof. The Cairo program we run performs the following verification:

• Verifies that the transaction data matches the merkle path leaf hash.

• Confirms consistency of the merkle path with the merkle root.

• Extends the continuity proof.

• Computes the hash of the query offsets.

For more information on the underlying merkle proofs, check out the section on Merkle Proving Transaction Inclusion.

Proof Outputs

Finally, the Cairo program will output the following values:

• the query index as computed from the Merkle path

• the attestation checkpoint digest as computed by reconstructing the attestation chain

• the number of blocks in the continuity attestation chain (i.e. size of one checkpoint)

• the Pedersen hashes of each entry of the query data layout (if query is not out of bound)

Post-processing

The prover client is then required to run the following additional checks:

• Computes the attestation checkpoint block number using the continuity proof length and query block number, then verifies the corresponding attestation checkpoint digest

• Confirms the query index matches the returned outputs

• Validates the hashes of the query data layout by comparing locally computed hashes with the returned outputs