Technical implementation of a memory hard hash block in Dynamo Coin proof of work algorithm

Introduction

Dynamo coin is designed to be a memory hard, ASIC proof, hybrid proof of work/proof of stake crypto currency. The current evolution of the proof of work algorithm allows for rapid deployment of new programmatic hash algorithms, albeit via a manual process. Several upgrades are currently planned for the hash algorithm. The current iteration involves making Dynamo proof of work memory hard and increasing the minimum memory requirement to 3GB.

Memory hard proof of work algorithm

Memory hard algorithms require lots of memory. It is impractical to regenerate large amounts of memory each block with current consumer hardware. Therefore, Dynamo will adopt an “epoch” generation procedure based on some number of sequential blocks. Every N blocks, a new chunk of a large amount of memory will be generated from a hashing algorithm. The only input into the hash block generation algorithm will be the block number, therefore all possible future blocks can be generated ahead of time. This is important to avoid large fluctuations in hash rates during epoch transitions.

The current implementation contemplates a fixed memory block of 3GB which will not grow over time. This will allow older generation hardware to mine Dynamo, thereby increasing the mining user base and overall decentralization.

The initial design will use an epoch time of 10,000 blocks. Each block # that is an even divisor of 10,000 will use a new hash block. Miner developers should include code to pre-generate upcoming hash blocks so as to avoid stalling hash rates.

The hash block will be built as two parts — a small seed block and the main hash block. The seed block and main hash block will be used by mining clients to solve the proof of work hash and by full nodes to validate submitted blocks. The generation of the main hash block will be sequential, such that the work required to derive a random location in the main block would severely handicap any mining client which attempted to simply compute values instead of deriving the entire block and reading them from memory.

Seed block generation

Experimental — subject to change

The seed block is created from the SHA 256 of the previous epoch block number plus the SHA 256 of the block height. The seed of block 0 is defined as:

B33C85B3A015E0108F541A460E3F2CC59D1B4E99A26B7639E502CA6E066A5097

1. Start with a 256 bit seed based on the SHA256 of the previous seed
2. Generate 3072 initial lane seeds with successive SHA 256
3. For each initial lane seed, calculate the PBKDF2 hash of the lane seed using the block seed as the salt and store this as the final lane seed. Use 1000 rounds.

Main block generation

Experimental — subject to change

The main block is generated in 3072 “lanes” comprised of 1MB per lane, organized as 32768 256 bit hashes, for a total of 3GB of main block memory. Conceptually, the main block can be thought of as a grid of 3072 rows and 32768 columns. The algorithm to generate each 256 bit hash is sequential, so that it is computationally expensive to generate any random hash on the fly.

1. Starting with the initial lane seeds from the seed block, each row is generated by taking successive SHA256 hashes.
2. After generating all rows, the value in each column is added to the value in the row below it and the SHA 256 of the sum is taken and stored in that cell. For the last row of each column, the value is summed with the value in the first row of the next column. For the hash in the last row and column, the value is summed with the value in the first row and column.
3. For each row, calculate the PBKDF2 hash on a sliding one byte window starting with the last 32 bytes and moving toward the first byte of each row, one byte at a time. Use the lane seed as the salt. Use 100 rounds.

Note: it is not expected that the seed block can be used to quickly verify any given random hash. Full nodes will need to calculate the main block in order to rapidly verify submitted blocks.

Additional OPCODES to make use of the main block

SUMBLOCK

This opcode will use the current intermediate hash as an index into the main hash block. The index is calculated by splitting the intermediate hash into 2 64 bit unsigned numbers, and then taking the mod 3072 and mod 32768 of those numbers to use as a row/column index. The opcode will then add the next successive 256 bytes of data from the main hash to the current interim hash. If the index exceeds the 3GB boundary the index will wrap to 0.

Economic rationale for memory hard algorithms

Memory hard algorithms help to deter development of ASIC mining hardware. As is well documented elsewhere, ASIC mining leads to centralization due to supply chain issues and cost of capital.

Memory hard algorithms make CPU mining much less efficient than GPU mining due to the much more efficient memory access of consumer GPU units. CPU based mining suffers from centralization due to ease of access to hosted VMs (AWS, GCD, Azure) and also suffers from vulnerability to VM account takeover bots or zombie attacks.

Finally, memory hard algorithms are well suited for consumer grade GPUs, which attracts small and medium sized investors who become financially attached to the project due to cost of capital and implied ROIs.

Conclusion

This paper presents the first draft of an extension to the Dynamo Coin proof of work algorithm which will introduce a procedure for calculating a 3GB hash block and an associated opcode which will read blocks of memory from that hash block. This implementation will further enhance the security of Dynamo Coin by deterring development of ASIC devices and reducing the efficiency of CPU miners.