[hashcash] split blocks with -Z2 (Re: Re: hashcash-1.15 released)

  • From: Adam Back <adam@xxxxxxxxxxxxxxx>
  • To: hashcash@xxxxxxxxxxxxx
  • Date: Sun, 16 Jan 2005 19:27:33 -0500

On Sun, Jan 16, 2005 at 05:45:31PM +0000, Jonathan Morton wrote:
> >There is scope to adapt Jonathan's fastmint code directly to make
> >compact stamps, just more complicated, so I may make that change in
> >future.  I believe Jonathan estimated it should be only around 15%
> >slower if done that way, and I think this slow down would be
> >acceptable.
> Libfastmint should already handle -Z1 stamps as-is, with the ~15% 
> penalty (over -Z0) because some optimisations aren't available.

Yes Z1 implementation is using libfastmint, not timed but presume
something like this perf cost.  In fact I start counting with 1 digit
counter when that overflows move to 2 digit etc.  So that will also
have a small slow down but I think fairly negligible.

> However, -Z2 stamps would still be about 2x slower than -Z1, because 
> the primary limitation is the need to hash two SHA1 blocks per try 
> instead of one

I agree this is the central issue it is allowing split blocks (though
these only occur for certain email lengths: between 21 and 32 char
email addresses (inclusive).  So maybe a simple hack is if the email
address is shorter or longer than that make -Z2 become -Z1.

The other thing I was thinking is one could partly pre-compute even
with a split counter.  Eg split counters like: (^ is SHA1 boundary)
123^4, 12^34, 1^234 like that you could precompute the 1st block and
count through the remainder.  Bringing the perf back from 2x to 1.1x
average (worst case) to 1.001x best case for those cases (as compared
to -Z1 15% slower stamps).

Of course counters like this 1234^ (and indeed all the way back to
1234xxxxxxxx^) are doomed because the 9 padding chars comes afterwards
so will be 2x on all of those.

> To make life easier for users, how about naming them -turbo, -normal, 
> and -compact?  I don't think -normal stamps are visually "too big" for 
> most people, so that's another argument against trying to make -compact 
> stamps faster.  Especially if it would potentially make -turbo slower.

Yes tend to agree.  Looks like there are enough cases were it will be
2x that it's not worth that much to optimize the other compact cases.
(Well to say that the other way around there are only 3 lengths were
you can speed it up -- the 123^4, 12^34, 1^234 above).


Other related posts: