[Significantly updated on Dec, 24th, 2020]

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

Autolykos v.2 is following Autolykos v.1, but with certain modifications made:

- non-outsourceability switched off. It turns out (based on more than 1 year of non-outsourceable PoW experience) that non-outsourceable PoW is not attractive to small miners.
- now algorithm is trying to bind an efficient solving procedure with a single table of ~2 GB (initially), which is significantly reducing memory optimizations possibilities
- table size (memory requirements of a solving algorithm) grows with time
- now table is depending on block height only, so there is no penalization for recalculating block candidate for the same height

Autolykos v.2 is briefly described at ErgoPow.pdf | DocDroid ,

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:

- 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) -
*k*indexes are pseudorandom values derived from block candidate and nonce -
*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) - 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 initially (about 2GB). Thus algo now is friendly to all the GPUs basically.

Also, table size (N value) is growing with time as follows. Until block 614,400, N = 2^{26} = 67,108,864 elements (31 bytes each). From this block, and until block 4,198,400, every 51,200 blocks N is increased by 5 percent. Since block 4,198,400, value of N is fixed and equals to 2,143,944,600. Test vectors for N values are provided in the paper.