[SPEC] Generate signature only from one of the signing sets

[1xstj]

Overview

Currently we generate multiple signing sets for for signing the same unsigned proposals. The goal is to successfully sign proposals immediately in the event that some authorities are not present. For example, if we have authorities: [1,2,3] and we only generate a single signing set (1,2), then if either party is absent, we will not be able to sign until we handle a misbehaviour. Instead, we brute force sign with multiple sets. For n authorities, to cover all signing sets of size t+1, we need to generate (n choose (t+1)) sets.

Problems

1. This approach does not scale well for large t/n
2. This leads to too many messages being send back and forth
3. The signing set index may not always align on different nodes, leading to signing round failure

Proposed variation

We continue to generate multiple signing sets, but only one of these signing sets will be used to generate signature

Proposed workflow

1. Generate signing sets as before
2. Select one signing set from the list of all generated signing sets, to ensure we select same value across different nodes and to avoid using same set again, we should consider expanding the seed using the current finalised block

let mut seed = local_key.public_key().to_bytes(true)[1..].to_vec();
seed.extend(header.current_finalised_block_number());

Since the public key and finalised block is shared among all nodes, this should lead to selection of the same signing set. This also allows us to eliminate the use of async_index to seperate signing sets.

[shekohex]

I agree, and approve this change.

[drewstone]

My only qualm with this is we fail to introduce redundancy when the selected signing set is faulty.

[drewstone]

The main issues at hand are:

1. (n choose k) is really large as n and k grow. This is why we cap it at 16 (or 32) but perhaps there's a better algorithm here to use. For example, we could take into account reputations of the nodes when selecting for signing.. We ought to update reputations when we sign things too in that case.
2. As we add redundancy, say by having >=2 sets sign the same proposals, we start to increase the message bandwidth over the network. This grows quite large (not sure how large or how much of an issue this is..). We do plan to grow the sets to 15 out of 30 (or 14 out of 30). We shouldn't avoid this and should consider the bandwidth will increase substantially.

[drewstone]

I think what we could have to add parallelization is to:

• Select the signing sets and cap at 16 or 32 (using seed and finalized block)
• Assign each signing different proposals to sign.
• Mark locally when "I am signing some proposal" and don't overwrite it until finished or timed out.
• Continue back to initial step.

[drewstone]

Another idea:

1. Select signing sets with Hash(seed, final_block_number) and cap at 16. (This generates different sets {(1,2), (2,3), (1,3)} in different orders each finalized block)

2. Look at the index of my signing sets. (If I am Alice (1) I am in {0, 2})

3. Now, for each index of my signing sets, I want to permute the set of proposals and create copies of these permuted proposals. (This generates 2 sets of unsigned proposals by {0,2}..)

We can permute these by simply right shifting the proposals by the index of one's set.

4. Now in stages I do the following

Protocol

1. I always continue to check the chain to see if the proposal I'm about to start signing has been signed. If it has, I mark the state as finished and move on. (use import_block_notifications to learn of these events faster).
2. I take my unsigned proposal sets (possibly staggered) and I pop the first proposal from stack (or as a queue) and I begin signing.
3. I do this repeatedly, returning to step 1 after finishing each proposal.

Intention

The intention here is to distribute the proposals to be signed over different sets. Since we permute the unsigned proposal set by a known index to each party in the same set, the will possibly see a different ordering of proposals. Then we can sign these proposals in theory, in parallel (we need to look at how the proposals are ordered truly). If all parties are participating properly, we should be able to sign proposals quite quickly and should buffer signing each successive proposal by some heuristic time to avoid too much redundancy.

We have redundancy now because if Alice and Bob fail to sign some proposal, Alice and Charlie might start signing it after finishing some other proposals and after noticing that it is not signed on chain. Alice and Charlie won't necessarily have to wait for a timeout (they've finished their other jobs and now they take on the unfinished jobs). This is all hypothetical of course.

Issues

• When there is only 1 proposal (or there is k-1 proposals for k sets), we should figure out how to delay other sets from starting to sign the proposal that has already been allocated/assigned. We can potentially solve this using a silly heuristic by delaying the set of index k and above. In the example where there is 1 proposal:
• (2,3) would be delayed by some fixed period T
• (1,3) would be delayed some fixed period T * 2