GUARDTs: Decentralized Access Control for Replicated Data Types

GUARDTs: Decentralized Access Control for Replicated Data Types

arXiv:2611.08083v1 [cs.PL] 5 Nov 2026

CHRISTIAN KUESSNER, Technische Universität Darmstadt, Germany RAGNAR MOGK, Technische Universität Darmstadt, Germany JULIAN HAAS, Technische Universität Darmstadt, Germany ANNETTE BIENIUSA, Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau, Germany MIRA MEZINI, Technische Universität Darmstadt, Germany, National Research Center for Applied Cybersecurity (ATHENE), Germany, and Hessian Center for Artificial Intelligence (hessian.AI), Germany Replicated data types providing strong eventual consistency offer a principled foundation for developing decentralized software. Yet existing approaches to programming such data types leave access control unresolved: they either provide none at all, delegate it to a trusted coordinator, reintroducing the centralization they were designed to avoid, or tie it to specific data-type constructions, while typically assuming non-Byzantine replicas and static policies. We present GUARDTs: Guarded Unforgeable Algebraic Replicated Data Types, which embed fine-grained permissions directly into the application data model, operate without a central authority, support dynamic policy evolution, and tolerate Byzantine replicas. We formally prove that GUARDTs guarantee confidentiality, integrity, and availability and show empirically that their access control adds negligible overhead on top of the cost of Byzantine-resilient replication itself.

1

Introduction

Distributed applications increasingly rely on centralized, cloud-based infrastructure to synchronize state across components and to enforce access control. The appeal is clear: centralization hides the complexities of distribution and provides a single source of truth for permissions. Yet it concentrates control in a third party, raising concerns about data ownership, privacy, and security; it imposes uniform policies ill-suited to the diverse needs of individual applications; and it introduces a single point of failure that undermines availability and increases latency. Strongly eventually consistent replicated data types, such as Conflict-free Replicated Data Types (CRDTs) [14], provide a principled programming foundation for decentralized applications. Yet existing approaches to programming such data types leave access control unresolved. Widely used CRDT libraries such as Automerge and Yjs provide no access control at all: by default, replicas are trusted and every replica can read and write everything. Other approaches either delegate it to a trusted authority [13], reintroducing the centralization they were designed to avoid, or tie it to specific data-type constructions [12]. To close this gap, we present an approach to access control for decentralized, strongly eventually consistent replicated data types, called GUARDTs (Guarded Unforgeable Algebraic Replicated Data Types). GUARDTs guarantee the three classical goals of access control: confidentiality, integrity, and availability (CIA): confidentiality ensures that no principal learns anything about data it is not permitted to read, integrity ensures that only authorized writes affect the state, and availability ensures that authorized readers eventually observe every write they are entitled to see. In addition, our approach to access control has four properties that decentralized applications need. First, decentralization: the access-control mechanism operates without a central authority; Authors’ Contact Information: Christian Kuessner, Technische Universität Darmstadt, Germany; Ragnar Mogk, Technische Universität Darmstadt, Germany; Julian Haas, Technische Universität Darmstadt, Germany; Annette Bieniusa, Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau, Germany; Mira Mezini, Technische Universität Darmstadt, Germany and National Research Center for Applied Cybersecurity (ATHENE), Germany and Hessian Center for Artificial Intelligence (hessian.AI), Germany.

2

Kuessner et al.

a trusted coordinator that manages permissions would reinstate the very single point of trust that decentralized architectures are designed to eliminate. Second, generality: the mechanism neither is tied to specific data-type constructions nor treats application data as opaque; instead, it is applicable to arbitrary application data types while still being able to inspect their specific structure to enforce fine-grained policies in which read and write privileges differ across replicas and across sub-components of the data types. Third, policy evolution: access rights remain updatable at runtime as users delegate permissions for tasks and revoke them upon completion, as team membership changes, or as contractors receive temporary write access. Fourth, Byzantine resilience: in decentralized applications, replicas may be adversarial, and the mechanism remains correct even under Byzantine behavior. Achieving CIA and the four properties of the enforcement mechanism together is non-trivial. Without a trusted mediator, every replica must enforce policies locally and cannot assume that its peers are honest: Byzantine replicas may impersonate others, inject unauthorized writes, or attempt to read data they are not permitted to see. At the same time, correct replicas must agree on which updates are authorized, although they observe permission changes in different orders. Revocations are particularly difficult: a revocation may be concurrent with writes of the replica whose rights were revoked, so replicas must consistently decide which of these writes to accept. We address these challenges as follows. For data generality, we build upon Algebraic Replicated Data Types (ARDTs) [10], a class of delta-based convergent algebraic data types [1]. We leverage their algebraic, tree-like structure to define fine-grained permission trees, tightly integrating access control into the data model. To enable policy evolution, we model permissions as first-class capability objects that can be delegated and revoked. The authorization state is replicated as a HashDAG [8] among all replicas, providing each with converging, tamper-evident evidence for local authorization decisions. Enforcement happens at the replication layer: replicas locally filter deltas based on the receiver’s read permissions and materialize only deltas whose write authority can be verified. Cryptographic commitments hide delta contents from unauthorized replicas while ensuring that authorized replicas converge to identical state. Revocations take effect without coordination, closing access to future writes while preserving already-delivered information. In summary, we make the following contributions. We design GUARDTs, combining path-based capabilities, a replicated event graph, and enforcement at the replication layer, and present them informally in Section 3 and formally in Section 4, based on the programming and system model of Section 2. We prove that GUARDTs guarantee CIA despite decentralized, dynamic enforcement in a Byzantine setting (Section 5). We show empirically that their access control adds negligible overhead on top of Byzantine-resilient replication (Section 6). Finally, we discuss related work (Section 7) and future work (Section 8). 2

Programming and System Model

In this section, we present and justify our assumed application programming and system models, which motivate the design goals of our decentralized access-control framework. 2.1

Application Programming Model with Algebraic Replicated Data Types (ARDTs)

As a running example, consider an application for managing business trips of service engineers who inspect industrial plants at customer sites. On a trip, an engineer records the inspections of individual plant components, such as valves or pumps, and the expenses incurred along the way. Figure 1 shows the application’s data types in Scala, modeled as algebraic data types (ADTs), a common programming abstraction in modern languages. A TravelPlan consists of a title,

GUARDTs: Decentralized Access Control for Replicated Data Types

1 2 3 4 5 6 7 8 9 10 11

3

case class TravelPlan ( title : Text , inspections : Map [ UniqueId , Text ] , expenses : Map [ UniqueId , Expense ] ) case class Expense ( description : Text , amount : Text , comment : Option [ Text ] ) enum Option [+ T] : case None case Some ( value : T )

Fig. 1. Application state modeled as algebraic data types in Scala.

inspections of plant components, and expenses, a Map of Expense objects. An Expense consists of a description, an amount, and an optional comment, represented as an Option.1 To let multiple users manage travel plans on their own devices without relying on a central server, we model TravelPlan and Expense as Algebraic Replicated Data Types (ARDTs) [10], which embed conflict-free replication with strong eventual consistency into the semantics of standard algebraic data types. Akin to state-based Conflict-free Replicated Data Types (CRDTs) [14], ARDTs structure state as a join-semilattice with a commutative, associative, and idempotent merge. Designing correct CRDTs by hand is notoriously error-prone, even for experts [7]. ARDTs overcome this challenge through compositionality: the framework provides replicated base types, such as Text, and derives a correct merge function for any composite ADT by recursively combining the merge functions of its fields and variants, guided by its algebraic structure. Strong eventual consistency therefore holds by construction. Crucially, developers never write these merge functions by hand. When modeling application state with ARDTs, they need neither force-fit their domain models into a fixed CRDT library nor verify the correctness of custom merge functions. Instead, they express arbitrary application-specific operations over standard data types, with the type system ensuring well-formedness and the runtime guaranteeing consistency. ARDTs employ a variant of delta-state replication [1]. Rather than transmitting the entire state upon every modification, replicas generate deltas, i.e., partial states encapsulating only the effects of recent operations. These deltas merge under the same semilattice semantics as full states in classical state-based CRDTs, enabling efficient dissemination over any transport layer guaranteeing uncorrupted message delivery. Enforcing access control in this setting requires synchronizing deltas selectively based on replica authorization. In our running example, Alice may want to share her inspections with her colleague Bob, who has inspected the plant before and can add notes from earlier visits. Bob may in turn want to grant the customer’s shift engineer Eve access to a single inspection entry, so that she can confirm that a defect has been fixed, without involving an administrator and often without connectivity on the plant floor. With Claudia, the office assistant who handles reimbursements, Alice wants to share only her business expenses, not her private ones. Moreover, Claudia should be permitted to append comments to expenses, but not change other fields such as amounts or descriptions. Standard CRDT replication treats a data structure as a monolithic unit, lacking awareness of such application-specific boundaries. This limitation motivates embedding access-control policies 1We include the definition of Option, although it is a built-in Scala type, to illustrate a sum type.

4

Kuessner et al.

directly into the data model, so that the runtime is able to enforce differentiated read and write permissions automatically when replicating deltas. 2.2

System and Threat Model

We consider a dynamic peer-to-peer system in which pairs of replicas communicate asynchronously over encrypted and authenticated channels. This communication model is realistic for modern decentralized and local-first settings: replicas run on distributed devices that experience variable network latency, intermittent connectivity, and churn, yet can establish secure point-to-point channels over untrusted public networks using standard public-key cryptography (e.g., TLS or Noisebased secure sessions). Each replica acts as an autonomous principal identified by a cryptographic public key. The system operates without a central coordinator or trusted server. Replicas are mutually distrustful. We adopt a Byzantine adversary model [11], where faulty replicas may deviate arbitrarily from the protocol. They may selectively drop or forge messages, introduce colluding malicious peers, or send conflicting updates to different peers to induce state divergence (equivocation). Adversaries are, however, computationally bounded: they cannot break standard cryptographic primitives, including the security of the encrypted channels, digital signatures, and collision-resistant cryptographic hash functions, which we model as random oracles. In particular, a salted hash 𝐻 (𝑠 ∥ 𝑥) with a fresh random salt 𝑠 reveals nothing about 𝑥. No replica can forge another’s digital signature or find two distinct values with the same hash. We do not address scenarios where an attacker holds legitimate write permissions but acts maliciously (e.g., writing semantic garbage); mitigating such authorized insider threats is orthogonal to access control. To ensure liveness, we assume eventual delivery: non-Byzantine replicas can eventually communicate with one another, consistent with prior models for Byzantine eventual consistency [9]. Without this assumption, an adversary could indefinitely partition the network and prevent convergence. 3

GUARDTs in a Nutshell

In this section, we provide a high-level informal overview of GUARDTs and illustrate it with the running example. Subsequently, Section 4 defines the protocol formally and Section 5 formally proves its properties. 3.1

Overview

