Towards System-Oriented Formal Verification of Local-First Access Control

Researchers Florian Jacob, Johanna Stuber, and Hannes Hartenstein from the Karlsruhe Institute of Technology have published a paper proposing a new method for formally verifying access control in local-first systems. These systems, which rely on conflict-free replicated data types (CRDTs) to enable offline-first collaboration, are increasingly used in large-scale applications like Matrix for instant messaging and Keyhive for collaborative documents. However, as these systems grow beyond small trusted groups, they require Byzantine fault tolerance and fine-grained access control—something that current implementations lack, relying instead on informal specifications and unverified reference code.

The team's approach uses a bottom-up methodology, starting with simplified collaboration groups and building up semantics and invariants for a replicated data type based on capabilities for access control and hash chronicles for replication. They leverage the Verus framework, which uses the Z3 theorem prover, to perform formal verification in Rust at zero runtime cost. This allows system engineers to write specifications, verification, and implementation in a single language, making the process more accessible. Their preliminary results demonstrate the potential of this system-oriented formal verification, though scaling up to the complexity of real-world systems like Matrix or Keyhive remains an open challenge.