[tor-dev] Proposal 225: Strawman proposal: commit-and-reveal shared rng

[Kang]

Relative to what's in the draft it's an improvement with no obvious downside.

If you were going to do this it would probably be best to use a full
commitment order instead of only selecting the final committer. That
is, instead of having an n'th committer and n-1 chaotically ordered
committers you have a first committer, second, third, ....

In the semi-ordered approach if an adversary had control over d
authorities, 1 of which was the final committer for that round then
for that round they could still easily choose from 2^d values. On the
other hand if you had a full, strict commit ordering then it would be
more difficult because the adversary would need to get all their
controlled authorities into the correct position in the ordering
rather than just one.

How they would be ordered is an interesting question. Making the
ordering unpredictable would amount to solving the same problem that
this shared random value calculation idea sets out to solve.
https://trac.torproject.org/projects/tor/ticket/8244

On Sat, Nov 30, 2013 at 4:24 PM, Sebastian G. <bastik.tor>
<bastik.tor at googlemail.com> wrote:
> 30.11.2013 02:28, Nick Mathewson:
>> [...]
> Trimming to shorten the length.
>
>> Filename: 225-strawman-shared-rand.txt
>> Title: Strawman proposal: commit-and-reveal shared rng
>> Author: Nick Mathewson
>> Created: 2013-11-29
>> Status: Draft
>>
>> 1. Introduction
>>
>>   This is a strawman proposal: I don't think we should actually build
>>   it.  It's just a simple writeup of the more trivial commit-then-reveal
>>   protocol for generating a shared random value.  It's insecure to the
>>   extent that an adversary who controls b of the authorities gets to
>>   choose among 2^b outcomes for the result of the protocol.
>>
>>   See proposal 224, section HASHRING for some motivation of why we want
>>   one of these in Tor.
>>
>>   Let's do better!
>>
>>   [TODO: Are we really stuck with Tor's nasty metaformat here?]
>>
>> 2. The protocol
>>
>>   Here's a protocol for producing a shared random value. It should run
>>   less frequently than the directory consensus algorithm. It runs in
>>   these phases.
>>
>>     1. COMMITMENT
>>     2. REVEAL
>>     3. COMPUTE SHARED RANDOM
>>
>>   It should be implemented by software other than Tor, which should be
>>   okay for authorities.
>>
>>   Note: This is not a great protocol. It has a number of failure
>>   modes. Better protocols seem hard to implement, though, and it ought
>>   to be possible to drop in a replacement here, if we do it right.
>>
>>   At the start of phase 1, each participating authority publishes a
>>   statement of the form:
>>
>>       shared-random 1
>>       shared-random-type commit
>>       signing-key-certification (certification here; see proposal 220)
>>       commitment-key-certification (certification here; see proposal 220)
>>       published YYYY-MM-DD HH:MM:SS
>>       period-start YYYY-MM-DD HH:MM:SS
>>       attempt INT
>>       commitment sha512 C
>>       signature (made with commitment key; see proposal 220)
>>
>>   The signing key is the one used for consensus votes, signed by the
>>   directory authority identity key. The commitment key is used for this
>>   protocol only. The signature is made with the commitment key. The
>>   period-start value is the start of the period for which the shared
>>   random value should be in use. The attempt value starts at 1, and
>>   increments by 1 for each time that the protocol fails.
>>
>>   The other fields should be self-explanatory.
>>
>>   The commitment value C is a base64-encoded SHA-512 hash of a 256-bit
>>   random value R.
>>
>>   During the rest of phase 1, every authority collects the commitments
>>   from other authorities, and publishes them to other authorities, as
>>   they do today with directory votes.
>>
>>   At the start of phase 2, each participating authority publishes:
>>
>>       shared-random 1
>>       shared-random-type reveal
>>       signing-key-certification (certification here; see proposal 220)
>>       commitment-key-certification (certification here; see proposal 220)
>>       received-commitment ID sig
>>       received-commitment ID sig
>>       published YYYY-MM-DD HH:MM:SS
>>       period-start YYYY-MM-DD HH:MM:SS
>>       attempt INT
>>       commitment sha512 C
>>       reveal R
>>       signature (made with commitment key; see proposal 220)
>>
>>   The R value is the one used to generate C. The received-commitment
>>   lines are the signatures on the documents from other authorities in
>>   phase 1. All other fields are as in the commitments.
>>
>>   During the rest of phase 2, every authority collects the
>>   reveals from other authorities, as above with commitments.
>
> (Still haven't read any paper linked from the "bitcoin hash thread".)
>
> By definition each subverted authority will try to be the last one that
> reveals. It would try to calculate whenever or not it is better to
> reveal or fake an error, based on the result it knows.
>
> How about specifying some sort of order for revealing? 8 Authorities
> will be split into 7 for A and 1 for B. Authority B can only reveal its
> commit after all A's revealed theirs, with some timeout, where its vote
> would count if others are missing. Each time they get together for
> voting a different Authority will be B.
>
> With one Authority under my control I could try to game it once instead
> of trying to do this all the time. This works with a fixed pattern,
> where Authority 1, 2, 3, 4, 5, 6, 7 and 8 rotate each time it is to be
> decided about the string. I'm not sure if there would be an improvement
> if that would be more random to avoid being able to predict what
> authority will be allowed to be the last one too far ahead.
>
>
> Regards,
> Sebastian G. (bastik)
> _______________________________________________
> tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev