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() < depth:
            t.append(i)
        elif (i >> (i.bit_length() - depth)) % 2 == 1:
            r.append(i)
        else:
            l.append(i)
    return t, l, r

def alphasort(ints, depth=2):
    if len(ints) <= 1:
        return ints
    t, l, r = split_by_root(ints, depth)
    return t + alphasort(l, depth+1) + alphasort(r, depth+1)

Example:

>>> 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:

   1
 2   3 
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].