# Hashcash Tree, a Data Structure to Mitigate Denial-of-Service Attacks
###### Abstract  
Client puzzle protocols are widely adopted mechanisms for defending against resource exhaustion denial-of-service (DoS) attacks. Among the simplest puzzles used by such protocols, there are cryptographic challenges requiring the finding of hash values with some required properties. However, by the way hash functions are designed, predicting the difficulty of finding hash values with non-trivial properties is impossible. This is the main limitation of simple proof-of-work (PoW) algorithms, such as hashcash. We propose a new data structure combining hashcash and Merkle trees, also known as hash trees. In the proposed data structure, called hashcash tree, all hash values are required to start with a given number of zeros (as for hashcash), and hash values of internal nodes are obtained by hashing the hash values of child nodes (as for hash trees). The client is forced to compute all hash values, but only those in the path from a leaf to the root are required by the server to verify the proof of work. The proposed client puzzle is implemented and evaluated empirically to show that the difficulty of puzzles can be accurately controlled. security; partial hash collision; price functions; denial-of-service attacks; client puzzles; proof of work +
Footnote †: journal:  
the main steps of solution-verification protocols. The client generates a puzzle based on the requested service and computes a solution (steps 1-2). After that, the client sends the puzzle, its solution, and the request to the server (step 3). The server verifies that the puzzle was correctly generated and that the solution is valid (step 4). If both tests succeed, the request is processed (step 5). Hashcash [11] is a cryptographic hash-based PoW algorithm that can be used for defining both challenge-response protocols and solution-verification protocols. In a challenge-response protocol, the client sends the puzzle, its solution, and the request to the server (step 6). The server verifies that the puzzle was correctly generated and that the solution is valid (step 7). If both tests succeed, the request is processed (step 8). Figure 1: Sequence of events in a challenge–response protocol. Figure 2: Sequence of events in a solution–verification protocol. response protocol based on hashcash, the verifier challenges the prover to find an extension of a given string whose hash value starts with a given number of zeros. As a PoW, the prover sends the extended string and its hash value, that is, the output of the hashcash algorithm. In a solution-verification protocol, the hashcash algorithm is applied to the service description, with a prefix length fixed in the protocol. Dissymmetry is given by the fact that the prover must try several extensions of the given string to find one with the required prefix, while the verifier needs only one hash value computation to verify the provided solution. The main downside of hashcash is that the difficulty of the puzzle only depends on the length of the required all-zeros prefix. Adding a single zero to the prefix doubles the number of attempts that the prover must afford, and also the variance increases exponentially. A much better control on the difficulty of the puzzle was obtained by [PERSON] (2018), who proposed a _solution-verification protocol based on hash trees_. In such trees, every leaf is labeled by the hash value of the leaf index concatenated with the service description. Every internal node is labeled by the hash value of the string obtained by concatenating child labels. Finally, some leaves are selected based on the hash value of the root. The prover constructs the tree and sends to the verifier the nodes in the paths from the selected nodes and their children (actually, the set of nodes is shrunk by removing nodes whose children belongs to the set; see Figure 3). This way, the verifier has sufficient data to verify that the puzzle was generated and solved correctly.