## 3 MHT Process Improvement
### Improved MHT Verification
#### 3.2.2 Verifying Node Values in Improved MHT  
We propose the concept of _the shortest verification path_ of a leaf node. To implement the shortest verification path of a leaf node, if a user verifies a segment, it saves valid node values of nodes on the full verification path of the corresponding leaf node and then reuses the saved valid node value to verify the next order segment. Denote \(P_{(n,1)}=\{a_{n},a_{n-1},\cdots,a_{1}\}\) as the path having length \(n\) of a binary tree, where \(a_{n}\) is a leaf node of the binary tree, \(a_{1}\) is the root node is the binary tree, and \(a_{i}\) is a child node of \(a_{i-1}\) for \(i=n,n-1,\cdots,2\). Let \(SP_{(n,r)}=\{a_{n},a_{n-1},\cdots,a_{r}\mid 1\leq\ r\}\) be the sub-path of \(P_{(n,1)}\). Definition 1: Let the number of leaf nodes of MHT be \(K=2^{k}\). Assume that a user saves valid nodes for verifying the \((i-1)\)th segment assigned to the \(i\)th leaf node of the MHT. The shortest verification path of the \(i\)th segment is the sub-path \(SP_{(k,r)}=\{a_{k},a_{k-1},\cdots,a_{r}\mid 1\leq\ r\leq k-1\}\) of the full verification path \(P_{(k,1)}=\{a_{k},a_{k-1},\cdots,a_{1}\}\) of the \(i\)th segment satisfying the following two conditions:  
(Condition 1) The \(a_{r}\) of \(SP_{(k,r)}\) is the same as one of the saved valid nodes. (Condition 2) \(r\) is the largest index that satisfies Condition 1. Figure 4 demonstrates the concept of valid node values and the shortest verification path of a segment. In Figure 4, \(m[i]\) is the internal storage used to record the valid node value of a node having level \(i\). If a user receives a segment and the segment is valid, it stores the node value \(V_{r}\) calculated during the verification process for the segment to \(m[i]\), where \(i=\lfloor log_{2}r\rfloor\) is the level of node \(N_{r}\). The operation process is as follows:  
Step 1: A user receiving \(p[0]\) verifies the \(s[0]\) as the original MHT scheme does. If it needs to authenticate the \(s[0]\) creator, it verifies the _DataSigature_ of \(p[0]\). Otherwise, it verifies the _RootValue_ of \(p[0]\). According to the characteristics of a secure hash function, given the _RootValue_, it is difficult to find a proper value such that the hash value of the found value is the _RootValue_. Even if an attacker changes both \(s[0]\) and the _RootValue_ to illegally pass this verification process, the attacker cannot create \(s[1]\) to satisfies the same _RootValue_, so the attacker's attempt is eventually detected. Hence, verifying the _RootValue_ is sufficient to check the integrity of \(s[0]\). If \(s[0]\) is valid, it saves the valid node values of the full verification path from the leaf node \(N_{16}\) of \(s[0]\) to the root node \(N_{1}\) according to their node levels. Step 2: To verify the next segment \(s[1]\), in principle, the user must compute all node values of nodes on the full verification path of \(s[1]\) from leaf node \(N_{17}\) to \(N_{1}\). To address such an inefficiency, we utilize _the shortest verification path_ of \(s[1]\), from the leaf node \(N_{17}\) to the internal node \(N_{8}\). Therefore, the user computes only two node values, \(V_{17}\) and \(V_{8}\), using witness data \(V_{16}\). Then, the user compares the computed \(V_{8}\) with the value of \(m[3]\). The user has saved the valid node value \(V_{8}\) in \(m[3]\) when verifying \(s[0]\). According to MHT characteristics, if the computed \(V_{8}\) is the correct node value, then the node values of the ancestor nodes, i.e., \(V_{4}\), \(V_{2}\) and \(V_{1}\), are always the correct node values. Therefore, if these two values are the same, it regards \(s[1]\) as being valid. Hence, the user no longer needs to confirm the node values of the ancestor nodes. Step 3: To verify the next segment \(s[2]\), it is necessary to compute the node values of a shorter verification path from the leaf node \(N_{18}\) of \(s[2]\) to \(N_{4}\), not to \(N_{1}\). After computing \(V_{4}\), the user compares the computed \(V_{4}\) with the value of \(m[2]\).