I have been thinking about ways to restore Momentum to a memory-hard problem and have had an insight that I believe changes the game.
Lets define a Birthday to be 1 MB of 'random data' that is relatively expensive to calculate and seeded with a nonce
Lets define a Collision to be the number of bits in common between two random sequences.
The goal is to produce two nonces such that the number of bits in common between the two 1 MB sequences is above some threshold.
The cost of validation is populating 2 MB of memory, performing an XOR, and then a population count.
Now lets populate the memory with AES which has hardware acceleration on CPU but not GPU
The population of the memory is sequential which helps eliminate memory bus latency and allows the CPU to saturate the BUS. A GPU would have an advantage in the comparison step because it could compare all birthdays with the new birthday in parallel. That said, a GPU would be limited in parallelism because it could only store 1000 or 2000 birthdays at a time. Even so I am not convinced that a GPU implementation would be a bad thing given the other changes we are making.
This proof is slightly harder to validate, but most of the optimization techniques used to accelerate Momentum 1.0 would not scale as well with this system and an ASIC would still require a very large amount of memory.
What do you all have to say?