Build set with PKI from reliable broadcast / random beacon

Question

I am trying to build a protocol (or find an existing one) for creating a set $S_2$ with PKI from a set of parties $S_1$ that initially does not know anything about the other parties.

We assume end-to-end communication and broadcast, all with a delay up to $\text{Delta}_\text{transmission}$. Additionaly, we also use NIST random beacon (could simplify the protocol, but it doesn't solve the deadline problem below).

So every party $p \in S_1$ would run this protocol $A$ at a time $t_1$, and we would like at $t_2$ that all honest parties have the same set $S_2$ of parties with PKI.

---

I could imagine a solution where all parties generates a private/public key pair, and then the protocol dictate that for each round, they broadcast a signed message with their public key and current vision of $S_2$; ie $m = [pk, S_2]$.

each time they receive a valid signed message with a new public key $pk'$ and a new set $S_2'$, they do $S_2 = S_2' \cup S_2 \cup {pk'}$, and rebroadcast $[pk, S_2]$

---

My main problem with this scenario is termination : if we want the protocol to terminate at any deadline $t_2$ fixed in advance; there is always a way for an attacker to break consistency (all honest parties have the same set $S_2$ in the end) by sending a new valid message $m'$ just before the deadline to a party $p$, so that this party accept it, but when the honest party rebroadcasts his new set including the new key, other honest parties discard it because it arrives after the deadline $t_2$.

Any help, either directly on how to fix the deadline problem, or indirectly how to build such protocol, would be greatly appreciated :)

Thank you in advance

Answer 1

There might be multiple solutions, and this could be one of them.

You can use multiple rounds of Terminating Reliable Broadcast (TRB). Each party in $S_1$ sends a message with their own proposal $pk$ -- this corresponds to one round of TRB.

After $|S_1|$ rounds, you're good to go. Since all honest parties have the same set of individual proposals, they can deterministically compute the result $S_2$.

Naturally, if you assume $f<|S_1|$ nodes can fail (e.g. by crashing, arbitrary), you have to stop the protocol after $|S_1|-f$ rounds.

PS: I might have misunderstood some of the details in your the question, so please correct me if anything's amiss.