PaperlayerView exact revision on arXiv

Source-linked AI summary

Reaching Consensus for Asynchronous Distributed Key Generation

Ittai Abraham, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern, Alin Tomescu

arXiv:2102.09041v3cs.DC

TL;DR

Prior optimally resilient A-DKG protocols required Ω(n) expected rounds and Ω(n^4) expected words. This paper combines a leaderless asynchronous consensus design with Proposal Election and aggregatable PVSS, achieving optimal resilience with O(1) expected rounds and ~O(n^3) expected words.

  • Problem

    The best prior A-DKG protocol with optimal resilience required Ω(n) expected rounds and Ω(n^4) expected words.

    Source: §1 · p. 1

  • Method

    The protocol uses a leaderless asynchronous consensus design with Proposal Election and aggregatable PVSS to reduce the cost of attaching secrets to parties.

    Source: §1 · p. 2, §1.2 · p. 3

  • Results

    O(1) expected rounds and ~O(n^3) expected words, with resilience against f<n/3 malicious parties, improve on the prior A-DKG protocol’s Ω(n) expected rounds and Ω(n^4) expected words.

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    The authors present the leaderless design as an improvement for DKGs suitable for Internet use and a step toward shedding asynchronous protocols’ “slow” connotation.

    Source: §1 · p. 2

    The results hold for static adversaries; adaptive security depends on an adaptively secure aggregatable PVSS, which remains an open question.

    Source: §1.2 · p. 4

Abstract

from arXiv · show

We give a protocol for Asynchronous Distributed Key Generation (A-DKG) that is optimally resilient (can withstand $f<\frac{n}{3}$ faulty parties), has a constant expected number of rounds, has $\tilde{O}(n^3)$ expected communication complexity, and assumes only the existence of a PKI. Prior to our work, the best A-DKG protocols required $\Omega(n)$ expected number of rounds, and $\Omega(n^4)$ expected communication. Our A-DKG protocol relies on several building blocks that are of independent interest. We define and design a Proposal Election (PE) protocol that allows parties to retrospectively agree on a valid proposal after enough proposals have been sent from different parties. With constant probability the elected proposal was proposed by a non-faulty party. In building our PE protocol, we design a Verifiable Gather protocol which allows parties to communicate which proposals they have and have not seen in a verifiable manner. The final building block to our A-DKG is a Validated Asynchronous Byzantine Agreement (VABA) protocol. We use our PE protocol to construct a VABA protocol that does not require leaders or an asynchronous DKG setup. Our VABA protocol can be used more generally when it is not possible to use threshold signatures.

1 INTRODUCTION

The paper improves asynchronous distributed key generation under a PKI, combining optimal resilience with constant expected rounds and lower expected communication than prior optimally resilient A-DKG. It introduces Verifiable Gather, Proposal Election, and VABA techniques to support that result.

1 INTRODUCTION

  • With f<n/3 faults, A-DKG uses O(1) expected rounds and ˜O(n^3) expected words, improving on ’s Ω(n) rounds and Ω(n^4) words.The protocol assumes a PKI and is leaderless.Source: §1 · pp. 1–2

1.1 Our Contributions:

  • The contributions include a PKI-based VABA without a DKG setup, with O(1) expected rounds and ˜O(mn^2+n^3) expected words for m-word inputs.This VABA is a key building block for the A-DKG.Source: §1.1 · p. 2
  • Proposal Election gives all parties the same value from a non-faulty proposer with constant probability, while Verifiable Gather makes verified outputs contain a common core.Proposal Election runs in O(1) rounds and ˜O(n^3) words; it is a key building block for VABA.Source: §1.1 · p. 2

1.2 Our techniques

  • Aggregatable PVSS addresses the cost of attaching many secret sharings, reducing that step to ˜O(n^3) words rather than the Ω(n^4) cost of separate VSS invocations.The cited construction uses O(n) reliable broadcasts of O(n)-sized APVSS transcripts.Source: §1.2 · p. 3
  • A weak common coin does not provide a known way to elect a valid proposal with constant probability for O(n)-bit inputs, motivating Verifiable Gather and Proposal Election.The authors describe the weak coin’s constant error as making a log n coin leader election fail with probability polynomially close to one.Source: §1.2 · p. 3
  • No Waitin’ HotStuff uses Proposal Election as a virtual leader to build leaderless VABA without a DKG, targeting ˜O(mn^2+n^3) expected words and O(1) expected rounds.The paper identifies prior validated multi-valued VABA approaches as requiring a DKG or not fitting Proposal Election’s constant error probability.Source: §1.2 · pp. 3–4

