Lack of agreement despite broadcast

[real-or-random]

The book currently gives a rather detailed description of broadcast (kudos for that!), and emphasizes that the first round needs to send over broadcast, see https://frost.zfnd.org/tutorial/dkg.html.

I don't think this is sufficient for typical scenarios:

Consider the following attack, say in a 2-of-3 with participants A, B, C. A is malicious and B and C are honest.

• A, B, C run round 1 honestly (over broadcast).
• Malicious participant A sends wrong shares to honest B but correct shares to honest C.
• C concludes that the DKG has finished, and sends money to the resulting threshold public key. [1]
• B and C are 2 honest participants, but they can't sign. The money is lost.

I believe what is necessary is to run another round of broadcast at the end, to confirm that all participants not only agree on the common parameters, but also on the fact that DKG has succeeded. C should only conclude that DKG was successful when it has confirmation from everyone else. Note that running an instance of echo broadcast with aborts as the last step of the DKG solves the problem only partially. Participant A could always equivocate in the last round of the echo broadcast, making B believe that something went wrong while making C believe everything is alright. (In this situation, B must not conclude that the protocol didn't work and delete shares. B is rather in some indeterminate state...)

@jonasnick and I are currently working on a draft spec for DKGs for FROST. We rely on the broadcast abstraction in the Olaf paper, which moves the broadcast for exactly this reason to the end of the protocol. Our draft spec contains a variant of echo broadcast with signatures. That has the advantage that participants will receive a "certificate" (transferable proof) of success of a DKG run, and can use this to convince every other signer that DKG has succeeded. This ensures that if messages arrive eventually, everyone will eventually learn that DKG was successful (and in case of success, eventually everyone leaves the indeterminate state). See https://github.com/jonasnick/bip-frost-dkg for our current write-up, but be aware that some of the text is currently outdated, and we're actively working on it. See this section for the echo broadcast with signatures. I hope we'll have a somewhat stable version soon.

[1] You could object that C isn't supposed to draw this conclusion, but then I'd wonder how C or anyone else is ever supposed to use the threshold public key.
[2] See also Section 4 in the Olaf paper, where we consider a variant of PedPop with a final broadcast round. (Caveat: While we mention the agreement problem, we later establish only unforgeabiliity formally, but the problem that arises from the lack of agreement is rather "correctness".)

[chelseakomlo]

Thanks @real-or-random! Yes, we are aware of this issue. It is good to know that you all are working on a spec for DKGs for FROST, we'll look at that for inspiration. Let us know if you would like reviews or comments as that spec progresses!

[pool2win]

Note that running an instance echo broadcast with aborts as the last step of the DKG solves the problem only partially.

@real-or-random - just to confirm your mention of echo broadcast refers to Goldwasser-Lindell 2003 broadcast?

I am curious if the much older echo broadcast by Bracha 83 (section 3) is more appropriate to let parties know that a threshold number of parties have sent the same share to them. The difference is that requiring a threshold number of parties to ack a message, we don't allow a party to equivocate.

Using Bracha's protocol, we'll get robustness, however we limit t < n/3. However, we can avoid A equivocating like in the example above.

This is how we can use Bracha's protocol during round 2 of FROST KeyGen. We add a new step 1.1 right after step 1 of round 2 of FROST KeyGen.

The new step 1.1 requires that

1. Each party reliably broadcasts a hash of their secret share (l, f_i(l)) using Bracha's protocol.
2. Each party waits till it has accepted the required threshold, T, number of share hashes. This threshold, T, is the threshold parameter to the FROST instance.
3. Continue to step 2 of round 2 from FROST KeyGen.

The broadcast protocol makes sure that is a party accepts a hash of a share, then every other correct process will eventually accept the hash of the share. With t < n/3 for the broadcast, in the above example A can't equivocate.

TBH, we can find more optimal atomic reliable broadcast protocols e.g. Cachin et al, that will be more efficient that Bracha's protocol, but to keep things simple and avoid introducing a complicated protocol I stay with Bracha above. I just want to check with you all if a byzantine fault tolerant reliable broadcast like Bracha's is sufficient.

[real-or-random]

@real-or-random - just to confirm your mention of echo broadcast refers to Goldwasser-Lindell 2003 broadcast?

Yes, I think this is what I had in mind.

The broadcast protocol makes sure that is a party accepts a hash of a share, then every other correct process will eventually accept the hash of the share. With t < n/3 for the broadcast, in the above example A can't equivocate.

Yep, that "if one party accepts v, then every party will eventually accept v" (Lemma 3 in the paper) is precisely the kind of property you'll need to avoid the issue. (By the way, here's another nice write-up of Brachas protocol: https://decentralizedthoughts.github.io/2020-09-19-living-with-asynchrony-brachas-reliable-broadcast/ )

TBH, we can find more optimal atomic reliable broadcast protocols e.g. Cachin et al, that will be more efficient that Bracha's protocol, but to keep things simple and avoid introducing a complicated protocol I stay with Bracha above. I just want to check with you all if a byzantine fault tolerant reliable broadcast like Bracha's is sufficient.

I can't endorse your exact protocol, of course, because I did not have a detailed look at it. But on this high-level this all sounds good to me. (And yes, it probably makes sense to keep things simple and avoid a complex protocol if you need the broadcast only for DKG.)