Consensus in the Partial PKI Setting Beyond One-Quarter Resilience

–

Statement: AI-written, not yet formalized. Proof: open – no attempt yet.

View PDF · LaTeX source · Formal statement — not yet formalized

The source bootstraps a public-key directory with no trusted setup, from a new primitive it calls a multi-verifier signature of work. The result is a \((\gamma,\epsilon)\)-partial PKI: every honest party’s recognized set of identities misses at most an \(\epsilon\) fraction of the honest identities, and honest identities make up all but a \(\gamma\) fraction of the union of everyone’s recognized sets. On top of this the source builds a Byzantine-agreement protocol, PartialPhaseKing, achieving consensus whenever \(\gamma < \tfrac14(1-3\epsilon)\) for \(\epsilon \in (0,\tfrac13)\) (Theorem 5), and proves a matching negative result: no simple protocol — one where honest parties sign everything they send and discard anything they cannot fully verify — achieves consensus at \(\gamma = \tfrac14\), \(\epsilon = 0\) (Theorem 6).

The classical resilience ceiling for consensus of this kind is \(\gamma < \tfrac12\), and the source leaves the gap between \(\tfrac14\) and \(\tfrac12\) open, naming why its own technique cannot close it: multi-verifier signatures of work are not transferable — one honest party may accept a proof that a different honest party rejects. With a transferable proof, one could instead build a ranked partial PKI, from which \(\tfrac12\)-resilient consensus already follows via an adaptation of the Dolev–Strong protocol.

Conjecture (consensus up to one-half resilience). For every constant \(\gamma\) with \(0 \le \gamma < \tfrac12\), there is a protocol achieving consensus (Agreement, Validity, Termination, except with negligible probability) in the source’s permissionless common-random-string setting, tolerating an adversary controlling at most a \(\gamma\) fraction of the registered identities — by any means of bootstrapping those identities, not necessarily a \((\gamma,\epsilon)\)-partial PKI as defined above.

Theorem 6’s impossibility bears only on protocols that are simple and whose identities form an (unstrengthened) \((\gamma,0)\)-partial PKI; it says nothing once a protocol is free to leave that setup abstraction behind, which is exactly what the source’s own proposed route — transferable proofs toward a ranked partial PKI — does.

Sources

  • Abram, Ball, Garay, and Kiayias. Permissionless Consensus from a Common Random String. Cryptology ePrint Archive, Report 2026/1179; abridged version to appear in Proc. CRYPTO 2026. The open question is in Section 5 (“Extensions and Open Questions”), p. 22; the \((\gamma,\epsilon)\)-partial PKI definition and execution model are on pp. 16–17; Theorem 5 (PartialPhaseKing) and Theorem 6 (the one-quarter impossibility for simple protocols, proved for deterministic protocols in Appendix B.3) are on p. 22; the classical \(1/2\) bound is attributed to Fitzi’s thesis, and the ranked-partial-PKI route to Andrychowicz and Dziembowski. InputOutput

View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized

Open. The source proves consensus up to \(\gamma < \tfrac14(1-3\epsilon)\) and proves a matching impossibility only for simple protocols at exactly \(\gamma = \tfrac14\), \(\epsilon = 0\) — and that impossibility proof itself is stated for deterministic protocols, so even the one-quarter barrier for simple protocols is not shown for randomized ones in full generality.

Why simple protocols cannot do better. A simple protocol’s discipline — sign everything sent, discard anything from an unverified signer — is exactly the property Theorem 6’s attack exploits; the source’s own diagnosis is that the fix requires abandoning that discipline entirely, not adjusting it.

The route the source names, and what it still needs. Transferable proofs of work would let every honest party agree on which proofs are valid, yielding a ranked partial PKI — a strictly stronger setup than the \((\gamma,\epsilon)\)-partial PKI above — from which \(\tfrac12\)-resilient consensus follows by a known adaptation of Dolev–Strong. The source does not construct a transferable multi-verifier signature of work; that primitive, or some other way past the \(\tfrac14\) barrier, is the missing piece.

The two halves of the source’s own result frame this cleanly: \(\tfrac14\) is tight for one class of protocols, not for the problem. Reading the impossibility as closing the question would be a mistake the source itself is careful not to make — Theorem 6 is explicitly scoped to protocols that sign and verify everything, and the paper’s own next paragraph points at a way to leave that class. This page states the paper’s actual question, over arbitrary protocols and arbitrary means of bootstrapping identities, precisely so that a construction taking the “obvious” route out — strengthening the setup rather than the protocol — still counts as an answer.

A narrower, harder question is also worth naming: what is achievable if the \((\gamma,\epsilon)\)-partial PKI setup is held fixed and only the protocol is allowed to vary. Theorem 6 does bear on that version, for the “simple” subclass, at \(\epsilon=0\). That is not what is conjectured on this page, since the source’s own preferred route abandons the fixed-setup framing, but it is a natural companion question for a formalization to record if it wants results in both directions.