WIP: compound tree enhancements

[cryptonemo]

In addition to existing compound tree enhancements, this adds functionality for having aggregations of compound trees, or compound compound trees in concept (poorly named as type CCompoundMerkleTree). This is work in progress as it would be ideal to not have a CCompoundMerkleTree and instead define a recursive CompoundMerkleTree type. I spent time investigating that route yesterday and today and haven't progressed, so I'm issuing this PR for reviews/ideas/suggestions on how to better solve that problem. I believe it solves the specific issue that we're looking at regarding tree compositions, but could also be improved since the naming is at best clunky. I'll continue to think about how to address this weekend as well, as this isn't intended to be merge ready as-is.

[porcuquine]

Hmmmm. I really don't think we should need three tree types. I haven't fully thought this through, but here's a sketch of how I think it could work without too much complexity.

• A compound tree is parameterized over two 'normal' merkle tree types. (This might require doubling the type parameters. Or perhaps some of them can be implicitly shared between the trees. Minimally, there should be type parameters for the arity of the subtrees and of the compound (top) tree.
• To construct:
  • create all the subtrees, then use their roots as the leaves of the compound tree.
• Create proofs:
  • create two proofs
    • one from leaf to subtree root
    • one from subtree root (compound leaf) to compound root.
  • combine the two proofs with a compound proof type which contains the two paths, each with the appropriate number of nodes per path.

[porcuquine]

Addendum, since my previous reply was simplistic. I will leave it there, though.

The detail which I skipped over is the need for the upper, compound tree to have potentially mixed arities. Presumably this was the point you're trying to work through, so I apologize for addressing the wrong concerns.

Taking that into account, and a few broad possibilities suggest themselves:

1. Move to a single tree type, which fully specifies the arity at each height. (This could work, but seems to make simple cases complicated.)
2. Similar to what I advocated above, but allow for any number of subtree 'signatures' (not just two).

• In this case, a signature is an (arity, height) pair.
• This keeps simple trees simple and allows for arbitrary complexity by composing simple trees.

The second option seems better, but in both cases, there is the problem of how to deal with an arbitrary number of arities with a static type signature.

One way to get around this might be to formalize our assumptions about how compound trees should work. If we do that, then the 'shape' of the compound tree is fully determined by two parameters:

• the number of subtrees
• the max arity

However, doing this accurately might require a lot of complexity doing compile-time math with typenums, and it might not be tractable (or even possible, not sure).

In practice, we will only need compound trees with one or two layers. Assuming 4GiB subtrees, that would let us handle sizes of 4GiB to 128GiB, assuming a max arity of 8. Now a compound tree just needs to know:

• subtree arity
• subtree height
• base compound arity (could be zero)
• top compound arity (could be zero)

I think this last suggestion is probably viable within the tradeoffs involved. I would focus on trying to see whether you can make that work. If it looks problematic or you want to discuss more, feel free to ping me.

[cryptonemo]

Thanks for the input. Much of it more or less sums up how the original compound merkle tree worked, and by extension how this works. The thing that isn't clear to me is how to define a recursive type in rust, specifically. I know rust generally doesn't allow that, but it would be convenient (though not functionally superior) if there was a way to collapse the types so that 'tree/sub-tree' and 'proof/sub-proof' are somehow the same type. The approaches I've already tried used parameterization, but ultimately did not eliminate the need for some recursive type.

As for the flexibility of sector size composition, I believe all of the mentioned scenarios are covered by the existing PR (i.e. this is a work in progress, but it does work).

[porcuquine]

I think you can use a box to include self references (type) and still have a size known at compile time.

[cryptonemo]

I think you can use a box to include self references and still have a size known at compile time.

👍 I did see that as a recommendation online, but wasn't sure it was the approach to take. I'll take a look at that.

[dignifiedquire]

yes, using Box seems like a resaonable approach here.

[cryptonemo]

Closed in favor of #79