Brief Announcement: Fair Binding for Hidden-State Authorization in Byzantine SMR

Brief Announcement: Fair Binding for Hidden-State Authorization in Byzantine SMR Arnab Mallick # Ñ Centre for Development of Advanced Computing, Hyderabad, India

arXiv:2608.17349v1 [cs.DC] 18 Aug 2026

Abstract Validated Byzantine SMR assumes that replicas can evaluate the validity of an ordered command. Agent authorization creates a different regime: a command may be valid only relative to a committed policy state that validators cannot reconstruct from the log. A proof that an action was authorized at an old commitment is then only a historical attestation, it does not by itself reserve the hidden resource for later use. We isolate two independent requirements for safe live allocation of a hidden consumable resource under a Byzantine leader. First, arrival order at correct replicas must constrain commit order, the gap addressed by fair-ordering protocols. Second, a committed first request must bind later validity: it must make conflicting later requests invalid, not merely record that the first request was once authorized. The second requirement is non-vacuous precisely because the current policy state is hidden and not prefix-recoverable. Using an explicit authorization-witness interface, we characterize the two distinct obligations in this one-shot reservation model and give a fair reserve/use protocol satisfying both authorization safety and first-arrival liveness. Under trusted FIFO admission the two requirements collapse because admission and execution are atomic, Byzantine SMR separates request commitment from use. 2012 ACM Subject Classification Computing methodologies → Distributed algorithms; Computer systems organization → Dependable and fault-tolerant systems and networks; Security and privacy → Distributed systems security Keywords and phrases Byzantine consensus, validated agreement, order fairness, hidden state, authorization Category Brief Announcement Supplementary Material Software (Lean 4 formalization): GitHub repository

1

Introduction

Byzantine state machine replication (SMR) [7, 2] makes correct replicas agree on an ordered log. Validated Byzantine SMR [1] further requires each ordered value to satisfy a validatorcheckable external-validity predicate. Standard applications make the predicate public or derivable from replicated state. Agent systems create a less classical case: authorization can depend on a policy state tracking budgets, permissions, retrieved context, or private balances that is committed but not replicated at validators. Validators see authenticated commitments to policy state and proof-carrying evidence, but cannot reconstruct the current state from the log prefix. This distinction matters for contended consumable resources. Suppose a hidden policy state contains one available unit of a resource. Two clients may both receive valid evidence that their action was authorized at the same commitment ci . A Byzantine leader can commit the second-arriving reservation before the first. Fair ordering addresses that arrival-order gap. But even if the first client’s claim is fairly ordered first, a claim that merely attests “the resource was free at ci ” does not reserve the resource: a Byzantine leader can order a conflicting reservation and use between the claim and the first client’s later use. Figure 1 summarizes the two failure modes and their composition.

2

Fair Binding for Hidden-State Authorization

(a) Binding without fair order log:

reserve(b)

arrival: reserve(a) ≺ reserve(b)

reserve(a) rejected

(b) Fair claim order without binding log:

claim(a)

claim(b)

b binds first arrival: claim(a) ≺ claim(b)

reserve(b)

use(b)

historical evidence only; later reservations remain unconstrained (c) Fair reservation order with binding log:

reserve(a)

reserve(b) rejected

arrival: reserve(a) ≺ reserve(b) use(a)

reserved(r, a) is prefix-visible

Figure 1 Two distinct obligations and their composition. Fair ordering protects a separated first arrival at the priority-command phase, binding determines what the winning committed command makes invalid afterward. Fairly ordered historical claims do not constrain later reservations, whereas a fairly ordered binding reservation does.

One-shot example. A confidential policy permits one remaining API invocation. Agents a and b obtain valid witnesses against the same commitment while the unit is available. If a’s historical claim commits without creating a public reservation, validators still have no prefix-visible reason to reject b’s later reservation. Committing reserved(r, a), in contrast, makes b’s conflicting reservation invalid.

Contribution. We formalize this as hidden-state authorization: validators can verify witnesses against commitments but cannot compute current authorization from the committed prefix. For a first-arriving honest request to safely and eventually execute, Byzantine SMR needs two orthogonal properties: Fair commit order. If all correct replicas receive request a before any receive conflicting request b, then a must commit before b. Binding validity. Once a commits, the validator must reject later conflicting requests. A historical attestation is not enough, the log must contain a reservation or an equivalent prefix-readable validity rule. We make the witness interface explicit. We show that reservation priority requires fair commit order and that fair ordering of nonbinding historical claims alone is insufficient. We then give a two-phase reserve/use construction. The characterization is for one indivisible, non-replenishing resource, replenishing and multi-resource conflicts are outside its scope.

2

Model

Validated Byzantine SMR. n = 3f + 1 replicas, at most f of which may be Byzantine and deviate arbitrarily, maintain an ordered log. The protocol is leader-based and partially synchronous: after an unknown GST, message delays are bounded and ordinary BFT liveness applies, timeouts trigger leader rotation. A slot is a position in the committed log. Before ordering a command, correct replicas evaluate its external-validity predicate.

Arnab Mallick

3

▶ Definition 1 (One-resource hidden-state authorization object). Let S, C, R, A, E be the domains of policy states, commitments, resources, actions, and witnesses. The policy predicate and public witness verifier have signatures P : S ×R×A → {0, 1},

VAuth : C ×R×A×E → {0, 1}.

The object exports reserve(r, a, e) → {commit, reject} and use(r, a) → {execute, reject}. We use the auxiliary historical command claim(c, r, a, e) → {commit, reject} to separate attestation from reservation. A matching reservation and use carry the same pair (r, a).

Notation and timing. Let L<j be the committed prefix before slot j. Validation for slot j uses L<j and the current policy commitment cj . Validators maintain a set Kj of authenticated commitments known from the prefix or authenticated policy-state interface. A prefix contains a matching reservation for a if it contains reserved(r, a), and a conflicting reservation if it contains reserved(r, x) for some x#r a. A witness e is current-valid for (r, a) at slot j when VAuth(cj , r, a, e) = 1.

Hidden policy state. At log height j, the policy state is Sj and its authenticated commitment is cj . Validators know cj but do not know Sj and cannot reconstruct it from L<j . All correct validators evaluate authorization against the same authenticated current commitment: the policy-state interface does not equivocate among them. If validators could compute Sj from the prefix, ordinary revalidation would subsume binding.

Authorization witnesses. Soundness says that if c binds state S and VAuth(c, r, a, e) = 1, then P (S, r, a) = 1; completeness gives an accepting witness for every authorized action. An opening, zero-knowledge proof, or transition certificate is an example realization of e, not a model primitive. Evidence is commitment-relative: evidence for ci proves authorization at ci , not continued validity after later transitions.

Hidden consumable resource. The theorem concerns one indivisible, non-replenishing resource r whose hidden projection is in {free, used}. A consuming action is enabled only at free and changes that projection to used; no transition restores it. Write a#r b when both compete for that unit, so no legal execution from the same available-resource state can execute both. This is the one-shot incompatibility specialization of state-dependent conflict and non-commutativity [6]. Replenishing balances and multi-resource transactions are outside the characterization.

Command classes. A historical command claim(c, r, a, e) is valid at slot j when c ∈ Kj and VAuth(c, r, a, e) = 1; committing it adds no public conflict fact and does not advance the hidden commitment. A reservation reserve(r, a, e) is valid when e is current-valid and L<j contains no conflicting reservation, on commit it appends reserved(r, a). A use use(r, a) is valid only after a matching reservation, successful use consumes the hidden unit. Reservations are irrevocable: there is no release, cancellation, or expiry.

4

Fair Binding for Hidden-State Authorization

For a protocol, its priority command is the command whose ordering establishes firstarrival precedence. It is reserve in the construction and claim in the claim-priority baseline, that baseline still requires a later reservation before use. ▶ Definition 2 (Fair commit order and binding validity). Fair commit order requires that if every correct replica receives the priority command for a before any correct replica receives a conflicting priority command for b, then b does not commit before a. Binding validity requires that once the winning priority command for a commits, the prefix contains a public conflict fact that makes every later conflicting reservation invalid. In the reserve/use construction this fact is reserved(r, a). ▶ Definition 3 (Evidence-local validation). A validator is evidence-local if its decision at slot j may use L<j , Kj , the current commitment cj , public facts reserved(·, ·) recorded in the prefix, syntactic well-formedness, and VAuth on supplied witnesses. It does not query or reconstruct Sj . Thus, unless the prefix contains a binding fact, authorization evidence does not make conflicting later commands invalid. ▶ Definition 4 (Authorization safety and first-arrival liveness). Authorization safety requires that no two actions a#r b both execute and every executed use(r, a) has a prior matching reservation. First-arrival liveness requires that if the honest priority command for a is received by every correct replica before any correct replica receives a conflicting priority command, then a eventually executes under the usual post-GST conditions, assuming the honest client remains live, supplies current-valid evidence until its reservation is ordered (refreshing it if necessary), and submits the required follow-up reservation and use. For interleaved conflicting arrivals no first-arrival guarantee is imposed, safety still permits at most one conflicting use. ▶ Proposition 5 (Trusted-FIFO baseline). Under trusted FIFO admission, the first request accepted by the trusted path is ordered and executed atomically before any later conflict. Fair ordering and consensus-resident binding are therefore not separate obligations. Byzantineleader SMR separates request commitment from later use, exposing both gaps.

3

Necessity

We separate two requirements. Fair ordering is about which request reaches the log first, binding validity is about what the first log entry makes invalid later. ▶ Lemma 6 (Fair order is necessary for first-arrival liveness). Consider an authorization-safe protocol using the reservation rule above. If it permits a later conflicting reservation to commit before a first-arriving honest reservation, then it can violate first-arrival liveness. Proof. Let honest reserve(r, a, ea ) be received by all correct replicas before any correct replica receives reserve(r, b, eb ) with a#r b, and suppose both witnesses are current-valid at the relevant slot. By the negative assumption, some Byzantine-leader execution commits b first. The prefix now contains reserved(r, b), a conflicting reservation for a. To preserve authorization safety, the protocol must reject or fail to execute a; accepting both would allow conflicting uses of r. Hence the first-arriving honest request is not live. First-arrival liveness therefore requires fair commit order for conflicting reservations. ◀ This is exactly the gap targeted by order-fairness mechanisms [4, 3, 8]. ▶ Lemma 7 (Historical attestations are insufficient). Suppose first-arrival precedence is enforced only by fairly ordering historical claim commands, while committed claims neither create a

Arnab Mallick

public conflict fact nor constrain the order of later conflicting reservations. Then fair claim order alone does not imply authorization safety plus first-arrival liveness. Proof. Suppose fair ordering guarantees that an attestation claim(ci , r, a, ea ) commits before a conflicting attestation claim(ci , r, b, eb ), where a#r b. By definition, an attestation-only claim records VAuth(ci , r, a, ea ) = 1 but appends no reserved(r, a), no other conflict fact, and no update that makes the hidden commitment unavailable for later conflicting authorization. Consider an execution in which no authenticated policy-commitment update occurs between these slots, so the current commitment remains ci . Immediately after the committed claim for a, the public prefix still contains no fact making b invalid, and eb can be current-valid for b. A Byzantine leader can therefore propose reserve(r, b, eb ) before a’s later use. If b is accepted, a can no longer execute without double-spending r; if a is later also accepted, safety is violated. Rejecting a preserves safety but violates first-arrival liveness. Fair ordering of attestations therefore does not suffice, the first committed claim must bind subsequent validity. ◀ ▶ Observation 8 (Orthogonality). Fair order and binding validity are independent. A binding reservation without fair order can bind the wrong, later-arriving request first. A fair-ordered attestation without binding leaves later conflicting validity unchanged. The two obligations therefore address distinct failure modes in the one-shot reservation model.

4

Sufficiency Construction

▶ Proposition 9 (Fair reserve/use). Assume a reservation-ordering layer satisfying fair commit order (Definition 2). The reserve/use protocol satisfies authorization safety and first-arrival liveness for the one-shot hidden resource. Construction. Reserve. At slot j, a client submits a reservation for (r, a) with evidence e. Validity requires VAuth(cj , r, a, e) = 1 and no conflicting reservation in L<j . On commit, the log records reserved(r, a) as a public binding fact. Use. A client submits use(r, a). Validity requires a prior reserved(r, a) in the prefix. No conflicting use(r, b) is valid because the prefix test prevented a conflicting reservation and use requires a matching one. Safety. By induction on slots, once reserved(r, a) appears, every later reserve(r, b, ·) with a#r b is invalid, and every use names a committed reservation. Hence conflicting uses cannot both execute. Liveness. If honest reserve(r, a, ·) is received by all correct replicas before any conflicting reservation, fair ordering puts it first while the client’s supplied or refreshed evidence remains current-valid. The reservation binds the prefix, so later conflicts are invalid. After GST, ordinary BFT liveness orders the matching use. ◀

Algorithmic interface. The construction treats fair ordering for reservation commands as a service supplied by the consensus layer. Binding is implemented by the application’s external-validity predicate: once reserved(r, a) appears in the committed prefix, validators reject every conflicting reservation. The two obligations therefore compose at different layers-ordering in consensus and conflict exclusion in application validity.

5

6

Fair Binding for Hidden-State Authorization

▶ Theorem 10 (One-resource characterization). For evidence-local Byzantine SMR implementing Definition 1 for one indivisible, non-replenishing resource under the reservationadmissibility rule above: an authorization-safe implementation satisfying first-arrival liveness for reservationpriority requests requires fair commit order for conflicting reservations; in the claim-priority baseline, fair ordering of historical claims without a prefix-visible binding fact or another ordering constraint on later conflicting reservations is insufficient for authorization safety plus first-arrival liveness; the fair reserve/use protocol satisfies authorization safety and first-arrival liveness. Proof. Clause (i) is Lemma 6, clause (ii) is Lemma 7, and clause (iii) is Proposition 9.

5

◀

Discussion

Why this is not just revalidation. If validators can compute the current state from the log, they can revalidate each command against Sj , and binding validity is automatic. That is not our model. Here the policy state is committed but hidden, so old evidence is stale information and the prefix contains no conflict fact unless the protocol writes one. Binding is therefore a consensus-level obligation.

Why this is not just locking. Under a trusted lock manager or trusted FIFO queue, admission and execution are atomic outside the Byzantine log. In Byzantine SMR, the log is the only shared durable medium. A lock that is not in the log can be ignored or reordered by the leader, a log entry that is not binding is only an attestation. The lock must be both consensus-visible and fairly ordered.

Why this is not just fair ordering. Order-fairness constrains the relative order of commands, not the monotonicity of an application’s validity predicate. Lemma 7 gives the separation: even perfectly fair ordering of historical claims leaves later validity unchanged unless the first claim creates a public binding fact.

Beyond one resource. We do not claim a free extension to replenishing balances, multiple units, multi-resource transactions, or partial fair orders. For example, if T1 and T2 spend Alice’s balance while an intervening T3 replenishes it, T1 → T3 → T2 may be legal: the conflict is version-dependent and can disappear after T3 . Such an execution requires fresh authorization rather than permanent exclusion and lies outside our one-shot theorem. With k units and m > k contenders, one must additionally agree on a winner set, while partial fair orders may contain cycles.

Relation to prior work. Fair-ordering protocols [4, 3, 8] repair the arrival-order-vs-commit-order gap but do not by themselves specify what a committed value means for later application validity. Validated Byzantine agreement [1] covers public predicates, our setting is different because current authorization is committed but not reconstructible by validators. The attestation/reservation

Arnab Mallick

distinction is the optimistic-vs-pessimistic concurrency-control boundary [5] transported into Byzantine SMR with hidden state. Dynamic-concurrency work makes conflict explicitly state-dependent [6], our relation #r is its non-replenishing, one-shot specialization. References 1

2

3

4

5 6

7 8

Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and efficient asynchronous broadcast protocols. In Joe Kilian, editor, Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19-23, 2001, Proceedings, volume 2139 of Lecture Notes in Computer Science, pages 524–541. Springer, 2001. URL: https://doi.org/10.1007/3-540-44647-8_31, doi:10.1007/ 3-540-44647-8_31. Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. In Margo I. Seltzer and Paul J. Leach, editors, Proceedings of the Third USENIX Symposium on Operating Systems Design and Implementation (OSDI), New Orleans, Louisiana, USA, February 22-25, 1999, pages 173–186. USENIX Association, 1999. URL: https://dl.acm.org/citation.cfm?id= 296824. Mahimna Kelkar, Soubhik Deb, Sishan Long, Ari Juels, and Sreeram Kannan. Themis: Fast, strong order-fairness in byzantine consensus. In Weizhi Meng, Christian Damsgaard Jensen, Cas Cremers, and Engin Kirda, editors, Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, CCS 2023, Copenhagen, Denmark, November 26-30, 2023, pages 475–489. ACM, 2023. doi:10.1145/3576915.3616658. Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels. Order-fairness for byzantine consensus. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17-21, 2020, Proceedings, Part III, volume 12172 of Lecture Notes in Computer Science, pages 451–480. Springer, 2020. URL: https://doi.org/10.1007/ 978-3-030-56877-1_16, doi:10.1007/978-3-030-56877-1_16. H. T. Kung and John T. Robinson. On optimistic methods for concurrency control. ACM Trans. Database Syst., 6(2):213–226, 1981. doi:10.1145/319566.319567. Petr Kuznetsov and Nathan Josia Schrodt. Resolving conflicts with grace: Dynamically concurrent universality. In Andrei Arusoaie, Emanuel Onica, Michael Spear, and Sara Tucci Piergiovanni, editors, 29th International Conference on Principles of Distributed Systems, OPODIS 2025, Iaşi, Romania, December 3-5, 2025, volume 361 of LIPIcs, pages 33:1–33:29. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.OPODIS.2025. 33. Leslie Lamport. State the problem before describing the solution. ACM SIGSOFT Softw. Eng. Notes, 3(1):26, 1978. doi:10.1145/1010734.1010737. Yunhao Zhang, Srinath T. V. Setty, Qi Chen, Lidong Zhou, and Lorenzo Alvisi. Byzantine ordered consensus without byzantine oligarchy. In 14th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2020, Virtual Event, November 4-6, 2020, pages 633–649. USENIX Association, 2020. URL: https://www.usenix.org/conference/osdi20/ presentation/zhang-yunhao.

7

Related documents

• On the (In)security of Peer-to-Peer Decentralized Machine Learning#134002
• Diffie-Hellman Proof-of-Possession Algorithms#139546
• FloatDoor: Platform-Triggered Backdoors in LLMs#290539
• Privacy-Preserving RAG by Concealing Sensitive Information from External LLMs#451247
• LLMs for Secure Hardware Design and Related Problems: Opportunities and Challenges#175114