Sintr: Safe Interactive Transactions in the Presence of Byzantine Clients

arXiv:2608.27091v2 [cs.DC] 31 Aug 2026

Sintr: Safe Interactive Transactions in the Presence of Byzantine Clients Austin T. Li

Daniel H. Lee

Lorenzo Alvisi

Cornell University

Cornell University

Cornell University

Natacha Crooks

Florian Suri-Payer

UC Berkeley

Cornell University / Databricks

Abstract

1

Byzantine fault-tolerant (BFT) systems are, in principle, an appealing foundation for transactional applications involving mutually distrustful participants. Yet their adoption has been hampered by two persistent stumbling blocks—performance and developer convenience—which are often in tension with one another. Recent systems show promising progress on both fronts by shifting to a client-centric architecture; clients execute transactions locally and concurrently, while the system resolves any data conflicts to maintain database serializability. We argue that, in its current form, this approach introduces a critical vulnerability: it leaves the integrity of the database exposed to Byzantine clients, which may issue malicious or incorrect transactions. We address this threat with Sintr, a framework that prevents Byzantine clients from compromising database integrity by executing rogue transactions. Sintr combines redundant execution to validate transaction outcomes with a flexible, heterogeneous policy framework for expressing an application’s data integrity requirements. We apply Sintr to harden several existing BFT database systems and find that it imposes only modest overheads—3%–16% in throughput and 3%–21% in latency.

Decentralized applications that support data sharing among mutually distrustful parties are increasingly deployed in domains such as healthcare and financial services [3, 5, 19, 21, 26]. In these settings, no single participant can be trusted to manage shared state, yet all require strong consistency and integrity guarantees. Byzantine fault-tolerant (BFT) systems address this tension by replicating state across multiple parties and ensuring agreement on a totally ordered, tamper-evident log of operations [14, 28, 35]. As a result, BFT systems present an appealing foundation for transactional applications spanning organizational or administrative boundaries. Despite this promise, BFT systems have seen limited adoption for general-purpose transactional workloads. Two obstacles have consistently hindered their use: performance and developer convenience. Traditional BFT designs follow the state machine replication (SMR) model, colocating application logic and state management at backend replicas [48]. This architecture enables strong safety guarantees—replicas deterministically execute application code and directly enforce application semantics. Over the years, extensive research has improved the performance [14, 35, 60], robustness [15], and network adaptability [28] of SMR-based BFT protocols. However, this approach imposes significant constraints on application developers, who must embed logic into replica-side execution environments, often through custom domain specific languages, and forfeit the ability to scale or evolve application logic independently of the storage layer [43]. To reconcile performance and usability, several recent systems have shifted to a client-centric architecture, in which clients (typically front-end servers) execute transactions locally and interactively issue database operations as part of transaction execution [54, 55, 58]. Combined with an appropriate concurrency control mechanism, this design enables high throughput, supports modern transactional abstractions, and significantly improves developer ergonomics. The BFT database backend enforces serializability over a stream of client-issued operations, while application logic remains entirely client-side. We argue that, while it improves performance and usability, this architectural shift unwittingly creates a fundamental vulnerability to database integrity.

CCS Concepts: • Computer systems organization → Dependable and fault-tolerant systems and networks; • Security and privacy → Distributed systems security. Keywords: Byzantine fault tolerance, databases, transactions, distributed systems ACM Reference Format: Austin T. Li, Daniel H. Lee, Lorenzo Alvisi, Natacha Crooks, and Florian Suri-Payer. 2026. Sintr: Safe Interactive Transactions in the Presence of Byzantine Clients. In Symposium on Operating Systems Principles (SOSP ’26), September 29–October 2, 2026, Prague, Czech Republic. ACM, New York, NY, USA, 22 pages. https://doi.org/10.1145/3830418.3843865

This work is licensed under a Creative Commons Attribution 4.0 International License. SOSP ’26, Prague, Czech Republic © 2026 Copyright held by the owner/author(s). ACM ISBN 979-8-4007-2585-2/26/09 https://doi.org/10.1145/3830418.3843865

Introduction

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

By moving execution out of the trusted replication boundary, client-centric BFT databases implicitly trust clients to execute application logic faithfully. A Byzantine client, however, may submit transactions that violate application-level invariants, embed malicious logic, or exploit subtle semantic assumptions—without violating serializability. The BFT database ensures agreement and ordering of operations as issued, but it cannot ensure that those operations correspond to a valid execution of the application. Thus, client-centric designs abandon a core safety guarantee traditionally provided by SMR-based systems: that all committed transactions reflect correct application execution. This vulnerability is not an implementation artifact but a structural consequence of today’s client-centric architectures. Figure 1 illustrates the execution boundary in these architectures: the BFT-hardened database enforces only database isolation properties, while application semantics are defined and executed entirely at the client. As a result, database integrity is fully exposed to arbitrary updates by Byzantine clients. Addressing this safety gap requires more than stricter concurrency control—it demands a way to validate application execution itself. This paper introduces Sintr,1 a framework that restores to client-centric BFT databases a fundamental guarantee: objects can be updated only by correctly executed application logic. Rather than trusting the execution of a single client, Sintr enforces proactive validation: a transaction is accepted only if multiple independent clients re-execute it and agree on its outcome. These endorsements serve as proof that the transaction’s effects are consistent with correct application execution. At the same time, naïvely validating all transactions redundantly would impose prohibitive overhead. Sintr therefore introduces a heterogeneous, object-level policy framework that allows applications to precisely specify their integrity requirements. Different data objects may demand different levels of scrutiny—for example, financial records may require stronger validation than auxiliary metadata. Policies determine how many validation clients must endorse transactions that modify a given object, ensuring that overhead scales with required safety rather than uniformly across the workload. Designing such a framework raises several challenges. First, Sintr must minimize redundant database access during re-execution to avoid overwhelming the backend. It addresses this by forwarding sufficient execution context to validators, while ensuring Byzantine clients cannot manipulate this information to forge endorsements. Second, transactions frequently span multiple objects with different policies; Sintr must ensure that endorsements jointly satisfy all relevant 1 Safe interactive transactions. Also, a nod to the process of sintering, which

uses heat to strengthen a material without fully melting it.

Li et al.

Payment(‘Alice’, ‘W1’, 50)

App Execution

amt1 = READ(‘Alice’) amt2 = READ(‘W1’) WRITE(‘Alice’, amt1 – 50) WRITE(‘W1’, amt2 + 100)

Tx Manager

DB

Figure 1. The safety guarantees of today’s client-centric BFT databases only extend to the isolation properties of the transactions being executed, not to their semantics: nothing prevents Byzantine clients from issuing incorrect transactions (e.g., Payment transactions that incorrectly update the customer and warehouse balances).

object policies and, further, prevent objects with weaker integrity requirements from influencing objects with stronger ones. Finally, integrity requirements may evolve over time. Sintr supports dynamic policy updates through governance transactions that take effect atomically during normal execution, treating policies themselves as first-class data objects. We have implemented Sintr by hardening several existing BFT systems, including Basil [54], Pesto [55], and HotStuff [60] and BFT-SMaRt [10] layered over transactional data stores with both SQL and key-value interfaces. Across standard transactional workloads (TPC-C, SEATS, and Smallbank), Sintr incurs modest overheads of 3%–16% in throughput and 3%–21% in latency. Additional microbenchmarks characterize how validation policies affect performance and quantify the residual influence Byzantine clients retain under different configurations. In summary, this paper makes the following contributions: • We identify and formalize application execution validity, a safety guarantee lost by existing client-centric BFT database designs. • We present Sintr, a validation-based framework that restores this guarantee using heterogeneous, object-level integrity policies. • We demonstrate that Sintr can be retrofitted onto multiple BFT database systems with low overhead, significantly strengthening their safety against Byzantine clients.

2

The Pitfall

State machine replication (SMR) has long served as the foundation for building fault-tolerant distributed systems. In SMR, a system is modeled in terms of two components: state variables, which capture the system’s state, and commands, which deterministically transform that state. Traditional SMR designs assign responsibility for both command execution and

Sintr: Safe Interactive Transactions in the Presence of Byzantine Clients

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

state maintenance to a set of replicas and require correct replicas to execute the same sequence of commands in the same order2 and update their local state accordingly. When applied to transactional data stores, this paradigm requires database replicas to both store shared state (i.e., the values of database objects) and execute transactions. Concretely, correct replicas execute transactions whose reads and writes (𝑖) arise from valid, application-defined transaction logic and (𝑖𝑖) collectively satisfy the required isolation guarantees (e.g., serializability). In Byzantine settings, replicas further vote on proposed updates so that only sufficiently endorsed state transitions are applied to the database. Architectures that embed application logic directly within the database—most notably via stored procedures—naturally satisfy these requirements. Because replicas execute application logic themselves, they can directly validate that all state updates arise from correct executions of approved transactions. However, this tight coupling comes at a steep cost: stored procedures are typically written in vendor-specific languages with limited tooling, making application logic harder to develop, test, maintain, and evolve. Client-centric BFT architectures were developed to overcome these limitations—and in many respects, they succeed. They allow application logic to be written in general-purpose languages and have been shown to achieve performance competitive with unreplicated databases on standard transactional workloads [54, 55]. Achieving these benefits, however, requires a subtle but consequential shift in how the SMR abstraction is instantiated. In these architectures, correct database replicas remain responsible for storing state and apply agreed-upon updates, but they no longer execute the commands that generate those updates. Instead, clients execute transactions, interleaving application logic with database operations, and submit only the resulting reads and writes to the replicated backend. As a result, replicas can enforce consistency properties over the operations they observe, but they can no longer determine whether those operations arise from correct executions of application-defined transactions. This shift breaks a foundational stipulation of the SMR contract. Once application logic resides outside the trusted replication boundary, replicas lose the ability to ensure that state variables are updated only by valid executions of state machine commands. Although we frame this discussion in terms of SMR, the issue we identify is not specific to state machine replication. It arises more generally in BFT systems that decouple application execution from replicated agreement. In client-driven Byzantine storage and quorum-based systems [1, 17, 39, 40], replicas ensure consistency over stored values or updates, but likewise lack visibility into the semantic correctness of client-side computation. When such abstractions are used

as substrates for transactional or application-level systems, they inherit the same vulnerability: replicas may agree on updates without being able to validate that those updates result from correct executions of application logic. SMR makes the loss explicit by contrast with its stronger guarantees, but the underlying problem is architectural rather than SMR-specific. Correctness notions rooted solely in ordering and isolation of reads and writes are insufficient in client-centric architectures, as they fail to capture whether application logic itself was executed correctly. Addressing this gap requires an explicit model of application execution and a corresponding safety definition that extends beyond traditional database consistency.

2 The total-order requirement can be relaxed when commands commute [48].

For simplicity, and without loss of generality, we ignore this optimization.

3

Model and Definitions

3.1

System Model

Sintr inherits the standard assumptions of prior BFT work [14, 35, 54, 55]. Sintr assumes partial synchrony only to ensure liveness [23]. A participant is correct if it adheres to the protocol specification, and faulty otherwise; faulty participants may deviate arbitrarily from their specification. The adversary is strong but static: it may coordinate the actions of faulty clients and servers subject to the underlying fault thresholds, but cannot break standard cryptographic primitives. We assume that all clients and servers are explicitly registered with the system and can be authenticated via signatures. We denote a signed message 𝑚 as ⟨𝑚⟩𝜎 . 3.2

Safety with Interactive Transactions

Traditional correctness definitions for databases are intentionally limited in scope: they characterize safety exclusively in terms of reads and writes, typically through isolation guarantees such as serializability [7, 9]. These definitions align naturally with classical SMR systems, where replicas execute application logic themselves and thus implicitly validate command execution. However, when application logic executes at clients, outside the replicated core, a Byzantine client may issue a sequence of reads and writes that is serializable yet does not correspond to any valid execution of an application-defined transaction. For example, the Payment transaction in Figure 1 remains serializable even when it violates fundamental application invariants. Reasoning about such behaviors requires correctness definitions that explicitly account for application execution, not merely for database-level consistency. Application Model. Most applications predefine a set of transactions as part of their application logic. Developers write this logic in a general-purpose programming language, where transactions interleave database requests with clientside computation. We adopt this development model and refer to such transactions as interactive transactions. This approach is not only developer-friendly, but allows applications to scale independently of the database backend [43].

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

Li et al.

