Refactor Proposal: Split FROST Share Generation into Two Operations

frost-refactor.md

Refactor Proposal: Split FROST Share Generation into Two Operations

Motivation

The current implementation of the secp256k1_frost_share_gen function combines the generation of Verifiable Secret Sharing (VSS) coefficient commitments and the generation of shares. This proposal aims to split these two operations into separate functions, which will provide a safer and more flexible API.

Motivations for this refactor include:

1. The session_id parameter was confusing and easy to misuse.
2. The FROST paper requires coefficient commitments and a proof-of-knowledge for the first commitment be distributed prior to shares. This change updates the APIs to conform to the paper specification, which it did not before.
3. The updated share generation function now requires the VSS, including the proof-of-knowledge, to ensure the share is not generated until those items have been received, commited to, and the proof-of-knowledge has been verified.
4. Using a dedicated authentication key for the recipient_pk instead of using the first coefficient commitment is safer; otherwise, the authentication key's private key is split and distributed in the process, which might not be desired or expected.

Proposed Changes

1. Introduce a new data structure, secp256k1_frost_vss, to store the VSS commitments and proof-of-knowledge.
2. Introduce a new function, secp256k1_frost_vss_gen, to generate a secp256k1_frost_vss struct.
3. Modify the existing secp256k1_frost_share_gen function to generate a share for a participant if their secp256k1_frost_vss struct verifies.

New Data Structure: secp256k1_frost_vss

typedef struct {
    secp256k1_pubkey *vss_commitments;
    size_t num_commitments;
    const unsigned char *sig64;
} secp256k1_frost_vss;

New Function: secp256k1_frost_vss_gen

SECP256K1_API int secp256k1_frost_vss_gen(
    const secp256k1_context *ctx,
    secp256k1_frost_vss *vss,
    const unsigned char *seed,
    size_t threshold
) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);

Description

Generates the VSS coefficient commitments and a proof-of-knowledge.

Parameters

• ctx: Pointer to a context object initialized for verification.
• vss: A VSS struct.
• seed: A random seed.
• threshold: The minimum number of signers required to produce a signature.

Original Function: secp256k1_frost_share_gen (for reference)

SECP256K1_API int secp256k1_frost_share_gen(
    const secp256k1_context *ctx,
    secp256k1_pubkey *vss_commitment,
    secp256k1_frost_share *share,
    const unsigned char *session_id32,
    const secp256k1_keypair *keypair,
    const secp256k1_xonly_pubkey *recipient_pk,
    size_t threshold
) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4) SECP256K1_ARG_NONNULL(5) SECP256K1_ARG_NONNULL(6);

Modified Function: secp256k1_frost_share_gen

SECP256K1_API int secp256k1_frost_share_gen(
    const secp256k1_context *ctx,
    secp256k1_frost_share *share,
    const secp256k1_frost_vss *vss,
    const secp256k1_xonly_pubkey *recipient_pk,
    const unsigned char *seed,
    size_t threshold
) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4) SECP256K1_ARG_NONNULL(5);

Description

This original function combined the generation of VSS coefficients and the generation of shares into a single operation. The proposed refactor aims to separate these two operations into different functions, resulting in a safer and more flexible API that conforms more closely to the FROST protocol as described in the paper.

This function is also updated to verify the VSS proof-of-knowledge prior to generating shares for a participant. In addition, a seed is used to generate coefficients, like in secp256k1_frost_vss_gen, which removes the need for a keypair that is overextended in the existing APIs where it serves as an authentication key, Shamir secret, and a component of the coefficient generation seed.

Parameters

• ctx: Pointer to a context object initialized for verification.
• share: Pointer to the key generation share.
• vss: The VSS struct for the recipient.
• recipient_pk: Pointer to the public key of the share recipient.
• seed: The random seed of the participiant generating the share. This must be the same one used by the participant in secp256k1_frost_vss_gen.
• threshold: The minimum number of signers required to produce a signature.

Additional Enhancement: Encrypt Shares with ChaCha20-Poly1305

To further enhance the security of the share generation and distribution process, the authentication key is used to encrypt the shares with the ChaCha20-Poly1305 encryption scheme. This symmetric encryption provides confidentiality and integrity, helping ensure that only the intended recipient can decrypt and access the share.

The proposal makes sense to me overall. In particular, I think it's much better to do POK proving and verification inside of the API instead of asking the user to come up with something. Not sure if this feature implies that we need to split the function as you suggest (since PoK verification could also happen in secp256k1_frost_share_verify). Also, the current API is somewhat clunky because you only want to provide vss_commitment to share_gen once (as e.g. demonstrated in the example).

The session_id parameter was confusing and easy to misuse.

In what way is it better now? How does a user create the seed, or is it just session_id renamed?

a safer and more flexible API

In what way is it more flexible? It seems to imply an additional communication roundtrip.

Another consideration with the new API is what happens if you give different arguments to vss_gen and share_gen. But as far as I can see that's not a problem for security.

