---
tags: ZK,Bundler-Design
---

# Bundler MPT circuit design

## background

We need to maintain a data structure similar to the Ethereum WorldState Tree, the fields involved are

- Nonce value
- Gas balance (GasBalance)

We need to perform a SecureHash on addeHex and convert it into a fixed-length binary data. For example,
address A gets a binary string of 10111, and searches each layer of BMPT sequentially from the back to the front. As shown in the figure below, only [111] exists The longest prefix, the remaining [10] as the tail, we get the address change information

- nonce:2, gasBal:900


## Circuit frame

We use $S$ to represent the WorldState MPT mentioned above
$$S_0 \to S_1$$

$$\{K_1:V_1,K_2:V_2...K_n:V_n\}$$

How to ensure the entered key $K$ and the corresponding nonce value $V$is correct

### train of thought

What we want to achieve is to correctly maintain the correctness of the nonce value of each AA account through an MPT, so the following input

- Address Addrs of each AA account
- The nonce corresponding to each AA account address

in the circuit cannot handle conventional $Address$(because of the package non-numeric characters)
(because of the package non-numeric characters),

- It needs to be converted into a binary string
$BAddress$
- will get $BAddress$Do a Posedion hash, get$Hash(BAddress)$(Prevent DDOS attack)

### MPT data structure
There are only two types of nodes
- Branch node is an 2 item node and NodeHash = H(NodeHashLeft, NodeHashRight)
- Leaf node is an 2 item node and NodeHash = H(H(1, encodedPath), value)

Scroll's MPT is binary, and I personally feel that the efficiency will not be too high. It may be better to choose a hexadecimal MPT.

### Off-chain data preprocessing

addrBigInt = addrHex.toInt()
safeAddrHash = Poseidon(addrBigInt)
keyLayerArray[] = convertToLayerArray(safeAddrHash) 

#### Update fee MPT

Here we have to do it separately (in order of priority)
- DepositFee user deposit fee
- RefundFee settlement Tx handling fee
- WithdrawFee User withdrawal fee

Circuit Constraints for Three Functions

##### RefundFee

struct txGasInfo {
    txHash
    txGasFee
    txNonce
    userAddr
}
def RefundFee(txGasInfo[], batchTxHash):
    assert(hash(txGasInfo) == unionHash)// 确保链上的batchTxHash与传过来的字段匹配上
    for i in txGasInfo.len:
        txGasInfo[i].txNonce < nonce[txGasInfo[i].]
    

### Constraints inside the circuit

Directly refer to the construction of Scroll's [MPT](https://github.com/scroll-tech/mpt-circuit/blob/main/spec/mpt-proof.md)

- 1. Constrain the association between keyLayerArray and addrBigInt
- 2. Constrain the relationship between the incoming value and leafNode

## Refer to

- https://github.com/scroll-tech/mpt-circuit/blob/main/spec/mpt-proof.md
- https://github.com/matter-labs/zksync/blob/master/docs/protocol.md
- [Ethereum Data Structures](https://arxiv.org/pdf/2108.05513.pdf)