Batch-Verifiable Stability Certificates via Gram Witnesses

Engineers prove that a control system is stable, or that it cannot amplify energy, by finding a matrix that satisfies a linear matrix inequality (LMI). An LMI is a constraint saying that some matrix built linearly from unknowns has no negative eigenvalues. Finding such a matrix is expensive: interior-point solvers scale roughly as $O(d^6)$ in the state dimension $d$. Checking a matrix someone hands you is cheaper, but it still needs a cubic-cost factorization, and it needs the checker to see all the matrices. That is a problem in a growing set of settings. One is a regulator auditing thousands of controller updates. Another is a smart contract with a tight compute budget. A third is a vendor who wants to prove that a plant identified from proprietary data is passive without revealing the data. Cryptographic proof systems handle this kind of problem for arithmetic statements: they compress thousands of checks into one object that verifies in milliseconds. They cannot express "this matrix has no negative eigenvalues," because positive semidefiniteness is an inequality over the reals. As the research file notes, a random linear combination of matrices can be positive semidefinite even when one of them is not.

This note proposes a way around that obstacle. We do not batch the inequalities. We have the prover attach a factorization witness that turns each inequality into an exact integer identity plus a few cheap sign and range checks. Identities batch and fold with standard random-linear-combination techniques. Sign checks batch the way range proofs already do. The result is an arithmetization of LMI certificates: a translation of "this LMI is satisfied" into arithmetic constraints a proof system can check. Its constraint count grows as $O(n^2)$ per $n \times n$ inequality rather than $O(n^3)$, and its relations are uniform enough that $K$ certificates fold into one succinct proof.

Core Claim

A strict LMI $F(x) \succ 0$ is witnessed by three objects supplied by an untrusted prover: a fixed-point decision vector $x$, a fixed-point lower-triangular matrix $L$, and the integer residual $R$ defined by

$$F(x) = \varepsilon I + L L^{\top} + R .$$

Here $\varepsilon > 0$ is a public margin, and all entries are integers scaled by $2^{-b}$ for a public bit budget $b$. Because $L L^{\top}$ is positive semidefinite by construction, Gershgorin's circle theorem gives a sufficient condition for strict feasibility:

$$\max_i \sum_j |R_{ij}| < \varepsilon \;\;\Longrightarrow\;\; \lambda_{\min}\big(F(x)\big) \ge \varepsilon - \max_i \sum_j |R_{ij}| > 0 .$$

Gershgorin's theorem bounds every eigenvalue of $R$ by its largest absolute row sum. That converts the eigenvalue question into one matrix-product identity and roughly $n^2$ absolute-value bounds. The identity is checked with the sum-check protocol for matrix products, an interactive protocol that verifies a claimed product without recomputing it. This is the machinery behind the GKR-style protocols that zkDL accelerates, and it means the prover never has to arithmetize a cubic-cost multiplication. The absolute values are handled with auxiliary sign-and-magnitude witnesses, the same trick zkDL's zkReLU uses for activations. Integer overflow in the prime field is excluded by range-bounding the entries of $x$ and $L$.

The conic constraint never enters the batching step. Across $K$ certificates, all identities are combined with a random challenge, so Schwartz–Zippel soundness applies exactly. The range checks are pooled the way Bulletproofs pools multiple range proofs.

What is new relative to the closest work is the following. SnarkFold folds thousands of algebraic proofs into a 0.5 KB attestation, but it has no representation of semidefinite cones. zkDL verifies the arithmetic of training steps and says nothing about dynamical invariants. The control papers that motivate this proposal each solve and check one monolithic LMI with no notion of delegation or batching: Learning Dissipative Neural Dynamical Systems, Controller Design for Bilinear Neural Feedback Loops, SafEDMD, and Provably Robust Verification of Dissipativity Properties from Data.

We are explicit that factor-based checks of positive semidefiniteness are classical linear algebra. The contribution is the exact, overflow-safe, fold-friendly arithmetization and an honest measurement of what it costs in certificate tightness.

Research Program

The first component is the compiler. It handles LMIs whose blocks are products of known data matrices and decision matrices. This covers Lyapunov inequalities $A^{\top}P + PA$, S-procedure and quadratic-constraint LMIs for neural feedback loops, and the full-block S-procedure LMIs that data-driven dissipativity builds from Hankel matrices, which are matrices stacking shifted windows of measured trajectories.

This restriction matters. Evaluating a generic $F_0 + \sum_i x_i F_i$ in a circuit costs $m n^2$, which is $d^4$ for a Lyapunov matrix. Product-structured LMIs instead let every block be checked by matrix-product sum-check in $O(n^2)$. The prover runs a standard solver such as MOSEK, rounds the decision matrices to $b$ bits, computes a Cholesky-like factor of $F(x) - \varepsilon I$, rounds it, and emits the residual. If the Gershgorin test fails, the prover retries with larger $b$ or a re-solve that tightens the margin. This retry loop is the prover-side analogue of the conservatism–cost trade-off the control literature already lives with.

The second component is aggregation. For fixed $(n, b)$ the relations are identical across instances, which sidesteps the uniformity limitation that folding schemes face with heterogeneous circuits. We will fold $K$ certificates with a split-accumulation design modeled on SnarkFold, in which expensive pairing checks are deferred outside the recursive loop. Instances of different sizes are padded to a small set of dimension classes.

Two structural cases get special treatment. One is a single decision matrix shared across many inequalities, as with a common Lyapunov matrix for $K$ polytope vertices or Markov modes. Here $x$ is committed once and only the $L_k, R_k$ differ. The other is network certificates, where node-level blocks are folded in a tree, following the tree-structured aggregation used in Managing Credible Anonymous Identities in Web 3.0 Services.

