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  PHC 
Open Source and information security mailing list archives
Hash Suite for Android: free password hash cracker in your pocket
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date: Sat, 27 Dec 2014 10:47:42 -0800
From: Gleb Kurtsou <>
Subject: Re: [PHC] [OT] Memory hard proof of work with constant time

On (25/12/2014 11:44), Bill Cox wrote:
> I am not sure if posting off-topic stuff like this here is still OK, but I
> read about the John Tromp's Cuckoo Cycle here, and frankly this list has
> provide amazing feedback in the past, so I'll keep milking this expert
> channel so long as it's not annoying...
> Here's an algorithm I'm thinking about on Christmas.  I hope you enjoy it:
> This algorithm implements a memory hard proof of work scheme with a
> constant time verificatoin capability.  This idea is motivated from:
>       Cuckoo Cycle: a memory-bound graph-theoretic proof-of-work system, by
> John Tromp
> The point is to require enough memory to make it difficult to compute more
> cheaply up  using GPUs, FPGAs or ASICs.  This is the goal of various
> crypto-coins, such as LiteCoin  and GlobalBoost-Y.  However, these schemes
> are forced to use low memory to enable rapid  block-chain verification.
> Like Cuckoo Cycle, much larger memory sizes can be supported because
> verification of the  proof of work is fast and does not require significant
> memory.  In contrast to Cuckoo  Cycle, this algorithm is simpler and
> verification is done in constant time rather than  O(log(N)).
>   Algorithm:
> For a given initial value, compute H(0 | value), H(1 | value),  H(2 |
> value) ... until we have at least a computation cost, c_cost, initial bits
> of the latest hash value being equal to the initial c_cost bits of some
> previous hash value.  To enable a memory cost,
> m_cost, to be independent of c_cost, require that the prior index be within
> 2^m_cost of the current index.  Verification is done with two calls to H.

I had somewhat similar idea this summer. It may be of interest to you.

Create T[i] table (I've used duplex construction as in SHA-3).
Travers all (i,j) pairs accumulating feedback differently if
MSB(T[i], cost) == MSB(T[j], cost).

I've also used multiplication in Galois field in order to achieve memory
access unpredictability while traversing all indexes and thus performing
the same set of operations. The intent was to keep function constant

Proof of concept implementation and pseudo-code available here:

Powered by blists - more mailing lists