# Hashcash Tree, a Data Structure to Mitigate Denial-of-Service Attacks
## 6 Related Work  
Detecting DoS attacks is challenging and addressed by sophisticated techniques, among them some based on machine learning [4; 5; 6]; a survey on DoS detection techniques is given by [PERSON] et al. [7]. As an earlier barrier against DoS attacks, prevention techniques can be adopted to protect sensitive services and assets of an organization [14; 15]. This article introduces a client puzzle protocol as a prevention technique to mitigate DoS attacks. The concept of the client puzzle was introduced by [PERSON] and [PERSON] [16], who suggested their application to prevent denial-of-service (DoS) attacks. The main characteristic of client puzzles is that they can be solved by a polynomial-time entity upon spending a certain amount of resources, and therefore a server may provide access to some of its assets in exchange of a valid solution for a new client puzzle. A similar concept is given by [PERSON] and [PERSON] [9] with the notion of pricing function to combat junk emails, and by [PERSON], [PERSON], and [PERSON] [17] with the notion of timed-lock puzzle as a tool to realize timed-release crypto. Client puzzles are expected to be unforgeable and difficult to solve [18] and possibly to have determinable difficulty and parallel computation resistance [19]. Client puzzles can be categorized as CPU-bound and memory-bound. In CPU-bound client puzzles, the prover effort is measured by the amount of CPU cycles needed to solve a puzzle; several client puzzles belong to this category [16; 17; 18; 19; 20; 21; 22]. In memory-bound client puzzles, the prover effort is measured by the amount of memory-look-ups needed to solve a puzzle; the main argument in support of memory-bound client puzzles is that CPU power varies more than memory look-up speed for different computers [23; 24; 25]. The CPP presented in Section 3 is CPU-bound and combines hashcash [11] and hash trees [26]. The main obstacle to using hashcash alone is its unbounded probability cost. The length \(k\) of the prefix is the only parameter that can be used to control the difficulty of the puzzle, and both difficulty and variance increase exponentially when \(k\) increases (see Proposition 1). An attempt to gain more control on the difficulty of puzzles was performed by [PERSON] and [PERSON] [16], who essentially designed a CPP involving several sub-puzzles. Figure 16: Average prover effort (\(P\)’s CPU time, in seconds) over 1000 requests, with standard deviation (dark shade), and minimum and maximum values (light shade). Prefix length (parameter \(k\)) fixed to 4, size of hashcash tree varying from \(n=127\) to \(n=4095\) with steps of 32. The results shown by Theorem 1 for hashcash trees can be extended to such a CPP when sub-puzzles are hashcash computations. On the other hand, such a CPP requires verifying (and therefore transmitting) the solutions of all sub-puzzles, while a logarithmic number of solutions is sufficient to verify a hashcash tree (see Theorem 2). A CPP based on hash trees was designed by [PERSON] [12]. It can be seen as a solution-verification version of the CPP proposed in Section 3; when the prefix length is fixed to \(k=0\) (i.e., hashcash is disabled), the tree is computed based on the service description and several leaves are selected for the verification phase based on the root hash value. The difficulty of the puzzle is determinable with high precision, but the size of hash trees can grow quickly. This is a downside of the protocol, given the fact that the hash tree must be stored (or recomputed) by the prover in order to provide the labels for the verification phase, which are discovered only after the root hash value is computed. The proposed CPP can rely on smaller trees because the difficulty of computing a single node can also be controlled via the length of the required prefix, i.e., by enabling hashcash.