Hashfactor is proof of work algorithm inspired by hashcash

hashfactor.py

# Hashfactor is proof of work algorithm inspired by [hashcash](http://www.hashcash.org/).

# Hashfactor is simpler to implement than hashcash but the result is not a
# hash with leading zeros. This tradeoff is worth-while if you have access to
# a computer to validate proof of work values but you'd like implementation to
# be simpler.

from random import randint
import binascii
import hashlib
import os


def hashfactor(data, target):
  # First hash the data. This is optional but
  # it means that when we're crunching hashes we'll
  # always be hashing the same length data. Uniform
  # length of data will insure the time to hash should be
  # relatively uniform as well.
  input_hash = sha256(data)

  # Start with a random value between 0 and `target`.
  # You could start with zero and increment from there
  # but this will make different runs result in different
  # run times this could be useful in implementing a proof of work
  # cryptocurrency  for example to determine which node mines a block.
  value = randint(0, target)

  # Keep incrementing the value until you find a valid one
  while not verify_hash(input_hash, target, value):
    value += 1
  return value


# Like hashfactor but returns the number of "guesses" it took to
# get the right answer. May be useful for debugging.
def hashfactor_debug(data, target):
  input_hash = sha256(data)
  starting_value = randint(0, target)
  value = starting_value
  while not verify_hash(input_hash, target, value):
    value += 1
  return value, value - starting_value


# Verifies a proof of work value
def verify(data, target, value):
  return verify_hash(sha256(data), target, value)


def verify_hash(input_hash, target, value):
  # First we compute the `output_hash`
  # This is the hash of the input hash concatenated with
  # the value we're testing
  output_hash = sha256(input_hash + int_to_bytes(value))
  # Next we need to convert the hash to an integer value
  # to test against. We could convert the whole hash to an integer
  # but that would be slow.
  # Instead we take a slice of the hash
  # whose length is equal to the one more that
  # the length of the target.
  target_length = len(int_to_bytes(target))
  output_value = bytes_to_int(output_hash[:target_length + 1])

  # We now have some very large random integer that we derived from
  # the hash value. We know the integer is larger than the target
  # The chances that 2 is a factor of the number are 1 in 2.
  # The chances that 3 is a factor of the number are 1 in 3 and so on
  # Therefore it'll take n - 1 "guesses" before we find a valid value.
  # that's why we add back 1 here to make the target values
  # equal to the number of hashes on average it'll take
  # to compute the winning hash.
  return is_factor(output_value, target + 1)


def bytes_to_int(value):
  return int.from_bytes(value[:8], "little")


def int_to_bytes(value):
  return (value).to_bytes((value.bit_length() + 7) // 8, byteorder='little')


def is_factor(numerator, denominator):
  return (numerator % denominator) == 0


def sha256(data):
  m = hashlib.sha256()
  m.update(data)
  return m.digest()


TARGET = 100
LENGTH = 10
data = bytearray(os.urandom(LENGTH))
print("Generated {} bytes of random data".format(LENGTH))
value, guess_count = hashfactor_debug(data, TARGET)

if verify(data, TARGET, value):
  print("It took {} \"guesses\" to find the proof of work value: {}".format(
      guess_count, value))

## Expected Output:
## Generated 10 bytes of random data
## It took 28 "guesses" to find the proof of work value: 65

# The code below can be used to verify that on average
# hashfactor should require TARGET number of hashes to
# get a valid proof of work value.
# --
# total_guesses = 0
# i = 0
# while True:
#   data = bytearray(os.urandom(10))
#   value, guess_count = hashfactor_debug(data, TARGET)
#   total_guesses += guess_count
#   i += 1
#   print("Expected number of hashes: {}, actual: {}".format(TARGET, total_guesses/i))
#
## Expected Output:
## Expected number of hashes: 100, actual: 99.07904245709123
## Expected number of hashes: 100, actual: 99.06726862302483
## Expected number of hashes: 100, actual: 99.05279783393502
## Expected number of hashes: 100, actual: 99.13035633739287
## Expected number of hashes: 100, actual: 99.1307484220018
## ..