I don't see how vss struct is supposed to work. How does vss_gen know where to place the data in the vss_commitments and sig64 arrays. And similarly, how does share_gen know which entry in vss it should verify against? This would also imply an order on the signers which iirc we tried to avoid.

Not sure if this feature implies that we need to split the function as you suggest (since PoK verification could also happen in secp256k1_frost_share_verify).

Yes, we could do the PoK verification without splitting the function.

In what way is it better now? How does a user create the seed, or is it just session_id renamed?

I had originally thought that a single keypair could be reused across many sessions, which is why there's both a session_id and a keypair, but I now think that is confusing and easily misused. With the current API, there's 2 sources of entropy: the session_id and the private key of the keypair. With the new API it's consolidated to the seed, although now that I think about it session_id might actually be a better name than seed. But the main idea is that there be a single source of entropy instead of 2, and to no longer use a keypair for the first coefficient/coefficient commitment of the polynomial that is provided as an argument, but to instead derive the entire polynomial from a seed.

In what way is it more flexible? It seems to imply an additional communication roundtrip.

In the current API, shares and coefficient commitments are sent together in the same round, however, the paper specifies that commitments be sent prior to the shares:

Current API

(1) send shares + VSS
(2) send PoK/broadcast-proof/sign(vss_hash)

Paper

(1) send PoK/sign(context_string) + VSS
(2) send shares (+ broadcast proof/sign(vss_hash))*

*broadcast proof is not specified by the paper but it could be sent here by signing a VSS hash

It's more flexible because with the proposed API the VSS can be generated prior to knowing the public keys of any participants, whereas with the current API, to generate the VSS, it always requires a recipient_pk.

I don't see how vss struct is supposed to work. How does vss_gen know where to place the data in the vss_commitments and sig64 arrays. And similarly, how does share_gen know which entry in vss it should verify against? This would also imply an order on the signers which iirc we tried to avoid.

secp256k1_frost_vss would represent a single participant's commitments, not the entire set, and sig64 would be that participant's signature over the context string (i.e. the PoK).

the main idea is that there be a single source of entropy instead of 2, and to no longer use a keypair for the first coefficient/coefficient commitment of the polynomial that is provided as an argument, but to instead derive the entire polynomial from a seed.

Ah got it, makes sense. I like the term seed.

In the current API, shares and coefficient commitments are sent together in the same round, however, the paper specifies that commitments be sent prior to the shares:

Yes, but I'm not aware of a reason that the scheme and corresponding security proof can't be rearranged such that it matches the current implementation.

It's more flexible because with the proposed API the VSS can be generated prior to knowing the public keys of any participants

Ah, makes sense. Thanks to your explanation I can also see now how this doesn't (seem to) introduce a roundtrip. With the changed API, we can send the shares and "broadcast proof" in parallel.

secp256k1_frost_vss would represent a single participant's commitments, not the entire set, and sig64 would be that participant's signature over the context string (i.e. the PoK).

Ah ok, that makes sense. Probably better to use singular "vss_commitment" in the struct then (at least this is what confused me).

Yes, but I'm not aware of a reason that the scheme and corresponding security proof can't be rearranged such that it matches the current implementation.

If it's okay to (1) send the shares along with the commitments in the first round and (2) send the PoK in the second round instead of the first round, then the current implementation might better in this respect because it is more space efficient due to combining the PoK with the broadcast proof as opposed to sending them separately (i.e. PoK/sign(context_string) in round 1 and broadcast-proof/sign(vss_hash) in round 2).

As discussed, we could still rework the API to check the PoK in share_verify. We could also still use the other proposed refactor ideas (replacing keypair and session_id with seed and splitting out vss_gen into its own function) while still preserving this one aspect of the current implementation if we think the deviation from the paper is secure and is an improvement due to space efficiency or other reasons.

Thanks for bringing up space efficiency - I hadn't considered that. But I don't think that minor space efficiency improvements during the DKG are particularly important. In that case, I think it makes sense to prefer the simpler variant that stays closer to the paper.

In that case, I think it makes sense to prefer the simpler variant that stays closer to the paper.

Ok cool, that's what I was thinking as well.

About the seed variable in secp256k1_frost_vss_gen it should probably be named seed32 to say that it's 32 bytes.

I like that by reusing the seed32 variable in secp256k1_frost_vss_gen we can re-generate the private coefficients without storing them in a dynamically sized array in some struct.

Overall, I really like this refactor; it aligns the implementation with the paper itself.
I'm not sure I understand the comment at the end about the encryption, what is the DH that you plan on doing?
I do like the idea of us doing the encryption, even though we can't do the broadcast (although we could add some API for transcript verification that will show the users that they need to make sure all the transcripts are the same)

I'm not sure I understand the comment at the end about the encryption, what is the DH that you plan on doing?

It would be a DH between the participant authentication keys. For example, when Alice sends a share to Bob, Alice would derive a shared secret from her private auth key and Bob's public auth key, and use that to encrypt the share.