PaperlayerView exact revision on arXiv

Source-linked AI summary

Sintr: Safe Interactive Transactions in the Presence of Byzantine Clients

Austin T. Li, Daniel H. Lee, Lorenzo Alvisi, Natacha Crooks, Florian Suri-Payer

arXiv:2608.27091v1cs.DC

TL;DR

Client-centric BFT databases improve performance and developer convenience but leave application integrity exposed to Byzantine clients. Sintr combines redundant client re-execution with heterogeneous object-level policies to validate transaction outcomes. Across several BFT systems and workloads, it incurs 3%–16% throughput overhead and 3%–21% latency overhead while strengthening safety.

  • Problem

    Client-centric BFT databases enforce serializability over client-issued operations but cannot ensure that Byzantine clients executed application logic correctly.

  • Method

    Sintr uses independent client re-execution, signed endorsements, and heterogeneous object-level integrity policies to validate transaction outcomes.

  • Results

    Across TPC-C, SEATS, and Smallbank on several existing BFT systems, Sintr incurs 3%–16% throughput overhead and 3%–21% latency overhead.

  • Takeaways & Limitations

    Sintr enables client-centric BFT databases to support interactive transactions while preserving application-level integrity policies against Byzantine clients.

  • Takeaways & Limitations

    Interactive transactions with initially unknown write sets may require additional validation clients and, in the worst case, an additional execution pass.

Abstract

from arXiv · show

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.

1 Introduction

Client-centric BFT databases improve performance and developer convenience by moving transaction execution to clients, but this exposes application integrity to Byzantine clients. Sintr addresses the gap with redundant validation and object-specific integrity policies, while adding modest overhead.

  • Motivation: Client-centric BFT systems improve throughput and developer ergonomics by having clients execute transactions while the backend enforces serializability.This architecture keeps application logic outside the database backend.
  • Motivation: Byzantine clients can issue semantically incorrect transactions that remain serializable, because replicas enforce isolation rather than application execution correctness.The vulnerability allows incorrect updates to application data without violating database-level consistency.
  • Sintr: Sintr validates transaction outcomes through independent client re-execution and endorsements, restoring the guarantee that objects are updated only by correctly executed application logic.Replicas accept transactions only after validating the required endorsements.
  • Sintr: Object-level heterogeneous policies require stronger validation for more sensitive data, so validation overhead scales with required safety rather than applying uniformly.Applications can protect financial records more strongly than auxiliary metadata.
  • Evaluation: 3%–16% throughput overhead and 3%–21% latency overhead were measured across TPC-C, SEATS, and Smallbank workloads.The implementation hardened Basil, Pesto, HotStuff, and BFT-SMaRt over SQL and key-value stores.

2 The Pitfall

Client-centric execution preserves database-level consistency but removes replicas’ ability to verify application semantics. This creates a general safety gap whenever application execution is decoupled from replicated agreement.

  • Traditional designs: Traditional SMR colocates application logic with replicas, allowing replicas to execute commands deterministically and enforce application semantics.This coupling supports stronger validation but constrains application development.
  • Client-centric designs: Client-centric systems let clients execute transactions and submit resulting reads and writes, while replicas enforce consistency over the observed operations.Replicas no longer execute the application logic that generated those operations.
  • The safety gap: A Byzantine client can submit serializable reads and writes that do not correspond to any valid application transaction.The Payment example can violate application invariants while remaining serializable.
  • Scope: The problem extends beyond SMR to BFT systems that decouple application execution from replicated agreement, including client-driven storage and quorum-based systems.These systems can ensure consistency over stored values without seeing semantic correctness of client computation.
  • Scope: Correctness definitions based only on ordering and isolation are insufficient because they do not capture whether application logic executed correctly.The gap requires an explicit application-execution safety definition.

3 Model and Definitions

