Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Adaptive Signing Set Selection #682

Open
tbraun96 opened this issue Jul 14, 2023 · 2 comments
Open

Adaptive Signing Set Selection #682

tbraun96 opened this issue Jul 14, 2023 · 2 comments

Comments

@tbraun96
Copy link
Contributor

tbraun96 commented Jul 14, 2023

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
Copy link
Contributor Author

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
Copy link
Contributor

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?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants