# Hashcash Tree, a Data Structure to Mitigate Denial-of-Service Attacks
## 3 Hashcash Trees and Their Application to Client Puzzle Protocols  
The definition of hashcash tree is parameterized with respect to a hash function \(h\) and a positive integer \(k\), which are assumed fixed in this section. Recall that \(h_{k}(s)\) denotes any pair \(\left\langle h(s|x),x\right\rangle\) such that \(x\in\mathbb{N}\) and \(\mathit{prefix}(h(s||x),k)=0^{k}\). For a string \(s\) and an integer \(n\in\mathbb{N}^{+}\), let \((\ell_{i})_{i\in\mathbb{N}^{+}}\) be the (nondeterministic) sequence of labels defined as follows:  
\[\ell_{i}:=\left\{ \begin{array}{ll}h_{k}(s||i||(\ell_{2i}|_{1})||(\ell_{2i+1 }|_{1}))&\text{if }i\in[1..n];\\ \langle\epsilon,0\rangle&\text{otherwise}.\end{array} \right. \tag{2}\]  
The _hashcash tree_ of size \(n\) for the string \(s\) is the perfect tree \(T\) of height \(\lceil\mathit{log}_{2}(n)\rceil\) such that, for each \(v\in\mathit{nodes}(T)\), if \(\mathit{order}(v,T)=i\), then \(\mathit{label}(v,T)=\ell_{i}\). As shown by Algorithm 3 and Figure 9, a hashcash tree of size \(n\) is constructed by first computing the labels of the nodes of level \(\lceil\mathit{log}_{2}(n)\rceil\) (i.e., leaves) and then iteratively computing the labels of nodes of previous levels until the label of the root is obtained. In total, the algorithm performs \(n\) hashcash computations. ```
1 height\(:=\lceil\mathit{log}_{2}(n)\rceil\);
2 tree\(:=\mathbf{array}[2^{\mathit{height}}]\); // new array of \(2^{\mathit{height}}\) elements
3 for\(i:=2^{\mathit{height}}\) down to \(1\)do
4 if\(i>n\)then
5\(\mathit{tree}[i]:=\langle\epsilon,0\rangle\);
6 else
7\(\mathit{tree}[i]:=\textsc{Hashcash}(s||i||\mathit{tree}[2i][1]||\mathit{tree}[2 i+1][1],h,k)\);
8
9 returntree;
```  
**Algorithm 3**HashcashTree(\(s,\,n,\,h,\,k\))  
**Example 7**. : _Let \(T\) be the hashcash tree shown in Figure 10. Let \(v_{o}\) denote the node of \(T\) such that \(\mathit{order}(v_{o},T)=o\). Once the label of the root is disclosed, changing any label in the tree is computationally unfeasible. In particular, changing the label of a leaf, say \(v_{4}\), requires violating second-preimage resistance of \(h\) at each level of \(T\), with the additional difficulty that the new hash values must also be a valid output of the hashcash algorithm._  
Figure 9: Activity diagram of Algorithm 3 building a hashcash tree of size \(n\) for the string \(s\) using hash function \(h\) and prefix length \(k\). Similarly to a hash tree, the validation of a leaf \(i\) of a hashcash tree \(T\) involves nodes in the path from \(i\) to the root of \(T\) and their children; see Algorithm 4 and Figure 11. Specifically, the prefix of all hash values associated with these nodes is validated (lines 8-9), while hash values are recomputed only for nodes in the path from \(i\) to the root of \(T\) (lines 2-6). On the basis of Algorithms 3-4, the proposed CPP comprises the following steps:  
1. The setup consists in the verifier \(V\) generating and storing a master key \(mk\). 2. The prover \(P\) needs to send a request \(req\) to \(V\). To this aim, \(P\) sends \(Req:=h(req)\) to \(V\). 3. \(V\) determines the difficulty parameter \(n\in\mathbb{N}^{+}\) based on its current workload, generates a timestamp \(t\) by which the protocol must be completed, computes \(s:=h(mk||Req||n||t)\), and sends \(\langle s,n,t\rangle\) to \(P\). 4. \(P\) computes and stores the hashcash tree \(T\) of size \(n\) for \(s\) using Algorithm 3 and sends \(\langle sol,s,n,t,Req\rangle\) to \(V\), where \(sol\) is \(label(root(T))|_{1}\). 5. \(V\) checks \(s=h(mk||Req||n||t)\), verifies that \(t\) is in the future, randomly selects a number \(i\in[2^{H-1}.2^{H-1}]\) (a leaf), and sends \(\langle I,i\rangle\) to \(P\), where \(I:=h(mk||Req||sol||i)\). 6. \(P\) sends \(\langle req,S,I,i,s,n,t,Req\rangle\) to \(V\), where \(S\) consists of labels associated with nodes in the path from \(i\) to the root and their children, in formulas, \(S\) is the sequence comprising \(\ell_{|i\cdot 2^{-j}|}\) and \(\ell_{|i\cdot 2^{-j}|}\), for \(j\in[0..\lceil\log_{2}(n)\rceil-1]\).