Write Your Own SDK

Convert Digits to Integers

The N and X challenge parameters are encoded as arrays of 32-bit unsigned digits. To be able to operate on those numbers comfortably and efficiently, we first have to parse those digits.

The algoritm is simple. Start with result = 0, then for every digit in the array do result = (result << 32) | digit. The following pseudocode displays it simply:

function get_integer_from_digits(digits: number[]) -> integer:
    result = 0
⠀
    for digit in digits:
        result = (result << 32) | digit
⠀
    return result

Easy. Then we can use that function on both X and N. The following examples show actual code implementations of such function:

/**
 * Converts an array of u32 digits to a bigint.
 *
 * @param digits The digits of the bigint, MSF.
 * @returns The formed bigint.
 */
function getBigintFromDigits(digits: number[]): bigint {
    let result = 0n;

    for (const digit of digits) {
        result = (result << 32n) | BigInt(digit);
    }

    return result;
}

Perform the Computation

Once we have our utility function to get numbers from digit arrays, we can perform the calculation that burns CPU cycles. The result of this step will later be used to compute a proof; Should this step be skipped, the proof will fail to validate.

In plain English, the computation is simple: starting with Y = X, repeat Y = Y^2 % N T amount of times. In pseudocode:

y = x
loop t times:
    y = y**2 % n

Y will be our solution to the challenge.

This step is not skippable given that it's effectively X^2^T % N. Since T is large and so is X, computing it in one operation is infeasible. For example, with T = 1,000,000, 2^T has about 301,030 decimal digits (1,000,001 bits). By using the algorithm above in a loop, we can get the result of the full computation without needing to build 2^T nor X^2^T nor store it in memory.

This step is also not parallelizable. Each iteration needs to know the result of the previous one, which leaves no advantage to GPUs. In code, this step would be

function solve(nDigits: number[], xDigits: number[], t: number): bigint {
    let n = getBigintFromDigits(nDigits);
    let x = getBigintFromDigits(xDigits);
    let y = x;

    for (let i = 0; i < t; i++) {
        y = y ** 2 % n;
    }

    return y;
}

Proving the Solution (Z)

Now that we have our solution Y, let's make a proof we actually solved the problem. This will allow the server to validate our solution without having to do all the iterations again. If our solution happens to be invalid, the challenge will fail to validate to the server.

Making a proof is divided into two parts: getting parameter L and getting parameter PI (our proof). PI depends on L, so lets get L first.

To get L, we'll create an intermediate parameter Z which is the result of SHA-256-hashing the following parameters (in order):

1. duckity as ASCII bytes,
2. The challenge's N as 512 MSF bytes padded with 0s,
3. The challenge's X as 512 MSF bytes padded with 0s,
4. The challenge's T as 512 MSF bytes padded with 0s,
5. Our Y as 512 MSF bytes padded with 0s.

The result of hashing those parameters together will be 32 bytes, which will be our Z parameter.

For this, we'll need a new function to convert our bigints to digits (bytes). The algorithm is simple, the inverse of what we used for our get_bigint_from_digits() to decode N and X in the previous step. In pseudocode, it's

function get_digits_from_bigint(number: bigint, array_width: number, digit_byte_width: number) -> number[]:
    digits = [0] * array_width
⠀
    mask = 0;
    loop digit_byte_width times:
        mask = mask << 8
        mask = mask | 0b1111_1111
⠀
    for i in 0..array_width:  # [0; array_width), from 0 to array_width - 1 inclusive.
        digit = number & mask
        digits[array_width - 1 - i] = digit
        number = number >> (digit_byte_width * 8)
⠀
    return digits

In TypeScript and Python, that's

/**
 * Converts a bigint into a MSF digit array.
 * 
 * @param number The bigint number to convert.
 * @param arrayWidth The amount of digits to return, padded with 0s.
 * @param digitByteWidth The amount of bytes each digit will carry.
 * 
 * @returns The digits array.
 */
function getDigitsFromBigint(number: bigint, arrayWidth: number, digitByteWidth: number): number[] {
    let digits: number[] = new Array(arrayWidth).fill(0);

    let mask = 0n;
    for (let i = digitByteWidth; i > 0; i--) {
        mask <<= 8n;
        mask |= 0b1111_1111n;
    }

    for (let i = arrayWidth - 1; i >= 0; i--) {
        let digit = Number(number & mask);
        digits[i] = digit;
        number = number >> (digitByteWidth * 8);
    }

    return digits;
}

