Schema

We generate proofs of requested block range to prove volume of Curve 3pool. Our circuits prove the integrity of Keccak, volume summation that includes arithmetic addition operating on 256 bit values, data integrity from receipts, transactions and integrated application logic.

Please find the items below for further details on how proofs are generated and descriptions of the proofs:

• Sum proof

• Search proof

• Data proof

• Keccak proof

• Keccak sponge proof

• Logic proof

• Arithmetic proof

Each STARK, such as DataStark, SumStark, SearchStark. . . etc. are implemented as a sub STARK proof of the AllStark structure, that performs each proof verification as a specific part of volume proving of trade pool by using Patricia Merkle Tree from Ethereum Node. The structure allow to three things:

• Check the correct integration between circuits via the shared croos table lookups, to verify that the table layouts match.

• Allow having a one structure of proofs for which a proofs can be generated and verified if we build regular proofs.

• Allow having a single structure for which a proof can be generated and verified recursively using aggregation. The main idea to aggregate each child STARK proof to one proof that we will name ”root proof” in terms of SNARK and verify it.

In public inputs, we include the counted volume as total_sum, the parent block hash of the first block header for the desired period as starting_blockhash, and the last block hash as ending_blockhash for volume proving. Other data required for proof generation is placed in private inputs. Additionally, we have the option to recursively aggregate the two primary STARK proofs to optimize both proof generation speed and verification cost.

Using proof wrapper we can reduce number of PI's to one Poseidon hash and prove that the final proof for wanted period is correct.

Patricia Merkle Trie

MPT is a prefix Patricia tree in which the keys are byte sequences. In this tree, edges consist of sequences of nibbles (half-bytes). Consequently, one node can have up to seventeen children (corresponding to branches from 0x0 to 0xF). Nodes are divided into three types:

• Leaf node: A node that contains a portion of the path and a stored value. It is the endpoint in the chain.

• Branch node: A node used for branching. It contains from 1 to 17 references to child nodes. It may also contain a value.

• Extension node: An addition node that stores a portion of the path shared by multiple child nodes, as well as a reference to a branch node further along the path.

This data structure allows for efficient storage of key-value pairs while ensuring data integrity verification. You can fully read description of MPT at the following link.

Merkle Patricia Receipt Trie in Ethereum

For volume proving we use receipts trie due to the fact that every block has its own receipts trie. A path here is rlp(transactionIndex). transactionIndex is its index within the block it’s mined. To query a specific receipt in the Receipts trie, the index of the transaction in its block, the receipt payload and the transaction type are required.

The returned receipt can be of type Receipt which is defined as the concantenation of TransactionType and ReceiptPayload. To prove volume of pool trades we need to get access data from MPRT of blocks, where the data for each transaction, in deserialized form, contains the following fields:

• sold token name: String name of the token being exchanged in the trade

• bought token name: String name of the token received as a result of the exchange

• sold token volume: Decimal amount of tokens (a floating-point decimal number) being exchanged.

• bought token volume: Decimal amount of tokens (a floating-point decimal number) received as a result of the exchange

For each token, trades are filtered where either sold token name or bought token name matches the name of that token. After, the trade data is serialized and included in the Event Log, where the following fields are important for verification:

• address address of the contract in which the event was saved in log.

• topics contains arbitrary auxiliary data in the form of a vector of data of type H256.

• data contains the values of the event’s parameters.

• transaction_index the index of the transaction, which determines the order of execution of transactions within a block