5.2
 The proposed algorithm
We propose a new memory-bound algorithm for the proof-of-work pricing function. It relies on
random access to a slow memory and emphasizes latency dependence. 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.
Our algorithm requires about 2 Mb per instance for the following reasons:
1. It fits in the L3 cache (per core) of modern processors, which should become mainstream
in a few years;
2. A megabyte of internal memory is an almost unacceptable size for a modern ASIC pipeline;
3. GPUs may run hundreds of concurrent instances, but they are limited in other ways:
GDDR5 memory is slower than the CPU L3 cache and remarkable for its bandwidth, not
random access speed.
4. Significant expansion of the scratchpad would require an increase in iterations, which in
turn implies an overall time increase. “Heavy” calls in a trust-less p2p network may lead to
serious vulnerabilities, because nodes are obliged to check every new block’s proof-of-work.
If a node spends a considerable amount of time on each hash evaluation, it can be easily
DDoSed by a flood of fake objects with arbitrary work data (nonce values).

Moreover, the scrypt construction itself allows a linear trade-off between memory size and
CPU speed due to the fact that every block in the scratchpad is derived only from the previous.
For example, you can store every second block and recalculate the others in a lazy way, i.e. only
when it becomes necessary. The pseudo-random indexes are assumed to be uniformly distributed,
hence the expected value of the additional blocks’ recalculations is 12 · N , where N is the number
of iterations. The overall computation time increases less than by half because there are also
time independent (constant time) operations such as preparing the scratchpad and hashing on
every iteration. 
...
This in turn implies that a machine with a CPU
2200 times faster than the modern chips can store only 320 bytes of the scratchpad.

#define MEMORY         (1 << 21) /* 2 MiB */
#define ITER           (1 << 20)
#define AES_BLOCK_SIZE  16
#define AES_KEY_SIZE    32 /*16*/
#define INIT_SIZE_BLK   8
#define INIT_SIZE_BYTE (INIT_SIZE_BLK * AES_BLOCK_SIZE)

...

void cn_slow_hash(const void *data, size_t length, char *hash) {
  uint8_t long_state[MEMORY];
  union cn_slow_hash_state state;
  uint8_t text[INIT_SIZE_BYTE];
  uint8_t a[AES_BLOCK_SIZE];
  uint8_t b[AES_BLOCK_SIZE];
  uint8_t c[AES_BLOCK_SIZE];
  uint8_t d[AES_BLOCK_SIZE];
  size_t i, j;
  uint8_t aes_key[AES_KEY_SIZE];
  OAES_CTX* aes_ctx;

  hash_process(&state.hs, data, length);
  memcpy(text, state.init, INIT_SIZE_BYTE);
  memcpy(aes_key, state.hs.b, AES_KEY_SIZE);
  aes_ctx = oaes_alloc();
  for (i = 0; i < MEMORY / INIT_SIZE_BYTE; i++) {
    for (j = 0; j < INIT_SIZE_BLK; j++) {
      oaes_key_import_data(aes_ctx, aes_key, AES_KEY_SIZE);
      oaes_pseudo_encrypt_ecb(aes_ctx, &text[AES_BLOCK_SIZE * j]);
      /*memcpy(aes_key, &text[AES_BLOCK_SIZE * j], AES_KEY_SIZE);*/
      memcpy(aes_key, state.hs.b, AES_KEY_SIZE);
    }
    memcpy(&long_state[i * INIT_SIZE_BYTE], text, INIT_SIZE_BYTE);
  }

  for (i = 0; i < 16; i++) {
    a[i] = state.k[     i] ^ state.k[32 + i];
    b[i] = state.k[16 + i] ^ state.k[48 + i];
  }

  for (i = 0; i < ITER / 2; i++) {
    /* Dependency chain: address -> read value ------+
     * written value <-+ hard function (AES or MUL) <+
     * next address  <-+
     */
    /* Iteration 1 */
    j = e2i(a, MEMORY / AES_BLOCK_SIZE);
    copy_block(c, &long_state[j * AES_BLOCK_SIZE]);
    oaes_encryption_round(a, c);
    xor_blocks(b, c);
    swap_blocks(b, c);
    copy_block(&long_state[j * AES_BLOCK_SIZE], c);
    assert(j == e2i(a, MEMORY / AES_BLOCK_SIZE));
    swap_blocks(a, b);
    /* Iteration 2 */
    j = e2i(a, MEMORY / AES_BLOCK_SIZE);
    copy_block(c, &long_state[j * AES_BLOCK_SIZE]);
    mul(a, c, d);
    sum_half_blocks(b, d);
    swap_blocks(b, c);
    xor_blocks(b, c);
    copy_block(&long_state[j * AES_BLOCK_SIZE], c);
    assert(j == e2i(a, MEMORY / AES_BLOCK_SIZE));
    swap_blocks(a, b);
  }

  memcpy(text, state.init, INIT_SIZE_BYTE);
  for (i = 0; i < MEMORY / INIT_SIZE_BYTE; i++) {
    for (j = 0; j < INIT_SIZE_BLK; j++) {
      /*oaes_key_import_data(aes_ctx, &long_state[i * INIT_SIZE_BYTE + j * AES_BLOCK_SIZE], AES_KEY_SIZE);*/
      oaes_key_import_data(aes_ctx, &state.hs.b[32], AES_KEY_SIZE);
      xor_blocks(&text[j * AES_BLOCK_SIZE], &long_state[i * INIT_SIZE_BYTE + j * AES_BLOCK_SIZE]);
      oaes_pseudo_encrypt_ecb(aes_ctx, &text[j * AES_BLOCK_SIZE]);
    }
  }
  memcpy(state.init, text, INIT_SIZE_BYTE);
  hash_permutation(&state.hs);
  /*memcpy(hash, &state, 32);*/
  extra_hashes[state.hs.b[0] & 3](&state, 200, hash);
  oaes_free(&aes_ctx);
}

state = hash(header)
do 2^32 times {
  interpret state as 16 pairs (i,v) of 32-bit values; for each pair set mem[i] := v
  state = hash(state)
  interpret state as vector of 32 bit indices; mix in all 32 mem[i]
  state = hash(state)
}