Reading the Security Bound

Bottom line: within the formal model, breaking the knowledge soundness of the deployed Action verifier is —up to a small statistical error— at least as hard as solving Vesta discrete log: the reduction turns every covered attack into a DLOG solver with comparable resources. The benchmark therefore remains Vesta DLOG, whose best known classical attacks have an expected-work scale of about $2^{126}$ group operations. This is conventionally summarized as a 126-bit headline security level for Vesta DLOG. At the certified profile, the constructed solver uses less than twice the attacker's group-work budget, giving this claim a conservative 125-bit computational-work headline; the advantage function below is the precise statement.

Here “knowledge soundness” means that whoever produced an accepted proof must know a valid witness: the private data that justifies the proved statement. The extractor computes the witness from the prover's declared group-element representations, not from the proof alone. “Covered” means inside the theorem's scope: an adversary that stays within the resource budgets below, supplies a representation for every group element it outputs, and faces Fiat–Shamir challenges modelled as a random oracle. The game also samples the verifier's fixed bases; the deployed, baked-in list inherits the result through the fixed-bases argument in Security Models.

For experts

For a bundle containing $n$ Actions and an adversary $A$ making at most $q$ random-oracle queries and performing at most $g$ Vesta group operations, the reduction gives

$$\mathrm{Pr}[\text{verifier accepts but extraction fails}]\le {\mathrm{Adv}}_{\mathrm{DLOG}}(q+22,g+R(n))+{\epsilon }_{\mathrm{stat}}(q,n).$$

${\mathrm{Adv}}_{\mathrm{DLOG}}(q,g)$ is the advantage function: for query budget $q$ and group-operation budget $g$, the externally supplied upper bound on the success probability of a Vesta DLOG solver.

${\epsilon }_{\mathrm{stat}}(q,n)$ is the statistical soundness error: it collects the non-DLOG statistical terms, including exceptional random challenges that prevent extraction and the random-URS binding term, for an adversary making at most $q$ oracle queries against a bundle containing $n$ Actions.

Direction of the reduction:

Action attacker $A$ using $q$ queries and $g$ group operations $⟶$ reduction adds 22 queries and $R(n)$ group operations $⟶$ Vesta DLOG solver using $q+22$ queries and $g+R(n)$ group operations.

The reduction constructs the DLOG solver by running the Action attacker and processing its output. $R(n)$ is the extra Vesta group work it performs for a bundle containing $n$ Actions — reduction overhead, not attacker work or a probability loss. For the deployed Action specialization, the reduction also makes 22 oracle queries beyond those made by the attacker.

For the certified consensus profile, $q\le 2^{123}$, $g\le 2^{125}$, $R(n)\le 2^{123}$, and ${\epsilon }_{\mathrm{stat}}(q,n)\le 2^{-83}$. The exact bound is

$$\mathrm{Pr}[\text{failure}]\le {\mathrm{Adv}}_{\mathrm{DLOG}}(2^{123}+22,2^{125}+2^{123})+2^{-83}.$$

Rounding the solver budgets up to powers of two gives the simpler endpoint

$$\mathrm{Pr}[\text{failure}]\le {\mathrm{Adv}}_{\mathrm{DLOG}}(2^{124},2^{126})+2^{-83}.$$

Here $2^{125}$ is the covered Action-attacker work budget. The reduction turns it into at most $2^{125}+2^{123}\approx 2^{125.32}$ solver work, giving Action a conservative 125-bit computational-work headline. The $2^{126}$ in the endpoint is only its rounded ceiling. Separately, Vesta itself has a headline 126-bit DLOG security level; the matching number has a different origin. Security Models gives the full coverage-parameter interpretation.

In plain language

Outside the statistical soundness error, a covered knowledge-soundness attack would imply a DLOG break with the resources shown above. No easier protocol-specific computational term remains in the bound.

The advantage function says more than any single “security-bit target” could: for any query and work budgets, it tells experts exactly where to evaluate their preferred Vesta DLOG estimate.

Reading the work curve

Choose an amount of Action-attacker group work on the horizontal axis, trace upward to the orange curve, and then read the corresponding computational-success scale on the vertical axis. The curve shifts the idealized Vesta DLOG reference by the reduction's conservative one-bit work loss. Its marked scale is therefore the headline for this claim: about $2^{125}$ group operations, derived from Vesta's 126-bit DLOG headline.

The graph shows only group work. The oracle-query budget $q$ remains a separate input in the equation above, and the statistical term is not plotted. The exact advantage function, not this illustration, is the security claim.

Lean proves the adversary-to-DLOG reduction, its resource transformation, and the statistical soundness error. The numerical DLOG estimate comes from external cryptanalysis.