Concrete Complexity Comparison. To demonstrate to what extent the communication complexity is improved in practice, we compare the concrete complexity of our new protocol with several state-of-the-art protocols, using reasonably-chosen concrete parameters. We measure the complexity in terms of the total worst-case amount gossiped per peer, as the underlying gossip functionality has a similar cost in all the cases. We compare only to protocols that are highly scalable in the permissionless setting, and security assuming simple honest majority. In all of these protocols, a small committee is sampled at random from the entire population (for the purposes of communication complexity, it does not matter if the same committee is chosen for every round). To guarantee an honest majority in the committee with probability at least 1 − 2−40 (a commonly used statistical security parameter), we need n ≈ 800 when the population has a 2/3 honest majority (for a smaller honest majority, the committee size would be larger, tilting the comparison even further in our favor). Reasonable values for the security parameters are λ = |r| = 64, λH = λpk = 256 and λsig = 512 (e.g., using SHA256 for hashing and ed25519 for signatures). Thus, λoverhead = 896. For the leader-election (which is required in all the protocols), we assume we are using Algorand-style leader election using VRFs, and rely only on a simple honest majority. The committee for the propose round only needs to guarantee that at least one party is elected with overwhelming probability (rather than an honest majority on the committee); thus, we can use n′ ≪ n. Using the same 2−40 statistical security parameter, it is enough to use n′ = 30. Since at least half of the population is honest, the probability that the minimal VRF value will be honest is at least 1/2, thus it is reasonable to use p = 1/2. For an apples-to-apples comparison, we will use our protocol to agree on 256-bit scalars rather than sets; thus, |S| = 256. Our protocol. Plugging these values into the computation of Theorem 4.12, we have Exp(Cost) ≤ 2|E| (n + (1 + 1/p) · (2n + n′)) · λoverhead +(n + (1 + 1/p) · n′) · |S| + 2n · (1 + 1/p) · λH ≤ 2|E| ((7n + 90) · λoverhead + (n + 90) · |S| + 6n · λH) = 2|E|(7808n + 80640) + (n + 90) · |S|) = |E| · (15616n + 161280 + 2(n + 90) · |S|). Thus, per communication link, over the entire protocol: • Less than 1.6MiB for signatures, keys and hashes (independent of the input size). • Less than 256 bytes per bit of input. With a 256-bit input, the ...
