Hashcash (a.k.a. “Proof of Work”)

A simple math problem that will take a client significantly more processing power (i.e. GPU or CPU) to solve than it will take a server to verify that a given solution is correct.

Although Hashcash is the seed from which the idea of “Crypto Currency” (Crypto=Hash, Cash=Currency) sprung, the original goal was nothing more than to provide simple and effective way to provide light resistance to spam bots and Denial of Service attacks.

It’s a niche application.

Overview

This is what HTTP Hashcash looks like:

Hashcash: H:20:5197489836:example.com:4PF4B5e0_spEr0b3n0OM4g:SHA-256:eHQPAA

As you can see (if you squint), it functions similarly to the HTTP Authorization schemes (such as Digest Authentication) in that you make a request and, if you have a valid header, you get the expected reply, otherwise you get an error along with instructions that accompany a simple computation.

(note: it is NOT a form of authentication or authorization and should not be used as such)

The basic flow is like this:

1. Client makes a request to POST /api/new-hashcash (optional)
2. Server responds with a Hashcash-Challenge header
3. Client solves the challenge with the specified algorithm
   • (“solving” means finding a hash with the specified number of leading zeros)
4. Client includes solution in Hashcash header (or Cookie) in future requests
5. Server rejects invalid requests with 400 Bad Request
   • such requests should include Hashcash-Challenge header
   • (and, technically, 402 Payment Required is an appropriate alternative)

It’s not strictly necessary to have the /api/new-hashcash resource - it’s just as well for the client to make the intended request, handle the error with the challenge, and then retry.

Wire Protocol

Just as with Digest Authentication and many of Bearer Authorization schemes (such as JWT), the Hashcash-Challenge header contains the metadata that describe the verification algorithm.

A solution is verified by using the specified algorithm to hash the “token” and then checking that at least as many of the leading bits are set to zero as specified by the difficulty.

Of course, the token must not be expired and the nonce must be a valid nonce issued by the server.

Example Hashcash Challenge

Hashcash-Challenge: H:20:5197489836:example.com:4PF4B5e0_spEr0b3n0OM4g:SHA-256

Example Hashcash Solution

Header for apps and API clients:

Hashcash: H:20:5197489836:example.com:4PF4B5e0_spEr0b3n0OM4g:SHA-256:eHQPAA

You can see that hash of the solution has 20+ leading zero bits, therefore the solution is correct:

SHA-256( "H:20:5197489836:example.com:4PF4B5e0_spEr0b3n0OM4g:SHA-256:eHQPAA" )

00000e0c52d2d99e231984605c3b2b4478132fb9a802ea0931cfede38fd24637

Cookie for static sites and Browser clients:

Cookie: hashcash=H:20:5197489836:example.com:4PF4B5e0_spEr0b3n0OM4g:SHA-256:eHQPAA; foo=...

Whenever the server issues a new Hashcash-Challenge the client should discard the prior hashcash and solve the new one. When a server is under attack this could be as frequently as every request.

If the hashcash expires, the server may reject

Hashcash Segments Explained

Part of the reason for this is that it allows the server to keep a small whitelist of unexpired nonce values rather than a large blacklist of used random values.

Pseudo-Code Solution

challenge = "H:20:5197489836:example.com:4PF4B5e0_spEr0b3n0OM4g:SHA-256"
solution = 0
difficulty = 20
hashcash = ""

while true {
    hashcash = challenge + ":" + URLSAFE_BASE64( solution )
    bytes = SHA256( hashcash )
    if FIRST_N_BITS_ARE_ZERO( bytes, difficulty ) {
        break
    }
    solution += 1
}

// H:20:5197489836:example.com:4PF4B5e0_spEr0b3n0OM4g:SHA-256:eHQPAA
return hashcash

Compared to SMTP Hashcash V1

HTTP Hashcash is similar to the original SMTP Hashcash v1 protocol, but with a few key differences (noted below).

SMTP MIME Header (initiated by client):

X-Hashcash: 1:20:1303030600:anni@cypherspace.org::McMybZIhxKXu57jd:ckvi

Here’s a breakdown of the SMTP Hashcash:

Key Differences:

• Allow Tag string in place of Version Int
• Rename Bits to Difficulty (definition only; for clarity)
• The server should define Expires At as an int64 Unix timestamp rather than accepting the client’s Date with arbitrary precision
  • (ISO timestamps could not be used due to : as a separator)
