PowerGlove
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 27, 2023, 04:33:49 AM |
|
Nice work, bitmover! ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) Although it's not a big deal for this application, using the modulo operator like that will introduce a bias into the results (look up "modulo bias", if you're interested). One way to ensure a mathematically fair selection process is to generate a random number, and then (instead of applying a modulo operation to force it within range) throw it away and try again if it's not already in the range you need it to be in. A naive implementation of this "rejection sampling" would be very inefficient, so what you need to do is mask off some bits (based on the nearest enclosing power of two) and then apply the range check after that. To make the above feasible, you need a good source of deterministically-generated random numbers. One way to get them would be to use Loyce's tip, and treat the blockhash as a "seed" which you append a running counter onto and then take the SHA-256 of that. Another way, which I prefer (only by a little) is to do effectively what Loyce suggested, but use SHA-256 in an HMAC construction (i.e. as a keyed hash function, with the seed as the "key", and a running counter as the "data"). I implemented the above as a Python (3.7+) script that you can play around with, if you like: #!/usr/bin/env python3
import sys
import hmac
import math
def fail_if(condition, message):
if condition:
sys.exit('fatal error: ' + message)
def random_uint32(seed_bytes, index):
fail_if(index < 0 or index > 4294967295, 'index is out of range.')
return int.from_bytes(hmac.digest(seed_bytes, index.to_bytes(4, 'little'), 'sha256')[:4], 'little')
def pick_winners_unbiased(how_many, from_list, seed_bytes):
fail_if(how_many < 0 or how_many > len(from_list), 'how_many is out of range.')
remaining = from_list[:]
winners = []
counter = 0
while len(winners) != how_many:
mask = 2 ** math.ceil(math.log2(len(remaining))) - 1
random = random_uint32(seed_bytes, counter) & mask
counter += 1
if random < len(remaining):
winners.append(remaining.pop(random))
return winners
def main(args):
fail_if(len(args) != 3, 'expected 3 arguments (how_many_winners, names_file_path, seed_text).')
how_many_winners, names_file_path, seed_text = int(args[0]), args[1], args[2]
with open(names_file_path) as file:
list_of_names = [name for name in file.read().splitlines() if name.strip()]
seed_bytes = seed_text.encode('utf-8')
print(f'Picking {how_many_winners} winner(s) from a list of {len(list_of_names)} participant(s), using seed "{seed_text}": {pick_winners_unbiased(how_many_winners, list_of_names, seed_bytes)}.')
if __name__ == '__main__':
main(sys.argv[1:])
To test it, I used this list of 54 names: TryNinja BitMaxz hilariousetc HeRetiK pooya87 HCP OmegaStarScream LeGaulois mocacinno DooMAD jackg mk4 buwaytress LoyceV AdolfinWolf Hydrogen stompix Potato Chips The Sceptical Chymist Welsh d5000 Steamtyme ranochigo DdmrDdmr Rath ETFbitcoin Lucius o_e_l_e_o 1miau malevolent mikeywith Husna QA suchmoon Halab nc50lc mole0815 fillippone Trofo NotATether Bthd GazetaBitcoin bitmover NeuroticFish dkbit98 Pmalek BlackHatCoiner DireWolfM14 SFR10 DaveF Ratimov webtricks Rikafip hosseinimr93 n0nce
It's mostly intended as reference code, so I didn't spend much time making it user-friendly. It expects 3 arguments: the number of winners to pick, a path to a file containing the names of participants (one per line), and a seed. So, if you place the script into a file named "pick_winners.py", and the above list into a file named "names.txt", and you wanted (for example) to pick 3 winners from that list (using the hash of the genesis block as the seed), then you would invoke it like this: $ python3 pick_winners.py 3 names.txt 000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f Which should produce the following: Picking 3 winner(s) from a list of 54 participant(s), using seed "000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f": ['n0nce', 'BlackHatCoiner', 'dkbit98'].Obviously, JavaScript would be more useful to you, and if you don't mind leaving older browsers out in the cold, then the above algorithm can actually be implemented pretty easily (by using the built-in SubtleCrypto interface; you just have to be careful to always serve the page over HTTPS, which is a requirement for this interface to be available on some browsers). Here are the important functions (forgive my clumsy JavaScript, I'm a bit out of practice): async function seed_from_text(text) {
// assumes: "text" is a non-empty string
const encoder = new TextEncoder();
return { hmac_key: await window.crypto.subtle.importKey("raw", encoder.encode(text), { name: "HMAC", hash: "SHA-256" }, false, ["sign"]) }; }
async function random_uint32(seed, index) {
// assumes: "seed" came from seed_from_text(...)
// assumes: "index" is an integer >= 0 && <= 4294967295
const data = new Uint8Array([index & 255, index >> 8 & 255, index >> 16 & 255, index >> 24 & 255]);
const hash = await window.crypto.subtle.sign("HMAC", (await seed).hmac_key, data);
return new DataView(hash).getUint32(0, true); }
async function pick_winners_unbiased(how_many, from_array, seed) {
// assumes: "how_many" is an integer >= 0 && <= from_array.length
// assumes: "from_array" is an array of all participants
// assumes: "seed" came from seed_from_text(...)
const remaining = from_array.slice();
const winners = [];
let counter = 0;
while(winners.length != how_many) {
const mask = 2 ** Math.ceil(Math.log2(remaining.length)) - 1;
const random = await random_uint32(seed, counter++) & mask;
if(random < remaining.length) {
winners.push(remaining.splice(random, 1)[0]); } }
return winners; }
The SubtleCrypto interface is asynchronous, so (unfortunately) these functions have to be, too. Here's a small example of me testing them, in the browser console: >> seed = await seed_from_text("000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f"); << Object { hmac_key: CryptoKey } >> names = ["TryNinja", "BitMaxz", "hilariousetc", "HeRetiK", "pooya87", "HCP", "OmegaStarScream", "LeGaulois", "mocacinno", "DooMAD", "jackg", "mk4", "buwaytress", "LoyceV", "AdolfinWolf", "Hydrogen", "stompix", "Potato Chips", "The Sceptical Chymist", "Welsh", "d5000", "Steamtyme", "ranochigo", "DdmrDdmr", "Rath", "ETFbitcoin", "Lucius", "o_e_l_e_o", "1miau", "malevolent", "mikeywith", "Husna QA", "suchmoon", "Halab", "nc50lc", "mole0815", "fillippone", "Trofo", "NotATether", "Bthd", "GazetaBitcoin", "bitmover", "NeuroticFish", "dkbit98", "Pmalek", "BlackHatCoiner", "DireWolfM14", "SFR10", "DaveF", "Ratimov", "webtricks", "Rikafip", "hosseinimr93", "n0nce"]; << Array(54) [ "TryNinja", "BitMaxz", "hilariousetc", "HeRetiK", "pooya87", "HCP", "OmegaStarScream", "LeGaulois", "mocacinno", "DooMAD", ... ] >> winners = await pick_winners_unbiased(3, names, seed); << Array(3) [ "n0nce", "BlackHatCoiner", "dkbit98" ]I hope all of the above can help you to improve your nice project! ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) One cool thing about this approach is that it would remove the 30-winner limit you currently have. Also, having the algorithm available as a Python script might find a use case in giving people a second way to verify results. P.S. Two small spelling mistakes I spotted: "For additonal winners" and " Provaly fair giveaway manager".
|