## 3 Information Leakage Analysis of Merkle Tree-Based Authentication Schemes
### Analysis of Merkle Tree-Based Authentication
#### 3.1.2 Leakage of Merkle Tree Hash Values  
Typically, data authentication is expected to operate reliably, regardless of the number of times it occurs. Contrary to this expectation, however, the maximum number of effective authentication is bounded by the size of the Merkle tree due to the leakage of hash values of it. Specifically, authentication can be conducted only as many times as the logarithmic number of leaf nodes in the tree, because responded hash values of the tree are leaked to the adversaries. After the limited number of authentications, the attacker can construct the entire Merkle tree through eavesdropping even though it has no information about the underlying content.  
Observing Figure 1, the two sibling paths which are proof for the challenged leaf nodes (1 or 2) and (3 or 4) provide all of the information required to construct the entire Merkle tree (i.e., \(\{H_{1}\), \(H_{2}\), \(H_{3-4}\), \((H_{1-2}\), \(MT_{M}^{root})\}\cup\{H_{3}\), \(H_{4}\), \(H_{1-2}\), \((H_{3-4}\), \(MT_{M}^{root})\}=MT_{M}=\{H_{1}\), \(H_{2}\), \(H_{3}\), \(H_{4}\), \(H_{1-2}\), \(H_{3-4}\), \(MT_{M}^{root}\}\), where the values inside the parentheses can be derived from the other values given as part of the proof).  
Therefore, it can be seen that the authentication range of the data is reduced at an exponential rate in the presence of an adversary exploiting information accumulated about the tree gained during repeated authentication attempts. Once the prover \(\mathcal{P}\) passes the authentication proof for a challenged block (e.g., \(B_{1}\)), an eavesdropper can obtain infomation about the subtree rooted at the child of the root node (e.g., \((H_{1},H_{2},H_{1-2})\) as a subtree rooted at \(H_{1-2}\) in Figure 1). The subsequent authentication attempt guarantees the integrity of at most half of the entire data (e.g., \(\{B_{3},B_{4}\}\) in Figure 1). Otherwise, the attacker can reuse the other half of the tree already known from the previous authentication attempt. Therefore, the authentication coverage reduces further or the adversary becomes able to bypass the verification process with overwhelming probability even when it does not know the corresponding data by exploiting the obtained hash values.  
The typical coverage pattern is illustrated in Figure 2. When data is composed of \(2^{i}\) blocks, the maximum authentication coverage \(C(\cdot)\) of the data (\(M\)) at the \(j\)-th execution attempt can be defined as  
\[C(M)^{j}=\begin{cases}1,&\text{if }j=0\\ \frac{1}{2}\lfloor\log_{2}j\rfloor+1,&\text{if }0<j<2^{i}\\ 0,&\text{otherwise.}\end{cases} \tag{2}\]  
As the number of demanding sibling paths for challenged leaf nodes in a single verification increases, the number of allowable verification attempts decreases sharply. (According to [PERSON] et al. [PERSON] et al. (2015), data composed of 10,000 blocks requires 460 samples of leaf nodes to be verified in order to achieve 99% confidence. When it comes to Merkle tree-based authentication ([PERSON] et al., 2016), effectiveness is only guaranteed for 21 times. After this, the entire Merkle tree can be reconstructed via eavesdropping so that the attacker can successfully pass authentication.)  
Figure 2: Authentication coverage for data by the number of blocks.