Recursive invariants improve staged transaction workflows in UTXO blockchains
Staged Multi-step UTXO Workflows via Recursive Invariants
Cryptography and Security
Summary
Transactions in some blockchain systems rely on outputs becoming inputs for future steps, which can cause problems if multiple people try to spend the same outputs at once. This paper presents a new way to write rules that check these multi-step transactions step-by-step without needing complex off-chain coordination. Their method uses a small programming language that allows some checks to be deferred until the information is available, keeping transaction validation local and efficient. The authors built tools to test their idea and showed it works well for several common scenarios.
What this means in practice
- •For blockchain protocol developers: Implement multi-step transaction workflows with built-in local consistency checks to reduce off-chain coordination overhead and latency.
- •For smart contract engineers: Use the recursive invariant framework to design staged contracts that maintain correctness without shared mutable state or complex re-computation.
Authors
Shuyang Tang, Sherman S. M. Chow, Hongfei Fu, Zihan Guo, Guoqiang Li
Abstract
Stateless UTXO-style execution validates transactions using local and referenced data, enabling parallel validation and predictable serialized-size/weight accounting. Multi-step workflows thread state across outputs, and a prepared next-step transaction may become stale if another valid spend confirms first. Explicit state threading therefore shifts consistency maintenance, off-chain tracking, and transaction rebuilding to the protocol boundary, increasing coordination cost and latency. Recursive invariants (RIs), our proposed transaction-level logic and toolchain, address this gap by expressing workflow rules as transaction-level predicates over a transaction's inputs and indexed successor positions referenced by the RI. An accepted transaction realizing such a successor position re-checks the predecessor's RI one step later, carrying the workflow rule forward without shared mutable application state or executable output logic. Thus, multi-step protocol rules preserve validation-time locality and admit explicit cost accounting, while cross-transaction guarantees arise from repeated one-step checking. Not all successor clauses are checkable at validation time, so our small statically typed domain-specific language (DSL) uses three-valued semantics (true, false, unknown) to defer future-dependent obligations until checkable. Co-designed with this DSL, our framework formalizes UTXO validation and ledger extension, identifies the validation-time-evaluable one-step fragment, and proves the deduction system sound w.r.t. the three-valued semantics. We give validation and ledger-extension algorithms for this model. We implement a prototype RI interpreter and benchmarking toolchain for six workloads. Six practice-motivated case studies exhibit roughly linear cumulative validation-cost proxy growth and illustrate staged workflow constraints without preconstructing each successor.