Compute Security Level in Mithril Explorer

[jpraynaud]

Issue

We need to display a Security Indicator for the Certificate in the Mithril Explorer and the formulas used to compute it (displayed when hovering the protocol parameters). Our goal is to provide a clear information of the security provided by the certificate to an end user. This will help to be transparent during the ramp-up phase where we will have SPOs on boarded. This could also be used in the Mithril Client to require a minimum level of security (a restoration would not be possible if the security indicator is not reached).

Tasks

• [ ] Define Security Indicator (for example a scale 0-100 or 0-5 or ..., to be defined)
• [ ] Compute the Security Level of the multi-signature given the protocol parameters
  • Correspondence table protocol parameters vs security level pre-computed
  • Or compute on the fly the security level given the parameters
• [ ] Compute the Stake Shares involved in Mithril vs Cardano
• [ ] Add a page in documentation of the Security Indicator with formulas and their explanations and a link from the explorer to this page

Glossary

• Security Indicator: Notation of the security of the certificate displayed to end user (e.g. in the explorer). It is computed by aggregating the Security Level and the Stake Shares (to be determined)
• Security Level: The cryptographic security of the multi-signature that is linked to the protocol parameters (e.g. 128 bits means that an adversary has 2^-128 probability to create a certificate)
• Stake Shares: The ratio of Cardano Stakes involved in the Mithril network vs Active Cardano Stakes

How to compute the security level of a multi-signature

Let A = max assumed adversarial stake
Let a = A / max_stake
Let p = φ(a)  // f needs tuning, something close to 0.2 is reasonable
Then, we're secure if SUM[from i=k to i=m] Binomial(i successes, m experiments, p chance of success) <= 2^-100 or thereabouts.
The latter turns to 1 - BinomialCDF(k-1,m,p)
To add to that, we also need to be lively (i.e good guys will actually manage to sign). For that we have:
Let h = 1-a     // this assumes all stake is mithril stake
Let q = φ(h)
Then, the chance of a signing attempt succeeding is 
`SUM[from i=k to i=m] Binomial(i successes, m experiments, q chance of success)`, which we want to be very close to 1.
We can "boost" the success attempt if we allow retries (e.g. by appending some counter to the message, and also adding some logic for clients to (1) understand the counter and (2) prefer smaller counter values), and also with the hybrid option ([long version here](https://github.com/input-output-hk/mithril/issues/11), but the short version is that we pick more than one set of (k,m). When  signing we pretend m is the largest amongst m of any set, but when aggregating we try all sets from the smallest: e.g. "we want 100 sigs on the first 180 slots, or 200 sigs on the first 350 slots". Signers sign as if m=350 but aggregators will first try the 100 of 180 hoping they can build a small cert.

Depends on #636

[jpraynaud]

@rezabaram @iquerejeta @pyrros @curiecrypt @abailly-iohk

Further discussions are probably needed to complete this issue:

• Define Security Indicator display with product team (e.g. which notation, which colors to use)
• Define Security Indicator computation with cryptographers/researchers
• Compute Security Level with cryptographers/researchers
• Redact documentation page