mappum
commented
4 years ago In the design document, chunks are built purely from iterating over nodes in key-order. However, for a verifier to check the range of keys in a given chunk is complete, we would have to include a node count in each node and it could get messy to handle the differing structures for each chunk for this check.
A simpler method that still works by iterating over nodes and involves only a small amount of traversal could be to instead generate a trunk chunk which contains the first N levels of the tree (N can be chosen based on tree size), and 2N leaf chunks (containing subtrees for each child of the last level of the trunk).
A client can first download and verify the trunk, then trivially download and verify each leaf chunk by ensuring its root hash is the child hash of its parent in the trunk, and that none of its nodes are pruned (e.g. containing just a hash or kvhash).
If the trunk chunk becomes too large, it can also be broken up into multiple chunks by applying the same principle on itself recursively.
Note that this still matintains the property that we can download and verify arbitrary chunks in any order (after first downloading the trunk), which is important for ensuring maximum bandwidth utilization (it's kind of like bittorrent pieces).
To build state replication, we'll need to build a chunk-proof builder as described in the design document, as well as a verifier (chunk proofs will already be valid in the existing proof format, but will also need to verify that the correct range of nodes are in the proof).