Following up on
this thread, I went back and looked at Tromp's
Cuckoo Cycle, dga's
response, and
Momentum. A commenter suggested investigating k-SUM (also known as the
Subset sum problem) as the basis for a PoW.
So here's what I've come up with:
1. Let d be the current difficulty
2. Let k be the number of hashes to SUM
(k-SUM(hash(block, nonce)) % d) == 0This function has the following properties:
1a. In 2-SUM,
memory increases linearly as d increases (since d/2 hashes are stored on average until you find (hash_stored + hash_current) % d == 0).
1b. In 3-SUM,
memory increases quadratically d increases (there are solutions that claim
subquadratic execution reduction but none that claim subquadratic memory reduction, which is what we care about for ASIC/FPGA resistance).
1c. Generalized, we end up with a d^k memory requirement.
2. A
verifier only needs constant memory, since they only have to check the k submitted nonce values.
3. It is easy to understand and implement, and there is a massive body of work around k-SUM.
4. It fits easily into existing infrastructure as the hash function could very well be SHA256d.
4a.
Bitcoin's PoW can be generalized in terms of k-SUM:
- SHA256d(block, nonce) < Target is essentially equivalent to 1SUM(SHA256d(block, nonce)) % d, as d ~= Target/Max_Target, with a starting d value of 2^32.
5. Simpler than anything else I've seen proposed so far.
Setting aside whether people think an ASIC/FPGA resistant PoW is a good thing, I'd like to put this one out there for folks to pick apart.
Thoughts?
