[tor-dev] Tor with collective signatures

[Tim Wilson-Brown - teor]

> On 26 May 2016, at 10:22, Nicolas Gailly <nicolas.gailly at epfl.ch> wrote:
> 
> A related issue for discussion is whether it could be problematic if
>    there are two or more distinct collective signatures for a given
> directory
>    consensus, and whether it is a problem if distinct subsets of 5 DAs
> might
>    (perhaps accidentally) produce multiple slightly different, though valid
>    and legitimately-signed, consensus documents at about the same time.

This is not possible, each authority only produces one consensus per hour.
If a majority of authorities sign the same consensus, that consensus will be served by all authorities, and accepted by clients.
Otherwise, there is a consensus failure, and no authority serves a consensus for that hour.

>  In
>    other words, does Tor directory consensus “need” strong consistency
> with a
>    single serialized timeline, as Byzantine consensus protocols are
> intended
>    to provide - or is weak consistency with occasional cases of multiple
>    concurrent consensus documents and/or collective signatures acceptable?
> 
>    As far as our understanding of Tor goes, there does not seem to be any
>    particularly strong consistency requirements between the different DAs’
>    perspectives. Therefore, the simplest approach would be that all DAs
>    independently act as leaders to produce different collective
> signatures on
>    the same consensus documents. This approach does not require any
>    synchronization between DAs and enable directly each DA to service the
>    CoSi-signed consensus document to the Tor network. Later it may be worth
>    exploring automated leader-election mechanisms and/or stronger
>    consensus-consistency mechanisms, but there does not seems to have a
> need
>    for such a complexity right now.

If you wish to include extra "CoSi" lines in the consensus, they must be deterministically agreed.
The process works something like this:
* each authority includes information in its vote,
* each authority deterministically uses the information in the votes to produce a consensus,
* each authority signs the consensus it produced,
* if a majority of authorities signed exactly the same consensus, that consensus is served to clients.

As you mention, one way to work around this requirement is for authorities to round-robin as CoSi leader.

A second is for each authority to validate the CoSi signatures provided by each other authority, and only include those signatures validated and voted for by a majority of authorities in the consensus. (CoSi validation is deterministic, even thought CoSi signing is not, due to network effects - a CoSi signer may sign one request, but go down before signing them all.)

A third is for CoSi signatures to be appended to the consensus, just like authority signatures are appended. Then authorities, mirrors, and clients only serve consensuses with a majority (5/9) of valid CoSi signatures.

Tim

Tim Wilson-Brown (teor)

teor2345 at gmail dot com
PGP 968F094B
ricochet:ekmygaiu4rzgsk6n



-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 842 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160526/fc0cc1d3/attachment.sig>