CryptoNight and Cuckoo Cycle

Discussion of math, cryptography, protocol, and features

CryptoNight and Cuckoo Cycle

Postby tromp » Mon Apr 21, 2014 12:24 am

CryptoNight appears to be an improvement on scrypt in several ways:

1) reducing block size from 128 to 16 bytes (according to slow-hash.c source;
i saw claims of 64 byte elsewhere; could you clarify perhaps?) increases the
ratio of random memory accesses vs computation.

2) the continuous re-writing of memory blocks prevents time-memory trade-offs

3) the use of AES encryption favors modern cpus that implement it natively.

How does it compare on verification time, particularly on mobile and other platforms
that have no hardware support for AES encryption? Using 16x more memory than scrypt
suggests that verification could be even slower.

One can achieve instant verifiability together with scalable memory use by
sacrificing non-parallellizability, as demonstrated in my Cuckoo Cycle proof-of-work.
It can require hundreds of MB of memory rather than just 2, making it much more
GPU/FPGA/ASIC resistent. Computation time is truly "dominated by the time spent
accessing memory" (measured at around 65%) as Abadi et al. argued for in their
original proposal of memory-bound functions.
I further conjecture that it doesn't allow for linear tmto.

Finally, parallellizability is limited by the number of threads needed to saturate main
memory with random accesses, which is likely under a 100 (I've not been able
to determine yet). In this regard, Cuckoo Cycle is no worse off than CryptoNight since
the latter can run a 100 instances in parallel using 200MB of main memory, which is not
that much slower (at most twice) than L3 cache.
CryptoNight could well need more threads to saturate main memory since it does more
computation per memory access.

Would you consider this a good alternative to CryptoNight?
tromp
 
Posts: 4
Joined: Sun Apr 20, 2014 11:39 pm

Re: CryptoNight and Cuckoo Cycle

Postby Maurice.P » Fri May 16, 2014 5:50 pm

As far as I understand, you've mentioned that your algorithm requires hundreds of megabytes and is more ASIC-resistant because of that. However, I've noticed the following GitHub note (https://github.com/tromp/cuckoo): "The latest implementation incorporates a huge memory savings proposed by Dave Andersen".

Is there a possibility that a new algorithm requiring even less memory will appear in the future?
Maurice.P
 
Posts: 63
Joined: Wed Mar 26, 2014 3:26 pm

Re: CryptoNight and Cuckoo Cycle

Postby tromp » Tue May 20, 2014 7:21 pm

The "hundreds of MB" applies to the latest implementation that includes the memory savings.
I'm pretty sure that using less than 1 bit per edge causes a superlinear slowdown, for which
I provide some empirical evidence in the whitepaper. Did you read the relevant section?
Of course that analyzes only one possible approach in reducing memory usage.
They're always the risk that an entirely different approach may work.
tromp
 
Posts: 4
Joined: Sun Apr 20, 2014 11:39 pm

Re: CryptoNight and Cuckoo Cycle

Postby tromp » Tue Feb 17, 2015 12:02 am

The latest version of my Cuckoo Cycle whitepaper has been peer-reviewed, accepted, and presented at the BITCOIN'2015 workshop. It includes a new section on time-memory trade-off algorithms, which suggests that such trade-offs suffer at least in order of magnitude penalty in time x memory, rendering
them practically infeasible.

Details at https://github.com/tromp/cuckoo
tromp
 
Posts: 4
Joined: Sun Apr 20, 2014 11:39 pm

Re: CryptoNight and Cuckoo Cycle

Postby Catherine_Erwin » Wed Feb 18, 2015 7:06 pm

tromp wrote:The latest version of my Cuckoo Cycle whitepaper has been peer-reviewed, accepted, and presented at the BITCOIN'2015 workshop. It includes a new section on time-memory trade-off algorithms, which suggests that such trade-offs suffer at least in order of magnitude penalty in time x memory, rendering
them practically infeasible.

Details at https://github.com/tromp/cuckoo


Congratulations!
Cuckoo Cycle is based on solving a certain problem. It requires more memory than computing power that is good. But nobody can guarantee there is no better solution for the problem (better algorithm or quantum computing or something else). Yes, CryptoNight may be optimized for quantum computers too. However in practice hashing algorithms are harder to optimize than, let's say, the discrete logarithm functions. Therefore hashing algorithms are considered to be quantum-resistant, while the traditional cryptography is not.
In general, CryptoNote's approach is more conservative. At the moment Cuckoo Cycle is not essentially better than CryptoNight and the practical comparison of realizations is needed.
Catherine_Erwin
 
Posts: 102
Joined: Wed Mar 26, 2014 3:28 pm

Re: CryptoNight and Cuckoo Cycle

Postby tromp » Thu Feb 19, 2015 6:05 pm

Thanks for the feedback, Catherine. I feel I must point out one inaccuracy though.

Therefore hashing algorithms are considered to be quantum-resistant


This statement is wrong in the following sense.

CryptoNight is an instance of Hashcash with a particular hash-function.
While that hash function itself may resist quantum speedup, the Hashcash problem
of meeting a difficulty threshold yields directly to Grover's quantum algorithm
for search in an unstructured database, letting you search a space of N nonces in
time only O(sqrt(N)).

Meanwhile, a quantum algorithm for speeding up cycle finding in graphs seems unlikely.
tromp
 
Posts: 4
Joined: Sun Apr 20, 2014 11:39 pm

Re: CryptoNight and Cuckoo Cycle

Postby Catherine_Erwin » Fri Feb 20, 2015 2:31 pm

tromp wrote:Meanwhile, a quantum algorithm for speeding up cycle finding in graphs seems unlikely.


I meant "quantum-resistant" in a broad sense. Grover's algorithm in terms of the quantum world is a relatively slow ( there are many other algorithms that are much faster such as Shor's algorithm )

The fact there is no specific algorithm for the particular problem-solving doesn't mean there is no fast quantum algorithm for that or it's hard to invent it. So speaking about unlikeliness of a quantum algorithm for speeding up cycle finding is a bit unsubstantiated.

Idea behind CryptoNight is simple exhaustive search. We believe that it is better to have a concrete process' evaluation than to rely on luck
Catherine_Erwin
 
Posts: 102
Joined: Wed Mar 26, 2014 3:28 pm


Return to Technology

Who is online

Users browsing this forum: No registered users and 2 guests

cron