1.3 Related Work

  • The paper situates its work among asynchronous consensus and MPC protocols, noting earlier ABBA communication costs and that modern asynchronous MPC protocols use DKG.Canetti and Rabin’s constant-expected-time ABBA is reported at Ω(n^8) expected words, while Patra et al. later achieved ˜O(n^4) words.Source: §1.3 · pp. 4–5

2 DEFINITIONS AND ASSUMPTIONS

The definitions specify an asynchronous Byzantine setting and the broadcast, gathering, election, and agreement primitives used in the paper. In particular, verification constrains outputs while preserving external validity.

2.1 Network and Threat Model

  • The network has point-to-point channels with unbounded message delay but finite delivery, and protocols tolerate a Byzantine adversary controlling fewer than n/3 parties.The results use cryptographic assumptions as black boxes; adaptive security depends on adaptively secure instantiations.Source: §2.1 · p. 5

2.2 Reliable Broadcast

  • Reliable Broadcast has a designated dealer and gives parties validity, agreement, and termination guarantees; validated broadcast additionally requires every output to be externally valid.The appendix gives broadcast protocols with ˜O(n^2+mn) word complexity for m-word values.Source: §2.2 · pp. 5–6

2.3 Verifiable Gather

  • Verifiable Gather extends multi-dealer gathering with verification: parties can send index-sets, and any verified gather-set contains the binding core.Gather outputs are supersets of a shared core, but need not be identical; verification also recovers values from the verifier’s state.Source: §2.3 · pp. 6–7

2.4 Proposal Election

  • Proposal Election takes externally valid inputs and, with probability α, binds to an input from a party that behaved nonfaultily when it started; verification restricts accepted values when binding succeeds.All nonfaulty parties eventually output a proposal and proof, and verified outputs are externally valid.Source: §2.4 · pp. 7–8

2.5 Validated Asynchronous Byzantine Agreement

  • Validated Asynchronous Byzantine Agreement requires agreement, external validity, α-quality—the output is a nonfaulty party’s input with probability α—and almost-sure termination.These properties assume all nonfaulty parties start the protocol.Source: §2.5 · p. 8

2.6 Cryptographic Abstractions

The paper treats cryptographic tools as black-box abstractions, defining the properties needed for distributed key generation, threshold verifiable random functions, and vector commitments. Its vector-commitment requirement is binding, but need not include hiding.

2.6 Cryptographic Abstractions

  • The cryptographic abstractions are used as black boxes; the paper instantiates prior tools from the literature except for its A-DKG protocol.The A-DKG is defined here and constructed in Section 6.Source: §2.6 · p. 8

2.6.1 Distributed Key Generation.

  • An A-DKG requires agreement on a verified transcript and almost-sure termination when all nonfaulty parties participate.Aggregation takes at least 2f+1 shares from different parties; the text omits a reconstruction algorithm because the DKG’s purpose is a threshold application.Source: §2.6.1 · pp. 8–9

2.6.2 Threshold Verifiable Random Function.

  • A threshold VRF lets f+1 parties compute an output that f parties cannot, with unbiasability, uniqueness, and correctness as stated properties.The text says unbiasability assumes no honest party has sent a reconstruction share; reconstruction is omitted for the threshold-VRF use case.Source: §2.6.2 · pp. 9–10

2.6.3 Vector commitment.

  • The vector commitment must be binding, so a commitment cannot be opened to multiple values at one position; hiding is not required.Opening and verification concern a value at a specified position in the committed vector.Source: §2.6.3 · p. 10

3 VERIFIABLE GATHER

Verifiable Gather lets parties produce verifiable sets of proposals without requiring exact agreement on the full set. Its security analysis establishes a common core shared by nonfaulty outputs.

3 VERIFIABLE GATHER

  • The protocol uses three conceptual rounds, and later rounds refer to previously broadcast values by sender index rather than resending the values.This avoids the overhead of broadcasting sets containing O(n) values when inputs are large.Source: §3 · p. 11
  • Every nonfaulty party’s output contains a common core of at least n-f party/value pairs, and GatherVerify checks that an output includes values referenced by at least n-f accepted sets.The shared core follows from an index appearing in at least f+1 broadcast sets.Source: §3 · p. 11

3.1 Security Analysis

  • For n>3f, (Gather, GatherVerify) is a verifiable reliable gather protocol.The proof identifies an index appearing in at least f+1 broadcast sets, which supports a common core in nonfaulty outputs.Source: §3.1 · pp. 12–13

