In IDEN3 we are using exactly those trees and the optimisation you mention plus an extra one that we see very convenient especially when checking merkle proofs onchain. That is: we force the root of any empty tree or any empty subtree to be zero. That is z1 = z2 = z3 = … zN = 0.
The format for merkle proofs that we are using is:
1.- One first word that is a bitmap of the siblings that are not zero.
2.- The non zero sibblings sorted bottom-up.
This has the advantage:
1.- Not having to initialize the lists with zN. The root of an empty list is zero, the default EVM value.
2.- Not having to worry of zX values. This saves SLOAD and SSTOREs a lot, and the onChain merkle proof is much cheaper.
3.- The implementation code is much more clean. You don’t have to handle z values.
5 Likes