# Hashcash Tree, a Data Structure to Mitigate Denial-of-Service Attacks
## 5 Implementation and Experiment  
A proof-of-concept implementation of the algorithm presented in Section 3 is available at [[https://github.com/alviano/hashcash-tree](https://github.com/alviano/hashcash-tree)]([https://github.com/alviano/hashcash-tree](https://github.com/alviano/hashcash-tree)) (accessed on 28 September 2023). It is written in Python 3.11 and uses the SHA-256 function from the hashlib package (even if other hash functions can be easily added). Numeric computation is powered by NumPy, and witnesses are represented as unsigned 16-bits integers. The CPP is implemented in a REST server powered by the FastAPI framework. Master keys are _universally unique identifier_ (UUID) v4, i.e., 36-character alphanumeric strings. Timestamps are represented as double precision floating-point numbers. An example client for consuming the REST API is also provided. It performs 1000 (one thousand) requests, possibly using multiple threads or processes. Requests themselves are not of particular importance for the example client, which is designed so that all the computation is focused on solving the CPP provided by the REST server. Note that fixing \(n=1\) in the implemented CPP essentially results into the CPP defined in Section 2.2; the prover is challenged to solve a single hashcash computation, for some prefix length \(k\). On the other hand, fixing \(k=0\) in the implemented CPP essentially results in a CPP using hash trees because hashcash is disabled. In order to empirically verify the theoretical analysis carried out in Section 4, the REST server and the example client were run with several configurations. The difficulty of the generated puzzles was varied by modifying both the prefix length (parameter \(k\)) and the size of the hashcash tree (parameter \(n\)); within this respect, \(k\) was tested with all values from 0 to 8, and \(n\) was tested with value \(2^{i}-1\) for \(i\in[4..15]\). As for the client, since the experiment was run on a quad-core Intel(R) Xeon(R) CPU X3430 @ 2.40 GHz with 16 GB of RAM, the number of workers was fixed to 4 (i.e., the 1000 requests were processed in parallel by 4 processes). Measured values include the total CPU usage of the REST server, and the CPU usage of the example client for each request (from starting the interaction with the REST server to the submission of the validation data). Computed values include the average CPU usage for completing the 1000 requests, the standard deviation, and the minimum and maximum CPU usage. A summary of the measured and computed values is shown in Figure 14. The plot uses logarithmic axes and reports the average CPU usage of the prover; times within the standard deviation are colored in dark shades, and other times between the minimum and the maximum CPU usage are colored in light shades. As a first observation, each increment of the prefix length (\(k\)) causes a jump in the effort required by the prover to solve the puzzle. Recall that for \(n=1\), the CPP is essentially the one based on hashcash alone. On the other hand, for every fixed value of \(k\), the prover effort scales linearly on the size of the hashcash tree (\(n\)). Observing the standard deviation, it is possible to conclude that all hashcash trees are computed with similar effort once \(k\) and \(n\) are fixed. As a final observation on the plot, note that for \(k=0\) (i.e., essentially using hash trees) the puzzle is solved in less than 2 s even for the largest case of \(n=2^{15}=32\),767. If storing a node takes 34 bytes (32 bytes for the SHA-256 hash value and 2 bytes for the witness), a hashcash tree of size \(n=2^{15}=32\),767 requires around 1024 KiB of memory. In contrast, note that for \(k=4\) and \(n=4095\) the puzzle is solved in around 2.26 s and the hashcash tree can be stored in around 136 KiB. Similarly, for \(k=5\) and \(n=2047\) the puzzle is solved in around 2.20 s and the hashcash tree can be stored in around 68 KiB. Figure 15 shows the measured prover effort for each solved CPP. There is a plot for each tested value of \(n\).