owned this note
owned this note
Published
Linked with GitHub
# M4 example
###### tags: binary m4
#### Values
To keep the example short, keys are one byte long and so are values.
| key | Value |
|-----|-------|
| 0 | 'a' |
| 1 | 'b' |
| 128 | 'c' |
| 255 | 'd' |
#### Tree structure
```graphviz
digraph D {
node [shape="rect"]
root
0
00
000
0000
00000
000000
0000000
00000000 [label="a"]
00000001 [label="b"]
1
10
100
1000
10000
100000
1000000
80 [label="c"]
11
111
1111
11111
111111
1111111
FF [label="d"]
root -> 0 -> 00 -> 000 -> 0000 -> 00000 -> 000000 -> 0000000 -> 00000000
0000000 -> 00000001
root -> 1 -> 11 -> 111 -> 1111 -> 11111 -> 111111 -> 1111111 -> FF
1 -> 10 -> 100 -> 1000 -> 10000 -> 100000 -> 1000000 -> 80
}
```
### Merkelization
```graphviz
digraph D {
node [shape="rect"]
root [label="hash(H_0 || H_1)"]
0 [label="H_0 = hash(H_00 || ∅)"]
00 [label="H_00 = hash(H_000 || ∅)"]
000 [label="H_000 = hash(H_0000 || ∅)"]
0000 [label="H_0000 =\nhash(H_00000 || ∅)"]
00000 [label="H_00000 =\nhash(H_000000 || ∅)"]
000000 [label="H_000000 =\nhash(H_0000000 || ∅)"]
0000000 [label="H_0000000 =\nhash(hash(0 || \"a\") || hash(0 || \"b\"))"]
00000000 [label="hash(0 || \"a\")"]
00000001 [label="hash(0 || \"b\")"]
1 [label="H_1 = hash(H_10 || H_11)"]
10 [label="H_10 = hash(H_100 || ∅)"]
100 [label="H_100 = hash(H_1000 || ∅)"]
1000 [label="H_10000 =\nhash(H_10000 || ∅)"]
10000 [label="H_10000 =\nhash(H_100000 || ∅)"]
100000 [label="H_100000 =\nhash(H_1000000 || ∅)"]
1000000 [label="H_1000000 =\nhash(hash(0 || \"c\") || ∅)"]
80 [label="hash(0 || \"c\")"]
11 [label="H_11 = hash(∅ || H_111)"]
111 [label="H_111 = hash(∅ || H_1111)"]
1111 [label="H_1111 =\nhash(∅ || H_11111)"]
11111 [label="H_11111 =\nhash(∅ || H_111111)"]
111111 [label="H_111111 =\nhash(∅ || H_1111111)"]
1111111 [label="H_1111111 =\nhash(∅ || hash(0 || \"d\"))"]
FF [label="hash(0 || \"d\")"]
root -> 0 -> 00 -> 000 -> 0000 -> 00000 -> 000000 -> 0000000 -> 00000000
0000000 -> 00000001
root -> 1 -> 11 -> 111 -> 1111 -> 11111 -> 111111 -> 1111111 -> FF
1 -> 10 -> 100 -> 1000 -> 10000 -> 100000 -> 1000000 -> 80
}
```
#### Witness: proof of existence
Proof of existence for `"c"` at key `8` in a multiproof-like format:
|leaves|hashes|instructions|
|:----:|------|----|
|`[(0x80,"c")]`|`[H_0,1,H_FF]`|`HASH`, `LEAF`, `EMPTYHASH`, `BRANCH`, `EXT(5)`, `HASH`, `BRANCH`, `BRANCH`|
where $H_{0,1}$ is the Merkle root of the subtrie containing keys `0` and `1`, and $H_{FF}$ is the merkle root of the subtrie containing key `0xFF`.
The semantics of `LEAF` is that it pops a (key,value) pair and adds the value inside a leaf node on the stack. `BRANCH` takes the top two nodes on the stack, and push a new branch node on the stack whose right child is the node previously at the top of the stack and whose left child is the node immediately below. `EMPTYHASH` pushes the empty hash ∅ on top of the stack. `EXT(n)` creates an extension node that needs to be expanded into a series of branch nodes before calculating the Merkle root.
The intermediate trie that has been rebuilt from the proof is:
```graphviz
digraph D {
node [shape="rect"]
root
0 [label="H_0,1"]
1
ext [label="10:00000"]
80 [label="\"c\""]
11 [label="H_FF"]
∅5 [label="∅"]
root -> 0
root -> 1 -> 11
1 -> ext -> 80
ext -> ∅5
}
```
Because the merkelization rule doesn't recognize extension nodes, it is replaced with as many internal nodes:
```graphviz
digraph D {
node [shape="rect"]
root
0 [label="H_0,1"]
1
10
100
1000
10000
100000
1000000
80 [label="\"c\""]
11 [label="H_FF"]
∅0 [label="∅"]
∅1 [label="∅"]
∅2 [label="∅"]
∅3 [label="∅"]
∅4 [label="∅"]
∅5 [label="∅"]
root -> 0
root -> 1 -> 11
1 -> 10 -> 100 -> 1000 -> 10000 -> 100000 -> 1000000 -> 80
10 -> ∅0
100 -> ∅1
1000 -> ∅2
10000 -> ∅3
100000 -> ∅4
1000000 -> ∅5
}
```
#### Witness: proof of absence
Proof of absence for key `"A0"` is as follows
|leaves|hashes|instructions|
|:----:|------|----|
|`[]`|`[h_0,1,H_80,H_FF]`|`HASH`, `HASH`, `EMPTYHASH`, `BRANCH`, `HASH`, `BRANCH`, `BRANCH`|
where $H_{0,1}$ is the Merkle root of the subtrie containing keys `0` and `1`, $H_{80}$ is the Merkle root of the subtrie containing key `0x80` and $H_{FF}$ is the merkle root of the subtrie containing key `0xFF`.
The trie that is rebuilt from this proof is:
```graphviz
digraph D {
node [shape="rect"]
root
0 [label="H_0,1"]
1
10
11 [label="H_FF"]
root -> 0
root -> 1 -> 11
1 -> 10 -> H_80
10 -> ∅
}
```
Because the path to `0xA0` ends up encountering the empty hash ∅, the value isn't present in the trie. The same proof also proves that `0xB0` and every other key that start with `0b101` are not present in the trie.
