[hashcash] Re: Hashcash performance improvements

  • From: Adam Back <adam@xxxxxxxxxxxxxxx>
  • To: hashcash@xxxxxxxxxxxxx
  • Date: Fri, 28 May 2004 17:39:58 -0400

btw I put Jonathan's latest code in (copied into 1.00 pre-release3):

        http://www.hashcash.org/source/current/hashcash-1.00/

breaks the 2 megahashes/sec barrier on my 3.06 Ghz P4:

    Rate  Name (* machine default)
  1754180 ANSI Compact 1-pipe *
  1382081 ANSI Standard 1-pipe
  2280434 ANSI Compact 2-pipe
  1824348 ANSI Standard 2-pipe
   ---    PowerPC Altivec Standard 1x4-pipe     (Not available on this machine)
Best minter: ANSI Compact 2-pipe (2280435 hashes/sec)


On Fri, May 28, 2004 at 08:19:26PM +0100, Malcolm Howell wrote:
> [...] Obviously this leaves us looking at a trade-off between stamp
> size and minting time.

Yes works within reason: it is just aesthetics, human readability and
line-wraps you're trading.

> Is there any concept of "order" on the counter, or a requirement
> that the value there is the "lowest"?

The recipient can't tell it's lowest (without repeating work).

I started at 0 and counted up to make a more compact counter.  That is
only motivation.

> And if so, who's going to check it?  

In theory the counter indicates how unlucky the sender got.  eg. if
you are sending a 20bit stamp and the counter is > 2^20 then sender
knows you were (relatively) unlucky.  Not sure that he particularly
cares though.

The other objective is if it fits inside one SHA1 block it helps the
recipient verify the stamp faster.

This makes a slight conflict between the senders interests and the
receivers (hostile sender may send massive stamp which costs nothing
extra practially to compute).  If we cared about this we would ideally
want to enforce small stamps on sender (measured in SHA1 blocks) to
make the receivers verification fast.  Simple "enforcement" would be
if it cost the sender disproportionately more.  

One way to do this would be to put the counter at the beginning,
however this is typically dangerous because then work can be
pre-computed and shared across multiple recipients.  Another would be
to put counter at beginning and at end
(ver:counter:rest-of-stamp:counter) but that is aesthetically
unpleasing and makes larger stamps.

> In other words, is it fair to say that a minting function can
> produce any string for the counter provided it's in the base64
> alphabet?

The random string used to be any printable char in version 0 format.

In version 1 format so far I generate hex digits.  But I accept
anything if I recall.  Need to decide what is clean / simple etc.  Ie
if we say base64 only, then it doesn't matter that its less efficient
because it will also be less efficient for spammers.

It might also help in some sense if we chose things which are simple
to code efficiently, with no unrolled pre-computed tricks available to
keep code simple if that makes same overhead for spammer and normal
user and results in simpler, less unrolled pre-computed, funny-order
counted, manipulated aligned field tricked etc.

(So think about that also in your optimization -- what would help
fairly prevent this optimization and keep things simpler -- we could
adapt v1 spec.)

> I ask because I vaguely remember a statement that the counter should
> be "the first" value that works, although I can't find it and am
> possibly mistaken.  The assumption may have simply been that the
> minter will naturally return the first value it finds that works.

That would have been me.  See above, size argument.

Izzy Kindred was also suggesting earlier that version 1 should support
multiple sub-puzzles; if we do this it will make align at end of SHA1
input block work less well.  As there will be multiple counters.  (See
my post from a few days ago on thought of how they would be
hashed... the previous counter would be hashed in the next one).

Adam

Other related posts: