Notaries.md

You trust t notaries. Suppose at some point in time,

• s of them are secure (not compromised),
• a of them are available.

We can choose m, the maximum number of notaries to query before giving up, and r, the minimum number of required root matches. Select a random m-size subset of the trusted notaries. Then:

• The probability of an attack happening in this update attempt* is the probability that at r or more compromised notaries are contained in that set.
• The probability of availability (assuming no attack) is the probability that at least r notaries in that set aren't down.

* - A network attacker can for example cause all of the queries to fail with a network error, causing the entire thing to restart, getting a re-roll of the dice that select which notaries to query. They can keep doing this until, by chance, a set is selected of which they've compromised r.

I would find an expression to calculate those probabilities for the given t, s, a. Then find a function that gives good enough security and good enough availability. I'm not sure how to deal with the attack where the attacker forces a re-roll until they've compromised enough of the queried set... You'd have to limit the number of attempts, or at least make it really noisy.

One way to deal with the re-roll attack is to assume the down notaries will eventually come back online, and remember the set that was randomly chosen, and just keep re-trying with that same set. Assuming r of them will eventually come back online that would work, but would be complicated and could unnecessarily postpone upgrades.

But then there's a more general attack, which is that for every new upgrade (e.g. first roll of the dice, no retrying yet) the attacker has a chance of having compromised r of the chosen set. If the probability of that is p then the attacker gets to compromise a p ratio of all updates that happen. I don't think it's possible to kill this attack except by querying all the trusted notaries, which would lead to terrible availability (and updates held back unnecessarily).

I think demanding ln(# notaries) successfully match the expected Merkle root, then failing if more than e * ln(# notaries) network failures occur, is an acceptable limit.

What you really ought to do is add a second layer of notaries just to query to ask which other notaries are up, and then a third layer of notaries to tell you which of those notaries should be up, and a fourth.... poof ... a blockchain appears.