# Hashcash Tree, a Data Structure to Mitigate Denial-of-Service Attacks
## 4 Properties  
### Computational Complexity  
The complexity of the algorithms introduced in the previous section is analyzed by measuring the number of computed hash values. Let \(s\) be a message and \(h\) be a crypto  
Figure 11: Activity diagram of Algorithm 4 verifying node \(i\) of a hashcash tree \(T\) of size \(n\) for the string \(s\) using hash function \(h\) and prefix length \(k\). Recall that \(v_{o}\) denotes the node of \(T\) such that \(\mathit{oder}(v_{o},T)=o\), for \(o\in[1..n]\).  
graphic hash function producing hash values of length \(m\in\mathbb{N}\). By definition of cryptographic hash function, the probability that \(h(s)=s^{\prime}\) is \(2^{-m}\), for all \(s^{\prime}\in\{0,1\}^{m}\). Hence, the probability that \(h(s)\) starts with the prefix \(0^{k}\) is \(2^{-k}\), for all \(k\in[0..m]\). Since all hash value computations are independent, the number of hash values computed by Algorithm 1 follows the geometric distribution. As for the verification procedure (Algorithm 2), a single hash value is computed.  
Proposition 1: _The probability that \(\textsc{Hashcash}(s,h,k)\) terminates after computing \(N+1\) hash values is \((1-2^{-k})^{N}\cdot 2^{-k}\), for all \(N\in\mathbb{N}\). On average, the number of unused hash values computed by Algorithm 1 is \((1-2^{-k})\cdot 2^{k}\), with variance \((1-2^{-k})\cdot 2^{2k}\)._  
Proof: Since all hash values are equiprobable by definition of \(h\), the probability that 0 occurs as a specific output bit is 0.5. As all bits are independent, the probability that a hash value starts by \(0^{k}\) is \(p=2^{-k}\). The algorithm terminates at the first success of independent trials, so the probability that it terminates after computing \(N+1\) hash value is modeled by the geometric distribution: the probability mass function (of observed failures) is \((1-p)^{N}\cdot p\), the mean value (of observed failures) is \((1-p)/p\), and the variance is \((1-p)/p^{2}\). The proof is complete after substituting \(p=2^{-k}\).  
Proposition 2: \(\textsc{HashcashVerify}(\langle hash\_value,x\rangle,s,h,k)\) _terminates after computing one hash value._  
Proof: Immediate by observing line 1 of Algorithm 2.  
Regarding hashcash trees, the first \(n\) nodes of a hashcash tree of size \(n\) are labeled by hashcash output values. The prefix \(0^{k}\) is common to all such hashcash output values, hence keeping the success probability constant for all hashcash computations. It turns out that the number of hash values computed by Algorithm 3 follows the negative binomial distribution.  
Theorem 1: _The probability that \(\textsc{HashcashTree}(s,n,h,k)\) terminates after computing \(N+n\) hash values is_  
\[\binom{N+n-1}{N}(1-2^{-k})^{N}\cdot 2^{-k\cdot n} \tag{3}\]  
_for all \(N\in\mathbb{N}\). On average, the number of unused hash values computed by Algorithm 3 (via Algorithm 1) is \(n\cdot(1-2^{-k})\cdot 2^{k}\), with variance \(n\cdot(1-2^{-k})\cdot 2^{2k}\)._  
Proof: Each call to Algorithm 1 follows the Bernoulli distribution with success probability \(p=2^{-k}\). Therefore, the total number of unused hash values (failures) follows the negative binomial distribution: the probability mass function (of observed failures) is  
\[\binom{N+n-1}{N}(1-p)^{N}\cdot p^{n}, \tag{4}\]  
the mean value (of observed failures) is \(n\cdot(1-p)/p\), and the variance is \(n\cdot(1-p)/p^{2}\). The proof is complete after substituting \(p=2^{-k}\).  
Regarding the verification procedure (Algorithm 4), the labels that are verified are those in the path from the selected leaf to the root.  
Theorem 2: \(\textsc{HashcashTreeVerify}(T,i,s,n,h,k)\) _terminates after computing at most \(\lceil\log_{2}(n)\rceil\) hash values._Proof.: Hash values are computed indirectly by calling Algorithm 2, one hash value for each call. Algorithm 2 is called at line 5, at all iterations of the main loop in the worst case. The main loop is repeated \(\lceil log_{2}(n)\rceil\) in the worst case because \(i\) is divided by 2 at line 7.