I decided to write a pure Python hashcash implementation. I have seen
David McNab's Python implementation. Unfortunately, as near as I can
tell (which is supported on the hashcash mailing list archive), McNab
actually implements a different algorithm than hashcash. It might (or
might not) be equivalent in security; but I cannot see any directly
way to transform what he computes into an actual hashcash stamp.
Barnes Connelly also posted a sort-of hashcash implementation on
c.l.py. But his only creates a padding suffix, not the actual
hashcash field; moreover, Connelly's version seems to look for
trailing zeros in the hash, not leading zeros.
I created a Pure Python module today that seems to conform with the
hashcash v.1 standard. But I probably missed something. It's just
barely tested--call this an alpha version. Still, I figured I'd send
it out here.... if anyone sees something I've done wrong, please let
me know so I can correct it before distributing the module more
widely.
Btw. If anyone wants to, please feel encouraged to post this to the
Cookbook.
-----------------------------------------------------------
"""Implemen t Hashcash version 1 protocol in Python
Double spend database not implemented in this module, but stub
for callbacks is provided in the 'check()' function
The function 'check()' will validate hashcash v.1 tokens, as well as
'generalized hashcash' tokens generically. Future protocol version
are
treated as generalized tokens (should a future version be published
w/o
this module being correspondingly updated).
A 'generalized hashcash' is implemented in the '_mint()' function,
with the
public function 'mint()' providing a wrapper for actual hashcash
protocol.
The generalized form simply finds a suffix that creates zero bits in
the
hash of the string concatenating 'challenge' and 'suffix' without
specifying
any particular fields or delimiters in 'challenge'. E.g., you might
get:
[color=blue][color=green][color=darkred]
>>> from hashcash import mint, _mint
>>> mint('foo', bits=16)[/color][/color][/color]
'1:16:040922:fo o::+ArSrtKd:164 b3'[color=blue][color=green][color=darkred]
>>> _mint('foo', bits=16)[/color][/color][/color]
'9591'[color=blue][color=green][color=darkred]
>>> from sha import sha
>>> sha('foo9591'). hexdigest()[/color][/color][/color]
'0000de4c9b27ce c9b20e2094785c1 c58eaf23948'[color=blue][color=green][color=darkred]
>>> sha('1:16:04092 2:foo::+ArSrtKd :164b3').hexdig est()[/color][/color][/color]
'0000a9fe0c6db2 efcbcab15157735 e77c0877f34'
Notice that '_mint()' behaves deterministical ly, finding the same
suffix
every time it is passed the same arguments. 'mint()' incorporates a
random
salt in stamps (as per the hashcash v.1 protocol).
"""
import sys
from string import ascii_letters
from math import ceil, floor
from sha import sha
from random import choice
from time import strftime, localtime, time
ERR = sys.stderr # Destination for error messages
DAYS = 60 * 60 * 24 # Seconds in a day
def mint(resource, bits=20, now=None, ext='', saltchars=8,
stamp_seconds=F alse):
"""Mint a new hashcash stamp for 'resource' with 'bits' of
collision
20 bits of collision is the default.
'ext' lets you add your own extensions to a minted stamp. Specify
an
extension as a string of form 'name1=2,3;name 2;name3=var1=2, 2,val'
FWIW, urllib.urlencod e(dct).replace( '&',';') comes close to the
hashcash extension format.
'saltchars' specifies the length of the salt used; this version
defaults
8 chars, rather than the C version's 16 chars. This still
provides about
17 million salts per resource, per timestamp, before birthday
paradox
collisions occur. Really paranoid users can use a larger salt
though.
'stamp_seconds' lets you add the option time elements to the
datestamp.
If you want more than just day, you get all the way down to
seconds,
even though the spec also allows hours/minutes without seconds.
"""
ver = "1"
now = now or time()
if stamp_seconds: ts = strftime("%y%m% d%H%M%S", localtime(now))
else: ts = strftime("%y%m% d", localtime(now))
challenge = "%s:"*6 % (ver, bits, ts, resource, ext,
_salt(saltchars ))
return challenge + _mint(challenge , bits)
def _salt(l):
"Return a random string of length 'l'"
alphabet = ascii_letters + "+/="
return ''.join([choice(alphabet ) for _ in [None]*l])
def _mint(challenge , bits):
"""Answer a 'generalized hashcash' challenge'
Hashcash requires stamps of form
'ver:bits:date: res:ext:rand:co unter'
This internal function accepts a generalized prefix 'challenge',
and returns only a suffix that produces the requested SHA leading
zeros.
NOTE: Number of requested bits is rounded up to the nearest
multiple of 4
"""
prefix_hash = sha(challenge)
counter = 0
hex_digits = int(ceil(bits/4.))
while 1:
candidate = prefix_hash.cop y()
candidate.updat e(hex(counter)[2:])
digest = candidate.hexdi gest()
if digest.startswi th('0'*hex_digi ts):
return hex(counter)[2:]
counter += 1
def check(stamp, resource=None, bits=None,
check_expiratio n=None, ds_callback=Non e):
"""Check whether a stamp is valid
Optionally, the stamp may be checked for a specific resource,
and/or
it may require a minimum bit value, and/or it may be checked for
expiration, and/or it may be checked for double spending.
If 'check_expirati on' is specified, it should contain the number
of
seconds old a date field may be. Indicating days might be easier
in
many cases, e.g.
[color=blue][color=green][color=darkred]
>>> from hashcash import DAYS
>>> check(stamp, check_expiratio n=28*DAYS)[/color][/color][/color]
NOTE: Every valid (version 1) stamp must meet its claimed bit
value
NOTE: Check floor of 4-bit multiples (overly permissive in
acceptance)
"""
if stamp.startswit h('0:'): # Version 0
try:
date, res, suffix = stamp[2:].split(':')
except ValueError:
ERR.write("Malf ormed version 0 hashcash stamp!\n")
return False
if resource is not None and resource != res:
return False
elif check_expiratio n is not None:
good_until = strftime("%y%m% d%H%M%S",
localtime(time( )-check_expiratio n))
if date < good_until:
return False
elif callable(ds_cal lback) and ds_callback(sta mp):
return False
elif type(bits) is not int:
return True
else:
hex_digits = int(floor(bits/4))
return sha(stamp).hexd igest().startsw ith('0'*hex_dig its)
elif stamp.startswit h('1:'): # Version 1
try:
claim, date, res, ext, rand, counter =
stamp[2:].split(':')
except ValueError:
ERR.write("Malf ormed version 1 hashcash stamp!\n")
return False
if resource is not None and resource != res:
return False
elif type(bits) is int and bits > int(claim):
return False
elif check_expiratio n is not None:
good_until = strftime("%y%m% d%H%M%S",
localtime(time( )-check_expiratio n))
if date < good_until:
return False
elif callable(ds_cal lback) and ds_callback(sta mp):
return False
else:
hex_digits = int(floor(int(c laim)/4))
return sha(stamp).hexd igest().startsw ith('0'*hex_dig its)
else: # Unknown ver or generalized
hashcash
ERR.write("Unkn own hashcash version: Minimal
authentication! \n")
if type(bits) is not int:
return True
elif resource is not None and stamp.find(reso urce) < 0:
return False
else:
hex_digits = int(floor(bits/4))
return sha(stamp).hexd igest().startsw ith('0'*hex_dig its)
def is_doublespent( stamp):
"""Placehol der for double spending callback function
The check() function may accept a 'ds_callback' argument, e.g.
check(stamp, "mertz@gnosis.c x", bits=20,
ds_callback=is_ doublespent)
This placeholder simply reports stamps as not being double spent.
"""
return False
David McNab's Python implementation. Unfortunately, as near as I can
tell (which is supported on the hashcash mailing list archive), McNab
actually implements a different algorithm than hashcash. It might (or
might not) be equivalent in security; but I cannot see any directly
way to transform what he computes into an actual hashcash stamp.
Barnes Connelly also posted a sort-of hashcash implementation on
c.l.py. But his only creates a padding suffix, not the actual
hashcash field; moreover, Connelly's version seems to look for
trailing zeros in the hash, not leading zeros.
I created a Pure Python module today that seems to conform with the
hashcash v.1 standard. But I probably missed something. It's just
barely tested--call this an alpha version. Still, I figured I'd send
it out here.... if anyone sees something I've done wrong, please let
me know so I can correct it before distributing the module more
widely.
Btw. If anyone wants to, please feel encouraged to post this to the
Cookbook.
-----------------------------------------------------------
"""Implemen t Hashcash version 1 protocol in Python
Double spend database not implemented in this module, but stub
for callbacks is provided in the 'check()' function
The function 'check()' will validate hashcash v.1 tokens, as well as
'generalized hashcash' tokens generically. Future protocol version
are
treated as generalized tokens (should a future version be published
w/o
this module being correspondingly updated).
A 'generalized hashcash' is implemented in the '_mint()' function,
with the
public function 'mint()' providing a wrapper for actual hashcash
protocol.
The generalized form simply finds a suffix that creates zero bits in
the
hash of the string concatenating 'challenge' and 'suffix' without
specifying
any particular fields or delimiters in 'challenge'. E.g., you might
get:
[color=blue][color=green][color=darkred]
>>> from hashcash import mint, _mint
>>> mint('foo', bits=16)[/color][/color][/color]
'1:16:040922:fo o::+ArSrtKd:164 b3'[color=blue][color=green][color=darkred]
>>> _mint('foo', bits=16)[/color][/color][/color]
'9591'[color=blue][color=green][color=darkred]
>>> from sha import sha
>>> sha('foo9591'). hexdigest()[/color][/color][/color]
'0000de4c9b27ce c9b20e2094785c1 c58eaf23948'[color=blue][color=green][color=darkred]
>>> sha('1:16:04092 2:foo::+ArSrtKd :164b3').hexdig est()[/color][/color][/color]
'0000a9fe0c6db2 efcbcab15157735 e77c0877f34'
Notice that '_mint()' behaves deterministical ly, finding the same
suffix
every time it is passed the same arguments. 'mint()' incorporates a
random
salt in stamps (as per the hashcash v.1 protocol).
"""
import sys
from string import ascii_letters
from math import ceil, floor
from sha import sha
from random import choice
from time import strftime, localtime, time
ERR = sys.stderr # Destination for error messages
DAYS = 60 * 60 * 24 # Seconds in a day
def mint(resource, bits=20, now=None, ext='', saltchars=8,
stamp_seconds=F alse):
"""Mint a new hashcash stamp for 'resource' with 'bits' of
collision
20 bits of collision is the default.
'ext' lets you add your own extensions to a minted stamp. Specify
an
extension as a string of form 'name1=2,3;name 2;name3=var1=2, 2,val'
FWIW, urllib.urlencod e(dct).replace( '&',';') comes close to the
hashcash extension format.
'saltchars' specifies the length of the salt used; this version
defaults
8 chars, rather than the C version's 16 chars. This still
provides about
17 million salts per resource, per timestamp, before birthday
paradox
collisions occur. Really paranoid users can use a larger salt
though.
'stamp_seconds' lets you add the option time elements to the
datestamp.
If you want more than just day, you get all the way down to
seconds,
even though the spec also allows hours/minutes without seconds.
"""
ver = "1"
now = now or time()
if stamp_seconds: ts = strftime("%y%m% d%H%M%S", localtime(now))
else: ts = strftime("%y%m% d", localtime(now))
challenge = "%s:"*6 % (ver, bits, ts, resource, ext,
_salt(saltchars ))
return challenge + _mint(challenge , bits)
def _salt(l):
"Return a random string of length 'l'"
alphabet = ascii_letters + "+/="
return ''.join([choice(alphabet ) for _ in [None]*l])
def _mint(challenge , bits):
"""Answer a 'generalized hashcash' challenge'
Hashcash requires stamps of form
'ver:bits:date: res:ext:rand:co unter'
This internal function accepts a generalized prefix 'challenge',
and returns only a suffix that produces the requested SHA leading
zeros.
NOTE: Number of requested bits is rounded up to the nearest
multiple of 4
"""
prefix_hash = sha(challenge)
counter = 0
hex_digits = int(ceil(bits/4.))
while 1:
candidate = prefix_hash.cop y()
candidate.updat e(hex(counter)[2:])
digest = candidate.hexdi gest()
if digest.startswi th('0'*hex_digi ts):
return hex(counter)[2:]
counter += 1
def check(stamp, resource=None, bits=None,
check_expiratio n=None, ds_callback=Non e):
"""Check whether a stamp is valid
Optionally, the stamp may be checked for a specific resource,
and/or
it may require a minimum bit value, and/or it may be checked for
expiration, and/or it may be checked for double spending.
If 'check_expirati on' is specified, it should contain the number
of
seconds old a date field may be. Indicating days might be easier
in
many cases, e.g.
[color=blue][color=green][color=darkred]
>>> from hashcash import DAYS
>>> check(stamp, check_expiratio n=28*DAYS)[/color][/color][/color]
NOTE: Every valid (version 1) stamp must meet its claimed bit
value
NOTE: Check floor of 4-bit multiples (overly permissive in
acceptance)
"""
if stamp.startswit h('0:'): # Version 0
try:
date, res, suffix = stamp[2:].split(':')
except ValueError:
ERR.write("Malf ormed version 0 hashcash stamp!\n")
return False
if resource is not None and resource != res:
return False
elif check_expiratio n is not None:
good_until = strftime("%y%m% d%H%M%S",
localtime(time( )-check_expiratio n))
if date < good_until:
return False
elif callable(ds_cal lback) and ds_callback(sta mp):
return False
elif type(bits) is not int:
return True
else:
hex_digits = int(floor(bits/4))
return sha(stamp).hexd igest().startsw ith('0'*hex_dig its)
elif stamp.startswit h('1:'): # Version 1
try:
claim, date, res, ext, rand, counter =
stamp[2:].split(':')
except ValueError:
ERR.write("Malf ormed version 1 hashcash stamp!\n")
return False
if resource is not None and resource != res:
return False
elif type(bits) is int and bits > int(claim):
return False
elif check_expiratio n is not None:
good_until = strftime("%y%m% d%H%M%S",
localtime(time( )-check_expiratio n))
if date < good_until:
return False
elif callable(ds_cal lback) and ds_callback(sta mp):
return False
else:
hex_digits = int(floor(int(c laim)/4))
return sha(stamp).hexd igest().startsw ith('0'*hex_dig its)
else: # Unknown ver or generalized
hashcash
ERR.write("Unkn own hashcash version: Minimal
authentication! \n")
if type(bits) is not int:
return True
elif resource is not None and stamp.find(reso urce) < 0:
return False
else:
hex_digits = int(floor(bits/4))
return sha(stamp).hexd igest().startsw ith('0'*hex_dig its)
def is_doublespent( stamp):
"""Placehol der for double spending callback function
The check() function may accept a 'ds_callback' argument, e.g.
check(stamp, "mertz@gnosis.c x", bits=20,
ds_callback=is_ doublespent)
This placeholder simply reports stamps as not being double spent.
"""
return False
Comment