# Hashcash Tree, a Data Structure to Mitigate Denial-of-Service Attacks
###### Abstract
While such a protocol succeeds in controlling the growth of the prover's effort, in practice it needs very large hash trees that must be either stored for the full computation or recomputed after the root hash is determined. In a nutshell, this article addresses the following research questions:  
**RQ1**: Is it possible to define a client puzzle protocol based on hashcash but with more controllable difficulty of puzzles? **RQ2**: Is it possible to define a client puzzle protocol based on hash trees but requiring smaller trees than those used by [PERSON] (2018)? **RQ3**: How resistant to parallel computation is the proposed client puzzle protocol? To answer the above questions, the challenge-response protocol is modified by splitting the challenge in two phases, as shown in Figure 4. In the first phase, the prover is challenged to solve a puzzle generated by the verifier (steps 2-3). After solving the puzzle (step 4), the prover sends to the verifier a _commitment_ to conclude the first phase (step 5). In the second phase, the prover is asked to provide a proof of the solution, that is, sufficient data to verify that the prover has computed the committed solution (steps 6-9). In the proposed protocol, the puzzle consists of building a tree satisfying the following conditions: every leaf is labeled by the output of the hashcash algorithm applied on a verifier-provided  
Figure 3: In a hash tree, to verify the hash value of the red node, the hash values of the blue nodes are used to reconstruct the hash value of the root. Pink nodes are those in the path from the selected node to root. Blue nodes are their children not included in the path. string concatenated to the leaf index; every internal node is labeled by the output of the hashcash algorithm applied on the verifier-provided string concatenated to the node index and the hash values of child nodes. This way, the difficulty of the construction of the tree can be controlled by varying the length of the all-zeros prefix and the number of nodes in the tree. Similarly to hash trees, the verification of a solution involves the selected node, those in the path from the selected node to the root, and their children. Given the combination of features from hashcash and hash trees, the proposed data structure is named _hashcash tree_. Hashcash trees and the two-phases challenge-response protocol relying on them are presented in Section 3, after introducing the required background in Section 2. Properties of the proposed client puzzle protocol are discussed in Section 4. In particular, the computational complexity is analyzed in terms of computed hash values for both the construction of hashcash trees and their verification. As for generating hashcash trees, the average number of computed hash values grows exponentially on the length of the all-zeros prefix and linearly on the number of nodes. Variance has a similar trend. It turns out that the grow can be controlled by fixing a relatively small length for the prefix and varying only the number of nodes depending on the workload of the verifier. As for the verification phase, the effort only depends (logarithmically) on the number of nodes. The construction of hashcash trees can be only partially parallelized, as the computation of a node label depends on the label of child nodes. An empirical evaluation of a proof-of-concept implementation of the protocol is reported in Section 5. The results confirm that the client puzzle protocol based on hashcash trees can be used in practice to challenge the prover in generating trees whose construction effort in terms of the number of computed hash values is controllable. Finally, related work is discussed in Section 6, and the article conclusion is summarized in Section 7. Figure 4: Sequence of events in a two-phases challenge–response protocol. In summary, the article answers **RQ1** and **RQ2** by introducing a new data structure combining hashcash and hash trees, namely hashcash trees.