Document that sorted leaves are stored backwards

[vsergeev]

I was wondering if there was a technical reason why the sorted leaves are stored backwards in the merkle tree. With the current construction, the lowest leaf index corresponds to the largest leaf value, which seems counterintuitive when attempting to reproduce the tree.

[frangio]

I don't think there is a technical reason. Other than it being counterintuitive I assume it hasn't caused any issues? Where would you expect this to be documented?

when attempting to reproduce the tree

Can you share more? Where were you trying to reproduce it? In what programming language?

[vsergeev]

I'm also using TypeScript. I had implemented a miniature version (~100 lines) of the merkle tree generation compatible with OZ MerkleProof.sol, partly to understand exactly how this library was building the tree and partly to provide a simplified version for our SDK. I ran into some issues validating against this library, until I realized the leaves were inserted in reverse. I figured I'd raise the issue in case it helps others trying to verify the results of this library in another language or using another merkle tree library.

Right now, I'm at the crossroads of deciding whether we want our SDK to build the tree in the natural order, or in the reversed order just to be compatible with this library.

[frangio]

to provide a simplified version for our SDK

This library is pretty simple and minimal, is there something in particular that you would like to see simplified?

[vsergeev]

I think the library is great, especially if you need to access additional details of the tree, and even if you don't, it's simple enough to wrap it for a more basic API. The internal hash lookup for leaves is efficient for generating many proofs. It's also the obvious choice if you've already settled on using the StandardMerkleTreeData format.

We elected not to use the StandardMerkleTreeData format to keep the metadata size down and instead reproduce the tree in runtime. We have to verify all of the leaves and root anyway, as they can be created offchain by anyone in our use case. I could see why someone would use it though, especially when working with large trees or with generic leaves.

I do regret that many projects are probably going to inherit the implicitly reversed order here for their onchain merkle trees, but there isn't any fundamental technical issue with that.

[frangio]

If you want to reproduce the tree in runtime using this library you could do that by just shipping the leaf values and leaf encoding and loading this with StandardMerkleTree.of instead of load.

merkle-tree/src/standard.ts

Lines 16 to 20 in 0951d3c

	values: {
	value: T;
	treeIndex: number;
	}[];
	leafEncoding: string[];

I don't know if I understand the real problem with the "reversed" ordering. It seems to me that this order has no implication almost ever except if you use multiproofs (and well, if you want to reproduce the tree from the leaves without using the library).

[vsergeev]

It's just a semantic discrepancy that makes it a bit more difficult to reproduce the merkle tree with another implementation. It's actually more nuanced than I've described: while the leaves are stored sorted backwards, the node hash pairs are still sorted forwards, so in a sense the sorting in the library isn't consistent with itself. The readme comment "The leaves are sorted." isn't entirely accurate -- "reverse sorted" would be more precise. It wouldn't hurt to mention that the pairs are sorted too, as that's just as important.

[frangio]

I recall now that there was a technical reason why we did this, though I don't remember the exact details. When you construct the arguments for a multiproof in a smart contract you will need to sort them and provide them sorted. I believe when you do that you will need to provide them in "forward" order if the tree contains the leaves "backwards". The current design prioritizes making that aspect the more natural one.