Cairo and SHARP in StarkEx

The Cairo programming language

Cairo is a general, Turing-complete language. For more information about the Cairo language, see cairo-lang.org.

The Cairo program in StarkEx

The Ambassador component of the StarkEx backend includes a Cairo program that receives and processes each batch of transactions. After the program processes the batch, StarkEx sends the resulting execution trace as a job to the prover.

Cairo is stateless, so the Cairo program does not hold the off-chain state.

Cairo cannot prove invalid transactions. In contrast, an invalid on-chain transaction can be executed, shown to be invalid, and reverted. If the input to the Cairo program contains an invalid transaction,the program does not execute, so there is nothing to prove.

The StarkEx backend does the following before submitting the transaction batch to the Cairo program:

  • Validates all transactions according to the application’s business logic, thus guaranteeing that the Cairo program can successfully complete execution.

  • Prepares the input for the Cairo program by aggregating a sufficient number of valid transactions into a batch, and then invokes the Cairo program with the batch as input.

The Cairo program receives both the transaction list and information to correlate with the previous state. For example, if a transaction transfers 500 USDC from Alice to Bob, the input to the Cairo program includes the previous balance of Alice’s vault, with a Merkle path that ties it to the previous root of the Balances tree.

About batches

Each batch that StarkEx proves is composed of:

  • a header

  • the transactions whose validity StarkEx proves

For example, consider the expiration_timestamp field, used in trades and transfers. Since the Cairo program is stateless, it is not aware of the current time and thus cannot verify the expiration of time. So this check must use blockchain time. However, comparing each and every timestamp in the batch to the blockchain time on-chain is very expensive.

To solve this problem and reduce costs, the StarkEx backend puts the minimum expiration time of all the transactions in the batch, in the batch header. The Cairo program attests that the expiration timestamp in each transaction is equal to or later than this minimum. After StarkEx submits the proof on-chain, the on-chain contract only needs to compare the minimal time with the blockchain time.

About SHARP

All StarkEx deployments send their Cairo program execution traces to the Shared Prover service, SHARP.

Several proofs are combined into one due to the exponential ratio between the cost of verifying a statement and the cost of executing it. So verifying one SHARP proof costs approximately the same as verifying one proof made by a single StarkEx-powered application, but with SHARP, this cost is divided between multiple StarkEx-powered applications.

SHARP recursively combines several claims into one proof. SHARP proves statements as they arrive at the proving stage. Their proofs can be merged over and over into recursive proofs in various patterns until, at a certain point, the resulting proof is submitted to an on-chain verifier contract. For example, see Figure 1, “A typical recursive proving flow”.

recursive STARKs
Figure 1. A typical recursive proving flow