Frost threshold signatures

Ed keys everywhere

In iroh we are using Ed25519 keypairs a lot. Nodes are identified by ed keypairs, documents are identified by keypairs, authors, namespaces etc. A gossip topic is an arbitrary 32 byte blob, which conveniently fits an ed public key.

With pkarr we have a great mechanism to publish information about keypairs. We are running a dns server, and we can also use the bittorrent mainline DHT for a fully peer to peer mechanism to publish and resolve pkarr packets.

Other recent protocols such as nostr are also using ed25519 keypairs.

How to keep the keys safe

A problem that frequently comes up when using a keypair to control access to an identity or a resource is how to keep the private key safe.

Some keypairs are ephemeral and don't need to be safeguarded much.

Some will have significant security implications from the start (e.g. a keypair associated with access to a crypto wallet).

And some will initially be of low value, but might grow in value over time (e.g. a social media account).

In most cases, there is a constant conflict between the need to keep the keys safe and the need to constantly access the private key for signing messages.

Existing solutions

Secure key storage

Most modern hardware supports secure storage for private keys. However, access to such secure storage locations is highly platform dependent. Also, while secure storage makes the key relatively inaccessible, it does not protect against key loss. It also does not provide a mechanism for revocation.

Delegation schemes

With the tools of public key cryptography you can come up with delegation schemes where a rarely used master key is used to delegate to a more frequently used keypair that can be revoked using the master key.

Local file system

The default way to store a private key is to just store it in a hidden directory in your local file system. While this is not extremely secure, it is still highly preferable to not using encryption at all. In many scenarios, e.g. device loss or theft, this is perfectly safe for low to medium value keypairs.

Threshold signatures

I was vaguely aware that something like threshold signatures exist. This is - very roughly speaking - a scheme where you split the private key into multiple parts called shares, and need a certain number of these shares to sign a message. Since the shares never have to be in one place, this provides safety in case a single share gets compromised.

What I did not know however is that the generated signature is fully compatible with normal ed25519 signatures. So you can sign a message with a threshold signature scheme and then validate the signature as usual using the ed public key.

This means that threshold signatures are compatible with existing infrastructure such as bep-0044 in the mainline DHT, pkarr, and nostr.

They are also compatible with all the other places in iroh where we are using ed keypairs.

Creating key shares

The reason I got interested in threshold signatures is the backwards compatibility.

There are various ways to create key shares. One I find interesting in particular is the ability to just take an existing ed private key and generate key shares from it.

Other ways include a scheme that requires a central trusted dealer, so basically a place that is considered secure at generation time and a way to securely transfer the shares.

And as the most advanced option a Distributed Key Generation scheme that allows generating the key shares directly on the target devices without ever having them all in one place.

The advanced key share generation schemes are certainly interesting, but given that we are starting off with ed private keys in hidden directories, even the trusted dealer approach is fine for an initial exploration.

Exploring the frost_ed25519 crate

The FROST scheme is implemented in the paper FROST: Flexible Round-Optimized Schnorr Threshold Signatures. Luckily for me there is also a crate implementing the scheme, that is pretty approachable.

Local operations - split and reconstruct

So I implemented a little command line tool to split existing iroh keys into key shares.

I also implemented a way to reconstruct a signing key from a sufficient number of key shares. Note that you can't reconstruct the ed private key, but just a key that can be used for signing.

This is all easy enough, but if the key shares are all on the same file system the scheme just adds complexity but no additional security.

So we need a way to distribute the key shares on multiple machines that can be physically separated.

Iroh is a library that can get you a fast and encrypted connection between any two devices anywhere in the world. So this should be easy.

Remote operations - sign and cosign

For using the key shares, there are two possible roles. The signer actively wants to sign a message, e.g. to publish it somewhere, but does not have the entire private key. Depending on the exact parameters for the key shares, it needs one more more co-signers.

The co-signer is a little daemon that just has a number of key shares. For this exploration it will just wait for incoming co-sign requests and sign them.

The protocol

The rough protocol looks like this

• The signer sends a request to its co-signers to sign a message for a public key.
• Each co-signer that has a key share for the requested public key answers with a commitment and remembers a corresponding nonce.
• The signer waits until it gets the required number of commitments. It then creates a signing package from all the commitments and the message and sends that to all co-signers.
• all co-signers sign the signing package and return a signature share.
• as soon as the signer has enough signing shares, it can create a signature.

