Usages of echo-broadcasting

[fjarri]

It appears that we are using echo-broadcasting for two separate purposes:

1. To simulate a verifiable broadcast. This is a common primitive required e.g. by CGGMP. While this worked fine for n-of-n scenarios, attempting to add threshold to the picture results in issues when faulty/malicious nodes are involved (see Proper threshold support #95).
2. To collect data for a possible generation of an evidence of malicious behavior. For example, some check of an incoming message from a node j may use a value assembled from messages received from all nodes during one of the previous rounds. If the check fails, we can only use the data signed by j in the evidence; this means j must echo all the received messages in that previous round so that during the evidence verification we could assemble the required value using only the data signed by j.

We may also want one more similar functionality:
3. Ensure that all nodes agree on the total set of nodes that is still considered active. This can be used to make e.g. the returned key shares each contain the same set of public shares. Is that necessary?

These purposes need to have separate APIs associated with them, and they will probably have to use separate algorithms since we need different guarantees in either case.

Open question: for item 1, do we need reliable broadcast (Bracha's algorithm etc) or verifiable broadcast (more complicated)? Or perhaps abortable broadcast (https://arxiv.org/abs/2410.22080)? What does CGGMP need?

More links:

• Bracha's reliable broadcast: https://decentralizedthoughts.github.io/2020-09-19-living-with-asynchrony-brachas-reliable-broadcast/
• Verifiable information dispersal: https://decentralizedthoughts.github.io/2024-08-08-vid/
• A modern reliable broadcast scheme: https://arxiv.org/pdf/2404.08070v2

[fjarri]

To summarize some assorted reading: GG'18 and '20 only required reliable broadcast. GG'21 uses the term "verifiable", although it is not clear whether it is a deliberate word choice. The only desirable property they mention explicitly is that "consensus is always reached between all honest parties" (which I think is equivalent to the totality property of a reliable broadcast), for the rest they reference R. Canetti. "Universally composable security", https://doi.org/10.1145/3402457, where the term "broadcast" only occurs twice and never really explained.

[dvdplm]

I find that different authors use different terms for these things, and the words used seem to really matter.

Property	Consistent Broadcast (Echo Broadcast)	Reliable Broadcast (BRB)
Validity	If correct sender broadcasts 𝑚, all correct parties deliver 𝑚.	If correct sender broadcasts 𝑚, all correct parties deliver 𝑚.
Consistency (aka Agreement)	If correct 𝑃ᵢ delivers 𝑚 & correct 𝑃ⱼ delivers 𝑚′, 𝑚 = 𝑚′.	If correct 𝑃ᵢ delivers 𝑚 & correct 𝑃ⱼ delivers 𝑚′, 𝑚 = 𝑚′.
Integrity	Deliver at most one message: if sender correct, message was sent.	Deliver at most one message: if sender correct, message was sent.
Totality	Not Guaranteed. Some correct parties may deliver, others not.	Guaranteed. If 𝑎𝑛𝑦 correct party delivers 𝑚, 𝑎𝑙𝑙 correct parties deliver 𝑚.
Typical Use	Lightweight broadcast where eventual delivery for all isn't critical.	Foundational primitive for consensus, SMR, MPC requiring strong agreement.
Key Limitation	Allows divergence in delivery decisions among correct parties.	Higher complexity (e.g., 𝑂(𝑛²) messages for classic Bracha).

Afaict "echo broadcast" is a sloppy term, most often meaning "consistent broadcast" but not always.

In CGGMP section 3.5 the authors use the following terms:

• "verifiable broadcast channel"
• "authenticated, synchronous broadcast channel"
• "'weak' broadcast"

While I can speculate about what e.g. "verifiable broadcast channel" means, it's hard to know for sure. I think that by "weak broadcast" they probably mean "Consistent Broadcast", i.e. BRB minus Totality?