• Rename Resource to Subject (definition only; for parity with other standards)
• Replace unused Extension with Algorithm, as this may need to change over time
• The server should define a random Nonce rather than accepting the client’s Rand
• Rename Counter to Solution as it’s not important that it “count”

Effectiveness, Caveats, and Considerations

The effectiveness of Hashcash is three-fold:

1. The amount of time and resources that it takes to reject a client with a missing or invalid Hashcash is almost zero - far less than the time of a normal response.
2. The difficulty of the challenge and the expiration can be temporarily modified during a Denial of Service attack (even when distributed), seriously limiting its effectiveness.
3. Any spam bot counter-measure is effective against most spam bots as they prefer targets that require zero effort.

This is similar to what CloudFlare does when it is “Checking your browser” when a site is under attack.

However, there are also some caveats:

1. Common debugging tools, such as curl do not implement Hashcash natively, meaning that more tooling is required for development.
2. In the event of a Denial of Service attack, the trade off is that the burden of the attack is shared equally among legitimate clients.
3. Any measure that makes your service less attractive or less accessible to spam bots will also do the same for some developers.

The difficulty and expiration can be adjusted when under attack, but doing so effectively redistributes the load of the attack among clients (including the attacker), which means that clients for whom the service is not critical may prefer to refuse challenges over a certain difficulty - which seems preferable to ALL clients being denied service.

Implementation

See https://git.rootprojects.org/root/hashcash

Issuing a Hashcash

1. The server should issue a Hashcash-Challenge header whenever the Hashcash header is absent or invalid.
2. The server should store the hashcash by the Nonce (including Subject, Difficulty, Expires At, etc) and validate the solution against the original hashcash.

Solving a Hashcash

The client should keep changing the solution value (incrementing and re-encoding to base64 would be acceptable) until the hash of the Hashcash string starts with the given number of bits set to zero.

(the comparison must be little endian, but since each byte can be checked independently, this should not matter)

var textEncoder = new TextEncoder();
var solution = 0;

function next() {
    var u8 = textEncoder.encode(
        'H:20:5197489836:example.com:4PF4B5e0_spEr0b3n0OM4g:SHA-256:' +
            int52ToBase64(solution)
    );
    var p = crypto.subtle.digest('SHA-256', u8).then(function (hash) {
        hash = new Uint8Array(hash);
        console.log(hash);
        return hash;
    });
    solution += 1;
}

next();

function int52ToBase64(n) {
    var hex = n.toString(16);
    if (hex.length % 2) {
        hex = '0' + hex;
    }

    var bin = [];
    var i = 0;
    var d;
    var b;
    while (i < hex.length) {
        d = parseInt(hex.slice(i, i + 2), 16);
        b = String.fromCharCode(d);
        bin.push(b);
        i += 2;
    }

    return btoa(bin.join(''));
}

Note: If you need to solve a hashcash in a browser you should use a pure JS implementation of SHA2. WebCrypto is NOT performant for small hashes (due to the Promise microtasks and C++ context switches) and will take WHOLE SECONDS for even a small number of rounds.

Verifying the Hashcash

1. The server should parse the hashcash into the relevant parts.
2. The server should check that the Nonce is valid and not expired.
3. The server should validate that the hash of the Hashcash results in a value with the minimum number of bits set to 0

// Psuedo-Code

hashcash = 'H:20:5197489836:example.com:4PF4B5e0_spEr0b3n0OM4g:SHA-256:eHQPAA';
bits = 20;
hash = SHA2.sum256(hashcash);

for (i = 0; bits > 0 && i < hash.length; i += 1) {
    if (bits > 8) {
        bits -= 8;
        if (0 != hash[i]) {
            return false;
        }
        continue;
    }

    if (0 != hash[i] >> (8 - bits)) {
        return false;
    }

    return true;
}

History of Hashcash

The general concept of a hashcash has been around for a long time - at least since 1997.

The goal is to make a service resistant to (Distributed) Denial of Service attacks and spam bots.

The implementation requires clients of a service to solve a math problem that will take the client many CPU cycles to complete, but will take the server very few cycles to verify that it is correct.

In practical terms this mean that the client may spend anywhere between a few milliseconds to a few whole seconds solving the problem, and the server will be able to verify in the order of microseconds (less than the time of a normal response), regardless of how challenging the original problem was.

The original hashcash specification was actually a pretty simple solution, but since it was designed back in the ’90s and was only intended for email (SMTP), it’s not quite adequate for modern web applications.