Reliable broadcast over p2p

[msgmaxim]

Most (if not all) literature on distributed key generation/signing assume a reliable broadcast channel (to ensure that all parties see the same data, otherwise we might have an aggregate key that can't be used). We don't have this luxury (we probably don't want to use blockchain for this...), so we need to come up with a way to achieve the same functionality over p2p.

Consider a scenario where node P1 needs to "broadcast" data M. We assume that all data send over p2p is signed: D = (M, signature).

Option 1. Nodes retransmit received "broadcast" data to each other in an additional p2p round

For simplicity, assume only three parties: P1, P2 and P3.

1. P1 sends D to P2 and D' to P3. (D' = optionally_tamper_with(M) - which changes D)
2. P3 sends D' to P2, and P2 sends D to P3.
3. P2 (and P3) checks D == D'. If equal, P2 considers D properly broadcast. If not equal, it reports P1 to the blockchian (it can be confident that P1 is cheating as D and D' are both signed and correspond to the same key_id).
4. If the majority of nodes (P2 and P3 in this case) report P1, P1 gets slashed. If P2 is in the minority, it gets slashed instead.

One potential issue with this approach is, it is enough for two nodes, say P1 and P150, (assume 150 parties now) to collude to get an honest node slashed: P1 could generate and sign D_a and D_b send both to P150, but only "broadcast" D_a. In turn, P150 could send D_b to P2 as the data it received from P1, while sending D_a to every other node. In this case, P2 would be the only node to report P1, and would get (unfairly) slashed. The solution, I think, is to submit the to contradicting signed pieces of data along with the report, so a single report would be enough since all other nodes could verify it. Would this verification be hard/annoying to do on SC?

Option 2. Use a semi-trusted cooridnator

1. P2 is selected as the coordinator for the ceremony
2. P1 sends D to P2
3. P2 sends D P3, P4, ..., PN
4. Since D is signed, other nodes can be certain that it came from P1.

Again, P1 and P2 can collude to distribute inconsistent (but signed) data. In this case, however, we wouldn't be able to detect the fact of collusion (so Option 2 is not really viable, I guess).

Any feedback on the above is appreciated.

---

Update: after disucssing this with a developer from thorchain, It looks like there is a better way to simulate a reliable broadcast, presented as Option 3.

Option 3.

In this case we consider N = 150 with parties P_i (i \in 1..N). We want party P_1 to broadcast message M to all other nodes. We will denote the message sent to party P_j as M_j as we don't want to assume that M_j = M (i.e. P_1 may be dishonest).

1. P_1 sends M_j to P_j (j != 1)
2. Each party P_j (j != 1) hashes M_j to produce H_j = Hash(M_j) and "broadcasts" H_j by sending (j, H_j) to P_k (k != j)
3. Now each party P_i holds N pieces of data: M_i and 149 H_j (j != i). Next they copmute H_i = Hash(M_i) and check if H_i matches at least 67% of H_j. If it does, P_i assumes that the broadcast has been successful. Otherwise, P_i reports P_1 to SC and abort the ceremony.
4. P_1 is removed from the next ceremony (and is potentially slashed) if it is reported by a majority of validators on SC.

[AlastairHolmes]

Do you mean this: "In turn, P150 could send P2 D_b as the data it received from P1, while sending D_a to every other node. In this case, P2 would be the only node to report P1, and would get (unfairly) slashed."?

[msgmaxim]

Updated, thanks.

[morelazers]

The solution, I think, is to submit the to contradicting signed pieces of data along with the report, so a single report would be enough since all other nodes could verify it. Would this verification be hard/annoying to do on SC?

What is the form that you expect the data to have here? It's difficult to say how hard it would be without some more information on any transformations that the SC might have to apply in order to verify the condition.

[msgmaxim]

This is more of a high level idea. We can submit in whatever way is easier to process on SC. I didn't think too much about the exact format, but it could looks something like:

{
  "reported_node": "<node_id>",
  "data_1": {
    "key_id": "<...>",
    "data:": "<...>",
  },
  "signature_1": "<...>",
  "data_2": {
    "key_id": "<...>",
    "data:": "<...>",
  },
  "signature_2": "<...>",
}

The nodes would need to check the validity of signatures and that data is different for the same key_id

[morelazers]

This looks fine to me, I don't think it would be particularly difficult to implement this.

[kylezs]

The problem this is trying to solve is not really clear to me - my response is based on what I think this is trying to solve.

If A broadcasts D to everyone except B, and broadcasts D' to B, then A can be slashed for this, right?

If B assumes it receives the correct data from A, and uses it, the network will see that the data B is using is incorrect. It seems there's an assumption that we always slash on nodes that use the incorrect data, and so we should always avoid using incorrect data (i.e. by doing something like you've described above, and check immediately). I'd argue this is more costly than necessary.

The assumption that B is automatically the malicious node if it is using incorrect data should not be the case. B might be malicious, but B can also provide a defence, by providing the data signed by A, that was invalid. No consensus is required, it's cryptographically true.

[msgmaxim]

then A can be slashed for this, right?

Yes, but proving that A needs to be slashed is not trivial

the network will see that the data B is using is incorrect.

The protocol is such that it is not obvious to others that B is using incorrect A's data. In the best case, they will say "B is doing something wrong, abort". But I think the most likely case is parties will generate a key, but will not be able to sign anything.

[kylezs]

Yeah, that's basically my broader point. Perhaps we should rethink at the protocol level how we slash in this scenario. Because what you're describing (while I think it would work) seems a little overkill. We'd be doing it every round, whereas slashable events ought to be pretty rare. So if we have to go through a bit of an "accuse/defend" process rarely - then we could do that, but yeah, I'm aware it's not trivial

[morelazers]

If the majority of nodes (P2 and P3 in this case) report P1, P1 gets slashed. If P2 is in the minority, it gets slashed instead.

I wonder why we care about this? If P2 receives two pieces of data signed by the same Validator, for the same ceremony, the State Chain can verify this and automatically slash the signer. Why do you think we might need to differentiate majority/minority voters here?

The point of a signature is to commit to some data. If you have committed to two pieces of data which contradict each other, we don't need a vote to slash you.

[msgmaxim]

The solution, I think, is to submit the to contradicting signed pieces of data along with the report, so a single report would be enough since all other nodes could verify it.

Yes, this part makes voting unnecessary