Now that we have our bigint to digit converters, we can hash our values as described above.

hasher = SHA256()
hasher.update("duckity")
hasher.update(getDigitsFromBigint(n, 512, 1))
hasher.update(getDigitsFromBigint(x, 512, 1))
hasher.update(getDigitsFromBigint(t, 512, 1))
hasher.update(getDigitsFromBigint(y, 512, 1))
z = hasher.finish()

Easy. The following examples show how to do such thing in TypeScript and Python.

/**
 * Hashes the provided parameters to get Z.
 * 
 * @param n The challenge's N param.
 * @param x The challenge's X param.
 * @param t The challenge's T param.
 * @param y The computed Y param.
 * 
 * @returns Z as bytes.
 */
async function getZ(n: bigint, x: bigint, t: bigint, y: bigint): number[] {
    let bytes = Array.from(new TextEncoder().encode("duckity"));
    bytes = bytes.concat(...getDigitsFromBigint(n, 512, 1));
    bytes = bytes.concat(...getDigitsFromBigint(x, 512, 1));
    bytes = bytes.concat(...getDigitsFromBigint(t, 512, 1));
    bytes = bytes.concat(...getDigitsFromBigint(y, 512, 1));

    let hash = await crypto.subtle.digest("SHA-256", new Uint8Array(bytes));
    let z = Array.from(new Uint8Array(hash));

    return z
}

Proving the Solution (L)

Getting L from Z involves interpreting our Z bytes as a big integer and getting the next prime using the Miller-Rabin algorithm.

For this, we'll have to update our previous get_bigint_from_digits() to allow arbitrary digit sizes. That's simple, instead of hardcoding the digit size we'll pass it as an argument to the function. Our pseudocode will then look like

function get_integer_from_digits(digits: number[], digit_byte_width: number):
    result = 0
⠀
    for digit in digits:
        result = (result << (digit_byte_width * 8)) | digit
⠀
    return result

In TypeScript and Python, that's

/**
 * Converts an array of digits to a bigint.
 *
 * @param digits The digits of the bigint, MSF.
 * @param digitByteWidth The amount of bytes each digit carries.
 * @returns The formed bigint.
 */
function getBigintFromDigits(digits: number[], digitByteWidth: number): bigint {
    let result = 0n;

    for (const digit of digits) {
        result = (result << (8n * BigInt(digitByteWidth))) | BigInt(digit);
    }

    return result;
}

Then in our solving code, update the function calls to convert N and X to bigints with a byte width set to 4 bytes.

Now let's interpret Z as a bigint. Since Z is currently the result of hashing our parameters together, each byte will be a single-byte digit.

z = get_bigint_from_digits(z, 1)

To get L, we need to find the next prime to our Z. E.g. if Z = 5, L = 7. Note how 5 is already a prime, yet we get the next one regardless.

Getting the next prime is simple. Starting with Z + 1, we call 40 Miller-Rabin tests to check whether it's prime. Many libraries out there already implement Miller-Rabin tests so you don't have to implement it yourself. In case you don't want to, or cannot, use such libraries, we'll explain how to implement it manually here.

Our implementation will be divided into 4 functions: is_prime(number, amount_of_bases), is_prime_for_base(number, base), get_next_prime(number, amount_of_bases), and mod_pow(base, exponent, modulus).

function mod_pow(base: bigint, exponent: bigint, modulus: bigint) -> bigint:
    result = 1
⠀
    while exponent != 0:
        if (exponent & 1) == 1:
            result = result * base
            result = result % modulus
⠀
        base = base * base
        base = base % modulus
⠀
        exponent = exponent / 2
⠀
    return result

/**
 * Computes `(base ^ exponent) % modulus` efficiently, without storing `base ^ exponent` in
 * memory.
 * 
 * @param base The base of the modular exponentiation.
 * @param exponent The exponent of the modular exponentiation.
 * @param modulus The modulus of the modular exponentiation.
 * 
 * @returns The result of the modular exponentiation as a bigint.
 */
function modPow(base: bigint, exponent: bigint, modulus: bigint): bigint {
    let result = 1n;

    while (exponent !== 0n) {
        // (something & 1n) is faster than (something % 2n)
        if ((exponent & 1n) === 1n) {
            result *= base;
            result %= modulus;
        }

        base **= 2n;
        base %= modulus;

        exponent /= 2n;
    }

    return result;
}