Formally, we model an application with interactive transactions as follows. Definition 1. An application consists of a set of interactive, deterministic transactions T = {𝑇1, . . . ,𝑇𝑛 }. Programmatic sources of nondeterminism (e.g., clocks and random seeds) are supported by treating them as transaction inputs; however, non-programmatic nondeterminism (e.g., dependent on memory layout) is not supported. Each transaction 𝑇𝑖 has a predefined implementation consisting of an interleaved sequence of database requests and application logic. The set of transactions T constrains which executions are correct for the application. Systems that colocate application execution with application state can guarantee that only predefined transactions commit, and that each such transaction is executed in accordance with its specification [48]. In contrast, existing BFT systems with interactive transactions implicitly trust authenticated clients (some of which may be Byzantine!) to execute application logic correctly [54, 55]. As argued in Section 2, this trust is misplaced. We therefore formalize safety directly in terms of application execution. Definition 2. A transaction is valid if it corresponds to a faithful execution of a transaction 𝑇𝑖 ∈ T . An application execution is valid if every non-read-only committed transaction in that execution is valid. Invalid read-only transactions affect only the issuing client and thus we intentionally make no assumptions on them. Application execution validity captures the core safety guarantee that is lost when shifting from server-side execution to clientside interactive transactions. Sintr focuses specifically on restoring this core guarantee, enabling applications to adopt client-side interactive transactions without sacrificing this fundamental safety guarantee. Other concerns—such as ordering transactions execution, enforcing isolation levels, or validating a transaction’s input—are orthogonal and addressed by existing mechanisms.

fault tolerance [14, 35], through heterogeneous trust assumptions [53] or by assuming a bound on the number of faulty clients system-wide. Sintr in particular leverages the fact that its clients are typically front-end servers controlled by the same organization(s) that run its applications to assume the existence of a bound on the number of faulty clients systemwide. Such fault models, however, are coarse-grained: they treat all transactions and all application data uniformly, regardless of their semantics or importance. Sintr instead adopts a transaction-centric fault model that expresses fault tolerance in terms of objects and the actions transactions perform on them. This model allows applications to pay for safety selectively, enforcing stronger guarantees only where application semantics demand them. Our design draws inspiration from integrity labels in the information-flow control literature [12] and instantiates them concretely as integrity policies. Integrity Policies. Each object is assigned an integrity policy that reflects the maximum degree of adversarial collusion the application expects that object to face. Intuitively, an object with policy 𝑥 is protected against up to 𝑥 colluding Byzantine clients. Importantly, integrity policies need not be uniform. Applications commonly contain data with different security and correctness requirements. For instance, in the TPC-C benchmark [57], financial records (e.g., customer balances) are significantly more sensitive than record-keeping data such as inventory counts, which can be reconciled through external validation. Sintr allows applications to reflect these distinctions directly in their safety policy. Enforcing Policies. Sintr enforces integrity policies through transaction endorsement. To modify an object governed by policy 𝑥, a client must collect at least 𝑥 other independent client endorsements that corroborate its transaction execution. This ensures that coalitions of 𝑥 or fewer Byzantine clients cannot corrupt the object. Allowing heterogeneous policies introduces a new challenge: policies cannot be assigned independently of application semantics. If a transaction reads a low-policy object and uses it to influence a write to a high-policy object, then the effective integrity of the high-policy object is weakened. To prevent this, Sintr adopts the principle of noninterference from information-flow control [29, 47]. Definition 3. An application satisfies noninterference if transactions only allow objects to influence objects governed by policies of equal or lower strength. Transactions that violate noninterference are rejected by default. Relaxing Noninterference. Strict noninterference is often too restrictive in practice [29, 47]. Some transactions legitimately transform low-integrity data into high-integrity updates by validating it against trusted information. In TPC-C, for example, a Delivery transaction may read order records

4

Sintr Framework

This section presents the Sintr framework, which restores application execution validity in client-centric BFT databases. Building on the model introduced in Section 3, Sintr provides fault tolerance against Byzantine clients by validating transaction execution at the application level, rather than relying solely on database-level consistency. We first introduce a transaction-centric fault model, then describe the safety and liveness properties Sintr guarantees, and finally give a high-level overview of its operation. 4.1

A Transaction-Centric Fault Model

Defending against Byzantine clients requires introducing redundancy into transaction execution. A natural approach is to adopt a client-centric fault model analogous to replica-based

Sintr: Safe Interactive Transactions in the Presence of Byzantine Clients

Warehouse/Customer Data High Policy Payment New Order Delivery Low Policy Order/Inventory Data

Figure 2. Example object policies and transactions for a transactional application (e.g., TPC-C).

Algorithm 1 Example Lift Function for Delivery (𝑇 ) 1: lift = [] 2: for order ∈ 𝑇

if ∃ payment ∈ 𝑇 : payment.order == order lift.𝑎𝑝𝑝𝑒𝑛𝑑 (order) 5: return lift 3: 4:

(low policy) and update customer balances (high policy) after performing application-specific validation (Figure 2). Sintr supports such patterns by allowing transactions to lift the policy of selected read objects. Lifting is an explicit, application-controlled operation: objects that are lifted are treated as having a higher policy for information flow purposes during the transaction. For simplicity, Sintr considers lifted objects as having policy as high as any object the transaction writes to, effectively excluding them from noninterference for that transaction. Applications express lifting logic using deterministic lift functions, which validate low-policy data according to the application’s semantics. Algorithm 1 illustrates a lift function for validating orders against payments. Lift functions offer a clean and fully general mechanism to express semantic checks that, in their absence, one would attempt to encode within a transaction or enforce through database consistency constrains. Lifting is optional and conservative by default: transactions that neither satisfy noninterference nor explicitly lift required objects are rejected. Because lifting weakens policy protections, it is intended to be used sparingly and with care. 4.2

Sintr Properties

Under the transaction-centric fault model described above, Sintr guarantees application execution validity. Theorem 1. Let 𝑂 be an object with policy 𝑝𝑂 . If the number of Byzantine clients that wish to collude for object 𝑂 is 𝑓𝑂 ≤ 𝑝𝑂 , then Sintr guarantees that 𝑂 is only updated by valid committed transactions. Moreover, if this holds for every object, then Sintr guarantees application execution validity. This guarantee ensures that, given a sufficiently strong policy, all committed, non-read-only transactions correspond to faithful executions of application-defined transaction logic, even in the presence of Byzantine clients. Sintr does not,

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

however, prevent Byzantine actors from obstructing progress. Liveness is guaranteed only when correct clients can satisfy required policies by collecting endorsements from correct clients (without relying on responses from faulty ones). We defer detailed proofs of correctness to an extended technical report [36]. 4.3

Sintr Overview

Figure 3 summarizes transaction processing in Sintr. Clients execute transactions locally while requesting parallel validation from peer clients. To avoid additional database load, validation clients do not issue database requests and instead rely on the initiating client to provide the necessary execution context and responses, along with proofs certifying their correctness. Upon completing their re-execution, validation clients return signed endorsements to signify that the initiating client performed the transaction candidly. The initiating client shares these endorsements with database replicas as part of its transaction commit request. Replicas then perform standard concurrency-control checks while additionally validating endorsements and enforcing information-flow constraints. Only transactions passing all checks are committed. Sintr also supports governance transactions that update integrity policies during normal execution. Sintr is designed for environments in which Byzantine clients are expected but limited. Clients are authenticated, transactions can be audited [31, 52], and collecting endorsements forces Byzantine clients to provably collude. While Sintr defaults to optimistic integrity policies, applications may adopt more conservative policies when stronger guarantees are required.

5

Sintr Protocol

Sintr is a general purpose framework, and can be used to augment any BFT database system supporting interactive transactions. Our evaluation instantiates Sintr atop several different BFT systems (Basil [54], Pesto [55], and SMR-based transactional systems using HotStuff [60] and BFT-SMaRt [10]). Here, we abstract protocol-specific functionality and assume the underlying system exposes a standard transaction interface. Each database object is identified by a unique key (e.g., a row’s primary key in a relational database), and each key is associated with a concrete policy. For simplicity, policies are initially fixed across a key’s lifetime; we discuss in Section 5.3 how to adjust policies at runtime. 5.1

Client Endorsement Collection Protocol

Clients execute transactions by interleaving database requests with application logic. To enforce application-level policies in the presence of Byzantine clients, Sintr requires transaction writes to be endorsed by other clients that independently validate the transaction’s execution.

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

Transaction Execution Client Execution Begin-Val

Fwd-Res

Commit

Li et al.

Transaction Commit

Decision

Endorse

Validation Execution

Update DB

CC-Check

Endorsement Information Validation Flow Check

Update Policy

Figure 3. Overview of transaction execution and validation in Sintr.

Endorsements provide cryptographic evidence that a transaction’s externally visible effects are consistent with the application specification: they attest to the correctness of the transaction’s writes and of the database reads that influence them. Reads that do not affect any writes produce no external effect and require no endorsements. The endorsement collection protocol has two goals. First, a Byzantine initiating client must not be able to fabricate, reuse, or manipulate endorsements to commit an invalid transaction. Second, endorsement and validation overheads should be minimal. Sintr organizes endorsement collection around the phases of transaction execution: beginning a transaction, issuing database requests, executing application logic, and committing. Throughout execution, initiating and validation clients record the transaction’s read set (keys accessed) and write set (keys modified). These sets conservatively approximate the information flow of the transaction and are later used to validate endorsements and enforce policy constraints. We use Figure 4 as a running example. When the initiating client diverges from correct execution, correct validation clients compute non-matching endorsements, causing replicas to abort the transaction at commit. Begin: Initiating client. When starting a transaction, the initiating client 𝐶 estimates the set of validation clients 𝑉 = {𝐶𝑉 } from which it must obtain endorsements. This estimate is based on the anticipated write set of the transaction and the policies associated with those keys, potentially using application-provided hints. Because the write set of an interactive transaction may not be fully known in advance, this estimate is best-effort; we assume for now that 𝑉 is sufficient and defer how to dynamically discover and adapt 𝑉 to Section 5.4. C → CV : Client 𝐶 sends begin validation requests.

Begin: Validation clients. Upon receiving a B EGIN -VAL message, each validation client 𝐶𝑉 begins local execution of the specified transaction using the provided inputs. Validation clients execute application logic eagerly but block on database requests until results are forwarded by the initiating client. Database Request. Validation clients do not issue database requests to the backend. Instead, the initiating client forwards the result of each database request along with a cryptographic proof produced by the underlying BFT system. This design serves two purposes. First, it avoids increasing load on the backend: redundant work is performed only at the clients, which can be scaled independently. Second, it ensures consistent execution across clients, as, without additional server-side support, independent reads issued by validation clients could return different results: executions could diverge even when all parties are correct. Because validation clients do not trust the initiating client, forwarded results must be verifiable. Sintr leverages the fact that BFT database systems already return replies accompanied by proofs of correctness (e.g., a quorum of matching responses with signatures). To prevent equivocation, each forwarded result is also bound to a unique request identifier.

To initiate validation, 𝐶 sends a request B EGIN -VAL := ⟨𝑆𝑇 , tx-id⟩ to each 𝐶𝑉 ∈ 𝑉 , where 𝑆𝑇 describes the transaction’s initial state (e.g., name and input parameters) and tx-id is a unique identifier used to prevent endorsement reuse. In Figure 4, the initiating client seeks validation for a Payment transaction from ‘Alice’ to warehouse ‘W1’ for $50.

Validation clients. Upon receiving a forwarded result, a validation client verifies the proof and checks that it certifies both the response and its association with R EQ - ID. If verification succeeds, the client resumes execution using the forwarded result; otherwise, it cannot produce a valid endorsement. In Figure 4, the initiating client forwards database results for the customer and warehouse balance reads. The correct

CV ← C: Validation clients begin execution.

C → CV : Client 𝐶 forwards database request results. Initiating client. For each database request issued during transaction execution, the initiating client forwards a result message F WD -R ES := ⟨R EQ - ID, R EQ - RES, R EQ - PROOF⟩ to all validation clients. Here, R EQ - ID is a cryptographic hash of the request and transaction identifier, R EQ - RES is the database response, and R EQ - PROOF is the accompanying proof of correctness. The response also includes the request’s read and write sets, allowing validation clients to track how database state influences the transaction. CV ← C: Validation clients receive forwarded results.

Sintr: Safe Interactive Transactions in the Presence of Byzantine Clients

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

ABORT

R READ(‘Alice’)

200

READ(‘W1’)

10

WRITE(‘Alice’, 150) WRITE(‘W1’, 110)

COMMIT

BEGIN Payment BEGIN-VAL

Payment(‘Alice’, ‘W1’, 50)

FWD-RES

(‘Alice’, 200)

FWD-RES (‘W1’, 10)

WRITE(‘Alice’, 150) WRITE(‘W1’, 60)

ENDORSE

Figure 4. Invalid transactions from Byzantine clients fail to gather matching endorsements, and abort at correct replicas.

