Interesting idea...

But your analysis seems wrong.

With O(sqrt(d)) hashes you can form O(d) different 2-SUMs, and expect a solution,
just like with the birthday paradox.

For 3-SUM, O(d^{1/3}) hashes using O(d^{2/3}) memory should suffice.

Cuckoo Cycle verification checks that k nonces form a cycle on k hash values;
I'd say that's comparably simple (with no need for modular arithmetic).

When considering modulus by d, I did so because modulus by a fixed value has pretty well known optimizations.


I don't think this is an instance of the birthday paradox as we're not trying to find collisions (like in Momentum), rather we're trying to find a subset sum where P is large.

The number of unique subsets is d choose k.  To make things concrete let d = 16, sqrt(16) = 4, so 4 hashes picked.  Assume all are unique values and the sums don't collide. We can get all possible 2-sums of the 4 hashes via 4 choose 2 or 6.  

If O(sqrt(d)) gave us O(d) different 2-SUMs, then we'd expect for 4 hashes to get 16 unique 2-SUMS, but instead we have 6.

Am I off here?  How are you getting O(sqrt(d))?

To be clearer, the PoW I'm suggesting is:

SUM = 0;
for (i to k) {
  SUM += hash(block, nonce{i});
}
return (SUM % d) == 0;

Collisions make it less likely that values will be found, not more likely.


EDIT: Going in to this, I did read your paper and momentum first - the multi-nonce submission was inspired from your work.  Structurally one can think of kSUM as a form of graph generation; every unique number hashed adds a fully connected vertex, but the edges have weights; find a path of weight d and length k.

An interesting topic, I will keep an eye on.

It wasn't obvious to me how you were getting your O estimate of O(sqrt(d)) - I get that it represents complexity as d approaches infinity.


If I rephrase this,

2*sqrt(d) * (2*sqrt(d)-1) / 2 == Choose(2 * sqrt(d), 2) == 2*d-sqrt(d)

O(2*d - sqrt(d)) == O(2*d - d^{1/2}) == O(d)

However concretely we also know that we have to sample d/2 unique hashes before we are guaranteed a 2SUM solution - also O(d).

So I *think* we're agreeing, but are taking different routes to the destination.  Were you referring to O(sqrt(d)) before applying Choose, or something else?  I agree that d/2 hashes on average was incorrect - it should have been d/2 hashes worst case - I'll need to do a bit more thorough complexity analysis.



Separately - I'd like to dig deeper into making this progress-free, as right now I think both a modified kSUM and Cuckoo Cycle suffer from the same thing:

Consider if one adds a final hash step construction to kSUM similar to Cuckoo Cycle:

HASH(concat(nonce{i})) <= Target

Such a construction really just constrains the domain to the nonce range.  It's not obvious how adding the final HASH < Target buys anything for either kSUM or Cuckoo Cycle and may be a vector for simplification.  I say this because one can arbitrarily pick nonces from potentially many partial solutions for a nonce range, and the likelihood of a partial solution gets greater as both kSUM and Cuckoo Cycle populate their sets/graphs.

Yes, while thinking about the design of memory-hard functions I realized there is a hard tradeoff here:

1. Progress-Free (scrypt; i.e. sequential memory hard)
2. Fast-To-Verify (cuckoo, ksum, momentum)

The Momentum paper somewhat identifies the mechanism in #2 indirectly by calling out the necessity of independent intermediate solutions as being required for fast verification.  The very presence of independent intermediate solutions implies "progress" since they are remembered in order to construct a result solution.

Based on this, an ideal Fast-To-Verify memory-hard PoW would forces a 1:1 mapping between intermediate results and input domain values.  An optimal one would only do this.

Does this sound like a correct design goal?

How are you defining an attempt?  If it is a single nonce range scan then we agree.  I was referring to progress as state within a nonce range scan.

OK - there isn't any fundamental disagreement then.

So the first thing I'd assert is any value of d should be a power of 2.  The reasoning being it avoids biasing any k-SUM when applying modulo d.  A convenient side benefit is the modulo can be done via bit mask.

3SUM is interesting because it's relatively prime with any power of 2 that could be d.  Also it simplifies discussion because we know the addition of the 3rd number "shifts" the target.  

I.e. for SUM2 we have

(k-SUM(hash(block, nonce)) % d) == 0  

and for SUM3 we roughly have

(k-SUM(hash(block, nonce)) % d) == -(3rd value % d)

However, the extra input in 3SUM doesn't really achieve much, and actually works against us complexity wise.  In normal 3SUM the domain is +-Infinity, but here it is GF(d), and by wrapping around at d we know once we pick a term, we have a 1/d chance the sum of whatever is chosen for all additional terms will "wrap us around" back to 0 and yield a solution.  Plus, we can then reuse any items found as part of the solution for any other item.  It's relatively intuitive to extend this reasoning from 3SUM to kSUM.

Net: k should == 2 like you hinted at earlier, at least in this construction, since > 2 doesn't buy us anything.

I also pondered an alternate construction to try to mitigate the wrap-around effect of GF(d):

(k-SUM(hash(block, nonce) % d)) == 0  

Here we apply modulus before k-SUM (assume the MSB of hash is a sign bit here since we don't have modulo wrap-around), but this has the adverse effect of making values closer to zero more valuable.  I.e. if k=3, d=8, and you draw a 7, you can form far fewer solutions than if you had drawn a 1 due a lack of an outer modulus.  So this alternate construction is out.


Incorporating your observation that 2SUM is roughly equivalent to Momentum complexity wise, I went back to the drawing board...


Taking the original 3SUM construction, I realized a significant source of weakness was the lack of ordering.  If we change the construction to something like:

SUM(
  hash(block, key0, nonce0),
  hash(block, key1, nonce1),
  hash(block, key2, nonce2)) % d == 0

(key0, key1, and key2 are unique/different)

Then it becomes much harder memory-wise.  Since we've established the average memory requirements for 2SUM are O(sqrt(d)), and we know 3SUM can be re-expressed as 2SUM(hash0, 2SUM(hash1, hash2)), 3SUM in this form should have complexity of O(sqrt(d)) * O(sqrt(d)) = O(d) average case, with a worst case of O(n^2).  Such a massive variance in potential memory use is interesting, but I would expect a miner to optimize for the 50% case at sqrt(d).  Assuming this is correct, it's pretty neat that we could tie the average memory usage linearly to d.


What do you think?  Does this construction seem correct/more robust?

Agree the upper bound on running time is O(n^2), but isn't the expected running time O(n)?  We know the time to lookup h_i and h_j is O(1), and expect to find a collision 50% of the time in O(sqrt(n)).  I'm using the assumption that d == n.