## 2 Merkle Tree-Based Authentication  
A Merkle tree [20] is constructed from a series of data blocks, where the value of an internal node is assigned based on the hash value of its children, while the value of a leaf node is assigned the direct hash value of the corresponding data block (Figure 1). In the tree construction procedure, the hash function satisfies the preimage-resistance property, which implies it is computationally infeasible to find the preimage of the given hash value. Also, since this forms a binary tree, the maximum depth from leaf to root is at most \(\lceil\log_{2}n\rceil\) for \(n\) data blocks. Thus, the Merkle tree acts as an authenticated data structure for efficient verification of the online content.  
In Merkle tree-based online authentication, there are two entities, prover \(\mathcal{P}\) and verifier \(\mathcal{V}\):  
* **Prover**\(\mathcal{P}\) is an entity who attempts to convince the other party (i.e., the verifier \(\mathcal{V}\)) that it owns all of the data. To converge network bandwidth, the prover sends a small piece of verifiable information instead of all of the content.
* **Verifier**\(\mathcal{V}\) is another entity who tries to determine whether prover \(\mathcal{P}\)'s claim is correct or not. To reduce storage requirements, the verifier usually stores only the value of the root node of the Merkle tree instead of all nodes of the tree.  
It is notable that the Merkle tree-based online authentication is a protocol that verifies that the prover and verifier own the same data. Unlike public verification, therefore, it assumes that the verifier has some secret (i.e., not publicly available) information about the data to be validated. This issue is dealt with in detail in Section 5.  
Based on the hardness assumption that it is infeasible to find a preimage of a given hash value within a computationally reasonable time [21], it can be guaranteed that only entities possessing the same data can obtain the same Merkle tree. In brief, the security of authentication based on Merkle tree is based on the security of hash function in use. Therefore, the verifier \(\mathcal{V}\) only stores the value of the root node of the tree and removes the rest of the metadata once the tree is constructed. On the other hand, the prover \(\mathcal{P}\) is required to generate a series of (different) hash values leading to a value of the root node that is identical to the one held by the verifier with each authentication cycle.  
In the example shown in Figure 1, the verifier \(\mathcal{V}\) chooses a random block index (e.g., 1) as a challenge. The prover \(\mathcal{P}\) then constructs a Merkle tree from its local data, followed by sending the corresponding unique sibling paths from the leaves to the root node (i.e., \((H_{1},H_{2},H_{3-4})\)) to the verifier. Upon receiving the proof response, the verifier \(\mathcal{V}\) derives the root value of the Merkle tree (i.e., \(H(H(H_{1},H_{2}),H_{3-4})\)) and determines whether the result is identical to the value of the root node held in local storage.  
In the above protocol, adversaries may not be able to uncover the underlying plain data from the communication as long as a secure (preimage resistant) hash function is used. However, we observed that it is vulnerable to a side-channel attack, which allows deducing meaningful information from communications during the authentication process and narrowing down the scope of the attack vector,  
Figure 1: Merkle Tree of data \(M\) composed of four blocks.  
thereby weakening the reliability of the authentication and possibly nulllyfying its effectiveness of authentication completely. Thus, we first analyze the weakness of Merkle tree-based authentication method to side-channel attacks on the same data in Section 3. After this, we present a simple method for improving security and reliability, of Merkle tree-based authentication with minimal overhead in Section 4.