validation client verifies the proofs and uses these values during local execution. Execute. Between database requests, the initiating client and all validation clients execute transaction logic locally. Sintr assumes transaction execution is deterministic given identical inputs and database results; as a consequence, correct clients will reach the same intermediate states and final outcome. If the initiating client deviates from correct execution—for example, by computing an incorrect write based on valid reads—correct validation clients will independently compute a different transaction state. In Figure 4, the Byzantine initiating client computes an incorrect warehouse balance update, while the correct validation client, executing the same logic over the same reads, obtains a different value—a mismatch that will eventually cause correct replicas to abort the transaction. Upon completing execution, each client also deterministically evaluates the transaction’s lift function. The lift function takes as input the final transaction state (including the read and write sets) and the associated policies, and returns a set of keys to lift. For each lifted key, its effective policy is raised to the maximum write-set policy for the transaction, excluding it from subsequent information-flow constraints. Commit. After completing execution, the initiating client collects endorsements from its validation clients. CV → C: Validation clients send endorsement. Validation clients. Once a validation client 𝐶𝑉 finishes local execution, it computes a transaction hash 𝐻𝑇 over the transaction identifier, read set, and write set. Any lifted keys are excluded from the read set prior to hashing. The client then sends an endorsement E NDORSE := ⟨𝐻𝑇 ⟩𝜎𝐶𝑉 to the initiating client, signed using its public key. This endorsement attests to 𝐶𝑉 ’s view of the transaction’s externally visible effects. C ← CV : Client 𝐶 assembles endorsements. Initiating client. 𝐶 independently computes 𝐻𝑇 . If it forwarded correct database results and executed the transaction correctly, its hash will match those of all correct validation

clients. A Byzantine initiating client cannot alter the transaction’s read set, write set, or lifted keys without causing an endorsement mismatch with correct clients. Once 𝐶 has collected a sufficient number of matching, wellformed endorsements to satisfy the policies associated with all keys in the write set, it begins the transaction commit process. We assume here that all validation clients reply correctly; we defer discussion of faulty validation clients to Section 5.4. C → R: Client 𝐶 begins commit process. To commit, 𝐶 sends an augmented commit message C OMMIT := ⟨𝑇 , tx-id, ReadSet𝑇 , WriteSet𝑇 , Endorsements𝑇 ⟩ to

the backend replicas. It contains all information required for replicas to validate endorsements and enforce application policies. In Figure 4, the validation client computes a hash that differs from the Byzantine initiating client’s, which nonetheless attempts to commit the transaction attaching the mismatched endorsement. 5.2 Transaction Commit Sintr augments the underlying transaction commit protocol with additional policy-related checks, but otherwise leaves concurrency control (CC) and atomic commit unchanged. Replicas vote to commit a transaction only if it satisfies both the backend’s native CC checks and Sintr’s policy enforcement. When a replica receives a commit message it performs two types of validation: endorsement validation and information-flow checks. A replica may vote to commit only if both succeed. Endorsement Validation. A replica first computes the transaction hash 𝐻𝑇 from the commit message. It then verifies each endorsement’s signature and checks that its hash matches 𝐻𝑇 , collecting all valid endorsements that do so (Algorithm 2, Lines 2–4). For each key in the transaction’s write set, the replica retrieves its policy and checks that the number of valid endorsements meets the policy requirement (Lines 5– 8). If any write’s policy is not satisfied, the replica votes to abort. In Figure 4, the transaction contains an endorsement whose hash does not match the replica-computed 𝐻𝑇 , causing endorsement validation to fail and the transaction to abort.

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

Algorithm 2 Endorsement Validation (𝑇 ) 1: 𝐸𝑇 = {} 2: for 𝑒 ∈ Endorsements𝑇 3: if e.sig is valid ∧ e.hash == 𝐻𝑇 4: 𝐸𝑇 = 𝐸𝑇 ∪ 𝑒 5: for key ∈ WriteSet𝑇 6: 𝑝 = GetPolicy(key) 7: if |𝐸𝑇 | < 𝑝 8: return false 9: return true

Algorithm 3 Policy Information Flow (𝑇 ) 1: 𝑃𝑇 = max({GetPolicy(key) : key ∈ WriteSet𝑇 }) 2: for key ∈ ReadSet𝑇 3: 𝑝 = GetPolicy(key) 4: if 𝑝 < 𝑃𝑇 5: return false 6: return true

Policy Information Flow. Endorsement validation ensures that transaction writes are explicitly approved by a sufficient number of clients, but it does not by itself prevent a transaction from indirectly circumventing policies. In particular, when objects have heterogeneous policies, a transaction could use reads protected by weaker policies to influence writes protected by stronger ones, effectively committing a high-policy write with insufficient endorsement. To prevent such policy violations, Sintr enforces a conservative information-flow check at replicas. Rather than requiring clients to track fine-grained data dependencies during execution, replicas approximate information flow using the transaction’s read and write sets. For a transaction 𝑇 , let 𝑃𝑇 denote the maximum policy among all keys in its write set. The replica verifies that every key in the read set has policy at least 𝑃𝑇 (Algorithm 3). Keys explicitly lifted by the transaction’s lift function are excluded from the read set for this check, as lifting conceptually raises their effective policy to 𝑃𝑇 . If any non-lifted read violates this constraint, the replica votes to abort the transaction. 5.3

Governance Transactions

Sintr supports dynamic updates to application policies at runtime. Doing so requires careful coordination between policy evolution and transaction validation to ensure that transactions are evaluated against the correct policy versions and that policy changes cannot be bypassed. To this end, Sintr represents policies as versioned data maintained by the database and updated through transactions. We refer to transactions that modify policy values as governance transactions. Versioned Policy Store. Sintr introduces a layer of indirection between database keys and concrete policies. Each database key is associated with a policy id, and each policy id corresponds to a versioned policy value. Each replica maintains a versioned policy store, implemented as ordinary database state (e.g., a dedicated table). Policy ids may be

Li et al.

assigned at arbitrary granularity: a single key, a table, or any application-defined grouping may map to the same policy id. This indirection allows policies to evolve independently of application data. Conceptually, both the policy values themselves and the mapping can be updated. Our prototype implementation, however, currently assumes fixed mappings, so we discuss only updates to policy values for simplicity. Policy Versions and Validation. Versioning affects both the view clients may have of policies and the checks performed by replicas. We defer discussion of stale client views to Section 5.4 and focus here on replica-side validation. Replica checks use policy versions consistent with the transaction’s execution. For a transaction 𝑇 with timestamp 𝑡𝑠𝑇 , writes are evaluated against the latest policy version with timestamp earlier than 𝑡𝑠𝑇 . For information-flow checks, each read is evaluated against the policy version that was current when the read value was produced. Transaction Processing and Isolation. Governance transactions must be committed by all correct replicas and respect database isolation. In particular, Sintr requires governance transactions to be serializable with respect to regular transactions, ensuring that committed writes cannot be invalidated retroactively by later policy changes. Conceptually, governance transactions are ordinary transactions over policy objects. The key additional mechanism is that regular transactions implicitly read the policy ids associated with their writes. These implicit reads capture the transaction’s dependency on specific policy versions and allow standard concurrency control to detect conflicts with governance transactions. Algorithm 4 illustrates an instantiation using optimistic concurrency control (OCC). For a regular transaction 𝑇 , the replica records an implicit read of the policy id (and version) associated with each key in 𝑇 ’s write set (Lines 2–6). During validation, 𝑇 aborts if a governance transaction committed a newer version of any such policy between 𝑇 ’s read and commit timestamps (Lines 9–11). Conversely, a governance transaction 𝐺 aborts if it updates a policy id that was implicitly read by a concurrently committed regular transaction (Lines 14–16). This bidirectional conflict detection ensures serializability between policy updates and policy-dependent transactions. To prevent clients from committing transactions under obsolete policies, Sintr additionally requires that a regular transaction is validated against the latest policy version available at its commit timestamp (Lines 4–5). This ensures that policy changes take effect immediately in the serialization order and cannot be circumvented by reordering. Endorsements and Governance. By default, governance transactions are subject to the endorsement requirements of the policies they modify. Applications may also define alternative endorsement rules for governance transactions (e.g., requiring endorsement from a majority of all clients). Governance transactions are exempt from information-flow checks,

Sintr: Safe Interactive Transactions in the Presence of Byzantine Clients

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

Algorithm 4 Governance Transaction OCC

(𝑖𝑖𝑖) Faulty validation clients. The selected validation set 𝑉 may include faulty clients that fail to respond or return invalid endorsements. If |𝑉 | is exactly equal to the required policy threshold, a single faulty validator can prevent progress. When this occurs, the initiating client may contact additional validators and repeat endorsement collection. In practice, clients can track validator responsiveness and reliability over time, biasing future selections toward well-behaved peers. Clients may also deliberately overestimate |𝑉 | to tolerate occasional failures. Optimizations. Several aspects of the Sintr protocol can be parallelized to reduce latency. Validation clients may verify forwarded database proofs asynchronously, provided verification completes before endorsement. Similarly, initiating clients may defer endorsement verification, as replicas revalidate endorsements during commit. At replicas, endorsement validation and information-flow checks can be performed in parallel with concurrency control. A replica votes to commit only if all checks succeed. These optimizations reduce end-to-end latency without weakening safety. Finally, rather than allowing clients to choose endorsers independently, applications can enforce a deterministic random selection of endorsers to prevent Byzantine clients from populating their validation sets with other Byzantine clients. Such packing poses no safety risk because validation thresholds are chosen to resist collusion. However, deterministic random selection may enable lower policy thresholds that nonetheless, in expectation, yield safety with high probability. This technique, however, does not reduce the threshold requirements needed for provable safety.

1: // Regular transaction 𝑇 2: for key ∈ WriteSet𝑇 3: 𝑝, tsp = GetPolicy(key, tsT ) 4: if ¬ (𝑡𝑠𝑝 is the latest version of 𝑝) 5: return Abort 6:

ImpPolicyReadsT .add ((p, tsp ))

7: 8: // Standard OCC for 𝑇 9: for (p, tsp ) ∈ ImpPolicyReadsT if ∃𝐺 ∈ Committed : 𝑝 ∈ WriteSet𝐺 ∧tsp < tsG < tsT 10: 11: return Abort 12: 13: // Standard OCC for governance transaction 𝐺 14: for 𝑝 ∈ WriteSet𝐺 15: if ∃𝑇 ∈ Committed : (p, tsp ) ∈ ImpPolicyReadsT 16:

∧tsp < tsG < tsT return Abort

as their effects are limited to policy state rather than application data. 5.4

Practical Considerations

Selecting Validation Clients. When beginning a transaction, an initiating client selects a set of validation clients 𝑉 to collect endorsements from. As long as the selected set can pass endorsement validation, the identities of the selected clients are immaterial. Determining 𝑉 ’s size, however, is not straightforward. Ideally, |𝑉 | equals the maximum policy associated with any key in the transaction’s write set. In practice, however, selecting an appropriate 𝑉 can be complicated by a limited knowledge of the write set, stale policy information, and by faulty validators. (𝑖) Write-set discovery. For interactive transactions, the full write set may not be known at the start of execution. If the initiating client later modifies a key whose policy exceeds |𝑉 |, it must contact additional validation clients and wait on them to re-execute the transaction. In the worst case, this incurs the overhead of an additional execution pass. Applications can reduce this cost by providing application-specific estimation functions. For example, if policies are assigned per table and the tables modified by a transaction are known in advance, the initiating client can determine |𝑉 | precisely. (𝑖𝑖) Stale policy views. Clients cache policy information to avoid fetching it on every transaction. After a governance transaction commits, this cache may become stale, causing a client to request too few or too many endorsements. If too few, the transaction aborts during commit; if too many, the client incurs unnecessary overhead. Replicas can return updated policy information as a response. Such information must be accompanied by a proof of commit to prevent Byzantine replicas from supplying incorrect policies. We assume policy updates are infrequent, limiting the cost of cache refreshes.

6

Evaluation

Our evaluation addresses the following questions: • What is the overhead Sintr adds on realistic applications? (§6.1) • How does policy affect Sintr’s performance? (§6.2) • How responsive is Sintr’s policy scheme to changes? (§6.3) • What residual impact can Byzantine clients have on Sintr? (§6.4) • How can lifting be leveraged to enable heterogeneous policies in Sintr and improve performance? (§6.5) • How does dynamic write-set discovery impact Sintr’s performance? (§6.6) Implementation. We implement Sintr in C++ atop several transactional BFT systems. Networking uses Protobuf [46] over TCP; authentication relies on ed25519 signatures [8, 41] and HMAC-SHA256 [18]. We use Blake3 [13] for hashing. Baselines. We integrate Sintr with four systems:3 (𝑖) Basil [54], a sharded BFT key-value store (KVS) with interactive transactions; 3 Code and experimental scripts are available at https://github.com/ ATLi2001/Sintr-Artifact.

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic 135

50 Peloton-HS Peloton-HS-P-1 Peloton-HS-P-2

Peloton-Smart Peloton-Smart-P-1 Peloton-Smart-P-2

40 Pesto Pesto-P-1 Pesto-P-2

