CATs: Secure Blockchain Interoperability with Cross-chain Atomic Transactions

Source: arXiv:2607.05387 · Published 2026-07-06 · By Andreas Penzkofer, Franck Cassez

TL;DR

This paper addresses the fundamental challenge of achieving atomicity and interoperability across independent blockchains in the presence of asynchronous communication delays and Byzantine actors. Traditional blockchain architectures lack a mechanism for executing cross-chain transactions atomically, resulting in risks of partial failure and inconsistent states. The authors propose the CATs protocol, a system that enables atomic, composable cross-chain transactions (CATs) by coordinating multiple blockchains through a shared coordination layer. This layer includes sequencers, transaction processors, a coordinator, and a confirmation mechanism which collectively ensure that either all or none of a CAT's component transactions are committed across chains. The design preserves chain autonomy by allowing each blockchain to maintain its own execution semantics while participating in coordinated multi-chain operations.

The protocol advances prior approaches by explicitly embedding causal dependency tracking, transaction postponement rules, and sophisticated timeout and dependency-depth bounds to balance liveness guarantees and minimal blocking. Formal analysis establishes strong safety and liveness properties, proving that independent transactions can proceed without blocking while dependent transactions incur only bounded delays. Through simulation under realistic network latencies, adversarial conditions, and varying CAT traffic volumes, the authors demonstrate that CATs achieve high success rates and efficient latency trade-offs, outperforming prior estimations of cross-chain atomicity feasibility. Overall, CATs provide a practical, deterministic foundation for secure blockchain interoperability without requiring speculative rollbacks or sacrificing decentralization.

Key findings

• CATs protocol ensures atomicity of cross-chain transactions even under Byzantine faults and asynchronous communication by coordinating execution and confirmation across chains.
• The protocol separates transactions into accepted and postponed sets, resolving outcomes within a few coordination rounds to minimize blocking.
• Timeouts and dependency-depth bounds guarantee liveness, ensuring all cross-chain transactions finalize within bounded time, preventing indefinite blocking.
• Simulation results show high CAT success rate when cross-chain transactions compose a modest fraction of block traffic (specific success rates in Fig. 6 and 7).
• Independent transactions experience minimal blocking delays, while dependent transactions suffer bounded, characterized latencies (see Fig. 8).
• The protocol preserves chain autonomy by allowing each blockchain to keep its own VM and execution semantics, coordinating only at the confirmation layer.
• CAT dependency depth metric limits exponential state branching by bounding pending cross-chain transaction dependencies, improving scalability.
• Formal proof establishes strong correctness (safety) and liveness of the protocol under asynchronous, Byzantine assumptions (Sec. V).

Threat model

Adversaries are Byzantine actors capable of arbitrary faults including message delays, reordering, and equivocation. They may attempt to desynchronize chains, cause partial execution of CATs, or introduce conflicting transactions. However, individual blockchains are assumed correct with finality guarantees, and the coordination layer has authenticated consensus ensuring resilience against equivocation. The adversary cannot violate cryptographic assumptions or directly force atomic commit inconsistencies without breaking the coordination protocol.

Methodology — deep read

1. Threat Model & Assumptions: The adversary is Byzantine and can cause arbitrary delays, message losses, and equivocations. However, blockchains are assumed to be correct individually with finality guarantees, and the coordination layer relies on a shared consensus mechanism with authentication to prevent equivocation. There is no trusted direct interchain communication, so the system must coordinate atomically without relying on synchronous channels.

2. Data & Model Setup: The authors construct a formal model of cross-chain transactions as pairs of transactions executed on two blockchains (generalizable to more). Each blockchain maintains state as a map of keys to values. Transactions have well-defined change sets and memory traces (reads/writes). Dependencies—read-write and write-write—between transactions are formally defined to capture causal relationships and concurrency constraints. CATs involve coordinating pairs of dependent transactions across chains.

3. Architecture & Protocol: CATs introduce a shared coordination layer comprising sequencers that order transactions, transaction processors that simulate and compute change sets, a coordinator that collects and confirms combined outcomes, and a confirmation layer that synchronizes commits across chains. Transactions are split into accepted and postponed sets based on dependencies. The protocol applies dependency tracking to allow independent transactions to execute out of order and avoid unnecessary blocking. Timeouts and bounded dependency-depth limits ensure progress and prevent cascading delays.

4. Training/Implementation Regime: While no ML training occurs, the protocol evaluation uses simulation with varying CAT traffic rates, network delays, and contention levels. The dependency graphs utilized in the protocol ensure bounded complexity and scalability by capping pending CAT dependency depth.

5. Evaluation Protocol: Metrics include CAT success rate (fraction of CATs fully committed), transaction latency (blocking and overall duration), and throughput. Baselines include uncoordinated cross-chain execution (no atomicity) and fully serialized blocking. Simulation assesses performance under varying numbers of CATs per block, chain delays, and contention. They explore the trade-off between CAT lifetime bounds and latency.

6. Reproducibility: The paper describes formal models and algorithms in detail but does not provide a public codebase or dataset, relying on simulation methodology specified in the evaluation section. Some details on exact simulator implementations or seeds are not specified.

Example end-to-end: Consider a pair of chains and a CAT involving Bob sending tokens to Charlie on Chain 1, and Charlie sending tokens to Bob on Chain 2. The sequencer orders these paired transactions, the transaction processors simulate the consequences, and the coordinator confirms the joint success or failure. If both succeed, the states are atomically committed; if one fails, both transactions are skipped to prevent inconsistent states. Independent transactions like sending from Dave to Eve on Chain 2 can proceed without blocking on the CAT resolution, demonstrating minimal blocking behavior.

Overall, the methodology combines formal modeling of transactions and dependencies, protocol design with coordination and concurrency control, formal proofs of correctness and liveness, and thorough simulation-based empirical evaluation to validate claims under realistic cross-chain conditions.

Technical innovations

• Introduction of a shared coordination layer with sequencers, transaction processors, coordinator, and confirmation actors to enable atomic cross-chain transactions without centralized trust.
• Embedding explicit dependency tracking and causal ordering into scheduling and confirmation layers to minimize blocking and allow out-of-order execution of independent transactions.
• Use of timeouts and bounding CAT dependency depth to guarantee liveness and mitigate cascading delays in asynchronous, Byzantine-prone multi-chain settings.
• Formalization of transaction memory traces and dependency graphs enabling precise identification of read-write and write-write conflicts relevant for multi-chain atomicity.
• Separation of accepted and postponed transaction sets to optimize throughput and latency while ensuring consistent cross-chain atomic commit outcomes.

Baselines vs proposed

• Uncoordinated cross-chain execution: CAT success rate significantly lower (unstated exact number) vs CATs protocol: high success rates >90% under modest CAT load (Fig. 6).
• Fully serialized blocking approach: higher latency vs CATs protocol: reduced blocking latency for independent transactions (Fig. 8).
• Latency vs CAT lifetime trade-off: latency rises with longer CAT lifetimes, but success rates also improve, showing a clear trade-off curve (Fig. 7).

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.05387.

Fig 1: A scenario with 5 participants and a cross-chain atomic

Fig 11: Average success of CATs with the number of CATs per block (nC).

Fig 12: shows the impact of nC on different types of post-

Fig 13: Impact of CAT lifetime on the average latency of regular transactions

Fig 14: Average success of CATs with the chain delay.

Fig 15: Average success of CATs with the throughput, and while keeping

Fig 16: Impact of the centralization of key accesses on the average success

Limitations

• The protocol requires all participating chains to run compatible transaction processors and integrate with the coordination layer, limiting compatibility with heterogeneous VM environments.
• Simulation-based evaluation lacks deployment on real-world blockchain platforms, so practical integration challenges or performance overhead are not empirically assessed.
• No detailed adversarial testing beyond Byzantine assumptions in simulation; robustness against adaptive or network-level adversaries is not fully explored.
• The dependency-depth bounding mitigates exponential branching but may limit concurrency in highly contended scenarios, potentially impacting scalability in extreme cases.
• The coordination layer introduces some degree of centralization, and security depends on this shared layer achieving consensus correctly.
• Formal proofs assume idealized abstractions and do not consider certain real-world blockchain failure modes such as reorgs or forks.

Open questions / follow-ons

• How can the CATs protocol be extended or adapted to heterogeneous blockchains with differing virtual machines and transaction semantics?
• What are the practical deployment challenges and performance impacts in real multi-chain ecosystems with variable network conditions and adversarial behaviors?
• Can the dependency-depth bounding and timeout parameters be dynamically optimized based on live network conditions to balance latency and throughput?
• How resilient is the protocol to sophisticated adaptive adversaries that attempt coordinated denial-of-service or censorship on the coordination layer?

Why it matters for bot defense

For bot-defense and CAPTCHA practitioners, this paper offers a rigorous approach to achieving atomicity and coordination in highly distributed, adversarial environments. The explicit modeling of dependencies and careful concurrency control in a Byzantine asynchronous context parallels challenges often encountered in distributed bot-detection systems, where partial state visibility and delayed coordination can cause inconsistent outcomes. The CATs protocol's use of shared coordination layers, dependency graphs, and timeout mechanisms might inspire designs for secure, atomic multi-step interactions in service infrastructures spanning multiple distinct verification or reputation providers.

Moreover, the minimal-blocking and eventual progress guarantees highlight strategies for designing systems that maintain throughput without sacrificing correctness or exposing users to inconsistent states—critical for bot-detection flows involving chained decisions or multi-party attestations. While this work focuses on blockchain interoperability, the underlying principles of atomic, composable, and secure cross-domain transactions could inform future defenses that require tight coordination among decentralized detection components or human challenge projects.

Cite

@article{arxiv2607_05387,
  title={ CATs: Secure Blockchain Interoperability with Cross-chain Atomic Transactions },
  author={ Andreas Penzkofer and Franck Cassez },
  journal={arXiv preprint arXiv:2607.05387},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.05387}
}

Read the full paper

• arXiv:2607.05387 (abstract)
• arXiv:2607.05387 (PDF)