Paper 2026/2937
Any Friend of Yours: Asynchronous Consensus with Unknown Participants from Local Trust
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
-
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}
}