The third component is analysis. We will bound the tightness lost to fixed-point rounding as a function of $b$, $\varepsilon$, and the conditioning of $F(x)$. We will also characterize when a near-infeasible LMI forces $b$ to grow. This gives the infeasibility diagnostic the file notes is missing from SDP solvers: a failed Gershgorin row points to the specific block, and hence the specific subsystem or constraint, that lacks margin.

Baselines

The naive reference is the fully trusting, non-delegated check. The verifier receives all matrices and runs a floating-point Cholesky factorization of $F(x) - cI$, with $c$ chosen to cover rounding error, once per certificate. It costs about $n^3/3$ flops per instance and $K$ times that in total, with no proof size because the matrices themselves are transmitted. We will run it in double precision on the same machine, on exactly the same certificates. We expect it to remain the fastest option whenever the verifier is a capable CPU that is allowed to see the data. Our method beats it only on verifier work and communication at large $K$ and $n$, and on settings where the matrices are private or on-chain. We will report the crossover point rather than claim a blanket win.

The strongest existing method for succinct aggregated verification is SnarkFold applied to a straightforward encoding: the LMI check written as an ordinary arithmetic circuit computing $L L^{\top}$ entry by entry. That encoding costs $O(n^3)$ multiplications per instance. On SnarkFold's own Plonk benchmark, the paper reports a 0.5 KB aggregated proof verified in 4.5 ms at 4,096 proofs, against 13 KB and 38 ms for aPlonk. These are the reference numbers for our aggregation layer. We will use the same curve cycle and the same proof count so the verifier figures are directly comparable. No reported result was found on Lacuna for proving LMI or positive-semidefiniteness certificates inside any proof system, so the circuit-level comparison will be run by us, under equal hardware and an equal engineering budget.

The ablation that isolates the key ingredient keeps everything else fixed and replaces the sum-check matrix-product step with the direct cubic encoding. A second ablation replaces Gershgorin-on-residual with an exact rational $LDL^{\top}$ witness, where the diagonal factor $D$ must be shown positive. This exposes the bit-growth cost that the fixed-point design is meant to avoid. Beating the strongest baseline means at least an order-of-magnitude fewer constraints and lower prover time at $n \ge 64$, with verifier time and proof size within a small constant factor of SnarkFold's 4.5 ms and 0.5 KB at $K = 4{,}096$.

Why not just…?

Why not just have the verifier run Cholesky with a rounding margin? For a single public certificate on a laptop, this is the right answer, and we will say so in the results. It fails in three regimes that motivate the work. The first is when the LMI is built from private trajectory data, as in the two-tank dissipativity certificate of Provably Robust Verification of Dissipativity Properties from Data; there the verifier cannot see the matrices at all. The second is when verification happens on-chain or on a constrained monitor; cubic work across thousands of certificates is what aggregation removes, as with the seven-fold gas reduction reported by Linking Souls to Humans. The third is when $K$ is large enough that $K n^3$ exceeds the verifier's budget. The crossover experiment below decides where this threat ends.

Why not just put a Cholesky factorization inside a general-purpose SNARK? That is the obvious idea, and it is our second baseline. A factorization circuit contains $O(n^3)$ fixed-point multiplications, divisions, and square roots. Our design never computes the factorization in-circuit. The prover supplies it as a witness, and only the product identity is checked, at $O(n^2)$ cost. The ablation measures exactly this gap. If the gap were small at realistic $n$, the proposal would collapse to an engineering note, and we would report that.

Why not just solve faster with first-order methods or prune the model so the LMI is small? These attack the solver, not the verifier, and they are complementary to our approach. Our prover may well use a splitting method. The fixed-point rounding with an explicit margin is in fact what makes low-precision first-order solutions safe to certify, since slightly indefinite outputs simply fail the Gershgorin test instead of being silently accepted. Pruning or truncation helps with size but has known costs. SafEDMD's error bound depends on the lifting capturing the dynamics. The bilinear feedback paper reports that ignoring the network's nonlinearities "exhibited poor performance or failed to maintain stability."

Proposed Experiments

Correctness and tightness come first, measured on the benchmarks in the file. On the two-tank data we will check whether the certified bounds survive rounding. The floating-point certificate gives $\hat\gamma = 7.92$ and $\hat\rho = -0.99$, and the decisive check is whether the proof-carrying certificate stays within a few percent of these at moderate $b$. On the Duffing oscillator Neural ODE we will prove that the perturbed 128-dimensional weights are dissipative; the reported perturbation norm is 1.4443. On the 4D bilinear neural feedback loop the reported region-of-attraction trace is 0.1959, and on the SafEDMD inverted pendulum the solve finishes in under one second on a laptop. In each case we report the smallest $b$ at which the certificate verifies and the resulting loss in $\gamma$, decay rate, or region-of-attraction trace.

Scaling comes second. We will use random stable systems and SafEDMD-style lifted models with $n$ from 8 to 512, and data-driven dissipativity LMIs with growing trajectory length. For each we measure prover time, constraint count, and memory, the last because of the known prover-memory limit of folding schemes. The sum-check design should grow quadratically in $n$, while the direct-encoding baseline should grow cubically.

Amortization comes third. We fold $K$ from 1 to 4,096 certificates in three configurations: independent systems, polytopic vertices sharing one Lyapunov matrix, and a tree-aggregated network of node certificates. We report verifier time and proof size against SnarkFold's reported 4.5 ms and 0.5 KB. We also report the $K$ and $n$ at which total verifier work drops below $K$ floating-point Cholesky factorizations.

A soundness stress test closes the study. Adversarial provers submit certificates for systems with one unstable mode, or with one marginally violating vertex out of 4,096. Every such batch must be rejected, while all honestly rounded certificates near the feasibility boundary must still be accepted.