Signers Selection

[shekohex]

Overview

Given a DKG with $t$-of-$n$, and Given $n$ of participants (each with a KeyShare), choose $t$ participant randomly* to participate and run the signing protocol.

Random* Selection would be deterministic between all $n$ nodes, to pick the $t$ signers. How? Basically, they will all construct a seed that they all share. Simply Let $S$ is the seed, where $S = keccak256(eId, retryId)$.

My Example

Step 1: Keygen

let e_id_bytes = b"dfns-cggmp21-keygen";
let e_id = cggmp21::ExecutionId::new(&e_id_bytes);
// a list of participants public keys, sorted across all participants by public key.
let participants_pub_keys = vec![ ... ];
let participants = participants_pub_keys.iter().enumarate().map(|(i, _)| i as u16).collect();
let i = participants_pub_keys.position(|pubkey| pubkey == my_pubkey).unwrap();
let n = participants_pub_keys.len();
let t = 3;
let incomplete_key_share = cggmp21::keygen::<Secp256k1>(eid, i, n)
    .set_threshold(t)
    .start(&mut OsRng, party)
    .await?;

let pregenerated_primes = cggmp21::PregeneratedPrimes::generate(&mut OsRng);
let e_id_bytes = b"dfns-cggmp21-aux-info";
let e_id = cggmp21::ExecutionId::new(&e_id_bytes);
let aux_info = cggmp21::aux_info_gen(eid, i, n, pregenerated_primes)
    .start(&mut OsRng, party)
    .await?;

let my_key_share = cggmp21::KeyShare::make(incomplete_key_share, aux_info)?;

When I did try this, I tried the very naive way like so:

let e_id_bytes = b"dfns-cggmp21-signing";
let retry_id = 0; // auto increment if we failed to sign for some reason.
let seed = keecak_256(&[&e_id_bytes[..], &retry_id.to_be_bytes()[..]].concat());
let rng = rand::rngs::StdRng::from_seed(&seed);
// a list of participants public keys, sorted across all participants by public key.
let participants_pub_keys = vec![ ... ];
// we convert the participants list to a list of indecies.
let participants = [0, 1, 2, 3, 4]; // n = 5
let t = 3;
let signers = participants.choose_multiple(&mut rng, t).cloned().collect();
// Now, let say the signers are
let signers = [1, 2, 4];
// How do I calculate `i` in this case? From the signers list or the participants list?
let i = ?;
// this would be 
let parties_indexes_at_keygen = ?;

let data_to_sign = cggmp21::DataToSign::digest::<Sha256>(b"data to be signed");
let eid = cggmp21::ExecutionId::new(&e_id_bytes);
let signature = cggmp21::signing(eid, i, &parties_indexes_at_keygen, &my_key_share)
    .sign(&mut OsRng, party, data_to_sign)
    .await?;

Questions and confusion

1. In my case, i would be from the signer set? Or from the participants?

   let i = participants_pub_keys.position(|pubkey| pubkey == my_pubkey).unwrap();

   or how?

2. parties_indexes_at_keygen are the participants list from the keygen, right?

[survived]

The library doesn't care how set of signers to perform signing is chosen, multiple valid strategies are possible, including the one you mentioned. Just one note: you can't use rand::rngs::StdRng to deterministically derive the same set of signers from the same seed on several machines. The documentation states that:

The algorithm is deterministic but should not be considered reproducible due to dependence on configuration and possible replacement in future library versions. For a secure reproducible generator, we recommend use of the rand_chacha crate directly.

So I'd also suggest to use rand_chacha instead.

Now, back to how indexes should be chosen. Suppose you generated a key shared between 5 signers with indexes [0, 1, 2, 3, 4], now you're doing signing between signers with indexes parties_indexes_at_keygen = [1, 3, 4] (indexes that they have occupied at keygen). In this case, index i at signing would correspond to signer that occupied index parties_indexes_at_keygen[i] at keygen, i.e.:

• i=0 at signing corresponds to the signer with index parties_indexes_at_keygen[0] = 1 at keygen
• i=1 at signing corresponds to the signer with index parties_indexes_at_keygen[1] = 3 at keygen
• i=2 at signing corresponds to the signer with index parties_indexes_at_keygen[2] = 4 at keygen

[shekohex]

So I'd also suggest to use rand_chacha instead.

TIL! Thank you for this advice, I will indeed use it instead.

And thanks again for your explanation, I followed your instruction, and Indeed it works now. I will share the code here just if anyone else needed it.

/// Given a list of participants, choose `t` of them and return the index of the current participant
/// and the indices of the chosen participants, as well as a mapping from the index to the account
/// id.
///
/// # Errors
/// If we are not selected to sign the message it will return an error
/// [`gadget_common::Error::ParticipantNotSelected`].
///
/// # Panics
/// If the current participant is not in the list of participants it will panic.
pub fn choose_signers<R: rand::Rng>(
    rng: &mut R,
    my_account_id: &AccountId,
    participants: &[AccountId],
    t: u16,
) -> Result<(u16, Vec<u16>, HashMap<UserID, AccountId>), gadget_common::Error> {
    let selected_participants = participants
        .choose_multiple(rng, t as usize)
        .cloned()
        .collect::<Vec<_>>();

    let selected_participants_indices = selected_participants
        .iter()
        .map(|p| participants.iter().position(|x| x == p).unwrap() as u16)
        .collect::<Vec<_>>();

    let j = participants
        .iter()
        .position(|p| p == my_account_id)
        .expect("Should exist") as u16;

    let i = selected_participants_indices
        .iter()
        .position(|p| p == &j)
        .map(|i| i as u16)
        .ok_or_else(|| gadget_common::Error::ParticipantNotSelected {
            id: *my_account_id,
            reason: String::from("we are not selected to sign"),
        })?;

    let user_id_to_account_id_mapping = selected_participants
        .clone()
        .into_iter()
        .enumerate()
        .map(|(i, p)| (i as UserID, p))
        .collect();
    Ok((
        i,
        selected_participants_indices,
        user_id_to_account_id_mapping,
    ))
}

Note: AccountIds are just public keys.

I will close this issue as solved. Thanks again @survived !