## 2 MHT for Data Authentication
### MHT Overview  
To efficiently transmit large-size data, a data publisher usually divides the data into small fragments (i.e., segments) and then sends each segment. If a user receives these segments of the data from multiple unspecific nodes, the user must verify the segments from the following two checkpoints:  
1. Is the received segment valid in itself? That is, the user must verify both the integrity of the segment and the authentication of the publisher of the segment. It confirms the identity of the publisher who generated the segment and whether the publisher is valid. Additionally, it guarantees whether the segment has been unchanged during transmission. However, even if the validity of a segment is acceptable based on the first checkpoint, it is not sufficient because the verified segment may not be a piece of the data that the user requires. Hence, the second checkpoint is also necessary. 2. Is the received segment a piece of the requested data? An MHT-based authentication scheme (MHT-Auth) efficiently provides proper answers for the two checkpoints. The MHT is a binary tree with \(K=2^{k}\) leaf nodes. Let \(N_{i}\) be a node with sequential index \(i\). \(N_{1}\) is the root node of the MHT. Each internal node \(N_{i}\) has two child nodes, \(N_{2i}\) and \(N_{2i+1}\). Let \(V_{i}\) be the node value of \(N_{i}\). Each \(V_{i}\) is computed as follows:  
1. If \(N_{i}\) (\(2^{k}\leq i\leq 2^{k+1}-1\)) is a leaf node of the MHT, \(V_{i}\) is the hash value of a segment assigned to the leaf node \(N_{i}\). 2. If \(N_{i}\) (\(1\leq i\leq 2^{k}-1\)) is the internal node (or the root node) of the MHT, \(V_{i}=h(V_{2i}||V_{2i+1})\), where \(h(x)\) is a one-way cryptographic hash function. Figure 1 shows that NDN constructs the MHT to verify data consisting of 16 (\(K=2^{k}=2^{4}\)) segments: \(\{s[i]\mid 0\leq i\leq 15\}\). A data publisher builds a binary tree with 16 leaf nodes and assigns the 16 segments to the leaf nodes of the binary tree according to the order of the segments. Since a segment \(s[i]\) is assigned to the leaf node \(N_{K+i}\) of the MHT, \(V_{K+i}\) is \(h(s[i])\). Then, starting from high-level nodes (i.e., from nodes in Level 3), it calculates all  
node values in order. Afterward, the publisher generates the digital signature for the \(V_{1}\) of the MHT, not for each segment \(s[i]\). Then, it packages both a segment \(s[i]\) and the digital signature. This package, denoted as \(p[i]\), assumes an NDN's data packet type. If a user receives the \(p[i]\) of the data, to verify the \(s[i]\) packaged in \(p[i]\), it must compute \(V_{1}\) of the MHT corresponding to the data. Therefore, it computes all node values of nodes on a full path, from \(N_{K+i}\) to \(N_{1}\). The path is called as the _verification path_ of \(s[i]\). Given a node value \(V_{r}\), if the user can obtain the sibling node value of \(N_{r}\), the user can easily compute the parent node value of \(N_{r}\). Hence, if the user obtains the sibling node values of the nodes on the path, it can compute all node values from \(V_{K+i}\) to \(V_{1}\). For example, in Figure 1, when verifying \(s[2]\), it can compute \(V_{18}\) using \(s[2]\). Hence, if it obtains the \(V_{19}\) of \(N_{18}\)'s sibling node, it can compute \(V_{9}\) of \(N_{9}\) on the path. The set of such sibling node values for all nodes on the path is called as a _witness_ of a segment. For each segment \(s[i]\), the data publisher generates a _witness_\(w[i]\) and then packages the \(w[i]\) into the \(p[i]\). Thus, \(p[i]\) consists of \(s[i]\), \(w[i]\), and the digital signature. If a user receives the \(p[i]\), using both the \(s[i]\) and the \(w[i]\), it can easily compute \(V_{1}\). As shown in Figure 1, if a user receives \(p[2]\) for transmitting a segment \(s[2]\), \(w[2]\) consists of \(\{V_{19}\), \(V_{8}\), \(V_{5}\), \(V_{3}\}\).