Aion equihash_210_9 specification and migration guide.
The AION PoW protocol is based on the Equihash algorithm; a memory hard PoW algorithm solving the Generalized Birthday Problem. The original Equihash algorithm developed by Alex Biryukov and Dmitry Khovratovich may be found here.
Memory hard problems feature several properties which make the ASIC resistant:
-
Large memory usage (relative to CPU on-chip memory). This forces the algorithm to access system memory resulting in memory bandwidth acting as the upper bound on algorithm run time.
-
Ineffective CPU - memory trade off. Traditionally CPU cycles and memory usage may be traded to offset one resource by another; Equihash is resistant to this type of trading by exponentially increasing CPU cycles when attempting to trade CPU cycles for memory usage.
AION uses a modified version of the Equihash solver developed by John Tromp; the original version may be found here.
The core challenge of Equihash is to find a complete binary tree of 2k indices (X values) such that the XOR of the hashes of indices (along with block header and nonce) is equal to 0. Additionally the following conditions must be met:
For each height subtree, the XOR of its 2i leaf hashes must start with i*n 0 bits.
The leftmost leaf of any left subtree is less than the leftmost leaf of the corresponding subtree.
This document serves as a migration and development guide detailing changes required to convert the Tromp solver to generate solutions to the AION PoW protocol. This document assumes a working knowledge of the Equihash algorithm as well as the Tromp Equihash solver. The reference implementation has been purposely left in a simplified and rather verbose state ensuring each algorithm step is clearly outlined.
The Equihash algorithm takes two integers N and K where N specifies the width in bits which must XOR to 0 while K specifies the number of steps in which the computation takes place.
In addition to Equihash algorithm parameters a personalization parameter is added to Blake2b. The personalization parameters ensures the digests computed are unique to AION. Given the same inputs to a non-AION Blake2b algorithm, the digests produced are guaranteed to be different.
The AION implementation of the Equihash algorithm uses parameters N = 210, K = 9, increasing the computational difficulty of the AION PoW as compared to popular existing Equihash implementations. One of the notable effects of changing to Equihash parameters is increased memory usage; at a minimum the amount of memory has been more than doubled from 144 MB to 300 MB based on some set of experimental parameters though the reference implementation uses over 500 MB.
The personalization parameter adds an additional layer of security by ensuring unrelated hash computations both within and outside of the AION kernel may not be used in the PoW process.
The personalization used in the current implementation is 16 bytes equal to "AION0PoW" + N + K where N and K are integers in little endian byte order.
The Tromp Equihash solver uses a two-stage bucket sort during its solution generation process; the number of bits to be processed in each sort are defined by two variables; RESTBITS and BUCKBITS. The values of RESTBITS and BUCKBITS must sum to DIGITBITS where . This document presents algorithm details where BUCKBITS = 14 and RESTBITS = 7.
Following the Tromp solver Equihash solver; the AION solver produces Equihash solutions by processing digests in K+1 steps. These steps may be broken up into 3 primary groups referred to as “Digit X”.
Digit 0 is responsible for generating the hashes and produce solution indices and to perform the first bucket sort based on the first BUCKBITS.
Input to the Blake2b algorithm is as follows: H(x) = H(BlockHeader) + nonce + X
-
H(BlockHeader) - A 32 byte hash of the current blocks block header (excluding nonce and solution) using default Blake2b settings with no personalization values.
-
nonce - a randomly generated 32 byte value
-
X - Hash index
When generating hashes, a 64 bye hash is generate by the Blake2b hashing algorithm. Next the hashes are split into J byte segments L bytes long where and
. ** Calculations are performed using integer division. In the case of N=210 and K=9, generated 64 byte hashes are split into J=2 segments, each segment L=27 bytes long.
Generated hashes are then sorted into buckets based on the first BUCKBIT bits; the actual number of bytes stored is determined by examining the number of bytes remaining to be processed. Table 1 shows the number of bytes to be stored at each step, subsequent sections explain how the tables values are calculated.
Digits 1 through 8 perform largely the same function and are grouped together. Each step performs two functions; first all pairs of hashes in each bucket are XORed to calculate the next set of collisions over the next RESTBITS. Next, the hashes must be stored in buckets for the following step. In order to calculate the bucket in which to store the hash for the next step, each pair of hashes is XORed, the next bucket ID calculated based on the XOR of the next BUCKBIT bits. Bit usage at each step is shown in figure 1.
Digit 9 is the final step in producing candidate Equihash solutions. First pairs with collisions on the last RESTBITS are found. Next, collisions on the last DIGITBITS of each pair are found, if the final set of DIGITBIT collisions are found to be 0 a candidate solution has been found. Each candidate solution is then processed to ensure it meets all remaining Equihash conditions; as these conditions have not changed with the parameter change they will not be covered in depth within this document. The steps to process candidate solutions are largely unchanged from the original Tromp solver, though hash byte lengths have change the number of bytes processed in each validation step.
One minor change to the validation procedure is in the final step verifying byte 27; as only the leading 2 bits are included in the calculation bit shift operations are used to isolate these bits while the remaining 6 bits are discarded.
Each step must process of portion of the hash; DIGITBITS bits long. Due to the asymmetry in processing of the 210,9 parameters, the bits to process in each step must be calculated individually. Figure 1 shows the bits to be processed at each step. The prevbo parameter within the implementation tracks the starting byte to process at each step; thus following figure 1 the appropriate bitshift operations are applied to isolate and XOR DIGITBITS at each step.
Figure 1. Bit shift operations.
In order to reduce the total amount of memory used the Equihash solver attempts to minimise the number of bytes stored at each step, excluding bytes processed in previous steps. Stored hashes are reduced in chunks of 4 bytes.
The number of bytes remaining to be processed is shown in table 1, the hash bytes values at may be calculated by subtracting the total number of bytes processed after that step from the total length of the hashed bytes.
Eg. Calculating Hash bytes for digit 1
Referring to figure 1 the total number of bytes processed after digit 1 is 4; following the calculation 27-4= 23 bytes.
Table 1
| Digit | Hash bytes |
|---|---|
| 0 | 26 |
| 1 | 23 |
| 2 | 20 |
| 3 | 18 |
| 4 | 15 |
| 5 | 13 |
| 6 | 10 |
| 7 | 7 |
| 8 | 5 |
| 9 | 0 |
As with existing Equihash implementations the format of the solutions generated is an array of 2k integers representing the indices of the solution hashes. Solutions are encoded using the I2BS (Integer to Bit String) as with existing Equihash implementations however the increased size of the solution index also results in an increase in the encoded solution size. Existing implementations use 21 bits (2k+1 possible index values) when representing each solution index saving 11 bits at each encoded integer ultimately resulting in an encoded size of 1344 bytes. The AION implementation also uses the I2BS encoding however 22 bits must be used to represent each integer, saving 10 bits per integer and resulting in an encoded solution size of 1408 bytes. The actual conversion process follows the existing Equihash solution conversion process and is not covered in detail within this document.
N = 210
K = 9
Personalization: "AION0PoW" + N + K (N & K in little endian byte order)
DIGITBITS = 21
BUCKBITS = 14
RESTBITS = 7
Header Length = 496 bytes
Nonce Length = 32 bytes (Little endian byte order)
Encoded Solution size: 1408 bytes