[cryptography] High-AT proof-of-work

CodesInChaos codesinchaos at gmail.com
Sat Jan 19 05:20:25 EST 2013

A naive implementation has a cost of 2^b: Using memory m it takes time
(2^b)/m keeping the product constant. These trade-offs are harmless.

A more sophisticated implementation is:

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}

That's significantly more efficient than what you can run on a standard PC
which cannot run step 2 quickly. Depending on the cost of memory vs. cores
the optimal tradeoff might not be 2^{b/4}, but the idea is the same.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20130119/f20c23fa/attachment.html>

More information about the cryptography mailing list