Scalable distributed agreement from LWE: Byzantine agreement, broadcast, and leader election Rex Fernando, Yuval Gelles, Ilan Komargodski Abstract Distributed agreement is a general name for the task of ensuring consensus among non-faulty nodes in the presence of faulty or malicious behavior. Well-known instances of agreement tasks are Byzantine Agreement, Broadcast, and Committee or Leader Election. Since agreement tasks lie at the heart of many modern distributed applications, there has been an increased interest in designing scalable protocols for these tasks. Specifically, we want protocols where the per-party communication complexity scales sublinearly with the number of parties. With unconditional security, the state of the art protocols have O~(n) per-party communication and O~(1) rounds, where n stands for the number of parties, tolerating 1/3-ε fraction of corruptions for any ε>0. There are matching lower bounds showing that these protocols are essentially optimal among a large class of protocols. Recently, Boyle-Cohen-Goel (PODC ’21, Journal of Cryptology ’24) relaxed the attacker to be computationally bounded and using strong cryptographic assumptions showed a protocol with O~(1) per-party communication and rounds (similarly, tolerating 1/3-ε fraction of corruptions). The security of their protocol relies on SNARKs for NP with linear-time extraction, a somewhat strong and non-standard assumption. Their protocols further rely on a public-key infrastructure (PKI) and a common-reference-string (CRS). In this work, we present a new synchronous protocol with O~(1) per-party communication and rounds but relying only on the standard Learning With Errors (LWE) assumption. Our protocol also relies on a PKI and a CRS, and tolerates 1/3-ε fraction of corruptions, similarly to Boyle et al. Technically, we leverage (multi-hop) BARGs for NP directly and in a generic manner that significantly deviates from the framework of Boyle et al. Introduction Byzantine Agreement [, ] is a classical problem in distributed computing whose aim is to ensure that all non-faulty nodes in a distributed system agree on the same value, even in the presence of faulty or malicious (Byzantine) behavior. This task is tightly related to other well studied distributed agreement tasks such as Broadcast, and Committee or Leader Election. All of the above are fundamental to many distributed systems, such as blockchain protocols (e.g., Algorand [, ]) and secure multiparty computation (MPC) protocols [–]. There are many natural efficiency metrics for agreement protocols, including rounds, communication, computation, and load balance. In this work we focus on two classical ones: the number of rounds of communication required to reach agreement, and the number of bits sent by each party. Optimizing these two metrics is the subject of a rich line of active research. Due to the need to support large numbers of parties, scalability has become an important goal. Ideally, we want to design protocols where the number of rounds and the per-party communication grow (much) slower than the number of parties. In this work, we consider the synchronous communication model and assume point-to-point channels. We further consider adversaries that corrupt parties statically (after the protocol is specified but before the protocol’s execution starts). Our main result is the first protocol with polylog(n) rounds and poly(λ,logn) bits of communication per party, based on standard falsifiable cryptographic assumptions; throughout, we do not attempt to optimize the precise degree of the polylogarithmic factors. Theorem 1 (Scalable Agreement from LWE) Assume a public-key infrastructure (PKI), a common reference string (CRS), and the hardness of the Learning With Errors problem (LWE). Then, there are n-party protocols for Byzantine agreement, broadcast, and committee or leader election, where each of these protocols is secure against a probabilistic polynomial-time adversary that statically corrupts up to 1/3-ε fraction of parties for any constant ε>0. Furthermore, each of these protocols terminates within poly(logn) rounds and each party sends poly(λ,logn) bits overall, where λ∈N is a computational security parameter. Our construction, in fact, is obtained using generic usage of a multi-hop non-interactive batch argument (BARG) system for NP. Such BARGs were recently constructed assuming LWE and in the CRS model by [, ]. Therefore, any construction of a multi-hop BARG from other assumptions, say group-based, will immediately imply the above result under the other assumptions. (We will explain what BARGs and multi-hop BARGs are below, in Sect. ). Putting the result in context: For convenience, throughout the paper, we use the notation O~(·),Ω~(·) to hide poly-logarithmic factors in n, and O~λ(·) to additionally hide polynomial factors in λ, the computational security parameter. That is, poly(logn)≡O~(1) and poly(λ,logn)≡poly(λ,logn). With information theoretic security, the state of the art protocol (in terms of per-party communication complexity) is due to King et al. [, ]. They obtained an O~(1)-round protocol where each party communicates O~(n) bits overall (tolerating 1/3-ε corruptions). Prior works (e.g., [, , –]) all had quadratic total communication. Other works that came around the same time or after [, ], for example [–], have total quasi-linear communication but they are unbalanced; i.e., few (poly-logarithmically many) parties need to communicate with everyone. A recent work [] gave a computationally-efficient variant of the state of the art protocol of [, ]. In another recent work [], a generic transformation was shown from protocols with worst-case (pessimistic) guarantees to protocols that have optimal guarantees in an honest (optimistic) execution (and same pessimistic guarantees in the worst case). In terms of lower bounds, few barriers are known. Holtby, Kapron, and King [] showed that in a large class of Byzantine agreement protocols there is at least one honest party that must send Ω~(n1/3) messages. Gelles and Komargodski [] showed that in the same class of Byzantine agreement protocols, there is at least one honest party that must send or process Ω~(n1/2) messages. Allowing cryptography and trusted setup assumptions (that invalidate both of the above-mentioned lower bounds), Boyle, Cohen, and Goel [, ] achieve a protocol with essentially best-possible communication: O~(1) rounds and per-party poly(λ,logn) bits of communication overall. To do this they introduce a new cryptographic primitive, which they call succinctly reconstructed distributed signatures (SRDS), and show that it suffices for distributed agreement. The authors then instantiate SRDS using a PKI and a strong form of succinct non-interactive arguments of knowledge (SNARKs), which are known not to be constructible based on falsifiable assumptions [, ]. The authors also give a construction of SRDS using falsifiable assumptions, but in order to achieve this, they modify the PKI model to be much stronger and less meaningful in the context of BA. Specifically, they assume that a single trusted party generates every key pair, where it provides valid secret keys only to a small randomly and secretly chosen subset of the parties; this PKI model can be referred to as a “centrally-generated PKI.” The construction of [, ] in the centrally-generated PKI model has the trusted party choose a secret, global committee, and programs knowledge of this committee into each member’s secret key. Thus, their construction can be seen as a way to bootstrap a single BA output (i.e., the choice of a global committee) in this model to achieve more BA outputs. It is unclear, however, what this result means in the context of actually achieving a BA protocol from scratch, since as explained before, it is assumed that a trusted party programs the output of a BA protocol into the trusted setup. Note that this is very different from the standard definition of PKI, where each party publishes a public key that it is allowed to choose arbitrarily. The authors of [, ] pose the existence of an efficient BA protocol from falsifiable assumptions and in the non-trusted PKI model as the main open question in this line of work. In Theorem we answer this question in the affirmative, obtaining the same efficiency properties of the resulting protocol as [, ] (in the non-trusted PKI model) except that we rely on the standard LWE assumption instead of (strong variants of) SNARKs. Notably, LWE is both falsifiable and believed to be quantum-secure, which has made it an attractive and widely-used assumption. This gives the first agreement protocols with O~(1) rounds and poly(λ,logn) per-party communication relying on standard falsifiable assumptions. Notably, we do not achieve our result by following their template of instantiating SRDSs using LWE; in fact, this is still an open problem. Instead, we suggest a completely different framework for achieving scalable agreement protocols utilizing the power of quorums and multi-hop aggregate signatures. Our approach is arguably much simpler and more direct. We stress that unlike the “centrally-generated PKI model,” our protocol does not require the public-key infrastructure to guarantee any sort of agreement. Namely, our protocol is a secure BA protocol even if a malicious party sends inconsistent public keys to different other parties. We give a detailed overview of our ideas in Sect. . On the corruption threshold: In the classical synchronous model with oral messages (no cryptography), Byzantine agreement is possible if and only if fewer than one third of the parties are corrupted [, ]. With cryptographic assumptions and authenticated channels, agreement protocols can in general tolerate a minority of corruptions (i.e., t|N|/2. - For each node in the tree, each node member from K knows the members of its neighboring nodes (parent and children). Note that in the above two properties we do not require anything for parties in H\K and so it is convenient to think of them as behaving adversarially. If we manage to generate such a tree with K=H, then we are essentially done. The supreme committee members (i.e., the O~(1) parties associated with the root node) can perform any polynomial complexity protocol to compute Byzantine Agreement, or Committee/Leader Election, and distribute the result to all the parties using the tree. Indeed, since any honest party has a direct (and short) path to the root, involving only nodes with an honest majority, it is guaranteed that it will learn the right value. The main challenge is therefore to come up with such a communication tree. Prior work: using the almost everywhere communication tree: Already in the original work of [], a communication tree as above was constructed. However, instead of achieving it with respect to K=H, they achieved it with respect to some K′⊂H, where |H\K′|∈Θ(n/logn). This is also why they achieved only almost everywhere agreement rather than everywhere agreement. Boyle et al. [, ] worked directly with the tree of [] and came up with a new primitive that suffices to make sure that the adversary can neither prevent an honest party from learning the right output or cause it to accept a wrong value. This new primitive is called succinctly reconstructed distributed signatures (SRDS), and allows the parties to aggregate cryptographic signatures along a tree. SRDS have a “robust threshold” property: if enough (say 2/3+ε) of the nodes are honest and agree to sign, then even if some internal nodes of the tree are malicious, these malicious nodes cannot prevent a signature from being generated. On the other hand, if few enough (say 1/3-ε) nodes agree to sign, then the malicious nodes cannot produce a signature. The authors of [, ] give two instantiations of SRDS. The first is using a PKI and a strong form of (recursively composable) succinct non-interactive arguments of knowledge (SNARKs). Specifically, since the communication tree is of logarithmic depth they eventually need to perform recursive composition log-many times. Thus, to bound the complexity of the knowledge extractor by a fixed polynomial, they need to assume that a single extraction has only constant multiplicative overhead. The second instantiation only requires one-way functions as a cryptographic assumption, but works in the much stronger and less standard centrally-generated PKI model, where it is assumed that a central, trusted party generates all key pairs. Crucially, such a setup essentially allows to secretly choose and identify a random committee, almost solving the problem we want to solve in the first place. (Multi-hop) BARGs to the rescue? We want to work in the standard PKI model, and to also eliminate the need for SNARKs. A natural attempt is to try to use the exciting recent line of work on BARGs. Recall that a non-interactive batch arguments (BARG) [, ], given an NP-language, is an argument system that allows an efficient prover to compute a non-interactive and publicly verifiable “batch proof” of the conjunction of k NP instances, with size much smaller than the combined witness length. If any of the k instances is false, then no polynomial-time cheating prover must be able to produce an accepting proof. The multi-hop variant [] allows to compose proofs, enabling mutually distrustful parties to perform distributed computations in a verifiable manner. See Sect. for the precise definition. BARGs are nowadays known from multiple assumptions like LWE [, ], bilinear maps [–], decisional Diffie-Hellman (DDH) and quadratic residuosity [, ], or obfuscation [], and the multi-hop variant in particular is known from LWE [, ]. Unfortunately, the specific structure of BARGs makes it clear that naively replacing SNARKs with (multi-hop) BARGs in the protocol template of [, ] does not work. At a high level, [, ]’s certification mechanism consists of a tree of SNARKs, where each non-leaf SNARK has a “running count” of how many valid signatures are present in the corresponding subtree. So a particular node n will have left and right children (cl,πl) and (cr,πr), where cl and cr are counts of the signatures, and πl and πr are SNARKs which attest to those signatures (or are signatures themselves, if l and r are leaf nodes). Upon seeing these values, node n will set cn=cl+cr, and generate πn that attests that it saw proofs for its child nodes, and that they sum up to cn . Multi-hop BARGs also allow aggregation of proofs in a tree, but they do not allow this summing-of-counts logic in the internal nodes. With BARGs, the leaves of the tree correspond to NP statements, and the only allowed logic is “all-or-nothing”: either all statements are true, and the root-node proof can be generated attesting to this, or if any statement is not true, then the aggregation fails. Our approach: To alleviate this problem, we completely deviate from the above template and construct a new communication tree which still satisfies the above properties for K′⊂H but we additionally have the following important guarantee: All internal (non-leaf) nodes have a majority of parties from H . Why does this suffice? Each internal node in the tree will collect signatures on the candidate string from its members. Because each internal node has an honest majority from K′, we are guaranteed that the right candidate string will form a majority. Now (because all internal nodes are “honest virtual nodes”), we can use multi-hop BARGs to aggregate the validity of the signatures along the tree. Once all lower level nodes hold an aggregate signature they can send it to their associate parties. The latter are then convinced that this value was held by more than 1/2 of the parties and so it must be correct. How do we achieve it? One can utilize the communication tree of [] in the following way: ask the members of the supreme committee to jointly sample a succinct representation of a new random tree. Say, this can be done by sampling (at the root node) a key for a pseudo-random function (PRF), disseminating it to everyone (along the tree), and locally expanding it to get a new (pseudo-random) new tree. Intuitively, this should satisfy the property that all internal nodes have an honest majority. To see why, recall that at most a 1/3-ε fraction of the parties are corrupted. If the members of each internal node were a freshly sampled random subset of parties (of poly-logarithmic size), then, by a Chernoff bound, the fraction of corrupted parties in that node would be close to the global fraction, and in particular below 1/2, except with negligible probability. Taking a union bound over the (polynomially many) internal nodes, all of them would have an honest majority with all but negligible probability. So obtaining a random tree from a freshly sampled seed suffices. The above idea almost works. The only problem is that there might exist some “bad” PRF key, which we call a terrible key, where the whole tree generated by this key consists of dishonest-majority nodes. To see why a terrible key is a problem, recall how our aggregation works: each internal node holds a statement asserting that a majority of its members signed the candidate seed, and the BARG aggregates these statements along the tree. Soundness of the BARG only guarantees that the aggregate proof cannot be forged as long as at least one node along the way has an honest majority (so that the adversary cannot produce a valid witness for that node). If, however, a terrible key exists, then every node is dishonest-majority, so the adversary can choose this key and, generate a BARG-based signature which is signed by all nodes in the tree (since they are all majority-dishonest), and present this to any of the honest parties in H\K′. Concretely, the corrupt majority in each node can honestly generate a valid witness for that node, and hence a valid aggregate proof for a wrong seed. Any such party in H\K′ will have no way of distinguishing this malicious signature from the honest signature of the true agreed-upon value (recall that a party in H\K′ does not necessarily know the true seed). Thus, this scenario allows the adversary to prevent full agreement. We need some way to prevent generating such a “terrible” tree, i.e., we need to guarantee that, in every possible choice of a tree (equivalently, of a seed), there must be at least one node that has an honest majority. We achieve this property by using a particular method for getting the tree. Instead of choosing it (pseudo-) randomly, we choose only one committee at random. We then “shift” this committee’s members in a particular way so that we are guaranteed that (1) w.h.p all committees consist of an honest majority and (2) for every choice of the initial committee, there must be at least one committee that has an honest majority. The second property is what rules out terrible trees, and it holds deterministically (for every seed) rather than only with high probability. The reason is a simple counting (pigeonhole) argument: concretely, we sample a single committee of size d and define the n committees to be its n cyclic shifts. In this construction every party appears in exactly d committees, so the total number of honest “slots” across all n committees is exactly d·|H|. By averaging, some committee must contain at least d·|H|/n honest members; when |H|>n/2 this is a strict majority. Thus no choice of seed can make all committees dishonest-majority. See details in Sect. . The idea of using shifts is somewhat similar to a recent idea due to [], however, the setting is a bit different and we end up needing new properties. Specifically, in [], the idea of using shifts was applied to a seed that was sampled differently, and further they use this idea for a different purpose than to generate a tree. In particular, the “no terrible tree” analysis, and in general the entire portion of our work which concerns the communication tree, is novel to this work. Model and preliminaries Notation For any distribution X, we denote by x←X the process of sampling a value x from the distribution X. For a set X we denote by x←X the process of sampling x from the uniform distribution over X. For an integer n∈N we denote by [n] the set {1,..,n}. A function negl:N→R is negligible if for every constant c>0 there exists an integer Nc such that negl(λ)<λ-c for all λ>Nc. Throughout this paper, honest parties are modeled as uniform probabilistic polynomial-time (PPT) machines, whereas the adversary (as well as the security reductions and extractors we build) is allowed to be non-uniform PPT. We will use λ to denote the computational security parameter. We will use PPT as an acronym for “probabilistic polynomial-time”. We write 1P for the indicator of a predicate P, i.e., 1P=1 if P holds and 1P=0 otherwise. Model We consider n parties in a fully connected network (i.e., clique). Each party has a unique ID and the IDs are common knowledge. We assume the IDs are 1,...,n. Parties are uniform and efficient algorithms, i.e., they can be represented as Turing machines that run in polynomial time in the (common) security parameter given in unary representation. Parties can perform arbitrary computation and they have a (private) source of randomness. Communication is private and authenticated, that is, whenever a party sends a message directly to another, the identity of the sender is known to the recipient and moreover the content of the message is hidden from the adversary. We assume synchronous communication. That is, communication proceeds in rounds; messages are all sent out at the same time at the start of the round, and then received at the same time at the end of the same round. We assume that there is a PPT adversary that controls up to t parties and whose goal is to cause the protocol to fail in some way, depending on the context. The adversary is allowed to be non-uniform PPT (while the honest parties need only be uniform). The adversary chooses which parties to control non-adaptively, i.e., it chooses the set of corrupted parties at the start of the protocol. The adversary is malicious: corrupted parties can engage in any kind of deviations from the protocol and send arbitrary messages in the name of the corrupted parties. We emphasize that corrupted parties can send arbitrarily long messages to arbitrary other parties. We assume that the adversary is rushing, that is, it can view all messages sent by the honest parties in a round before the corrupted parties send their messages in the same round. We further consider protocols in the PKI model, where each party i∈[n] samples for itself a secret key ski and a public verification key vki from some distribution. The adversary can replace the vk’s of corrupted parties arbitrarily and even send inconsistent public keys to different parties. We further assume a common reference string (CRS) which is sampled once at the beginning of time by a trusted party (alternatively, one can think of the CRS as being non-uniformly hardwired into the protocol’s description). The CRS is known to all parties as well as to the adversary. We emphasize that the adversary chooses which parties to corrupt after seeing the CRS and after seeing all (honest) vks, but before the protocol’s execution begins. In this paper, we say that a protocol is secure if a computationally-bounded adversary cannot contradict any of its properties except with negligible probability. By this, we mean that the probability of the adversary succeeding should be bounded by negl(n)+negl(λ), where n is the number of parties, and λ is a security parameter which is used to instantiate the cryptographic primitives used in the protocol. For this to be meaningful, we can either assume that λ and n are polynomially related (i.e., n is upper-bounded by an unspecified polynomial p(·) in terms of λ), and rely on polynomial-hardness assumptions, or we can rely on sub-exponential hardness assumptions and relax this relation, saying that n can go up to 2Θ(1). We stress that even in the polynomial-hardness regime, none of the constructions in this paper require knowing or specifying the bounding polynomial p upfront in order to work. Definition of byzantine agreement and friends Byzantine agreement: In this problem, there are n parties, P1,...,Pn. At most t of the parties may be corrupted. Each party Pi begins with an input bit xi∈{0,1} and outputs a bit yi. The goal of the protocol is (with high probability) for all honest parties to terminate and, upon termination, agree on a bit held by at least one honest party at the start. This should hold even when the t corrupted parties collude and actively try to prevent it. More precisely, the Byzantine agreement problem is defined as a protocol that satisfies with high probability the following agreement, validity, and termination properties: - Agreement: For every pair of honest parties Pi and Pj it holds that yi=yj. - Validity: If there exists a bit x such that for every honest party Pi it holds that xi=x, then the common output is x. - Termination: Every honest party eventually outputs a bit. Committee election and broadcast: We now state the analogous definitions for broadcast, committee election, and leader election. As before, all properties are only required to hold with high probability, and only for honest parties. In broadcast, there is a designated sender S who holds an input message m, and each party outputs a message. The following are required: - Agreement: All honest parties output the same message. - Validity: If the sender S is honest, then all honest parties output m. - Termination: Every honest party eventually outputs a message. In committee election, the parties agree on a subset (committee) C⊆[n] of a prescribed size s. Denoting by B the set of corrupted parties, the following are required: - Agreement: All honest parties output the same committee C. - Quality: The fraction of corrupted parties in the elected committee is close to their global fraction; that is, |C∩B|/|C|≤|B|/n+o(1). - Termination: Every honest party eventually outputs a committee. Here we think of the committee size s as small (e.g., poly-logarithmic in n), so that a “good” committee can subsequently run a heavier protocol among its members. In leader election, the parties agree on a single party (the leader), i.e., committee election with s=1, and the requirements are: - Agreement: All honest parties output the same leader. - Validity: The elected leader is honest with at least some constant probability (over the randomness of the protocol). - Termination: Every honest party eventually outputs a leader. Quorum to byzantine agreement, broadcast, and committee election It is not at all obvious if one can translate a protocol for one of the above tasks into another one while preserving scalability. One naive idea is to choose a small committee and let it do most of the work. That is, elect a small committee and run a “heavy-weight” protocol among the committee members for task X, where X could be (for instance) leader election, Byzantine agreement, or broadcast. If the committee is sufficiently small, then we can afford to execute rather inefficient protocols among the committee members. The problem with this approach is that it results with highly unbalanced protocols: members would need to communicate with all other parties. There is a useful abstraction called a quorum that does imply all of the above applications as a special case. A quorum is a collection of n committees where (1) each committee contains roughly the same fraction of bad parties as in the total population, (2) Each party is a member in roughly the same number of committees. Once we have a quorum, it is relatively easy to obtain all other above-mentioned abstractions with essentially no extra complexity (as noted in []). For completeness, we sketch the details next. The following lemma formalizes this reduction; we give the intuition first and then a concise proof. Consider the Byzantine agreement problem first. Given a quorum, each party sends its bit to its associated committee members. The committees now perform agreement in a tree-like fashion by say computing the majority value of their input bits. Lastly, all committees distribute the agreed upon bit to their respective associated parties. Broadcast is implemented in a similar fashion by performing broadcast in a tree-like fashion between the committees defined via the quorum (again, since these committees are behaving honestly, this is easy). Committee election is a special case of quorum (the first committee in the quorum is a good committee). Leader election can be implemented by running a naive (heavy-weight) protocol among a chosen committee. We formalize the above as follows. Below, by a good quorum we mean a collection of n committees, each of poly-logarithmic size, in which every committee has an honest majority and every party belongs to only poly-logarithmically many committees (this is exactly the notion made precise in Definition and Sect. ). Lemma 1 (Quorum to agreement tasks) Suppose all honest parties hold (agree on) a good quorum of n committees, each of size d∈O~(1), such that every committee has an honest majority and every party belongs to at most O~(1) committees. Then there are protocols for Byzantine agreement, broadcast, and committee or leader election that terminate within O~(1) rounds in which each party sends poly(λ,logn) bits overall. Proof sketch Fix a good quorum and associate its n committees with the nodes of a fixed complete binary tree of depth O(logn) (say, committee Ci with the i-th node). Since every committee has an honest majority, each committee can reliably compute a majority function of its inputs and reliably relay messages to neighboring committees (a corrupted minority cannot change the majority value). For Byzantine agreement, each party Pi sends its input bit to the members of its associated committee; committees then aggregate up the tree by (honest-majority) majority vote, the root committee fixes the agreed bit, and the value is propagated back down the tree and finally to the associated parties. Agreement and validity follow because every committee along every path faithfully computes and forwards the majority, and termination follows since the tree has depth O(logn). Broadcast is identical except that the sender first sends its message to its committee (validity for an honest sender follows as its message reaches the root unaltered). Committee election is immediate, as (say) the first committee of the quorum is itself a good committee of the required quality. Leader election is obtained by electing a good committee as above and then running a heavy-weight (polynomial) leader-election protocol among its O~(1) members. For the complexity, each committee has d∈O~(1) members, each party belongs to O~(1) committees, the tree has depth O(logn)⊆O~(1), and each message is a bit or a poly(λ,logn)-size object; hence each party sends poly(λ,logn) bits over O~(1) rounds. □ Cryptographic building blocks Learning with Errors: The learning with errors (LWE) problem, introduced by Regev [] and denoted LWEn,m,q,χ for parameters n,m,q∈N and for a distribution χ supported over Z, is to distinguish between the following pair of distributions where A←Zqn×m, s→←Zq1×n,e→←χ1×m, and u→←Zq1×m. The LWEn,m,q,χ assumption states that the two distributions are computationally indistinguishable. Informally, it asks to tell noisy linear equations over Zq apart from uniformly random ones. In this paper, we rely on multi-hop BARGs for NP (to be defined in Sect. , below) in a generic manner, that in turn, can be constructed based on LWE. Since we rely on a standard polynomially-hard version of BARGs, we need a standard version of LWE with polynomial ratio between modulus and noise. Digital signatures A digital signature allows one party to “convince” another party that a third party indeed “approved” a given message. The notion that suffices for this paper is that of existential unforgeability, where it is required to be computationally infeasible to generate a valid message-signature pair even after seeing as many such pairs for different messages as needed. We first describe the syntax and then formalize the security notion via a game between a challenger and an adversary. A signature scheme consists of three polynomial-time procedures S=(Gen,Sign,Verify) with the following syntax: - Gen(1λ)→vk,sk: given security parameter 1λ, the procedure outputs a verification key vk and signing key sk pair. - Sign(sk,m)→σ: given signing key sk and a message m, the procedure outputs a signature σ. - Verify(vk,m,σ)→{0,1}: given verification key vk, message m, and a signature σ, the procedure outputs 0 (for “fail”) or 1 (for “success”). Correctness: A signature scheme should satisfy that honestly generated signatures verification always succeed. That is, for all λ∈N, vk,sk←Gen(1λ), and m∈{0,1}∗, it holds that PKI existential unforgeability: We require that for any PPT adversary A, there is a negligible function negl(·) such that the probability to win the unforgeability game is at most negl(λ). That is, where the game ExUnfgS,A(λ) is defined as: - A(1λ) specifies an integer k by writing it in unary. - Initialize M=∅ and run {(vki,ski)←Gen(1λ)}i∈[k]. Send {vki}i∈[k] to A. - A chooses a set C⊆[k] and gets back {ski}i∈C. - A gets access to a signing oracle that gets as input pairs of the form (i, m) for i∈[k]\C and returns σi,m=Sign(ski,m). A makes as many queries as it wants (adaptively), and upon every such query, the experiment updates M=M∪{(i,m)}. When A queries (⊥,⊥), the experiment proceeds to the next step. - A outputs (i∗,m∗,σ∗) and the experiment outputs 1 (i.e., adversary wins) if (1) i∗ is not among the set of corrupted keys C, (2) (i∗,m∗) does not belong to the list of queries M, and (3) the signature σ∗ is a valid signature of m∗ with respect to vki∗. That is, i∗∈[k]\C∧(i∗,m∗)∉M∧Verify(vki∗,m∗,σ∗). Remark 1 (Equivalence to standard existential unforgeability) The standard definition of existential unforgeability of signatures is a special case of the above where k=1 and C=∅. By a standard “guessing” argument the two notions are existentially equivalent. That is, to translate an attacker of the above definition to an attacker in the “single-key” variant, we can embed the challenge vk into the list of vk at a random index. If this index ends up being corrupted (i.e., in C), the game aborts. Otherwise, the game proceeds normally. A successful attack to the PKI existential unforgeability game will translate into a successful attack in the single-key existential unforgeability game with probability smaller by 1/n factor. The above definition of digital signatures is standard and satisfied by many known constructions. For instance, the one-way function-based construction satisfies it [, ] (which then implies an LWE-based construction, directly). Multi-Hop BARGs for NP Let R(·,·) be an NP relation, and let x1,⋯,xn be n public statements. A BARG scheme stands for publicly verifiable non-interactive argument system for batch-NP. Such a scheme allows a prover to prove that it knows n witnesses such that for all i∈[n],R(xi,wi)=1, using total communication o(n). A multi-hop BARG scheme extends this notion to a distribute system where there are n provers, each one holding a different witness. A multi-hop BARG allows the provers to jointly and aggregate a proof that they know n witnesses using o(n) communication for each prover. In two concurrent recent works [, ], a multi-hop BARG was given. We give the definition of multi-hop BARG from [], except that we simplify it slightly by fixing the aggregation pattern to be in a full binary tree-like manner. Definition 1 (Multi-hop BARG scheme with fixed aggregation pattern) Let R(·,·) be a NP-relation and let λ,n∈N be two parameters. Let X=(x1,⋯,xn) be n public statements, and let the aggregation pattern be the full binary tree with n labeled nodes (denoted T). A multi-hop BARG scheme with fixed aggregation pattern for R consists of the following (randomized) polynomial time algorithms: - Gen(1λ,i∗)→crs,td. The setup algorithm receives as input the security parameter λ, and an index of statement i∗. It returns the crs (common reference string) and trapdoor td. - P(crs,x,w)→π/⊥. The proof generation algorithm receives the common reference string crs, an instance x, and a potential witness w. If R(x,w)=1, it outputs a proof π; otherwise, it returns ⊥. - AggProve(crs,X,i,πi,πL,πR)→π. The aggregation algorithm receives as input the n instances X, an index i in the aggregation tree, the proof πi associated with the ith instance xi, and the aggregated proofs πL and πR of the left and right subtrees of index i, respectively. It returns an aggregated proof π associated with the subtree of index i. - V(crs,X,i,π)→{0,1}. The verification algorithm gets as input the n instances X, an index i, and a proof π. It returns 1 if π is valid proof for the aggregated statements with respect to the subtree; otherwise, it returns 0. The scheme need to satisfy the following: - Efficiency: The size of crs,td is at most poly(λ,logn), and the size of a (combined) proof corresponding to T is at most maxi∈[n]|wi|+poly(λ,logn). - Correctness: For any crs,td←Gen(1λ,i∗), and for any X and valid witnesses:For every leaf j of T: V(crs,X,j,P(crs,xj,wj))=1.For every internal node k∈[n] the following holds. Let kL and kR be k’s left and right children, respectively. Assume that πL and πR are proofs associated with kL and kR such that V(crs,X,kL,πL)=1 and V(crs,X,kR,πR)=1. Then, V(crs,X,k,AggProve×(crs,X,k,P(crs,xk,wk),πL,πR))=1. - For every leaf j of T: V(crs,X,j,P(crs,xj,wj))=1. - For every internal node k∈[n] the following holds. Let kL and kR be k’s left and right children, respectively. Assume that πL and πR are proofs associated with kL and kR such that V(crs,X,kL,πL)=1 and V(crs,X,kR,πR)=1. Then, V(crs,X,k,AggProve×(crs,X,k,P(crs,xk,wk),πL,πR))=1. - Index hiding: For any PPT adversary A, and any i,j∈[n]: Prcrs←Gen(1λ,i)[A(crs,i,j)=i]-Prcrs←Gen(1λ,j)[A(crs,i,j)=i]≤negl(λ). - Somewhere argument of knowledge: There exists a PPT extractor E, such that for any PPT adversary A: [446_2026_519_Equ17_HTML.gif] Theorem 2 (Theorem 1.3 in []) Assume hardness of LWE against non-uniform polynomial-time attackers. A multi-hop BARG for all NP satisfying Definition exists. Above, we assume that n, the number of instances in the batch, and λ, the computational security parameter, are polynomially related. One can support even n that grows sub-exponentially with λ (or, alternatively, λ that is only poly-logarithmic in n) if we assume sub-exponential hardness of LWE. Our agreement protocol is eventually proven secure by a reduction to the security of the multi-hop BARG and an underlying signature scheme. We have stated the existence of multi-hop BARGs from LWE because this is the way that [, ] state it. However, the latter works actually show a generic construction of multi-hop BARGs from two primitives (1) somewhere-extractable hash functions (SEH) [, ], and (2) standard batch arguments (i.e., not necessarily multi-hop). These were first constructed from LWE [, ], and more recently using other assumptions (e.g., DLIN or subexponentially-hard DDH) []. By relying on these results (and noting that signatures exist too under these assumptions), we can get our results also from those assumptions. Lastly, we mention that our protocols only require multi-hop BARG that supports logarithmically-many hopes. Quorum agreement protocol In this section we provide a scalable protocol used to agree on a “good” quorum. Recall that a quorum is a collection of n committees C1,...,Cn∈[n]d (i.e., size d subsets of parties). In our context, each committee will be of size d=log2n and a quorum is good if the following conditions hold. Denote by B the set of parties the adversary controls, and recall that |B|≤(1/3-ε)n for ε>0. - For each i∈[n], |Ci\B|>d/2. That is, there is an honest majority in each committee. - For each j∈[n], ∑i∈[n]|Ci∩{j}|∈Θ(d). That is, each party appears in about d committees (in fact, our construction places every party in exactly d committees). The protocol that we describe in this section results with a good quorum as described above, and does so using only poly(λ,logn) per-party communication and O~(1) rounds. All of our protocols succeed with very high probability, i.e., all but negligible probability of error in the security parameter and in n. Theorem 3 Assume a PKI, a CRS, and the hardness of LWE. Then, there is a protocol for generating a good quorum (with probability at least 1-negl(n)), secure against a PPT adversary that statically corrupts up to 1/3-ε fraction of parties for any constant ε>0. Furthermore, the protocol terminates within O~(1) rounds and each party sends poly(λ,logn) bits overall. As immediate corollaries, we obtain protocols for classical agreement tasks such as byzantine agreement, broadcast, and committee or leader election. The construction that achieves this transformation is immediate and is described in Sect. . Theorem 4 (Restatement of Theorem ) Assume a PKI, a CRS, and the hardness of LWE. Then, there are protocols for byzantine agreement, broadcast, and committee or leader election, secure against a PPT adversary that statically corrupts up to 1/3-ε fraction of parties for any constant ε>0. Furthermore, these protocols terminate within O~(1) rounds and each party sends poly(λ,logn) bits overall. Section organization: In Sect. we present a protocol that makes almost all parties agree on a random string. That is, at the end of this phase, each party i holds a string seedi. For all but o(1) fraction of parties, there is a string seed such that all seedi’s are equal to it. The o(n) parties that do not hold seed are called unknowledgeable. There is no guarantee on the seedi of the unknowledgeable parties. Furthermore, seed is distributed uniformly from {0,1}log3n. It is not guaranteed that a party knows whether it is knowledgeable or not. Then, in Sect. we show that the output of the previous protocol can be used to sample from a strong family of good quorums. That is, we construct a family of good quorums with additional properties that are crucial for the next step in our protocol. Lastly, in Sect. we preset the full protocol that causes all parties to agree on seed and thereby implies a good quorum. Almost everywhere agreement on a seed Recall that []’s protocol establishes a O(logn)-degree communication tree (which is essentially a sparse overlay network) in which each node is assigned with a committee of O~(1) parties. The guarantees are that the O~(1)-size root committee has a 2/3 honest majority and almost all of the parties are connected to the supreme committee via the communication tree. Denote root the root committee. We note that this building block was recently revisited by Bhangale, Liu-Zhang, Loss, Nayak, and Yandamuri [], who observed that the analysis of [] is incomplete: the “silencing” mechanism (used to keep communication low) interacts poorly with sampler-induced bad elections, and the original argument does not adequately bound the number of honest parties that get silenced. They give a modified protocol that restores the intended almost-everywhere guarantees, with poly-logarithmic communication per party, for t<(1/3-ε)n. Whenever we invoke almost-everywhere agreement / the communication tree of [] as a black box, we rely on this corrected construction (rather than on the original analysis alone). Before describing the protocol, we recall the primitives that it composes. We run a standard MPC protocol among the parties of the root committee in order to sample a fresh random string seed of length log3n. Concretely, we use the BGW protocol [], which assumes pairwise private channels and a broadcast channel among the participating parties. Private channels are already part of our model (and can be implemented from a PKI), whereas the broadcast channel among the (poly-logarithmically many) root-committee members is implemented using a standard—polynomial but not necessarily scalable—broadcast protocol, such as that of Berman, Garay, and Perry []. Since BGW is executed only among the O~(1) members of the root committee, its polynomial cost translates into O~(1) cost overall. AlmostEverywhereAgreementOnASeed_: - All the parties run the protocol of [] (as corrected by []) to generate the communication tree. - Each party i∈root samples seedi←{0,1}log3n. The parties in the root committee run the BGW MPC protocol [] to compute seed←⨁i∈rootseedi (the required broadcast channel is realized via [], as discussed above). - The root committee distributes seed to the leaves using the communication tree from step 1. - Each leaf node Ni sends seed to party Pi, who stores the value it received most often. Theorem 5 For any PPT adversary A that statically corrupts up to a 1/3-ε fraction of parties, for any constant ε>0, with probability at least 1-negl(n)-negl(λ), at the end of the protocol, a 1-o(1) fraction of honest parties agree on a uniform string seed∈{0,1}log3n. In addition, the protocol terminates after O~(1) rounds, and each party sends poly(λ,logn) bits overall. We prove Theorem by direct composition of the results of [, , , ]. We first recall the two building blocks that we compose, and then give the proof. We use BGW to obtain a coin-flipping protocol. Below we state a weak version of the result of [] that suffices for us. Here, security means that the protocol computes the prescribed function even against a malicious adversary who controls the corrupted parties; in particular, the adversary is allowed to choose the inputs of the corrupted parties. Theorem 6 ([]) Given private channels between each pair of parties and a broadcast channel, for every n-ary polynomially-computable function f, and for any (computationalally unbounded) adversary A that statically corrupts at most n/3-1 parties, there exists a protocol that terminates after poly(n,|f|) rounds, and in which each party sends poly(n,|f|) bits. At the end, each party holds f(x1,⋯,xn), where x1,⋯,xn are the parties’ inputs. In particular, taking f to be the exclusive-or (XOR) of one-bit inputs yields a coin-flipping protocol for a single unbiased bit, as long as at least one participating party is honest. Running this bit-by-bit (equivalently, computing a single multi-bit XOR over GF(2)) yields the following corollary. Corollary 1 (Coin-flipping a bitstring) Given private channels between each pair of parties and a broadcast channel, and for any adversary that statically corrupts at most n/3-1 of the participating parties, there is a protocol that terminates after poly(n,l) rounds, in which each party sends poly(n,l) bits, at the end of which all parties hold the same string s∈{0,1}l. Moreover, if at least one participating party is honest, then s is distributed uniformly over {0,1}l. For the above theorem, recall that our model already assumes private channels, and further we can use a well-known protocol for broadcast []. We now state the result of [] (as corrected by []) that gives a communication tree. Theorem 7 ([, ]) For any (computationally unbounded) adversary A that statically corrupts a 1/3-ε fraction of parties, for any constant ε>0, there is a O~(1)-round protocol, where each party sends at most O~(1) bits during the protocol, that creates a communication tree with the following properties: - There is n leaf nodes, where each internal node has logn sons, so the tree depth is O(logn/loglogn). - Each leaf node of the tree is assigned a set of log5n processors. Each processor is assigned to O(log4n) leaf nodes. All processors know exactly which processors participate in which leaf nodes. - Each internal node of the tree is assigned a set of log3n processors. Each processor is assigned to O(log4n) internal nodes per level, and it knows the other parties that assigned to that nodes. - With probability at least 1-negl(n), at most a 3/log2n fraction of the nodes in the tree are bad (contains dishonest majority), and all but a 3/logn fraction of the leaf nodes have a good path (all node in the path are good) to the root node. - Suppose there is a good path from A to the root, and let B be the parent of A. Then all processors in A know all processors in B, and all processors in B know all processors in A. Now we are ready to prove the correctness of the combined protocol. Proof of Theorem 5 From Theorem it follows that after Step 2 each party in the root will hold seed. Since there exists at least one honest party in the root, the XOR of all these independently chosen values is uniformly random. Also, since there are log3n parties in the tree root, the end of Step 2 will be reached after O~(1) rounds and each party will send at most O~(1) bits, overall. Lastly, since there are only o(1) leaves nodes that are “bad” or have “bad” path to the root, at the end of the protocol, 1-o(1) fraction of parties will hold seed. □ Sampling a strong quorum Recall that a quorum is a collection of n committees. Roughly, a quorum is good if each committee has a fraction of corrupt parties similar to the fraction of total corrupt parties (out of n). Also, we shall require a balancedness property meaning that each party appears roughly in the same number of committees. These properties have been considered before and are not new to this work. We introduce and require a new property called no terrible quorums meaning that in every possible (adversarially chosen) quorum there is at least one “good” committee. Looking ahead, this is precisely the property that prevents the adversary from forging a BARG-based proof for a wrong seed: for any seed the adversary might try to convince honest parties of, the induced quorum contains at least one committee Ci∗ with an honest majority. Since the BARG setup embeds a random index i∗ that is hidden from the adversary (index hiding), with probability at least 1/n this good committee is exactly the one from which the somewhere-extractor extracts a witness. Extracting a valid witness for that committee would require a valid signature on the wrong seed by an honest party, contradicting unforgeability. In other words, “no terrible quorums” combined with somewhere extraction (and a pigeonhole argument over committees) is what rules out proofs for wrong seeds; see Claim and lemma . Definition 2 (Good family of quorums) A family of quorums is a family Q={Qn}n∈N. For each n∈N, each member Q∈Qn is a set of n committees Q=(C1,...,Cn)∈([n]d)n, where the size of each committee is d=log2n. Note that each Ci is a multi-set. The family Q is said to be good if - Efficient sampling: There is a deterministic polynomial-time procedure QSample(1n,seed) that gets as input n∈N and seed∈{0,1}log3n, and outputs a quorum Q∈Qn. - Good committees: For every n∈N, every H⊆[n] such that |H|>n/loglogn, with high probability over the choice of the quorum Q=(C1,...,Cn), the density of H-members in Ci is very close to their density in [n]. That is, [446_2026_519_Equ18_HTML.gif] - Balanced committees: For every n∈N, with high probability over the choice of the quorum Q=(C1,...,Cn), every party appears in O(d) committees overall. That is, [446_2026_519_Equ19_HTML.gif] - No terrible quorums: For every n∈N and every H⊆[n], for every possible choice of a quorum Q=(C1,...,Cn), there exists at least one committee Ci where the density of H-members in Ci is at least |H|/n. That is, for every seed∈{0,1}log3n such that (C1,...,Cn)=QSample(1n,seed), it holds that ∃i∈[n]:1d·∑z∈Ci1z∈H≥|H|n. Theorem 8 There is an implementation of QSample such that for every n∈N, QSample(1n,·) results with a good family of quorums as defined in Definition . Proof We define the QSample procedure as follows: QSample(1n,seed),where|seed|=log3n_: - Parse seed as d≜log2n elements in [n], denoted C∗=P1∗,...,Pd∗. - Define Ci=P1∗+i,...Pd∗+i (all arithmetic is mod(n) and the nth party is identified by 0). - Output Q=(C1,...,Cn). The efficiency property of this construction is immediate by description. We argue that we get balanced committees for every seed (i.e., with probability 1). Fix party j∈[n] and seed∈{0,1}log3n. Denote Q=(C1,...,Cn)=QSample(1n,seed) and let C∗ be as above. It holds that The fact that the resulting committees are good (with high probability) follows by an application of Chernoff’s bound along with a union bound. Specifically, fix i∈[n] and abbreviate the event of interest by By Chernoff’s bound (recall d=log2n), where the last inequality follows since |H|>n/loglogn. The second property of a good quorum now follows by a union bound over all i∈[n]. For the no terrible quorum property, observe that each party appear in exactly d committees and therefore the total number of honest parties in all quorums together is d·|H|. By the pigeonhole principle, there must be one Ci with (d·|H|)/n parties from H. □ Everywhere agreement on a quorum In this section we explain the final protocol, resulting with a good quorum known to all honest parties. At a very high level, we utilize the almost everywhere protocol from Sect. 4.1 to get a seed that is known to almost everyone. Then, we let each party expand its candidate seed to a quorum (that is agreed upon by almost everyone) using Theorem . We then use the multi-hop BARG to aggregate signatures along a tree of the quorum committees. Once the committees get an aggregated signature of all other committees they can pass on the candidate string to their associated parties. Building blocks: Our protocol utilizes the following primitives: - A signature scheme S=(Gen,Sign,Verify), as in Sect. . - A multi-hop BARG for NP BARG=(Gen,P,AggProve,V), as in Definition . The NP relation that we use is defined next. Committee signature relation: Recall that d is the size of a committee in the quorum. The NP relation we utilize in our BARGs is defined next. Definition 3 (NP relation for BARGs) We define the following NP-relation: where f:[n]×{0,1}∗×[d]→[n] is a fixed polynomial-time computable function, vk→ is a vector of fixed public verification keys, and seed is a fixed seed string. Above, we view f(i,seed,⋆) as a function that outputs a multi-set of d parties (i.e., a committee). So, the above relation classifies a valid witness for index i as one containing a majority of valid signatures on seed from the multi-set members. The QuorumAgree protocol: We now present the QuorumAgree protocol. Let T be an abstract binary tree with n nodes. Each of the nodes is virtually associated with a committee (in some arbitrary but fixed manner). Let Depth(T) be T’s depth, i.e., the number of nodes in the longest path from the root to the leaves (so roughly Depth(T)=logn). For a node j in the tree, let Parent(j) be its parent, Left(j) and Right(j) be its left and right children, respectively. Throughout the protocol description below, when we say that a committee does something (e.g., sends a message or computes a value), we mean that every party in the committee performs this operation and labels it with its identity and its view of the committee index. Importantly, since every party holds its own candidate for seed, the protocol may proceed differently for different parties. We write ← for assignment and = for equality. Efficiency Lemma 2 The QuorumAgree protocol from Sect. terminate after O~(1) rounds and each party sends poly(λ,logn) bits overall during the protocol. Proof By Theorem it is guaranteed that all parties reached the end of step 3 after O~(1) and until then where each party sent O~(1) bits. We next analyze the following steps. Rounds complexity: step 5a takes a single round, steps 5e and 5f consist of O(Depth(T))⊂O~(1) iterations, where each iteration takes a single round. Then, there is an additional round to send the aggregated proof to everyone. So, at total there are O~(1) rounds, as needed. Communication complexity: consider a single committee. At step 5a each party sends |σ|∈poly(λ,logn) bits to d∈O~(1) parties. By Theorem , during steps 5e and 5f each party sends poly(λ,logn) bits in each step, and O(Depth(T))⊂O~(1). At the last round, each party sends poly(λ,logn) bits. Finally, since each party is part of exactly d committees and d∈O~(1), it follows that during the entire protocol each party sends at most poly(λ,logn) bits, as needed. □ Security This section provides the proof of agreement for the above protocol. We show that even if an adversary controls 1/3-ε fraction of parties and behaves arbitrarily in their name, the protocol still results with each honest party agreeing on seed. We start by stating the result of our transformation from almost everywhere agreement to everywhere agreement. Note that the transformation and the almost everywhere protocol tolerate a different number of corrupted parties (1/2-ε fraction vs. 1/3-ε fraction, respectively). Thus, the combined protocol will be secure against 1/3-ε fraction of parties. (Still, we decide to state a stronger result below as it might be useful for future works.) Theorem 9 (From almost everywhere to everywhere agreement) For any PPT adversary A that statically corrupts up to 1/2-ε fraction of parties, where ε is any positive constant, if at the end of step 3 of QuorumAgree at least 1-O(log-1n) fraction of (honest) parties hold the same uniformly sampled value, denoted by seed, then with probability at least 1-negl(n)-negl(λ), at the end of the protocol all (honest) parties outputs seed. Obviously, Theorem follows from Theorem together with the almost everywhere agreement protocol from Theorem . The rest of this section is devoted to the proof of Theorem . At a high level, the proof of Theorem consists of two main claims: (1) that the adversary can’t prevent the honest parties from generating a valid proof for seed, and (2) that the adversary cannot generate valid proof for a maliciously chosen seed seed∗. Consider a PPT adversary A that statically corrupts up to a 1/2-ε fraction of parties, where ε>0. Denote by C⊆[n] the set of corrupted parties. Additionally, we assume (as written in the statement) that at the end of Step 3, at least 1-O(log-1n) fraction of (honest) parties hold the same uniformly sampled value, denoted seed. Let H={Pi∣i∈([n]\C)∧seedi=seed}, i.e., H is the set of honest parties that hold the “right” seed. The first claim (Claim below) states that if an honest party is part of committee j, then it must hold a valid witness for index j, that is, it knows a w such that R(j,w)=1. We utilize the following claim that says that every committee contains majority of honest parties that hold the right seed. The proof of this claim follows by the construction of the almost everywhere protocol that results with a uniform string which is then fed into our quorum construction. Claim 1 With probability at least 1-negl(n)-negl(λ), for all j∈[n], |H∩Cj|>|Cj|/2. Proof Recall that with probability at least 1-negl(n)-negl(λ), seed, the output of the almost everywhere agreement protocol, is sampled uniformly at random and we use it as a seed to generate a quorum (using Theorem with H=H). Thus, with probability at least (1-negl(n)-negl(λ))(1-negl(n)), for each j∈[n], □ Claim 2 At the end of Step 5a, with probability at least 1-negl(n)-negl(λ), for every i,j∈[n], if Pi∈H∩Cj, then party Pi holds {σf(j,seed,k)}k∈[log2n] such that R(j,{σf(j,seed,k)}k∈[log2n])=1 (see Definition ). Proof By description of the protocol, if Pi∈H∩Cj, then the size of the set is at least |H∩Cj|. Claim implies that |H∩Cj|>|Cj|/2 and so party Pi holds a valid witness. □ From this point on, it is convenient to assume that for all j∈[n], |Cj∩H|>|Cj|/2 (which holds w.h.p due to Claim ). In the next claim, we show that the honest parties aggregate the proof successfully. For simplicity of notation, let Xseed=([n],vk→,seed). Claim 3 Let Tj be the subtree where j is its root. After l iterations of step 5e, for each j∈[n]: - If Depth(Tj)=l+1, then State=(Send,π) and V(crs,Xseed,j,π)=1. - If Depth(Tj)l+1, then State=WaitToAggregate. Proof We prove by induction on l, the number of executed iterations of step 5e. - Base case: For l=0 and for all j∈[n], j is a leaf of T. Then, If Depth(Tj)=1: By step 5d, State=(Send,π), where π=P(crs,j,{σf(j,seed,k)}k∈[log2n]). By the correctness property of the BARG (Definition ) and by Claim , it follows that V(crs,Xseed,j,π)=1.It is impossible that Depth(Tj)<1, since for every j, Depth(Tj)≥1.If Depth(Tj)>1: By step 5d, State=WaitToAggregate. - If Depth(Tj)=1: By step 5d, State=(Send,π), where π=P(crs,j,{σf(j,seed,k)}k∈[log2n]). By the correctness property of the BARG (Definition ) and by Claim , it follows that V(crs,Xseed,j,π)=1. - It is impossible that Depth(Tj)<1, since for every j, Depth(Tj)≥1. - If Depth(Tj)>1: By step 5d, State=WaitToAggregate. - Inductive step: Assume that the claim is true for 0,⋯,l-1, and we prove it for l. For j∈[n]: If Depth(Tj)=l+1, then before the start of the lth iteration of step 5e, Depth(Tj)>(l-1)+1, so by the inductive assumption, State=WaitToAggregate. W.l.o.g. assume that the left child sub-tree depth is l and the right child sub-tree depth is l′≤l. Due to the inductive assumption, at the lth (resp. l′th) iteration of step 5e, the state of Left(j) (resp. Right(j)) was (Send,π), where V(crs,Xseed,Left(j) (resp. Right(j)),π)=1. So, from the protocol’s description, State=(Send,π=AggProve(crs,Xseed,j,πj,πL,πR)), such that V(crs,Xseed,j,π)=1.If Depth(Tj)l+1, by the inductive assumption, before the lth iteration of step 5e, State=WaitToAggregate. W.l.o.g. assume that the left child sub-tree depth is Depth(Tj)-1≥l+1. From the inductive assumption, it follows that the left child ends the lth iteration of step 5e in state WaitToAggregate or Send, so j has not yet updated πL. □ - If Depth(Tj)=l+1, then before the start of the lth iteration of step 5e, Depth(Tj)>(l-1)+1, so by the inductive assumption, State=WaitToAggregate. W.l.o.g. assume that the left child sub-tree depth is l and the right child sub-tree depth is l′≤l. Due to the inductive assumption, at the lth (resp. l′th) iteration of step 5e, the state of Left(j) (resp. Right(j)) was (Send,π), where V(crs,Xseed,Left(j) (resp. Right(j)),π)=1. So, from the protocol’s description, State=(Send,π=AggProve(crs,Xseed,j,πj,πL,πR)), such that V(crs,Xseed,j,π)=1. - If Depth(Tj)l+1, by the inductive assumption, before the lth iteration of step 5e, State=WaitToAggregate. W.l.o.g. assume that the left child sub-tree depth is Depth(Tj)-1≥l+1. From the inductive assumption, it follows that the left child ends the lth iteration of step 5e in state WaitToAggregate or Send, so j has not yet updated πL. □ A corollary of Claim is that the state of all nodes at the end of the iterations of step 5e is as expected. Corollary 2 After the Depth(T)-1 iterations of step 5e, the state of Root(T) is (Send,π), where V(crs,Xseed,Root(T),π)=1. Additionally, the state of all other nodes is WaitToDistribute. Now, similarly, we prove that each committee will learn the right proof attesting to the validity of seed w.r.t T. Claim 4 Let Tj be the subtree with j at its root. After the l iterations of step 5f, for each j∈[n]: - If Depth(Tj)=Depth(T)-l, then State=(Send,π), where V(crs,Xseed,Root(T),π)=1. - If Depth(Tj)Depth(T)-l, then State=(Done,π), where V(crs,Xseed,Root(T),π)=1. Proof By induction on l: - Base case: For l=0, and for all j∈[n]: If Depth(Tj)=Depth(T), then since j is the root of T, the claim follows from Corollary .If Depth(Tj)Depth(T) since for every j, Depth(Tj)≤Depth(T). - If Depth(Tj)=Depth(T), then since j is the root of T, the claim follows from Corollary . - If Depth(Tj)Depth(T) since for every j, Depth(Tj)≤Depth(T). - Inductive step: Assume that the claim is true for 0,⋯,l-1, and we will prove it for l. For j∈[n]: If Depth(Tj)=Depth(T)-l, by the inductive assumption, before the lth iteration of step 5f, the state of j is WaitToDistribute, and the state of Parent(j) is (Send,π), where V(crs,Xseed,Root(T),π)=1. Since there is at least one honest party in each committee (actually, there is an honest majority) and by description of step 5f, at the end of the lth iteration of step 5f, the state of j will be (Send,π), as needed.If Depth(Tj)Depth(T)-l there are two cases. First, if Depth(Tj)>Depth(T)-l+1, we use the inductive assumption directly. Second, if Depth(Tj)=Depth(T)-l+1, by the inductive assumption, before the lth iteration of step 5f, State=(Send,π), where V(crs,Xseed,Root(T),π)=1. Thus, by the protocol’s description, during the lth iteration of step 5f, the state changes to (Done,π). □ - If Depth(Tj)=Depth(T)-l, by the inductive assumption, before the lth iteration of step 5f, the state of j is WaitToDistribute, and the state of Parent(j) is (Send,π), where V(crs,Xseed,Root(T),π)=1. Since there is at least one honest party in each committee (actually, there is an honest majority) and by description of step 5f, at the end of the lth iteration of step 5f, the state of j will be (Send,π), as needed. - If Depth(Tj)Depth(T)-l there are two cases. First, if Depth(Tj)>Depth(T)-l+1, we use the inductive assumption directly. Second, if Depth(Tj)=Depth(T)-l+1, by the inductive assumption, before the lth iteration of step 5f, State=(Send,π), where V(crs,Xseed,Root(T),π)=1. Thus, by the protocol’s description, during the lth iteration of step 5f, the state changes to (Done,π). □ A corollary of Claim is that the state of all nodes at the end of the iterations of step 5f. is as expected. Corollary 3 After the Depth(T) iterations of step 5f the state of all nodes j∈[n] is (Done,π). Additionally, V(crs,Xseed,Root(T),π)=1. Next, we conclude that with high probability, each honest party will receive at least once the right seed along with a valid proof. Lemma 3 With probability at least 1-negl(n)-negl(λ), at step 6b, every (honest) party sets out=seed, where seed is the value that is outputted by the almost-everywhere agreement sub-protocol. Proof By Corollary , each committee’s state is (Done,π), where V(crs,Xseed,Root(T),π)=1. Together with Claim , every party receives at least once the right seed and a valid proof. Thus, after step 6b, each party will update out with seed. □ The above lemma stands for the protocol’s “correctness”. In other words, we proved that the adversary cannot prevent from any honest party from receiving the right seed along with a valid proof for it. However, we have not yet proved that the adversary cannot generate another valid proof for a wrong seed, which is also undesirable. For simplicity, assume that the adversary is given free of charge full control over unknowledgeable honest parties, i.e., parties with seedi≠seed (after step 6). Notice that this group is of size o(n), so this does not add significant power to the attacker. We show that if there exists an adversary that generates a valid proof for a maliciously chosen seed, then we can build another adversary that wins the unforgeability game of the signature scheme (Sect. ) with only slightly lower probability. Our adversary uses the BARG scheme knowledge extractor from Definition which, to recall, is an efficient procedure that receives valid proofs for some seed′ and extracts (w.h.p.) the witness associated with some committee Ci∗, where the index i∗ is supplied during setup. Claim 5 Assume a PPT adversary A′ that at step 6b of the protocol can generate a pair (seed′,π′) where seed′≠seed and Pr[V(crs,Xseed′,Root(T),π′)=1]≥p(n). Then, there is another PPT adversary A such that Pr[ExUnfgS,A(λ)=1]≥p(n)/2n, where the game ExUnfgS,A(λ) is defined in Sect. . Proof Let E be the knowledge extractor of the BARG scheme (Definition ). We build A as follows: - A chooses k=n, and receives {vki}i∈[n] from the experiment. - A samples i∗←[n] and runs (crs,td)←BARG.Gen(1λ,i∗). - A sends crs and {vki}i∈[n] to A′. - A′ chooses the set of corrupted parties C and sends C to A. A sets C as its corrupted set, receives {ski}i∈C from the experiment, and forwards it to A′. - A and A′ run together the QuorumAgree protocol up to the end of step 6b, where A simulates [n]\C. When it needs to sign a message m, the experiment signs it for him. At the end, A′ sends (seed′,π′) to A. - A sends (Xseed′,td,i∗,Root(T),π′) to E, and it answers with {σf(i∗,seed′,j)}j∈[log2n]. - For each j∗∈{f(i∗,seed′,j)}j∈[log2n], if j∗∈[n]\C and Verify(vkj∗,seed′,σj∗)=1, then A outputs (j∗,seed′,σj∗). - A outputs (⊥,⊥,⊥). To analyze the above reduction, we define the following events: - EventEAcceptProof_: V(crs,Xseed′,Root(T),π′)=1. - EventEEnoughValidSigs_: RS,f,vk→,seed′(i∗,{σf(i∗,seed′,j)}j∈[log2n])=1. (See Definition .) - EventEHonestMajority(i)_: |Ci∩([n]\C)|>log2n/2, where Ci the ith committee in the quorum QSample(n,seed′). - EventE1_: The experiment outputs 1. First, recall that every committee size is exactly log2n, independently of seed′. By the definition of RS,f,vk→,seed′ if EAcceptProof happens, then This means that Pr[EEnoughValidSigs∧EHonestMajority(i∗)∧¬E1]=0. From the “no terrible quorum” property (see Definition ), we know that Pr[∃i∈[n]:EHonestMajority(i)]=1. Since A′ is unaware of i∗, Pr[EHonestMajority(i∗)]≥1/n, and also EHonestMajority(i∗) and EAcceptProof are independent events. Next, from the claim requirement it follows that Pr[EAcceptProof]≥p(n), and from the “somewhere argument of knowledge” property of the BARG scheme we conclude that Finally, □ Next, we show how to use the above reduction to prove that the adversary cannot generate a proof for a wrong seed. Lemma 4 With probability at least 1-negl(n)-negl(λ), at step 6b, if (honest) party sets out=seed, then seed is the value that defines H (the almost everywhere agreed value). Proof Assume, by contradiction, that the claim is false. That is, with noticeable probability an honest party sets out=seed′ for some seed′≠seed. Then, by Corollary , there exists a PPT adversary A that can generate a pair (seed′,π′) such that seed′≠seed and for some noticeable function f(n), Pr[V(crs,Xseed′,Root(T),π′)=1]≥f(n). By Claim , there is another PPT adversary A′ that win the PKI unforgeability game of the signature scheme (Sect. ) with noticeable probability. This is a contradiction. □ Finally, Theorem follows by combining Lemmas and . Footnotes