Amxx
commented
9 months ago If a tree has 2**n leaves, with n the depth of the tree, then all leaves are at the same level. In that case, reverting the order of leaves (or not) does not change the resulting root. That is because the hash used is symmetric.
That is a property of the tree we are building in the Solidity structure we plan to introduce.
The fact that the leaves are reversed only affect trees where all leaves are not at the same level. In that case, the reversal part affects which leaves are at which level. In that case reverting the leaves (or not) changes the overall tree.
Note that before merging we plan to update the README to document that feature, and its consequences.
By default, leaves are sorted. This is done so to simplify the multiproof process.
When building a multiproof, all the leaves being proven must be in the same order as they appear in the tree. This means that when verifying a multiproof, the contract will have to order the leaves in an order that matches their position in the tree. Best practice is to order the leaves of the tree such that the smart contract can replicate that order without knowledge of the tree, and thus verify the multiproofs.
However, there are also usecases where the tree is constructed iterativelly, from unsorted leaves. See:
StandardMerkleTree.of.In order to support that usecase, I'm proposing we add a option object to
StandardMerkleTree.of. Leaves will be sorted by default to replicate existing behavior. Disabling the sorting addresses the need of the usecases describe above. Note that since these usecase use full/complete tree, the reversal part (done by the core) is irrelevant.In ay b more difficult for contracts to verify multiproofs for trees constructed without leave sorting. This may not be a major drawback though. In any case, it is still possible to verify such multiproof, as long as the caller of the contract can force the ordering of the leaves that must be proven.