Additional Related Work. Threshold signatures [43, 80, 50, 85, 10, 55] can guarantee that a sufficiently large number of parties signed the message, while keeping the signature-length (including all information needed to verify) independent of n. However, threshold signatures require the keys to be generated by a trusted party in a correlated way (e.g., as a Shamir sharing of the signing key), and the signature- reconstruction protocol of existing schemes does not offer succinct aggregation in “small” batches. SRDS imply threshold signatures by having the setup algorithm produce the PKI for the parties, and using the aggregation algorithm to reconstruct a signature. We note that Xxxxxx et al. [70] constructed fully distributed threshold signatures that do not require any setup assumptions. However, this scheme is not applicable in our setting, since it requires an interactive key-generation protocol to generate the public and secret keys, and this protocol in turn uses a broadcast channel. In fact, as indicated by our lower bound, some form of private-coin setup is inherently needed for constructing SRDS. Multi-signatures [60, 77, 10, 5, 72, 13] guarantee that a subset of parties signed the message. Unlike threshold signatures, correlated trusted setup is not needed and a bulletin-board PKI suffices; in addition, some of the constructions enable succinct aggregation in “small” batches. Aggregate signatures [12, 73, 11, 72, 69, 56] are a similar primitive that allows aggregating signatures on different messages. The main distinction of SRDS is succinctness that enables verification without knowing the signing parties. This property is crucial for our BA protocol construction. Group signatures [27] and ring signatures [84] allow any individual party to sign a message on behalf of a set while hiding their identity. This is different than our setting where we need to prove that a majority of the parties signed the message.
Additional Related Work. As mentioned earlier, the t + 1 lower bounds for deterministic BA [FL82, DS83] were extended to rule out strict-constant-round t-secure randomized BA for t = Θ(n) [CMS89, KY86, CPS19]; these bounds show that any such r-round BA must fail with probability at least (c r)−r for a constant c, a result that is matched by the protocol of [GGL22]. Xxxxx et al. [CHM+22] showed that for t > n/3, two-round BA are unlikely to reach agreement with constant probability, implying that the expected round complexity must be larger; this essentially matches Micali’s BA [Mic17] that terminates in three rounds with probability 1/3. Attiya and Censor-Hillel [AC10] extended the results on worst-case round complexity for t = Θ(n) from [CMS89, KY86] to the asynchronous setting, showing that any r-round A-BA must fail with probability 1/cr for some constant c. In the dishonest-majority setting, expected-constant-round broadcast protocols were initially studied by Xxxxx et al. [GKKO07], who established feasibility for t = n/2 + O(1) as well as a negative result. A line of work [FN09, CPS20, WXDS20, WXSD20, SLM+23] established expected- constant-round broadcast for any constant fraction of corruptions under cryptographic assumptions. Synchronous and (binary) asynchronous OCC protocols in the information-theoretic setting were discussed earlier. Using the synchronous protocol in [BE03], Xxxxxx and Xxxxx [MR90] showed how to realize a perfectly unbiased common coin in expected-constant rounds for t < n/3 over secure channels (recall that this task is impossible in asynchronous networks [dSKT22]). In the cryptographic setting, both synchronous and asynchronous OCC protocols with optimal resiliency are known, relying on various computational assumptions; we mention a few here. Beaver and So [BS93] gave two protocols tolerating t < n/2 corruptions in synchronous networks, which are secure under the quadratic residuosity assumption and the hardness of factoring, respectively. Xxxxxx et al. [CKS05] presented two protocols for t < n/3 and asynchronous networks, which are secure in the random oracle model based on the RSA and Xxxxxx-Xxxxxxx assumptions, respectively. Xxxxxxx [Nie02] showed how to eliminate the random oracle and construct an asynchronous OCC protocol relying on standard assumptions alone (RSA and DDH). Although these constructions are for asynchronous networks, they can be readily extended to work in synchronous networks for t < n/2 (i.e., so that they can be used in the c...
Additional Related Work. The literature on Byzantine agreement is vast (especially, on complete networks), and we limit ourselves to those that are most relevant to this work, mainly focusing on sparse networks. Most prior works on Byzantine protocols on sparse networks assume an underlying expander graph, where the expansion properties prove crucial in solving fundamental problems such as agreement and leader election, see, e.g., [19, 41, 30]. The protocol of [30] builds an underlying communication mechanism where messages can be relayed with only polylog (n) overhead. The issue with all the above protocols, as mentioned earlier, is that they assume that nodes have global knowledge of the network topology to begin with. Such an assumption does not work where nodes start with local knowledge of only themselves and their immediate neighbors, as is common in real-world P2P networks (including those that implement cryptocurrencies and blockchains) which are bounded degree and sparse. Xxxxxx and Xxxxx [13, 12] improved on the efficiency of Dwork et al [19]. Their main result is an algo- rithm that achieves consensus in the butterfly network using O(t +ln n ln ln n) one-bit parallel transmission steps while tolerating t = O(n/ ln n) corrupted processors and having O(t ln t) confused processors (i.e., uncorrupted processors that have decided on the incorrect bit). The number of rounds, corrupted processors that can be tolerated, and confused processors in this result are all asymptotically optimal for the butterfly network. Ben-Or and Xxx designed a bounded degree network and an almost-everywhere agreement al- gorithm that is fully polynomial and tolerates a linear number of faults with high probability if the faulty processors are randomly located throughout the network [11]. King et al. [29] describe protocols for Leader Election and Byzantine Agreement that take polylogarithmic rounds and require each processor to send and process a polylogarithmic number of bits. These protocols only run on complete networks and do not apply to sparse networks. The work of [4] presented a fully-distributed algorithm for Byzantine agreement in the presence of Byzantine nodes and high adversarial churn. The algorithm could tolerate (only) up to √n/ polylog (n) Byzantine nodes and up to √n/ polylog (n) churn per round and took a O(polylog (n)) number of rounds. The work of [5] used the Byzantine agreement protocol of [4] and designed a fully-distributed algorithm for Byzantine leader election that coul...
