threshold/docs/Broadcast.md

title, author, date

title	author	date
Broadcast	J.-P. Aumasson A. Hamelink L. Meier	14-07-2021

Reliable Broadcast

Let P^{(1)}, \ldots, P^{(n)} be a set of n participants in a protocol, and let t be the maximum number of participants that may be malicious at any given epoch.

For a general threshold signature scheme, the integer t may take any value in \{0,1,\ldots, n-1\}, since t+1 corrupted parties may reconstruct the full signing key by combining their individual shares. The signing protocol itself can then be run by any subset S\subseteq \{P^{(1)}, \ldots, P^{(n)} \}, as long as |S| > t. In the worst case scenario, S may contain only a single honest participant, and we must therefore assume a dishonest majority in S.

In this setting, it may be impossible to guarantee that the protocol acheives either guaranteed output delivery (the adversary cannot prevent honest parties from receiving the final output) or fairness (either all honest parties receive the protocol output, or none do). Most often, this is due to the protocol assuming the existance of a reliable broadcast channel, which guarantees that all participants receive the same message, even when the broadcaster may be malicous. When implementing a protocol, we must often rely only on a point-to-point network between participants, and naively broadcasting a message by sending it to each party individually may fail when a corrupt party decides to send different messages to different parties. In fact, a reliable broadcast primitive is equivalent to a consensus primitive, since it requires all participants to agree on the message which was broadcast. Given that consensus is impossible to acheive when t < n, we must look at other ways to acheive a broadcast primitive.

Broadcast with abort

When a dishonest majority is assumed, it is possible to implement a broadcast primitive which guarantees that either all honest participants agree on the sent message, or otherwise abort. This channel is due Goldwasser and Lindell and we will refer to it as an "echo broadcast". Unfortuanately, it allows an adversary to force an abort by simply sending two different messages during a broadcast round.

Suppose each participant P^{(i)} is instructed in round k to reliably broadcast some message x^{(i)} to all other parties. The broadcast is done as follows, from the perspective of P^{(1)}:

• P^{(1)} sends x^{(1)}_j = x^{(1)} to each P^{(j)}, and stores x^{(1)}_1 \gets x^{(1)}.
• Upon reception of x^{(j)}_1 from P^{(j)}, store x^{(j)}_1.
• Compute V^{(1)} \gets \mathsf{H}(x^{(1)}_1, \ldots, x^{(n)}_1) and deliver (x^{(1)}_1, \ldots, x^{(n)}_1) to round k+1.
• When instructed by round k+1 to send message y^{(1)}_j to P^{(j)}, send (y^{(1)}_j, V^{(1)}) instead.
• Upon reception of (y^{(j)}_1, V^{(j)}) from P^{(j)}, abort if V^{(j)} \neq V^{(1)}, otherwise deliver y^{(j)}_1 normaly to round k+2.