[cryptography] High-AT proof-of-work

Elias Yarrkov yarrkov at gmail.com
Sat Jan 19 06:28:39 EST 2013

On Sat, Jan 19, 2013 at 12:20 PM, CodesInChaos <codesinchaos at gmail.com> wrote:
> 1. Run the sequential squaring algo, but only store every 2^{b/4} value.
> This takes around 2^{b/2} time and 2^{b/4} memory (product 2^{b*3/4}
> 2. Run parallel squaring from all checkpoints stored in step 1. Use 2^{b/4}
> small cores, taking 2^{b/4} time, and 2^{b/2} memory (product 2^{b*3/4})
> Cost is something like 2^{b*3/4}

Interesting, but the combined cost of the steps doesn't seem to be correct.

If one were to build a machine to implement both steps, it would take
1. 2^{b/2} time (and a negligible amount of memory)
2. 2^{b/2} memory (for a negligible amount of time)

That machine costs 2^{b/2}, and takes time 2^{b/2}.

In step 1, most of the memory of this machine is wasted. Utilized or not, it
must be constructed to run step 2. If one builds a machine using this approach
to solve a large number of challenges, can it be made useful? I can't think of
a way.

yarrkov -- http://cipherdev.org/

More information about the cryptography mailing list