## 3 MHT Process Improvement
### Improved MHT Verification
#### 3.2.2 Verifying Node Values in Improved MHT
If these two values are the  
Figure 4: The segment verification process of the proposed scheme. same, it regards \(s[2]\) as being valid. Now, it saves the computed \(V_{9}\) to \(m[3]\) for verifying the next segments. Step 4: To verify the remaining segments, it repeats a process such as step 2 or 3. Algorithm 1 describes the pseudocode for selecting a shorter verification path of a given segment, as well as verifying the segment. Let data consist of \(K=2^{k}\) segments. Hence, the MHT consists of \(K=2^{k}\) leaf nodes. As shown in Algorithm 1, a user requesting the data needs \(k\) internal storages \(\{m[i]\mid i=0,\ldots,k-1\}\) to save the computed valid node values. \(\{w[i]\mid i=1,\ldots,k-1\}\) is the witness of a segment, and \(N[i]\) is the node value of a node having a level \(i\). ```
1:data = [index, segment, witness = \(\{w[k],\ w[k-1],\ldots,\ w[1]\}\), signature]
2:storage = \(\{m[k-1],m[k-2],\ \ldots,\ m[0]\}\)
3:result = {valid; invalid}, storage = \(\{m[k-1],m[k-2],\ \ldots,\ m[0]\}\)
4:Set mask= 1
5:for level = \(k-1\) down to 0 do
6:if (index AND mask) is not zero then
7: Stop this routine
8:else
9: Set mask:= mask*2
10:endif
11:endfor
12:Compute the hash value \(N[k]\) of the segment
13:for \(r=0\) up to level\(-1\)do
14: Read \(w[k-r]\)
15: Compute \(N[k-r-1]\) using \(w[k-r]\) and \(m[k-r]\)
16:endfor
17:if index is 0 then
18: Verify the signature using \(N[0]\)
19:if the signature is invalid then
20: Return invalid
21:endif
22:else
23:if \(m[level]\) is not equal \(N[level]\)then
24: Return invalid
25:endif
26:for\(r=1\) up to level\(-1\)do
27: Save \(N[r]\) in \(m[r]\)
28:endfor
29:Return valid
```  
**Algorithm 1**Pseudo code for verifying a segment (Proposal 1). The procedure of the proposed scheme is as follows:  
(1) A user initializes every \(m[i]\) with the NULL value. (2) If the user receives \(p[0]\) for the first segment \(s[0]\) of the data, it computes all node values \(\{N[k],\ N[k-1],\ldots,\ N[0]\}\) of nodes on a full verification path from the leaf node of \(s[0]\) to \(N_{1}\). These values are \(\{V_{K},\ V_{K/2},\ V_{K/4},\ \ldots,\ V_{1}\ \}\). Using the computed \(N[0](=V_{1})\), the user verifies the digital signature packaged in \(p[0]\). If the signature is valid, it saves the computed node value \(N[i]\) in \(m[i]\) for \(i=0,\ldots,k-1\). That is, if a node \(N_{r}\) is on the path, the user saves the computed \(V_{r}\) to \(m[i]\), where \(i=\lfloor log_{2}r\rfloor\). (3) After that, the user receives \(p[j]\) for the other segment \(s[j]\) for \(j>0\). The user selects a full verification path of \(s[j]\). It searches the node values of nodes on the verification path from the leaf node such that the node value \(N[r]\) of the node on the path for \(s[j]\) is equal to the value of \(m[r]\). Let \(i\) be the first index found such that \(N[i]=m[i]\). The index \(i\) is called the verification level of \(s[j]\). A node having level \(i\) on the verification path of the \(s[j]\) is called the _verification node_ of the \(s[j]\). A verification path from a leaf node of \(s[j]\) to the verification node is called the _shortest verification path_ of \(s[j]\). Given a segment \(s[j]\), the user can easily find both the level and the shortest verification path of \(s[j]\) as follows: The user finds the largest \(i\) such that \(\left(j\ AND\ 2^{k-1-i}\right)\
eq 0\), where \(AND\) is a bitwise AND operation. Then, the largest \(i\) is the level, and the shortest verification path of \(s[j]\) is from the leaf node of \(s[j]\) to the node having a lever \(i\). (4) Let the verification level of \(s[j]\) be \(i\). The user computes the node values \(\{N[k],\ N[k-1],\ldots,\ N[i]\}\) of nodes on the shortest verification path of the \(s[j]\). (5) The user compares \(N[i]\) with \(m[i]\). If these two values are equal, the user regards segment \(s[j]\) as valid. (6) The user saves \(\{N[k-1],\ldots,\ N[i-1]\}\) in \(\{m[k-1],\ldots,\ m[i-1]\}\) according to their indices. (7) The user repeats steps (3) through (6) until it finishes verifying the final segment of the data.