Shamir BLS thresholds

I understand that NNS generates the share of the secret key for nodes in a subnet etc. Furthermore it is this key material that is used for signing purposes by the consensus algorithm within a subnet. But if the # of nodes in the subnet keep changing over time how is threshold for the BLS signatures managed?

For instance if the subnet is created by 10 nodes to start with,

  • What threshold is used for the key generation?
  • How does this change if the 10 nodes becomes say 50 over time?

Clearly we would like to tolerate 1/3 of the nodes being malicious. If we start with 30 nodes then we want the threshold to be min 10 nodes. But when this number increases to say 100 how is the threshold increased to tolerate malicious actors.

3 Likes

I was wondering about the similar thing. Thresholds can’t change so I am not sure how this thing is bootstrapped to begin with.

Whenever subnet membership changes, the consensus protocol would “reshare” DKG keys from old set of nodes to the new set of nodes, so that everyone get new secrets and yet the subnet public key remains unchanged.

More details can be found in this paper Non-interactive distributed key generation and key resharing

5 Likes

Thanks. I think, I understand how the re-sharing is done. Let’s say the subnet is created with 10 nodes. Each node receives a secret share. What is the Shamir threshold in this case? Is it something like (7, 10)? If that is the case when more nodes are added, say 10 → 30, original (t, n) cannot change because that would mean changing the existing secret shares. Now needing only 7/30 nodes to verify BLS signatures makes it vulnerable, no? What am I missing?

Say nodes goes from 10 → 31, and we use threshold 2f+1 for nodes = 3f+1, then the original threshold is (7, 10), and new threshold is (21, 31). The secrets are “re-shared” from original 10 nodes to the new 31 nodes with the new threshold 21.

Edit:
Further more, the original 10 nodes and the new 31 nodes may not have any overlap. This allows us to bootstrap new subnets from an existing subnet by running NiDKG protocol on the existing one and reshare to the nodes in the yet to be formed new subnet.

2 Likes

Thanks. In essence when the subnet goes from 10 → 31 all the secret shares for all the nodes are refreshed, so to speak. Now does this mean that while this refresh process is taking place that the original 10 nodes cannot serve/handle external requests because their shares are being refreshed? Or is this non-disruptive?

Old nodes continue to work until the DKG resharing is finished, and then the new set of nodes can start. Node removal is always non-disruptive, but node addition means there are new nodes requiring syncing from existing nodes, which may take some time (i.e. a few minutes) before they can catch up with the rest of the nodes. I think by now the boundary nodes are smart enough to avoid forwarding user messages to nodes that are not yet fully caught up, so disruption is kept to the minimal.

In any case, DKG resharing is non-disruptive, but adding new nodes will often require state syncing.

1 Like