Not sure if this is already well known and documented somewhere, but I'd like to sort out the implication of dishonest witnesses.
Say there are a total of n witnesses, m of which are honest. The other n-m are willing to participate in either denial of service (refuse to cosign anything) or split-view attacks (cosign multiple inconsistent tree heads). Assume client policy requires at least k valid cosignatures.
To thwart denial of service attacks, we must have k <= m.
For a split-view attack, the attacker wants two clients (with the same policy) to accept two distincts views of the log. It seems the best the attacker can do is to have each view the tree cosigned by half of the honest witnesses and all of the dishonest witnesses, so that the number of valid cosignatures on each view is
n - floor(m/2), n - ceil(m/2)
The attack succeeds if both are accepted, and it is thwarted if
k > n - ceil(m/2)
We would like to have at least one value of k that is secure, and that would have to be k = m, and then we need
k > n - ceil(k/2)
which should be equivalent (if I get the details of ceil and floor logic right) to
k > 2n/3
and
k >= 1 + floor(2*n/3)
So a little table,
n 1 2 3 4 5 6 7 8 9 10 min k 1 2 3 3 4 5 5 6 7 7
The important point here, is that if one uses a k-of-n policy with smaller k than in this table, say, 5-of-8 witnesses, then it is *not* sufficient with 5 honest witnesses to reject a split view, since we could have a split view with 5 and 6 cosignatures on each view. And 6 honest witnesses isn't enough either, we need at least 7, i.e., we can tolerate at most a single dishonest witness.
It also seems worth noting that we need at least 4 witness before we can have any redundancy.
Regards, /Niels