3 Byzantine

The security properties of Gather and GatherVerify ensure that outputs retain a shared binding core while respecting the validity of broadcast inputs. Verification also gives nonfaulty parties consistent outputs for a given index set.

3 Byzantine

  • If all nonfaulty parties participate and nonfaulty inputs pass validation, they eventually complete Gather and output gather-sets.The termination argument follows the protocol’s successive waits for n-f broadcasts and sets.Source: §3 · p. 13
  • Nonfaulty parties that complete GatherVerify on the same index set output the same set, and successful verifications agree across index sets.The proof uses agreement of validated reliable broadcast so parties use the same broadcast values.Source: §3 · p. 14
  • The binding core X* has at least n-f party/value pairs and is a subset of every nonfaulty party’s Gather output.Its pairs use values received by the first nonfaulty party to complete Gather.Source: §3 · pp. 14–15
  • When GatherVerify terminates for an index set, its output contains only tuples from validated broadcasts and includes the binding core.The verification checks that the index set contains values referenced by at least n-f accepted T sets.Source: §3 · p. 15

4 PROPOSAL ELECTION

Proposal Election uses a threshold VRF and Verifiable Gather to retrospectively select among externally valid proposals. Its verification mechanism and security analysis connect a common binding-core proposal to agreement among nonfaulty parties.

4 PROPOSAL ELECTION

  • The four-round protocol gathers proposal/transcript pairs, broadcasts gather-set indices, obtains VRF evaluation shares, then selects the proposal with the highest evaluation.Parties commit to a proposal and its aggregated VRF-DKG transcript together before learning which proposal wins.Source: §4 · pp. 15–16
  • With probability at least 1/3, the maximum VRF evaluation belongs to a nonfaulty proposal in the binding core, and then all nonfaulty parties output that proposal.The VRF evaluations are unbiased, so each party has the same probability of having the maximum evaluation.Source: §4 · pp. 15, 17
  • A proposal is verifiable using a gather-set’s indices, which let parties check the gather-set and confirm that the proposal has the maximal associated VRF evaluation.When the maximum evaluation is tied to a binding-core tuple, only gather-sets containing that tuple verify.Source: §4 · p. 17

4.1 Security Analysis

  • Nonfaulty parties’ evaluation state eventually becomes consistent: a tuple in one party’s start_eval is eventually evaluated by every nonfaulty party.The security analysis also states that evaluations in one nonfaulty party’s evals set eventually appear for every nonfaulty party.Source: §4.1 · p. 17

12: broadcast ⟨푖푛푑푖푐푒푠,퐼푖⟩

The protocol uses gathered proposal sets and VRF evaluations to select a proposal, then lets parties verify that selection consistently. Its binding argument gives the maximum evaluation a constant chance of belonging to a nonfaulty proposer.

12: broadcast ⟨푖푛푑푖푐푒푠,퐼푖⟩

  • When all nonfaulty parties participate, each eventually gathers at least n−f valid DKG shares and outputs a proposal from PE.They aggregate the shares into a valid VRF-DKG value before entering Gather.Source: §12 · p. 19
  • PE output proofs are complete: a nonfaulty verifier eventually reconstructs the same maximal index and confirms the corresponding proposal.The parties rely on matching gathered tuples and VRF evaluations.Source: §12 · pp. 19–20
  • Each eligible tuple has an equally likely maximal VRF value, giving the binding-set maximum a constant chance of coming from a nonfaulty proposer.The collision analysis requires a security parameter of at least 3 log(n).Source: §12 · pp. 20–21
  • If one nonfaulty party's PEVerify terminates, every other nonfaulty party eventually verifies the same value and proof.Agreement follows from common gathered sets and evaluations, followed by the same deterministic computation.Source: §12 · p. 21
  • Any proposal accepted by PEVerify must equal the proposal at the maximal-evaluation index in the binding set.Gather's Includes Core property ensures that the verification set contains the binding set, so its maximum identifies the same proposal.Source: §12 · pp. 20–21
  • Every proposal accepted by PEVerify is externally valid because Gather only verifies tuples that pass its validity check.The check implies that the proposal itself passes validate.Source: §12 · p. 21

5 NO WAITIN’ HOTSTUFF

This section presents No Waitin’ Hotstuff, a leaderless asynchronous consensus protocol that uses Proposal Election and a key-lock-commit design. Its security analysis establishes its Validated Asynchronous Byzantine Agreement properties, including correctness, validity, state and view progression, and termination.

