Check out the Issue Explorer
Looking to fund some work? You can submit a new Funded Issue here.
#### Problem statement
In an SSZ partial, we have:
* A list of generalized indices representing the `leaves` you want to make a partial of (often, this is just a single one)
* A list of generalized indices (`sisters`), that can be generated as a function `get_sister_indices(leaves: Sequence[int]) -> Sequence[int]`
* A set of `hashes` for each index in `leaves` and `sisters`
How do we serialize the whole structure? Specifically, how do we serialize which indices the partial is referring to and in what order?
### Proposed solution
First, we do **not** include `leaves` and `sisters` in the partial. We definitely don't need to include `sisters` because it can simply be calculated from `leaves`. But more importantly, we do not even need to include `leaves`, because much of the time some or all of the information from `leaves` will be known. For example, if we want to make a partial representing a Merkle path to a particular block in history from a history accumulator, it would be more reasonable to represent the block height (as that might already be included alongside the proof anyway), and then calculate the generalized index for the leaf from there. If we want to make a partial representing an entire object in a tree, we can easily calculate the set of generalized indices representing all leaves in that object. Also, this fits with the existing convention for Merkle proofs where the index is separate from the proof.
Second, we store `hashes` in the following order: first, the `leaves` in _bit-alphabetical left-to-right order_, then the `sisters` in _descending numerical order_.
Here's the definition of bit-alphabetical left-to-right order:
def split_by_root(ints, depth):
t, l, r = , , 
for i in ints:
if i.bit_length() > (i.bit_length() - depth)) % 2 == 1:
return t, l, r
def alphasort(ints, depth=2):
if len(ints) >> alphasort([1,2,3,4,5,6,7])
[1, 2, 4, 5, 3, 6, 7]
The idea is that it is a recursive "top, then left subtree, then right subtree" order (though `leaves` should never contain both "top" and "left" (or "top" and "right")). To see more clearly, here's the tree structure:
4 5 6 7
The goal of bitwise sorting is so that if a partial includes an entire SSZ object that has multiple levels, the different levels will be provided in order. The goal of the "leaves then sisters in descending order" structure is so that a single-item SSZ partial is always identical to a Merkle proof: first the object, then the leaves in the Merkle tree from bottom-to-top order.
For example, if we want a partial of just element 5 in the above tree, the order would be [5, 4, 3], just as in a regular Merkle proof. If we want a partial of elements 5 and 6, it would be [5, 6, 7, 4]. For elements 4 and 5, it would be [4, 5, 3].