phc-discussions - Re: [PHC] Memory-hard proof of work with fast verification (CPU Hash)

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Tue, 7 Jul 2015 20:27:55 +0000
From: "Zooko Wilcox-O'Hearn" <zookog@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Memory-hard proof of work with fast verification (CPU Hash)

On Mon, Jul 6, 2015 at 9:24 PM, Bill Cox <waywardgeek@...il.com> wrote:
>
> Yep.  1 GiB would make block-chain verification too slow.  This trade-off is
> why LiteCoin is facing an ASIC crisis.

I've heard this said before, but I'm skeptical. According to
https://www.litecoin.info/User:Iddo/Comparison_between_Litecoin_and_Bitcoin,
litecoin chose a 128 KiB memory requirement in order to fit into L2
cache so that people could run a Litecoin miner on their desktop while
also using it for other interactive apps. (If I understand that wiki
page correctly.)

*That's* why there are Litecoin ASICs today, right? If they had chosen
a 1 GiB memory requirement instead then there would not be.

But, your related point is that it might take too much time to do
verification by simply recomputing the winning nonce and seeing if it
produces the right output. How long does it take?

According to https://password-hashing.net/submissions/specs/Argon-v2.pdf

"0.1 seconds on a 2 Ghz CPU using 1 core — Argon2d with 2 lanes and
250 MB of RAM"

You, Bill, probably know better than I do how that would be affected
by such changes as upping RAM from 250 MB to 1 GiB, setting t_cost to
minimum if it isn't already, and switching from Intel i7 to an ARM
chip. Actually, you probably don't, and we need to run our own
benchmarks and report back. :-)

How much of a time budget do we have for verification? There are three answers:

For a full-node (i.e. a verifier but not a miner) that keeps up to
date with the blockchain they need only to perform one verification
every block (10 minutes on average), so the added cost of even a few
tens of seconds per verification isn't too important for them.

For a miner, added latency means a higher chance that the block you
just mined will get beaten in a race by another miner (this is called
a "stale block"), so the cost of a few seconds is probably okay but
10's of seconds is probably not.

For a node that doesn't keep up-to-date with the blockchain but wants
to catch up, for example a "light client" on your cell phone that
wakes up and wants to verify thousands of new-to-it blocks, then this
is killer. An extra few seconds of CPU time per verification means
that your phone heats up and runs out of battery faster. So maybe we
should just say we don't support that use case. :-/

Regards,

Zooko