How does CryptoNight "depend on all the previous blocks"?

Question

Originally, I thought the CryptoNight puzzle was similar to the SHA2 puzzle, with a more exotic hash function replacing SHA2. In other words, the puzzle was essentially H(prev||nonce) < diff, but with H being the slow_hash in the CryptoNote code.

However, the CryptoNote website's description actually says, "As opposed to scrypt, every new block (64 bytes in length) depends on all the previous blocks. As a result a hypothetical "memory-saver" should increase his calculation speed exponentially."

I looked at the mining code, but I couldn't figure out how the puzzle differed from the one I described above. With that in mind, what exactly is the CryptoNight puzzle? How, exactly, does it depend on all the previous blocks (rather than merely the one immediately prior to it) in a way that scrypt does not?

Answer 1

I think the CryptoNote website's page about the egalitarian proof of work is about the inner working of the hash function, not about how the hash of a block is computed (which is basically cn_slow_hash(block_header + tree_hash(block_transaction_hashes)) as you thought).

Internally, the Scrypt function computes blocks of pseudo-random data. Something like:

B0 = SMix(B0, N)
B1 = SMix(B1, N)
B2 = SMix(B2, N)
...

The computation of the next value of block Bi only depends on the current value of Bi, therefore the computations of blocks B0, B1, B2... can be done in parallel.

The CryptoNight function also computes blocks internally, but computing a block depends on the previous blocks. Something like:

B1 = AES_rounds(B0)
B2 = AES_rounds(B1)
B3 = AES_rounds(B2)
...

Therefore the blocks can only be computed one after the other, because computing B5 requires B4, which requires B3, which requires B2, etc.

Description of the CryptoNight algorithm: https://cryptonote.org/cns/cns008.txt