Last active
March 4, 2024 09:00
-
-
Save fawazahmed0/d1f4015c1d0683e47b4fd673cfbc9888 to your computer and use it in GitHub Desktop.
Rejection sampling random number
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// https://drand.love/blog/2023/02/22/how-to-use-drand/ | |
// https://research.kudelskisecurity.com/2020/07/28/the-definitive-guide-to-modulo-bias-and-how-to-avoid-it | |
// https://go.dev/src/crypto/rand/util.go | |
// https://go.dev/src/crypto/rand/util.go | |
//follows rejection sampling | |
function getPublicRandom(max, randomHexString){ | |
if(max<=0) | |
throw "max cannot be <=0" | |
let bitCount = Math.floor(Math.log2(max)+1) | |
if (bitCount === 0) | |
return 0 | |
let byteCount = Math.ceil(bitCount/8) | |
// number of bits in the most significant byte of max | |
let sigBit = bitCount % 8 | |
if(sigBit==0) | |
sigBit=8 | |
let firstByteNum = Number("0x"+randomHexString.slice(0, 2)) | |
// Clear bits in the first byte to increase the probability that the candidate is <= max | |
firstByteNum &= (1<<sigBit) - 1 | |
const randomNumber = Number("0x" + firstByteNum.toString(16) + randomHexString.slice(2, (byteCount-1)*2)) | |
if(randomNumber<=max) | |
return randomNumber | |
} | |
// returns randomHexString | |
async function fetchPublicRandomness(round=0){ | |
let randJSON = await fetch(`https://drand.cloudflare.com/8990e7a9aaed2ffed73dbd7092123d6f289930540d7651336225dc172e51b2ce/public/${round}`).then(res=>res.json()) | |
return randJSON.randomness | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment