[Cryptography] Looking for sequential-memory-hard hashing

Ray Dillinger bear at sonic.net
Sat Mar 14 17:21:11 EDT 2015


I have an application that requires a proof-of-work function
depending on some data plus a nonce - (possibly a hash but
needn't have all the properties of a good cryptographic hash)
which needs to be fast to verify on all machines, but
drastically harder to compute on machines with small memory
than on servers with large memory.

The best I've come up with is a "triplet birthday search" -
a search for 3 nonces that yield a collision in the first
N bits under some conventional hash function.  (I think N
is around 30 bits).

It's memory hard because an efficient implementation
requires a large (2^N entries) cache of nonces indexed by
hash to efficiently find triplets, and triplets don't
invoke the birthday paradox nearly as quickly as twins
do. Any implementation with a smaller table should be
able to find triplets at a speed that depends on the
ratio of their table size to the size of the whole table.

I can limit the effect of ASIC parallelism by forcing
parallel threads to have contention for locks in the table.
This can be accomplished by requiring that the nonces be
within a limited numeric range of each other - the proof-
of-work would be presented as A,B,C, where A is a 64-bit
number, and B and C are 32-bit "offsets" from A. That
will require constantly updating the table so that its
entries stay within the set numeric range.

My question for the list is, can anybody think of a way
to make this worse for ASICs and small-memory systems?
Can I force more contention for the table?  Is there
any construction anyone is aware of that's better than
a triplet search?

Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150314/9b3ce68a/attachment.sig>


More information about the cryptography mailing list