40

Mean Latency (ms)

105 90 75 60 45 30

Peloton-HS Peloton-HS-P-1 Peloton-HS-P-2

Peloton-Smart Peloton-Smart-P-1 Peloton-Smart-P-2

30

20

Tx-Smart Tx-Smart-P-1 Tx-Smart-P-2

30 25 20 15 10 5

0

200

400

600

800

1000

1200

1400

1600

Throughput (tx/s)

Figure 5. TPC-C (20 warehouses) 1

1800

0

0

500

1000

1500

2000

2500

3000

Throughput (tx/s)

Figure 6. SEATS

(𝑖𝑖) Pesto [55] a BFT SQL database that extends Basil with Peloton’s [44] query engine; (𝑖𝑖𝑖) Peloton-SMR, which executes SQL queries at replicas after ordering them via BFT SMR. We take the Peloton-SMR implementation from the open source Pesto artifact, which includes two versions: Peloton-HS uses HotStuff [60] for consensus; Peloton-Smart instead relies on BFT-SMaRt [10, 11]. (𝑖𝑣) Tx-SMR, a transactional KVS system layered over BFT SMR. We take the Tx-SMR implementation from the open source Basil artifact, which also includes two versions: Tx-HS uses HotStuff as its consensus engine, while Tx-Smart relies on BFT-SMaRt. Experimental Setup. Experiments run on m510 machines (8-core 2.0 GHz CPU, 64 GB RAM, 10 GB NIC, 0.15 ms ping latency) on CloudLab [22]. Clients execute transactions in a closed-loop using a single thread, and retry aborts with exponential back-off. Sintr allocates three additional cores per client for validation; these cores do not accelerate transaction execution, which is largely sequential and bottlenecked on asynchronous database calls. Unless stated otherwise, we assume that Sintr clients have static knowledge of the required endorsements for all transactions; in Section 6.6 we explicitly evaluate the impact of imperfect predictions and dynamic policy discovery. Each system is configured to tolerate 𝑓 = 1 faults (𝑛 = 3𝑓 + 1 replicas for HotStuff/BFT-SMaRt, 𝑛 = 5𝑓 + 1 for Basil/Pesto). All systems run in-memory and enforce serializable isolation. Experiments run for 60 s total, including a 15 s warm-up and a 15 s cool-down. 6.1

Tx-HS Tx-HS-P-1 Tx-HS-P-2

10

15 0

Basil Basil-P-1 Basil-P-2

35

Mean Latency (ms)

Pesto Pesto-P-1 Pesto-P-2

120

Mean Latency (ms)

Li et al.

High Level Performance

We evaluate Sintr on three popular transactional benchmarks: TPC-C [57], SEATS [20], and Smallbank [20]. SQL systems run TPC-C (20 warehouses, high contention) and SEATS (lower contention, many read-only queries), while KVS systems run Smallbank (1M accounts, 90% skew to 1,000 hot keys). In each experiment, all objects in the database are assigned the same integrity policy, which remains constant throughout the experiment. We denote by P-x that a transaction requires

1

3500

4000

4500

0

0

2000

4000

6000

8000

10000

12000

14000

16000

18000

Throughput (tx/s)

Figure 7. Smallbank 1

𝑥 endorsements, excluding the initiating client. Baselines correspond to P-0. Initiating clients select validation clients uniformly in a round-robin manner. Figures 5, 6, and 7 report throughput and latency. TPC-C. Pesto with P-1 and P-2 achieves peak throughput (1471 tx/s and 1431 tx/s, respectively) within 12.5% and 14.9% of base Pesto (1681 tx/s). Latency increases by 16.8% and 21.7% at the respective inflection points. Peloton-SMR incurs lower overhead: compared with the baseline, throughput with P-1 drops by 6.4% (Peloton-HS) and 3.0% (PelotonSmart), while latency increases, respectively, by 6.9% and 3.1%. The overheads of Sintr stem primarily from the additional cryptographic operations required by its protocol. At replicas, Sintr incurs the cost of verifying endorsement signatures, while at clients it adds HMAC computation for forwarded requests and signature verification for forwarded proofs. Most validation latency is hidden by Sintr’s pipelined design and by clients’ precise knowledge of the number of validators required. As a result, Sintr’s overhead is more pronounced under Pesto, which is CPU-bound and therefore sensitive to the added signature verification costs. In contrast, PelotonSMR systems are dominated by contention induced by higher baseline latency, making the additional overhead of Sintr relatively smaller. SEATS. Pesto with P-1 and P-2 achieve throughputs (3569, 3468 tx/s) that are within 7.4% and 10.0% of base Pesto (3855 tx/s), respectively. The latencies are 8.2% and 11.3% higher than base Pesto, respectively. Compared to TPC-C, SEATS contains a significantly higher portion of read-only transactions, which don’t incur Sintr’s overheads. All systems are CPU bottlenecked, but Sintr adds little overhead to the Peloton-SMR systems as the latency of replica endorsement checks is relatively low compared to that of consensus. Smallbank. Basil under P-1 and P-2 achieves similar throughput, remaining within 16.1% of base Basil. However, these policies increase latency by 16.8% and 21.4%, respectively. Tx-HS under P-1 experiences a smaller impact, with a 4.6% reduction in throughput and a 4.9% increase in latency, while Sintr adds negligible overhead to the base Tx-Smart system. As in TPC-C, Basil is CPU-bound, whereas Tx-SMR

Sintr: Safe Interactive Transactions in the Presence of Byzantine Clients

12

12 P-0 P-1-U

P-1-Z P-2-U

P-3-U

P-0 P-1-U

P-1-Z P-2-U

6000

P-3-U

10

8

6

4

8

6

4

2

2

0

0

0

1000

2000

3000

4000

5000

6000

7000

8000

5000

Throughput (tx/s)

Mean Latency (ms)

10

Mean Latency (ms)

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

3000

2000

1000 Gov-10 Gov-90 0

1000

2000

3000

Throughput (tx/s) 1 (a) Uniform workload

4000

4000

5000

6000

Throughput (tx/s)

(b) Zipfian1 workload

7000

8000

0

0

10

20

P-1 P-5

Policy Change

30

40

50

60

Time (s)

Figure 9. Dynamically changing policies 1

Figure 8. Impact of application policy

systems are contention-bound, amplifying Sintr’s overhead on Basil relative to Tx-SMR. Takeaway. In SQL and KVS workloads, Sintr incurs modest overhead, with higher costs primarily in CPU-bound systems.

Takeaway. Sintr’s overhead is primarily determined by where the system bottlenecks: it is more pronounced in CPUbound settings with short transactions, but modest when contention dominates. Even under skewed or stronger policies, endorsement costs scale predictably.

6.2

6.3

Impact of Application Policy

We study how performance scales with policy strength using a YCSB-based microbenchmark (10 tables, 1M keys each; transactions read and update five rows) using Pesto as a baseline. We consider two workloads: an uncontended uniform access pattern and a contended Zipfian access pattern with coefficient 0.99. For each workload, we instantiate Sintr under a family of policies denoted P-x-[𝑈 /𝑍 ], where all keys share a static policy, 𝑥 is the number of required client endorsements, and 𝑈 and 𝑍 indicate uniform and Zipfian distributions of validation load, respectively. The Zipfian case models scenarios where certain clients are preferred as validators, e.g., because of reputation or proximity. Under the uniform workload (Fig. 8a), Sintr with P-1-U incurs a 15% throughput loss and a 32.6% latency increase relative to P-0. Because transactions are short, Sintr’s overhead is proportionally large, and at high load servers become CPUbound. Strengthening the policy further requires additional signature validations per transaction, reducing throughput by a steady 8–9% per added endorsement. With P-1-Z, skewed validator selection causes a small subset of clients to become CPU-bound on validation. Under the Zipfian workload (Fig. 8b), all configurations are contention-bound. The added latency from endorsement checks slightly increases transaction conflict windows and abort rates, leading P-1-U to incur a 20.6% throughput reduction and a 36.8% latency increase. However, because servers are no longer CPU-bound, the marginal cost of additional endorsement checks is small. Skewed validation performs only slightly worse, as contention caps throughput well below client validation capacity.

Dynamically Changing Policies

We evaluate dynamic policy updates in Sintr using a YCSBbased microbenchmark with a uniform access pattern. The experiment runs for 90 s with 20 clients, including 15 s warmup and cool-down periods. Initially, all keys are assigned P-1. We then inject a governance transaction that upgrades 𝑥% of keys (Gov-𝑥) from P-1 to P-5, followed 30 s later by a second governance transaction that reverts the change. For reference, we also report steady-state performance with all keys fixed at P-1 or P-5. Figure 9 illustrates the effect of policy updates. Governance transactions commit in under 5 ms, on par with regular transactions. When the first update commits, each client aborts at most one in-flight transaction due to concurrency control or insufficient endorsements. After the second update, clients temporarily generate excess endorsements, but detect and correct this on their next transaction. Throughout, transaction processing never halts, and throughput shifts immediately to the level dictated by the active policy. Takeaway. Sintr supports fast, minimally disruptive policy changes at runtime. They take effect immediately, with throughput adapting smoothly and without pausing execution. 6.4

Residual Impact of Byzantine Clients

Sintr’s policy-based design ensures that, under a well-chosen policy, Byzantine clients cannot compromise execution correctness. Nevertheless, Byzantine clients may still degrade performance by deviating from the endorsement protocol— for example, by ignoring validation requests or by soliciting excessive endorsements for their own transactions. Such behavior is indistinguishable from benign behavior: an unresponsive client may simply pose as slow, and correct clients cannot tell whether their endorsement was strictly necessary.

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

300

250

ignore-val-delay-0 ignore-val-delay-2 ignore-val-delay-4

200

150

100

50

0

0

1

2

3

4

Num Byzantine Clients

(a) Uniform workload 1

5

ddos-delay-0 ddos-delay-2 ddos-delay-4

250

900

ignore-val-delay-0 ignore-val-delay-2 ignore-val-delay-4

800 700

Throughput (tx/s)

ddos-delay-0 ddos-delay-2 ddos-delay-4

Throughput / Correct Client (tx/s)

Throughput / Correct Client (tx/s)

300

Li et al.

200

150

100

50

600 500 400 300 200 100

0

0

1

2

3

4

Num Byzantine Clients

(b) Zipfian workload 1

5

0

P-5

Lift

P-1

Figure 11. Leveraging policy lifting 1

Figure 10. Residual impact of Byzantine clients

We study two representative attacks: ignore-val, where Byzantine clients ignore validation requests, and ddos, where they request endorsements from all clients. Other denial-ofservice behaviors (e.g., flooding the system with arbitrary validation requests) are mitigated by bounding the number of outstanding transactions per client. Our evaluation uses a YCSB-based microbenchmark with uniform and Zipfian access patterns. We deploy 20 clients and configure the system to tolerate up to five Byzantine clients by assigning P-5 to all keys. Validation cost is varied using an artificial 𝑥 ms busy-wait (delay-x). Correct clients optimistically contact five validators per transaction; in ignoreval, ignored requests trigger contacting additional validators, both immediately and in subsequent transactions. Figure 10 reports throughput of correct clients. Under ignore-val, performance degradation is small (1–5%) across all validation costs. Timeouts allow correct clients to identify unresponsive validators, requiring only 1–2 additional contacts on average, which validation clients can absorb without saturating. In contrast, ddos attacks grow more disruptive as validation becomes more expensive, ranging from negligible impact at delay-0 to a 25% throughput reduction at delay-4. When validation is cheap, correct clients can handle surplus requests; as validation cost grows, excess endorsement work delays transaction processing. Because this pressure is primarily client-side, the effect is similar under uniform and Zipfian workloads. In practice, applications may restrict which peers clients contact for validation. For low-compute transactions, such policies can remain permissive, as Sintr retains high throughput even under adversarial validation load. Takeaway. Byzantine clients in Sintr cannot compromise correctness and have limited performance impact unless validation is computationally expensive. 6.5

Leveraging Policy Lifting

Sintr allows applications to define heterogeneous policies so they pay high safety costs only where needed. For example, a

TPC-C-like application (Fig. 2) manages high-integrity financial data alongside lower-integrity record-keeping data, and ideally enforces strong policies only on the former. However, the Delivery transaction reads low-policy order data while updating high-policy financial state, violating safe information flow. To resolve this, Sintr supports lifting, allowing transactions to promote low-policy objects after validation. In Delivery, a lift function checks orders against customer balances; upon success, the order data is lifted and the transaction proceeds safely. This preserves heterogeneous policies without sacrificing correctness. We evaluate lifting using a modified TPC-C workload in which Delivery executes a lift function that checks that order amounts do not exceed available credit. The experiment uses 20 clients, tolerating up to five Byzantine clients. Financial tables (warehouse, district, customer, history) are assigned P-5, while record-keeping tables (orders, stock, item) are assigned P-1. We compare this configuration against uniform P-5 and uniform P-1 deployments. The uniform P-5 setup incurs unnecessary overhead on record-keeping data, while uniform P-1 accepts undue risk for financial data. Figure 11 shows the resulting throughput. Lifting improves throughput by 11.6% over uniform P-5. Lifting results in marginally more transactions requiring five endorsements than one endorsement; it proportionally recovers 43% of the throughput gained by the unsafe P-1 configuration while preserving P-5 safety for financial data. Takeaway. Lifting enables heterogeneous policies that substantially improve performance without sacrificing safety. 6.6

