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

[Nick Mathewson]

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