Safety and Liveness of Cross-Domain State Preservation under Byzantine Faults: A Mechanized Proof in Isabelle/HOL
Jinwook Kim (for the Oraclizer Core Team) · 2026
Read Safety and Liveness of Cross-Domain State Preservation under Byzantine Faults: A Mechanized Proof in Isabelle/HOL by Jinwook Kim (for the Oraclizer Core Team) (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-03844.txt.
Introduction
Jinwook Kim mechanized cross-domain state preservation in Isabelle/HOL as a functor. The goal is simple: a freeze, seizure, or confiscation on a tokenized asset must hit every domain holding it or none at all. State machines serve as objects and synchronization maps as morphisms, with identity, composition, and associativity as theorems. Safety, liveness under bounded Byzantine faults, convergence from arbitrary states, and a hierarchy of functors follow. Ten theory files build cleanly, with the refinement to code still unproven.
Catalog record
| CREATOR | Jinwook Kim (for the Oraclizer Core Team) |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42274 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.03844
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Safety and Liveness of Cross-Domain State Preservation under Byzantine Faults: A Mechanized Proof in Isabelle/HOL Jinwook Kim (for the Oraclizer Core Team) Abstract Formally guaranteeing the safety and liveness of regulatory state transitions in cross-domain state synchronization systems is a problem of growing importance as tokenized assets are increasingly operated across heterogeneous blockchain networks and off-chain ledgers. This paper presents a mechanized proof of 2,348 lines in Isabelle/HOL establishing two complementary properties. First, cross-domain state preservation (safety): a regulatory state transition performed on one domain is faithfully reflected across all connected domains with structural preservation. This guarantee encompasses bidirectional roundtrip preservation, consistency across an arbitrary finite set of domains, and per-asset isolation. Second, liveness under Byzantine faults: in the presence of up to f < n / 3 f<n/3 Byzantine nodes, we prove deterministic resolution of conflicting regulatory actions, deadlock freedom, and starvation freedom. In the combination of these two properties, the liveness proof discharges the honest-node assumption of the safety proof under Byzantine faults, promoting conditional safety to an unconditional guarantee. The seven generic locales derived in this process are domain-independent and reusable for arbitrary domains via Isabelle/HOL’s interpretation mechanism. The application context is a regulatory state transition model based on the RCP framework (arXiv:2603.29278), which systematizes 31 requirements from 15 global financial regulatory authorities. All proof artifacts build in Isabelle/HOL without sorry or oops , have been submitted to the Archive of Formal Proofs (under review), and are publicly available on GitHub. 1 Introduction Guaranteeing the consistency of regulatory compliance states is a fundamental challenge when tokenized assets operate across multiple blockchain networks and off-chain ledgers. When an asset freeze order is issued in one jurisdiction, it must be reflected immediately, deterministically, and with structural preservation across every domain where that asset exists. Without this guarantee, regulatory arbitrage becomes structurally possible. This problem involves two independent dimensions. The first is safety : if synchronization is performed correctly, is the resulting state consistent across all domains? The second is liveness : in a decentralized environment with Byzantine nodes, does synchronization actually proceed—that is, does the system avoid halting and does no asset remain permanently locked? No prior work has formally verified both properties simultaneously. Lochbihler and Marić’s Merkle Functor pattern [ 1 ] formalized authenticated data structures within the Canton protocol in Isabelle/HOL, but its scope is limited to unidirectional data integrity within a single domain; it addresses neither cross-domain state preservation nor Byzantine environments. Velisarios [ 2 ] verified PBFT’s safety in Coq, but liveness was out of scope. Byzantine consensus liveness has been verified in various tools including TLA+, Coq, and model checkers [ 3 , 4 ] , but to the best of our knowledge, no prior work has used Isabelle/HOL alone to verify BFT consensus liveness in a blockchain context. No prior work in any tool has formally verified regulatory-specific consensus properties such as priority determinism, regulatory asset deadlock freedom, and regulatory request starvation freedom. Our contributions are as follows: 1. Seven generic locales as reusable verification infrastructure. We define four locales for safety ( state_machine , state_preservation , symmetric_state_preservation , multi_domain_preservation ) and three for liveness ( priority_system , deadlock_free_locking , fair_leader_system ). These locales are domain-independent: instantiating them via Isabelle/HOL’s interpretation mechanism for any conforming domain type automatically inherits all proven properties. 2. Mechanized verification of bidirectional, multi-domain cross-chain state preservation. We extend the Merkle Functor pattern from a single domain to bidirectional roundtrip guarantees, N -domain consistency, and per-asset isolation, unifying all three in a single locale hierarchy. 3. Mechanized verification of regulatory consensus properties under Byzantine faults. To the best of our knowledge, this is the first use of Isabelle/HOL alone to verify BFT consensus liveness in a blockchain context. The formal verification of regulatory-specific consensus properties is without precedent in any tool. 4. Safety–liveness combination via assumption discharge. The liveness proof discharges the honest-node assumption of the safety proof under Byzantine faults ( f<n/3 ), promoting conditional safety to an unconditional guarantee. This is an instance of assume-guarantee reasoning. 5. Implementation design guide. Parameter constraints derived from the proofs ( n\geq 3f+1 , positive timeout, fairness bound) translate directly into mathematical design rationale for a decentralized sequencer implementation. The application context is a regulatory state transition model based on the RCP (Regulatory Compliance Protocol) framework (arXiv:2603.29278) [ 5 ] , which systematizes 31 requirements from 15 global financial regulatory authorities into five regulatory states and seven regulatory actions. This paper introduces the regulatory state transition model self-contained; detailed regulatory justifications are deferred to [ 5 ] . All proof artifacts comprise four Isabelle/HOL theory files totaling 2,348 lines, building without sorry or oops . The artifacts have been submitted to the Archive of Formal Proofs (AFP) and are under editor review [ 6 ] ; they are publicly available on GitHub [ 7 ] . The remainder of this paper is structured as follows. Section 2 defines the system model and threat model. Section 3 introduces the regulatory state transition model. Section 4 presents the cross-domain state preservation proof (Property 1, safety). Section 5 presents the liveness proof under Byzantine faults (Property 2). Section 6 analyzes the combination of both properties through assumption discharge. Section 7 surveys related work. Section 8 discusses limitations, and Section 9 concludes. 2 System Model and Threat Model 2.1 System Model The formal model comprises the following elements. Domains. A finite set of domains (chains) \mathcal{D} . Each domain shares the same state machine structure. A domain abstracts a blockchain network, an off-chain ledger, or any system supporting state transitions. State transitions. A deterministic partial function: \delta:S\times A\rightarrow S_{\bot} (1) where S is a finite state set, A is a finite action set, and S_{\bot}=S\cup\{\bot\} . The same (state, action) pair always yields the same result. Terminal states T\subseteq S return \bot for all transitions. Per-asset locking. Preemptive locking at the asset_id granularity. Lock acquisition and release are atomic. Each synchronization operation holds at most one lock on one asset (single-resource locking). Synchronization. The sync function executes atomically: (1) verify the asset exists on the source chain, (2) validate the transition, (3) acquire a lock, (4) update all connected chains, (5) release the lock. If any step fails, the entire operation returns None . Communication. The safety proof (Property 1) assumes reliable channels. Message loss, duplication, and reordering are outside the model. Extending to a partially synchronous network model remains an open problem. Global state. Formalized in Isabelle/HOL as: ⬇ record global_state = gs_chains :: "chain_id \Rightarrow chain_state" gs_locks :: "asset_id \Rightarrow bool" where chain_state = asset_id \Rightarrow asset_state option and asset_state is a record containing the asset identifier, regulatory state, owner, and lock status. Global validity. Defined as the conjunction of two conditions: ⬇ definition valid_state :: "global_state \Rightarrow bool" where "valid_state gs \equiv consistent_state gs \wedge no_locked_without_reason gs" consistent_state requires that all chains holding the same asset agree on its regulatory state. no_locked_without_reason requires that no asset is locked in quiescent states. 2.2 Threat Model Property 1 (Safety). All nodes follow the protocol honestly. Concurrent regulatory actions are serialized via preemptive locking. Network delays and Byzantine behavior are out of scope. Property 2 (Liveness). The honest-node assumption of Property 1 is relaxed. Up