[Cryptography] hashes based on lots of concatenated LUT lookups

[Bear]

On Fri, 2014-07-11 at 13:51 +0200, Eugen Leitl wrote:
> It's hard to make a cryptocurrency hash that's ASICproof.

Not as hard as it is to accomplish a specific purpose 
by doing so.

What are you trying to do?  Why do existing ASIC-hard 
hashes not serve your purpose?  

> 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. 

Not quite the case, but close; you can have as many 
parallel threads using the same lookup table as you 
like.  The bottleneck is in the form of limited 
bandwidth between CPU and memory, because each of
those parallel threads is going to ask to see a 
thousand memory locations that no other thread will 
be asking to see.  

>  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.

Right... 

> 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?

For what purposes have you not just answered your own 
question?  Seriously, do you want an all new hash function, 
as opposed to going to going with Scrypt-J or Cuckoo?
If so, what needs to be different from those functions?

				Bear