Snippets

nerva-project The CN-Adaptive-v2 Algorithm

Created by nerva-project last modified

The CN-Adaptive-v2 Algorithm

In this document, I will attempt to explain the changes of Cryptonight Adaptive v2 (CN-Adaptive-v2).
A technical understanding of the Cryptonight hash algorithm, NERVAs first algorithm (CN-Adaptive-v1) and C++ programming is assumed.

These changes took effect on the mainnet at height 180000.

Basic Overview

The simplest way I can explain the proposed changes is that the daemon uses block hashes from previous blocks, to generate an unpredictable dataset
which is then used to manipulate the data in the scratchpad. This data manipulation occurs after the scratchpad is first populated with data, before
the AES mixing function is performed.

Detailed Overview

NERVAs hash algorithm, Cryptonight Adaptive (CN-Adaptive-v1) is based on Cryptonight-v1 with the following ammendments:

  • Scratchpad reduced from 2MB to 1MB
  • Reduce AES mixing function iterations from 0x80000 to 0x40000
  • Per block variation of the AES mixing function iteration count between 0x40000 - (0x40000 + 1024)

CN-Adaptive-v2 makes the following changes to v1

  • Reduce AES mixing function iteration variation from 1024 to 64

CN-Adaptive-v2 maintains the basic functionality of v1 and provides a secondary algorithm to manipulate the data in the scratchpad, and resulting hash, further
randomizing the algorithm each block. This data is calculated before the Cryptonight hash algorithm is run and applied to the scratchpad after it is initialized,
directly before the variable iteration AES mixing function.

The scratchpad used in NERVAs hash algorithm is 1MB, or 1,048,576 bytes.
Of that, 32 bytes are manipulated via a non-predictable algorithm, which is calculated at the start of each block. A broad overview of of the steps looks like

  • Get hash of last block
  • Bit shift arbitrary bytes in the hash to generate 4 uint8_t values
  • Read the block hashes at these locations, reading back from the current height
  • Convert the 4 block hashes into a single 128 byte buffer
  • Generate arrays of scratchpad byte indices and randomization values from that buffer
  • Apply that randomization data to the scratchpad buffer

Step 1: Get a list of old block hashes from the blockchain

Step 1 involves fetching the hashes of 4 previous blocks in the blockchain.
The process consists of the following steps

  • Retrieve a previous block hash. In this case we could back 256 blocks as an arbitrary value
  • XOR 4 pairs or arbitrary bytes together to generate 4 new uint8_t values (designated b1 - b4)
  • Retireve the block hash at the height - bytes value. Example: height - b1.
  • Do this for each 4 values

The last block is XOR'd together like so:

01234567890123456789012345678901  
|   |   |   |   |   |   |   |  
b1  b2  b3  b4  b1  b2  b3  b4  

Code:

uint64_t ht = height - 256;  
crypto::hash h0 = bc->get_block_id_by_height(ht);

uint8_t b1 = (uint8_t)(h0.data[0] ^ h0.data[16]);  
uint8_t b2 = (uint8_t)(h0.data[4] ^ h0.data[20]);  
uint8_t b3 = (uint8_t)(h0.data[8] ^ h0.data[24]);  
uint8_t b4 = (uint8_t)(h0.data[12] ^ h0.data[28]);  

crypto::hash h1 = bc->get_block_id_by_height(ht - b1);  
crypto::hash h2 = bc->get_block_id_by_height(ht - b2);  
crypto::hash h3 = bc->get_block_id_by_height(ht - b3);  
crypto::hash h4 = bc->get_block_id_by_height(ht - b4);  

At the end of the first step, we then have 4 block hashes to be used in step 2. By using the last block hash, we have an unpredicatable method of
retrieving block hashes which results in a different set of hashes each block. Also, since the last block hash is not known until the new block
begins mining, there is no was to precalculate the information and all miners get the last block hash at the same time.

There is one drawback to this method however and it is quite significant. Since each block needs the hash of the previous block to calculate the
hash algorithm, blockchains must be synced one block at a time. When attempting to sync more than one block at a time, the previous block hash
is not stored on disk and the hash to verify the block cannot be calculated. This results in longer sync times, and a higher load on nodes
providing the blockchain data. Bootstrap syncing is recommended when using this algorithm.

