StarkEx, Cairo, and SHARP

In the overview, we presented SHARP as a component of the system that includes the STARK Prover. Here we discuss the interface between, and the role of, the StarkEx service and SHARP and present how the Cairo programming language is used.

The Cairo Programing Language

Cairo is a general, Turing-complete language. Read more about the Cairo language here.

Each batch of transactions that are proven together represent a successful execution of a Cairo program. Note that Cairo operates in the following framework:

  • It is stateless. i.e., the Cairo/Prover component of the system does not hold the off-chain state.​

  • It cannot prove invalid transactions. By comparison, on L1, an invalid transaction can be executed, shown to be invalid, and reverted. If the input to the Cairo program contains an invalid transaction, the Cairo program does not complete (and, therefore, we have nothing to prove).

The Goals of the StarkEx Back End

The StarkEx back end service has two goals that support the Cairo framework described above:

  1. Ensure that all transactions to be executed and proved are valid according to the application business logic. This guarantees that the Cairo program will be able to complete a run with them as an input.

  2. Prepare the input for the Cairo program and run it. This is done by first aggregating a sufficient number of valid transactions into one batch and then invoking the Cairo program with this batch of transactions as the input. In this process, the STARK Prover attests to the Cairo program's correct execution.

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

StarkEx Proves Batches

As a result of the modus operandi described above, we see that StarkEx works in units (and proves the validity) of batches. This is important since each batch contains a header in addition to the transactions that are used in the proof.

As an example of how the batch header is used, 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. Thus, this must be done with blockchain time. However, comparing each and every timestamp in the batch on-chain to the blockchain time is very expensive.

To solve this problem and reduce costs, the StarkEx back end 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 the proof submission, it is sufficient for the on-chain contract to only compare the minimal time with the blockchain time.

SHARP

The flow so far describes a StarkEx deployment with its own STARK Prover. However, from StarkEx V3, all StarkEx deployments send their Cairo program execution to SHARP – the Shared Prover service.

If the claim of a singular StarkEx is "The following Cairo program P1P_{1} finished its run successfully with input inp1\text{inp}_1, and had output out1\text{out}_1, the claim of the SHARP is: the Cairo program PSHARPP_{\text{SHARP}} got the inputs P1,…,PnP_1,\dots,P_n, inp1,…,inpn\text{inp}_1,\dots, \text{inp}_{n} and got the outputs out1,…,outn\text{out}_1,\dots, \text{out}_n​

Several claims/proofs are combined into one due to the exponential ratio between the cost of verifying a statement and the cost of executing it. Thus, verifying one proof made by SHARP will cost roughly the same as verifying one proof made by a single StarkEx, but this cost can be divided between several applications.