Autolykos v. 2 details

The goal of this post is to explain and discuss upcoming proof-of-work function change.

Autolykos v.2 is following Autolykos v.1 with pool-resistance switched off and possible ways to bypass memory hardness closed.

Autolykos v.2 is briefly described at ,

main algorithms for verification and proving are below:

and auxiliary genIndexes algorithm is

(takeRight(n, *) is taking least significant n bytes, dropMsb is dropping the most significant byte, so for 32 bytes, dropMsb(…) == takeRight(31, …)).

So basic ideas behind the algo:

  1. Like Autlykos-1, based on k-sum problem, so a miner needs to finds k (k=32) out of N (2^n = 2^26) elements, and hash of their sum must be less than target value (inverse of difficulty)
  2. k indexes are pseudorandom values derived from block candidate and nonce
  3. N elements are derived from block height and constants just, unlike Autolykos v.1, so miners can recalculate block candidates easily now (so only indexes are depending on them)
  4. Indexes calculation also involving the same table (which elements are last 31 bytes of H(i | | h | | M ), where i is in [0, N), h is block height, M is padding to slow down hash calculation (8kb of constant data).

So algorithm trying to make mining efficient for ones who store the table which size is 2^26 * 31 = 2,080,374,784 bytes (about 2GB). Thus algo now is friendly to all the GPUs basically.