Date: Mon, 6 Jul 2015 14:24:12 -0700
From: Bill Cox <waywardgeek@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] Memory-hard proof of work with fast verification (CPU Hash)

On Mon, Jul 6, 2015 at 1:56 PM, Solar Designer <solar@...nwall.com> wrote:

> On Mon, Jul 06, 2015 at 08:25:48PM +0000, Zooko Wilcox-O'Hearn wrote:
> > Forgive me if this is a naive question, but if you wanted a
> > Proof-of-RAM for a cryptocurrency to be ASIC-resistant and (maybe)
> > GPU-resistant (and I do want that!), then what's wrong with Argon2d
> > with memory size = 1 GiB?
>
> I guess Bill meant the "fast verification" bit in the Subject.  Filling
> 1 GiB isn't as fast as Bill would like verification to be.
>

Yep.  1 GiB would make block-chain verification too slow.  This trade-off
is why LiteCoin is facing an ASIC crisis
<https://bitcoinmagazine.com/11125/asics-litecoin-come/>.

Maybe we have to get more extreme, and start executing randomly generated
x86-64 machine code in  PoW, but we can certainly do better than a 128KiB
Scrypt hash if we can do rapid verification.

However, Argon team recently described what may be a solution to that,
> in Section 8 of:
>
> "Research paper "Fast and Tradeoff-Resilient Memory-Hard Functions for
> Cryptocurrencies and Password Hashing". Introduces Argon2 and its
> fast-verification feature."
>
> as available here:
>
> https://www.cryptolux.org/index.php/Argon2
>
> I haven't looked into this myself yet.  I guess Bill should.  And I
> guess you did, Zooko?


I just went and read it.  I have a post waiting in the queue at the
meltzdown crypto list, where I ask if anyone knows if Momentum and/or
Cuckoo Cycle have been broken, which I equate to proving they are not
memory-hard.  I think I outlined enough of a proof to show why neither are
memory hard (basically, generate hashes in parallel, and use a parallel
sort algorithm).

So, for now, the Argon work is the only remaining memory-hard PoW with
rapid verification left standing, AFAIK.  I read it, and I do believe it
works.  It is basically the old Merkel Hash Tree based PoW
<http://eprint.iacr.org/2007/433> using Argon2 (or any other memory-hard
algorithm) to create the leaf data.

There are practical details that may have been left out of the paper, such
as how to keep the Blake2 hashes over every 256-bits generated by Argon2
from massively dominating runtime, which might allow an attacker to use
slower memory.  I do not think these are fundamental problems, just things
to be fleshed out, or upgraded.

> In other words, what's the point of the proposed ROM-hardness feature?
>
> I originally proposed it for authentication servers, and it's similar:
> need to support request rates in thousands per second, so can't fill a
> lot of RAM within the allotted time.  This is compensated for by also
> having a large ROM.  And yes, this is a different type of defense, with
> its different properties, so no exact "compensation" - it can be worse
> or better than simply filling more RAM each time, but usually filling as
> much RAM as we'd use for a ROM is simply not an option (would be taking
> too long for the use case where we'd also use a ROM).  Quite often, we
> don't even get close - e.g., 1.75 MiB RAM + 112 GiB ROM for one of my
> authentication server examples, for 10k requests/s on 16-core server.
>
> Alexander


I am a big fan of this approach.   It defeats most nodes in a bot-net for
an off-line attacker with a copy of the ROM, and defeats any off-line
attacker without it.  Too bad that the ROM access is not memory-hard :-)
 That would have made a nice memory-hard PoW.

Bill

Content of type "text/html" skipped

Powered by blists - more mailing lists