Impact of Dynamic Write-set Discovery

Sintr does not require advance knowledge of a transaction’s write set and can dynamically infer during execution the size of the set 𝑉 of validation clients required by the transaction. If the client initiating a transaction 𝑇 modifies a key whose policy exceeds the client’s initial estimate for |𝑉 |, it must contact more validation clients and wait on them to re-execute 𝑇 . If this step happens early in the 𝑇 ’s execution, it causes little

Sintr: Safe Interactive Transactions in the Presence of Byzantine Clients 8

p50

p90

p99

known

7

Latency (ms)

6 5 4 3 2 1 0 10%

20%

50%

Percentage of P-5

Figure 12. Dynamic write-set discovery 1

additional end-to-end latency, as the processing of these extra requests overlaps with the transaction’s ongoing execution. The worst case is when the key update that triggers the need for a larger 𝑉 is 𝑇 ’s last: this adds one message delay to contact the additional validation clients plus the time those clients need to execute 𝑇 —which they can do without issuing additional remote database calls. We evaluate the impact of dynamic write-set discovery by varying the fraction of P-5 versus P-1 keys using a YCSBbased microbenchmark with a uniform access pattern. The experiment uses 20 clients and each transaction reads and updates five rows. Clients always begin transactions by contacting one validation client. If a client’s transaction updates a P-5 key, then it dynamically contacts four additional validators. Figure 12 shows the latency under dynamic discovery, compared with that obtained with initial perfect knowledge of 𝑉 (shaded). As the percentage of P-5 keys increases, transactions are more likely to be delayed by waiting on four additional validation clients. The resulting delay is primarily due to Sintr’s cryptographic operations, as message delays and local transaction execution times are small. The p99 latency also reflects the worst-case for dynamic discovery when the last update is to a P-5 key; at 50% P-5 keys, the delay caused by lack of perfect initial knowledge is about 1 ms. Takeaway. Sintr remains efficient without advance knowledge of the write set. Dynamic discovery incurs only modest latency when policies are mostly homogeneous, with the overhead increasing to roughly a single message round trip as policy heterogeneity grows.

7

Related Work

BFT State Machine Replication. State machine replication (SMR) [48] provides the abstraction of a single fault-tolerant server and underpins a wide range of distributed storage systems in both crash fault-tolerant (CFT) [16, 56] and Byzantine fault-tolerant (BFT) settings [4, 6, 24, 34]. BFT SMR systems rely on consensus protocols [14, 15, 28, 30, 35, 60] to ensure replicas agree on a total order of requests despite arbitrary failures. A common approach is to execute application logic at the replicas themselves, thereby ensuring that all committed state transitions arise from correct execution

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

of application-defined commands. Blockchains [25, 51, 59] follow this model, often by embedding application logic in custom smart-contract languages. However, colocating application execution with storage imposes significant usability costs, including reliance on domain-specific languages and limited ability to scale application logic independently of the backend [43]. Client-Side Computation in Byzantine Systems. Several BFT systems improve performance and developer usability by shifting application execution to clients. Client-centric transactional systems such as Basil, Pesto, and HRDB [54, 55, 58] expose database-style interfaces while relying on replicas to enforce ordering and isolation. Similarly, client-driven Byzantine storage and quorum systems [1, 17, 39] delegate computation to clients while replicas ensure consistency over stored values or updates. While these designs provide strong guarantees at the storage or consistency level, they share a common limitation: replicas do not validate the semantic correctness of client-side computation. Authenticated Byzantine clients may therefore issue operations that are serializable or quorum-certified yet violate application-level invariants. When such systems are used as substrates for transactional or application-level services, they relinquish the guarantee that committed updates arise from correct executions of application logic. Sintr addresses this architectural gap by restoring application execution validity in systems that permit clientside interactive computation, without reverting to replica-side execution. Transaction Validation by Redundant Execution. Prior systems [4, 32, 33, 49] employ redundant execution to validate transaction outcomes. However, these approaches retain the SMR execution model and require application logic to execute within the replica, limiting scalability and flexibility. Moreover, redundant execution typically occurs over replica-local state, allowing even correct replicas to diverge. In contrast, Sintr uses redundant execution among clients to validate interactive transactions while ensuring that all correct validators reach identical outcomes. Database Integrity Constraints. Modern databases support integrity constraints that automatically enforce semantic properties of stored data (e.g., non-negativity and referential integrity) [27, 45]. Although these constraints remain valuable in Sintr, enforcing constraints powerful enough to check whether a transaction’s execution is valid quickly degenerates into re-executing the transaction within the database. For example, even for a simple payment transaction (Figure 1), verifying that credits equal debits requires examining the transaction inputs together with the initial and final account balances, effectively re-executing the transaction. Instead, Sintr keeps transaction execution entirely client-side while still ensuring valid application executions. Information Flow. Sintr draws inspiration from classical information flow control (IFC) techniques [12, 29, 47]. Language-based systems [37, 42, 50] enforce confidentiality

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

Li et al.

and integrity by ensuring data flows respect security policies. These approaches address a different problem: they regulate who may access or modify data, but not how application logic is executed. A node with sufficient privileges may still perform incorrect application logic while respecting IFC constraints. Sintr, in contrast, focuses on ensuring that transactions are executed according to their applicationdefined semantics, regardless of which clients are authorized to execute them.

Cocco, and Jason Yellick. 2018. Hyperledger fabric: a distributed operating system for permissioned blockchains. In Proceedings of the Thirteenth EuroSys Conference (Porto, Portugal) (EuroSys ’18). Association for Computing Machinery, New York, NY, USA, Article 30, 15 pages. doi:10.1145/3190508.3190538 [5] Suveen Angraal, Harlan Krumholz, and Wade Schulz. 2017. Blockchain Technology: Applications in Health Care. Circulation: Cardiovascular Quality and Outcomes 10 (09 2017), e003800. doi:10.1161/ CIRCOUTCOMES.117.003800 [6] Mathieu Baudet, Avery Ching, Andrey Chursin, George Danezis, François Garillot, Zekun Li, Dahlia Malkhi, Oded Naor, Dmitri Perelman, and Alberto Sonnino. 2019. State Machine Replication in the Libra Blockchain. In The Libra Association Technical Report. [7] Hal Berenson, Philip A. Bernstein, Jim Gray, Jim Melton, Elizabeth O’Neil, and Patrick O’Neil. 1995. A Critique of ANSI SQL Isolation Levels. In Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data. ACM, San Jose, CA, USA, 1–10. [8] Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and BoYin Yang. 2011. High-speed high-security signatures. Cryptology ePrint Archive, Paper 2011/368. https://eprint.iacr.org/2011/368 [9] Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman. 1987. Concurrency Control and Recovery in Database Systems. AddisonWesley. [10] Alysson Bessani, João Sousa, and Eduardo E. P. Alchieri. 2014. State Machine Replication for the Masses with BFT-SMART. In Proceedings of the 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN ’14). IEEE Computer Society, USA, 355–362. doi:10.1109/DSN.2014.43 [11] BFTSmart [n. d.]. Byzantine Fault-Tolerant (BFT) State Machine Replication (SMaRt) v1.2. https://github.com/bft-smart/library. Accessed: 2025-11-10. [12] Kenneth J. Biba. 1977. Integrity Considerations for Secure Computer Systems. Technical Report MTR-3153. MITRE Corporation, Bedford, MA. [13] blake3 [n. d.]. BLAKE3. https://github.com/BLAKE3-team/ BLAKE3. Accessed: 2025-11-04. [14] Miguel Castro and Barbara Liskov. 1999. Practical Byzantine Fault Tolerance. In 3rd Symposium on Operating Systems Design and Implementation (OSDI 99). USENIX Association, New Orleans, LA. https://www.usenix.org/conference/osdi-99/practicalbyzantine-fault-tolerance [15] Allen Clement, Edmund Wong, Lorenzo Alvisi, Mike Dahlin, and Mirco Marchetti. 2009. Making Byzantine fault tolerant systems tolerate Byzantine faults. In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation (Boston, Massachusetts) (NSDI’09). USENIX Association, USA, 153–168. [16] James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, and Dale Woodford. 2013. Spanner: Google’s Globally Distributed Database. ACM Trans. Comput. Syst. 31, 3, Article 8 (Aug. 2013), 22 pages. doi:10.1145/2491245 [17] James Cowling, Daniel Myers, Barbara Liskov, Rodrigo Rodrigues, and Liuba Shrira. 2006. HQ Replication: A Hybrid Quorum protocol for Byzantine fault tolerance. In Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation (NSDI’06). [18] Wei Dai. [n. d.]. CryptoPP. https://github.com/weidai11/cryptopp. Accessed: 2025-11-04. [19] Diem [n. d.]. Diem. https://en.wikipedia.org/wiki/Diem_(digital_ currency). Accessed: 2025-09-30.

8

Conclusion

This paper presents Sintr, a framework for providing fault tolerance against Byzantine clients in client-centric, interactive transactional systems. Sintr makes it possible to reconcile two seemingly conflicting goals: the scalability and expressiveness of client-side transactions, which can benefit from mature programming languages, tooling, and development workflows; and the strong safety guarantees of server-side validation. Sintr achieves this reconciliation by leveraging redundant client execution and explicit endorsement of transaction outcomes, ensuring that committed transactions adhere to application-level integrity policies even in the presence of malicious clients. A key contribution of Sintr is its support for flexible, heterogeneous policies that allow applications to express fine-grained integrity requirements without modifying underlying database protocols. By integrating endorsement validation and policy enforcement into the commit path, Sintr enables existing BFT transactional systems to safely support interactive, client-driven execution with modest overhead.

Acknowledgments We are grateful to our shepherd and the anonymous SOSP reviewers for their thorough and insightful comments. This work was supported in part by the NSF grant CNS-CORE 2106954.

References [1] Michael Abd-El-Malek, Gregory R. Ganger, Garth R. Goodson, Michael K. Reiter, and Jay J. Wylie. 2005. Fault-scalable Byzantine fault-tolerant services. In Proceedings of the Twentieth ACM Symposium on Operating Systems Principles (Brighton, United Kingdom) (SOSP ’05). Association for Computing Machinery, New York, NY, USA, 59–74. doi:10.1145/1095810.1095817 [2] Atul Adya. 1999. Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions. Ph. D. Dissertation. Massachusetts Institute of Technology. [3] Cornelius C. Agbo, Qusay H. Mahmoud, and J. Mikael Eklund. 2019. Blockchain Technology in Healthcare: A Systematic Review. Healthcare 7, 2 (2019). doi:10.3390/healthcare7020056 [4] Elli Androulaki, Artem Barger, Vita Bortnikov, Christian Cachin, Konstantinos Christidis, Angelo De Caro, David Enyeart, Christopher Ferris, Gennady Laventman, Yacov Manevich, Srinivasan Muralidharan, Chet Murthy, Binh Nguyen, Manish Sethi, Gari Singh, Keith Smith, Alessandro Sorniotti, Chrysoula Stathakopoulou, Marko Vukolić, Sharon Weed

Sintr: Safe Interactive Transactions in the Presence of Byzantine Clients

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