Sintr models applications as deterministic interactive transactions and defines safety in terms of faithful application execution. This formalization distinguishes semantic validity from database-level isolation.

  • System model: Sintr assumes authenticated participants, a strong static adversary, and partial synchrony only for liveness.Faulty participants may deviate arbitrarily, subject to the underlying fault thresholds.
  • Safety definition: Client-side reads and writes may be serializable yet violate application invariants, motivating correctness definitions that explicitly account for application execution.This is the safety property Sintr seeks to restore.
  • Application model: Interactive transactions interleave client-side computation with database requests and are written in general-purpose languages.This model supports developer-friendly application logic that can scale independently of the backend.
  • Application model: The application is modeled as a set of predefined deterministic transactions, with programmatic nondeterminism represented as transaction inputs.Non-programmatic nondeterminism is not supported.
  • Safety definition: A transaction is valid when it faithfully executes one predefined application transaction, and an application execution is valid when every committed non-read-only transaction is valid.Invalid read-only transactions are intentionally excluded from the guarantee.

4 Sintr Framework

Sintr restores application execution validity by combining redundant client validation with object-specific integrity policies. Its guarantees depend on policy strength and endorsement availability, while practical mechanisms address heterogeneous data and interactive write-set discovery.

  • Framework: Sintr introduces redundant transaction execution so independent clients can validate outcomes against Byzantine client behavior.The framework uses a transaction-centric fault model with bounded faulty clients.
  • Integrity policies: Heterogeneous policies let applications assign stronger protection to sensitive financial records than to lower-integrity record-keeping data.TPC-C-like workloads illustrate this distinction.
  • Integrity policies: An object with policy x requires at least x independent client endorsements before a transaction may modify it.This protects the object against coalitions of x or fewer Byzantine clients.
  • Information flow: Sintr rejects transactions that violate noninterference unless they explicitly lift selected read objects through deterministic application-defined lift functions.Lift functions validate low-policy data before it influences higher-policy writes.
  • Safety: If Byzantine collusion for object O is at most its policy p_O, Sintr guarantees that O is updated only by valid committed transactions.Application execution validity follows when the condition holds for every object.
  • Limitations: Liveness requires correct clients to collect the endorsements demanded by policy without relying on faulty clients.Byzantine clients can still obstruct progress by ignoring requests or soliciting excessive endorsements.

5 Sintr Protocol

Sintr has clients execute transactions locally while peer validation clients independently re-execute them using verified forwarded database results. Signed endorsements over transaction effects allow replicas to reject divergent executions, while validation requirements depend on anticipated writes and policies.

  • Sintr can augment any BFT database supporting interactive transactions.
  • Validation scope: The initiating client estimates required validators from the anticipated write set and key policies, but undiscovered writes can require another validation pass.
  • Execution and validation: Clients execute application logic locally, while validation clients re-execute transactions without issuing database requests to the backend.Validation clients instead use forwarded execution results and proofs, avoiding additional backend load.
  • Execution and validation: Forwarded database results include responses and cryptographic proofs bound to request identifiers, enabling validation clients to verify them before resuming execution.
  • Execution and validation: Deterministic execution over identical inputs should produce matching states, so an incorrect client computation yields mismatching endorsements and transaction abort.
  • Endorsements: Endorsements attest to externally visible reads and writes, while reads that influence no writes require no endorsements.

6 Evaluation

