3
Let us prove by induction on depth that for every node $v$, there exist $a_v,b_v$ (possibly $\pm \infty$) such that the input $x$ reaches $v$ iff $a_v < x < b_v$. This is true for the root since we can take $a_r = -\infty$ and $b_r = +\infty$. Now suppose that it is true for some node $v$, and let $v_<,v_>$ be its two children. Suppose that node $...
2
Further expanding on @Paul Etscheit, sorting the hash pairs simplifies the verification of merkle proofs.
Example:
The open zeppelin merkle proof verification smart contract, requires the hash pairs to be sorted. This is made even clearer when you look at their tests.
Merkle inclusion proofs can be verified through a function function verify(bytes[] proof, ...
Only top voted, non community-wiki answers of a minimum length are eligible
