Thanks for all your input. We are reading it over carefully to see what we can use in our project and will get back to you.
We have already rewritten the following functions to make them as fast as possible:
static void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context *ctx, secp256k1_gej *r, const secp256k1_scalar *gn)
SECP256K1_INLINE static int secp256k1_scalar_reduce(secp256k1_scalar *r, unsigned int overflow)
static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)
We are working on rewriting:
static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b)
Our internal function
#define ec_point_mul_and_add(r,a,n)
{
secp256k1_gej rj;
secp256k1_ecmult_gen(&ecgrp->ecmult_gen_ctx, &rj, n); // highly optimized
secp256k1_gej_add_ge_var(&rj, &rj, a, NULL); // optimization is work in progress
secp256k1_ge_set_gej_var(r, &rj);
}
We heavily rely on and use the following observation to inform our parameter choices:
If the PRF is defined as follows:
x = 1 << (X % m)
The PRF will generate one of the numbers: 2**0, 2**1, .., 2**(m-1) with equal probability
So the average hop distance as a function of m can be calculated as follows:
ahd = (1/m)(2**0) + (1/m)(2**1) + .. + (1/m)(2**(m-1))
= (1/m)[(2**0) + (2**1) + .. + (2**(m-1))]
= (1/m)[(2**m) - 1]
= ((2**m) - 1)/m
Therefore the entire distance hopped by the kangaroo, given nn hops, can be estimated as:
c = nn(ahd)
= (nn/m)((2**m) - 1)