Adaptive Signing Set Selection

[tbraun96]

We want to be able to choose signing sets, symmetrically, containing t+1 signers. However, we also want to be able to choose the best signing set(s), which will be based not necessarily on just the reputation, but rather, on whether or not all the nodes within that signing set are.

Previously, we may have chosen a signing set [0, 2, 3]. This means nodes 0, 2, and 3, (but NOT 1), would participate in signing. This would be selected without keeping into mind whether or not nodes [0, 2, 3] were online or not. Thus, if any of these nodes were offline or suddenly became offline, the signing protocol would fail even if their reputations were good beforehand. We need a solution to prevent running protocols for signing sets that won't converge to completion. Enter adaptive signing set selection (AXS).

In AXS, we begin with a t and k value. The k value is the number of proposed signing sets. We generate these signing sets as we do here: https://github.com/webb-tools/dkg-substrate/blob/42da1bc7cf9cdae1d3678399e78d7b3cc5c19836/dkg-gadget/src/signing_manager/mod.rs#L208-L220

Once we generate k proposed signing sets (PSS), we then gossip these signing sets via the gossiping layer. Beforehand, assuming t=2 and k=2, each peer sets their state as such:

[Alice]
PSS-0: [alice: 1, bob: 0, charlie: 0] <--- This signing set has Alice, Bob, and Charlie. Alice sets to 1 since she knows she is online
PSS-1: [alice: 1, eve: 0, charlie: 0]

[Bob]
PSS-0: [alice: 0, bob: 1, charlie: 0]
PSS-1: [alice: 0, eve: 0, charlie: 0] < --- Bob is not in this list, so, he will not listen for this set

[Charlie]
PSS-0: [alice: 0, bob: 0, charlie: 1]
PSS-1: [alice: 0, eve: 0, charlie: 1]

[Eve]
PSS-0: [alice: 0, bob: 0, charlie: 0] <--- Eve is not in this list, so, she will not listen for this set
PSS-1: [alice: 0, eve: 1, charlie: 0]

Each peer sets a value of 1 for a received gossiping message from another peer, and keeps at 0 for a peer whom they have not heard from.

The moment any of the peers fill up an entire proposed signing set with 1's (meaning they have heard from all those peers in the proposed signing set), they immediately begin an async protocol for that signing set since we know there is (with very high certainty) bidirectional communication between each of these nodes. Importantly, we endow such an async protocol with a signing set ID, or SSID, which is similar to our old use of the async_index.

Discussion

We do not necessarily want to propose signing sets that have actors we know locally we cannot reach. When generating randomly, including disconnected peers is a possibility. This is why we should set a k value to e.g., 3, that way, we increase the likelihood that such actors eventually end up in a (symmetric!) signing set. Alternatively, we can keep k to a lower value, and, each node will also (ontop of the symmetric signing sets) construct a potentially-non-symmetric signing set at the end of the proposed signing set list that removes the errored nodes. That way, the only way this final signing set is symmetric is if ALL the nodes also see the same errored nodes. This final signing set, which we can call the wildcard set, will only work when the same node is registered as dropped off for all the nodes.

[tbraun96]

Using multiple signing sets has the benefit of fault-tolerance. Additionally, by including the wildcard set, we have redundancy that covers the case where the same node is unreachable for all nodes. Finally, by using the gossipping engine beforehand to determine connectivity, we increase the likelihood that we choose a signing that converges to completion.

[drewstone]

How often are blames cleared and are the cleared within a single session? What if a node falls off and joins back the network, will their blame be removed?

Scenario that likely results in STALL, again...

• Alice, Bob, Charlie, Dave, Eve (4-out-of-5)
• Alice drops off and Charlie drops off either same or different times to cause blame. Both are blamed.
• Charlie rejoins, handshakes. What set is created?

Other considerations

• What happens if there are not enough unblamed parties to create a set?
• What happens if different parties have different blame views?
• What is the expected behaviour in these cases?