Quote from: bytemaster on October 19, 2013, 06:42:06 pm

The point of Scrypt was to make parallel operation difficult and its primary weakness is that validation time suffers as you scale it.

If you don't require that the first match in the sequence of generated pseudo-random numbers, then my upthread described parallelism attack works to allow GPUs to blow away CPUs, assuming the pseudo-random sequence can be generated much faster than the random memory latency bound on the CPU so the GPU can try 100s of values from the same pseudo-random sequence in parallel to hide the memory latency.

If you do require it, then you lose the fast validation time.

Do you get it now or you going to continue to ignore me?

I expended the time to explain this in more detail:

https://bitcointalk.org/index.php?topic=325261.msg3520992#msg3520992

I think that is the last effort I will apply to this.

Ok, lets do this on a GPU..... I have found through experience that theoretical gains on the GPU often do not pan out as you expect.   So I need to see an implementation.

Your bounty only called for showing it is NO BETTER than Scrypt. I already did. I don't have to prove it is much faster on the GPU (but it will also be, yet that is irrelevant to how you stated your bounty).

If you choose to blissfully ignore what has been revealed to you, then so be it. I love it if you go down the wrong road. Please do. Worth much more to me than the $5000.

Your original bounty didn't ask for an implementation. And $5000 doesn't buy enough time from me.

It is up to you how far you want to go down the wrong road.

There is no way to make CPU-only and fast verification. I realized that recently in analysis and research. I realize this is big problem for your coin design.

The point of Scrypt was to make parallel operation difficult and its primary weakness is that validation time suffers as you scale it.

If you don't require that the first match in the sequence of generated pseudo-random numbers, then my upthread described parallelism attack works to allow GPUs to blow away CPUs, assuming the pseudo-random sequence can be generated much faster than the random memory latency bound on the CPU so the GPU can try 100s of values from the same pseudo-random sequence in parallel to hide the memory latency.

If you do require it, then you lose the fast validation time.

Do you get it now or you going to continue to ignore me?

Quote from: AnonyMint on November 06, 2013, 09:36:12 pm

Quote from: bytemaster on November 06, 2013, 06:05:10 pm

While the GPU can hide latency it cannot change bandwidth and your bandwidth usage is still N^2.

Memory bandwidth is several times faster on the GPU than CPU and you won't get close to saturating memory bandwidth on the CPU because the full random memory access latency is too high and you can only run at most 8 threads on a core i7 thus unable to hide the latency entirely. Software threads above that 8 count don't matter.

Your constant time hardware gains in memory bandwidth and parallelism are combating a N^2 algorithmic disadvantage.    It may be possible to develop a GPU based solution, but how much faster it will be is TBD... will it be 10x faster?  I don't think so.

Why do you assume the GPU can't use a hash table also?

Ok... a few corrections for you to consider.   The address space of the birthdays is 50 bits.   The TARGET_MEMORY is the number of birthdays that must be stored to have a 90+% probability of finding 1 collision once you have filled TARGET_MEMORY.    As a result, this isn't sparse memory access unless you are operating on some MULTIPLE of the TARGET_MEMORY.

Correct that by using a hash table it is no longer physically sparse, so CPU and GPU only need to have the target physical memory. So thus the birthday aspect is useless except for causing the collisions on the serial hash bucks.

Your GPU algorithm is still O(C * N^2) where C is some constant factor improvement.
CPU algorithm is O( C * N )

While the GPU can hide latency it cannot change bandwidth and your bandwidth usage is still N^2.

Only if you assume the GPU can't use a hash table too. I see no reason for that to be the case, and as I wrote in my prior post. And I expect the collisions to be irrelevant. If that last sentence is the only one that is in contention, I can explain more?

Also re-read my prior post, I added to it.

Okay if I understand correctly your proposed PoW algorithm, we are generating pseudo-random values that can range over the address space of the memory size we target until we generate a duplicate (or triplicate). The Birthday math tells us that we will find a solution with 50% probability before visiting less than roughly 10% of the addresses, or 99% before visiting less than roughly 20% of the addresses. Thus this is a way to require large memory without actually writing to every memory address, i.e. a sparse memory access algorithm. Btw, I also considered this sort of algorithm before and dumped it.

Assuming the generation of the pseudo-random values can be accelerated by parallelism, i.e. that the algorithm is main memory latency bound, then the GPU is going to be much faster, because the GPU masks memory latency by employing 1000s of threads, i.e. we can test 1000s of pseudo-random values in parallel. This was the key myopia that caused Litecoin to fail at stopping GPUs from outperforming CPUs, although it did improve the difference relative to Bitcoin's PoW.

I don't see how the use of a hash table really changes the outcome significantly, as it will only serialize perhaps every 10 buckets and we assume the pseudo-random values are uniformly distributed over the entire address space. Collisions with a 1000 threads are going to be rare.

I have revealed my key insight into PoW. If you weren't aware of this and I am correct, I hope you tip me consumerately regardless if it leads you to make changes or not (I should not be responsible for your success, only for proving what doesn't work).

Edited: to insert word "not" after "I should" that was missing.

For example:  Suppose momentum as specked requires about 1 GB of RAM for maximum performance and produces hashes at 1hz.   If you design an algorithm that only requires 1 MB of RAM and can find hashes at .001 hz then you win because you will have proven that computational complexity is linear with RAM use rather than non-linear like I believe the problem calls for.   

Best of luck to you all!

I believe there is a weakness where GPUs can run much faster, but it doesn't requiring lowering the memory. If I explain it to you and am correct, do I qualify for at least part of the bounty?

It is possible I am incorrect or have misunderstood some aspect of the algorithm, so let's not jump to conclusions yet.