Random coin sort is slightly biased

[emilbayes]

Random sorting of coins during coin selection uses Math.random(), which outputs in the interval [0, 1[. Splitting this interval in two equal intervals yields [0, 0.5[ and [0.5, 1[. This means the current sort is slightly biased as it considers the intervals [0, 0.5] and ]0.5, 1[. In large this probably doesn't matter, but it is a slight logic bug. It can easily be fixed by changing to either < or >=

bcoin/lib/primitives/mtx.js

Line 2040 in 7bc3251

return Math.random() > 0.5 ? 1 : -1;

[pinheadmz]

Interesting, good eye!

Looks to me like the default for initializing the coin selection in init() is by value anyway (not random) and there is a good deal of processing that follows in the coin selector anyway, so this bug will very rarely have a noticeable effect.

But I think you are right, if the random initialization is selected, there will be a tiny bias towards coins that occur later in the passed coins array. How tiny? I'm curious.

Well, Math.random() returns a 64-bit float with 52 bits of "entropy" like 0.22262904318293097. Since this is only a bug in the case that Math.random() returns exactly 0.5 the sorting function will select the "b" value an extra 1/2^52 times 😁 (Check my math?)

Were you noticing nay other bugs? Out of curiosity, What brings you own to this part of the code base? Thank you for your observation!

[emilbayes]

Floats are not uniformly distributed in that range, so I don't think the probability is that simple. But like I mentioned above, I don't think "bug" is of any consequence :)

[tynes]

Maybe bcrypto.random.randomRange would be a better source of randomness?
It uses "openssl/rand.h" and "random.h"

https://github.com/bcoin-org/bcrypto/blob/master/src/random/random.c
https://github.com/bcoin-org/bcrypto/blob/master/lib/js/random.js#L89

[emilbayes]

If you want to go that route, then a random bitflip is probably better, eg. bcrypto.random.randomInt() which will give interval [0, 2**32[, split it and you get [0, 2**16[, [2**16, 2**32[ and you can then check randInt =< 0xffff

[emilbayes]

@tynes Actually that function you linked doesn't allow you to generate the full uint32 range, because the max is exclusive but also asserted to be a valid 32 bit uint itself. Don't know if this is on purpose :)
https://github.com/bcoin-org/bcrypto/blob/b812f35db315b0272790202ca386a3cbbfc20d87/lib/js/random.js#L91