# Hashcash Tree, a Data Structure to Mitigate Denial-of-Service Attacks
## 2 Background
### A Client Puzzle Protocol Based on Hashcash  
Hashcash is a (nondeterministic) function parameterized by a hash function \(h\) and a positive integer \(k\); it associates every input string \(s\in\{0,1\}^{*}\) with any pair \(\langle h(s||x),x\rangle\) such that \(x\in\mathbb{N}\) and \(\mathit{prefix}(h(s||x),k)=0^{k}\). Let \(h_{k}(s)\) denote any valid output \(\langle h(s||x),x\rangle\) of the hashcash function parameterized by \(h\) and \(k\). Hashcash essentially asks for finding partial hash collisions on the all-zeros prefix of length \(k\), and the fastest algorithm for computing partial collisions is brute force [13]; see Algorithm 1. Assuming that the brute force algorithm increments \(x\) starting from \(x=0\), finding a valid \(\langle h(s||x^{\prime}),x^{\prime}\rangle\) output value requires the computation of \(x^{\prime}+1\) hash values. In general, hashcash has _unbounded probability cost_, in the sense that theoretically the brute force algorithm can run forever, though the probability that a solution is not found decreases rapidly towards zero. On the other hand, verifying that \(\langle h(s||x),x\rangle\) is a valid output requires the computation of one hash value, as shown in Algorithm 2. ```
1 for\(x\in\mathbb{N}\)do
2\(\mathit{hash\_value}:=h(s||x)\);
3 if\(\mathit{prefix}(\mathit{hash\_value},k)=0^{k}\)then
4 return\(\langle\mathit{hash\_value},x\rangle\);
```  
**Algorithm 1**Hashcash(\(s\), \(h\), \(k\))  
```
1 return\(\mathit{prefix}(\mathit{hash\_value},k)=0^{k}\)and\(\mathit{hash\_value}=h(s||x)\);
```  
**Algorithm 2**HashcashVerify(\(\langle\mathit{hash\_value},x\rangle\), \(s\), \(h\), \(k\))  
```
1 return\(\mathit{prefix}(\mathit{hash\_value},k)=0^{k}\)and\(\mathit{hash\_value}=h(s||x)\);
```  
solve a puzzle before processing its request. A simple CPP based on hashcash comprises the following steps:  
1. The setup consists in \(V\) generating and storing a master key \(mk\). The master key is used to sign data so that \(V\) can complete the protocol without storing any further data. (No signed data is extended in the protocol; no need for HMAC.) 2. \(P\) needs to send a request \(req\) to \(V\). To this aim, \(P\) sends \(Req:=h(req)\) to \(V\). (Here \(req\) is considered unique. For example, \(req\) can include a \(nonce\) chosen by \(P\) and a timestamp, and \(V\) can track \(Req\) for all completed \(req\) within the allotted time window. To simplify the presentation, such details are omitted from the discussion.) 3. \(V\) determines the _difficulty parameter_\(k\in N^{+}\) based on its current workload, generates a timestamp \(t\) by which the protocol must be completed, computes \(s:=h(mk||Req||k||t)\), and sends \(\langle s,k,t\rangle\) to \(P\). (Note that the hash value of the request is signed, not the request, so that the signed message has fixed length.) 4. \(P\) computes \(S:=h_{k}(s)\) and sends \(\langle req,S,s,k,t,Req\rangle\) to \(V\). 5. \(V\) checks all the following conditions: \(s=h(mk||Req||k||t)\); \(t\) is in the future; \(S\) is valid, i.e., \(S|_{1}=h(s||S|_{2})\) and \(prefix(S|_{1},k)=0^{k}\); \(Req=h(req)\). If all conditions are met, \(req\) is processed. The idea of a CPP is that a legit user is willing to waste a small amount of its computational resources in order to access a resource of \(V\), while an attacker requires an unaffordable amount of computational resources to exhaust \(V\) capabilities. The main downside of the above simple protocol is that the difficulty parameter \(k\) does not give a fine-grained control on the amount of resources needed to solve the puzzle (no _determinable difficulty_). Moreover, the brute-force algorithm for hashcash has linear speedup (weak _parallel computation resistance_). **Example 4**. : _As shown in Example 3, for the message \(foo\) there is essentially no difference in increasing the prefix from \(0^{8}\) to \(0^{12}\), while increasing the prefix to \(0^{16}\) makes the problem much more difficult.