Shared Coin Sample Clauses

Shared Coin. ‌ ∈ We describe here an asynchronous protocol for a shared coin with a constant success rate against the delayed-adaptive adversary. We assume that for every r N, shared_coin(r) is invoked by all correct processes and that the invocation of shared_coin(r) by some process p is causally independent of its progress at other processes. The definition of a shared coin is given below. ► Definition 2 (Shared Coin). A shared coin with success rate ρ is a shared object that gener- ates an infinite sequence of binary outputs. For each execution of the procedure shared_coin(r) with r ∈ N, all correct processes output b with probability at least ρ, for any value b ∈ {0, 1}. The pseudo-code for our shared coin is presented in Algorithm 1. Our protocol is composed of two phases of messages passing. Each process first samples the VRF with its private key and the protocol’s argument in order to generate a random initial value. For brevity, we denote by V RFi the VRF with pi’s private key. Using a VRF to generate a random initial value effectively weakens the adversary as Byzantine processes can neither choose their initial values nor equivocate. If a Byzantine process would try to act maliciously, the VRF proof would easily expose it and its message would be ignored. In each phase of the protocol, each process sends one value to every other process. The receiver validates the received values using the VRF proofs, which are sent along with the values. We omit the proof validation from the code for clarity. After two phases of communication, each process chooses the minimum value it received in the second phase and outputs its least significant bit. We follow the concept of a common core, as presented by Attiya and ▇▇▇▇▇ for the crash failure model [6], and argue that if a core of f + 1 correct processes hold the global minimum value at the end of phase 1, then by the end of the following phase all processes receive this value. We exploit the s parameter in our resilience definition to bound the number of values held by f + 1 correct processes. We show that this number is linear in n and hence with a constant positive probability, by the end of the second phase, all correct processes receive the global minimum among the VRF outputs and therefore produce the same output. Algorithm 1 Protocol shared_coin(r): code for process pi 1: Initially first-set, second-set = ∅ 2: vi ← VRFi(r) 3: send (first, vi) to all processes