VACS with Subquadratic Communication Complexity Sample Clauses

VACS with Subquadratic Communication Complexity. A protocol for the asynchronous common subset (ACS) problem [4, 11] allows n parties to agree on a subset of their initial inputs. We consider a validated version of ACS, where it is additionally ensured that all values in the output multiset satisfy a given predicate Q. This notion is inspired by the standard notion of validated asynchronous Byzantine agreement [9]. Definition 13 Let Q be a predicate, and let Π be a protocol executed by parties P1, . . . , Pn, where each party Pi initially holds an input vi, outputs a multiset of size at most n, and terminates upon generating output. Π is an f -secure Q-validated ACS protocol with A-output quality if the following hold if at most f parties are corrupted: • Correctness: If an honest party outputs S, each value v ∈ S satisfies Q(v) = 1. • Consistency: every honest party outputs the same multiset. • A-Output quality: if every honest party’s input vi satisfies Q(vi) = 1, then all honest parties output a multiset of size at least A. We describe a common-subset protocol with subquadratic communication complexity. Let Q be a predicate. The protocol allows n parties, P1, . . . , Pn, to agree on a common subset of inputs values satisfying the predicate Q. The protocol follows the structure of [4]. VACS The protocol ΠA,Q uses as setup a secret randomly chosen committee of parties C, where each 2+s party is independently added to the committee with probability p := s/n, where s := 3 A and A is the output-quality. The idea is that parties run a number of instances RBC1, . . . , RBC|C| of the reliable broadcast protocol introduced in Section 3, where each party Pi ∈ C acts as the sender in one instance of reliable broadcast, and then run |C| instances of asynchronous byzantine agreement BA1, . . . , BA|C| to agree on the set of reliable broadcast instances which terminated and satisfy the VACS predicate Q. A formal description of the protocol ΠA,Q and a proof of the following theorem can be found in Appendix E. Theorem 14 Let 0 < s < 1/3, f ≤ (1 − 2s)n/3, and A ≤ (2 + s)n/3. For Q an arbitrary predicate, Π A,Q VACS is an f-secure Q-validated ACS protocol with A-output quality. The expected communication complexity is O(A · (Iκn + κ4n)), where I is the size of each party’s input. The expected size of the setup is O(Aκ ).