Co-Signer

The co-signer in this scheme acts as a server. It needs to locally store its iroh keypair to have a stable id. It also needs to publish discovery information. It does not, however, have to look up discovery information since it does not call other nodes.

    let discovery = PkarrPublisher::n0_dns(secret_key.clone());
    let endpoint = iroh_net::endpoint::Endpoint::builder()
        .alpns(vec![COSIGN_ALPN.to_vec()])
        .secret_key(secret_key)
        .discovery(Box::new(discovery))
        .bind()
        .await?;

Once the endpoint is created, it needs to run a normal accept loop where it just handles incoming co-sign requests

    while let Some(incoming) = endpoint.accept().await {
        let data_path = data_path.clone();
        tokio::task::spawn(async {
            if let Err(cause) = handle_cosign_request(incoming, data_path).await {
                tracing::error!("Error handling cosign request: {:?}", cause);
            }
        });
    }

Handling a request is described above.

To run the co-sign daemon, you just need to run the co-sign daemon with a directory containing a key share.

> cargo run cosign --data-path b
Can cosign for following keys
- 25mzjgjlrcrma7wkm4l3fjv2afcs53cvmmyw3v2uwwt2dczsinaa (min 2 signers)

Listening on 4bqd4r3fivo5722twrvmlwcs7wjlnv6xf567lyweb7yyb34x37ba

Signer

The signer in this scheme acts as client. It does not need a stable node id, but it needs the ability to look up the addresses of other nodes.

    let discovery = DnsDiscovery::n0_dns();
    let endpoint = iroh_net::endpoint::Endpoint::builder()
        .secret_key(secret_key)
        .discovery(Box::new(discovery))
        .bind()
        .await?;

It first calls out to all configured co-signers and sends them a co-sign request for the key to be signed for. Then it waits until it has a sufficient number of valid responses and starts with the next stage.

    let cosigners = futures::stream::iter(args.cosigners.iter())
        .map(|cosigner| send_cosign_request_round1(&endpoint, &cosigner, &args.key))
        .buffer_unordered(10)
        .filter_map(|res| async {
            match res {
                Ok(res) => Some(res),
                Err(cause) => {
                    tracing::warn!("Error sending cosign request: {:?}", cause);
                    None
                }
            }
        })
        .take(min_cosigners as usize)
        .collect::<Vec<_>>()
        .await;

In the next stage, it creates a signing package, sends it to all the co-signers that answered in the first round, and then collects the signature shares.

As soon as all signature shares arrive, it can sign the message. We validate the signature against the public key.

To sign, you need to provide the node ids of one or more co-signers. You also need to provide a local data path containing the local signature share.

> cargo run sign --message test --key 25mzjgjlrcrma7wkm4l3fjv2afcs53cvmmyw3v2uwwt2dczsinaa --data-path c 4bqd4r3fivo5722twrvmlwcs7wjlnv6xf567lyweb7yyb34x37ba
Signature: a42d8ada7fc84a99f95e588eed99f89cc3ffdf3806862d6f5efd6511dd7b97912d04655e2c5f8f42e85c231ba8e084ae07d3e88c1bc17bc31156a9765b71200b

Possible usage

So now we have a way to split an ed keypair into multiple key shares, store these shares on multiple devices, and sign a message using a co-signer.

How would we use this to have good usabilty when publishing to pkarr while still keeping the key safe?

One key share a will be on the device that is actively publishing. One key share b would be on a remote server, either on a computer owned by the user or on a server operated by a service provider. And the third share c would be safely stored by the user, e.g. on a USB stick.

The user device would first do a co-sign request, which would be answered by the co-sign server. Then it would publish the signed message.

The co-sign server has a key share for the key, but that alone is not sufficient to publish to the key.

Recovery on key loss

If the user device is lost or compromised, the user can simply disable publishing to the key by stopping the co-sign server. Then he can regenerate the signing key on a secure device, create a new set of three key shares a2, b2, c2, destroy the old two key shares b and c, and start from scratch with a similar setup as before.

The key b on the lost device is completely useless without either b or c.

Automation

This entire process could be automated to provide a smooth user experience.