Path-based capabilities. Permissions in our protocol take the form of capabilities and are expressed using delegation events that grant a designated replica sets of path descriptors it may read and write, following the hierarchical tree structure of ARDTs (Section 4.1). Every event references the capability that authorizes it, and only the delegatee of that capability may use it. A path descriptor may cover the entire data type, a specific field, or a dynamically populated collection, down to a single leaf node, giving policies the same granularity as the data model itself. Capabilities are hierarchical: granting access to a descriptor implicitly covers all its structural descendants, and write access entails read access. Capabilities thus apply to any ARDT without type-specific enforcement code. Our protocol supports fine-grained, dynamically evolving access-control policies: the set of permissions that principals hold is not statically fixed but changes over time as replicas delegate capabilities to other replicas. Replicas can only delegate permissions they already hold, so even colluding Byzantine replicas cannot extend their authority beyond the capabilities they have been granted. Delegated capabilities can themselves be delegated further, forming delegation chains. Moreover, replicas may revoke capabilities they have granted; revoking a capability also revokes all capabilities delegated from it, closing off entire branches of the delegation chain (Section 4.2.3). Every delegation chain originates from a designated initiating replica that initially holds full

GUARDTs: Decentralized Access Control for Replicated Data Types

5

permissions over the entire path space of the replicated state. In our example, this is Alice, who owns all rights over her travel plan and delegates subsets of them to others. Replicated event graph. Each replica must decide locally whether to apply a delta and whether to share it with a given peer. Since delegations and revocations may be concurrent with updates and reach replicas in different orders, these decisions depend on which policy changes causally precede an update. We therefore record all operations as events in a causally ordered, replicated event graph: delegate events grant capabilities to a replica, update events record application state changes, and revoke events invalidate a delegation. The root of the graph is a genesis event that grants the initiating replica full read and write access to the ARDT. Each replica uses its local view of the graph to verify delegation chains and to determine whether a revocation precedes, follows, or is concurrent with an update. As the graph is convergent, all correct replicas eventually observe the same events and reach the same decisions. To account for Byzantine behavior, the event graph is a HashDAG, a construction proposed for Byzantine fault-tolerant CRDTs [3, 8, 9] and used by Matrix [4]: hash links and signatures prevent Byzantine replicas from forging events or retroactively altering them. The graph is replicated to all replicas, but application data must remain confidential. Update events therefore contain only a salted-hash commitment to their delta, which is hiding (it reveals nothing about the delta) and binding (no replica can associate two different deltas with the same event). The deltas themselves are kept in a separate delta store and sent only to replicas with read permission. Enforcement at replication boundaries. Our protocol enforces policies at the replication layer, when deltas are disseminated. For confidentiality, a correct replica sends a delta only to peers with valid read authority for its path; for integrity, each correct replica materializes only deltas with valid write authority. In both cases, authority is valid if its chain of authorizing capabilities leads back to the genesis event and none of these capabilities has been revoked. Rather than blocking writes until the existence of concurrent revocations can be ruled out, which compromises availability, writes without locally known revocations are applied optimistically and reverted if concurrent revocations become locally known. Reads of updates committed before or concurrently with a revocation remain permitted. This asymmetry preserves already-disclosed information while preventing replicas from circumventing revocations by backdating their writes. 3.2 GUARDTs Illustrated Figure 2 shows an instance of the event graph of our running example. It contains all three kinds of events: delegations (depicted as ), updates ( ), and revocations ( ); Section 4.2 introduces them formally. The event 𝐴⊥ is the genesis event, which grants Alice access to the entire path space. Alice delegates capabilities to Bob ( 𝐴2 ) and to Claudia ( 𝐴3 ); in turn, Bob delegates capabilities to Eve ( 𝐵 4 ). The graph in Figure 2 depicts one replica’s view at a single point in time; other replicas may hold different views (subsets or supersets of it). Eventually, all correct replicas receive every event shown here, possibly extended by further events. We walk through the graph of Figure 2 and determine for each update whether it is authorized and thus included in the materialized state (Section 4.2 and Section 4.3 formalize these decisions). The simplest case in Figure 2 is the update 𝐴1 , which is authorized by the genesis event 𝐴⊥ . Claudia’s update 𝐶 5 is authorized by 𝐴3 and is concurrent with Bob’s delegation 𝐵 4 to Eve. The update event 𝐸 6 has a longer delegation chain, which is depicted in Figure 3 together with the information captured in delegation events, such as the author of the delegation, the delegatee, and the permissions each delegation passes on. The delegation chain in Figure 3 starts at the genesis event 𝐴⊥ , which captures that Alice is both the author and the delegatee and that she is granted read and write access to the entire travel

6

Kuessner et al. delegate

pre

revoke

auth

update

𝐴⊥

× 𝐴1

𝐸6

revokes

𝐸9

𝐵4

×

𝐴3

𝐴2

𝐸7

𝐴8

𝐶5

Fig. 2. An example event graph, with one row per author. Events are drawn as diamonds (delegate), octagons (revoke), and circles (update), and are named after the initial of their author – Alice (A), Bob (B), Claudia (C), Eve (E). Solid arrows are pre pointers referencing an event’s causal predecessors; dotted arrows are auth pointers referencing the capability that authorizes an event; the dashed edge marks a revoked capability. Section 3.2 walks through the example. 𝐴⊥ author: Alice delegatee: Alice Πrd = Πwr = { * }

auth

𝐴2 author: Alice delegatee: Bob Πrd = Π wr = { inspections }

auth

𝐵4 author: Bob delegatee: Eve Πrd = Π wr = { inspections.valve3 }

auth

𝐸6 author: Eve writes inspections.valve3

Fig. 3. The delegation chain authorizing Eve’s update 𝐸 6 of Figure 2. Each delegation is authorized by the one to its left and delegates a subset of its permissions, down to the single inspection entry that 𝐸 6 writes.

plan ({*}). She asks Bob to help with the inspections and authors 𝐴2 , a delegation event with delegatee : Bob, Π rd = Πwr = {inspections}. This delegation is valid: both sets are covered by {*}, so Bob receives no more than Alice holds. Bob can therefore read and modify every inspection entry, but nothing else, in particular none of the expenses. Bob, in turn, asks Eve, the customer’s shift engineer, to confirm that a defective valve has been fixed. Because Bob is the designated delegatee of 𝐴2 , he is authorized to issue a delegation that references 𝐴2 as its authorizing parent. He authors 𝐵 4 with delegatee : Eve and Π rd = Πwr = {inspections.valve3}, the single entry Eve is supposed to confirm. This delegation is valid, as inspections.valve3 ⊑ inspections. Eve thus receives access to one inspection entry, with no authority over the rest of the travel plan, and her update 𝐸 6 writes to exactly that path. The chain of 𝐸 6 is valid. When Alice learns that Eve’s tablet has been stolen from the plant floor, she revokes Bob’s delegation to Eve, 𝐵 4 , with 𝐴8 , which is authorized by 𝐴2 . Alice has already seen Eve’s first update, but not her second: 𝐴8 references 𝐸 6 and 𝐶 5 as predecessors, but not 𝐸 7 . Eve’s second update is thus concurrent with the revocation, 𝐸 7 ∥ 𝐴8 , which makes 𝐸 7 unauthorized. 𝐸 6 is authorized by the same delegation event 𝐵 4 that was revoked by 𝐴8 , but 𝐸 6 ≺ 𝐴8 , so Alice has acknowledged 𝐸 6 in her revocation. A revocation does not affect earlier events, and 𝐸 6 therefore remains authorized. The materialized state of Figure 2 thus contains 𝐴1 , 𝐶 5 , and 𝐸 6 , but not 𝐸 7 and 𝐸 9 . 𝐸 9 is a special case: it references 𝐴8 as a predecessor but is still authorized by the revoked 𝐵 4 . Its author knew about the revocation, so 𝐸 9 is a Byzantine event that no correct replica would create, and none will ever include the update it captures.

GUARDTs: Decentralized Access Control for Replicated Data Types

7 Expense

12 13 14 15 16 17 18 19

case class Expense ( description: Text , amount: Text , comment: Option [ Text ] ) enum Option [+ T ] : case None case Some(value: T )

description

comment

amount

Text

Option

Text Some

None

Some

None

value Text

Fig. 4. Type definitions of Expense and Option (left, from Figure 1) and the resulting tree representation (right): field names and variant tags become edge labels, i.e., path segments.

4

Formalization of GUARDTs

In this section, we formally define GUARDTs. Capabilities grant permissions over paths of the ARDT (Section 4.1); delegations, revocations, and updates form a replicated event graph (Section 4.2); and from this graph, each replica locally decides which deltas it may send and apply (Section 4.3). 4.1

Path-Based Capabilities

Because ARDTs are constructed via nested algebraic data types (products, sums, and collections), their structural schema forms a hierarchical tree: edges carry the field selectors of product types, and sum types branch into their variants. Figure 4 shows this tree for Expense. Nodes of an ARDT tree can be addressed by path descriptors and paths. Definition 4.1 (Path Descriptors and Paths). A path descriptor is a dot-separated list of path segments 𝑠, which are either the wildcard * or an edge label of the ARDT tree, i.e., a field name of a product type, a variant tag of a sum type, or a key of an associative collection: PathDesc ::= 𝑠 (. 𝑠) ∗

A descriptor with no wildcard is a concrete path 𝑝, addressing exactly one node of the ARDT tree by the sequence of edge labels traversing the tree from the root to that node. The empty path 𝜖 denotes the root of the ARDT and is only matched by the path descriptor *. Path descriptors are the basis of permissions. A permission is the right to read or to write the nodes matched by a path descriptor. A capability is a delegation event (Section 4.2) that grants its delegatee read permissions for a set of path descriptors Π rd ⊆ PathDesc and write permissions for a set Π wr ⊆ PathDesc. Every event references the delegation event that authorizes it. A path 𝑝 matches a descriptor 𝑝𝑑, written 𝑝 ⊑ 𝑝𝑑, if 𝑝𝑑 is a prefix of 𝑝, where a wildcard segment matches any single path segment. Concrete paths thus grant permissions as fine-grained as the data type itself, while wildcards cover dynamically populated collections, such as maps with generated keys, whose elements cannot be enumerated in advance. Because path descriptors are defined over the structural schema of any ARDT rather than a fixed set of types, the same mechanism applies to any ARDT without type-specific enforcement code. For example, in the travel plan of Figure 1, the path expenses.e17.description addresses the description of the expense with the (randomly generated) ID e17, and expenses.e17.comment. Some.value the text of its comment, if present. The descriptor expenses.*.description instead matches the description of every expense: the wildcard stands for an arbitrary key of the expenses

8

Kuessner et al.

map, so the descriptor also covers expenses added later. A replica can thus delegate access to expenses.*.comment without enumerating expense IDs. Each delta value 𝛿 modifies the node at a single path, written path(𝛿). Since deltas and permissions both refer to nodes by path, deciding whether a capability covers a delta reduces to path matching. Because matching is by prefix, access to a descriptor extends to all its structural descendants; and because modifying a data element requires observing its context, write access implies read access. A replica is thus authorized to write 𝛿 if ∃𝑝𝑑 ∈ Π wr : path(𝛿) ⊑ 𝑝𝑑, 4.2

