Towards System-Oriented Formal Verification of Local-First Access Control Conference: 13th Workshop on Principles and Practice of Consistency for Distributed Data; April 27, 2026; Edinburgh, Scotland 13th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC ’26), April 27, 2026, Edinburgh, Scotland DOI: 00.0000/0000000.0000000 ISBN: 000-0-0000-0000-0/0000/00 CCS: Computing methodologies Distributed algorithms CCS: Information systems Data structures CCS: Security and privacy Distributed systems security CCS: Software and its engineering Access protection
Florian Jacob, Johanna Stuber, Hannes Hartenstein · 2026
Read Towards System-Oriented Formal Verification of Local-First Access Control Conference: 13th Workshop on Principles and Practice of Consistency for Distributed Data; April 27, 2026; Edinburgh, Scotland 13th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC ’26), April 27, 2026, Edinburgh, Scotland DOI: 00.0000/0000000.0000000 ISBN: 000-0-0000-0000-0/0000/00 CCS: Computing methodologies Distributed algorithms CCS: Information systems Data structures CCS: Security and privacy Distributed systems security CCS: Software and its engineering Access protection by Florian Jacob, Johanna Stuber, Hannes Hartenstein (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-23560.txt.
Introduction
Jacob, Stuber, and Hartenstein take a bottom-up step toward formally verified access control for local-first collaboration systems, where users keep their own copies and mutual trust cannot be assumed. They define semantics and invariants for a replicated data type that manages simplified groups, using capability-based access control and hash chronicles for replication. The work is specified and checked in Rust with the Verus framework at no runtime cost.
Catalog record
| CREATOR | Florian Jacob, Johanna Stuber, Hannes Hartenstein |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68364 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.23560
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Towards System-Oriented Formal Verification of Local-First Access Control Conference: 13th Workshop on Principles and Practice of Consistency for Distributed Data; April 27, 2026; Edinburgh, Scotland 13th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC ’26), April 27, 2026, Edinburgh, Scotland DOI: 00.0000/0000000.0000000 ISBN: 000-0-0000-0000-0/0000/00 CCS: Computing methodologies Distributed algorithms CCS: Information systems Data structures CCS: Security and privacy Distributed systems security CCS: Software and its engineering Access protection Florian Jacob, Johanna Stuber, Hannes Hartenstein Abstract . Conflict-free replicated data types (CRDTs) and the local-first concept are increasingly employed not only in small-scale collaboration systems among few users who trust each other, but also in large-scale systems, like Matrix for instant messaging and Keyhive for collaborative documents. Since mutual trust is no longer warranted, these systems require Byzantine fault tolerance and fine-grained access control. As of today, Matrix and Keyhive pair an informal specification with an unverified reference implementation. In this work, we follow a bottom-up approach towards constructing formally verified authorization algorithms for Byzantine fault-tolerant local-first systems. As intermediate target for formal verification, we contribute semantics and invariants of a replicated data type for managing simplified collaboration groups, based on capabilities for access control and hash chronicles for replication. To enable future integration into local-first systems like Matrix and Keyhive, we strive for accessibility to system engineers by using the Rust programming language for formal specification, verification, and implementation, enabled by the Verus framework using the Z3 theorem prover at zero runtime cost. We report on our experience and preliminary results following this approach, and discuss next steps towards scaling up access control expressiveness. Whether this approach can be scaled up to the complexity of real-world local-first access control systems like Matrix or Keyhive remains future work, but our findings demonstrate the potential of system-oriented formal verification with Verus. † † cc-license: by 1. Introduction Conflict-Free Replicated Data Types (CRDTs, ( 30 ; 2 ) ) are a common solution to concurrency conflicts in local-first systems, i.e., decentralized systems designed for low latency and availability under partition ( 17 ; 18 ) . CRDT-based systems do not attempt to conceal their inherent concurrency, but instead demand concurrent thinking from their designers. In the CRDT research community, the benefits of formal methods for CRDT design to ensure consistency and application invariants are well-established, especially in Byzantine contexts ( 10 ; 6 ) , to counter the highly-concurrent and nondeterministic nature of distributed systems. However, Basin et al. recently called attention to the gap between formal methods theory and distributed systems practice relying on informal specifications and unverified reference implementations ( 5 ) . An example for this gap is the Matrix decentralized system for instant messaging and group chats ( 32 ) , widely used in security-critical settings ranging from the French public sector and the German healthcare system to the United Nations and NATO ( 8 ; 9 ) . A recent update of the Matrix specification dealt with an algorithm violating a security invariant ( 7 ; 33 ) , which could have been caught early by integrating formal methods into the standardization process. Large-scale local-first systems like Matrix cannot rely on mutual trust but face arbitrary malevolence of participants, necessitating Byzantine fault tolerance and fine-grained access control. We therefore study formal verification of local-first access control in an asynchronous system with Byzantine faults. We strive for accessibility to system engineers by using Verus ( 23 ; 22 ) , a recent verification framework that pairs the popular high-performance programming language Rust with the Z3 theorem prover at zero runtime cost. Instead of attempting to verify the authorization algorithms of Matrix or Keyhive directly, we follow a bottom-up approach to construct simple but formally verified authorization algorithms for local-first systems, in order to gradually extend complexity and expressiveness in the future. We contribute a semantics specification of a replicated data type for capability-based access control in collaboration groups, along with a simplified but verified algorithm for local-first authorization. We report on our experience with Verus to unify specification, implementation, and verification in a single Rust source file, and publish all source code under a free license ( 31 ) . 2. Local-First Systems and Related Work Inspired by local-first software ( 17 ; 20 ) , we use the term local-first to describe decentralized systems where every entity independently maintains its own local replica of system state and acts autonomously, i.e., autonomously executes query and mutate operations. Instead of necessitating up-front coordination among entities, information on state changes is exchanged asynchronously. Thus, the operations offered by an entity are available with local latency regardless of network partitions and faults in other entities. In addition, large-scale local-first systems demand algorithms that tolerate Byzantine faults, since trust among entities is no longer warranted at scale. For fault tolerance, low latency, and eventual consistency, local-first systems rely on previous work on wait-freedom ( 13 ) , coordination avoidance ( 4 ) , and conflict-free replicated data types ( 30 ; 2 ) . A group is what we call a replicated object together with the set of entities that replicate and collaborate on that object, i.e., a chat group or collaborative document. The group’s state encompasses both data, like the document state, and metadata, like the group name or permission assignments. Group state is replicated via a partially ordered set of state change events using the hash chronicle data type ( 16 ) . Hash chronicles are Byzantine fault-tolerant CRDTs that replicate a partially ordered event set via recursive hash linking: Any event is bound to its causal history , i.e., the chronicle subset that contains all causal precursor events back to group creation, by recursively linking its direct causal precursors. The concept behind hash chronicles represents the current community consensus for replication in large-scale local-first systems; the concept is also known as hash-linked DAGs (directed acyclic graphs, ( 19 ) ), blocklace ( 1 ) , Matrix Event Graph ( 14 ) , or MerkleDAG ( 29 ) . Among the most sophisticated examples of large-scale local-first systems and frameworks is the Matrix ( 32 ) group communication system, as well as the Automerge/Keyhive ( 3 ; 37 ) and p2panda ( 25 ) CRDT frameworks for local-first collaborative applications. While Matrix is widely deployed already, Keyhive and p2panda are still in the research project phase, but also aim to scale collaborative local-first systems up to, e.g., a decentralized Wikipedia equivalent ( 37 ) . We recently proposed a conceptual model and security properties for a Matrix-like local-first authorization algorithm in an informal top-down approach ( 16 ) . In this paper, we follow a bottom-up approach and focus on constructing local-first access control semantics and simplified but formally verified algorithms, instead of characterizing what is currently present in Matrix. In his work on local-first authorization, Kleppmann focuses on resolving mutual authorization revocations among equally-privileged entities ( 21 ) , which are out of scope for this work. The work of Rault et al. explores CRDT-based access control under the honest-but-curious assumption instead of Byzantine faults, and focuses on delegation, revocation, and compensating actions consecutive to access control concurrency conflicts ( 26 ; 27 ) . Other work