Authentication structure vs. naive authentication paths for removal record chunks

[Sword-Smith]

The RemovalRecord contains authentication paths of all of its chunks. These are stored in VM memory due to authentication requirements.

pub struct RemovalRecord {
    pub absolute_indices: AbsoluteIndexSet,
    pub target_chunks: ChunkDictionary,
}

pub struct ChunkDictionary {
    // {chunk index => (MMR membership proof for the whole chunk to which index belongs, chunk value)}
    // This list is always sorted. It has max. NUM_TRIALS=45 elements.
    dictionary: Vec<(u64, (MmrMembershipProof<Hash>, Chunk))>,
}

Do we store the RemovalRecord authentication paths in memory as one authentication path per chunk, or do we store it as an authentication structure with the minimal number of digests that are needed to verify all leafs?¹

The code is likely to be simpler to write with the naive approach. In fact, we already have a working example on the asz/transaction-consensus branch. How much space is saved by compressing the authentication paths?

To answer this question, I wrote a test² that attempts to approximate this number. For chunk-indices uniformly picked from a range of size $2^8$ within a Merkle tree of size $2^{12}$, the compressed version uses 80 % fewer digests than the naive approach. As the tree height grows to $2^{32}$, this saving exceeds 90 %.

Output:

compressed, number of digests: mean: 93.3995±5.292249025697906
naive approach: 540
Savings: 82.70379629629629 % ±0.9800461158699826
compressed, number of digests, big tree, height 32: 113.3995
naive approach, big tree: 1440

Footnotes

1. See https://github.com/Neptune-Crypto/twenty-first/blob/master/twenty-first/src/util_types/merkle_tree.rs#L65 for how to merge multiple authentication paths. ↩

2. Test can be found here: https://gist.github.com/Sword-Smith/4ecf808756a436ccfcf027e51af2b65b ↩