Topic: [ANN] Bitcointalk Giveaway Manager (Read 713 times)

Hmm, we must have our wires crossed somewhere because both of those points are wrong. Let me try again: I'm saying that if you were to call pick_winners_unbiased (from this post) with the blockhash as the "seed" and with the same number of winners as there are contestants, then you would have performed a completely deterministic shuffle. By deterministic I mean that it would always come out the same way (which is your first point) and that the particular way it comes out would depend on the blockhash (which is your second point).

I think maybe I overcomplicated that post with too many ideas (modulo bias, rejection sampling, HMACs, using the SubtleCrypto interface, etc.) and that (as a result) you didn't properly understand the code.

I'm not suggesting that you switch to shuffling, I'm just pointing out that it would work correctly and that you already have everything you need if you decided to approach the problem from that angle.

I think your algorithm (since the overflow fix) is fine as is, and it has the important advantage of being simple to understand (and easy to explain). But, if you wanted to remove the 30-winner limit, and you wanted to keep things simple (no rejection sampling), then one way to do it (since you're already using CryptoJS) would be to change these two lines:



To these:



That would adjust the range of your random numbers from 0-16777215 to 0-4294967295 (making modulo bias even less of a problem) and would let you pick as many winners as you like.

Here's a simulation/histogram (same parameters as before) to confirm that the above algorithm works as expected:

Thanks your suggestion. you are right about them.

The point is that this website needs a new version.
Most of the stuff there is somehow broken already. API changed, many web standards changed, my skills improved and so on. There are many broken links as well.

I need to change so many things there. I also need to figure out a different model for it.

I might make something in react.

Edit: For example, I just took a look at the website and I saw that the most used tool (balance checker) is down because mempool.space changed their API structure. I will try to fix it soon.

you responded well to the giveaway transparency problem, the solution has already been used.

why didn't you integrate it with your main site?
on these giveaway pages, you could at least have a menu linked. There are some interesting tools there, why not inform the giveaway visitors about them?
Just my 2c.

I am happy to announce that this tool is already being used, and it was first used in this giveaway :
https://bitcointalk.org/index.php?topic=5437138.0;all

Results can be verified in this link
shareable result


I am open for ideas for similar projects!

Just added your suggestions here

---

I also add a feature to tell when the future block will be mined, considering 10 minutes per block.

Lol, no, I missed clearly the last part.

Thanks for simulating this, otherwise it could have gone unnoticed for a very long time! O_e_l_e_o's graph doesn't look like what I expected at all.

We're not alts

Did you read my whole post?

Yes. That's a pretty essential detail, so I made sure to get it right.

With bitmover's algorithm, where you appear in the list of participants (in your case, near the middle) affects the probabilities of where you'll appear in the list of winners (which is a sign that something is very wrong). For example, here's the same simulation, but done for o_e_l_e_o (who's near the end of the participants list):



And here's how it looks (i.e. as it should) when repeated with the reference algorithm:



Hmm, these graphs must be much more confusing than I think they are. 1,000,000 simulated outcomes distributed between 30 "bins", leaves each bin with ~33,333 (on average).

---

I don't know how both of you have managed to miss the fact that I suggested that.

This kind of approach will not work for 2 reasons:

1 - not verifiable by third party and cannot be reproduced.
2 -  don't use blockhash, which is a "must" for this project, as this is a deep culture in forum giveaways.


Thats a very good idea, I will implement it.

But also, I believe giveaways with more than one winner are quite unusual, and we won't see this is a lot here.

Anyway, I will implement LoyceV idea to remove a digit when adding another

An easy fix would be to remove a digit on the right when adding one on the left.

Without checking the math, a question: did you remove one participant each time you calculated a next winner? The 0 wins at 15^th (16^th?) makes me think you didn't.

If you simulated 1 million giveaways and made a graph for places 1-30, why is the average around 33,333, and not 1 million?

No problem, happy to help.

Hmm, that's getting a bit too hacky I would say (i.e. adding one imperfect approach onto another). It's worth pointing out that if you did have a good way to shuffle the participants (e.g. with a modern variant of the Fisher-Yates algorithm, and enough entropy to feed it with) then you wouldn't need anything else, because after a properly-executed shuffle you could simply read off the winners according to position (i.e. index 0 = winner 1, index 1 = winner 2, etc.)

