KV-Witness
an alternative approach to block witnesses
There is currently a proposed format for block witnesses in Stateless Ethereum, that has a spec in a GitHub repo. It is based on opcodes. You can imagine a tiny programming language with just a few commands that generate a Merkle Mupltiproof.
This post researches an alternative approach to block witness construction. It is based on a list of keys and values and has a simpler semantics.
In this post I will try to answer the following questions:
- What is the KV witness format and how it is different from currently proposed (opcode-based) Witness format?
- What are the pros and cons of the KV comparing to OP?
- How efficient is this format is in terms of network bandwidth?
Requirements
Any block witness must satisfy the following requirements:
- Correctness. We should be able to run any block from Ethereum mainnet using this format.
- Efficiency. We should use the minimum network footprint to transfer this witness.
- Merkelization. The witness format must support Code Merkelization.
- Arity-agnostic. The witness format must support both hexary and binary Merkle Tries.
Semantics
Witness format I describe in this part of the post is semantics. I’m not talking about the exact byte layout here.
Later on, I will touch more on the exact binary format of the witness that was used for testing.
witness ::= header, body, proofs
header ::= version : byte, trie_arity : byte
body ::= array of [ { type: byte key : []byte, value : []byte } ]
proofs ::= map { <type>: [ { prefix : []byte, hash : []byte } ] }
Witness body
Witness body
conists of 2 elements:
- Data.
The key can be: an account address, a storage key or a code key and the value is an account, a storage item or a code chunk respectively. This part of the witness body is completely agnostic to the arity of a Merkle Trie that is used to validate its correctness. Moreover, if we use something else for correctness check this part won’t change. - Proof(s).
The key is the Merkle path and the value is a hash. The proof is dependent on the trie arity and will be different for hex and bin tries. This semantics allows including multiple proofs with different types in the same witness. So, we can theoretically make a witness that supports both hex and bin tries.
body
is sorted lexicographically by key, making sure that:
- shorter keys are earlier in the list (so we are rebuilding a trie from top to bottom);
- when keys are equal (that could happen for account and code) account always goes first.
Parsing Algorithm
- Validate witness version and the proof arity (make sure that the witness proof arity matches the trie arity that that block requires).
- Validate the witness hash (if canonical witness is there).
- Create an empty trie of the right arity.
- Go though the data, just insert data into this trie in the order it comes (witness should be lexicographically sorted).
- Insert proofs into the trie.
- Validate root hash (should match the root hash of the previous block).
Pros & Cons
Here is the list of pros and cons comparing KV-Witness vs the current opcode-based witness format.
Pros
- It matches the flat DB structure, can be inserted immediately if the canonical witness hash is valid (no need to verify Merkle Root).
- It can be used for snapshot sync.
- The witness data is independent from the validity proof method we choose: Merkle Tries or Polynomial Commitments or something else.
Cons
- Potentially higher network footprint on binary tries due to byte alignment (e.g. the proof key
0b01
, that is 2 bits will take a byte of storage space). - Potentially slower witness parsing.
Network Efficiency Research
KV Witness Example Implementation
We need to be able to prove the correctness of the format. It should be able to run on all blocks of Ethereum Mainnet.
To do that, I have implemented this witness format in a branch of turbo-geth repository: kv-witness-research
.
This implementation was tested in Google Cloud on Ethereum mainnet blocks from 5.000.000–8.000.000.
How to repeat the experiment?
You need at least 200GB of free space and least 32gbs of RAM (the code is a PoC and isn’t optimized much).
1) clone kv-witness-research
branch of turbo-geth (commit aa6b4dc609b3d871c778597a71ac08601f17de53
2) (took 1 day in my case) sync block headers and bodies for mainnet: go run ./cmd/geth --syncmode staged --datadir ~/stateless-chaindata/
3) (took 17 days in my case) run stateless prototype on this data
go run ./cmd/state stateless --blockSource ~/stateless-chaindata/geth/chaindata --statefile ~/kv_witness_statefile --witnessInterval 5000000 --statsfile ~/stats_kv_witness.csv 2>&1 | tee debug.log
That way, in stats_kv_witness.csv
you should obtain the same stats as I have in this document.
Witness binary format
The witness starts with a single-byte header that contains version: header
.
Then, there is a witness body
that consists of the size (1-4 bytes dependent on the number of witness elements) and the elements
themselves.
Each element
starts with a single-byte type
, followed by key
field that is a byte array of arbitrary size prefixed by the size byte (just like body
itself) followed by the actual data.
Data depends on what type of element is there:
- for storage leafs it is a byte array of arbitrary size refixed by the size bytes;
- for code leafs it is a byte array of arbitrary size prefixed by the size bytes too;
- for proofs it is a fixed-size 32 byte hash value w/o any size prefix;
For accounts it is more complicated, but basically it is
- flags byte (mask that tells if account elements don’t have their default values)
- nonce, 8 bytes (if nonce != 0)
- balance (if balance != 0), byte array of arbitrary size, prefixed by its size;
- storage root hash (if not empty root hash), 32 bytes, byte array of fixed size;
- code hash (if code not empty), 32 bytes, byte array of fixed size.
In the end we get something like this: this: [<header> <witness_elements_count> <element1_type> <element1_key_size> <element1_key_byte1> ... <element1_value_size> ... <element2_type> ...]
Optimization: Key prefix deduplication
Key is a Merkle Path that consists of nibbles, not bytes. A single nibble size is 4 bits for a hex trie and 1 bit for a binary trie. That way, we can see that sometimes a key can be a non-integer amount bytes: (for example 12 bits is 8,5 bytes).
The key is encoded as []byte
, where it is aligned by byte (so a key with a len between 4 and 5 bytes will always be 5 bytes). Also, an additional "mask" byte is added to the beginning that shows which bits are "active" in the last byte.
- a key
0xFF
(1 byte): [00001000 11111111] <== 8 significant bits - a key
0b11
(2 bits): [00000010 11000000] <== 2 significant bits - a key
0b10
(2 bits): [00000010 10000000] <== 2 significant bits - a key
0b_10101010_01010101_1101
(2 bytes 4 bits): [11110000 10101010 01010101 11010000]
Then, we can add a simple optimization that allows us to mitigate repeating prefixes in both data and proofs.
To increase compression efficiency, we will intermix both data and proof in the same ordered map.
The highest 4 bits of a header byte mean a byte offset of a previous key.
Since in our semantics the keys are sorted, we can use the first 4 bytes describe the followng cases:
- the key is the same as the previous one, the whole key can then be reduced to 1 byte:
[10000000]
- the key doesn’t share any bytes with the previous one (
[0000xxxx xxxxxxxx ...]
) - the key shares up to 14 prefix bytes with the previous one (
[????xxxx xxxxxxxx ...]
): ??? is big-endian encoded number 1 (001) to 14 (1110). - the key shares 15 or more bytes with the previous one (
[1111xxxx ???????? xxxxxxxx ...]
): where ???????? is an addition to 15. - for 15 bytes it will be
[1111xxxx 00000000 ... ]
(15 + 0) - for 16 bytes it will be
[1111xxxx 00000001 ... ]
(15 + 1) - for 32 byte it will be
[1111xxxx 00010001 ... ]
(15 + 17)
Network Efficienty Research Results
Raw data for the results is available in this GitHub repo: https://github.com/mandrigin/ethereum-mainnet-kv-witness-data
To give a comprehensive image in terms of network efficiency, we compare 3 types of witnesses, all of them are running on hexary tries:
1) Opcode witness, the existing one. (Data is from my previous experiments).
2) KV Witness(uncompressed): no key prefix deduplication.
3) KV Witness(compressed): key prefix deduplication is included.
Tests were conducted on blocks 5.000.000–8.000.000.
Absolute size comparison
Quantile analysis
Conclusion
Key prefix deduplication does provide significant improvements to the KV witness. With it enabled, we have almost the same numbers between these two formats.
The KV Witness has a couple of advantages.
The main one is its simplicity. It is much easier to make a spec for a data format, essentially a dictionary, then a more complicated almost-programming-language approach.
The second advantage is that proof is semantically separate from the data, so when we want to change trie arity (from hexary to binary) or when we want to change the proof mechanics completely, it is will require less changes with the KV-Witness approach.
I think it is definitely a worthy contender for the witness spec standard.