Shorter Certificates via Early Stopping

[pyrros]

Currently, mithril operates with a single set of f/m/k parameters. The parameter f determines the probability of success, and the protocol then requires k successes over m indices. For security and liveliness, k and m are chosen so that an adversarial stake will have negligible probability of success while an honest one will have a significant one. Importantly, this choice assumes that (1) the adversarial stake will refuse to cooperate with honest users and that (2) the adversarial stake is the maximum allowed by the definition.

If we relax the two above assumptions, we are able to be much more aggressive in our choice of parameters, with no security impact against adversarial forgeries. There is however considerable impact in the possibility for denial of service/ liveliness. This can however be overcome:

We can select two* pairs (k_a,m_a) and (k_c,m_c) with the first one being aggressively parametrized, and the second one conservatively. Signers operate as normal. Aggregators attempt to create an aggressively parametrized certificate before a conservative one, and verifiers prefer aggressive certificates to normal ones.

This solution realizes the space savings of the aggressive parametrization if the adversary is weaker than allowed, but retains liveliness versus a maximal adversarial stake. Against forgeries, the adversary gains a small benefit, but the overall gain is in the order of 1 bit of security i.e from one chance at 2^{-100} to (less than) two chances at 2^{-100}.

Motivational Example:

One current (k/m) pair is 357 out of 2643. Shorter certificates can be set to 228/1400 (36% smaller) with a fallback to the initial values if we are unable to locate 228 sigs in the first 1400 indices.

Changes in the primitive:

Low to None (assuming k,m not hardcoded or embedded in sigs/certs --also see #9 ).

Changes in node logic:

Yes, limited. Nodes need to be aware of both values and use them in the correct order.

Relevant to BP/Halo:

Yes, the benefits will be similar. Need a “short” version of the circuit to handle short proofs, but no structural changes are needed.

Security impact:

Negligible. We can quantify the advantage of the adversary to less than 2x of the original. We can either accept that, or re-parametrize for 2^{-101} base advantage which will still be bounded by 2^{-101} after doubling.