Use consistent terminology for Eq's properties

[jonasnick]

The terminology we use in the BIP should try to both be clear and consistent with existing literature - in particular with the literature that this BIP is based on. If there are important differences we should mention it somewhere - if only for documentation.

Practical Schnorr Threshold Signatures Without the Algebraic Group Model ("Olaf"):

• Agreement: If some honest party outputs true, then every honest party will output true.

The Secure Multi-Party Computation without Agreement ("GL") solves a problem that is different from Eq, namely "broadcast with abort" (one party broadcasts a single value instead of all parties comparing their values as in Eq):

• Agreement: Byzantine Agreement (All honest parties receive their outputs or all honest parties abort)
• Broadcast: Essentially synonym for Byzantine generals (or agreement) problem
• Broadcast with abort: has "agreement for broadcast with abort" (Definition 9)
• Agreement for broadcast with abort: If an honest party receives an output, then all honest parties receive the output or abort

Abort in this protocol roughly corresponds to the "in-progress" state of Eq.

In the master branch:

• Consistency: If some honest participant outputs SUCCESS, no other honest participant outputs FAIL.
• Conditional Termination: If some honest participant outputs SUCCESS, then all other participants will (eventually) output SUCCESS.
• Agreement is mentioned informally (and the name of the "Ensuring Agreement" section)

From this overview I see the following possible improvements.

1. Conditional Termination implies Consistency, so we could remove the latter.
2. We could rename Conditional Termination to Agreement. The property is equal to Agreement in Olaf and roughly equal to Agreement as defined for Broadcast with Aborts in GL. However, I like Conditional Termination. It's a clearly distinct from Byzantine Agreement.

[real-or-random]

Related, and what often comes up in discussions is the (im)possibility of various broadcast notions.

Make the following basic assumptions: We want security for any f<n (dishonest majority) in an asynchronous network, but we can have PKI and signatures.

If we want to achieve a consistent broadcast under these assumptions, then guaranteeing termination of the broadcast is impossible. This is true even against an adversary that can only drop messages, e.g., Theorem 2 https://arxiv.org/pdf/2205.09992.pdf. (Interestingly, the problem is solvable, against arbitrarily malicious nodes, in the synchronous model using the Dolev-Strong protocol (see https://timroughgarden.github.io/fob21/l/l2.pdf for a beginner-friendly writeup), but this model is not really appropriate for the Internet and the protocol needs O(n) rounds.)

Strictly, speaking, the above impossibility result does not formally rule out that robust DKG with bias can be solved under the above assumptions. It only shows that what does not work is to build DKG by using broadcast to agree on the transcript. (But what else could we do? We'll need to agree at least on the threshold key, and enough honest parties should be able to contribute to it. I suspect that this observation can be used to prove formally that robust DKG with bias is impossible. Perhaps it's even not that hard, but I haven't really thought about it.)

Katz points out that unbiasable DKG cannot be solved without an honest majority (see a footnote in https://eprint.iacr.org/2023/1094.pdf) because it can be reduced to fair coin tossing, which is impossible without honest majority (https://kodu.ut.ee/~swen/courses/crypto-ii/2008/cleve1986.pdf).