title: Merkle tree for finding data inconsistencies - optimizing number of queries
body: <p>I understand the idea behind using Merkle tree to identify inconsistencies in data, as suggested by articles like</p>
  <ul>
  <li><a href="http://distributeddatastore.blogspot.com/2013/07/cassandra-using-merkle-trees-to-detect.html#:%7E:text=Comparing%20Merkle%20trees,range%20are%20consistent%20between%20replicas." rel="nofollow noreferrer">Key Concepts: Using Merkle trees to detect inconsistencies in data</a></li>
  <li><a href="https://brilliant.org/wiki/merkle-tree/" rel="nofollow noreferrer">Merkle Tree | Brilliant Math &amp; Science Wiki</a></li>
  </ul>
  <p>Essentially, we use a recursive algorithm to traverse down from root we want to verify, and follow the nodes where stored hash values are different from server (with trusted hash values), all the way to the inconsistent leaf/datablock.</p>
  <p>If there's only one such block (leaf) that's corrupted, this means we following a single path down to leaf, which is log(n) queries.</p>
  <p>However, in the case of multiple inconsistent data blocks/leaves, we need up to O(n) queries. In the extreme case, all data blocks are corrupted, and our algorithm will need to send every single node to server (authenticator). In the real world this becomes costly due to the network.</p>
  <p><strong>So my question is, is there any known improvement to the basic traverse-from-root algorithm?</strong> A possible improvement I could think of is to query the level of nodes in the middle. For example, in the tree below, we send the server the two nodes in the second level ('64' and '192'), and for any node that returns inconsistency, we recursively go to the middle level of that sub-tree - something like a binary search based on height.</p>
  <p><a href="https://i.stack.imgur.com/p3aqY.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/p3aqY.png" alt="enter image description here" /></a></p>
  <p>This increases our best case time from O(1) to O(sqrt(n)), and probably reduces our worst case time to some extent (I have not calculated how much).</p>
  <p>I wonder if there's any better approach than this? I've tried to search for relevant articles on Google Scholar, but looks like most of the algorithm-focused papers are concerned with the merkle-tree traversal problem, which is different from the problem above.</p>
  <p>Thanks in advance!</p>