Thanks. I still think you're underestimating the issue. I think you should change it to have a large nonce space much larger than anyone could store in memory so that you have asymptotically linear scaling in terms of RAM.

Could you clarify what exactly you require in order to claim the full bounty?

To clarify, the 50% chance for at least 1 collision for 23 people in your example is with doing n^2 operations, but when you're hashing you check each one against the ones you already have saved each time you add it to the hash table. You're not doing all n^2 operations each time since you've already compared the previous hashes to each other. You're just going n comparisons each time to see if the new hash matches. There's a disconnect between what you describe in your graphs and the actual algorithm. That 50% chance would be after 23 hashes you'd find AT LEAST 1 collision, but miners want to find MULTIPLE collisions which changes the whole scaling.

I like the core idea of using the bday hash to force high memory usage. I think you're idea of saturating the memory bandwidth has promise. I think that with the right parameters you could design mining that would have a very low improvement (perhaps none without the scale of ATI behind it) going to ASICs over GPUs due to GPU optimization of parallel operations and memory bandwidth. You could give CPUs a fighting chance as well since they can leverage high amounts of memory to make up for less raw hashes/memory bandwidth.

Your algorithm as it is though does not scale the way you think it does.

Nathaniel

Here's a proof that your algorithm scales sublinear with RAM i.e. adding more RAM up to the TARGET_RAM_USE actually has slight diminishing returns and even in the asymptomatic case is at best linear in speed up.
Informally, my impression is that you misunderstand what the actual steps in your algorithm look like. Because of the difficulty function, a user wants to find as many BirthdayHash collisions as possible rather than just the first match and each time a new nonce is BirthdayHashed and put into the hashtable it is compared to the others rather than all hashes being compared in one n^2 computation at the end.
I'll reference my original post on the bitcoin forum and quote extensively from it.
https://bitcointalk.org/index.php?topic=313479.msg3365654#msg3365654

Let B = the number of ‘birthdays’ (hashspace of BirthdayHash).
Let S = the number of BirthdayHash(nonce+H) stored in RAM.
Let M = maximum number that S can be given a particular system’s RAM.

If we find a new BirthdayHash(A + H), the expected number of matches ( BirthdayHash(A+H)==BirthdayHash(B+H) ) = S / B

Now we calculate the total number of expected matches during a time frame (average block creation time for instance). we take the number of BirthdayHash() we compute in that time (N). S will increase from 0 to N unless M<N, meaning we do not have enough RAM to store N results, from your comments I gather that you intend for M (TARGET_RAM_USE/(nounce size +hashtable overhead per nounce)) >= N.

N * Mean(S) / B = Total expected matches
If M>=N:
Mean(S) = (1 + 2 + 3 + … + N)/N = (N+1)/2

Now let's see what happens when a user only has M/2 RAM available and M/2<N<=M. To when your challenge I must prove that with M/2 RAM a user would still have at least half as many matches ((N+1)/2)*.5.

For the first M/2 hashes both users produce the same results. Then, the user stuck at M/2 RAM only has M/2 nonces to compare each new one to like this:
(1+2+3 + … M/2 + M/2 + … + M/2) = ((M/2)*(M/2 + 1)/2 + (M/2)*(N-M/2))
The mean then is  ((M/2)*(M/2 + 1)/2 + (M/2)*(N-M/2))/N
Total expected matches for M/2 RAM is (Ns cancel out): ((M/2)*(M/2 + 1)/2 + (M/2)*(N-M/2))/B

(M/2 scenario) ((M/2)*(M/2 + 1)/2 + (M/2)*(N-M/2))/B vs (N*(N+1)/2)/B (N<=M scenario)
Plug in the numbers M = 2^26 nonces worth of RAM, N = 2^26 hashes during the time period since it’s always more efficient to continue hashing until the nonce space is complete to avoid extra cost in rebuild the hashtable of potential matches.
(M/2 scenario)
((2^26/2)*(2^26/2 + 1)/2 + (2^26/2)*(2^26-2^26/2)) /2^50= 1.5000000149
vs,
(M scenario)
(2^26*(2^26+1)/2)/2^50 = 2.0000000298

So in the same time frame with half the RAM, I will find ~1.5 matches vs your ~2 matches your scaling is actually worse than a linear increase when you double the RAM.

Let me know if you have any questions. I suggest you run the empirical experiment yourself if you’re not convinced. Just change the code to stop adding new results to the hash table once you’re half way through the nonce space to simulate halving your RAM.

Hope this helps your design. You can get asymptotically linear increases per RAM increase if you make the TARGET_RAM_USE ridiculously huge like 1TB+.


Thanks,

Nathaniel
16EeLa9BrZc1A4sasztaRdnfp3aU8DmuVC