Shuffling is actually a very natural way to think about this problem, and the code I provided earlier is capable of doing a "perfect" (unbiased) shuffle. If you call pick_winners_unbiased with a list of (let's say) 50 names and you ask it to return 50 winners, then what results is a shuffled version of the original list.

Sorry to be discouraging, but I don't think the approach you've settled on (i.e. using the available entropy directly, and coming up with an improvised scheme to generate a sequence of random numbers) is one that you should stick with for too long. Stretching out the entropy (with a cryptographic hash function, like Loyce and I have suggested) will let you explore better algorithms (and remove the limit on the number of winners, too).

Your algorithm suffering from "modulo bias" is not that much of a big deal (particularly for this application, and especially with the divisors being so much smaller than your random numbers), but it's a strong indication that you've probably gotten other details wrong, too. For example, the way you're prepending an extra hexadecimal digit for each winner beyond the first one, seems very sketchy to me. Aside from it having no mathematical basis for working correctly (at least, not one that I can see), that approach will overflow; after around 8 "steps" you'll start to lose precision (i.e. you'll be passing things into parseInt that are greater than Number.MAX_SAFE_INTEGER).

One way to test the quality of algorithms like these is to run simulations and compute histograms. So, I simulated 1,000,000 giveaways between 30 participants using your algorithm. In each giveaway "LoyceV" was included in the list of participants with 29 other names. Here's how many times LoyceV won, or came second, or third, etc:



For reference, here's the same simulation data run through the algorithm I proposed earlier:



Now, one of these is clearly working correctly and the other needs a little help.

If you feel like I must have made some kind of mistake, then feel free to replicate my results:

• Use the first 30 names from my previous post as the list of participants.
• Keep an array H of 30 integers, initialized to 0.
• Keep a running counter T set to the current trial # (from 0 to 999,999).

Then, do this 1,000,000 times:

• Compute an imaginary "blockhash" by taking the SHA-256 of T (as a string; e.g. "0" == "5feceb66ffc86f38d952786c6d696c79c2dbc239dd4e91b46729d73a27fb57e9").
• Pick 30 winners from the list of participants using your algorithm and the above blockhash.
• Find the position of "LoyceV" in the list of winners and increment H accordingly.

My suggestion to you would be to take a more careful look at my previous post. But, if you're committed to sticking with your approach (which you seem to be), then I suggest changing this line:


To this:


That will improve things quite a bit (both by avoiding overflow, and also by producing a less correlated sequence). With the above fix applied, your histogram looks very similar to mine:

It essentially boils down to creating a system where each participant has a way to check that the draw was fair and not staged. The fairness is already guaranteed using the hash method of an upcoming block as you mentioned. But this improves and builds upon that idea with more advanced features.

I didn't know this website until now, but let me point a few things this tool can do (I don't know if random.org can do all of not  , but probably not all)

1 - code and results easily verified. No trust involved.
2 - it uses blockhash of a block to select multiple winners, which is already a culture of this forum for a long time.
3 - it allows anyone to share the results here in a simple URL.
4 - easy to use. Random.org is much more complicated as it is much bigger.
5 - you will always get the same winner no matter how many times you roll

I might sound like an unknowledgeable jackass, but what is the problem with random.org and why can't it be used for all kinds of random draws?

Is it the 'it's closed-source so we don't like it' problem or something else? Is there proof the randomness is unsatisfactory?
I fail to see the motive of random.org creators to built a non-random generator that shows a tendency to certain selections over others. Especially because they don't know what kind of selection and for what purpose the software is being used.

I understand that 3rd-parties can't verify that the selection was indeed random and drawn only once. Therefore, there is a need to trust whoever makes the draw to have done it fairly and not generate draws until the number/numbers he wants comes up. Is that the main reason or is there something else?

Yeah, this is certainly important. Easily verified by anyone who wants and always get the same result.

Long day?

I wouldn't shuffle the list of participants, it makes it harder to verify the result.
If you really mind the (give or take) 0.001% difference in chance of winning, just use more digits of the hash to make the difference even smaller. I'd say it's negligible already.

Hello PowerGlove.
Thank you a lot for pointing this out.

I believe you read this article, where the author make similar suggestions about this problem:

https://research.kudelskisecurity.com/2020/07/28/the-definitive-guide-to-modulo-bias-and-how-to-avoid-it/

The problem is that players who are in the first spots will more likely be winners than the ones in last (if we have more than 40 competitors), as pointed in the article.



As in this project I am not dealing with cryptographic schemes that could be attacked and things like that,  I believe I can make an easier way out for this bias.

I can just shuffle the list of competitors before applying the modulo operator.

As I need to always have the same result, I will not use the built in  shuffle function. I can use the blockhash decimal in a custom function to shuffle it.


This function will take move the item up or down depending if 0.5-blockhash_lastdigit is positive or negative.
It will shuffle the array.  

I will take a look if I can find a better way to shuffle it in a more random way.
(Good ideas here: https://stackoverflow.com/questions/16801687/javascript-random-ordering-with-seed)

I believe this will solve the problem in a much simpler way. What do you think?

Nice work, bitmover!

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:


To test it, I used this list of 54 names:


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:


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):


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!

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".

Even better than what I imagined, I like it

Thank you.
I found the bugs. I guess all fixed now.

Now, it's possible that a participant wins more than once. It wasn't like this before the changes.

Edit:
I found another bug.
When I save the link, it doesn't save the target block. It's set to the current block again when I open the saved link.