# Intro

From the current circuits that we have in the zkevm project, build a zkproof to improve (network usage) light client syncing.

# Current state of light clients

Light clients don't keep a copy of the Ethereum state (accounts and storage tries). To sync a block they do the following:
1. Get the full block (with all txs) and the access list (list of all accounts and storage keys used in the block)
2. Query a node for all the MPT proofs of each account/storage from the access list via [`eth_getProof`](https://eips.ethereum.org/EIPS/eip-1186)
3. Build a partial MPT from point (2)
4. Process each tx in the block using the partial MPT as a StateDB
5. Calculate the new root of the partial MPT and verify that it matches the root in the block

# Improvements

## zkp for MPT proofs

We could build a zk proof that verifies all the state updates. The circuit could have these public inputs:
- old state root
- new state root
- list of account updates: (address, account_value_old, account_value_new)
- list of storage updates: (address, key, value_old, value_new)

Then the light client would sync a block doing the following:
1. Get the full block (with all txs) and the access list (list of all accounts and storage keys used in the block)
2. Query state values for entires in the access list of previous block
3. Build a partial StateDB from point (2)
4. Process each tx in the block using the partial StateDB
5. Verify the State update zkproof using as inputs: block_old.root, block.root, list of entries from point (2), list of entries in the partial StateDB after point (4)

The server would follow the Blockchain, and for each block:
1. Get the access list
2. Build a partial MPT from that access list (using [`eth_getProof`](https://eips.ethereum.org/EIPS/eip-1186))
3. Apply all reads and updates that happened in the block (to end in the new block state), recording MPT proofs in between
4. Generate the zk proof of all updates using the recorded MPT proofs as witness

Improvements for light clients:
- Skip root calcuation of updated partial MPT
- Skip MPT proofs network transfer

### NOTES

In case we can't prove a full block (because all the verification doesn't fit in a single proof), we can make proofs of k MPT updates:
1. Get block access list
2. Split accesses into chunks
3. Make a proof of each chunk, where the roots are chained until we arrive to the new block root

## zkp for signature verification

Each tx comes with a signature. The light node needs to recover the sender address of each tx from the hash of the tx and the signature.

We could build a zk proof that verifies all the tx signatures. The circuit could have these public inputs:
- list of tx sender addresses
- list of tx hashes

Note: a more advanced version could replace the list of tx hashes by the block hash. This would require proving inclusion of each tx in the Transaction Trie + proving the block Hash from its fields (including the Transaction Trie Root).

Improvements for light clients:
- Skip signature recovery
- Skip signature network transfer

# Work to do

- Build a new zk circuit by reusing the components we have developed for this use case
- Build the infrastructure, protocols, etc. to continuously monitor L1 blocks, generate their proofs, and serve them to light clients.

# Exercices to validate this project
- A. Figure out the network usage to sync an average block by a light client
- B. Figure out the network savings with the zkp for MPT proofs
- C. Figure out the network savings with the zkp for signature verification
- D. Figure out how many keccacks we can prove in a single proof VS how many keccacks are required for an average block MPT updates
- E. Figure out how many signatures we can prove in a single proof VS how many txs there are in an average block

# Links

- https://ethereum.org/en/developers/docs/nodes-and-clients/light-clients/
- [Geth light client documentation](https://geth.ethereum.org/docs/fundamentals/les)
- [Light client summit](https://www.youtube.com/watch?v=zxQvEEY9e4k&list=PLJijNYoOwnst-feT7PsCLaSdiFYzWtf7j)
-

# light node

- Storage:
- last block header (N-1)
- last 256 block hashes

- How it works to sync
- get new block (headers + txs) from P2P (N)
- access to another node to (maybe P2P, but now REST):
- get "partial" state (account + storage) of last block (N-1) of data accessed by current block txs
- get the proof of state accesses+changes from N-1 to N
- execute txs and build a statedb
- check for changes in account value & storage (old -> new)
- use this list of changes to verify the proof
- old_state_root (N-1)
- new_state_root (N)
- list of accesses (dynamic)
- list of changes (dynamic)
- considerations about proof
- the list of accesses and list of changes can be hashed in the public input lower the proof size (and can be posseidon)

## B. Network savings with the zkp for MPT proofs

https://github.com/adria0/go-ethereum/tree/statedblog

- acc:r : number of account reads
- acc:w : number of account read+write
- code : bytes of the bytecode
- acc:mt : bytes of merkle paths in account
- sto:r : number of slot reads
- sto:w : number of slot read+write
- sto:mt : bytes of merkle paths in account
- nw : no witness: `(acc:r+acc:w)*4*32 + code + (sto:r+sto:w)*2*32`
- w : witness: `acc:mt` + `sto:mt`
- gain : (nw+w) / nw

block;Acc:r;Acc:w;Code;Acc:mt;Sto:r;Sto:w;Sto:mt;nw;w;Gain
17737100;133;251;1556774;1408995;633;733;2484632;1693350;3893627;3,29
17737101;131;219;1686230;1284522;615;460;1540033;1799830;2824555;2,56
17737102;165;261;2091148;1566419;727;630;1911717;2232524;3478136;2,55
17737103;123;207;1746128;1213696;598;493;1673262;1858192;2886958;2,55
17737104;218;216;2406421;1593295;796;609;2093578;2551893;3686873;2,44
17737105;160;263;1908617;1553598;705;621;2010399;2047625;3563997;2,74
17737106;98;193;1244962;1069580;524;712;2434823;1361314;3504403;3,57
17737107;128;254;1766707;1404230;661;557;1808555;1893555;3212785;2,69
17737108;115;203;1547201;1168123;728;760;2702154;1683137;3870277;3,29
17737109;148;179;1770831;1202421;648;682;2317245;1897807;3519666;2,85
17737110;145;292;1768831;1606502;951;592;1954050;1923519;3560552;2,85
17737111;135;220;1649767;1307086;840;760;2639933;1797607;3947019;3,19
17737112;133;211;1672652;1263626;739;739;2439479;1811276;3703105;3,04
17737113;96;226;1285868;1182767;500;378;1359752;1383276;2542519;2,83
17737114;96;200;1143320;1088053;436;577;1943323;1246040;3031376;3,43

**average gain: 2,9 -> 290% improvment using snarks over mt paths**

note: 1 MTnode = 532 bytes, 1 MTleaf = 54 bytes

### D. How many keccacks are required for an average block MPT updates

From data collected from B, average MTs size is 3415056, if each node takes 532 bytes, it is approx 6420 nodes if we take into consideration that we need a keccak for each node 3415056/532 so it's like 6420 keccaks per block

From new data collected, removing duplicated MT nodes, the average MT size is 1587118, meaning 1587118/532 nodes, 2938 nodes

- from circuit https://github.com/privacy-scaling-explorations/zkevm-circuits/blob/main/zkevm-circuits/src/keccak_circuit/keccak_packed_multi.rs#L11 300 keccak rows x 136 bytes, so 4 absortions per 532 bytes => 4*300 rows per 532 bytes, 2938 * 4 * 300 = 3.5Mrows; 2^22

- big case, block 1345786
- account mt nodes bytes 1452507
- storage mt nodes bytes 1345786
- * 1.5 (block is 20Mgas and can be 30Mgas)
- 4.2M
- 4.2M / 532 = 7900 nodes
- 7900 * 4 * 300 => 2^24 rows