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

[Sebastian G. <bastik.tor>]

25.11.2013 17:53, 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?
>> [...]
> 
> 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]

This reply is made without having read (at least recently, if ever) any
article or paper linked by any one participating on this topic, but I
will do that at some later point. (Usually the weekend)

Let me say that I think that the world need a distributed voting system
deployed and proven in practice. (Sealed envelope, commit-reveal)

Below you said you'd have A (distributed voting) or B (external string),
right below this text, here, you say 'dependency'.

I wouldn't consider it a good idea to depend on something that may goes
away. I considered it as addition. (more down below)

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

I tend to introduce complexity by thinking to complex at times.

I'm agnostic about the source of the string if it's provable, that it is
not predictable, not modifiable or only at high cost.

In the case of bitcoin, which was used as an example because nothing
else popped into my head, I didn't consider to include bitcoin into Tor.

I considered the authorities building circuits to one or more
websites/public resources to fetch the hash for a given time. Nothing
that would require huge amounts of code.

Beside bitcoin, space-weather data might be published by multiple
sources. Unpredictable, unchangeable fluctuations in the brightness of
the sun...

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

All those questions, wherever the 'numbers' are coming from would have
to be answered for each one of the sources. Indeed, something for
experts, in their individual filed, to think about, I guess.

> How hard is it to figure out --before doing a transaction-- what
> effect it would have on the blockchain's hash afterwards?

As you've noticed (second email) it's related to the mining.

> Also, besides bitcoin, are there other public verifiable values we
> could look at?

Good question. Beside cosmological events nothing else I could come up
with so far.

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

I intended to walk you though my mind to show you why I wanted to
combine them, but that doesn't seem to be required.

If you have a "random global external secure string" and you pick that
before you get the "distributed voting/number generation* going the
subverted parties might be able to game this. So from that perspective
you are right, I think.

Let's consider the bitcoin hash as "random global secure string", just
as example. If you'd include that into the consensus and for some reason
bitcoin starves suddenly, because no ones is mining (or any other
reason), you are were you started. Therefore I'm not for including
something that might go away.

I considered a basic voting scheme (public voting), where each party
votes (oversimplified) for either 1 or 0 and if there's a tie it's
always 1 (or 2). The last voting party can possibly decide if it prefers
1 or 0. In this case adding a number that is unknown to any voting party
after they voted would prevent that. It appears to be correct that
voting is unnecessary if the number can not be influenced or predicted.

I can't come up with a case, right now, where it would make sense to
have "commit-and-reveal" and "external string". I just thought there
would be a case, but I guess there's not, unless it is unclear how much
influence a modified "external string" actually has on the final result.
(So where an adversary can't tell what the string has to be and what the
authorities do commit.)

Regards,
Sebastian G. (bastik)