read 𝛿 if ∃𝑝𝑑 ∈ Π rd ∪ Π wr : path(𝛿) ⊑ 𝑝𝑑.

Tracking and Evolving System Knowledge

The replicated event graph records all delegations, revocations, and application state updates as causally ordered events and is implemented as a HashDAG. In this subsection, we introduce the structure of the events, the event graph, and the actions that change and replicate its state. 4.2.1

Events, Event Graph, and System Knowledge.

Definition 4.2 (Replica Identifier). Let I be the universe of replica identifiers. An identifier id ∈ I is a cryptographic public key whose corresponding private key is held exclusively by that replica. A replica signs every event it authors with its private key, which allows any other replica to authenticate events without a trusted third party. A replica identifier may correspond to an individual user, a specific device owned by a user (allowing different devices of the same user to hold disjoint privileges), or an isolated process that follows the principle of least privilege, i.e., holds only the permissions it needs. Because our access-control model is agnostic to the operational boundary of a principal, treating all authorization endpoints uniformly as replica identifiers simplifies the formal semantics without loss of generality. Definition 4.3 (Cryptographic Hash). Events refer to each other, and to the data they control, only by cryptographic hash. We write 𝑒 # for the hash of a value 𝑒 and, for a set 𝐸, 𝐸 # = {𝑒 # | 𝑒 ∈ 𝐸} for the set of hashes of its elements. Because we use hashes as cryptographically verified pointers, we generally assume that we can use a hashed value 𝑒 # as if it were the value 𝑒 itself, except where noted otherwise. Definition 4.4 (Event). Let E be the domain of system events. An event 𝑒 ∈ E is a tuple 𝑒 = ( op, author, auth, pre )

of an operation op ∈ Operation that the event performs, the replica author ∈ I that authored 𝑒 and whose signature authenticates it, the hash auth ∈ E# of the delegation event authorizing 𝑒, and the set pre ⊆ E# of hashes of the direct causal predecessors of 𝑒. Because auth and pre are hashes rather than the events themselves, altering an event invalidates the references of every event that follows it: a Byzantine replica cannot splice, reorder, or retroactively insert entries without detection. This is what gives the event graph Byzantine Eventual Consistency (BEC) [9]. Definition 4.5 (Operation). An operation op ∈ Operation takes one of three forms: Delegate(delegatee, Πrd, Πwr ) delegates to replica delegatee ∈ I the read permissions Π rd ⊆ PathDesc and write permissions Π wr ⊆ PathDesc. We call events carrying such an operation delegation events and use them as capabilities for authorization. Update((id ∥ 𝛿) # ) establishes a cryptographic commitment (Section 4.2.4) by id to ARDT delta value 𝛿. We call events carrying such an operation update events. Revoke(𝑒𝑑# ) revokes the delegation event 𝑒𝑑 , which it identifies by its hash. We call events carrying such an operation revocation events.

GUARDTs: Decentralized Access Control for Replicated Data Types

9

