I’m starting this topic to summarize the ideas from our discussion with Photon and to have a public place where anyone interested in the topic can share his ideas.
1.) My main motivation is that modern CPUs already have hardware implementation of the AES encryption rounds (so called Intel AES-NI instruction set; supported by most desktop and server CPUs since ca. 2010. ARM CPUs found in mobile devices have similar instruction set). You can see it as an AES ASIC of sorts.
Compared to AES, the current hash function used to generate the cuckoo graph, Siphash-2-4 doesn’t have hardware implementation on common CPUs and its not expected that there would be one in the near future (if ever).
2.) Which AES scheme? AES-NI provides HW implementation of AES-128 encryption round. The standard prescribes 10 rounds with specific round keys generated from the 128 bit wide AES key. There are few open questions here.
Since we currently use 256 bit key to encrypt each vertex index in the graph (to generate each of the directed edges), how do we convert it to the 128 bit key used by AES-128?
How many rounds are necessary for our purposes? According to the AES design proposal, (128 bit block/key length): “Two rounds of Rijndael provide “full diffusion” in the following sense: every state bit depends on all state bits two rounds ago, or, a change in one state bit is likely to affect half of the state bits after two rounds.”
3.) What is the possible gain? My first experiments showed roughly halved time with 7 AES encryption rounds on the lean miner compared to Siphash on a CPU where we have the advantage.
Photon has been testing on GPU using highly optimized software AES code (from a Cryptonight miner) and found 70 ms time to generate edges using 4 AES rounds vs 60 ms for siphash-2-4. Increasing the number of rounds gives linear increase in the time needed – 102 ms for 6 rounds and 170 ms for 10 rounds. So AES with lower rounds count is competitive even on GPUs.
That’s all that comes to my mind so far. Your questions and ideas are welcome!