Step 2: Copy the block hashes to a single 128 byte buffer

In step 2 we convert the 4 32 byte hashes into a single 128 byte buffer. This is done simply by interleaving the 4 hashes together in 4 byte chunks, which can be visualized as

h1 0000            0000            0000
h2 |   1111        |   1111        |   1111
h3 |   |   2222    |   |   2222    |   |   2222
h4 |   |   |   3333|   |   |   3333|   |   |   3333
   |   |   |   |   |   |   |   |   |   |   |   | 
   000011112222333300001111222233330000111122223333....

Code:

int j = 0;
for (int i = 0; i < 128; i += 16)
{
    std::memcpy(cn_bytes + i, h1.data + j, 4);
    std::memcpy(cn_bytes + i + 4, h2.data + j, 4);
    std::memcpy(cn_bytes + i + 8, h3.data + j, 4);
    std::memcpy(cn_bytes + i + 12, h4.data + j, 4);
    j += 4;
}

This buffer is then used to generate a struct random_values in step 3

Step 3: Generate the random values for the algorithm

Now we are at the step where we will generate the random values that will randomize the scratchpad data.
First the layout of the random_values struct (defined in src/crypto/hash-ops.h)

#define RANDOM_VALUES 32

enum {
  NOP = 0,
  ADD,
  SUB,
  XOR,
  OR,
  AND,
  COMP,
  EQ
};

typedef struct randomizer_values
{
  uint8_t operators[RANDOM_VALUES];
  uint32_t indices[RANDOM_VALUES];
  int8_t values[RANDOM_VALUES];
} random_values;

As you may deduce, each array is 32 values long. Each index in these arrays functions in a group
- Scratchpad index - indices[n]: This is the index in the scratchpad the byte manipulation will occur
- Operator - operators[n]: A value in the range of 0-7 corresponding to the enum to determine which function is performed
- Value - values[n]: The operand of the bitwise operation defined by operators[n]

The easiest way to describe what the operators are is with the code

void randomize_scratchpad(random_values *r, uint8_t *scratchpad)
{
    if (r == NULL)
        return;

    for (int i = 0; i < RANDOM_VALUES; i++)
    {
        switch (r->operators[i])
        {
            case ADD:
                scratchpad[r->indices[i]] += r->values[i];
                break;
            case SUB:
                scratchpad[r->indices[i]] -= r->values[i];
                break;
            case XOR:
                scratchpad[r->indices[i]] ^= r->values[i];
                break;
            case OR:
                scratchpad[r->indices[i]] |= r->values[i];
                break;
            case AND:
                scratchpad[r->indices[i]] &= r->values[i];
                break;
            case COMP:
                scratchpad[r->indices[i]] = ~r->values[i];
                break;
            case EQ:
                scratchpad[r->indices[i]] = r->values[i];
                break;
        }
    }
}

After this 32 bytes of the scratchpad are altered, the rest of the Cryptonight algorithm completes.

Summary

CN-Adaptive-v2 strengthens the solo CPU mining goals of NERVA, by making it a requirement to have a local blockchain copy and strenthens
the concept of ASIC resistance via dynamically adjusting the hash algorithm. v1 created 1024 different algorithm variations. v2 expands
that randomization by orders of magnitude. Consider that 32 out of a possible 1,048,576 scratchpad bytes are changed, with each byte changed
in one of 8 possible ways, by one of 256 potential operand values. Furthermore, each of those possible combinations can be performed up to 64
different ways via the variable AES iteration count.

The cost of this however is sync speed. A node blockchain must be synced one block at a time, so that the previous block hash can be read to
generate the required information to randomize the scratchpad. CN-Adaptive-v2 must therefore be accompanied by a bootstrap method of chain
synchronization to speed up synchronization times and improve the end user experience.

It is also important to distinguish that CN-Adaptive-v2 is not exactly a modification to the CN Variant 1 as used by Monero.
CN-Adaptive-v2 creates a secondary algorithm which generates a random dataset that is applied to change the scratchpad buffer to
change the resulting hash produced by Cryptonight. As a result, CN-Adaptive-v2 could be applied to any cryptonight variant that may seek to
promote Solo CPU mining as it's method of distribution.

Please feel free to post any optimizations, questions or comments in the comments below or in the of the NERVA Discord #development channel

Comments (0)