FROST key storage format

[LLFourn]

What are applications meant to store on disk to persist the FROST key and share. I have ideas about this but just noting this down since it's probably in scope for this spec.

[real-or-random]

I have ideas about this

Would you like to share them?

[nickfarrow]

Just confirming i'm on the same page here, is this referring to what data is to be stored, rather than how it would be stored (format) like https://github.com/jonasnick/bip-frost-dkg/issues/5?

I've been thinking about the concept of a polynomial identifier that allows parties to determine whether their secret share is "compatible" with another party's. Particularly important later for frost extensions with different structures controlling the same secret, such as subsets of parties doing things like key-rotation or enrollment.

One idea is to evaluate the public polynomial at some standard compatibility-index compatibility_id = F(Scalar::from_bytes(b'frost-compatibility-index')) Parties with the same compatibility index evaluation know they share the same public poly and so their secret shares are compatible.

[LLFourn]

Just confirming i'm on the same page here, is this referring to what data is to be stored, rather than how it would be stored (format) like #5?

This is about what and how applications should store the public FROST key not user backups. I mentioned in the OP the share as well but I guess that's pretty straightforward!

Would you like to share them?

Yes! Taking a relevant point from the current spec:

For each signer, the DKG has three outputs: a secret share, the shared public key, and individual public keys for partial signature verification.

This is what we have implemented atm but I think returning public keys for individuals and the shared public key is suboptimal if we keep an eye on the future. You can just return (and persist) the public polynomial from which you can generate each verification share (this obviously includes the public key too). This makes invalid states unrepresentable (e.g. the t+1 share not being on the same polynomial as the first t shares). Another upside is that you don't need to know how many signers there are out there because that can change over time:

1. Protocols may enroll new parities with new shares.
2. You may recover from a set of t shares and slowly find out about the other shares by interacting with those devices.

Just storing the polynomial and lazily producing the verification shares means we don't change the persisted data over time (at least until the actual access structure changes). Of course the downside is that the verification shares take a t multi-mul to produce which may dominate the verification time. Performance sensitive applications can cache these verification shares even on disk if they want which I think fully addresses the issue.

One idea is to evaluate the public polynomial at some standard compatibility-index compatibility_id = F(Scalar::from_bytes(b'frost-compatibility-index')) Parties with the same compatibility index evaluation know they share the same public poly and so their secret shares are compatible.

I think it would be better just to hash the polynomial coefficients. Two polynomials can have the same value at frost-compatibility-index. If you don't care about collision resistance then it's fine but hashing is also faster and simpler.

[jonasnick]

You can just return (and persist) the public polynomial from which you can generate each verification share (this obviously includes the public key too).

Interesting idea. This also slightly helps in an EncPedPop recovery when you've only backed up secret data. Instead of asking for n verification shares ("individual public keys") and the shared public key, you ask for the VSS commitment, i.e., t public coefficients. You can then also verify your share again against the public VSS commitment that was sent to you.

@llfourn Can you explain

This makes invalid states unrepresentable (e.g. the t+1 share not being on the same polynomial as the first t shares)

In what scenario does this help?

[LLFourn]

@LLFourn Can you explain

This makes invalid states unrepresentable (e.g. the t+1 share not being on the same polynomial as the first t shares)

In what scenario does this help?

Just in general the representation that makes invalid states unrepresentable is usually the right design choice. In this case it excludes the possibility of verifying correctly t signature shares at distinct indexes under having them not form a valid signature. If instead of deserializing (t, public_key, verification_shares) you just deserialize (polynomial) it is strictly impossible for this to happen.