Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Shorter Certificates via Early Stopping #11

Open
pyrros opened this issue Oct 19, 2021 · 0 comments
Open

Shorter Certificates via Early Stopping #11

pyrros opened this issue Oct 19, 2021 · 0 comments
Assignees
Labels
P-low Priority: low T-feature Type: new features

Comments

@pyrros
Copy link

pyrros commented Oct 19, 2021

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.

@pyrros pyrros self-assigned this Oct 19, 2021
@pyrros pyrros changed the title Shorter Certificates via Early Stopping. Shorter Certificates via Early Stopping Oct 19, 2021
@iquerejeta iquerejeta added T-feature Type: new features P-low Priority: low and removed enhancement labels Nov 23, 2021
@iquerejeta iquerejeta self-assigned this Apr 28, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
P-low Priority: low T-feature Type: new features
Projects
None yet
Development

No branches or pull requests

2 participants