[20] Djellel Eddine Difallah, Andrew Pavlo, Carlo Curino, and Philippe Cudre-Mauroux. 2013. OLTP-Bench: an extensible testbed for benchmarking relational databases. Proc. VLDB Endow. 7, 4 (Dec. 2013), 277–288. doi:10.14778/2732240.2732246 [21] Digital Euro [n. d.]. Digital Euro. https://www.ecb.europa.eu/euro/ digital_euro/html/index.en.html. Accessed: 2025-09-30. [22] Dmitry Duplyakin, Robert Ricci, Aleksander Maricq, Gary Wong, Jonathon Duerig, Eric Eide, Leigh Stoller, Mike Hibler, David Johnson, Kirk Webb, Aditya Akella, Kuangching Wang, Glenn Ricart, Larry Landweber, Chip Elliott, Michael Zink, Emmanuel Cecchet, Snigdhaswin Kar, and Prabodh Mishra. 2019. The Design and Operation of CloudLab. In Proceedings of the USENIX Annual Technical Conference (ATC). 1–14. https://www.flux.utah.edu/paper/duplyakinatc19 [23] Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988. Consensus in the presence of partial synchrony. J. ACM 35, 2 (April 1988), 288– 323. doi:10.1145/42282.42283 [24] Zarko Milosevic Ethan Buchman, Jae Kwon. 2016. Tendermint: Byzantine fault tolerance in the age of blockchains. Master’s thesis. The University of Guelph. [25] Ethereum [n. d.]. Ethereum. https://ethereum.org/. Accessed: 202511-05. [26] Fnality [n. d.]. Fnality. https://fnality.com/. Accessed: 2025-09-30. [27] Hector Garcia-Molina, Jeffrey D. Ullman, and Jennifer Widom. 2008. Database Systems: The Complete Book (2nd ed.). Pearson. [28] Neil Giridharan, Florian Suri-Payer, Ittai Abraham, Lorenzo Alvisi, and Natacha Crooks. 2024. Autobahn: Seamless high speed BFT. In Proceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles (Austin, TX, USA) (SOSP ’24). Association for Computing Machinery, New York, NY, USA, 1–23. doi:10.1145/ 3694715.3695942 [29] Joseph A. Goguen and José Meseguer. 1982. Security Policies and Security Models. In Proceedings of the 1982 IEEE Symposium on Security and Privacy. IEEE Computer Society, 11–20. [30] Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. 2019. SBFT: A Scalable and Decentralized Trust Infrastructure. In 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 568–580. doi:10.1109/DSN.2019.00063 [31] Andreas Haeberlen, Petr Kouznetsov, and Peter Druschel. 2007. PeerReview: practical accountability for distributed systems. In Proceedings of Twenty-First ACM SIGOPS Symposium on Operating Systems Principles (Stevenson, Washington, USA) (SOSP ’07). Association for Computing Machinery, New York, NY, USA, 175–188. doi:10.1145/1294261.1294279 [32] Chi Ho, Robbert Van Renesse, Mark Bickford, and Danny Dolev. 2008. Nysiad: Practical Protocol Transformation to Tolerate Byzantine Failures. In 5th USENIX Symposium on Networked Systems Design and Implementation (NSDI 08). USENIX Association, San Francisco, CA. https://www.usenix.org/conference/nsdi-08/nysiad-practicalprotocol-transformation-tolerate-byzantine-failures [33] Manos Kapritsos, Yang Wang, Vivien Quema, Allen Clement, Lorenzo Alvisi, and Mike Dahlin. 2012. All about Eve: execute-verify replication for multi-core servers. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (Hollywood, CA, USA) (OSDI’12). USENIX Association, USA, 237–250. [34] Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Ewa Syta, and Bryan Ford. 2018. OmniLedger: A Secure, ScaleOut, Decentralized Ledger via Sharding. In 2018 IEEE Symposium on Security and Privacy (SP). 583–598. doi:10.1109/SP.2018.000-5 [35] Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. 2010. Zyzzyva: Speculative Byzantine fault tolerance. ACM Trans. Comput. Syst. 27, 4, Article 7 (Jan. 2010), 39 pages. doi:10.

1145/1658357.1658358 [36] Austin T. Li, Daniel H. Lee, Lorenzo Alvisi, Natacha Crooks, and Florian Suri-Payer. 2026. Sintr: Safe Interactive Transactions in the Presence of Byzantine Clients. arXiv:2608.27091 [cs.DC] https: //arxiv.org/abs/2608.27091 [37] Jed Liu, Michael D. George, K. Vikram, Xin Qi, Lucas Waye, and Andrew C. Myers. 2009. Fabric: a platform for secure distributed computation and storage. In Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles (Big Sky, Montana, USA) (SOSP ’09). Association for Computing Machinery, New York, NY, USA, 321–334. doi:10.1145/1629575.1629606 [38] Dahlia Malkhi, Kartik Nayak, and Ling Ren. 2019. Flexible Byzantine Fault Tolerance. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (London, United Kingdom) (CCS ’19). Association for Computing Machinery, New York, NY, USA, 1041–1053. doi:10.1145/3319535.3354225 [39] Dahlia Malkhi and Michael Reiter. 1997. Byzantine quorum systems. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (El Paso, Texas, USA) (STOC ’97). Association for Computing Machinery, New York, NY, USA, 569–578. doi:10.1145/ 258533.258650 [40] J-P Martin, Lorenzo Alvisi, and Michael Dahlin. 2002. Small Quorum Systems. In Proceedings of the 32nd International Conference on Dependable Systems and Networks (DSN’02). 374–383. [41] Andrew Moon. [n. d.]. ed25519-donna. https://github.com/ floodyberry/ed25519-donna. Accessed: 2025-11-04. [42] Andrew C. Myers. 1999. JFlow: practical mostly-static information flow control. In Proceedings of the 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (San Antonio, Texas, USA) (POPL ’99). Association for Computing Machinery, New York, NY, USA, 228–241. doi:10.1145/292540.292561 [43] Andrew Pavlo. 2017. What Are We Doing With Our Lives? Nobody Cares About Our Concurrency Control Research. In Proceedings of the 2017 ACM International Conference on Management of Data (Chicago, Illinois, USA) (SIGMOD ’17). Association for Computing Machinery, New York, NY, USA, 3. doi:10.1145/3035918.3056096 [44] peloton [n. d.]. Peloton-DB. https://db.cs.cmu.edu/peloton/. Accessed: 2025-11-04. [45] PostgreSQL [n. d.]. PostgreSQL. https://www.postgresql.org/. [46] Protocol Buffers [n. d.]. Protocol Buffers. https://protobuf.dev/. Accessed: 2025-11-04. [47] Andrei Sabelfeld and Andrew C. Myers. 2003. Language-Based Information-Flow Security. IEEE Journal on Selected Areas in Communications 21, 1 (2003), 5–19. [48] Fred B. Schneider. 1990. Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Comput. Surv. 22, 4 (Dec. 1990), 299–319. doi:10.1145/98163.98167 [49] Felix Martin Schuhknecht, Ankur Sharma, Jens Dittrich, and Divya Agrawal. 2021. chainifyDB: How to get rid of your Blockchain and use your DBMS instead. In 11th Annual Conference on Innovative Data Systems Research (CIDR ’21). [50] David Schultz and Barbara Liskov. 2013. IFDB: decentralized information flow control for databases. In Proceedings of the 8th ACM European Conference on Computer Systems (Prague, Czech Republic) (EuroSys ’13). Association for Computing Machinery, New York, NY, USA, 43–56. doi:10.1145/2465351.2465357 [51] Kevin Sekniqi, Daniel Laine, Stephen Buttolph, and Emin Gün Sirer. 2020. Avalanche Platform. https://cdn.prod.website-files.com/ 5d80307810123f5ffbb34d6e/6008d7bbf8b10d1eb01e7e16_ Avalanche%20Platform%20Whitepaper.pdf [52] Alex Shamis, Peter Pietzuch, Burcu Canakci, Miguel Castro, Cedric Fournet, Edward Ashton, Amaury Chamayou, Sylvan Clebsch, Antoine Delignat-Lavaud, Matthew Kerner, Julien Maffre, Olga Vrousgou, Christoph M. Wintersteiger, Manuel Costa, and Mark Russinovich.

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic 2022. IA-CCF: Individual Accountability for Permissioned Ledgers. In 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22). USENIX Association, Renton, WA, 467–491. https://www.usenix.org/conference/nsdi22/presentation/shamis [53] Isaac C. Sheff, Xinwen Wang, Robbert van Renesse, and Andrew C. Myers. 2020. Heterogeneous Paxos. In 24th International Conference on Principles of Distributed Systems, OPODIS 2020, Strasbourg, France (Virtual Conference), December 14-16, 2020 (LIPIcs, Vol. 184). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 5:1–5:17. doi:10.4230/LIPICS.OPODIS.2020.5 [54] Florian Suri-Payer, Matthew Burke, Zheng Wang, Yunhao Zhang, Lorenzo Alvisi, and Natacha Crooks. 2021. Basil: Breaking up BFT with ACID (transactions). In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles (Virtual Event, Germany) (SOSP ’21). Association for Computing Machinery, New York, NY, USA, 1–17. doi:10.1145/3477132.3483552 [55] Florian Suri-Payer, Neil Giridharan, Liam Arzola, Shir Cohen, Lorenzo Alvisi, and Natacha Crooks. 2025. Pesto: Cooking up High Performance BFT Queries. In Proceedings of the ACM SIGOPS 31st Symposium on Operating Systems Principles (Lotte Hotel World, Seoul, Republic of Korea) (SOSP ’25). Association for Computing Machinery, New York, NY, USA, 529–554. doi:10.1145/3731569.3764799 [56] Rebecca Taft, Irfan Sharif, Andrei Matei, Nathan VanBenschoten, Jordan Lewis, Tobias Grieger, Kai Niemi, Andy Woods, Anne Birzin, Raphael Poss, Paul Bardea, Amruta Ranade, Ben Darnell, Bram Gruneir, Justin Jaffray, Lucy Zhang, and Peter Mattis. 2020. CockroachDB: The Resilient Geo-Distributed SQL Database. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (Portland, OR, USA) (SIGMOD ’20). Association for Computing Machinery, New York, NY, USA, 1493–1509. doi:10.1145/3318464.3386134 [57] Transaction Processing Performance Council. [n. d.]. The TPC-C home page. http://www.tpc.org/tpcc. [58] Ben Vandiver, Hari Balakrishnan, Barbara Liskov, and Sam Madden. 2007. Tolerating byzantine faults in transaction processing systems using commit barrier scheduling. SIGOPS Oper. Syst. Rev. 41, 6 (Oct. 2007), 59–72. doi:10.1145/1323293.1294268 [59] Anatoly Yakovenko. 2018. Solana: A new architecture for a high performance blockchain v0.8.13. https://solana.com/solana-whitepaper. pdf [60] Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. 2019. HotStuff: BFT Consensus with Linearity and Responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Toronto ON, Canada) (PODC ’19). Association for Computing Machinery, New York, NY, USA, 347– 356. doi:10.1145/3293611.3331591

Li et al.

Sintr: Safe Interactive Transactions in the Presence of Byzantine Clients

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

A

Proofs

A.1

Formal Definitions

Definition 5. Each database replica has a set of transactions that it locally considers to be committed. From this, the backend protocol defines the set of globally committed transactions. In an SMR-based system, all correct replicas contain the same sequence of committed transactions; this exactly determines the globally committed transactions. In an inconsistent replication system (e.g., Basil and Pesto), transactions are globally committed if there is a quorum of replicas which consider it as committed (e.g., at least 3𝑓 +1 of 5𝑓 +1 replicas). Sintr requires that the backend BFT database’s fault assumptions hold (i.e., at most 𝑓 faulty replicas). From this, we require the following to be true of the BFT database. Assumption 1. A globally committed transaction must have some correct replica which considers it committed. Assumption 1 gives a weak safety guarantee on the backend protocol. SMR-based systems satisfy this as all correct replicas consider the same transactions to be commited; Basil/Pesto satisfy this with their quorum requirements. Next, Sintr requires serializability4 for its governance transactions. Because Sintr performs its concurrency control for governance transactions at each replica, it requires that the BFT backend achieves serializability through its correct replicas. Assumption 2. If correct replicas only commit transactions which are serializable, then the set of globally committed transactions are also serializable. The SMR-based systems satisfy this as the set of globally committed transactions is exactly those which every correct replica commits. Basil and Pesto each achieve this as well; see Lemma 1 and Theorem 1 in each. The BFT backend system should also ensure that any two globally committed transactions have at least one correct replica which has locally commited both. Intuitively, this is the only way in which correct replicas alone can determine the isolation level of the database. Assumption 3. For any two globally committed transactions, there exists at least one correct replica which has locally committed both.

We begin by restating our definitions for an application with interactive transactions, our notion of safety for application executions, and noninterference. Definition 1. An application consists of a set of interactive, deterministic transactions T = {𝑇1, . . . ,𝑇𝑛 }. Programmatic sources of nondeterminism (e.g., clocks and random seeds) are supported by treating them as transaction inputs; however, non-programmatic nondeterminism (e.g., dependent on memory layout) is not supported. Each transaction 𝑇𝑖 has a predefined implementation consisting of an interleaved sequence of database requests and application logic. Definition 2. A transaction is valid if it corresponds to a faithful execution of a transaction 𝑇𝑖 ∈ T . An application execution is valid if every non-read-only committed transaction in that execution is valid. Definition 3. An application satisfies noninterference if transactions only allow objects to influence objects governed by policies of equal or lower strength. Note that with policy versions, noninterference must be clarified. Sintr ensures writes cannot circumvent the latest policy, and further assumes that policy changes are proactive in ensuring safety. Thus, reading a value written under an old policy version should be considered safe. We also formally define what faithful execution is. Intuitively, a faithful execution produces reads and updates that would be expected from the transaction specification. Definition 4. Consider a transaction 𝑇 with inputs 𝑥, read set ReadSet𝑇 , and write set WriteSet𝑇 . Here we treat ReadSet𝑇 as an ordered series of read results from object to value (in the order of transaction execution), and WriteSet𝑇 as an unordered collection of object-value pairs. 𝑇 is a faithful execution of 𝑇𝑖 ∈ T if given 𝑥 and ReadSet𝑇 , executing 𝑇𝑖 produces WriteSet𝑇𝑖 that exactly matches WriteSet𝑇 . At each point in 𝑇𝑖 where an intermediate read result to an object 𝑂 is required, the next unused read result in ReadSet𝑇 is used if it is a read to 𝑂; otherwise, the transaction was not faithfully executed. A.2

