Hashcash is a proof of work algorithm

Hashcash was created by Adam Back to prevent spam and other similar types of abuses of internet resources where you don’t have to pay for the marginal use of that resource.

The solution is to have a token that proves the client has done an expensive computation. This way, it becomes prohibitively expensive to abuse these resources, as you would need an ever increasing computational power.

This token is generated by a cost-function. A cost-function should be hard to compute, but easy to verify. The hashcash cost-function relies on computing partial hash collisions. Partial Hash Collision is when a part of two hashes collide.

If the token is valid, when it is appended to the message, and this combo (message+token) is hashed, the result will be a hash with a partial hash collision.

The size of the partial hash collision is parametrized in the cost-function.

The only way to compute the token is brute-force. i.e. trying every possibility until a desired one is found. The larger the collision wanted, the more expensive it is to compute the token.

Hashcash is an example of a proof-of-work algorithm.

Here’s a simple implementation of it:

import hashlib
 
def leading_zeros(message):
	for i in range(len(message)):
		if message[i] != "0":
			return i
		++i
	return len(message)
 
 
def hash(message):
	return hashlib.sha256(message.encode()).hexdigest()
 
 
def make_token(message, collision_size):
	i = 0
	token = ""
	while True:
		token = format(i, "x")
		result = hash(message + token)
		if leading_zeros(result) >= collision_size:
			print(f"Made {i} iterations")
			return token
		i += 1
 
 
def verify_token(message, token, collision_size):
	result = hash(message + token)
	return leading_zeros(result) <= collision_size