> For the complete documentation index, see [llms.txt](https://maru-2.gitbook.io/maru/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maru-2.gitbook.io/maru/zk-implementation/schema/search-proof.md).

# 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.