BFT Backend Assumptions

We will prove Sintr’s guarantees in general, without assuming a specific backend system. To do so, we make a minimal set of assumptions on the BFT database; the systems we instantiate Sintr on satisfy them. First, we clarify the notion of a committed transaction. In some BFT backend systems, even correct replicas may diverge in local state [54, 55]. As such, we use the term globally committed to distinguish transactions that are considered to be committed by the BFT database as a whole.

A.3

Correctness Sketch

We sketch the main theorems and lemmas necessary to show Sintr’s safety properties. We proceed in three steps: we first prove safety under a fixed application policy, then we show governance transactions are serializable, and finally we prove safety for versioned policies. First, we prove that Sintr’s protocol ensures correct validation clients only give matching endorsements for valid transactions. 4 For

BFT databases, serializability is formally defined as Byzserializability [54]. Intuitively, Byz-isolation ensures that correct clients observe state that could have been produced by correct clients alone.

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

Li et al.

Lemma 1. Let 𝑇 be a transaction. If 𝑇 received a matching endorsement from a correct validation client, then 𝑇 must be valid. We then show that if Sintr’s policy holds for an object, then the protocol ensures the object is only updated by valid committed transactions. Lemma 2. Assume that the application policy is fixed. Let 𝑂 be an object with policy 𝑝𝑂 . If the number of Byzantine clients that wish to collude for object 𝑂 is 𝑓𝑂 ≤ 𝑝𝑂 , then Sintr guarantees that 𝑂 is only updated by valid committed transactions. We also show Sintr’s protocol guarantees noninterference for objects that are not lifted. Lemma 4. Assume that the application policy is fixed. Sintr upholds noninterference except for objects which have been explicitly lifted. Next, we prove that governance transactions are serializable. Theorem 2. Sintr’s governance transactions are serializable. Finally, we show that Sintr’s protocol still guarantees safety with versioned policies. Theorem 1. Let 𝑂 be an object with policy 𝑝𝑂 . If the number of Byzantine clients that wish to collude for object 𝑂 is 𝑓𝑂 ≤ 𝑝𝑂 , then Sintr guarantees that 𝑂 is only updated by valid committed transactions. Moreover, if this holds for every object, then Sintr guarantees application execution validity. For noninterference with versioned policies, we first prove that governance transactions maintain noninterference. Lemma 7. Sintr’s governance transactions maintain noninterference. From this, we obtain noninterference in general for Sintr. Theorem 3. Sintr upholds noninterference except for objects which have been explicitly lifted.

Furthermore, because all forwarded database results contain R EQ - PROOF (which certify both R EQ - ID and R EQ - RES), 𝐶𝑉 will only use correct database results where the read object exactly matches what 𝑇𝑖 would require at that point. Thus, 𝐶𝑉 can only produce a faithful execution of 𝑇𝑖 . However, since 𝑇 is not a faithful execution of 𝑇𝑖 , it must have a write set that differs. The resulting endorsement hash contains the write set, so the endorsement 𝐶𝑉 gives cannot match transaction 𝑇 . This is a contradiction. □

A.4

Safety with Fixed Application Policy

Assuming a fixed application policy, we prove that Sintr is safe. In particular, we show application execution validity and noninterference. Lemma 1. Let 𝑇 be a transaction. If 𝑇 received a matching endorsement from a correct validation client, then 𝑇 must be valid. Proof. Suppose for the sake of contradiction that 𝑇 is not valid but it received a matching endorsement from a correct validation client 𝐶𝑉 . Because 𝐶𝑉 is correct, it will only begin validation for transactions in T . Thus, to receive an endorsement, the initiating client 𝐶 must have claimed 𝑇 to be some transaction 𝑇𝑖 ∈ T . We assume that 𝑇𝑖 is deterministic. Any local computation can only depend on the inputs to the transaction and intermediate database results. Since 𝐶𝑉 is correct, it will execute all local computation in 𝑇𝑖 according to its specification.

Lemma 2. Assume that the application policy is fixed. Let 𝑂 be an object with policy 𝑝𝑂 . If the number of Byzantine clients that wish to collude for object 𝑂 is 𝑓𝑂 ≤ 𝑝𝑂 , then Sintr guarantees that 𝑂 is only updated by valid committed transactions. Proof. Suppose for the sake of contradiction that there exists an invalid committed transaction 𝑇 which updates 𝑂. By Assumption 1, there exists at least one correct replica which committed 𝑇 . At that replica, 𝑇 must have passed Sintr’s endorsement check. Thus, 𝑇 contains at least 𝑝𝑂 matching endorsements (Algorithm 2 Lines 5–8). Because the replica checks for endorsement validity (Algorithm 2 Lines 2–4), including the initiating client, there are at least 𝑝𝑂 + 1 clients which obtained the same result for 𝑇 . The number of Byzantine clients is 𝑓𝑂 ≤ 𝑝𝑂 , so there must be at least one correct client which endorsed 𝑇 , or the initiating client was correct. If the initiating client was correct, then 𝑇 must be valid. Otherwise, by Lemma 1, since only valid transactions receive endorsements from correct clients, 𝑇 must be valid. In either case, this is a contradiction. □ Lemma 3. If every object is only updated by valid committed transactions, then Sintr guarantees application execution validity. Proof. If all objects are only updated by valid committed transactions, then all non-read-only committed transactions are valid, which is exactly the definition of application execution validity. □ Lemma 4. Assume that the application policy is fixed. Sintr upholds noninterference except for objects which have been explicitly lifted. Proof. Suppose for the sake of contradiction that Sintr does not uphold noninterference in this case. Then there exists objects 𝑂 1, 𝑂 2 with policies 𝑝 1, 𝑝 2 , respectively, such that 𝑝 1 < 𝑝 2 but 𝑂 1 influences 𝑂 2 . In particular, this means there exists a committed transaction 𝑇 that reads from 𝑂 1 and writes to 𝑂2. By Assumption 1, there exists at least one correct replica which committed 𝑇 . At that replica, 𝑇 must have passed the policy information flow check (Algorithm 3). Since 𝑂 1 is not lifted, it is included in the read set for the information flow check. When the check reaches 𝑂 1 in the read set, its policy 𝑝 1 will be extracted (Line 3). But Line 4 will explicitly compare

Sintr: Safe Interactive Transactions in the Presence of Byzantine Clients

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

𝑝 1 against the maximum policy of the write set, which is at least 𝑝 2 . A correct replica must then abort 𝑇 . This is a contradiction. □

1. CC check on 𝐺 𝑗 first. During the CC check on 𝑇𝑖 , each write set object policy is checked for conflicts against (replica-voted) committed governance transactions (Algorithm 4 Lines 9–11). However, 𝐺 𝑗 is already voted to be committed, and this check would have found 𝑡𝑠𝑝 < 𝑗 < 𝑖 and aborted 𝑇𝑖 . This is a contradiction. 2. CC check on 𝑇𝑖 first. When the CC check on 𝐺 𝑗 occurs, 𝑇𝑖 is (replica-voted) committed and thus has recorded an implicit policy read to 𝑝 at time 𝑖 (Algorithm 4 Lines 2– 6). When the CC check for 𝐺 𝑗 occurs, 𝐺 𝑗 will not be allowed to commit since it would have caused 𝑇𝑖 ’s implicit policy read to miss a policy write (Algorithm 4 Lines 14–16). This is a contradiction. In all cases, we have a contradiction. This implies 𝑖 < 𝑗. Thus, in the DSG for a correct replica, if there exists an edge 𝑇𝑖 → 𝑇 𝑗 , then 𝑖 < 𝑗. The set of transactions is serializable if the DSG has no cycles. Assume for the sake of contradiction that there exists a cycle consisting of 𝑛 transactions 𝑇𝑡𝑠1 , . . . ,𝑇𝑡𝑠𝑛 . This implies that 𝑡𝑠 1 < · · · < 𝑡𝑠𝑛 < 𝑡𝑠 1 . However, transaction timestamps are totally ordered. This is a contradiction, and thus a correct replica only commits transactions which are serializable. Then by Assumption 2, if every correct replica only commits transactions which are serializable, then the set of committed transactions is serializable. □

A.5 Governance Transaction Serializability Sintr requires serializability for governance transactions. To formally define how a governance transaction can conflict with a regular transaction, we extend Adya’s formalism [2]. An execution produces a direct serialization graph (DSG) whose vertices are committed transactions, denoted 𝑇𝑡 , where 𝑡 is the unique timestamp identifier. Edges between regular transactions in the DSG are one of three types: 𝑤𝑤

• 𝑇𝑖 −−−→ 𝑇 𝑗 if 𝑇𝑖 writes the version of object 𝑥 that precedes 𝑇 𝑗 in the version order. 𝑤𝑟

• 𝑇𝑖 −−→ 𝑇 𝑗 if 𝑇𝑖 writes the version of object 𝑥 that precedes 𝑇 𝑗 reads. 𝑟𝑤

• 𝑇𝑖 −−→ 𝑇 𝑗 if 𝑇𝑖 reads the version of object 𝑥 that precedes 𝑇 𝑗 ’s write. We assume, as does Adya, that if an edge exists between 𝑇𝑖 and 𝑇 𝑗 , then 𝑇𝑖 ≠ 𝑇 𝑗 . For an object 𝑥, let 𝑝𝑥 be its policy. When a regular transaction writes to 𝑥, it uses (implicitly reads) a version of 𝑝𝑥 for its endorsement check. The edges which can exist between a governance transaction 𝐺 and a regular transaction 𝑇 are: 𝑤𝑟

• 𝐺𝑖 −−→ 𝑇 𝑗 if 𝐺𝑖 writes the version of 𝑝𝑥 that is implicitly read in 𝑇 𝑗 ’s write to 𝑥. 𝑟𝑤

• 𝑇𝑖 −−→ 𝐺 𝑗 if 𝑇𝑖 writes a version of 𝑥 that implicitly reads the version of 𝑝𝑥 that precedes 𝐺 𝑗 ’s write. We assume that governance transactions are write-only and issued one at a time by the application. As such, we exclude edges between governance transactions for the DSG. We prove here that Sintr’s governance transactions, when integrated into a serializable BFT database with optimistic concurrency control (OCC), are serializable. Theorem 2. Sintr’s governance transactions are serializable. Proof. We first show that at each correct replica, the set of committed transactions are serializable. To do this, we show that if there exists an edge 𝑇𝑖 → 𝑇 𝑗 in the DSG, then 𝑖 < 𝑗. Since Sintr does not modify regular transaction concurrency control, we only need to show this holds between regular and governance transactions. 𝑤𝑟 Case: 𝐺𝑖 −−→ 𝑇 𝑗 . 𝑇 𝑗 only implicitly reads policy versions with timestamp before 𝑗, and thus we must have 𝑖 < 𝑗. 𝑟𝑤 Case: 𝑇𝑖 −−→ 𝐺 𝑗 . Suppose for the sake of contradiction there exists such an edge but 𝑗 < 𝑖. In particular, let 𝑇𝑖 be the regular transaction and let 𝐺 𝑗 the governance transaction. We split our analysis based on whether the replica ran the CC check on 𝑇𝑖 first or 𝐺 𝑗 first, and in each case show that this violation is not possible.

A.6

Safety with Policy Versions

We now prove that Sintr maintains safety with policy versions. Lemma 5. Let 𝑂 be an object with policy 𝑝𝑂 . If the number of Byzantine clients that wish to collude for object 𝑂 is 𝑓𝑂 ≤ 𝑝𝑂 , then Sintr guarantees that 𝑂 is only updated by valid committed transactions. Proof. Suppose for the sake of contradiction that there exists an invalid committed transaction 𝑇 which updates 𝑂. Let 𝐺 be the latest governance transaction relative to 𝑇 which updated the policy 𝑝𝑂 . By Assumption 3, there exists at least one correct replica which committed 𝑇 and 𝐺. By Theorem 2, that replica must have ordered 𝐺 before 𝑇 . Thus, 𝑇 must have passed Sintr’s endorsement checks relative to 𝑝𝑂 . The rest of the proof follows by the same logic as in Lemma 2. □ Theorem 1. Let 𝑂 be an object with policy 𝑝𝑂 . If the number of Byzantine clients that wish to collude for object 𝑂 is 𝑓𝑂 ≤ 𝑝𝑂 , then Sintr guarantees that 𝑂 is only updated by valid committed transactions. Moreover, if this holds for every object, then Sintr guarantees application execution validity. Proof. By Lemmas 5 and 3 (note that Lemma 3 does not depend on a fixed policy). □ Lemma 6. Let 𝑇 be a globally committed transaction that reads object 𝑂 1 with version 𝑡𝑠𝑂 1 and writes object 𝑂 2 . In the global serialization order, let 𝑂 1 have policy 𝑝 1 with version 𝑡𝑠𝑝 1 and let 𝑂 2 have policy 𝑝 2 with version 𝑡𝑠𝑝 2 . Let 𝐺 1 be

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

