Zero Knowledge Proof — Deep into zkEVM source code (MPT Circuit)

1. Background Knowledge

1.1 ETH Account Model

Account {
Nonce,
Balance,
CodeHash,
StorageRoot,
}

1.2 RLP Encoding

The string “dog” = [ 0x83, ‘d’, ‘o’, ‘g’ ]

The list [ “cat”, “dog” ] = [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]

The empty string (‘null’) = [ 0x80 ]

The empty list = [ 0xc0 ]

The integer 0 = [ 0x80 ]

The encoded integer 0 (’\x00’) = [ 0x00 ]

The encoded integer 15 (’\x0f’) = [ 0x0f ]

The encoded integer 1024 (’\x04\x00’) = [ 0x82, 0x04, 0x00 ]

The set theoretical representation of three, [ [], [[]], [ [], [[]] ] ] = [ 0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0 ]

1.3 Compact Encoding

> [ 1, 2, 3, 4, 5, ...]
'11 23 45'
> [ 0, 1, 2, 3, 4, 5, ...]
'00 01 23 45'
> [ 0, f, 1, c, b, 8, 10]
'20 0f 1c b8'
> [ f, 1, c, b, 8, 10]
'3f 1c b8'
hex char   bits   |   node type partial     path length
----------------------------------------------------------
0 0000 | extension even
1 0001 | extension odd
2 0010 | terminating (leaf) even
3 0011 | terminating (leaf) odd

1.4. Merkle Patricia Trie (MPT)

2. MPT Prooof

2.1. What does MPT need to Prove?

MPT circuit checks that the modification of the trie state happened correctly.

The circuit checks the transition from val1 to val2 at key1 that led to the change of trie root from root1 to root2 (the chaining of such proofs is yet to be added)

2.2. Representations of the complete path, former state and latter state

2.3. The representation and relationship of Branch/Extension Node

2.4. Representation of Leaf

Key S

Nonce balance S

Nonce balance C

Storage codehash S

Storage codehash C

Leaf key S

Leaf value S

Leaf key C

Leaf value C

Leaf in added branch

2.5. How to prove the accurcy of Hash and its location

2.6. Hash based RLC Computation

Branch 0 | Branch 0
| Branch 1
Leaf 1 | Leaf 2
Branch 1 | Branch 1
| Leaf 2
Branch 1 | Branch 1
Leaf 1 | Leaf 2

2.7. Key RLC Calculations

n0n1, n2n3, ..., n62n63
key_rlc = (n0 * 16 + n1) + (n2 * 16 + n3) * r + (n4 * 16 + n5) * r^2 + ... + (n62 * 16 + n63) * r^31
[228,130,0,149,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
key_rlc = key_rlc_prev + 149 * key_rlc_mult
key_rlc = key_rlc_prev + 9 * key_rlc_mult + 5 * 16 * key_rlc_mult * r
[228,130,19,149,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
key_rlc = key_rlc_prev + ((19 - 16) * 16 + 9) * key_rlc_mult + 5 * 16 * key_rlc_mult * r
key_rlc = key_rlc_prev + (19 -16) * key_rlc_mult + 149 * key_rlc_mult * r
226,16,160,172,105,12...

3. MPT Circuit Resource Consumption

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store