Common use of Our Contribution Clause in Contracts

Our Contribution. We give an affirmative answer to the above question. At the core of our solution, we present a new efficient private-setup free construction for reasonably fair common coin that are pluggable in many ex- isting ABA protocols [15,30,18]; more interestingly, we formalize and construct an efficient (reasonably fair) leader election with perfect agreement such that it can be directly plugged in all existing VBA protocols [12,3,28] to remove private setup. In greater detail, our technical contribution is three-fold: – We give an AVSS construction satisfying the classic CR93 notion [15] with only bulletin PKI (and discrete logarithm assumption), and it costs only (n2) messages and (λn2) bits when sharing λ-bit secret. To our knowledge, this is the first private-setup free AVSS that attains (λn2) communication complexity, and prior art either relies on private setup [6,23] or incurs at least O(λn3) bits [11,7] (except a very recent work [4], yet it still has an extra log n factor than ours). – We implement private-setup free ABAs with expected (n3) message complexity and (λn3) communication complexity with only bulletin PKI. As illustrated in Table 1, it closes the (n) gap between the message and the communication complexities in the earlier private-setup free ABA protocols such as CKLS02 [11], while preserving other benefits such as the maximal n/3 resilience and the optimal expected constant running time. Even comparing with a very recent work due to ▇▇▇▇▇▇▇ et al. [2] that presents a more efficient VBA construction and improves ABA as a by-product,2 our approach still realizes a log n factor improvement. The crux of our design is a novel efficient construction for the reasonably fair common coin in the bulletin PKI setting (conditioned on the random oracle model), with using the more efficient AVSS protocol and verifiable random function. This private-setup free common coin costs only (λn3) bits and constant asynchronous rounds. – We further present how to efficiently instantiate private-setup free VBAs (i.e., multi-valued Byzan- tine agreement with external validity) in the asynchronous setting. For λn-bit input, the resulting VBA realizes the maximal n/3 resilience and optimal expected constant running time, with cost- ing expected (n3) messages and (λn3) bits. As shown in Table 1, this construction closes the (log n) gap between the message and the communication complexities of VBA protocols. In addi- tion, as a by-product, our VBA construction can be directly plugged in the asynchronous distributed key generation protocol in AJM+21 and reduces its communication cost by an O(log n) order to realize O(λn3) communication complexity. To implement more efficient VBA without private setup, we construct a leader election primitive with reasonable fairness and perfect agreement without private setups, assuming the random oracle model. The design costs only (λn3) bits and expected constant asynchronous rounds, and can directly be plugged in all existing VBA protocols [12,3,28] to replace its counterpart relying on private setups, which can be of independent interests. Table 1. Complexities of private-setup free asynchronous protocols with optimal resilience. Message complexity is omitted, as all one-shot protocols in the Table costs O(n3) messages, except that n ABAs cost O(n4) messages. Protocols w/o private setup Earlier Results Our Result Results CommunicationComplexity RunningTime CommunicationComplexity RunningTime (Reasonably fair) common coin CKLS02 [11] 4 O(λn ) O(1) 3 O(λn ) O(1) KMS20 [25] 4 O(λn ) O(n) AJM+21 [2]† 3 O(λn log n) O(1) (Reasonably fair) leader election with perfect agreement AJM+21 [2]† 3 O(λn log n) O(1) 3 O(λn ) O(1) Binary agreement (ABA) CKLS02 [11] 4 O(λn ) O(1) 3 O(λn ) O(1) AJM+21 [2]‡ 3 O(λn log n) O(1) n ABAs instances in parallel CKLS02 [11] 5 O(λn ) O(log n) 4 O(λn ) O(log n) KMS20 [25] 4 O(λn ) O(n) AJM+21 [2]‡ 4 O(λn log n) O(log n) Validated agreement (VBA) AJM+21 [2] 3 O(λn log n) O(1) 3 O(λn ) O(1) Asynchronous ▇▇▇ ▇▇▇▇▇ [▇▇] ▇ ▇(▇▇ ) O(n) 3 O(λn ) O(1) AJM+21 [2] 3 O(λn log n) O(1) † Note that AJM+21 [2] did not present any explicit constructions for the reasonably fair common coin and leader election. Nevertheless, this very recent work gave an asynchronous distributed key generation protocol with O(λn3 log n) bits and expected constant running time, which can potentially bootstrap threshold verifiable random function and can faithfully set up common coin and leader election schemes. However, this unnecessarily long path to constructing common randomness protocols is essentially improvable to our results. ‡ Note that AJM+21 [2] did not explicitly give any constructions for asynchronous binary agreement (ABA). Nonetheless, there is a simple complexity-preserving reduction from ABA to VBA in the PKI setting [12].