# Storage Tree Circuit

## Layout in halo2

Suppose there would be several gadgets work together for verifing a single operation and the whole circuit would verify a bunch of operations at a time so all the gadgets are organized like following:

| MPT region |
|:---------:|
| Gadget A for 1st op |
| Gadget B for 1st op |
| ... |
| Gadget A for 2st op |
| Gadget B for 2st op |
| ... |
| paddings |

We use an unify layout, which could stack many separated gadgets in the same region. All gadgets can occupy any number of rows and compy with the scheme of our layout. The adjacent gadgets which all dedicated for the same operation are called a *op block*. And the layout contains following kinds of cols:

+ A global selector `s_row` which decide the total size of the layout;
+ n `flag_(n)` cols for maxium n gadgets which would be used in one op block. Each col would enable one of them;
+ a `op_step` col indicate in the n gadgets which one should be actived for each row;
+ 3 *public* cols dedicated for `ctrl_type`, `old_val` and `new_val`:
+ the `ctrl_type` col is used by each gadget for controlling how rows are used for among them. And our layout scheme would combile (`op_step`, `ctrl_type`) for forming a lookup to the allowed transition between adjacent steps (gadgets) and op blocks;
+ `old_val` and `new_val` are used by gadgets for assigning the values before and after the operation, which should be verified by the previous and next steps (i.e.: root or leaf value in the MPT), so the adjacent gadgets would be connected;
+ several "free cols" being shared between gadgets. Each gadget would use these cols by its own, set gates / lookup on them with a switch being controlled by the `flag` col belonging to it.

Following is an example of layout with 3 gadgets A, B and C:

| Rows | series | s_ga | s_gb | s_gc | op_step | ctrl_type | ... | old_val | new_val |root_aux |
| ---- | ------ | ------ | ------ | ------ | --------- | --------- | --- | ------- | -------- |-------- |
| 1 | 0 | 1 | 0 | 0 | 0 | 0(start) | | old1 | root1 | root1 |
| 2 | 0 | 1 | 0 | 0 | 0 | | | | | root1 |
| 3 | 0 | 1 | 0 | 0 | 0 | | | | | root1 |
| 4 | 0 | 1 | 0 | 0 | 0 | 5(leaf) | | | | root1 |
| 5 | 0 | 0 | 0 | 1 | 1 | 0 | | | | |
| ... | 0 | 0 | 0 | 1 | 1 | ... | ... | | | |
| 8 | 0 | 0 | 0 | 1 | 1 | 3 | ... | | | |
| 9 | 0 | 0 | 1 | 0 | 2 | 0(start) | | | leaf root| root1 |
| 10 | 0 | 0 | 1 | 0 | 2 | | | | | root1 |
| 11 | 0 | 0 | 1 | 0 | 2 | 4(empty) | | | | root1 |
| 12 | 1 | 1 | 0 | 0 | 0 | start | | root1 | root2 | root2 |

col `series` indicate the series number of each op block, start from 0. And col `root_aux` would be constraint to equal to the value of public col `new_val` in the first row of each op block. The can be different value assigned to `ctrl_type` col for each gadget, but only following transation would be allowed (in the form of before(`op_step`, `ctrl_type`) -> after(`op_step`, `ctrl_type`)):

+ Inside an op block (so they are called *intra-block* transation):
* before(0, 5) -> after(1, 0)
* before(0, 4) -> after(1, 0)
* before(1, 2) -> after(2, 0)
+ Between op block (so they are called *inter-block* transation):
* before(2, 4) -> after(0, 0)
* before(2, 5) -> after(0, 0)

Rules before enforce any block can begin on first gadget (A), with `ctrl_type` is 0, and such a gadget can be finished and start next gadget (C) with `ctrl_type` is 4 or 5. And gadget (C) must be finished when `ctrl_type` is 3 and start the next gadget (B), which finished with `ctrl_type` is 4 or 5 subsequently. The transition of `ctrl_type` inside a gadget is constrainted by itself.

## Lookup tables

Some lookup tables would be defined and can be used by any gadgets.

### Hash table

For verifing any calculation of hashes, gadget lookup from this table to check if corresponding hashing result occur here. All hash calculations inside table would be verified by external hashing circuit.

### Transition table

Used by gadgets to constraint the transition of `ctrl_type` among of theirself:

+ **cur:** the value of `ctrl_type` in a specified row
+ **before:** the value of `ctrl_type` in the row just above the specified one
+ **tag:** each gadget should obtain an unique tag for all the transition rules of itself so rules filled in the table could be distinginshed by different gadgets. Current we have tag 1 for MPT gadget and tag 2 for account gadget

| before | cur | tag |
| :----: |:---:|:---:|
| | | 1 |
| | | 2 |

## MPTOpGadget: for operation on a single trie

## AccountGadget: for operation on specified eth account

## PaddingGadget

The padding gadget is used for filling any unused rows for the fixed size (rows) circuit.

There should be no more transition rules avaliable for padding gadget so it act as a "terminator" of the rest rows: i.e. once a row is treated as PaddingGadget, rows below it are all belong to this PaddingGadget until it has hit the border indicated by the global selector `s_row`.

## Build them together: for operation on the alternative storage trie

We have induced an [alternatived designation for the storage in go-ethereum](https://hackmd.io/rNkgMCG0TJuZHsakphO1eA). In which the binary Merkle tree has replaced the original hexary trie and a more compact hashing scheme is applied for account data rather than RLP. The updates to account trie and state trie would be respectively verified by a MPTOpGadget, and the updating on account data is verified by AccountGadget. So under one *op-block* we have:

| Gadget type | ctrl_type | old_val | new_val |
|:-------------------------------:|:---------:| :-------: | :-------: |
| MPTOpGadget (for account trie) | 0 | trie root before | trie root after |
| ... | | | |
| MPTOpGadget (for account trie) | 4 or 5 | trie leaf before | trie leaf after |
| AccountGadget | 0 | hash of account data|hash of account data|
| ... | |
| AccountGadget | 3 or 4 | account state root | account state root |
| \[MPTOpGadget (for state trie)\]| 0 | trie root before | trie root after |
| ... | |
| \[MPTOpGadget (for state trie)\]| 4 or 5 | trie leaf before | trie leaf after |

The hash of account data would just be the leaf value in the account trie, and the root of state trie is part of account data. Notice we can skip the second MPTOpGadget if AccountGadget end with `ctrl_type` is 4, which indicate no change for account state root in the operation (i.e.: transfer eth between accounts).