Sintr is evaluated across transactional workloads, policy configurations, runtime policy changes, Byzantine-client behavior, policy lifting, and dynamic write-set discovery. It generally adds modest overhead, while costs depend on bottlenecks, validation expense, and policy heterogeneity.

  • High Level Performance: Under TPC-C, throughput reductions range from 3.0% to 6.4% on Peloton-SMR, while Pesto reaches 1471 tx/s and 1431 tx/s under P-1 and P-2.Latency increases by 6.9% and 3.1% on Peloton-SMR, and by 16.8% and 21.7% for the respective Pesto inflection points.
  • High Level Performance: Under SEATS, Pesto reaches 3569 tx/s and 3468 tx/s under P-1 and P-2, within 7.4% and 10.0% of base Pesto.Latency is 8.2% and 11.3% higher, while Peloton-SMR systems incur little additional overhead because endorsement checks are small relative to consensus latency.
  • Impact of Application Policy: Policy overhead is larger in CPU-bound, short-transaction settings, but modest when contention dominates; each added endorsement reduces throughput by 8–9% under the uniform workload.Under Zipfian contention, P-1-U incurs a 20.6% throughput reduction and a 36.8% latency increase.
  • Dynamically Changing Policies: Governance transactions commit in under 5 ms, and policy updates take effect without halting transaction processing.Clients may abort at most one in-flight transaction after the first update and temporarily generate excess endorsements after the second.
  • Residual Impact and Policy Lifting: Byzantine clients cannot compromise correctness under a well-chosen policy, but denial-of-service behavior can reduce throughput by 25% when validation is expensive.Ignore-val causes only 1–5% degradation, whereas ddos impact grows with validation cost; lifting improves throughput by 11.6% over uniform P-5 while preserving P-5 safety for financial data.
  • Dynamic Write-set Discovery: Dynamic write-set discovery remains efficient without advance write-set knowledge, with overhead rising to roughly one message round trip as policy heterogeneity grows.The worst case occurs when the final update triggers contact with four additional validation clients.

7 Related Work

Prior BFT systems either execute application logic at replicas or delegate it to clients, trading scalability and usability against execution safety. Sintr instead validates interactive client-side transactions through redundant client execution.

  • SMR-based BFT systems colocate application logic and state at replicas, enabling deterministic execution and direct enforcement of application semantics.
  • Client-centric systems such as Basil, Pesto, and HRDB improve performance and developer usability while replicas enforce ordering and isolation.
  • Prior redundant-execution systems retain replica-side execution and may allow correct replicas to diverge because validation uses replica-local state.
  • Sintr uses redundant execution among clients to validate interactive transactions while ensuring correct validators reach identical outcomes.
  • Database integrity constraints can enforce semantic properties, but checking transaction-execution validity may degenerate into re-executing the transaction inside the database.
  • Information-flow approaches regulate who may access or modify data, whereas Sintr addresses whether application logic was executed correctly.

8 Conclusion

Sintr reconciles client-side transaction scalability and expressiveness with strong server-side validation. It uses redundant client execution and endorsements alongside heterogeneous integrity policies to protect committed transactions.

  • Sintr targets Byzantine clients in client-centric interactive transactional systems while preserving client-side scalability and expressiveness.
  • Redundant client execution and explicit endorsements ensure committed transactions adhere to application-level integrity policies despite malicious clients.
  • Heterogeneous policies express fine-grained integrity requirements without modifying the underlying database protocols.

A Proofs

The proofs define faithful execution and globally committed transactions, then rely on backend assumptions about correct replicas, serializability, and shared commitments. These assumptions support Sintr’s general safety arguments.

  • A.1 Formal Definitions: A faithful execution reproduces the transaction specification’s write set exactly for the given inputs and ordered read results.
  • A.2 BFT Backend Assumptions: Sintr’s proofs are backend-independent and require only minimal assumptions satisfied by the instantiated BFT systems.
  • A.2 BFT Backend Assumptions: A globally committed transaction is defined from the transactions locally committed by replicas and the backend protocol’s global-commit rule.
  • A.2 BFT Backend Assumptions: In inconsistent replication systems, global commitment may require a replica quorum, such as at least 3f+1 of 5f+1 replicas.
  • A.2 BFT Backend Assumptions: The backend must ensure that every globally committed transaction has at least one correct replica that considers it committed.
  • A.2 BFT Backend Assumptions: Globally committed transactions must remain serializable when correct replicas commit only serializable transactions.
  • A.2 BFT Backend Assumptions: For any two globally committed transactions, at least one correct replica must have locally committed both to determine database isolation.

A.3 Correctness Sketch

The correctness sketch proves Sintr’s guarantees through validation, fixed and versioned policies, governance serializability, and noninterference. Its safety condition bounds colluding Byzantine clients by each object’s policy strength.

  • A.3 Correctness Sketch: The proof proceeds through fixed-policy safety, governance-transaction serializability, and safety for versioned policies.
  • A.3 Correctness Sketch: A matching endorsement from a correct validation client implies that the transaction is valid.
  • A.3 Correctness Sketch: When an object’s policy holds, Sintr ensures the object is updated only by valid committed transactions.
  • A.3 Correctness Sketch: For an object with policy p_O, execution validity holds when colluding Byzantine clients satisfy f_O ≤ p_O.
  • A.3 Correctness Sketch: Sintr preserves noninterference except for explicitly lifted objects, including under versioned policies.
  • A.3 Correctness Sketch: Sintr’s governance transactions are serializable and maintain noninterference.

A.4 Safety with Fixed Application Policy

With a fixed application policy, Sintr uses matching client endorsements to validate transaction execution and protect object integrity and noninterference.

  • Execution validity: A transaction receiving a matching endorsement from a correct validation client must be valid.Correct validation clients deterministically re-execute the claimed transaction using correct database results, and the endorsement hash includes its write set.
  • Execution validity: If at most p_O Byzantine clients collude over object O, Sintr ensures O is updated only by valid committed transactions.The endorsement check requires at least p_O matching endorsements, so a colluding group of at most p_O cannot satisfy the requirement without a correct client.
  • Execution validity: When every object is updated only by valid committed transactions, Sintr guarantees application execution validity.This follows because all non-read-only committed transactions are valid.
  • Noninterference: Sintr upholds noninterference except for objects explicitly lifted by the application policy.A lower-policy object cannot influence a higher-policy write because the information-flow check compares the read policy with the maximum write policy and aborts the transaction.

A.5 Governance Transaction Serializability

Sintr integrates governance transactions into serializable BFT databases by extending conflict analysis to policy versions and governance–regular transaction dependencies.

  • Conflict model: Sintr requires serializability for governance transactions and extends Adya’s formalism to define their conflicts with regular transactions.Governance transactions are write-only, issued one at a time, and have policy-version dependencies with regular transactions.
  • Conflict model: The direct serialization graph represents committed transactions as timestamped vertices connected by write–write, write–read, and read–write edges.Governance–regular edges capture policy versions implicitly read by regular transaction writes.
  • Serializability result: Sintr’s governance transactions are serializable when integrated into a serializable BFT database with optimistic concurrency control.The proof shows every direct-serialization-graph edge proceeds from a lower to a higher timestamp, preventing cycles.
  • Serializability result: Correct replicas preserve timestamp order because concurrency checks reject governance–regular conflicts that would reverse the order.If either transaction’s check runs first, the other transaction is aborted when committing would violate the recorded policy read or conflict order.

A.6 Safety with Policy Versions

With versioned policies, Sintr extends its safety guarantees to governance updates while addressing liveness risks caused by client-controlled coordination and timestamps.

  • Versioned-policy safety: If at most p_O Byzantine clients collude over object O, Sintr still ensures O is updated only by valid committed transactions under policy versions.The theorem extends the fixed-policy guarantee using the latest governance transaction relevant to O.
  • Versioned-policy safety: A globally committed transaction has a correct replica that also committed the governance transactions defining the policies of its read and write objects.This property supports applying the relevant policy versions during information-flow checking.
  • Noninterference: Sintr’s governance transactions maintain noninterference.The proof considers whether governance or regular concurrency checks run first and uses serializability to ensure the relevant policy version is enforced.
  • Noninterference: Sintr upholds noninterference except for objects explicitly lifted by the application.If a lower-policy read would influence a higher-policy write, a correct replica uses the relevant policies and aborts the transaction.
  • Liveness considerations: Basil’s client-coordinator design can enable Byzantine clients to equivocate transaction results across replica subsets, creating a liveness attack when endorsements are added naively.A client can send sufficient endorsements to make a transaction visible to one replica set, then insufficient endorsements to another set so correct replicas vote to abort.
  • Liveness considerations: Client-controlled timestamps and endorsement-free read-only transactions make conflicting read-only transactions likely to commit before an original transaction in Basil.Byzantine clients can choose overlapping conflict windows to exploit this behavior.
Loading 2608.27091v1…