A threshold signature scheme enables a set of parties to split a secret key for a signature scheme in such a way that any subset of t+1 or more parties can collaborate to produce a signature, but no subset of t or fewer parties can produce a signature or even learn any information about the secret key.

Threshold protocols exist for today’s most widely deployed signature schemes, including the ECDSA scheme used in Bitcoin and Ethereum. The signatures produced by a threshold protocol are indistinguishable from ordinary (non-threshold) ECDSA signatures.

Axelar validators use threshold signature schemes to collectively maintain accounts on various blockchains such as Bitcoin and Ethereum. These accounts allow Axelar validators to unlock assets on chain A in order to move those assets to chain B.

Axelar network uses proof-of-stake consensus; there may be an unequal allocation of stake among Axelar validators. It helps to think of a simple example with three Axelar validators: Alice, Bob, and Claire whose stake percentages are 47%, 17%, and 36%.

A fundamental principle is that assets in threshold accounts can be moved only if a sufficiently high fraction of Axelar stake agrees to move it. Continuing our example, let’s suppose that fraction is 40%, so that only those subsets of Alice, Bob, and Claire whose total stake exceeds 40% can move assets. Thus, Alice has sufficient stake to move assets by herself, but Bob must team up with Claire in order to move assets without Alice.

Unfortunately, existing threshold signature schemes assume all parties in the protocol have equal authority to create signatures. A naive use of threshold signatures might allocate one share of the secret key to each of Alice, Bob, and Claire. In this case, there is no threshold value t that can achieve the access structure we just described:

What we need is a way to replicate our desired access structure using existing threshold signature schemes.

One solution to our problem is quite simple in principle: allocate multiple threshold shares to each validator in proportion to the amount of stake controlled by that validator. But there are some pesky edge cases to resolve.

Let’s begin with a slightly more detailed description of the solution and then see how it fares against pesky edge cases. The solution allocates a target of n total threshold shares among validators according to the following method:

Applying this method to our example, let’s stipulate a target of n=100 total shares, so the threshold t=40. Then Alice gets 47 shares, Bob 17, and Claire 36. Easy!

The numbers in this example work out nicely, but what if the numbers aren’t quite so nice? Suppose instead that Alice’s and Bob’s stake percentages are 47.5% and 16.5%. Should (Alice, Bob) get (48, 16) or (47,17) shares? According to the above procedure, the extra share goes to Alice, not Bob.

At first glance the choice to give the extra share to Alice in the above example may seem arbitrary, so let’s motivate it with another example. Suppose instead we have 200 validators with the following stake distribution:

In this case it is clear that the correct allocation of 100 shares is as follows:

And that is precisely the allocation we get from this solution.

It is conceptually simple to allocate multiple threshold shares per validator, but doing so in a software library brings increased low-level complexity and book-keeping relative to a naive, one-share-per-validator rule.

For example, additional routing information must be attached to each message in the threshold signature protocol. It no longer suffices to implement “Alice sends message m to Bob”. Instead we need to implement “Alice #3 sends message m to Bob #7”. The threshold signature software must pack and unpack the additional metadata “#3”, “#7”.

The library user -an Axelar validator -should not need to worry about routing. Instead, the validator should be aware only of “Alice sends a message to Bob.” Indeed, the only difference from naive one-share-per-validator from the validator’s perspective is the following: to initiate the key generation protocol, the validator must specify once at the beginning of the protocol how many shares each party gets. The library handles everything else. After initialization, the library API should be indistinguishable from the simpler one-share-per-validator protocol.

Consider the following architectural diagram:

An Axelar validator (Alice) has 3 threshold shares allocated to her. She receives messages from the Axelar network directed to her. Alice’s router unpacks each message just enough to discover which of her shares (#1, #2, #3) is the ultimate destination for the message. Each share is administered by a separate instance of the threshold protocol (“Protocol instance #1”, etc. in the diagram). Each protocol instance adds routing data to its outgoing messages and pushes them directly to the Axelar network. The final result of each instance is aggregated appropriately by Alice as per the details of the underlying threshold protocol before a single, final result is pushed to the Axelar network.

This final result might also be stored in Alice’s local data store for later use. For example, if the final result is a threshold secret key share then Alice needs to remember this secret data in order to participate in message signing in the future.

Accounting for stake in threshold signature schemes was originally published in Axelar on Medium, where people are continuing the conversation by highlighting and responding to this story.