5 NO WAITIN’ HOTSTUFF

  • NWH uses PE to determine whether parties agree; if PE fails, parties repeat it, amplifying constant-probability agreement to overwhelming probability.PE can output different values across parties when unsuccessful, so NWH allows the protocol to move to another view and try again.Source: §5 · p. 22
  • The key-lock-commit mechanism protects safety: locks prevent conflicting values from advancing, and commit messages let other parties terminate with the same value.Parties may ignore a lock only with a later-view key proving that no commitment took place in the lock’s view.Source: §5 · p. 22
  • NWH proceeds in five rounds per view: parties select a key through PE, confirm its output, set and confirm locks, then commit; failed PE moves them to a new view.Before setting a lock, parties ensure enough parties have set keys for the current value; a party that sees enough locks can commit and terminate.Source: §5 · pp. 23–24

5.1 Security Analysis

  • The security theorem establishes correctness, validity, termination, and quality; correct messages in a view share one value, and a commitment prevents conflicting future echoes.The safety argument relies on at least f + 1 nonfaulty parties acting as sentinels in later views.Source: §5.1 · pp. 24, 25, 27, 28
  • When all nonfaulty parties begin a view with valid inputs, NWH has a constant probability of terminating; if earlier views fail to commit, honest parties eventually advance.The analysis derives eventual termination with high probability across views, and quality from termination together with PE’s α-binding property.Source: §5.1 · pp. 25, 28, 29
  • A nonfaulty party with a valid input maintains correct key and lock values and proofs throughout the protocol.Source: §5.1 · p. 29
  • If all nonfaulty parties participate with valid inputs and none terminates in an earlier view, they all eventually reach the view.The proof uses induction over views and PE verification to ensure parties advance together.Source: §5.1 · pp. 29–30
  • No party can send a blame message for a proposal that a nonfaulty party supplied as its PE input.The proof uses the lock-correctness condition and the quorum of signatures supporting a lock to show the proposal’s key is at least the lock value.Source: §5.1 · pp. 30–31
  • If all nonfaulty parties start a view with inputs x_i satisfying validate(x_i)=1, then with constant probability all nonfaulty parties terminate during that view.The proof also states that if the PE binding value is the input of a party that acted nonfaultily when starting PE, all parties terminate during the view.Source: §5.1 · p. 31
  • Theorem 4 identifies NWH as a Validated Asynchronous Byzantine Agreement protocol.Source: §5.1 · p. 32

3 Byzantine

The NWH security analysis establishes correctness, validity, almost-sure termination, and a quality guarantee tied to Proposal Election’s binding value.

Correctness

  • Every nonfaulty party that outputs a value outputs the same value, because correct commit messages in the first committing view must agree.The proof uses quorum signatures and the fact that at least one signer among n−f is nonfaulty.Source: §3 · p. 32

Validity

  • An output value must pass the external validity check encoded in the proposal’s key-correctness proof.The proof connects a verified PE proposal to keyCorrect(k,v,π)=1 and rejects a value for which validate(v)=0.Source: §3 · p. 32

Termination

  • With valid inputs and all nonfaulty parties participating, NWH terminates almost surely through independent constant-probability opportunities in successive views.The probability of reaching a given view decreases exponentially with the view number.Source: §3 · p. 33

Quality

  • With probability at least α, the binding value is an input proposed by a party that behaved nonfaultily when it started PE.Nonfaulty parties participating in that view terminate with the proposal’s value.Source: §3 · p. 33

6 ASYNCHRONOUS DISTRIBUTED KEY GENERATION

The A-DKG construction aggregates verified shares into a proposal and uses NWH to agree on a valid DKG transcript.

Protocol construction

  • Each party aggregates received DKG shares into a proposal and submits it to NWH with DKGVerify as the external validity function.The construction waits for shares from n−f parties before aggregating.Source: §6 · p. 33
  • After NWH terminates, parties output the same externally valid DKG transcript.The construction relies on NWH’s agreement and validity properties.Source: §6 · p. 33

Theorem

  • The stated theorem identifies ADKG as an asynchronous distributed key generation protocol resilient to f<n.The supplied theorem statement ends after this bound.Source: §6 · p. 33

3 Byzantine

The ADKG analysis derives its security properties by combining the guarantees of the DKG components with those of NWH.

Security preservation

  • If the DKG share, verification, aggregation, and transcript-verification components preserve security against concurrent adversaries, ADKG preserves security for the same threshold application.The proof models expected honest-share delivery as concurrent requests to a DKG-share oracle.Source: §3 · p. 34

Correctness

  • ADKG correctness follows from the correctness of its DKG share-generation, share-verification, aggregation, and transcript-verification components.Source: §3 · p. 34

Agreement

  • Nonfaulty parties that complete ADKG output the same transcript, and NWH validity ensures that transcript passes DKGVerify.Source: §3 · p. 34

Termination

  • When all nonfaulty parties participate, each aggregates n−f verified shares into a valid proposal and NWH ensures eventual termination.Source: §3 · p. 34

7 EFFICIENCY OF OUR PROTOCOLS ASSUMING CONCRETE CRYPTOGRAPHY ALGORITHMS

This section analyzes protocol efficiency under suggested concrete cryptographic algorithms and tracks the security parameter λ. Its A-DKG implementation has expected O(λn^3 log(n)) word complexity and a constant expected number of rounds.

7.1 Broadcast

  • O(n^2 log(n)λ + mn) words suffice to broadcast a message of m words.The section suggests a Cachin–Tessaro broadcast using vector commitments and Merkle trees; SNARKs could reduce opening proofs to O(1) at the cost of trusted setup and high proving time.Source: §7.1 · pp. 34–35

7.2 Verifiable Gather

  • O(λn^3 log(n) + mn^2) words and a constant number of rounds are achieved by Verifiable Gather.Its cost follows from O(nb(m)) words, where b(m) is the cost of broadcasting m words.Source: §7.2 · p. 35

7.3 Proposal Election

  • O(λn^3 log(n) + mn^2) words and a constant number of rounds are achieved by Proposal Election (PE).PE relies on Gather and a threshold VRF.Source: §7.3 · p. 35

7.4 No Waitin’ HotStuff

  • O(1) expected views, each with a constant number of rounds, and O(λn^3 log(n) + mn^2) expected words are achieved by NWH.The word bound is per view; the expected number of views is constant.Source: §7.4 · p. 36

7.5 Asynchronous Distributed Key Generation

  • O(λn^3 log(n)) expected words and O(1) expected rounds are achieved by the A-DKG implementation.It uses one round to send DKG shares and one call to No Waitin’ HotStuff (NWH).Source: §7.5 · p. 37

A BACKGROUND: RELIABLE BROADCAST FOR ASYNCHRONOUS SYSTEMS

The cited reliable broadcast protocol uses error-correcting codes with Bracha broadcast in an asynchronous setting. It tolerates f < n/3 adversaries and has communication complexity O(n^2 log(n) + |M|n).

A BACKGROUND: RELIABLE BROADCAST FOR ASYNCHRONOUS SYSTEMS

3 Byzantine

The reliable broadcast protocol adapts Bracha’s echo-and-ready pattern using committed, verifiable shares of a polynomial encoding. It is resilient to f < n/3 Byzantine parties.

3 Byzantine

  • A party sends ready after n−f matching echo messages or f+1 ready messages, then, after n−f ready messages, interpolates the corresponding points to polynomial p and outputs its coefficients m0,…,mℓ.Source: §3 · p. 40
  • Error-correcting encoding avoids sending the full message in every party’s message, reducing communication for large broadcasts.The text identifies Reed–Solomon encoding as the approach used to reduce communication costs.Source: §3 · p. 40
  • The dealer commits to a vector of polynomial-share sets and sends each party its set with an opening proof; parties echo verified shares.After receiving enough echoes, a party interpolates the polynomial and can reconstruct its own set and proof for a ready message.Source: §3 · p. 40
  • Nonfaulty parties’ ready messages share the same commitment, supporting agreement on the broadcast value.The proof uses overlapping quorums and the fact that a nonfaulty party sends only one ready message.Source: §3 · pp. 41–42
  • The protocol is a reliable broadcast protocol resilient to f < n/3 Byzantine parties.Source: §3 · p. 42

A.2 Proof of Theorem 6

The proof counts dealer, echo, and ready messages and describes a validated variant that checks the output before termination.

A.2 Proof of Theorem 6

  • The dealer sends each party a commitment, proof, and O(ℓ/n) additional words; parties each send at most one echo and one ready message.Source: §A.2 · p. 44
  • The communication accounting covers O(n^2) messages, each carrying commitment, proof, and coded-message data.Source: §A.2 · p. 44
  • The reliable broadcast protocol becomes validated by requiring parties to check validate(m′) = 1 before outputting.The passage states that this preserves validity and correctness and gives termination when a valid dealer input exists.Source: §A.2 · p. 44
Loading 2102.09041v3…