An optimized compacted sparse merkle tree without pre-calculated hashes

Data Structure
4
  1. The scheme I linked to also doesn’t need to do non-trivial hash pre-computation (see this comment specifically).
  2. The scheme I linked to only needs O(\lg n) disk reads (but still requires 256 hashes). In this comment further down however, an optimization is presented that reduces the number of hashes to O(\lg n) (hint: it’s an isomorphism of the optimization you propose here, which you’d know if you had bothered to read the prior art).
1 Like