function is_prime_for_base(number, base) -> boolean:
    number_minus_one = number - 1
    odd = number_minus_one
    base_times = 0
⠀
    while odd % 2 == 0:
        odd = odd / 2
        base_times = base_times + 1
⠀
    odd_power = mod_pow(base, odd, number)
⠀
    if odd_power == 1 or odd_power == number_minus_one:
        return true
⠀
    loop base_times - 1 times:
        odd_power = (odd_power * odd_power) % number
⠀
        if odd_power == number_minus_one:
            return true
⠀
    return false

/**
 * Runs a single Miller-Rabin test on a number for a specific base.
 * 
 * This function assumes basic checks have been run on the number, like division by two and
 * by five.
 * 
 * @param number The number to check if is prime.
 * @param base The base to use to check if the number is prime.
 * 
 * @returns If the primality test yielded positive for the specified base.
 */
function isPrimeForBase(number: bigint, base: bigint): boolean {
    let numberMinusOne = number - 1n;

    let odd = numberMinusOne;
    let baseTimes = 0;

    while (odd % 2n == 0n) {
        odd /= 2n;
        baseTimes += 1;
    }

    let oddPower = modPow(base, odd, number);

    if (oddPower == 1n || oddPower == numberMinusOne) {
        return true;
    }

    for (let i = 0n; i < baseTimes - 1n; i++) {
        oddPower = modPow(oddPower, 2, number);

        if (oddPower == numberMinusOne) {
           return true;
        }
    }

    return false;
}

function is_prime(number, amount_of_tests) -> boolean:
    if number in [2, 3, 5, 7]:
        return true
⠀
    if number % 2 == 0 or number % 5 == 0:
        return false
⠀
    base = 2
⠀
    loop amount_of_tests times:
        if base >= number:
            break
⠀
        if not is_prime_for_base(number, base):  // Any test returning false means the number is certainly not a prime.
            return false
⠀
    return true

/**
 * Runs up to `tests` amount of tests to check whether a number is a prime.
 * 
 * @param number The number to check for primality.
 * @param tests The maximum amount of tests to run on the number. Setting this value to a
 * higher number means better precision at the cost of speed.
 * 
 * @returns `true` if the number is likely a prime, `false` if the number is not a prime.
 */
function isPrime(number: bigint, tests: number): boolean {
    if ([2n, 3n, 5n, 7n].includes(number)) {
        return true;
    }

    // (something & 1n) is faster than (something % 2n)
    if ((number & 1n) === 0n) {
        return false;
    }

    if (number % 5n === 0n) {
        return false;
    }

    let base = 2n;

    for (let i = 0n; i < BigInt(tests) && base + i < number; i++) {
        let prime = isPrimeForBase(number, base + i);

        if (!prime) {
           return false;
        }
    }

    return true;
}

loop indefinitely:
    number = number + 1
⠀
    if is_prime(number, 40):
        return number

/**
 * Returns the first prime after a number.
 * 
 * Numbers are checked for primality using Miller-Rabin tests on 40 bases each number.
 * 
 * @param number The number to get the following prime for.
 * 
 * @returns The number's following prime.
 */
function getNextPrime(number: bigint): bigint {
    while (true) {
        number += 1n;

        if (isPrime(number, 40)) {
            return number;
        }
    }
}

l = get_next_prime(z)

let l = getNextPrime(z);

Proving the Solution (PI)

Once we have L, our last step towards getting everything we need to get a solution token is getting PI. We want a parameter Q which comes from 2^T = Q * L + R. Then for PI, we use PI = X^Q % N. Not to compute 2^T directly, we'll use a short algorithm to compute PI progressively:

r = 1
pi = 1
⠀
loop t times:
    r = r * 2
⠀
    if r >= l:
        r = r - l
        pi = (pi * pi * x) % n
    else:
        pi = (pi * pi) % n

This way, we get our solution PI without filling up our memory with 2^T. In Python and TypeScript, this is

let r = 1n;
let pi = 1n;

for (let i = 0n; i < t; i++) {
    r = r * 2n;

    if (r >= l) {
        r = r - l;
        pi = (pi * pi * x) % n;
    } else {
        pi = (pi * pi) % n;
    }
}

Once that's done, we'll have our final PI value.