ifdefelse / ProgPOW

A Programmatic Proof-of-Work for Ethash. Forked from https://github.com/ethereum-mining/ethminer
GNU General Public License v3.0
257 stars 84 forks source link

Random math is not uniformly distributed #20

Closed chfast closed 5 years ago

chfast commented 5 years ago

The math operation selection is based on r % 11 which is not uniformly distributed. Because (2^32-1) % 11 == 3 the first 4 math operations have higher probability of being selected.

Solution: extend the operations to 16 or trim to 8.

ifdefelse commented 5 years ago

Assuming that KISS99 produces good random numbers then the difference is negligible. They'll have a 1/390,451,572 higher probability of being chosen.

It'd be good to verify KISS99 does behave properly, but every reference I can find indicates it does. For example this review shows KISS99 has a period of 2**123 and doesn't fail any statistical test: https://www.iro.umontreal.ca/~lecuyer/myftp/slides/mixmax-cern16.pdf

chfast commented 5 years ago

How about


    case 11:
        return ~a + ~b;
    case 12:
        return bswap32(a) + bswap32(b);
    case 13:
        return a - b;
    case 14:
        return uint32_t(-a) | uint32_t(-b);
    case 15:
        return a >= b ? a * 7 : b * 5;
chfast commented 5 years ago

This is histogram (with errors) for KISS99 mod 16 (4 last bits) aster 100G and 200G iterations.

 100G:  -0.000062%  -0.000023%  -0.000108%  -0.000043%   0.000078%   0.000062%  -0.000047%   0.000062%   0.000117%  -0.000193%  -0.000237%   0.000092%   0.000276%  -0.000224%   0.000207%   0.000042%
 200G:  -0.000124%  -0.000007%  -0.000055%  -0.000085%  -0.000058%   0.000089%  -0.000008%   0.000008%   0.000138%  -0.000096%  -0.000115%   0.000061%   0.000253%  -0.000075%   0.000014%   0.000060%

And for mod 11.

 100G:  -0.000026%  -0.000162%   0.000034%  -0.000002%  -0.000008%  -0.000225%   0.000005%   0.000084%   0.000061%   0.000148%   0.000090%
 200G:  -0.000081%  -0.000065%   0.000026%   0.000054%  -0.000015%  -0.000062%   0.000001%  -0.000000%  -0.000080%   0.000087%   0.000134%

The biggest error for mod 16 is smaller than 0.0003%. The biggest error for mod 11 is smaller than 0.0002%. The errors does not indicate that numbers 0, 1, 2, 3 are more popular.

chfast commented 5 years ago

I forgot to turn it off, for mod 11 after a night:

37166G:   0.000007%  -0.000004%  -0.000003%  -0.000003%  -0.000001%   0.000006%  -0.000014%  -0.000001%   0.000001%   0.000013%  -0.000001%

For me this can be closed unless you want more random math. bswap and negation looks nice :)

ifdefelse commented 5 years ago

bswap and negate would be nice-to-add, but I don't think it's worth the spec churn at this point