# Data proof Maru data proof via zk-STARKs enables efficient verification of any receipts, leafs, nodes, roots, super root that included in Patricia Merkle Trie and connect with other STARKs while proving using CTL's. ### Circuit **Private inputs** include data fields about each value: * `input` includes bytes of hashes or other data from MPT * `offset` includes the index of required element in `input` Data operation has a structure, which consists of enum DataType that indicates what type of data in operation and `DataItem`, which contains additional data as offset in block and item - bytes array of hash or volume value: ```rust #[derive(Clone, Debug, Copy)] pub(crate) struct DataItem { pub(crate) offset: usize, pub(crate) offset_in_block: usize, pub(crate) item: [u8; KECCAK_DIGEST_BYTES], } #[derive(Debug, Copy, Clone, Eq, PartialEq)] pub enum DataType { Leaf = 0, Node = 1, ReceiptsRoot = 3, BlockHash = 4, TotalSum = 5, } #[derive(Clone, Debug)] pub(crate) struct DataOp { pub(crate) input: Vec, pub(crate) contract: Option, pub(crate) value: Option, pub(crate) child: Option>, pub(crate) external_child: Option>, pub(crate) data_type: DataType, pub(crate) method_signature: Option, pub(crate) receipts_root: Option, pub(crate) token_id: Option, pub(crate) pi_sum: Option } ``` If we insert `Leaf` data type that doesn’t have `child` , then value of `contract`, `value` and `method_signature` must be included. When we insert Node, Root we have only `input` , `DataType` and `child`. To handle multiple transactions in one block, we partially "reconstruct" PMT to get one receipts root. Therefore, node will have multiple common childs. For block linking we input only parent block hash as `starting_blockhash`, and the last block hash as `ending_blockhash`. In execution trace we have column structure: * `already_absorbed_bytes` value of input bytes that have already been absorbed prior to this block. * `is_full_input_block` will be 1 if this row represents a full input block, i.e. one in which each byte is an input byte, 0 otherwise. * `len`: value of the original input length (in bytes). * `last_block` is equal to 1 if is it the last block per data operation. * `is_leaf` will be 1 if this operation has leaf data type. 8 * `is_node` will be 1 if this operation has node data type. * `is_receipts_root` will be 1 if this operation has root data type. * `is_block_hash` will be 1 if this operation has block hash data type (we use this type to prove that the last block hash in linking is correct). * `is_shadow` has value of 1 if in one block we have contract address, method signature, transfer value. * `prefix_bytes` contain the last 32 bytes of previous block or zero bytes if this the first row of data operation. * `block_bytes` contain the block being absorbed, which may contain input bytes and/or padding bytes. * `contract_address_found` will be 1 when contract address is present in block. * `method_signature_found` will be 1 when method signature is present in block. * `transfer_value_found` will be 1 when volume value is present in block. * `child_hash_found` will be 1 when child hash is present in block. * `receipts_root_found` will be 1 when root hash is present in block. * `external_child_hash_found` will be 1 when first parent hash of block is present in block. * `sold_token_id_found` will be 1 when token id value is present in block. * `calculation_id`: the ID of volume summation operation. * `range_counter` is used to store value of counter in table. * `rc_cols` are used to check bytes range for every value of block\_bytes in the trace, namely the permutation of the column and the permutation of the range. * `id`: the ID of search operation. It will be identical in Data and Search tables. * `offset_block` equals to index indicating start of sub-array in input block with required data. * `shift_num` has value of cyclic shifts number required for search proof and respectively zero number of shifts. * `zero_shift_num` has zero value. * `offset_object` has value of index indicating start of sub-array in input. * `typed_data` has values of 32 bytes array containing hash, value, contract address or method signature. ### Constraints The Data Stark aims to constrain the following aspects: * Each flag (full-input block, final block or implied dummy flag) must be boolean. * Ensure that `zero_shift_num` is always zero. * Ensure that full-input block and final block flags are not set to 1 at the same time. * If this is a final block, the next row’s original sponge state should be 0 and `already_absorbed_bytes` = 0. * If this is a full-input block, the next row’s `already_absorbed_bytes` should be ours plus 136. * Verify that the offset of the previous row is greater than one corresponding to the next row. * Verify that if this a is shadow row the next rows have equal `already_absorbed_bytes`. * A dummy row is always followed by another dummy row, so the prover can’t put dummy rows ”in between” to avoid the above checks * Ensure that if we have more than 2 objects of 32 length in one block, is shadow will be 1 and next row has the same `prefix`, `block_bytes` as previous row * Ensure that if we have `method_signature_found` = 1 then `typed_data` have to be equal to hard-coded sell signature of Curve 3pool trade (temporarily). * Ensure that if we have `contract_address_found` = 1 then `typed_data` have to be equal to hard-coded contract address of Curve 3pool trade (temporarily). * Ensure that the distance between end of contract and start of method signature is equal to 3 (feature of location elements in Curve 3pool trade receipts). * Ensure that the distance between end of method signature and start of `sold_token_id` value is equal to 35 (feature of location elements in Curve 3pool trade receipts). * Ensure that the distance between end of `sold_token_id` and start of volume value is equal to 0(feature of location elements in Curve 3pool trade receipts). The main idea of the proof relies on CTL, where we connect columns data from other STARKs: * `ctl_data()` Block bytes using filter when we have leaf, node, root data equal to concatenation columns of `xored_rate_u32s`, `original_capacity_u32s`, `updated_state_u32s` for input block. * `ctl_keccak_sponge()` Typed data of child hash have to be equal `updated_state_bytes` when it’s the final input block. * `ctl_substr_in_haystack()` The lookup guarantees that the concatenated columns of `typed_data` with `zero_shift_num` and `id` in Data table, using a row filter where `child_hash_found`, `transfer_value_found`, `method_signature_found`, `contract_address_found`, `receipts_root_found`, `external_child_hash_found`, `sold_token_id_found`, or `total_sum` = 1, equal to the concatenated columns of `NEEDLE_REGISTER` with `OFFSET` and `ID` in Search table using a filter where `IS_OUT` = 1. * `ctl_haystack_equal_data()` The lookup guarantees that the concatenated columns of `prefix`, `block_bytes`, `id`, and `shift_num` in Data table, using a filter where `child_hash_found`, `transfer_value_found`, `method_signature_found`, `contract_address_found`, `receipts_root_found`, `external_child_hash_found`, `sold_token_id_found`, or `total_sum` = 1, have the exact values of `HAYSTACK_REGISTER` in Search table. * `ctl_last_blockhash_included()` The lookup guarantees that first parent block hash and the last block hash in linking are equal to block hashes and total volume from public inputs. * `ctl_volume_value()` ensures that `typed_data` and `CALCULATION_ID` columns contain the exact values of `VALUE` and `CALCULATION_ID` in the Sum Stark. * `ctl_token_id()` ensures that `typed_data`and `CALCULATION_ID` columns contain the exact values of `TOKEN_ID` and `CALCULATION_ID` in the Sum Stark. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://maru-2.gitbook.io/maru/zk-implementation/schema/data-proof.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.