Search proof

Maru search proof via zk-STARKs enables efficient verification of any transaction data(hashes, ... etc) that included in Patricia Merkle Trie. Using this approach we can ensure that volume values, contract address, method signature, hashes are included in RLP encoding.

For example, we have to ensure that BranchNode hashes consist of previous hash of RLP BranchNode , LeafNode or receipts_root in RLP of block header. To implement this calculation, we got the idea to search 32 bytes in array of 136 + 32 bytes (block_size + postfix bytes of previous block) to ensure that searched bytes not will be between start of one and end of the next block. Using right cyclic shifts we create one row per shift until the first 32 bytes of HAYSTACK_REGISTER will be equal to 32 bytes in NEEDLE_REGISTER, where the searched bytes. As input we get from trusted setup we use start indexes of each data array (value, contract address, ... etc).

Circuit

Private inputs include data fields about each value:

• input includes one block of 136 bytes and 32 bytes of previous block

• sub_string includes searched 32 bytes

• offset includes the index of first sub_string element

• id includes the number of search operation

In execution trace we use such fields:

• IS_IN will be set to 1 in rows where the initial sub-array is present.

• IS_OUT will be set to 1 where the first 32 bytes of HAYSTACK_REGISTER are equal to NEEDLE_REGISTER.

• DUMMY_ROW indicates padding rows.

• OFFSET is a number of offsets in block, after using cyclic shifts will reduced to one per shift operation .

• IS_SHIFT will be set to 1 in rows where we used a right cyclic shift.

• HAYSTACK_REGISTER register of array.

• NEEDLE_REGISTER register of subarray

• ID number of search operation

Constraints

The Search Stark aims to constrain the following aspects:

1. Verify that the first 32 elements in HAYSTACK_REGISTER are equal to the first 32 elements in NEEDLE_REGISTER.

2. IS_IN and IS_OUT can have values in the range of {0, 1}.

3. Confirm that the last element of the haystack’s first row of each search operation equals the first element in the next row of the cyclic shift when IS_IN = 1, and IS_IN in the next row equals to 0.

4. Ensure that the previous element in the row of the cyclic shift equals the next element of the next row when IS_IN = 0, and the rows are not dummy.

5. Check that the offset in the row equalst to 0, when IS_OUT = 0.

6. Verify that the offset of the previous row is greater than one corresponding to the next row

The main idea of the proof relies on CTL, where we build two functions for CTL proofing:

• ctl_substr_in_haystack() guarantees that the concatenated columns of typed_data with zero_shift_num (always zero) in the 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 the Search table using a filter where IS_OUT equals 1.

• ctl_haystack_equal_data() guarantees that the concatenated columns of prefix, block_bytes, and shift_num in the 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 the Search table.