Topposting cause I'm tired and lazy. Sorry. So I designed exactly this type of thing c. fifteen years ago. Cf. "Weakly Secret Bit Commitment: Applications to Lotteries and Fair Exchange" and a journal version of some of that in "Temporarily Hidden Bit Commitment and Lottery Applications" Also, Roger and I described an application of the basic idea to mix routes in 2002 <rant> in which we introduced the idea of suicide defense to protect the network that Tyler Moore would later invent independently and get all the credit for</rant> "Reliable MIX Cascade Networks through Reputation" You can find all of these on my homepage http://www.syverson.org/
aloha, Paul On Mon, Nov 25, 2013 at 11:53:45AM -0500, Nick Mathewson wrote: > On Fri, Oct 11, 2013 at 9:44 AM, Sebastian G. <bastik.tor> > <[email protected]> wrote: > > Hello, > > > > beside having each authority call in for their vote about the random > > string, how about including a string in the consensus not under control > > by any authority? > > > > For example a hash from the bitcoin blockchain (its popular and I had no > > other source in mind). The authorities get together at some point, lets > > say 10 minutes before each full hour. They all take the hash from > > hh:45:00 or the closest to that result, where the newest wins. (hh:46:00 > > wins over hh:44:00) > > > > Clients and hidden-services use both the hash and the random string. > > > > If for whatever reason an authority picks a different hash than the > > others there is no error. Like with all(?) other votes the majority > > wins, so the majority would need to be buggy or compromised in order to > > vote for the 'desired' hash. > > > > The bitcoin blockchain is observable and so it is known where the hash > > in the consensus comes from. Anyone could see which hash is included > > look it up in the blockchain and see if it matches the criteria that > > were specified for selecting the hash. > > That's a pretty clever idea! It reminds me of the way that > unsanctioned[1] "numbers game"[2] lotteries used to run. To gain > gamblers' trust, the house wouldn't pick the numbers themselves; > instead, they'd use a number that was supposed to be outside of their > control -- typically, the final digits of the total bets placed that > day at a racetrack.[3] > > The history of gambling sure does have interesting stuff for people > who are interested in computer security! [4] > > > > I'm not sure that I want to incorporate a full bitcoin dependency in > our voting protocol, though: it seems like it would pull in a lot of > code if a Tor authority needs to also be running a full bitcoin > client. > > So, how hard is it to receive and authenticate an unambiguous version > of "The blockchain hash as it stood at midnight UTC today?" Can we get > that with a stripped-down subset of the bitcoin protocols? > > How hard is it to try to get the last transaction before midnight? > What chance of success would an attacker have doing that? I see that > transactions-per-second these days is still pretty close to 1. That > doesn't feel like an impossible target to me, but I'd like to hear > more from people who know the bitcoin protocols better than I do. > > How hard is it to figure out --before doing a transaction-- what > effect it would have on the blockchain's hash afterwards? > > > > Also, besides bitcoin, are there other public verifiable values we > could look at? > > > > [1] (okay, illegal.) > [2] While researching this to refresh my memory, I found that my state > has a lottery called "The Numbers Game". I have no words. > [3] Because there's obviously no way that the mob could have any > influence on _that_, right? > [4] And for computers in general. Check out George Julius's early 20th > century work on electromechanical computers for running parimutuel > betting at racetracks. It's fascinating stuff! > > > > I'm unsure if that solves the case where a single authority can > > influence the result to a desired outcome. I think a non-voting > > authority will have an influence on the random string, but to what > > degree could it benefit a malicious authority not to vote? Authorities > > that drop out of the consensus seem to happen every now and then. > > > > I'm not sure how many time an authority has to calculate the outcome it > > desired. It can know the hash 5 minutes before it gets picked, wait for > > all the other authorities to vote for their part on the random string > > and then compute what it has to vote for to get a string that has the > > desired properties and vote. > > > > If the time for an authority to game this is too high, how about voting > > for the random string as soon as possible, then after all authorities > > voted in time, those that didn't are ignored, the next (upcoming) hash > > of the bitcoin blockchain is included, unless there is none within a > > given timeframe (as one can not guarantee that there will be a new block > > while voting) in which case the latest available hash will be used. > > > > So instead of picking the hash first, then vote doing it the other way > > around. > > > > I'm not sure if that's too complex, although to me it sounds easy. I > > mean I could think of it so it shouldn't give anyone with a > > cryptographic background headache to think this one through. > > > > I've read the thesis and tried to understand the text parts. Having a > > temporary secret so that each authority doesn't know what any other > > authority voted for until the time for voting is up sounds very safe to me. > > So, for commit-and-reveal protocols, the issue is that a malicious > party can decide whether to fake a network failure or something when > it's time to reveal, and then not expose their temporary secret. They > can wait until all honest parties have revealed before making this > choice. That gets the attacker one bit of control per corrupt party. > Call the total number of corrupt parties C. > > I'm not sure that using a commit-and-reveal protocols *together* with > a bitcoin hash makes sense, though: If the attacker can have <C bits > of control on the bitcoin hash, we should just use the bitcoin hash > as-is without voting. If the attacker can have >C bits of control on > the bitcoin hash, then we didn't gain any additional security by using > it. > > So I think that when we're looking at "global external secure secret" > versus "secure multiparty random number generation" designs, we should > consider it an either-or choice, unless I'm doing the analysis wrong. > > > yrs, > -- > Nick > -- > tor-talk mailing list - [email protected] > To unsubscribe or change other settings go to > https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk -- tor-talk mailing list - [email protected] To unsubscribe or change other settings go to https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk
