Paper 2026/2937

Any Friend of Yours: Asynchronous Consensus with Unknown Participants from Local Trust

Ignacio Amores-Sesar, Aarhus University
Simon Holmgaard Kamp, Ruhr University Bochum
Juan Villacis, University of Bern
Abstract

Byzantine agreement protocols typically assume that all processes already agree on who participates and which failures must be tolerated. In an open system, reaching agreement on this information is itself a consensus problem. We avoid this circularity by presenting asynchronous protocols in which each process acts only on its own local trust. Each process declares quorums over the identities it knows and communicates by authenticated multicast. Processes need not know the number of participants or the trust assumptions of others, and we assume no trusted dealer, common reference string, or bound on the number of identities, including Sybil identities. Unlike Stellar and prior asymmetric-trust protocols, our protocols do not require a closed set of mutually trusting correct processes. Instead, their guarantees are characterized by depth, a fine-grained, failure-dependent measure of how well each process's trust matches the actual failures. We construct validated reliable broadcast, Byzantine agreement, agreement on a core set, and state machine replication in this model. The main technical ingredient for randomized termination is an approximate common coin based only on local trust.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Asynchronous Byzantine agreementunknown participantsasymmetric trustquorum systems
Contact author(s)
amores-sesar @ cs au dk
simonhkamp @ gmail com
juan villacis @ unibe ch
History
2026-11-22: approved
2026-11-18: received
See all versions
Short URL
https://ia.cr/2026/2937
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2937,
      author = {Ignacio Amores-Sesar and Simon Holmgaard Kamp and Juan Villacis},
      title = {Any Friend of Yours: Asynchronous Consensus with Unknown Participants from Local Trust},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2937},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2937}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.