Resolves YES if by end of November there is a Manifold bot that generates random numbers upon request.
See also https://manifold.markets/post/public-randomness-sources for my post on current methods for generating random numbers without having to trust someone.
Related:
1,000
3.00This resolves YES. Thanks to @A for implementing it!
I haven't had time to look at the code carefully to examine the cryptography, but it clearly suffices for the purpose of this market (which doesn't even require any cryptography). Will continue discussing on https://manifold.markets/jack/will-there-be-an-easy-way-to-genera about whether it's secure (so far, I think so).
Tested; seems secure.
(The beacon is being queried after, /0 = /latest, might actually link to /latest for verifiability)
Not clear how to audit except in real-time as the beacon doesn’t store timestamps; worth adding “wait N steps” for large markets or a blockchain with cleaner historical records.
Modulo looks right; makes sense.
—
Secure with eyes on it, less so if no one checks https://drand.cloudflare.com/8990e7a9aaed2ffed73dbd7092123d6f289930540d7651336225dc172e51b2ce/public/latest and perhaps not at all historically unless there is a log somewhere;
(Still prefer verifiably random source, ie bitcoin hash, and others audit, though would trust it in any smaller markets certainly.)
@Gigacasting Good point about verifying the timestamps, I expect someone in the drand ecosystem has a solution for this. It's odd that they don't include timestamps in the API.
Someone could easily write a bot to verify all the outputs (especially if the above point is solved so that you can verify historical data, not just real-time), so I think this is good enough for most practical purposes.
The whole reason I suggested this bot is that it does the work of grabbing the public randomness source for us - it was way too much burden to do manually (most of us who were were doing it because we were interested in experimenting with randomization protocols). I think the bot could easily be adapted to any public randomness source - I suggested drand as a public randomness beacon for a couple reasons, mainly that it publishes randomness at predictable, frequent intervals unlike blockchain, and is in some ways more manipulation-resistant than blockchain.
Good points, thanks!
It looks like the drand rounds are published at a fixed increment of one per 30 seconds (https://drand.cloudflare.com/8990e7a9aaed2ffed73dbd7092123d6f289930540d7651336225dc172e51b2ce/info), so I guess you can use that to compute when they become available -- I've added that calculation to the bot output. Ideally though yes, someone who wants to be 100% trust-free should audit this in real-time to ensure Cloudflare isn't violating the protocol and publishing rounds early.
I added a link to latest in the bot output to make this easier to audit manually, as well as an offset option to increase the number of delay rounds on particularly important markets. I also increased the default offset from 1 to 2 to make it less likely to have the appearance of manipulation in case the bot falls slightly behind.
Yeah it shouldn't be too hard to adjust this to add an option for using bitcoin or something as the randomization source instead but I'm going to punt on that for now unless someone wants to submit a PR, I think drand is good enough.
@A Yeah they're supposed to be every 30 sec but presumably that can be disrupted not just by attacks but also by enough of the participants having an outage.
Light audit: clean code, possible the randomness beacon should be queried after comment_id, and the modulo can be vastly simpler (int(s, 16) % N) using the entire seed in one-pass.
Possible for manifold/gcp exploits currently, and maybe buggy with the seed use.
Still eight orders of magnitude better than the current randomness source:
@Gigacasting Thanks! Going through your suggestions:
possible the randomness beacon should be queried after comment_id
Are you saying it should be sha256(salt + randomness) instead of sha256(randomness + salt)? Not sure why this matters as long as SHA256 is secure. The general idea here is that once the bot posts its first comment announcing the salt and which round of drand will be used, everything after that is entirely deterministic and can be computed by anyone independently as soon as drand releases its next randomness round. So it shouldn't be too sensitive to exactly how we randomize since we don't have any choices available to manipulate.
modulo can be vastly simpler (int(s, 16) % N) using the entire seed in one-pass
Same thing basically -- it shouldn't matter too much exactly what we do here as long as the procedure is fixed. I think it's helpful to limit to 64-bit integers so people can more easily reproduce the results in languages other than Python that might be less friendly to big-ints. And there's no benefit to using more bytes assuming SHA256 is secure, right? It is important that we do the "retry until value is less than evenly_divisible" logic though because otherwise the lower numbers in the range will be slightly favored. (E.g. imagine if we had an initial random input in the range 0-15 and we were doing modulo 13 to reduce it -- obviously 0,1,2 are much more likely than the rest without the retry logic.)
Possible for manifold/gcp exploits currently
You mean if Manifold edits the initial comment declaring what we're going to do? Yeah I guess so. If you really don't trust Manifold, anyone can feel free to log those values somewhere and complain if they change later on. But if we don't trust Manifold at all then the Mana you win isn't worth much. 🙂
Yes, using a prefix is still secure, but it does make the logic a bit less simple. I think your reasoning is fair and you could go either way here. In my mind, the main downside of using a small prefix is that it makes the retry logic important. If you used the full hash, then the retry logic doesn't matter for practical values of N which will be astronomically smaller than the hash size.
Re manifold/gcp exploits: I think it's a lot more robust than you all are giving it credit for, because of email notifications, which ensure that the commitment data is sent on another channel to anyone watching the market. One can imagine attacks based on disabling email notifs or pretending emails were down, sure. But it's not terribly hard to harden the protocol against this class of issue.
Right, I capped the supported range at 2^48 precisely so that the retry logic should already almost never come into play (less than 0.01% probability on any given attempt, even in the worst case scenario, and realistically people will mostly generate much smaller numbers and the probability will be way lower). But yeah if someone demonstrates a use-case for larger numeric ranges than sure we can easily increase the prefix length.
Yeah good point on emails, that basically means that the "anyone can feel free to log those values somewhere" suggestion is already covered.
Does this qualify for resolution yet, or would you rather wait for more quality controls?
https://manifold.markets/FairlyRandom https://manifold.markets/FairlyRandom/test-market-b5247070e715
@lu Oh nice! This is awesome - I see you're using drand so I think it even satisfies the stronger criteria for the "secure and verifiable randomness" market.
@lu Yes, it's by me. Unfortunately the public Manifold API only supports top-level comments currently as far as I can tell.
@lu Okay I've moved the bot to run on a legit server now instead of just from my laptop, so this should be good to go now. If anyone wants to play around with it on other markets feel free -- just remember that you need to add the FairlyRandom tag first so it knows which markets to scan for comments. No remaining known bugs, but I would still consider this slightly experimental for the next day or two and reserve the right to make slight tweaks if issues are found -- don't use it for anything super high stakes quite yet.
@jack What's the requirement for how long this needs to be running stably in order for these markets to resolve?
@A I didn't have any requirement for uptime, I think as soon as it was demonstrated in your test market it counted as YES.
