[cryptography] hashes based on lots of concatenated LUT lookups

[Eugen Leitl]

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?
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

Re: [cryptography] hashes based on lots of concatenated LUT lookups

[Zooko Wilcox-OHearn]

Dear Eugen:

There have been several experiments in this direction, using
memory-hard proofs-of-work. For example, this was the motivation for
Litecoin (https://en.wikipedia.org/wiki/Litecoin) to use scrypt in its
Proof-of-Work. To my knowledge, the state-of-the-art design is John
Tromp's Cuckoo PoW: https://github.com/tromp/cuckoo

In my opinion, this is a promising direction to take. It might still
succumb to centralization-of-mining in the long-term, but maybe not.
There's a possibility it would settle into an economic equilibrium in
which independent/hobbyist/small-time mining is sufficiently
rewarding, but customized, large-scale, vertically-integrated mining
is not rewarding enough to justify its costs.

Among anti-mining-centralization techniques that I've studied, this is
the only one that is easy to implement in the near-term, and doesn't
come with too many complications and risks for near-term deployment.

For the contrarian view, arguing that ASIC-resistance is either
undesirable and/or impossible, see this whitepaper by andytoshi:
http://download.wpsoftware.net/bitcoin/asic-faq.pdf . I disagree with
the conclusions, but it makes some good arguments.

For a survey of state-of-the-art ideas about Proof-of-Stake — ideas
which *aren't* easily implementable and which *do* come with
complexity, uncertainty, and risk — see Vitalik Buterin's latest opus:
https://blog.ethereum.org/2014/07/05/stake/ . That guy is a good
thinker and writer! And he appears to have been reading my mind. As
well as adding in a bunch of ideas that were not in my mind, from such
sources as http://eprint.iacr.org/2014/452.pdf .

Regards,

Zooko
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography