Optimistic Randomness for ABA

[amiller]

Optimistic Randomness for ABA

[amiller]

@amiller It doesn't really matter if the actual process needs to continue longer after you've already produced an output right? Continuing longer only parallelizes with the rest of the protocol with no cost to latency.

Right, it's OK if the actual process continues longer even after output is delivered, it is just a little bit inelegant. In our Go implementation we've found it's easier to code to be able to clean up memory by only having one active at a time.

Thus you can share the coins for each round between all instances by waiting until every single instance has gotten to the end of round r before flipping the coin for round r, and this won't introduce any issues for liveness.

This is a really interesting optimization. If we could share common coins between instances it could cut down on the worst-case threshold crypto bottleneck.

Indeed the main reason why we did not try to share the common coins between instances is because of a deadlock problem.. we need to be able to proceed with some ABA's that receive input 1 and complete before providing input 0 to any other ABAs. So if we wait until all instances are ready to proceed with the coin, then we would get stuck. Your observation is that by forcing the first coin to be 1 we are already removing that deadlock. We are guaranteeing that at least N-t of the ABA instances reach agreement on 1 in the first round. After this point, honest parties will be able to provide input to all the remaining ABA instances as well. This is cool, I think reduces the worst-case expected communications per node of N instances of ABA from O(N^2 lambda) to O(N^2 + N lambda)

[Vagabond]

When you say 'coin schedule' do you mean (for option 2) instead of calling get_coin() and modulus the result by 2, we'd act like round 1 had a coin flip modulus 2 result of 1, round 2 also had a coin flip modulus 2 result of 1, round three had a coin flip modulus 2 result of 0... and round 5 we actually ran the common coin protocol?

In addition, when you have those trailing ...s in the options, are the elided values coin() or a repetition of the pattern?

[amiller]

@Vagabond yes your description is exactly what I mean by "coin schedule".
The trailing ...s in the options mean repetitions of the pattern 1,0,coin()

[Vagabond]

Yeah, this seems really interesting. I like it.

Just to confirm: the idea here is that in the usual case, when an attacker is not actively attacking ABA, a fixed coin schedule allows us to reach agreement faster with the fallback to the heavyweight common coin if we exceed 4 rounds (which is the expected number needed to converge)?

Does this weaken security or just allow an adversary, if they are present, to cause ABA to take more rounds to complete?

[ChronusZ]

I believe you only need to do the very first round deterministic 1, since if every honest node begins by voting 1 then every node is guaranteed to always have bin_vals={1} and hence terminate on the first round. Similarly you should only need one round of deterministic 0 to handle the benign crashed nodes.

I personally quite like the prf idea. You could even adjust the number of prf rounds dynamically to minimize the average number of message rounds until termination, so that in the presence of an active network adversary the prf rounds decrease, and in absence they increase.

[amiller]

@ChronusZ even if every node starts by inputting 1, and therefore every honest node sees bin_values={1}, it is still necessary to continue participating in the protocol until another coin returns 1.
The reason is that given the local view of an honest party bin_values={1} in this scenario, there is a different possible world where other honest parties see bin_values={0,1} and hence they need to see another 1 coin before deciding.

[ChronusZ]

@amiller It doesn't really matter if the actual process needs to continue longer after you've already produced an output right? Continuing longer only parallelizes with the rest of the protocol with no cost to latency.

By the way, another point worth mentioning is that a simple modification to the CONF round turns it into an RBC READY-type round which can also be used to fix this. More specifically, you add the logic:

• Upon receiving t+1 CONF(r,{v}) messages, broadcast CONF(r,{v}).
• Upon receiving n-t CONF(r,{v}) messages, terminate and ouput v if v equals the common coin value, even if we've already progressed past round r.

This way if you terminate in round r, by the reliability of the CONF message you know everyone else can eventually terminate on round r, and by the ABBA properties you know that no one will terminate on a different value even in a future round.

Also, one more optimization that occurs to me is that by making the first round deterministically flip to 1, for any round r>1 all instances can get to the end of round r independently of any other other instance. Thus you can share the coins for each round between all instances by waiting until every single instance has gotten to the end of round r before flipping the coin for round r, and this won't introduce any issues for liveness.

[ChronusZ]

Alternatively, you could just add a READY-type message at the very end, and after outputting a value in some round only continue to the next round if t+1 nodes send a message for the next round. Then if t+1 honest nodes output in round r everyone can eventually receiving enough READY's to terminate, and otherwise everyone receives enough messages from the next round to participate in the next round themselves.

[afck]

I'm probably missing something, but I was wondering whether some kind of special v*/termination message is necessary anyway, to guarantee that all instances terminate (not for output, of course, but for termination)?

Let's say the f faulty nodes just never send any messages, one node, Alice, decides and outputs 0️⃣ in round 1, and the coin shows 0️⃣ in round 2 again. Then Alice will terminate in round 2 and honest Bob will output in round 2. But Bob must continue until the coin comes up 0️⃣ again. He will be stuck in round 3, where he won't receive more than N - f - 1 Aux messages.