\documentclass{article}[10 pt]
\usepackage{latexsym}
\usepackage{fullpage}
\usepackage{color}
%\usepackage[bottom]{draftcopy}
\usepackage[english]{babel}
\usepackage{times}

\begin{document}

\title{Hashcash - A Denial of Service Counter-Measure}

\author{
Adam Back\\
e-mail: adam@cypherspace.org
}

\dateenglish

\maketitle

\newcommand{\n}[1]{\mbox{#1}}
\renewcommand{\b}[1]{\n{\textbf{#1}}}
\newcommand{\s}[1]{\n{\textsf{#1}}}
\renewcommand{\c}[1]{\mathcal{#1}}

\newcommand{\lb}[1]{\stackrel{\mathrm{left}}{=}_{#1}}
\newcommand{\rb}[1]{\stackrel{\mathrm{right}}{=}_{#1}}
\newcommand{\nlb}[1]{\not\!\lb{#1}}
\newcommand{\nrb}[1]{\not\!\!\!\rb{#1}}

\begin{abstract}

\emph{Hashcash} was originally proposed as a mechanism to throttle
systematic abuse of un-metered internet resources such as email, and
anonymous remailers in May 1997.  Five years on, this paper captures
in one place the various applications, improvements suggested and
related subsequent publications, and describes initial experience from
experiments using hashcash.

The \emph{hashcash} CPU cost function computes a token which can be
used as a proof-of-work.  Interactive and non-interactive variants of
cost functions can be constructed which can be used in situations
where the server can issue a challenge (connection oriented
interactive protocol), and where it can not (where the communication
is store--and--forward, or packet oriented) respectively.

\end{abstract}

\bigskip

\noindent{\bf Key Words:} hashcash, cost functions

\section{Introduction}

Hashcash \cite{Back:1997:hashcash} was originally proposed as a
mechanism to throttle systematic abuse of un-metered internet
resources such as email, and anonymous remailers in May 1997.  Five
years on, this paper captures in one place the various applications,
improvements suggested and related subsequent publications, and
describes initial experience from experiments using hashcash.

The \emph{hashcash} CPU cost function computes a token which can be
used as a proof-of-work.  Interactive and non-interactive variants of
cost functions can be constructed which can be used in situations
where the server can issue a challenge (connection oriented
interactive protocol), and where it can not (where the communication
is store--and--forward, or packet oriented) respectively.

At the time of publication of \cite{Back:1997:hashcash} the author was
not aware of the prior work by Dwork and Naor in
\cite{Dwork:1992:junkmail} who proposed a CPU pricing function for the
application of combatting junk email.  Subsequently applications for
cost functions have been further discussed by Juels and Brainard in
\cite{Juels:1998:clientpuzzles}.

\section{Cost Functions}

A \emph{cost function} should be efficiently verifiable, but
parameterisably expensive to compute.  We use the following notation
to define a cost function.

In the context of cost functions we use \emph{client} to refer to the
user who must compute a \emph{token} (usually denoted $\c{T}$) using a
cost function \textsf{MINT()} which is used to create tokens to
participate in a protocol with a \emph{server}.  We use the term
\emph{mint} for the cost function because of the analogy between
creating cost tokens and minting physical money.

The server will check the value of the token using an evaluation
function \textsf{VALUE()}, and only proceed with the protocol if the
token has the required value.

The functions are parameterised by the amount of work $w$ that the
user will have to expend on average to mint a token.

With \emph{interactive cost functions}, the server issues a challenge
$\c{C}$ to the client -- the server uses the $\s{CHAL}()$ function to
compute the challenge.  (The challenge function is also parameterised
by the work factor.)

\[
\left\{
\begin{array}{ll}

\c{C} = \s{CHAL}(w) & \n{server challenge function} \\
\c{T} = \s{MINT}(\c{C}) & \n{mint token based on challenge} \\
\c{V} = \s{VALUE}(\c{T}) & \n{token evaluation function} \\

\end{array}
\right.
\]

With \emph{non-interactive cost functions} the client choses it's own
challenge or random start value in the \textsf{MINT()} function, and
there is no \textsf{CHAL()} function.

\[
\left\{
\begin{array}{ll}

\c{T} = \s{MINT}(w) & \n{mint token} \\
\c{V} = \s{VALUE}(\c{T}) & \n{token evaluation function} \\

\end{array}
\right.
\]

Clearly a \emph{non-interactive cost function} can be used in an
interactive setting, whereas the converse is not possible.

\subsection{Publicly Auditable, Probablistic Cost}

\begin{itemize}

\item

A \emph{\textbf{publicly auditable}} cost function can be
\emph{efficiently} verified by any third party without access to any
trapdoor or secret information.  (When we say \emph{publicly
auditable} we mean implicitly that the cost function is
\emph{efficiently} publicly auditable compared to the cost of minting
the token, rather than auditable in the weaker sense that the auditor
could repeat the work done by the client.

\item 

A \emph{\textbf{fixed cost}} cost function takes a fixed amount of
resources to compute.  The fastest algorithm to mint a fixed cost
token is a deterministic algorithm.

\item

A \emph{\textbf{probablistic cost}} cost function is one where the
cost to the client of minting a token has a predictable expected time,
but a random actual time as the client can most efficiently compute
the cost function by starting at a random start value.  Sometimes the
client will get lucky and start close to the solution.

There are two types of probablistic cost \emph{bounded probablistic
cost} and \emph{unbounded probablistic cost}.

\begin{itemize}

\item

An \emph{\textbf{unbounded probablistic cost}} cost function, can in
theory take forever to compute, though the probablity of taking
significantly longer than expected decreases rapidly towards zero.
(An example would be the cost function of being required to throw a
head with a fair coin; in theory the user could be unlucky and end up
throwing many tails, but in practice the probability of not throwing a
head for $k$ throws tends towards $0$ rapidly as $\lim_{k \rightarrow
\infty} (\frac{1}{2})^k = 0$.)

\item

With a \emph{\textbf{bounded probablistic cost}} cost function there
is a limit to how unlucky the client can be in it's search for the
solution; for example where the client is expected to search some key
space for a known solution; the size of the key space imposes an upper
bound on the cost of finding the solution.

\end{itemize}

\end{itemize}

\subsection{Trapdoor-free}

A disadvantage of known solution cost functions is that the challenger
can cheaply create tokens of arbitrary value.  This precludes public
audit where the server may have a conflict of interests, for example
in web hit metering, where the server may have an interest to inflate
the number of hits on it's page where it is being paid per hit by an
advertiser.

\begin{itemize}

\item

A \emph{\textbf{trapdoor-free}} cost function is one where the server
has no advantage in minting tokens.

\end{itemize}

An example of a trapdoor-free cost function is the Hashcash
\cite{Back:1997:hashcash} cost function.  Brainard and Juel's
client-puzzle cost function is an example of a \emph{known-solution}
cost function where the server has an advantage in minting tokens.
Client-puzzles are also not publicly auditable.

\section{The Hashcash cost-function}

Hashcash is a non-interactive, publicly auditable, trapdoor-free cost
function with unbounded probablistic cost.

First we introduce some notation: consider bitstring $s =
\{0,1\}^{\star}$, we define $[s]_i$ to means the bit at offset i,
where $[s]_1$ is the left-most bit, and $[s]_{|s|}$ is the right-most
bit.  $[s]_{i \ldots j}$ means the bit-wise substring between and
including bits $i$ and $j$, $[s]_{i \ldots j} = [s]_i \; \| \; ... \;
\| \; [s]_j$.  So $s = [s]_{1 \ldots |s|}$.

We define a binary infix comparison operator $\lb{b}$ where b is the
length of the common left-substring from the two bit-strings.

\[
\begin{array}{ll}

% x \lb{0} y & [x]_1 \ne [y]_1 \\
x \lb{0} y & true \\
x \lb{b} y & \forall_{i=1 \ldots b} \; [x]_i = [y]_i \\
x \lb{b+1} y & \Rightarrow x \lb{b} y \\
\end{array}
\]

Hashcash is computed relative to a service-name $s$, to prevent tokens
minted for one server being used on another (servers only accept
tokens minted using their own service-name).  The service-name can be
any bit-string which uniquely identifies the service (eg. host name,
email address, etc).

The hashcash function is defined as:

\[
\left\{ 
\begin{array}{ll}

\s{PUBLIC:} & 
\n{hash function} \; \c{H}(\cdot) \; \n{with output size} \; k \; \n{bits} \\

\\

\c{T} = \s{MINT}(s,w) & 
\b{find} \; x \in_{R} \{0,1\}^{\star} \; \b{st} \; 
\c{H}(s) \lb{w} \c{H}(s\|x) \\
& \b{return} \; ( x, s ) \\

\c{V} = \s{VALUE}(\c{T}) & \c{H}(s) \lb{v} \c{H}(s\|x) \\
& \b{return} \; v \\

\end{array}
\right.
\]

The hashcash cost function is based on finding \emph{partial hash
collisions}.  The fastest algorithm for computing partial collisions
is brute force.  There is no challenge as the client can safely choose
his own random challenge, and so the hashcash cost function is a
\emph{trapdoor-free} and \emph{non-interactive} cost function.

In addition the Hashcash cost function is \emph{publicly auditable},
because anyone can efficiently verify any published tokens.

(In practice $|x|$ should be chosen to be large enough to make the
probability that clients reuse a previously used start value
negligible; $|x| = 128$ bits should be enough even for a busy server.)

The server needs to keep a double spending database of spent tokens,
to detect and reject attempts to spend the same token again.  To
prevent the database growing indefinitely, the service string can
include the time at which it was minted.  This allows the server to
discard entries from the spent database after they have expired.  Some
reasonable expiry period should be chosen to take account of clock
inaccuracy, computation time, and transmission delays.

Hashcash was originally proposed as a counter-measure against email
spam, and against systematic abuse of anonymous remailers.  It is
necessary to use \emph{non-interactive cost functions} for these
scenarios as there is no channel for the server to send a challenge
over.  However one advantage of \emph{interactive cost functions} is
that it is possible to prevent pre-computation attacks.  For example,
there is a cost associated with sending each email, which tends to
throttle the types of email abuse perpetrated by spammers; however for
a pure DoS attack a determined adversary may spend a year
pre-computing tokens to all be valid on the same day, and on that day
be able to temporarily overload the system.

It would be possible to reduce the scope for such pre-computation
attacks by using a slowly changing \emph{beacon} (unpredictable
broadcast authenticated value changing over time) such as say this
weeks winning lottery numbers.  In this event the public value is
included in the start string, limiting pre-computation attacks to
being conducted within the time period between beacon value changes.

\section{Interactive Hashcash}

\label{interactive-hashcash}

With the interactive form of hashcash, for use in interactive settings
such as TCP, TLS, SSH, IPSEC etc connection establishment a challenge
is chosen by the server.  The aim of interactive hashcash is to defend
server resources from premature depletion, and provide graceful
degradation of service with fair allocation across users in the face
of a DoS attack where one user attempts to deny service to the other
users by consuming as many server resources as he can.  In the case of
security protocols such as TLS, SSH and IPSEC with computationally
expensive connection establishment phases involving public key crypto
the server resource being defended is the servers available CPU time.

The interactive hashcash cost function is defined as follows:

\[
\left\{ 
\begin{array}{ll}

\c{C} = \s{CHAL}(w) & 
\b{choose} \; c \in_{R} \{0,1\}^{k} \\
& \b{return} \; ( s, c, w ) \\
T = \s{MINT}(C) & 
\b{find} \; x \in_{R} \{0,1\}^{\star} \; \b{st} \; 
\c{H}(s\|c\|x) \lb{w} \c{H}(s\|c) \\
& \b{return} \; ( x, s ) \\

\c{V} = \s{VALUE}(T) & \c{H}(s\|c\|x) \lb{v} \c{H}(s\|c) \\
& \b{return} \; v \\

\end{array}
\right.
\]

\subsection{Dynamic throttling}

With interactive hashcash it becomes possible to dynamically adjust
the work factor required for the client based on server CPU load.  The
approach also admits the possibility that interactive hashcash
challenge-response would only be used during periods of high load.
This makes it possible to phase-in DoS resistent protocols without
breaking backwards compatibility with old client software.  Under
periods of high load non-hashcash aware clients would be unable to
connect, or would be placed in a limited connection pool subject to
older less effective DoS counter-measures such as random connection
dropping.

\subsection{hashcash-cookies}

\label{hashcash-cookies}

With connection-slot depletion attacks such as the syn-flood attack,
and straight-forward TCP connection-slot depletion the server resource
that is being consumed is space available to the TCP stack to store
per-connection state.

In this scenario it may be desirable to avoid keeping per connection
state, until the client has computed a token with the interactive
hashcash cost-function.  This defense is similar to the syn-cookie
defense to the syn-flood attack, but here we propose to additionally
impose a CPU cost on the connecting machine to reserve a TCP
connection-slot.

To avoid storing the challenge in the connection state (which itself
consumes space) the server may choose to compute a keyed MAC of the
information it would otherwise store and sent it to the client as part
of the challenge so it can verify the authenticity of the challenge
and token when the client returns them.  (This general technique -- of
sending a record you would otherwise store together with a MAC to the
entity the information is about -- is referred to as a \emph{symmetric
key certificate}.)  This approach is analogous to the technique used
in syn-cookies, and Juels and Brainard proposed a related approach but
at the application protocol also in their client-puzzles paper.

For example with MAC function $\c{M}$ keyed by server key $K$ the
challenge MAC could be computed as:

\[
\left\{ 
\begin{array}{ll}

\s{PUBLIC:} & 
\n{MAC function} \; \c{M}(\cdot,\cdot) \\

\\

\c{C} = \s{CHAL}(w) & \b{choose} \; c \in_{R} \{0,1\}^{k} \\
& \b{compute} \; m = \; \c{M}( K, t \| s \| p \| w \| c ) \\
& \b{return} \; ( t, s, p, w, c, m ) \\

\end{array}
\right.
\]

The client must send the MAC $m$, and the challenge $c$ and challenge
parameters $p$ with the response token so that the server can verify
the challenge and the response.  The server should also include in the
MAC the connection parameters, at minimum enough to identify the
connection-slot and some time measurement or increasing counter $t$ so
that old challenge responses can not be collected and re-used after
the connection-slots are free.  The challenge and MAC would be sent in
the TCP SYN-ACK response message, and the client would include the
interactive hashcash token (challenge-response) in the TCP ACK
message.  As with syn-cookies, the server would not need to keep any
state per connection prior to receiving the TCP ACK.

For backwards compatibility with syn-cookie aware TCP stacks, a
hashcash-cookie aware TCP stack would only turn on hashcash-cookies
when it detected that it was subject to a TCP connection-depletion
attack.  Similar arguments as given by Dan Bernstein in
\cite{Bernstein:syn-cookie} can be used to show that backwards
compatibility is retained, namely under syn-flood attacks Bernstein's
arguments show how to provide backwards compatibility with non
syn-cookie aware implementations; similarly under connection-depletion
attack hashcash-cookies are only turned on at a point where service
would anyway otherwise be unavailable to a non-hashcash-cookie aware
TCP stack.

As the flood increases in severity the hashcash-cookie algorithm would
increase the collision size required to be in the TCP ACK message.
The hashcash-cookie aware client can still connect (albeit increasinly
slowly) with a more fair chance against the DoS attacker presuming the
DoSer has limited CPU resources.  The DoS attacker will effectively be
pitting his CPU against all the other (hashcash-cookie aware) clients
also trying to connect.  Without the hashcash-cookie defense the DoSer
can flood the server with connection establishments and can more
easily tie up all it's slots by completing n connections per idle
connection time-out where n is the size of the connection table, or
pinging the connections once per idle connection time-out to convince
the server they are alive.

Connections will be handed out to users collectively in rough
proportion to their CPU resources, and so fairness is CPU resource
based (presuming each user is trying to open as many connections as he
can) so the result will be biased in favor of clients with fast
processors as they can compute more interactive-hashcash
challenge-response tokens per second.

\subsection{Non-Parallelizability}

For interactive hashcash there are some arguments in favor of using
non-parallelizable CPU cost functions to frustrate Distributed DoS
(DDoS): with such a cost function the DDoS attacker would be unable
sub-divide and farm out the work of computing a token corresponding to
an individual challenge.  The author described a fixed-cost,
non-parallelizable cost function in \cite{Back:1999:amortizable} using
Rivest, Shamir and Wagner's time-lock puzzle
\cite{Rivest:1996:timelock}.  The time-lock puzzle cost function can
be used in either an interactive or non-interactive setting as it is
safe for the chose their own challenge.  Subsequently the same
non-parallelizable cost function was independently suggested by
Freedman et al in chapter 16 of \cite{orielly:2001:p2p}.

For completeness we present the time-lock puzzle based cost function
from \cite{Back:2000:amortizable} here:

\[
\left\{ 
\begin{array}{ll}

\s{PUBLIC:} & n = pq \\

\s{PRIVATE:} & \n{primes} \; p \; \n{and} \; q, \;
\phi(n) = (p-1)(q-1) \\

\\

\c{C} = \s{CHAL}(w) & \b{choose} \; r \in_{R} [0,n) \\
& \b{return} \; (r,w) \\

\c{T} = \s{MINT}(\c{C}) & \b{compute} \; x = r^{r^{w}} \pmod{n} \\
& \b{return} \; (x,w) \\

\c{V} = \s{VALUE}(\c{T}) & \b{if} \; 
r^{r^{w}} = t \pmod{n} \; \b{return} \; w \\
& \b{else return} \; 0 \\

\end{array}
\right.
\]

We argue however that the added DDoS protection provided by
non-parallelizable cost functions is marginal: unless the server
restricts the number of challenges it hands out to a recongizably
unique client the DDoS attacker can farm out multiple challenges as
easily as farm out a sub-divided single challenge, and consume the
resources on the server at the same rate as before.  Further it is not
that hard for a single client to masquerade as multiple clients to a
server.

Consider also: the DDoS attacker has generally due to the nature of
his method commandeering nodes an equal number of network connected
nodes at his disposal as processors.  He can therefore in any case
have each attack node directly participate in the normal protocol
indistinguisably from any legitimate user.  This attack strategy is
also otherwise optimal anyway because the DDoS attacker's swarm of
servant nodes will be hardest to distinguish from geniune users if
they connect separately to present a varied set of source addresses
which will by-pass attempts at per-connection fairness and throttling
strategies and router based DDoS counter-measures based on volume of
traffic across IP address ranges.  In these attack node marshalling
patterns non-parallelizable hashcash offers no added resistance.

As well as this argument against the practical efficacy and value of
non-parallelizable cost functions, to date non-parallelizable cost
functions have had orders of magnitude slower verification functions
than non-parallelizable cost functions.  This is because the
non-parallelizable cost functions so far discussed in the literature
are related to trap-door public key cryptography constructs which are
inherently less efficient.  It is an open question as to whether there
exist efficiently verifiable non-parallelizable cost functions based
on symmetric key constructs.

While for the application of cost functions, a reduced public key size
could be used to speed up the verification function, this approach
introduces risk that the modulus will be factored with the result that
the attacker gains a massive advantage in minting tokens.  Factoring
is itself a largely parallelizable computation.

To combat this the server should change the public parameters
periodically.  However in the particular case of the public parameters
used by time-lock puzzles (which are the same as the RSA modulus used
in RSA encryption), this operation is itself moderately expensive, so
this operation would not be performed too frequently.  It would
probably be wise for a node not to use key sizes below 768 bits and to
change the key every hour or so.  (RSA modulii of 512 bits have
recently been demonstrated to be factorizable using standard equipment
in an office \cite{vanSomeren:2002:512-RSA-factorization}; DDoS
attackers are known be able to muster significant resources, probably
easily exceeding those used in this demonstration.)

The time-lock puzzle cost-function also is necessarily trap-door as
the server needs a private key to allow it to efficiently verify
tokens.  The existance of a verification-key presents the added risk
of key compromise allowing the attacker to by-pass the cost-function
protection.  (The interactive hashcash cost function by comparison is
trap-door-free, so there is no key which would allow an attacker a
short-cut in computing tokens).  In fact if the verification-key were
compromised, it could be replaced, but this need adds complexity and
administrative overhead as this event needs to be detected and manual
intervention or some automated detection triggering key-replacement
implemented.

The time-lock puzzle cost-function also will tend to have larger
messages as there is a need to communicate planned and emergency
re-keyed public parameters.  For some applications, for example the
syn-cookie and hashcash-cookie protocols, space is at a premium due to
backwards compatibility and packet size constraints imposed by the
network infrastructure.

So in summary we argue that non-parallelizable cost functions are of
dubious practical value in protecting against DDoS attacks, have more
expensive verification functions, incur the risk of verification key
compromise and attendant key management complexities, have larger
messages, and are significantly more complex to implement.  We
therefore recommend instead the interactive hashcash protocol.

\section{Hashcash improvements}

One improvement suggested independently by Hal Finney
\cite{Finney:2002:hashcash} and Thomas Boschloo
\cite{Boschloo:2002:hashcash} for the non-interactive form of hashcash
is to find a collision against a fixed, hash-output sized string
rather than the current method which creates a \emph{fair} target to
find a collision against by hashing the service-name.  Their
observation is that a fixed collision target is also fair, and
simpler.  A fixed target string which is convenient to compare trial
collisions against is the k-bit string $0^k$ where $k$ is the hash
output size.  Hashcash would then be defined as:

\[
\left\{ 
\begin{array}{ll}

\c{T} = \s{MINT}(s,w) & 
\b{find} \; x \in_{R} \{0,1\}^{\star} \; \b{st} \; 
\c{H}(s\|x) \lb{w} 0^k\\
& \b{return} \; ( x, s ) \\

\c{V} = \s{VALUE}(\c{T}) & \c{H}(s\|x) \lb{v} 0^k \\
& \b{return} \; v \\

\end{array}
\right.
\]

which should make the hashcash verification function about twice as
fast.

\section{Applications}

Apart from the initially proposed applications for hashcash of
throttling DoS against remailer networks and detering email spam, the
following applications have been discussed, explored and in some cases
implemented and deployed:

\begin{itemize}

\item hashcash-cookies, a potential extension of the syn-cookie as
discussed in section \ref{hashcash-cookies} for allowing more graceful
service degradation in the face of connection-depletion attacks.

\item interactive-hashcash as discussed in section
\ref{interactive-hashcash} for DoS throttling and graceful service
degradation under CPU overload attacks on security protocols with
computationally expensive connection establishment phases.  No
deployment but the analogous client-puzzle system was implemented with
TLS in \cite{Stubblefield:2001:client-puzzles}

\item hashcash throttling of DoS publication floods in anonymous
publication systems such as Freenet \cite{Clarke:2001:freenet},
Publius \cite{Rubin:2000:publius}, Tangler
\cite{Waldman:2001:tangler},

\item hashcash throttling of service requests in the cryptographic
Self-certifying File System \cite{sfs:mazieres-phd}

\item hashcash throttling of USENET flooding via mail2news networks
\cite{deJoode:m2n-flood:2002}

\item hashcash as a minting mechanism for Wei Dai's b-money electronic
cash proposal, an electronic cash scheme without a banking interface
\cite{Dai:b-money:1998}

\end{itemize}

\newpage

\bibliographystyle{unsrt}
\bibliography{hash}

% todo
% check Michael Freedoman's Tarzan anon-IP system

% think about non-parallelizability of interactive hashcash
% it's not relevant for hashcash but is for interactive

% theory: bounded-cost \subset fixed-cost \subset non-parallelizable 
% as non-parallelizable may not be fixed-cost (and may not be bounded cost)

% reference bread-pudding protocol

\newpage

\begin{appendix}

\end{appendix}

\end{document}