The domain E additionally contains one distinguished genesis event 𝑒 ⊥ (Definition 4.6). This event bootstraps full authority for the initiating replica id⊥ , granting it read and write access to the entire path space (Π rd = Πwr = {*}). It is axiomatically authorized (auth = 0# ) and has no causal predecessors (pre = ∅). As the root of all other events, the genesis event is initially known to all replicas. The initiating replica thus acts as an omnipotent administrator: all authority in the system derives from it, and, as the genesis event cannot be revoked, its authority is permanent. Definition 4.6 (Genesis Event). Every event graph is seeded with the same genesis event 𝑒 ⊥ : 𝑒 ⊥ = ( Delegate(𝑖𝑑 ⊥, {*}, {*}), 𝑖𝑑 ⊥, 0#, ∅ )

Definition 4.7 (Event Graph). An event graph 𝐸 ⊆ E is the set of events a replica has created locally or received from peers. Its edges are the predecessor references: each event 𝑒 ′ ∈ 𝐸 has an edge to every event 𝑒 ∈ 𝐸 with 𝑒 # ∈ 𝑒 ′ .pre. We write 𝑒 ≺ 𝑒 ′ and say that 𝑒 happened before 𝑒 ′ if 𝑒 is reachable from 𝑒 ′ along these edges, and we write 𝑒 ∥ 𝑒 ′ and call the two events concurrent if neither 𝑒 ≺ 𝑒 ′ nor 𝑒 ′ ≺ 𝑒 holds. Reachability is a partial order on 𝐸.

The happened-before order may be incomplete: a Byzantine author can omit known events from the predecessors of its own events and thereby backdate them, making them appear concurrent with events they actually follow. Conversely, hash links prevent the order from containing false precedences: an event can only reference events that already exist, so 𝑒 ≺ 𝑒 ′ implies that 𝑒 was indeed created before 𝑒 ′ . Every ARDT update is encapsulated in a delta value that modifies a specific node in its tree. Replicas store the deltas they have produced and received in their local delta store. Definition à 4.8 (Delta Value and Delta Store). Let D be the join-semilattice of an ARDT, with merge operator . A delta value is an element 𝛿 ∈ D that targets a single concrete path, written path(𝛿). A delta store Δ ⊆ D is the set of concrete delta values a replica has produced locally or received from remote peers. Definition 4.9 (Local and Global Knowledge). The local knowledge of a replica id is the triple ⟨𝐸, Δ, 𝐼 ⟩ of its event graph, its delta store, and its inbox 𝐼 ⊆ E ∪ D of messages (events or deltas) that have been sent to it but not necessarily received yet. The global system knowledge is a finite map
𝐾 : I ⇀ events : P (E), deltas : P (D), inbox : P (E ∪ D) with 𝐾 [id ↦→ ⟨𝐸, Δ, 𝐼 ⟩] denoting that replica id holds event graph 𝐸, delta store Δ, and inbox 𝐼 . 4.2.2 Transition Rules of the Event Graph. The event graph of a replica is modified by the rules

Action, Send Event, and Receive Event below. Each rule is a step → − taken by a single acting replica id. Action and Receive Event change only the local knowledge 𝐾 (id), while Send Event

adds to the inbox of a peer id𝑟 . Action

𝑒 = (op, id, 𝑒𝑑# , heads(𝐸))

𝑒𝑑 ∈ 𝐸

id

Δ′ = Δ ∪ {𝛿 | op = Update((id ∥ 𝛿) # )}

𝐾 [id ↦→ ⟨𝐸, Δ, 𝐼 ⟩] − → 𝐾 [id ↦→ ⟨𝐸 ∪ {𝑒}, Δ′, 𝐼 ⟩] 𝑒∈𝐸

Send Event

id

𝐾 [id ↦→ ⟨𝐸, Δ, 𝐼 ⟩, id𝑟 ↦→ ⟨𝐸𝑟 , Δ𝑟 , 𝐼𝑟 ⟩] − → 𝐾 [id𝑟 ↦→ ⟨𝐸𝑟 , Δ𝑟 , 𝐼𝑟 ∪ {𝑒}⟩] Receive Event

𝑒 ∈𝐼

causally_ready(𝑒, 𝐸) id

𝐾 [id ↦→ ⟨𝐸, Δ, 𝐼 ⟩] − → 𝐾 [id ↦→ ⟨𝐸 ∪ {𝑒}, Δ, 𝐼 ⟩]

10

Kuessner et al.

Action. This rule models a replica taking a local action that modifies its local copy of the event graph by appending a new event to it. The operation is freely chosen by the replica: honest replicas construct events that adhere to the correctness properties we discuss later in this section (Sections 4.2.3 and 4.3), but Byzantine replicas may produce arbitrary operations. The author of the event is the acting replica id, which cryptographically signs the event, so that Byzantine replicas cannot forge it. Its auth is the capability that the acting replica picks to authorize the event, i.e., a delegation event 𝑒𝑑 ∈ 𝐸 that grants the required permissions. Its pre is the set of heads of the local event graph 𝐸, i.e., the events not in pre of events in 𝐸. Since 𝑒𝑑 ∈ 𝐸, this implies 𝑒𝑑 ≺ 𝑒. While hash-linking prevents claiming unseen predecessors, a Byzantine replica may omit known heads to backdate the event and thus subvert the protocol. When the operation is an Update, the delta 𝛿 it references is added to the delta store. Send Event and Receive Event. These rules model peer-to-peer dissemination of the event graph. In Send Event, the acting replica id puts an event 𝑒 from its event graph into the inbox 𝐼𝑟 of some peer id𝑟 . In Receive Event, the acting replica id takes an event 𝑒 from its inbox 𝐼 and inserts it into its event graph. Send Event has no access-control guard: events contain only causal links, delegations, and hiding commitments (𝑒.op = Update((𝑒.author ∥ 𝛿) # )), so they reveal no confidential application data and are replicated without access-control filtering. Since the sender may be Byzantine, a received 𝑒 may be any event, but signatures and hash links ensure that it cannot impersonate other replicas or alter existing events. Metadata needs to be replicated in a causally consistent manner, so that the events a received event points to are already present at the receiving replica. Any algorithm for causal broadcast achieves this, and we abstract over the choice with the predicate causally_ready(𝑒, 𝐸), checked by the receiver. We only require that causally_ready(𝑒, 𝐸) implies that all predecessors pre of 𝑒 are in 𝐸, and that pre ≠ ∅ and 𝑒.auth ≺ 𝑒 unless 𝑒 = 𝑒 ⊥ . The former is necessary because an event without predecessors would otherwise constitute a second root of the event graph, which a Byzantine replica could use to create events unrelated to the genesis event. The latter ensures that the authorizing capability of an event, and transitively its whole delegation chain, is part of the causal past of the event, and thus known to every replica that knows the event.

4.2.3 Validating and Invalidating Delegations. The predicates in Figure 5 formalize the validity of a delegation (delegation_valid(𝑒𝑑 )) and the effect of invalidating, i.e., revoking, an existing delegation (revocations). Validating Delegations. The delegation_valid(𝑒𝑑 ) predicate in Figure 5 formalizes a valid delegation chain from a delegation event 𝑒𝑑 back to the genesis event 𝑒 ⊥ . The genesis event is valid delegation_valid(𝑒𝑑 ) := 𝑒𝑑 = 𝑒 ⊥ ∨ delegation_valid(𝑒𝑑 .auth)

∧ 𝑒𝑑 .author = 𝑒𝑑 .auth.op.delegatee

revocations(𝐸, 𝑒 ⊥ ) := ∅

∧ 𝑒𝑑 .op.Πrd ⊑ 𝑒𝑑 .auth.op.Π rd ∧ 𝑒𝑑 .op.Πwr ⊑ 𝑒𝑑 .auth.op.Πwr

(i) (ii)

(iii)

revocations(𝐸, 𝑒𝑑 ) := {𝑒𝑟 ∈ 𝐸 | 𝑒𝑟 .op = Revoke(𝑒𝑑# ) ∧ may_revoke(𝑒𝑟 )} ∪ revocations(𝐸, 𝑒𝑑 .auth) auth∗ (𝑒 ⊥ ) := {𝑒 ⊥ }

auth∗ (𝑒𝑑 ) := {𝑒𝑑 } ∪ auth∗ (𝑒𝑑 .auth)

may_revoke(𝑒𝑟 ) := 𝑒𝑟 .author = 𝑒𝑟 .auth.author ∧ 𝑒𝑟 .auth ∈ auth∗ (𝑒𝑟 .op) ∧ 𝑒𝑟 .op ≠ Revoke(𝑒 ⊥# ) Fig. 5. The delegation and revocation predicates: delegation_valid, revocations, and may_revoke. The authorization chain auth∗ (𝑒𝑑 ) contains 𝑒𝑑 and all capabilities reachable from it by following auth pointers.

GUARDTs: Decentralized Access Control for Replicated Data Types

11

by axiom; any other delegation is validated recursively along its chain: (i) The authorizing parent 𝑒𝑑 .auth must itself have a valid delegation chain; this recursion terminates at the genesis event. (ii) The author of the new delegation 𝑒𝑑 must be the replica that the parent delegates access to, its delegatee. (iii) The delegated read and write paths must be covered (⊑) by those of the parent. Together, (ii) and (iii) ensure that a replica can only pass on permissions it holds itself, and never more. Cascading Revocations. The right to revoke a delegation strictly remains with the delegator: one can only revoke access one has delegated oneself. This includes delegations that transitively depend on one’s own: a replica may revoke any delegation whose authorization chain passes through a delegation it authored (may_revoke). The genesis event cannot be revoked, as it is the root of all authority. Invalidating a delegation 𝑒𝑑 also invalidates every delegation whose authorization chain passes through 𝑒𝑑 . This closes the security gap that would otherwise emerge if a revoked principal could continue exercising authority via downstream sub-delegations. The revocations function in Figure 5 computes the set of all revocations for a given delegation event 𝑒𝑑 . It is recursive: the revocations for 𝑒𝑑 also include the revocations for its authorizing parent 𝑒𝑑 .auth. It terminates because the event graph is acyclic, so the recursion eventually reaches the genesis event 𝑒 ⊥ .

4.2.4 Cryptographic Commitments. Every replica performs authorization checks based on the shared event graph, which requires that it is replicated to all replicas, including those not permitted to read the data it records. Delta values are therefore kept separately and sent only to authorized replicas, while each update event only contains a commitment to its delta. The commitment must be hiding (confidentiality): it reveals nothing about the delta, so a replica that lacks read permissions can replicate the update event 𝑒𝑢 without learning the underlying state mutation. It must also be binding (integrity and non-equivocation): no replica, not even the author, can find a second delta 𝛿 ′ ≠ 𝛿 matching the commitment in 𝑒𝑢 , so every authorized replica that receives 𝛿 can verify it against the event graph, and correct replicas converge on identical materialized state. We achieve both properties with a salted hash. A plain hash of the delta would not suffice, as it would let an unauthorized replica guess the actual payload and then confirm the correctness of the guess by checking the hash. Update events therefore record a salted hash as a commitment:
𝑒𝑢 .op = Update (𝑠 ∥ 𝑒𝑢 .author ∥ 𝛿) # , where the salt 𝑠 is a random secret that the author chooses when creating the update and sends along with 𝛿. We assume that correct replicas choose fresh salts, i.e., salts never collide for any two commitments from correct replicas. The commitment is also bound to the author, so that no other replica can replay the public commitment in an event of its own. Under the cryptographic assumptions of our threat model (Section 2.2), this construction is hiding, since hashes are modeled as random oracles and 𝑠 is fresh and random, and binding, since hashes are collision-resistant. As the salt is irrelevant for the remainder of the paper, we treat it as part of 𝛿 and write (𝑒𝑢 .author ∥ 𝛿) # . 4.3

Enforcing Read and Write Access

In a centralized access-control system, all events are totally ordered, so the semantics are straightforward: a read or write is allowed after a delegation and until its revocation. Our protocol preserves exactly these semantics whenever there is no concurrency. In a decentralized system, however, updates can be concurrent with delegations and revocations, so we must additionally decide how a revocation affects reads and writes of updates that are concurrent with it. We answer this question for reads in Section 4.3.1 and for writes in Section 4.3.2. 4.3.1 Enforcing Read Access. The Send Delta and Receive Delta transition rules below govern the peer-to-peer dissemination of application state. Send Delta determines whether the acting replica id

12

Kuessner et al.

may_read(𝐸, id, 𝑒𝑢 , 𝛿) := 𝑒𝑢 .op = Update((𝑒𝑢 .author ∥ 𝛿) # )

∧ ∃𝑒𝑑 ∈ 𝐸 : delegation_valid(𝑒𝑑 ) ∧ 𝑒𝑑 .op.delegatee = id

∧ ¬∃𝑒𝑟 ∈ revocations(𝐸, 𝑒𝑑 ) : 𝑒𝑟 ≺ 𝑒𝑢

∧ path(𝛿) ⊑ 𝑒𝑑 .op.Πrd ∪ 𝑒𝑑 .op.Πwr

(i) (ii) (iii) (iv) (v)

Fig. 6. The predicate may_read governs read access.

may reveal a delta 𝛿 from its store Δ to a peer id𝑟 by putting it into the peer’s inbox 𝐼𝑟 ; this is where read access is enforced. Receive Delta moves a delta from the inbox of id into its store, provided that id itself may read it according to its own event graph; unsolicited deltas pushed by Byzantine peers are thus never stored. Whether a stored delta affects the application state is additionally filtered by materialization (Section 4.3.2). This is how replicas propagate authorized payload deltas (Δ) to reconcile disparate local application state. 𝛿∈Δ ∃𝑒𝑢 ∈ 𝐸 : may_read(𝐸, id𝑟 , 𝑒𝑢 , 𝛿) Send Delta

id

𝐾 [id ↦→ ⟨𝐸, Δ, 𝐼 ⟩, id𝑟 ↦→ ⟨𝐸𝑟 , Δ𝑟 , 𝐼𝑟 ⟩] − → 𝐾 [id𝑟 ↦→ ⟨𝐸𝑟 , Δ𝑟 , 𝐼𝑟 ∪ {𝛿 }⟩] Receive Delta

𝛿 ∈𝐼

∃𝑒𝑢 ∈ 𝐸 : may_read(𝐸, id, 𝑒𝑢 , 𝛿) id

𝐾 [id ↦→ ⟨𝐸, Δ, 𝐼 ⟩] − → 𝐾 [id ↦→ ⟨𝐸, Δ ∪ {𝛿 }, 𝐼 ⟩] Unlike Send Event, which sends authorization metadata without access-control filtering because such metadata reveals no confidential application data to unauthorized replicas, the selected 𝛿 in the rule Send Delta is filtered before it is sent: a correct replica transmits 𝛿 to peer id𝑟 only if the predicate may_read defined in Figure 6 holds. This filtering happens at transmission time, because a delta cannot be revoked once delivered. Condition (i) of may_read requires that the update event 𝑒𝑢 commits to the delta 𝛿 being sent, bound to the author of 𝑒𝑢 . The remaining conjuncts require some capability 𝑒𝑑 in the local event graph 𝐸 that authorizes the transmission: (ii) the capability has a valid delegation chain, (iii) it is issued to the reading replica id, (iv) no revocation of it, or of any delegation in its chain, causally precedes 𝑒𝑢 , and (v) the path that 𝛿 mutates is covered by either the read or the write permissions of 𝑒𝑑 . Write permissions suffice here because modifying a value requires observing it, so write access implies read access. Condition (iv) is what makes read access monotonic: a delta may still be delivered as long as the capability was not revoked at the time when the update was performed. Updates generated while a peer held legitimate read access thus remain accessible to that peer, even if the capability is revoked concurrently or afterward. More precisely, given an update 𝑒𝑢 committing to 𝛿, a capability 𝑒𝑑 issued to id, and a revocation 𝑒𝑟 ∈ revocations(𝐸, 𝑒𝑑 ), i.e., an authorized revocation of 𝑒𝑑 or of any delegation in its chain: (1) if 𝑒𝑢 ≺ 𝑒𝑟 , then reading 𝛿 via 𝑒𝑑 remains authorized; (2) if 𝑒𝑢 ∥ 𝑒𝑟 , then reading 𝛿 via 𝑒𝑑 remains authorized; (3) if 𝑒𝑟 ≺ 𝑒𝑢 , then reading 𝛿 via 𝑒𝑑 becomes unauthorized. This formulation aligns with the protection relation in weakly consistent access-control systems [16]: all preceding revocations must be considered. Cases (1) and (2) both satisfy this protection relation, since 𝑒𝑟 does not causally precede 𝑒𝑢 in either; only case (3), where the revocation causally precedes the commit (𝑒𝑟 ≺ 𝑒𝑢 ), violates it and strips read access. Peers thus retain the right to read

GUARDTs: Decentralized Access Control for Replicated Data Types

may_write(𝐸, 𝑒𝑢 , 𝛿) := 𝑒𝑢 .op = Update((𝑒𝑢 .author ∥ 𝛿) # )

13

(i)

∧ path(𝛿) ⊑ 𝑒𝑢 .auth.op.Πwr

(ii)

∧ ∀𝑒𝑟 ∈ revocations(𝐸, 𝑒𝑢 .auth) : 𝑒𝑢 ≺ 𝑒𝑟

(iv)

∧ 𝑒𝑢 .auth.op.delegatee = 𝑒𝑢 .author ∧ delegation_valid(𝑒𝑢 .auth)

(iii) (v)

included (𝐸, Δ) := { 𝛿 ∈ Δ | ∃𝑒𝑢 ∈ 𝐸 : may_write(𝐸, 𝑒𝑢 , 𝛿) } Ä materialized (𝐸, Δ) := included (𝐸, Δ) Fig. 7. Write access: the predicate may_write and state materialization.

deltas committed during the valid epoch of their capability, and only causally preceding revocations remove that right. Enforcing a stricter policy against concurrent reads requires a total causal serialization. Our system can achieve this by forcing all communication through a centralized coordinator [2], at the cost of giving up the benefits of decentralization. This shows that our solution is a superset of centralized enforcement: it recovers the same guarantees whenever that stricter setting is imposed. 4.3.2 Enforcing Write Access. Write access is enforced locally by each replica when it decides which of the deltas in its delta store Δ are included in its application state (Figure 7). Write authority is not checked on receipt and may change: a Byzantine peer could send deltas whose authors lack write permissions, or deltas authorized by capabilities whose concurrent revocation arrives only à later. The materialized application state is the merge of all included deltas. A delta 𝛿 is included if some update event 𝑒𝑢 committing to it satisfies the predicate may_write, which requires that: (i) the event commits to the delta 𝛿, bound to the author of the event, (ii) the path modified by 𝛿 is covered (⊑) by the write permissions of the authorizing capability 𝑒𝑢 .auth, (iii) the author of 𝑒𝑢 is the designated delegatee of that capability, (iv) every known revocation of the authorizing capability, or of any delegation in its chain, causally follows the event, i.e., is neither concurrent with nor before it, and (v) the authorizing capability is supported by a valid delegation chain. Condition (iv) implements a revocation-wins semantics: writes that are concurrent with a revocation of their authorizing capability are rejected. More precisely, given an update event 𝑒𝑢 and a revocation 𝑒𝑟 ∈ revocations(𝐸, 𝑒𝑢 .auth), i.e., an authorized revocation of 𝑒𝑢 .auth or of any delegation in its chain: (1) if 𝑒𝑢 ≺ 𝑒𝑟 , then 𝑒𝑢 remains authorized; (2) if 𝑒𝑢 ∥ 𝑒𝑟 , then 𝑒𝑢 becomes unauthorized; (3) if 𝑒𝑟 ≺ 𝑒𝑢 , then 𝑒𝑢 becomes unauthorized.

This semantics eliminates the backdating loophole. In a Byzantine setting, an adversarial replica can deliberately omit 𝑒𝑟 from its predecessor set and thus manufacture an apparent concurrency (𝑒𝑢 ∥ 𝑒𝑟 ). These backdated writes are still treated as unauthorized. 5

Correctness

In this section, we prove that our protocol provides three access-control guarantees: integrity, i.e., only authorized writes affect the materialized state (Section 5.3); confidentiality, i.e., correct replicas never disclose deltas to replicas that may not read them (Section 5.4); and availability, i.e., every authorized write eventually reaches every correct replica that may read it (Section 5.6). These

14

Kuessner et al.

results build on basic properties of the event graph (Section 5.1) and on the fact that delegations cannot expand permissions (Section 5.2). We further show that, without concurrent revocations, our semantics match those of a centralized system (Section 5.5). All guarantees hold in the presence of Byzantine replicas (Section 2.2). Byzantine replicas may put arbitrary events and deltas into the inbox of any other replica, and they may read everything in their own inbox. They are, however, bound by the cryptographic assumptions of our threat model: they cannot forge signatures of other replicas, find collisions, or invert hashes. Our goals are therefore twofold. First, no confidential delta may reach the inbox of a Byzantine replica that lacks read access to it. Second, whatever Byzantine replicas place into the inbox of a correct replica must not cause it to include an unauthorized write in its materialized state. Purely local operations are irrelevant to access control, so we do not further consider the Action rule in the proofs, and only assume that correct replicas do not make up data for paths they may not read. 5.1

Event Graph Properties

All subsequent results rely on a few basic properties of event graphs. Lemma 5.1 is less a result in its own right than a summary of what our assumptions provide: the properties follow almost directly from the cryptographic assumptions of our threat model, the construction of events in Action, and the causally_ready check in Receive Event. Lemma 5.1 (Well-Formed Event Graphs). Let 𝐸 be the event graph of a correct replica in a reachable configuration. Then: (1) the happened-before relation ≺ (Definition 4.7) is a strict partial order on 𝐸, and 𝐸 contains all causal predecessors of its events; (2) the genesis event 𝑒 ⊥ is the unique minimal event of 𝐸; (3) the pre and auth links of an event cannot be changed or forged; (4) for every 𝑒 ∈ 𝐸 with 𝑒 ≠ 𝑒 ⊥ , we have 𝑒.auth ≺ 𝑒, and thus auth∗ (𝑒) ⊆ 𝐸.

Proof sketch. 𝐸 starts as {𝑒 ⊥ } and only grows by Action and Receive Event. Action creates an event whose predecessors are the (non-empty) heads of 𝐸 and whose authorizing capability is in 𝐸; Receive Event admits only causally ready events, whose predecessors are in 𝐸 and, unless the event is 𝑒 ⊥ (which is already in 𝐸), non-empty and include the authorizing capability in their causal past (Section 4.2.2). Thus every new event only points to existing events, which yields (1), (2), and (4). (3) follows from the cryptographic assumptions (Section 2.2): links are collision-resistant hashes inside a signed event. □ Since the event graph is grow-only and replicated without access-control filtering, it converges under the eventual-delivery assumption (Section 2.2). Theorem 5.2 (Event Graph Convergence). Every event in the event graph of a correct replica is eventually in the event graph of every correct replica. Proof. Event graphs are grow-only sets, and Send Event and Receive Event filter nothing. The only premise, causally_ready, merely orders deliveries: by Lemma 5.1, the predecessors of an event of a correct replica are also in its graph and are thus delivered as well. □ 5.2

Capabilities Cannot Be Expanded

We prove that colluding Byzantine replicas cannot extend their permissions. Intuitively, whatever permissions a group of Byzantine replicas delegates, they are no more than the permissions delegated to the group from the outside, i.e., by a correct replica.

GUARDTs: Decentralized Access Control for Replicated Data Types

15

Theorem 5.3 (No Expansion of Permissions). Let B ⊆ I be a set of (possibly colluding) Byzantine replicas, and let 𝑒𝑑 be a delegation event with delegation_valid (𝑒𝑑 ) and 𝑒𝑑 .author ∈ B. Then there is a delegation event 𝑒𝑔 ∈ auth∗ (𝑒𝑑 ) that is either 𝑒 ⊥ or authored by a correct replica, that delegates to a member of the group (𝑒𝑔 .op.delegatee ∈ B), and 𝑒𝑑 grants no more read and write permissions than 𝑒𝑔 (𝑒𝑑 .op.Πrd ⊑ 𝑒𝑔 .op.Πrd and 𝑒𝑑 .op.Π wr ⊑ 𝑒𝑔 .op.Πwr ).

Proof. If the initiating replica id⊥ = 𝑒 ⊥ .op.delegatee is in B, the Byzantine replicas already hold full permissions via 𝑒 ⊥ , which trivially cannot be expanded further. Otherwise, id⊥ ∉ B. Since delegation_valid (𝑒𝑑 ) holds, unfolding its recursive clause shows that every delegation in the authorization chain auth∗ (𝑒𝑑 ) satisfies delegation_valid, and that the chain contains 𝑒 ⊥ , the only base case. Every event is signed by its author (Definition 4.4), so an event whose author is a correct replica was indeed created by that replica: replicas in B cannot sign in its name. Follow the auth pointers from 𝑒𝑑 towards 𝑒 ⊥ , and let 𝑒𝑔 be the first delegation reached that is 𝑒 ⊥ or authored by a correct replica. Let 𝑒ℎ be the delegation visited just before 𝑒𝑔 , i.e., 𝑒ℎ .auth = 𝑒𝑔 . All delegations visited from 𝑒𝑑 up to 𝑒ℎ are authored by replicas in B, and by delegation_valid(𝑒ℎ ), the author of 𝑒ℎ is the delegatee of its parent, so 𝑒𝑔 .op.delegatee = 𝑒ℎ .author ∈ B. Thus, 𝑒𝑔 is the delegation by which a correct replica initially granted permissions to the group B. By delegation_valid, each of these delegations grants a subset of the permissions of its parent; since ⊑ is transitive, 𝑒𝑑 grants a subset of the permissions of 𝑒𝑔 , i.e., the permissions initially granted by the correct replica have not been expanded within the group. □ 5.3

Write Integrity

Write integrity states that every write needs to be justified by a non-revoked delegation. Because later revocations may invalidate already received writes, we enforce integrity by filtering the deltas included by materialization (Figure 7). Theorem 5.4 (Write Integrity). Let 𝐸 be an event graph and Δ a delta store. If 𝛿 ∈ included (𝐸, Δ), then (1) there is an update event 𝑒𝑢 ∈ 𝐸 that commits to 𝛿, i.e., 𝑒𝑢 .op = Update((𝑒𝑢 .author ∥ 𝛿) # ), and that is authorized by a delegation 𝑒𝑑 = 𝑒𝑢 .auth that grants 𝑒𝑢 .author write access to path(𝛿), (2) that is not revoked, i.e., for every 𝑒 ∈ auth∗ (𝑒𝑑 ) and every 𝑒𝑟 ∈ 𝐸 with 𝑒𝑟 .op = Revoke(𝑒 # ) and may_revoke(𝑒𝑟 ), we have 𝑒𝑢 ≺ 𝑒𝑟 .

Proof. By definition of included, there is an 𝑒𝑢 ∈ 𝐸 with may_write(𝐸, 𝑒𝑢 , 𝛿). (1) is conjuncts (i)–(iii) of may_write (Figure 7). (2) revocations(𝐸, 𝑒𝑑 ) recurses along the auth pointers (Figure 5), so it contains every 𝑒𝑟 described in (2). Conjunct (iv) of may_write requires 𝑒𝑢 ≺ 𝑒𝑟 for all of them. □

Theorem 5.4 only states that a non-revoked delegation 𝑒𝑑 exists. Since may_write also requires delegation_valid (𝑒𝑑 ), Theorem 5.3 additionally ensures that 𝑒𝑑 stems from a delegation chain that does not expand rights: even if Byzantine replicas created 𝑒𝑑 , it grants no more than they were given by a correct replica or the genesis event. 5.4

Read Confidentiality

We prove that correct replicas do not reveal confidential writes2 , i.e., delta values, to replicas lacking the corresponding read permissions. A delta is revealed to a replica as soon as it is placed into that replica’s inbox, which for correct senders only happens via Send Delta; whether and when the 2We cannot guarantee confidentiality of data that Byzantine replicas may read: they can simply send it to unauthorized

replicas, or, with sufficient write access, re-commit it in a backdated update that is concurrent with a revocation of another replica’s read access, making it readable by the revoked replica. Such leaks are outside the scope of our guarantees.

16

Kuessner et al.

receiver id𝑟 takes it out via Receive Delta is irrelevant for confidentiality. Theorem 5.6 shows that a correct sender places a delta 𝛿 into the inbox of id𝑟 only when id𝑟 holds a valid read capability for it, and that this decision is never invalidated by revocations that arrive later. The decision whether a delta may be sent must not be reversed by events that arrive later. Read access for a specific delta is indeed never revoked: Lemma 5.5 (Read Authorization Is Stable). Let 𝐸 and 𝐸 ′ with 𝐸 ⊆ 𝐸 ′ be causally closed event graphs. If 𝑒𝑢 ∈ 𝐸 and may_read(𝐸, id, 𝑒𝑢 , 𝛿), then may_read(𝐸 ′, id, 𝑒𝑢 , 𝛿).

Proof. Take the delegation 𝑒𝑑 chosen by may_read(𝐸, id, 𝑒𝑢 , 𝛿), which is in 𝐸 ′ since 𝐸 ⊆ 𝐸 ′ . No conjunct of may_read except the revocation conjunct depends on the event graph, so it remains to show that no 𝑒𝑟 ∈ revocations(𝐸 ′, 𝑒𝑑 ) satisfies 𝑒𝑟 ≺ 𝑒𝑢 . Suppose such an 𝑒𝑟 exists. Then 𝑒𝑟 is a causal predecessor of 𝑒𝑢 ∈ 𝐸, so 𝑒𝑟 ∈ 𝐸. As may_revoke does not depend on the event graph, 𝑒𝑟 ∈ revocations(𝐸, 𝑒𝑑 ), contradicting may_read(𝐸, id, 𝑒𝑢 , 𝛿). □ Correct replicas’ event graphs satisfy the premise, since Receive Event only admits causally ready events.

Theorem 5.6 (Read Confidentiality). Let a correct replica id with event graph 𝐸 take a Send Delta step that places 𝛿 into the inbox of id𝑟 . Then there is an update event 𝑒𝑢 ∈ 𝐸 that commits to 𝛿 and a delegation 𝑒𝑑 ∈ 𝐸 with delegation_valid(𝑒𝑑 ) that grants id𝑟 read (or write) access to path(𝛿), and this send is never invalidated: may_read(𝐸 ′, id𝑟 , 𝑒𝑢 , 𝛿) holds for every later event graph 𝐸 ′ of any correct replica with 𝐸 ⊆ 𝐸 ′ .

Proof. Since id is correct, the premise of Send Delta holds: may_read(𝐸, id𝑟 , 𝑒𝑢 , 𝛿) for some 𝑒𝑢 ∈ 𝐸, whose conjuncts (Figure 6) give the delegation 𝑒𝑑 . By Lemma 5.5, may_read still holds in 𝐸 ′ . □

Together with Theorem 5.3, this ensures that the path is legitimately readable by id𝑟 : 𝑒𝑑 stems from a delegation chain that does not expand rights. Intuitively, every revocation that causally precedes 𝑒𝑢 is already known to the sender, and revocations that are concurrent with or causally after 𝑒𝑢 do not apply to reads (Section 4.3.1). A revocation 𝑒𝑟 ∥ 𝑒𝑢 may be unknown to any replica holding 𝛿, in particular to the author of 𝑒𝑢 , which may already have sent 𝛿 before learning of 𝑒𝑟 ; a delta, once placed into an inbox, cannot be retracted. This is precisely why concurrent revocations do not remove read access: it would not be possible to enforce. Enforcing concurrent revocations would make the read policy depend on delivery order, which no correct replica can guarantee. Revocations still take effect for causally dependent updates: any update event 𝑒𝑢′ created after a replica learned of 𝑒𝑟 is causally after 𝑒𝑟 , so the revocation applies to 𝑒𝑢′ . No correct replica sends the delta for 𝑒𝑢′ based on a delegation that was revoked causally before 𝑒𝑢′ . Theorem 5.7 (Read Confidentiality After Revocation). Let a correct replica id with event graph 𝐸 create an update event 𝑒𝑢 committing to 𝛿, and let 𝑒𝑑 be a delegation that is revoked in 𝐸, i.e., revocations(𝐸, 𝑒𝑑 ) ≠ ∅. Then no correct replica ever sends 𝛿 to id𝑟 = 𝑒𝑑 .op.delegatee based on 𝑒𝑑 .

Proof. A correct replica with event graph 𝐸 ′ places 𝛿 into the inbox of id𝑟 only via Send Delta, which requires some 𝑒𝑢′ ∈ 𝐸 ′ with may_read(𝐸 ′, id𝑟 , 𝑒𝑢′ , 𝛿) that in turn requires a delegation 𝑒𝑑′ that is not revoked in 𝐸. We show that 𝑒𝑢 is the only possible update 𝑒𝑢′ = 𝑒𝑢 and that it was authorized by a non-revoked delegation 𝑒𝑑′ ≠ 𝑒𝑑 . 𝑒𝑢′ = 𝑒𝑢 . may_read requires that 𝑒𝑢′ commits to 𝛿 written by 𝑒𝑢′ .author. Since events are signed, ′ 𝑒𝑢 was created by 𝑒𝑢′ .author. If 𝑒𝑢′ .author = id, i.e., the correct replica that created 𝑒𝑢 , then because of the fresh salt (Section 4.2.4), it commits to 𝛿 only once, so 𝑒𝑢′ = 𝑒𝑢 . If 𝑒𝑢′ .author ≠ id, the salt in 𝛿 is not fresh, so 𝑒𝑢′ .author is Byzantine; we thus disregard this case.

GUARDTs: Decentralized Access Control for Replicated Data Types

17

𝑒𝑑′ ≠ 𝑒𝑑 . The predecessors of 𝑒𝑢 are the heads of 𝐸, so 𝑒 ≺ 𝑒𝑢 for every 𝑒 ∈ 𝐸. As 𝑒𝑢 ∈ 𝐸 ′ and ′ 𝐸 is closed under predecessors (Lemma 5.1), 𝐸 ⊆ 𝐸 ′ . Now let 𝑒𝑑′ be the delegation chosen by may_read(𝐸 ′, id𝑟 , 𝑒𝑢 , 𝛿). By definition of may_read, there is no revocation 𝑒𝑟 ∈ revocations(𝐸 ′, 𝑒𝑑′ ) : 𝑒𝑟 ≺ 𝑒𝑢 . Thus, if such an 𝑒𝑟 is not in 𝐸 ′ , it also cannot be in 𝐸, as revocations(𝐸, 𝑒𝑑′ ) ⊆ revocations(𝐸 ′, 𝑒𝑑′ ) with 𝐸 ⊆ 𝐸 ′ . By assumption 𝑒𝑑 has a revocation 𝑒𝑟 ∈ 𝐸, which implies that 𝑒𝑑′ ≠ 𝑒𝑑 . □ Receiving. A Byzantine replica could simply send deltas to a correct replica that the latter is not permitted to read. This is technically no breach of confidentiality, since information from Byzantine replicas is not protected. However, it is still undesired: a correct replica should not store or process data it may not read.

Corollary 5.8 (No Unauthorized Reception). In any reachable configuration, the delta store Δ of a correct replica id with event graph 𝐸 (and thus its materialized state) contains no delta it may not read: for every 𝛿 ∈ Δ there is an 𝑒𝑢 ∈ 𝐸 with may_read(𝐸, id, 𝑒𝑢 , 𝛿). Proof. A delta enters Δ only through an Action step, where may_read holds by the threat-model assumption, or through Receive Delta, whose premise excludes every delta the replica may not read. As 𝐸 grows afterwards, may_read remains valid by Lemma 5.5. □ 5.5

Centralized Semantics Without Concurrency

To further strengthen the case for the design decisions made in our protocol, we compare the semantics to a centralized system that rules out concurrent operations. In particular, we show that without concurrent revocations, our semantics match those of a centralized system. Corollary 5.9 (Centralized Semantics Without Concurrency). If no event in 𝐸 is concurrent with a revocation, then an update 𝑒𝑢 is authorized for reading and writing via a delegation 𝑒𝑑 if and only if 𝑒𝑑 was not yet revoked when 𝑒𝑢 was committed, as in a centralized access-control system. Proof. Writes before a revocation are authorized and writes after it are not (Theorem 5.4); the same holds for reads (Theorem 5.7). Without concurrency, these are the only cases. □ Here, a read takes place at commit time: a delta delivered after a revocation but committed before it corresponds to a read that a centralized system would have permitted before the revocation. 5.6

Availability and Convergence

Availability, as a security goal, states that every write, i.e., every delta 𝛿 committed by an update event 𝑒𝑢 with may_write(𝐸, 𝑒𝑢 , 𝛿), eventually becomes visible to every correct replica that may read it. Since the policy evolves dynamically, this first requires that delegations and revocations are eventually applied at every correct replica, which is guaranteed by Theorem 5.2. First, Lemma 5.10 shows that write access implies read access, so every authorized delta has at least one reader, its author, who includes it. Then, Theorem 5.11 shows that if a correct replica includes a delta and believes that another correct replica may read it too, then that other replica eventually includes the delta as well. Lemma 5.10 (Write Authority Implies Read Authority). For every event graph 𝐸 of a correct replica in a reachable configuration, update event 𝑒𝑢 ∈ 𝐸, and delta 𝛿: may_write(𝐸, 𝑒𝑢 , 𝛿) =⇒ may_read(𝐸, 𝑒𝑢 .author, 𝑒𝑢 , 𝛿).

Proof. The predicate may_read (Figure 6) asks for some delegation 𝑒𝑑 that grants the reader access to the path, and it accepts write permissions as well as read permissions for this. may_write already provides such a capability: the delegation 𝑒𝑑 = 𝑒𝑢 .auth that authorizes the write. We check that it satisfies each conjunct of may_read:

18

Kuessner et al.

• 𝑒𝑑 ∈ 𝐸: by Lemma 5.1 (4), the authorizing capability of 𝑒𝑢 ∈ 𝐸 is in 𝐸. • 𝑒𝑢 commits to 𝛿 and 𝑒𝑑 is valid: both are also conjuncts of may_write. • 𝑒𝑑 is granted to the reader 𝑒𝑢 .author : may_write requires 𝑒𝑢 .author to be the delegatee of 𝑒𝑑 . • 𝑒𝑑 covers the path: may_write gives path(𝛿) ⊑ 𝑒𝑑 .op.Π wr , which is part of 𝑒𝑑 .op.Π rd ∪ 𝑒𝑑 .op.Πwr . • 𝑒𝑑 is not revoked before 𝑒𝑢 : may_write requires every revocation of 𝑒𝑑 to come after 𝑒𝑢 , and an event cannot be both before and after 𝑒𝑢 . □ Theorem 5.11 (Availability). Let id be a correct replica with event graph 𝐸 and delta store Δ that includes a delta 𝛿, with the corresponding update event 𝑒𝑢 with may_write(𝐸, 𝑒𝑢 , 𝛿), and let id𝑟 be a correct replica with may_read(𝐸, id𝑟 , 𝑒𝑢 , 𝛿). Then eventually, for the event graph 𝐸 ′ and delta store Δ′ of id𝑟 , either 𝛿 ∈ included (𝐸 ′, Δ′ ), or 𝐸 ′ contains a revocation 𝑒𝑟 ∈ revocations(𝐸 ′, 𝑒𝑢 .auth) with 𝑒𝑢 ⊀ 𝑒𝑟 . Proof. By Theorem 5.2, the event graph of id𝑟 eventually contains 𝐸. As may_read remains valid when the event graph grows (Lemma 5.5), may_read(·, id𝑟 , 𝑒𝑢 , 𝛿) then holds in the graphs of both id and id𝑟 and keeps holding: read access for a specific delta is never revoked (cf. Theorem 5.6). Thus Send Delta of 𝛿 from id to id𝑟 and then Receive Delta at id𝑟 are enabled and remain so, and by eventual delivery 𝛿 ∈ Δ eventually. Deltas are never removed, so 𝛿 is included if may_write(𝐸 ′, 𝑒𝑢 , 𝛿). All conjuncts of may_write except the revocation conjunct do not depend on the event graph and hold since they hold in 𝐸; so if may_write(𝐸 ′, 𝑒𝑢 , 𝛿) fails, there is an 𝑒𝑟 ∈ revocations(𝐸 ′, 𝑒𝑢 .auth) with 𝑒𝑢 ⊀ 𝑒𝑟 . □ Beyond availability, access control also preserves the convergence of the underlying ARDTs among replicas with the same read permissions: Corollary 5.12 (Eqal Read Access, Eqal State). Let id1 and id2 be correct replicas, and suppose that from some point on no new events are created, so that both eventually hold the same event graph 𝐸 (Theorem 5.2). If may_read(𝐸, id1, 𝑒𝑢 , 𝛿) ⇔ may_read(𝐸, id2, 𝑒𝑢 , 𝛿) for all 𝑒𝑢 and 𝛿, then eventually their materialized states are equal. Proof. By Theorem 5.11, every delta included at one replica is eventually included at the other, as both share 𝐸 and agree on may_read; so the included sets eventually coincide. The materialized states are then joins of the same deltas, which are equal as the ARDT merge is associative, commutative, and idempotent. □ 6

Evaluation

We empirically quantify the computational overhead of the GUARDTs event graph relative to two HashDAGs without access control as baselines, with and without signatures. 6.1

Experimental Setup

System Variants. HashDAGs are a common construction for Byzantine fault-tolerant CRDTs [3, 8, 9]. They are used in Matrix [5] and also in Automerge, which is not Byzantine fault-tolerant. We therefore compare GUARDTs against two HashDAG baselines without access control, in which each entry records the ARDT delta, the author’s identity, and the hashes of the preceding heads. The baselines differ only in whether entries are signed with Ed25519. Signatures are needed in any Byzantine setting to authenticate authors, independently of access control. Comparing against both baselines thus separates the cost of signatures from the additional cost of our access-control mechanism.

GUARDTs: Decentralized Access Control for Replicated Data Types

19

id ⊥ : *

id 4 : a.a

id 5 : a.b

id 3 : c

id 2 : b

id 1 : a id 6 : a.c

id 7 : b.a

id 8 : b.b

id ⊥ rev 1 : id 1 − a id ⊥

id ⊥

id ⊥

id ⊥

id 3

id ⊥ : *

id 1 : a

id 2 : b

id 3 : c

𝑢1

id 10 : c.a

id 11 : c.b

id 1 rev 2 : id 4 − a.a

···

id 2

id 1

𝑢𝑛/2 id 4 : a.a

phase 1: 𝑛2 updates by id 1 –id 3 delegate

id 9 : b.c

···

id 3

id 2

id 12 : c.c 𝑢 (𝑛/2) +1

id 12 : c.c

id 1 rev 3 : id 4 − a.a

···

id 9

id 4

𝑢𝑛−1

𝑢𝑛 rev 4 : id 1 − a

id ⊥

phase 2: 𝑛2 updates by id 1 –id 12 update

revoke

pre

Fig. 8. The benchmark trace with the delegation hierarchy at the top showing the write paths delegated to each replica. At the bottom is the event graph of the trace, with events labeled with their author. The "· · · " stand for elided events, and 𝑛 ∈ {10 000, 100 000} is the number of updates. Delegations are annotated with the replica they delegate to and the write path they delegate, and revocations with the write path of the capability they revoke. While all revocations are shown in the graph, they are only included in the revocation-specific benchmarks and only one of them per benchmark.

The overhead of access control does not depend on the semantics of the replicated application state, i.e., on how deltas are merged. We therefore choose a cheap application ARDT to isolate the access-control overhead from the cost of the application itself. For more expensive ARDTs, the absolute overhead stays the same and its relative share only shrinks. Concretely, we use nested product ARDTs of counters: the products provide multiple paths to exercise access control, while counters have a small, fixed cost per operation. We name the fields a, b, and c at each level, so a path to a counter is, e.g., a.a.b. Benchmarks. We benchmark the isolated overhead of individual event graph operations: (1) Creating Updates: creating an event, computing the delta and its commitment, and selecting a capability with sufficient permissions; (2) Sending Updates to a peer: filtering according to the peer’s read permissions; (3) Receiving Updates: integrating the event into the local event graph, and merging the delta into the materialized application state; (4) Applying Revocations: adding the revocation event to the graph and, if necessary, invalidating updates that become unauthorized and recomputing the materialized state. The benchmark uses a generated trace with two phases, each containing half of the updates (Figure 8). In the first, an initial replica delegates partial write and full read access to three replicas, which then perform updates. In the second, each of these replicas delegates parts of its access to three new replicas, after which all replicas perform updates. Altogether, the trace has 13 replicas: the initial replica, which only delegates, and 12 that concurrently perform updates. We use a trace with 100 000 updates. Trace size has negligible impact on operations (1) to (3), so we additionally use a trace with 10 000 updates only for revocations (4). To ensure a fair comparison, all updates are authorized and every replica has full read access: unauthorized updates would be filtered out before reaching the application state, and withheld deltas would not be sent, both artificially reducing the cost of the system with access control. We report the computational cost of a single replica

20

Kuessner et al.

executing each operation. Only the author creates an update (1), while other replicas also send (2) and receive (3) it. Operations (1) to (3) are thus on the critical path until an update becomes visible at a directly connected replica, while relaying an existing update involves only (2) and (3). Receiving a revocation is only expensive if the receiver has already applied an update that is concurrent with the revocation and authorized by the revoked delegation. The materialized state must then be fully recomputed without that update, because ARDT deltas have no inverse that could subtract it. We assume that revocations are rare compared to updates, and revocations concurrent with an affected update rarer still, especially among well-connected replicas. We thus quantify the cost of recomputation but exclude it from the critical path. For benchmark (4), the cost depends on the size of the event graph and the revocation’s position within it, so we evaluate four revocation scenarios, rev 1 to rev 4 in Figure 8. rev 1 revokes the delegation of a right after it is issued, so it is concurrent with all updates and invalidates roughly 13 of them. rev 2 revokes the delegation of a.a right after it is issued in the middle of the trace, so it is concurrent with half of the updates and invalidates roughly 4 % of them. rev 3 is concurrent only with the last update, which it invalidates. Finally, rev 4 is placed after all updates and invalidates none. For rev 1 to rev 3 , we compare traces with 10 000 and 100 000 updates, whereas rev 4 requires no rematerialization and is thus unaffected by trace size. Our benchmarks do not include actual networks: values are only serialized and deserialized into in-memory data structures. The per-update bandwidth overhead is modest: each update event gains a 32-byte SHA3-256 commitment and each delta a 32-byte salt, comparable to the 64 bytes per signature and 32 bytes per predecessor pointer of the signed baseline. Delegation and revocation events have no counterpart without access control, but carry only a few short path strings or a single hash pointer. Assuming both are far rarer than updates, their bandwidth cost is negligible wherever the baseline is viable. Hardware and Software Setup. All benchmarks ran on a desktop computer with an AMD Ryzen 9 5950X processor and Arch Linux (kernel 7.2.6), using OpenJDK 27 and the Java Microbenchmark Harness (JMH). Ed25519 signatures were computed with the Bouncy Castle library. 6.2

Results

(1) Creating Updates. The first benchmark measures the average time to create and locally apply an update event. Figure 9 shows the average runtimes for a trace of 100 000 updates in its three left bars. The cost is dominated by Ed25519 signing: both signed systems are roughly 30 𝜇s slower than the unsigned baseline, while access control adds only roughly 1 𝜇s on top of the signed baseline. (2) Sending Updates. The second benchmark measures the average time a replica spends sending a single delta to a peer. For the access-control system, this involves verifying that the peer holds a valid capability for reading the delta’s path, then serializing the authorization event and the delta payload separately. The results appear in the second group of Figure 9. The two baselines behave similarly: since no signatures are computed in this step, the additional metadata carried by signatures accounts for a difference of only about 0.1 𝜇s between them. The access-control system adds roughly 0.6 𝜇s over both baselines. (3) Receiving Updates. The third benchmark measures the overhead of processing a received update. For the access-control system, this includes deserializing the event and the delta, computing the event hash and verifying the commitment and signature, and checking read and write authorization. As Figure 9 shows, signature verification dominates: both signed systems perform similarly, with the transition from unsigned to signed adding about 70 𝜇s, while the access-control system adds only roughly 3 𝜇s on top of the signed baseline.

GUARDTs: Decentralized Access Control for Replicated Data Types

HashDAG (unsigned)

21

HashDAG (signed)

80

Time per event [𝜇s]

rev 4 rev 40

Access control 72.6

75.1

70.3

70.8

60

40

37.4

36.3

20 7.8 0.653

0.535

0 Create update

3.8

1.12

Send update

Receive update

Receive non-concurrent revocation

Fig. 9. Time to create, send, and receive updates and to receive non-concurrent revocations with a trace of 100 000 updates. Error bars are JMH’s 99.9 % confidence intervals over five measured iterations. rev 1

Without snapshot

Time of receive [ms]

250

rev 3

Merge all deltas

With snapshot 236

Only merge 193

200 147

150

179

194

188

188

188 140

128

100 50

rev 2

13.3 18.3 18.8 19.3

16.8 10.7

0 10,000

100,000

#Updates in event graph

0.193

10,000

19.3

2.2

100,000

#Updates in event graph

Fig. 10. Time for receiving a concurrent revocation event with and without snapshots, for a trace of 10 000 and 100 000 events. Error bars are JMH’s 99.9 % confidence intervals over five measured iterations.

(4) Applying Revocations. Since creating a revocation requires no recomputation, we only measure receiving revocations, for which the baselines have no counterpart. We first consider the nonconcurrent revocation rev 4 of a and the analogous revocation rev 4′ of a.a, which invalidate no applied updates: as the rightmost group of Figure 9 shows, receiving them is about as efficient as receiving a regular update. Figure 10 shows the concurrent revocations rev 1 to rev 3 . Revocations that require rematerialization are significantly more expensive than the other operations (note that the plot is in ms). Most of this cost is due to merging the remaining, non-revoked deltas (bottom part of each bar), while

22

Kuessner et al.

the top part shows the additional cost of the revocation logic. As a baseline, Merge all deltas shows the time to merge all deltas of the event graph without any revocation, i.e., a full materialization. The revocations rev 1 to rev 3 invalidate less and less of the state: rev 1 invalidates ≈ 13 of the updates, rev 2 ≈ 4 %, and rev 3 a single update. Consequently, the revocation logic gets cheaper (19 ms, 14 ms, and 6 ms, respectively), while recomputation gets more expensive, as more deltas remain to be merged (128 ms, 179 ms, and 188 ms, respectively, the latter as expensive as merging all deltas). Overall, every concurrent revocation is significantly more expensive than a non-concurrent one, and costs about as much as a full materialization. Revocation With Snapshots. Since merging dominates the cost of concurrent revocations, snapshots can reduce it. We use a simple strategy: a single snapshot at the causal stability frontier, i.e., the point seen by all replicas, so that, barring backdating, no revocation can be concurrent with the deltas in the snapshot. In our benchmarks, this snapshot is taken right before the revocation. For rev 1 , the snapshot is effectively empty, so there is no potential for optimization. The approach is even slower (236 ms vs. 147 ms without snapshots), since deciding which deltas to include is more costly. rev 2 is faster with the snapshot (140 ms vs. 193 ms), as only roughly half of the deltas need to be merged on top of the snapshot. For rev 3 , which invalidates a single update near the end of the trace, the cost falls from 194 ms to 2 ms, because partial recomputation amounts to merging a single delta on top of the snapshot. Discussion of Results. The absolute overhead of access control is small in comparison to signature processing. Creating, sending, and receiving an update together take ≈ 114 𝜇s with access control, only ≈ 4 𝜇s or ≈ 4 % more than with the signed baseline. Receiving a revocation that invalidates no applied updates is about as efficient as receiving a regular update. Revocations that invalidate applied updates, which we assume to be rare and which are not on the critical path, incur two costs. The access-control logic, i.e., determining the invalidated updates, adds only 6–19 ms at 100 000 updates. The dominant cost is rematerialization, i.e., merging the remaining deltas, which depends on the application’s ARDT and grows roughly linearly with the number of updates. Without backdating, snapshots at the causal stability frontier avoid most of this merging cost. We conclude from these observations that GUARDTs introduce acceptable overheads in open networks with latencies above 1 ms and human-scale operation frequencies. 7

Related Work

Renaux et al. [13] propose an access-control scheme for synchronizing JSON CRDTs between untrusted clients and a trusted central server that enforces access control. Permissions are specified using a policy specification language based on the paths in the JSON CRDTs. Their use of paths is similar to that of GUARDTs, but their policy language is more expressive. Their approach, however, requires a single trusted centralized server, is tied to JSON CRDTs, and assumes a static policy. Rault et al. [12] propose access control for CRDTs using a policy CRDT in conjunction with a separate data-storing CRDT. The merge function for the policy CRDT resolves conflicts using a combination of the authors’ role hierarchy and a deterministic tie-breaker. To avoid divergence of state caused by concurrent policy and data operations, their model requires undo and redo operations for both CRDTs, which are used to roll back conflicting operations. In contrast to our approach, which supports fine-grained access control for arbitrary ARDT compositions, their scheme is limited to specific CRDT constructions and is not Byzantine fault-tolerant. Weber et al. [15, 16] propose access control for a weakly consistent information system in which mutually trusted servers replicate a dataset and enforce access control towards external clients.

GUARDTs: Decentralized Access Control for Replicated Data Types

23

The servers also replicate a policy CRDT that resolves concurrent policy versions by their intersection, granting only permissions present in all of them. While their setting differs from ours – the data-management layer versus the application-programming layer – the two approaches share correctness criteria: policy updates and dependent operations must be handled in causal order (protection relation), and conflicting policy updates must be resolved in favor of restrictions (conservative conflict resolution). For reads, however, conservative resolution of concurrent revocations is impossible without a total order [18], so we enforce only causally preceding ones. Wobber et al. [17] were the first to propose eventually consistent access control for mutually distrustful replicas without central synchronization infrastructure. Their approach authenticates updates with signatures and detects unauthorized writes, but neither tolerates Byzantine replicas nor ensures convergence itself. Policies are specified in a separate logical assertion language over a flat namespace of item labels, independent of the structure of the data. Jacob and Hartenstein [6] present a theoretical model for eventually consistent access control (ECAC) that draws inspiration from the Matrix system. The model derives a mutable total order of events over which authorization policies can be specified. GUARDTs do not rely on such a derived total order but instead exploit the immutable causal order of the event graph. Crucially, the model by Jacob and Hartenstein targets the replication layer, not the application layer. As such, it leaves open how policies are structured relative to application data, while we derive fine-grained, path-based permissions from the application data structure. Yanakieva et al. [18] study access control for partition-tolerant distributed file systems with POSIX-like semantics. They show that, without a total order, a file system cannot enforce standard POSIX access control, supporting our conclusion that revocations require more nuanced semantics for concurrent reads and writes. 8

Conclusion

We presented GUARDTs, replicated data types with decentralized access control for strongly eventually consistent systems with mutually distrustful replicas. Unlike existing approaches, which require a trusted coordinator or static policies, assume cooperative replicas, or are tied to specific data-type constructions, GUARDTs achieve all four properties that principled decentralized access control for RDTs demands. Path-based capabilities derived from the tree structure of ARDTs express fine-grained read and write permissions over arbitrary application data types (generality). Replicas can delegate and transitively revoke capabilities at runtime (policy evolution). Authorization events are recorded in a signed HashDAG replicated as a CRDT among all replicas, providing tamper-evident, causally ordered evidence for local authorization decisions that remain correct under Byzantine behavior (Byzantine resilience). Every replica enforces access control by filtering outgoing deltas and verifying authority on incoming ones, with no central policy server (decentralization). We formally proved that GUARDTs guarantee confidentiality, integrity, and availability despite concurrent policy changes and Byzantine replicas. Empirically, the total per-operation overhead of access control over a signed HashDAG baseline is roughly 4 %, confirming that the mechanism is practical. The dominant cost of revocations that invalidate already-applied updates is rematerialization of the affected state. Snapshots at the causal stability frontier can reduce this overhead. As interesting avenues for future work, we see using encryption as a complementary or alternative means of enforcing read access. Another extension is to automatically derive the set of paths that an application-level operation requires, such as appending an element to a list, which modifies multiple paths, or to use more expressive path descriptors inside the capabilities.

24

Kuessner et al.

References [1] Paulo Sérgio Almeida, Ali Shoker, and Carlos Baquero. 2018. Delta State Replicated Data Types. J. Parallel and Distrib. Comput. 111 (Jan. 2018), 162–173. doi:10.1016/j.jpdc.2017.08.003 [2] Kegan Dougal. 2026. ERA: Epoch-Resolved Arbitration for Duelling Admins in Group Management CRDTs. In Proceedings of the 13th International Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC ’26). Association for Computing Machinery, New York, NY, USA, 1–8. doi:10.1145/3806077.3806691 [3] Florian Jacob, Saskia Bayreuther, and Hannes Hartenstein. 2022. On CRDTs in Byzantine Environments : Conflict Freedom, Equivocation Tolerance, and the Matrix Replicated Data Type. In Sicherheit 2022 : Sicherheit, Schutz Und Zuverlässigkeit. Hrsg.: C. Wressnegger (GI-Edition : Proceedings, Vol. 323). Gesellschaft für Informatik (GI), 113–128. doi:10.18420/sicherheit2022_07 [4] Florian Jacob, Luca Becker, Jan Grashöfer, and Hannes Hartenstein. 2020. Matrix Decomposition: Analysis of an Access Control Approach on Transaction-Based DAGs without Finality. In Proceedings of the 25th ACM Symposium on Access Control Models and Technologies (SACMAT ’20). Association for Computing Machinery, New York, NY, USA, 81–92. doi:10.1145/3381991.3395399 [5] Florian Jacob, Carolin Beer, Norbert Henze, and Hannes Hartenstein. 2021. Analysis of the Matrix Event Graph Replicated Data Type. IEEE Access 9 (2021), 28317–28333. arXiv:2011.06488 [cs] doi:10.1109/ACCESS.2021.3058576 [6] Florian Jacob and Hannes Hartenstein. 2025. To the Best of Knowledge and Belief: On Eventually Consistent Access Control. In Proceedings of the Fifteenth ACM Conference on Data and Application Security and Privacy (CODASPY ’25). Association for Computing Machinery, New York, NY, USA, 107–118. doi:10.1145/3714393.3726520 [7] Martin Kleppmann. 2022. Assessing the Understandability of a Distributed Algorithm by Tweeting Buggy Pseudocode. Technical Report UCAM-CL-TR-969. University of Cambridge, Computer Laboratory. doi:10.48456/tr-969 [8] Martin Kleppmann. 2022. Making CRDTs Byzantine Fault Tolerant. In Proceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC ’22). Association for Computing Machinery, New York, NY, USA, 8–15. doi:10.1145/3517209.3524042 [9] Martin Kleppmann and Heidi Howard. 2020. Byzantine Eventual Consistency and the Fundamental Limits of Peer-toPeer Databases. arXiv:2012.00472 [cs] doi:10.48550/arXiv.2012.00472 [10] Christian Kuessner, Ragnar Mogk, Anna-Katharina Wickert, and Mira Mezini. 2023. Algebraic Replicated Data Types: Programming Secure Local-First Software. In Leibniz International Proceedings in Informatics. Schloss-Dagstuhl Leibniz Zentrum für Informatik. doi:10.4230/LIPIcs.ECOOP.2023.14 [11] Leslie Lamport, Robert Shostak, and Marshall Pease. 1982. The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst. 4, 3 (July 1982), 382–401. doi:10.1145/357172.357176 [12] Pierre-Antoine Rault, Claudia-Lavinia Ignat, and Olivier Perrin. 2022. Distributed Access Control for Collaborative Applications Using CRDTs. In Proceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC ’22). Association for Computing Machinery, New York, NY, USA, 33–38. doi:10.1145/3517209.3524826 [13] Thierry Renaux, Sam Van den Vonder, and Wolfgang De Meuter. 2023. Secure RDTs: Enforcing Access Control Policies for Offline Available JSON Data. Proceedings of the ACM on Programming Languages 7, OOPSLA2 (Oct. 2023), 227:146–227:172. doi:10.1145/3622802 [14] Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. 2011. Conflict-Free Replicated Data Types. In Stabilization, Safety, and Security of Distributed Systems, Xavier Défago, Franck Petit, and Vincent Villain (Eds.). Springer, Berlin, Heidelberg, 386–400. doi:10.1007/978-3-642-24550-3_29 [15] Mathias Weber and Annette Bieniusa. 2018. ACGreGate: A Framework for Practical Access Control for Applications Using Weakly Consistent Databases. arXiv:1801.07005 [cs] doi:10.48550/arXiv.1801.07005 [16] Mathias Weber, Annette Bieniusa, and Arnd Poetzsch-Heffter. 2016. Access Control for Weakly Consistent Replicated Information Systems. In Security and Trust Management, Gilles Barthe, Evangelos Markatos, and Pierangela Samarati (Eds.). Springer International Publishing, Cham, 82–97. doi:10.1007/978-3-319-46598-2_6 [17] Ted Wobber, Thomas L. Rodeheffer, and Douglas B. Terry. 2010. Policy-Based Access Control for Weakly Consistent Replication. In Proceedings of the 5th European Conference on Computer Systems (EuroSys ’10). Association for Computing Machinery, New York, NY, USA, 293–306. doi:10.1145/1755913.1755943 [18] Elena Yanakieva, Michael Youssef, Ahmad Hussein Rezae, and Annette Bieniusa. 2021. On the Impossibility of Confidentiality, Integrity and Accessibility in Highly-Available File Systems. In Networked Systems, Karima Echihabi and Roland Meyer (Eds.). Springer International Publishing, Cham, 3–18. doi:10.1007/978-3-030-91014-3_1

Related documents

• Defending the Data Access Spectrum.#423127
• Revocation Is Not Complete at Receipt: An Executable Outcome Contract for Distributed Agent-Tool Gateways#1327581
• Let My Data Go: Data Brokers' Compliance with Opt-Out and Deletion Requests#343382
• Secure Programming with SAS: Mitigating Risks and Protecting Data Integrity#465596
• TCDA: Tunable Coded Distributed Arrays for Data Availability Sampling#1386483