the governance transaction which creates 𝑝 1 ’s version 𝑡𝑠𝑝 1 , and let 𝐺 2 be the governance transaction which creates 𝑝 2 ’s version 𝑡𝑠𝑝 2 . Then there exists a correct replica that commits 𝑇 and has committed both 𝐺 1 and 𝐺 2 . Proof. We prove this for the systems we instantiate Sintr on. For the SMR-based systems, all transactions are ordered through BFT consensus. Thus, every correct replica has committed the same set of transactions; in particular, the most recent governance transactions will be committed. For Basil/Pesto, we use a quorum argument. 𝐺 1 and 𝐺 2 must have been committed by all correct replicas, or at least 𝑛 − 𝑓 = 4𝑓 + 1 replicas. Thus, there must be at least 3𝑓 + 1 replicas which have committed both 𝐺 1 and 𝐺 2 . In order for 𝑇 to be globally committed, there must exist at least 3𝑓 + 1 replicas which committed it. Thus, there are at least 𝑓 + 1 replicas (at least one correct replica) which commit 𝑇 and both 𝐺 1 and 𝐺 2 . □ Lemma 7. Sintr’s governance transactions maintain noninterference. Proof. Suppose for the sake of contradiction that there exists a committed transaction which violates noninterference. Let 𝑇 be such a transaction with timestamp 𝑡𝑠𝑇 , and let 𝑇 read object 𝑂 1 with version 𝑡𝑠𝑂 1 and write object 𝑂 2 . In the global serialization order, let 𝑂 1 have policy 𝑝 1 with version 𝑡𝑠𝑝 1 and let 𝑂 2 have policy 𝑝 2 with version 𝑡𝑠𝑝 2 . Let 𝐺 1 be the governance transaction which creates 𝑝 1 ’s version 𝑡𝑠𝑝 1 and let 𝐺 2 be the governance transaction which creates 𝑝 2 ’s version 𝑡𝑠𝑝 2 . To violate noninterference, there must be a quorum of replicas which commits 𝑇 despite 𝑝 1 < 𝑝 2 . By Lemma 6, there exists at least one correct replica in this quorum which has committed both 𝐺 1 and 𝐺 2 and votes to commit 𝑇 . We will first prove that this correct replica must have used 𝑝 1 for 𝑂 1 in its information flow check. We split our analysis based on whether the replica ran the CC check on 𝑇 first or 𝐺 1 first. Additionally, let 𝑇 ′ be the transaction that creates 𝑂 1 ’s version 𝑡𝑠𝑂 1 . Case 1: CC check on 𝐺 1 first. If 𝐺 1 is globally committed by the time the information flow check on 𝑇 runs, then the check will capture policy 𝑝 1 with version 𝑡𝑠𝑝 1 for 𝑂 1 (Algorithm 6 Line 3). Now consider the case when 𝐺 1 is only locally committed by the time the information flow check on 𝑇 runs. If this were possible, then 𝑇 would not read 𝑡𝑠𝑝 1 as the latest version for 𝑝 1 . However, since 𝑇 depends on 𝑇 ′ for its read to 𝑂 1 , 𝑇 ′ must have been globally prepared or committed by that point as well. By Theorem 2, we know that if 𝑇 ′ and 𝐺 1 both commit, then they are serializable. If they both globally commit, since 𝑡𝑠𝑝 1 < 𝑡𝑠𝑂 1 , 𝑇 ′ must be held to the latest policy in 𝐺. This means that 𝐺 1 must already be globally committed by the time 𝑇 ′ prepares (and, transitively, 𝑇 as well). Otherwise, one of 𝐺 1 or 𝑇 ′ would be aborted. This contradicts 𝐺 1 only being prepared.

Li et al.

Algorithm 5 Endorsement Validation (𝑇 ) 1: 𝐸𝑇 = {} 2: for 𝑒 ∈ Endorsements𝑇 3: if e.sig is valid ∧ e.hash == 𝐻𝑇 4: 𝐸𝑇 = 𝐸𝑇 ∪ 𝑒 5: for key ∈ WriteSet𝑇 6: 𝑝 = GetPolicy(key, tsT ) 7: if |𝐸𝑇 | < 𝑝 8: return false 9: return true

Case 2: CC check on 𝑇 first. Since 𝑇 depends on 𝑇 ′ for its read to 𝑂 1 , 𝑇 ′ must be globally prepared or committed before 𝑇 . But then 𝑇 ′ cannot be held to the latest policy in 𝐺 1 . In order to maintain serializability (Theorem 2), 𝐺 1 must have aborted in this case. This is a contradiction. Thus, it must be the case at least one correct replica used 𝑝 1 for 𝑂 1 in its information flow check. By Theorem 2, if both 𝐺 2 and 𝑇 commit, then the replica must use 𝑝 2 for the write to object 𝑂 2 . But we have 𝑝 1 < 𝑝 2 , so the correct replica must abort the transaction (Algorithm 6 Line 6). This is a contradiction. □ Theorem 3. Sintr upholds noninterference except for objects which have been explicitly lifted. Proof. By Lemma 4, Sintr does not violate noninterference for fixed policies. By Lemma 7, governance transactions do not introduce violations for noninterference. Thus, in all cases, Sintr does not violate noninterference. □

B

Extended Technical Discussion

This section outlines supplementary technical details, optimizations, and considerations for Sintr beyond those discussed in the main technical sections. B.1

Transaction Commit with Versioned Policies

We show Sintr’s endorsement validation and policy information flow checks with a versioned policy store in Algorithms 5 and 6, respectively. We highlight the differences below. For endorsement validation, for each write set key, the replica gets the latest policy version relative to 𝑇 (Line 6). Assuming transaction 𝑇 has timestamp 𝑡𝑠𝑇 , the replica gets the latest policy earlier than 𝑡𝑠𝑇 . For policy information flow, the maximum write set policy is similarly modified to use the latest policy for each key (Line 1). For each read set key, the replica checks what policy was in place when the key was written (Line 3). If there exists a more recent version of that policy, then this implies that the version in the read set was admitted under an old policy (Lines 4–5). In this case we assume the read value was safe and do not check for information flow.

Sintr: Safe Interactive Transactions in the Presence of Byzantine Clients

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

Algorithm 6 Policy Information Flow (𝑇 )

B.3

1: 𝑃𝑇 = max({GetPolicy(key, tsT ) : key ∈ WriteSet𝑇 }) 2: for key, version ∈ ReadSet𝑇

𝑝, tsp = GetPolicy(key, version) if ¬ (tsp is the latest version of 𝑝) continue 6: if 𝑝 < 𝑃𝑇 7: return false 8: return true

3: 4: 5:

B.2

Unique Transaction Identifier with Endorsements

In Sintr, endorsements give a client direct control over a replica’s decision on its transaction. For some BFT databases (e.g., Basil [54], Pesto [55]), this gives Byzantine clients undue influence on correct client transaction outcomes. We use Basil as a representative example to illustrate when the vulnerability is possible and how Sintr addresses it. Basil makes two design choices which, when naïvely combined with Sintr’s endorsements, creates a liveness attack for Byzantine clients. First, Basil makes clients the coordinators of their own transactions. This prevents correct clients from relying upon Byzantine replicas, but also introduces the risk for Byzantine clients to equivocate transaction results. However, Byzantine clients can only equivocate transaction results when replica responses allow them to do so; it is not a strategy that can be pursued reliably in Basil without Sintr. Second, for performance, transactions are permitted to read prepared (but not committed) transaction writes. If correct client transactions acquire dependencies on equivocated transactions, they can subsequently be aborted. To perform this attack, a Byzantine client can send their transaction with a sufficient set of endorsements to the minimum number of replicas to make it visible (𝑓 + 1 in Basil). After the transaction is made visible, the Byzantine client then sends the same transaction, but with insufficient endorsements, to a distinct set of replicas to abort the transaction (at least 3𝑓 + 1 in Basil). Correct replicas, upon receiving this transaction, will vote to abort it due to the transaction failing the endorsement check. A correct client that acquired a dependency on this transaction while it was visible will eventually be forced to abort its own transaction. To prevent this, Sintr ensures that equivocated transactions are considered unique. Upon commit, a transaction 𝑇 receives a unique identifier 𝑖𝑑𝑇 , which is computed as a cryptographic hash of 𝑇 to prevent Byzantine clients from manipulating 𝑇 ’s content. Sintr modifies the transaction identifier to also include endorsements. Identical transactions with different sets of endorsements will be considered different transactions by the system. Aborting a transaction with a different set of endorsements will not affect the results of the original transaction.

Sharing Validation Information

In Sintr, initiating clients must share information about their transaction to validation clients. In particular, clients must share what transactions they run, and what reads and writes are made during the transaction. For some BFT systems (e.g., Basil [54], Pesto [55]), this introduces the possibility for Byzantine validation clients to attack the liveness of the system by creating conflicting transactions. We use Basil as a representative example to discuss the vulnerability. Basil allows clients to choose the timestamps of their transactions for concurrency control. This allows clients to choose when their transactions commit in the serializable schedule of transactions. Byzantine clients can design read-only transactions with conflict windows that overlap with the original transactions. Since Sintr does not require read-only transactions to collect endorsements, the likelihood that the conflicting transaction commits before the original transaction is high. Requiring endorsements for read-only transactions can prevent this attack. Application execution validity is then extended to read-only transactions, preventing Byzantine clients from creating arbitrary read-only transactions. However, committing read-only transactions becomes more expensive as they would now also incur validation costs. We expect Sintr to be used in settings where Byzantine attacks can occur but are infrequent, an assumption commonly held in permissioned blockchains. In order to uphold their reputation in a permissioned system, Byzantine clients are unlikely to participate in detectable Byzantine attacks, and prefer to preserve liveness of the system if they cannot break safety [31, 38]. Under such assumptions, applications do not need to extend Sintr with endorsements for read-only transactions. B.4

Generalizing Policies

In principle, Sintr is compatible with any integrity policy that describes whether a transaction with a set of endorsements can modify an object. We formally define this generalization as follows. Definition 6. Let the set of clients be [𝑛] = {1, 2, . . . , 𝑛}. A policy is as a Boolean-valued function that takes a subset of clients as input, and outputs true if a transaction endorsed by that subset of clients is allowed to write, and false otherwise. That is, a policy 𝑝 is a function 𝑝 : 2 [𝑛] → {0, 1}. For a set of client endorsements 𝐸 ⊆ [𝑛], if 𝑝 (𝐸) = 1, then the set of endorsements satisfies the object’s policy. Otherwise, if 𝑝 (𝐸) = 0, it does not. For example, a policy that requires at least two clients to endorse any transaction could be written as 𝑝 (𝐸) = (|𝐸| ≥ 2). Next, we generalize information flow accordingly. As before, a transaction that reads from an object of policy 𝑝 1 and writes to an object of policy 𝑝 2 has safe information flow if

SOSP ’26, September 29–October 2, 2026, Prague, Czech Republic

Li et al.

𝑝 1 is at least as strong as 𝑝 2 . We formally define this partial ordering below. Definition 7. For two policies 𝑝 1, 𝑝 2 , we write 𝑝 1 ⊑ 𝑝 2 to mean that 𝑝 1 is at least as strong as 𝑝 2 .

More complex policies over client sets can cause endorsements to grow rapidly when accessing objects with nonoverlapping policies. This creates practical challenges for performance and liveness because of the dependence on specific clients.

𝑝 1 ⊑ 𝑝 2 ⇐⇒ ∀𝑆 ⊆ [𝑛], (𝑝 1 (𝑆) = 1) =⇒ (𝑝 2 (𝑆) = 1)

Related documents

• SilentLedger: Privacy-Preserving Auditing for Blockchains with Complete Non-Interactivity#1062793
• Security Issues and Solutions in Peer-to-Peer Systems for Realtime Communications#501173
• SoK: Cross-Chain Transaction Identification and Matching#463158
• Considerations for Web Transaction Security#133849
• Making TransactionIsolation Checking Practical#124147