[cryptography] hashes based on lots of concatenated LUT lookups

Eugen Leitl eugen at leitl.org
Fri Jul 11 07:51:02 EDT 2014

It's hard to make a cryptocurrency hash that's ASICproof.

Cheap/multisource serve/PC COTS hardware has large memory 
size, and intrinsic random access latencies that can't be 
much improved upon for physical reasons (embedded memory
is limited in size due to die yield reasons, so large
LUTs are always much slower than embedded memory).

As such any hash that needs lots of serial/concatenated 
lookups on large (several GByte), random (same preparation as one-time
pads) memory-locked LUTs to compute is ASIC/FPGA/GPU-proof
since it can't be parallized without replicating the expensive
LUT. Dedicated hardware LUT doesn't have price advantages
over COTS-based LUT, though at very large scales LUTs requiring no
refresh are more energy-efficient.

LUT size can be variable to track technology improvements.
Distribution of several GByte LUT across participating nodes
is not too difficult with P2P protocols (Bittorrent & Co)
as it only happens once on bootstrap.

Memory-bound code, especially if run at low priority does
not make end user all-purpose (ASIC is intrinsically special-purpose) 
hardware unusable for other tasks the way GPU mining is.

How would you construct such a hash?

More information about the cryptography mailing list