On 30 April 2016 at 09:56, Nicolas Gailly nicolas.gailly@epfl.ch wrote:
On 04/29/2016 05:13 PM, Tom Ritter wrote:
The mechanism is similar for witnesses that went offline. The parent of an offline witness will set the bit in the bitmap of the failed witness.
You mention this in Cons as well - it seems like the parents in the tree need to be more carefully selected than the leaf nodes or the tree can degrade heavily over time as they leave.
First of all, you have to remember that the Tree layout is not important regarding the signature generation, but is merely here as an optimization. It enables us to restart CoSi with a new Tree layout with a better Leader. Secondly, in the context of Tor + CoSi, the leader would be selected as one of the D.A. (in RR fashion or fixed, see below). From my limited point of view, the D.A.s are considered to be longterm and highly available servers.
Yup, DAs are longterm and available servers. Now it's my understanding that the parent nodes were needed to communicate to the children, and this was a part of the optimized protocol you had developed. If a parent goes offline, permanently, one needs to update the tree and reorganize it. This won't cause a change to signature _verification_ but will cause a change to signature _generation_ - nodes will need to be told 'your new parent is X', and they need to be told that outside the normal tree-based communication. So - doable, and doesn't affect clients, but does require some engineering.
One issue for discussion is who should initiate CoSi protocol rounds and at what times. For example, each of the 9 DAs (or whatever subsetis online) could independently initiate CoSi rounds on each directory consensus event, producing up to nine separate, redundant collective signatures on each directory consensus. Alternatively, the common case might be for one of the 9 DAs to be the CoSi initiator at a given time, with a round-robin leader-change mechanism ensuring that another leader takes over if the prior one becomes unavailable.
Can't CoSi nodes ignore a request to initiate on a consensus document they're already in the process of signing?
Sure. But "ignore a request" would mean that every witnesses refuse to sign? In that case, the leader must have a way to determine if the signature has not been issued because the consensus document is already in the process of being signed or because the consensus document looks suspicious. Here both approaches will return valid signature as long as the CoSi system has been given a valid consensus document.
For my point of view - a consensus should never not-be-signed because it's suspicious. CoSi nodes aren't the determination of what's suspicious. That's some other process entirely separate to this.
I see it as more simple: I get a request to sign document A (identified by some hash). Am I already signing it, or signed it in the past? If so, ignore it. If not, sign it. I would need support for running many instances of the multi-step signing protocol at the same time.
A related issue for discussion is whether it could be problematic ifthere 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. 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?
Such a situation should be a primary use case of CoSi. If an attacker submits a fraudulent consensus for signing it _should_ be signed and logged - that's the primary motivation. Having that signing process fail cause there's already a document in progress would be a poor design.
The question is related to what was discussed during the Tor dev meeting about the Tor Transparency idea (https://lists.torproject.org/pipermail/tor-dev/2014-July/007092.html). There's been some concerns regarding having different signatures for the same content (https://trac.torproject.org/projects/tor/wiki/org/meetings/2016WinterDevMeet...).
In any case, the specifics rules for signing (see the above paragraph.) should be tailored to the Tor needs and should be discussed more in-depth with Tor experts (I'm not one;);
Hmmmmm. I *think* I understand this concern. AIUI the issue is Consensus A and B - which differ only by Authority N who signed B but not A due to network timing or clock skew. Both valid consensuses.
It seems to me we would want to log them both. We want to track all signatures made by a DA key. But perhaps I haven't thought closely enough about this.
4.2 Benefits
Technically, it is quite easy to implement witness cosigning if thegroup of witnesses is small. If we want the group of witnesses to be large, however – and we do, to ensure that compromising transparency would require not just a few but hundreds or even thousands of witnesses to be colluding maliciously – then gathering hundreds or thousands of individual signatures could become painful and inefficient. Worse, every client would need to check all these signatures individually.
That seems like a very painful cost to pay - I would expect this would significantly hurt the performance of Tor in constrained spaces: mobile phones, IOT devices. I had hoped signature checking was a one-shot, not for each individual key.
It was a comparison regarding other multi-signature approaches ;) A CoSi signature can be verified in "one-shot" against the aggregate public key of all witnesses. Moreover, using the Fallback Directory mirrors https://trac.torproject.org/projects/tor/wiki/doc/FallbackDirectoryMirrors) as witnesses, the Tor clients won't need any additional keys as they would already be included in the source code.
Ah okay, so it is just one signature verification? That's great if so.
Additionally, you (or maybe not you, but your protocol) results in a _single_ signature, not N signatures. So there's a size benefit compared to a standard 'N of M' scheme where each element is it's own signature.
Exactly.
it also decreases the incentive to launch such an attack because the threshold of witnesses that are required to sign the document for the signature to be accepted can be locally set on each client.
This does; however, give a pretty straightforward fingerprinting attack.
I'm afraid I don't see what you mean here. Are you talking about the "locally set" threshold of witnesses that must have participated in the CoSi signature in order to be considered valid ? -> Yes: If an attacker has successfully fingerprinted a Tor client by knowing its "threshold", that means the attacker already has corrupted the *majority of the D.A.s* (because the consensus document still need to be signed as usual by a majority of D.A.s), AND at least *threshold* witnesses. -> No: Could you elaborate then please ? :)
Yes. Hardly an easy attack, but if Alice has set her threshold to N+20 signers from the normal N, I can feed a client consensus documents with N+19 and N+20 witnesses and if the first doesn't stick and the second does - I've a good idea it's Alice (or someone else who has set their threshold to N+20).
Teor's comments about Fallback Dirs are better than ones I could write. =)
-tom