# Hashcash Tree, a Data Structure to Mitigate Denial-of-Service Attacks
## 2 Background
### Trees  
A _labeled binary tree_\(T\) is either the empty set \(\emptyset\) or a quadruple \(\langle r,\ell,L,R\rangle\), where \(r\) is the _root_ node (of \(T\)), \(\ell\) is the _label_ (of \(r\)), and \(L,R\) are labeled binary trees referred to as the _left child_ and the _right child_ (of both \(T\) and \(r\)); \(r,L\) and \(R\) are respectively denoted by \(root(T)\), \(left(T)\) and \(right(T)\). (In the following, the term \(tree\) is used to refer labeled binary trees.) Nodes of a tree are defined inductively: \(nodes(\emptyset):=\emptyset\); \(nodes(\langle r,\ell,L,R\rangle):=\{r\}\cup nodes(L)\cup nodes(R)\). When \(L=R=\emptyset\), node \(r\) is also called a _leaf_. Leaves of a tree are defined inductively: \(leaves(\emptyset):=\emptyset\); \(leaves(\langle r,\ell,\emptyset,\emptyset\rangle):=\{r\}\); \(leaves(\langle r,\ell,L,R\rangle):=leaves(L)\cup leaves(R)\), if \(L\
eq\emptyset\) or \(R\
eq\emptyset\). An _internal node_ of \(T\) is any non-leaf node of \(T\), that is, \(interval(T):=nodes(T)\setminus leaves(T)\). Let \(v\in nodes(T)\) be a node of \(T=\langle r,\ell,L,R\rangle\). The label of \(v\) in \(T\) is defined inductively: \(label(v,\emptyset):=e\); \(label(v,T):=\ell\) if \(v=r\); \(label(v,T):=label(v,L)\) if \(v\in nodes(L)\); \(label(v,T):=label(v,R)\) if \(v\in nodes(R)\). The _level_ of \(v\) in \(T\) is defined inductively: \(level(v,T):=1\) if \(v=r\); \(level(v,T):=1+level(v,L)\) if \(v\in nodes(L)\); \(level(v,T):=1+level(v,R)\) if \(v\in nodes(R)\). A tree is _perfect_ if all interior nodes have nonempty children and all leaves have the same level. (In the following, only perfect trees are considered.) The _height_ of a tree is the level of its leaves. The _order_ of \(v\) in \(T\) is defined via _break-first search_ (BFS) or _level-order search_: \(order(r,T):=1\); for every \(\langle v,\ell^{\prime},L^{\prime},R^{\prime}\rangle\) occurring in \(T\), \(order(root(L^{\prime}),T):=2\cdot order(v,T)\) and \(order(root(R^{\prime}),T):=2\cdot order(v,T)+1\). Note that \(T\) can be compactly represented by a one-based array \(arr\) of size \(|nodes(T)|\), having \(arr[i]=label(v,T)\) whenever \(order(v,T)=i\). **Example 5**. : _Let \(T\) be the tree of height 4 shown in Figure 7. \(T\) is such that \(label(v,T)=order(v,T)\) for all \(v\in nodes(T)\). Its array representation is \([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]\). The leaves have level 4 and are the nodes with label from 8 to 15. Inner nodes have label from 1 to 7. The root has label 1._  
A _hash tree_, or _Merkle tree_, is a tree in which every leaf is labeled with the hash value of a data block, and every internal node is labeled with the hash value of the labels of its child nodes. Here a data block is any piece of information in a commitment scheme, that is, hidden data that cannot be changed. In fact, sharing the hash value associated with the root is sufficient to guarantee that no label of the hash tree is modified. If \(T\) is the hash tree associated with a sequence \(s_{1},\ldots,s_{2^{n}}\) of data blocks (\(n\in\mathbb{N}\)), in order to verify that some \(s_{i}\) (\(i\in[1..2^{n}]\)) was not modified, it is sufficient to check nodes in the path from the leaf with label \(h(s_{i})\) to the root. The check involves the labels of these nodes and their children; in formulas, if \(v_{o}\) denotes the node of \(T\) such that \(oder(v_{o},T)=o\), the labels involved in the verification of \(s_{i}\) are \(label(v_{\lfloor i\cdot 2^{-j}\rfloor},T)\) and \(label(v_{\lfloor i\cdot 2^{-j}\rfloor+1},T)\), for \(j\in[0..n-1]\). **Example 6**. : _Let \(T\) be the hash tree shown in Figure 8. Let \(v_{o}\) denote the node of \(T\) such that \(oder(v_{o},T)=o\). To verify that \(s_{5}\) was not modified, the nodes involved are \(v_{1},v_{2},v_{3},v_{6},v_{7},v_{12},v_{13}\). In particular, the hash values that are recomputed are those associated with nodes from the leaf with label \(h(s_{5})\) to the root, i.e., those of \(v_{12}\), \(v_{6}\), \(v_{3}\) and \(v_{1}\).