When a design house cannot trust the foundry that builds its fastest chip, one answer is to make the fast chip prove its work. Verifiable ASICs builds such a system, called Zebra. An untrusted 7nm "prover" chip computes a result together with an interactive proof of correctness. A slow 350nm "verifier" chip, made in a trusted onshore fab, checks that proof. Zebra reports 2–3× better area-adjusted throughput than running the same Number Theoretic Transform workload on the trusted 350nm chip alone. The proof guarantees that a wrong answer will be caught. It guarantees nothing about when an answer arrives. A tampered prover cannot forge results, but it can stall, or send a proof that fails only in its last round after the verifier has already spent its checking time. In a control loop with deadlines, a missed deadline is as bad as a wrong answer.
This proposal treats the trusted verifier as what it really is: a single slow processor. On it, proof checking, fallback recomputation and purely local tasks all compete for one timeline. The untrusted prover's promised completion times then play the role of untrusted predictions in the sense of Scheduling with Untrusted Predictions. The goal is a scheduler for the trusted chip with two properties. First, it keeps every designated hard deadline no matter what the prover does. Second, it recovers most of Zebra's throughput gain when the prover is honest. In between, its performance degrades in proportion to how many times the prover misbehaves.
Core Claim
Three claims define the contribution. First, a hard guarantee against an adversarial prover forces a strict accounting on the trusted chip. Every offloaded job must carry a reserved fallback cost of verification time $V_i$ plus local recomputation time $C_i$. The prover may waste the verification and then force the fallback, so an attacked job costs more than simply running it locally. This means unconditional offloading is never safer than staying local. Second, the proof system does let the trusted chip tell two kinds of misbehavior apart. An invalid proof is cryptographic evidence of a faulty prover. A late proof is not, because benign I/O jitter looks the same, and Zebra depends on 3D stacking and high-bandwidth I/O.
Third, building on that distinction, a trust budget scheduler beats both the fully robust and the fully optimistic policies across a measurable range of adversary strength. The trust budget is a reserved amount of fallback capacity per time window that offloading may spend. The scheduler offloads only while unspent budget covers the worst-case fallbacks of the jobs currently in flight. It stops offloading permanently after a proof is proven invalid. Lateness only drains the budget for the current window.
Concretely, let a task set on the trusted chip have hard tasks with local utilization $U_H$ and offloadable tasks with verification utilization $U_V$. Let $B$ be the fallback budget, written as a utilization fraction. Our target schedulability condition under preemptive earliest-deadline-first (always run the job with the nearest deadline) is
$$U_H + U_V + B \le 1,$$
with $B$ sized so that at most $k$ adversarial fallbacks per window are absorbed. The quantity we analyze is how honest-case throughput and missed soft deadlines scale with the number $\eta$ of adversarial events. We expect a degradation linear in $\eta$, analogous to the $1 + 2\eta/n$ bound for Preferential Round Robin in Scheduling with Untrusted Predictions. The linear form is expected because each adversarial event costs a bounded amount of trusted-chip time, $V_i + C_i$.
Where This Sits
The motivating gap comes straight from Zebra. That paper treats proof latency as a fixed pipeline parameter. Its verifier also depends on precomputed auxiliary inputs, and it never models periodic tasks or deadlines. We keep its proof protocol and its cost model unchanged. We add the timing threat and a scheduler to handle it.
The scheduling machinery comes from the learning-augmented line. Scheduling with Untrusted Predictions shows how to blend a prediction-following policy with a robust fallback so that performance tracks prediction error. However, it assumes free preemption and no deadlines. Contract Scheduling with Distributional and Multiple Advice gives consistency–robustness bounds when advice comes from untrusted experts. Its interruptible-contract model does not fit proof checking, because a half-checked proof is worth nothing. We therefore borrow the robustness/consistency style of analysis, not the algorithms.
Two security–scheduling hybrids are close in spirit but assume trusted silicon. Opportunistic Data Flow Integrity spends the slack between worst-case and actual execution time on security checks, cutting full integrity checking's 184% worst-case overhead to 2.7%. SchedGuard inserts protection windows into a uniprocessor schedule. Both are evidence that security work can be folded into real-time budgets. Neither faces a co-processor whose timing is chosen by an adversary.
Two hardware papers constrain the threat model. RTL-Breaker shows that functionally correct but slower circuits pass verification. A degraded prover therefore cannot be ruled out at design time, which supports modeling slow-but-correct behavior separately from forged results. TrojanSAINT reports 78% true-positive detection without a golden reference. Pre-silicon screening therefore leaves room for a misbehaving prover in the field.
Research Program
The first step is a model. Following Zebra's layer-by-layer interaction, each offloaded job becomes a chain of verifier segments on the trusted chip. Each segment is released when a prover message arrives. In real-time terms this is a self-suspending task: a task that pauses while waiting on an external device. Here the suspension lengths are controlled by the adversary and capped by a timeout. We will derive the schedulability condition when timeouts are set at the latest point that still leaves room for fallback within the reserved budget.
We will also prove a lower bound. No online policy can guarantee all hard deadlines against an unbounded adversary while using less trusted capacity than trusted-only execution plus $V$ for in-flight jobs. This bound makes precise why hard tasks must be schedulable locally. It also identifies where offloading genuinely pays off: soft and throughput tasks, plus energy and slack.
The second step is the trust-budget scheduler. Its two-channel attribution rule is that invalid proofs disable offloading and lateness drains the per-window budget. We will analyze it for consistency (honest-case throughput relative to Zebra) and robustness (hard deadlines always met). We will also analyze degradation in $\eta$.
The third step is an evaluation. It uses Zebra's analytical cost model, which its authors confirmed within 11% of RTL simulation, to set prover and verifier times. We need no new silicon.
Baselines
The naive reference point is trusted-only execution: every job runs on the 350nm chip under earliest-deadline-first. It is fully robust by construction. Zebra already quantifies its cost: the offloaded system achieves 2–3× area-adjusted throughput on NTT and about 2× on Curve25519 (Verifiable ASICs). Those figures are the ceiling on what offloading can recover.
The strongest optimistic competitor is Zebra-style offloading with a fixed per-job timeout and local fallback, scheduled by earliest-deadline-first, with no budget accounting. It captures Zebra's honest-case gain and is what a practitioner would deploy. No reported result on Lacuna exists for the deadline behavior of Zebra under a stalling prover, so we will establish that number ourselves.
The strongest robust competitor is static full reservation. Every offloaded job reserves $V_i + C_i$ on the trusted chip, in the style of mixed-criticality scheduling. It is always safe, but it tends to forfeit throughput.
The key ablations are the trust-budget scheduler without attribution (stalls and invalid proofs treated identically) and with the budget fixed at zero (one-strike). All policies run on the same generated task sets, the same Zebra-derived costs and the same adversary strategies. Each policy gets an equal tuning sweep over its own timeouts and budgets.
Beating the baselines means two things. The trust-budget scheduler must meet 100% of hard deadlines in every adversarial run, as full reservation does. With an honest prover, it must recover a substantially larger share of Zebra's throughput gain than full reservation does. Under the stalling adversary, it must miss fewer soft deadlines than fixed-timeout offloading.
Why not just…?
Why not just run a fixed timeout and fall back locally? Each job's timeout is set in isolation. An adversary that stalls many jobs at once forces several fallbacks into the same window, and their summed local work can exceed the trusted chip's capacity even though each job alone looked feasible. The burst-stall adversary experiment below measures exactly this.
Why not just disable the prover after the first failure? This is the real threat to the proposal. Against invalid proofs it is essentially our rule. Against lateness it may also be good enough if benign jitter is rare. If honest-case jitter almost never trips the timeout, one-strike will match the budget scheduler. In that case the contribution narrows to the schedulability analysis and the lower bound. The experiments settle this by sweeping a benign jitter distribution and measuring how often one-strike needlessly discards the prover's throughput.
Why not just screen the prover chip before deployment and trust it? Screening is imperfect. TrojanSAINT reaches 78% true-positive rate in practical settings. RTL-Breaker shows that slow-but-correct circuits pass functional checks, and foundry-level tampering happens after the netlist stage. The whole reason to use Zebra is that the prover is not trusted. A scheduler that assumes it is honest discards that premise.
Proposed Experiments
We will generate synthetic task sets in the style of the 1,000,000-task-set study in SchedGuard and the 500-set utilization sweeps in Restart-Based Fault-Tolerance, with periods from 10 to 1000 time units. A controllable fraction of tasks will be offloadable NTT or Curve25519 jobs, with prover time, verifier time and local time taken from Zebra's cost model. The hard-task utilization and the offloadable fraction will both be swept.
The adversaries are an honest prover with benign I/O jitter, a burst-stall adversary that delays all in-flight proofs simultaneously, a last-round-invalid adversary, and an adaptive adversary that stalls just below the timeout to drain the budget. The metrics are the hard-deadline miss rate (which must be zero), the soft-deadline miss rate, and honest-case throughput as a fraction of Zebra's reported gain. We will also measure throughput as a function of the number of adversarial events $\eta$ and check it against the predicted linear degradation.
Two decisive checks frame the outcome. The first is whether fixed-timeout offloading actually misses hard deadlines under burst stalls at realistic utilizations. If it never does, the threat is weaker than claimed. The second is whether the budget scheduler beats one-strike under benign jitter. If it does not, we report that the simpler rule suffices and keep the analysis as the contribution.
References
- Verifiable ASICs
- Scheduling with Untrusted Predictions
- Contract Scheduling with Distributional and Multiple Advice
- Opportunistic Data Flow Integrity for Real-time Cyber-physical Systems Using Worst Case Execution Time Reservation
- SchedGuard: Protecting against Schedule Leaks Using Linux Containers
- RTL-Breaker: Assessing the Security of LLMs Against Backdoor Attacks on HDL Code Generation
- TrojanSAINT: Gate-Level Netlist Sampling-Based Inductive Learning for Hardware Trojan Detection
- Restart-based fault-tolerance: System design and schedulability analysis