[tor-talk] Regarding #8244; Including a string not under authority control?

Tue Nov 26 03:02:37 UTC 2013

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>
> <bastik.tor at googlemail.com> 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 - tor-talk at lists.torproject.org
> To unsubscribe or change other settings go to
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk