💻 computer science

Safety and Liveness of Cross-Domain State Preservation under Byzantine Faults: A Mechanized Proof in Isabelle/HOL

This paper presents a mechanized Isabelle/HOL proof establishing both safety and liveness guarantees for cross-domain regulatory state preservation under Byzantine faults, utilizing a reusable framework of seven generic locales instantiated against a comprehensive model of global financial regulatory requirements.

Original authors: Jinwook Kim

Published 2026-06-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jinwook Kim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where digital assets (like tokenized stocks or real estate) can move freely between different "neighborhoods" (blockchains) and "paper ledgers" (off-chain systems). The problem is: if a judge in Neighborhood A freezes an asset, that freeze must happen instantly and perfectly in Neighborhood B, Neighborhood C, and the paper ledger, too. If it doesn't, bad actors could play "regulatory arbitrage," hiding assets in places where the rules aren't enforced.

This paper is a mathematical proof that a specific system for moving these assets is both safe (it never makes mistakes) and alive (it never gets stuck), even if some participants are trying to sabotage it.

Here is the breakdown using simple analogies:

1. The Goal: The "Perfect Relay Race"

Think of the system as a relay race where the baton is a "regulatory status" (like "Frozen" or "Active").

The Challenge: When one runner (a blockchain) changes the baton's color, every other runner on the team must instantly see the same color.
The Risk: If one runner lies, forgets, or gets stuck, the whole race could stop, or the baton could end up being two different colors at the same time.

2. The Two Big Wins (Safety and Liveness)

The authors proved two things about their system:

A. Safety: The "Unbreakable Mirror"

What it means: If the system works, the result is always consistent. If Chain A says "Freeze," Chain B must say "Freeze." There is no ambiguity.
The Analogy: Imagine a set of magic mirrors. If you put a red ball in front of Mirror A, Mirror B, Mirror C, and the paper log all show a red ball. They never show a blue ball, and they never disagree.
The Proof: The authors built a "map" (called a locale) that proves this mirroring happens perfectly, even if the chains speak different languages (different technical vocabularies) or if the asset is moving between a blockchain and a paper database. They proved that no matter how you shuffle the order of operations, the final picture is always the same.

B. Liveness: The "Anti-Stuck Mechanism"

What it means: The system never freezes up, even if some participants are "Byzantine" (a fancy word for malicious or broken nodes that lie, delay messages, or refuse to let go of assets).
The Analogy: Imagine a group of people trying to pass a heavy box through a narrow hallway.
- The Problem: A bad actor might grab the box and refuse to let go, blocking everyone else.
- The Solution: The system has a built-in "timeout" (like a spring-loaded trapdoor). If someone holds the box too long, the system automatically pries it out of their hands and passes it to the next person.
- The Proof: They mathematically proved that even if up to 1/3 of the people are trying to block the hallway, the box will always eventually get through. No asset will ever be locked forever.

3. The "Magic Trick": Combining the Two

Usually, safety proofs assume everyone is honest. Liveness proofs assume some people are bad.

The Paper's Trick: They combined the two. They showed that the "Anti-Stuck Mechanism" (Liveness) is so strong that it fixes the "Honest People" assumption required for the "Unbreakable Mirror" (Safety).
The Result: You don't need to trust anyone. Even with bad actors, the system is guaranteed to be consistent and moving.

4. The Toolkit: "Lego Bricks" for Math

The authors didn't just prove this for one specific blockchain. They built 7 reusable "Lego bricks" (called locales in Isabelle/HOL).

How it works: These bricks are generic. You can snap them onto any system (a bank, a supply chain, a game) to instantly get the same safety and liveness guarantees.
Real-world tests: They didn't just leave the bricks in the box. They snapped them onto three very different, real-world scenarios to prove they work:
1. Different Languages: A chain that only speaks "Freeze" vs. a chain that speaks "Freeze" and "Unfreeze."
2. Different Worlds: A blockchain vs. a complex off-chain legal document (DAML).
3. The Consensus Engine: The specific voting mechanism used to decide who moves next.

5. What This Is NOT

To be clear about the paper's limits:

It does not check if a specific judge actually has the legal right to freeze an asset. It only checks that if a freeze is ordered, it happens correctly everywhere.
It does not prove the computer code (Rust/Solidity) is bug-free; it proves the mathematical model of the system is sound.
It does not handle the chaos of a network that is constantly adding or removing new chains while running (that's future work).

Summary

This paper is a mathematical certificate of trust. It says: "We have built a system where regulatory rules (like freezing assets) are enforced perfectly across different worlds. Even if some participants try to break it, the system has a self-correcting mechanism that ensures the rules are followed and the system never gets stuck."

They did this by writing 3,215 lines of code in a proof assistant (Isabelle/HOL) that a computer checked step-by-step to ensure there are no logical holes.

Technical Summary: Safety and Liveness of Cross-Domain State Preservation under Byzantine Faults

1. Problem Statement

The paper addresses the critical challenge of guaranteeing the consistency of regulatory compliance states for tokenized assets operating across heterogeneous blockchain networks and off-chain ledgers. Without formal guarantees, regulatory arbitrage becomes structurally possible; for instance, a freeze order issued in one jurisdiction must be immediately and deterministically reflected across all connected domains.

The problem is decomposed into two dimensions:

Safety: Ensuring that if a synchronization is performed, the resulting state is consistent across all domains with structural preservation.
Liveness: Ensuring that in a decentralized environment containing Byzantine nodes (malicious actors), the synchronization process actually proceeds, avoiding deadlocks and starvation.

Prior work has not formally verified both properties simultaneously in a single framework, nor has it verified regulatory-specific consensus properties (such as priority determinism and asset deadlock freedom) using Isabelle/HOL.

2. Methodology

The authors employ a mechanized proof approach using Isabelle/HOL. The development consists of 3,215 lines of code across four theory files, building without sorry or oops (unproven assumptions).

2.1 System and Threat Models

System Model: The system comprises a finite set of domains (chains/ledgers) sharing a state machine structure. Synchronization is modeled as an atomic operation involving verification, validation, lock acquisition, state update, and lock release.
Threat Model:
- Property 1 (Safety): Initially assumes honest nodes and reliable channels.
- Property 2 (Liveness): Relaxes the honest-node assumption to allow up to $f < n/3$ Byzantine nodes. Byzantine nodes may withhold lock releases or act maliciously.
- Combined: Property 2 discharges the honest-node assumption of Property 1, yielding an unconditional guarantee.

2.2 Regulatory State Transition Model

The formal model is based on the Regulatory Compliance Protocol (RCP) framework, which systematizes 31 requirements from 15 global financial authorities.

States: Five regulatory states (ACTIVE, FROZEN, SEIZED, CONFISCATED, RESTRICTED).
Actions: Seven regulatory actions (FREEZE, SEIZE, CONFISCATE, RESTRICT, UNFREEZE, UNRESTRICT, RELEASE).
Constraints: The model enforces specific legal constraints, such as the exclusion of "SEIZED → FROZEN" transitions (as seizure is a stronger legal constraint than freezing) and the terminal nature of the CONFISCATED state.

2.3 Verification Infrastructure: Generic Locales

The core methodology relies on defining seven generic, domain-independent locales in Isabelle/HOL. These locales serve as reusable verification infrastructure. Theorems proven within these locales are automatically inherited by any concrete domain that instantiates them via Isabelle's interpretation mechanism.

Safety Locales (4):
1. state_machine: Defines finite states, actions, and deterministic transitions.
2. state_preservation: Establishes a naturality condition where synchronization commutes with state transitions (homomorphism).
3. symmetric_state_preservation: Adds inverse maps to guarantee bidirectional roundtrip preservation.
4. multi_domain_preservation: Generalizes consistency to an arbitrary finite set of domains ( $N$ -domain consistency) and ensures per-asset isolation.
Liveness Locales (3):
1. priority_system: Guarantees deterministic selection of actions via injective priorities.
2. deadlock_free_locking: Ensures no resource is locked indefinitely via timeout-based forced release.
3. fair_leader_system: Guarantees starvation freedom under periodic honest leader scheduling.

3. Key Contributions

3.1 Mechanized Safety Proof (Property 1)

The paper extends the Merkle Functor pattern (previously limited to unidirectional data integrity in a single domain) to a cross-domain, bidirectional, and multi-domain framework.

Bidirectional Roundtrip: Proves that state transitions are faithfully reflected in both directions between domains.
N-Domain Consistency: Proves that after a synchronization on one domain, all connected domains reach the same resulting state.
Per-Asset Isolation: Proves that synchronization on one asset does not affect the state of other assets.
Concrete Instantiations: The authors provide concrete witnesses to ensure the locales are not vacuously satisfied:
- Escalation Instance: A heterogeneous-action instance where one chain supports only escalation actions (FREEZE, SEIZE, etc.) while the other supports the full set, proving structural preservation across differing vocabularies.
- Layer-Crossing Instance: A bidirectional bridge between an on-chain reg_state enum and an off-chain DAML permission record, proving injectivity and no information loss.

3.2 Mechanized Liveness Proof (Property 2)

This is the first use of Isabelle/HOL alone to verify BFT consensus liveness in a blockchain context.

Determinism: Conflicting regulatory actions are resolved via a total order on priority keys (authority level, timestamp, severity, node ID).
Deadlock Freedom: Proves that even if Byzantine nodes withhold lock releases, the timeout mechanism ensures the lock expires within a bounded time.
Starvation Freedom: Proves that under a fairness bound (guaranteeing an honest leader within $k$ epochs), all pending requests are eventually processed.

3.3 Assumption Discharge (Combined Guarantee)

The paper demonstrates an assume-guarantee reasoning pattern. Property 2 discharges the "honest-node" assumption required by Property 1. By proving that the system remains live and deterministic even with Byzantine faults ( $f < n/3$ ), the conditional safety guarantee is promoted to an unconditional guarantee: cross-domain state preservation holds even in the presence of Byzantine nodes.

4. Results and Artifacts

Proof Artifacts: The development includes eight concrete locale interpretations (covering all seven generic locales) alongside a parametric multi-domain instantiation.
Regulatory Model: The model covers 31 regulatory requirements mapped to 5 states and 7 actions.
Availability: All artifacts are publicly available on GitHub and have been submitted to the Archive of Formal Proofs (AFP) for review.
Design Guide: The proofs yield specific parameter constraints for implementation (e.g., $n \ge 3f + 1$ , positive timeouts, fairness bounds) that translate directly into mathematical design rationale for decentralized sequencers.

5. Significance and Claims

The paper claims significance in three primary areas:

Novelty in Formal Verification: It is the first work to formally verify both safety and liveness simultaneously for cross-domain regulatory state transitions. It is also the first to verify regulatory-specific consensus properties (priority determinism, regulatory asset deadlock freedom) in any tool.
Methodological Advancement: By utilizing a hierarchy of generic locales, the authors provide a reusable verification infrastructure that is domain-independent. This allows the same safety and liveness proofs to be applied to arbitrary domains (e.g., DeFi, distributed databases) simply by instantiating the locales.
Bridging Theory and Practice: The work moves beyond abstract consensus verification (like agreement/validity) to address domain-specific regulatory constraints. It explicitly bridges the gap between a theoretical state machine and a regulatory compliance model, providing a "design guide" for implementation parameters derived directly from the proofs.

The authors explicitly note limitations: the model does not verify chain-specific characteristics (gas, block times), does not prove formal refinement to Rust/Solidity code, and assumes a closed system (dynamic request arrival is future work). The current framework establishes the foundational locales and instances but does not yet formalize category-theoretic functor laws (identity and composition), which are reserved for future work to achieve full "functor" status.