Fractional difficulty proof of concept, related to https://github.com/TecharoHQ/anubis/issues/106

fractional-difficulty.c

#include <math.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <sys/random.h>

void print_hex(FILE * stream, uint8_t * hash, int size) {
    for (int i = 0; i < size; ++i) {
        uint8_t b = hash[i];
        fprintf(stream, "%02x", b);
    }
}

// Puts the max hash value (inclusive) in buf
void max_hash_f64(double difficulty, uint8_t * buf, int size) {
    const double max_difficulty = size * 8;
    double bits = max_difficulty - difficulty;

    double max_hash = pow(2, bits);
    // extract the exponent and mantissa
    uint64_t mantissa = 0;
    memcpy(&mantissa, &max_hash, sizeof(double));
    // equivalent of what frexp would give, the exponent of a value in range [0.5, 1)
    // see also https://float.exposed/0x3fe0000000000000
    int exponent = (int)((mantissa >> 52) & 0x7FF) - 0x3FE;
    mantissa = (mantissa << 11) | ((uint64_t) 1 << 63);
    // round exponent to next multiple of 8
    {
        const int new_exponent = ((exponent + 7) / 8) * 8;
        mantissa = mantissa >> (new_exponent - exponent);
        exponent = new_exponent;
    }
    // cap exponent
    if (exponent > size * 8) {
        mantissa <<= ((size * 8) - exponent);
        exponent = size * 8;
    }
    mantissa -= 1;
    for (int i = 0; i < size; ++i) {
        int cur_exponent = (size - i) * 8;
        if (cur_exponent > exponent || mantissa == 0) {
            buf[i] = 0;
        } else {
            buf[i] = mantissa >> 56;
            mantissa = (mantissa << 8) + 0xFF;
            exponent -= 8;
        }
    }
}

bool validate(double difficulty, uint8_t * hash, int size) {
    uint8_t max_hash[size];
    max_hash_f64(difficulty, max_hash, size);

    return memcmp(hash, max_hash, size) <= 0;
}

float test(double difficulty, int64_t iters, uint8_t * buf, int size, float * err) {
    // using Welford's algorithm for the variance
    int64_t successes = 0;
    double mean = 0.0;
    double M2 = 0.0;
    int64_t current_attempts = 0;
    for (int i = 0; i < iters; ++i) {
        getrandom(buf, size, 0);
        current_attempts += 1;
        if (validate(difficulty, buf, size)) {
            successes += 1;
            double delta = current_attempts - mean;
            mean += delta / successes;
            double delta2 = current_attempts - mean;
            M2 += delta * delta2;
            current_attempts = 0;
        }
    }
    // TODO: use more appropriate error margin calculation
    if (successes > 1) {
        *err = 2 * sqrt(M2 / ((successes - 1) * successes));
    } else {
        *err = INFINITY;
    }
    return successes > 0 ? mean : NAN;
}

// in bytes
#define HASH_SIZE 32

int main(int argc, char * argv[]) {
    double difficulty = 3.0f;
    int64_t iters = 0;
    if (argc > 1) {
        difficulty = strtod(argv[1], NULL);
    }
    if (argc > 2) {
        iters = strtol(argv[2], NULL, 10);
    }

    uint8_t buf[HASH_SIZE] = {0};

    max_hash_f64(difficulty, buf, HASH_SIZE);
    printf("Max hash (difficulty %7.4f): ", difficulty);
    print_hex(stdout, buf, HASH_SIZE);
    printf("\n");

    if (iters > 0) {
        float err = 0.0f;
        float avg_iters = test(difficulty, iters, buf, HASH_SIZE, &err);
        printf("Difficulty of %7.4f needs %.2f +- %.2f iterations per success\n", difficulty, avg_iters, err);
    }
}

Compiling with gcc -lm -o fractional-difficulty fractional-difficulty.c, and testing with a bunch of different values:

$ for d in -4 0 1 4 8 15 15.25 15.5 15.75 16 32 999; do ./frac-difficulty $d; done
Max hash (difficulty -4.0000): ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Max hash (difficulty  0.0000): ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Max hash (difficulty  1.0000): 7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Max hash (difficulty  4.0000): 0fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Max hash (difficulty  8.0000): 00ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Max hash (difficulty 15.0000): 0001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Max hash (difficulty 15.2500): 0001ae89f995ad3acfffffffffffffffffffffffffffffffffffffffffffffff
Max hash (difficulty 15.5000): 00016a09e667f3bccfffffffffffffffffffffffffffffffffffffffffffffff
Max hash (difficulty 15.7500): 0001306fe0a31b714fffffffffffffffffffffffffffffffffffffffffffffff
Max hash (difficulty 16.0000): 0000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Max hash (difficulty 32.0000): 00000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Max hash (difficulty 999.0000): 0000000000000000000000000000000000000000000000000000000000000000

And when testing the match rate with random bytes:

$ for d in -4 0 1 4 8 15 15.25 15.5 15.75 16 32 999; do ./fractional-difficulty $d 10000000; done
Max hash (difficulty -4.0000): ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Difficulty of -4.0000 needs 1.00 +- 0.00 iterations per success
Max hash (difficulty  0.0000): ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Difficulty of  0.0000 needs 1.00 +- 0.00 iterations per success
Max hash (difficulty  1.0000): 7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Difficulty of  1.0000 needs 2.00 +- 0.00 iterations per success
Max hash (difficulty  4.0000): 0fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Difficulty of  4.0000 needs 16.01 +- 0.04 iterations per success
Max hash (difficulty  8.0000): 00ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Difficulty of  8.0000 needs 256.49 +- 2.60 iterations per success
Max hash (difficulty 15.0000): 0001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Difficulty of 15.0000 needs 33698.30 +- 3654.57 iterations per success
Max hash (difficulty 15.2500): 0001ae89f995ad3acfffffffffffffffffffffffffffffffffffffffffffffff
Difficulty of 15.2500 needs 40208.07 +- 5043.11 iterations per success
Max hash (difficulty 15.5000): 00016a09e667f3bccfffffffffffffffffffffffffffffffffffffffffffffff
Difficulty of 15.5000 needs 45249.27 +- 5925.36 iterations per success
Max hash (difficulty 15.7500): 0001306fe0a31b714fffffffffffffffffffffffffffffffffffffffffffffff
Difficulty of 15.7500 needs 52348.02 +- 8264.05 iterations per success
Max hash (difficulty 16.0000): 0000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Difficulty of 16.0000 needs 68543.54 +- 11767.04 iterations per success
Max hash (difficulty 32.0000): 00000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Difficulty of 32.0000 needs nan +- inf iterations per success
Max hash (difficulty 999.0000): 0000000000000000000000000000000000000000000000000000000000000000
Difficulty of 999.0000 needs nan +- inf iterations per success