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.
I think demanding
ln(# notaries)
successfully match the expected Merkle root, then failing if more thane * ln(# notaries)
network failures occur, is an acceptable limit.