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.
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.