Autolykos v. 2 details

[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:

  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 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.