Skip to content

Instantly share code, notes, and snippets.

@masonforest
Last active March 29, 2019 00:56
Show Gist options
  • Save masonforest/e674ee749a01391f4ce7a35aa7bbf286 to your computer and use it in GitHub Desktop.
Save masonforest/e674ee749a01391f4ce7a35aa7bbf286 to your computer and use it in GitHub Desktop.
Hashfactor is proof of work algorithm inspired by hashcash
# 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
## ..
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment