Alternative Signatures Schemes

How to not lose your crypto with novel cryptography.

By: Leland Lee (Independent) and Dev Ojha (UC Berkeley / ex Tendermint)

Figure: Sometimes we need multiple signatures to get things done

It is ironic how some multi billion dollar cryptocurrencies do not natively support multisignature. Where m-of-n signers are required to authorized a transaction. We’re not ones to judge because maybe it’s by design to only have one private key[0]. But that is not the world that we want to live in, because who wants to lose millions of dollars due to a faulty smart contracts or lost private keys?

Today we will examine various multisignature schemes for transaction signing in blockchains that are applicable to both UTXO and account based models. Please note that some of schemes are still being actively researched and that there are multiple constructions with differing attributes (communication over head, signing time, etc). And if there’s too much technical content jump to the trade off space section.

In the status quo, existing blockchains have pursued several different systems to have multiple owners control the same set of coins: smart contract based (Ethereum) to native scripts (BTC’s P2SH).

• Smart Contract: Ethereum, Tezos, EOS, VeChain, Ethereum Classic
• Scripts: BTC, LTC, Iota, Cardano, Zcash[1], NEO, DASH, Decred
• Built into the Client: Stellar, Ripple
• Custom Cryptography: GRIN[2], Monero[3]

How Signatures Work

In order to send a valid transaction on any blockchain several steps must be taken.

1. Construction a valid transaction
2. Sign the transaction with the corresponding private key of the account or UTXO
3. Submit the signed transaction to network
4. A miner verifies the transaction and signature
5. The transaction is placed into a block and relevant blockchain state is updated.

Non Cryptographic Techniques and Their Issues

Smart Contracts

Although smart contract based multi signature accounts offer much flexibility (daily allowances, infinite customization) they historically have suffer from bugs in both the code, language, virtual machine and compiler. Hundreds of millions have been locked up in perpetuity due to human related errors.

Scripts

Unlike smart contract platforms, Bitcoin has a more primitive scripting language. The differences are stark: not Turing complete, not compiled, no virtual machine and no concept of “state”. Whether this makes the cryptocurrency less useful is a debate to be held elsewhere. But more importantly there are specific op_codes for operations such as multisignature. In Bitcoin and Bitcoin related forks, there is a special script known as Pay-to-Script-Hash which is used to create multisignature accounts. An in depth explanation can be found here.

Both Bitcoin’s multisignature addresses and Ethereum’s multisignature wallets require on chain submission of all relevant signature for a transaction to be sent. Some of the schemes we will explore today only require one signature to be submitted, saving valuable onchain space and potentially making the address indistinguishable from single private key addresses.

Cryptographic Techniques

Here we explore various techniques to add multisignature to blockchain protocols. None of these are the silver bullet, as each method has various trade offs that need to be explored thoroughly before determining which technique is optimal for particular situations.

Note depending on what lense we apply to these class of cryptographic constructions they all look the same from high up enough, we’ve taken a distinct balance to highlight some of the key technical differences without diving to far into the technical weeds.

Shamir’s Secret Sharing (SSS)

Note this is not a multisig in a classical sense, nonetheless it is discussed here to provide a counterexample to other forms of cryptographic multisignature.

Here a private key is used to derive n shards, where m are required to reconstruct the private key. This scheme is often used for key recovery, if a user loses the private key it is possible to to reconstruct the original key using the shards the user has distributed to various friends. However it is not apt for multi signature as:

1. The private key must be generated to derive the shards.
2. The private key must be reassembled from the shards before a transaction can be signed.

This means that there is a trusted generation and reassembly step which are points of failure. Also individual shard holders have no say in which transaction is going to be signed, all they provide is the shard. Trusted hardware could mitigate the trusted generation and signing concerns, but this leads issues such as side channel attacks, availability, etc.

Nonetheless there are some unique features of SSS that should be noted, it is possible to create as many distinct set of shares without modifying the underlying secret / private key. Thus if Alice originally has 10 secrets and unfriends Bob, a secret holder, Alice can regenerate 9 secrets and give it to the remaining trusted parties (who hopefully destroy their old shares, rendering Bob’s share useless).

There are some libraries out in the wild for Bitcoin (SplitKey) and Ethereum, however they function as key recovery systems.

Threshold ECDSA

In threshold ECDSA, we remove the vulnerability of Shamir’s where there is a preimage / existing private key. Here we describe a recent construction pioneered by Steven Goldfeder in his ECDSA MPC paper, which surpasses previous ECDSA work in terms of efficiency for both the key generation and signing.

Using a distributed key generation (DKG) scheme, all key holders participate in an interactive process that generates both a private key for themselves and a single public key. This ensures that no party ever learns the true private key. Before this construction key generation would only be practical using a trusted dealer as the computation time would be too great for parties greater than two.

We know of two working implementations of threshold ECDSA done by Keep Network and Kzen Networks.

Threshold Ed25519

An issue with ECDSA is that due to the intricacies of the signing algorithm, threshold signatures are complex. However for other signatures schemes such as EdDSA (Edwards-curve Digital Signature Algorithm), and particularly with curve Edwards25519 whose signature scheme Ed25519 has relatively more efficient and straightforward threshold signatures. Users generate their own keys and then have an aggregation step to create a single public key and transaction signing has a three round interactive protocol.

Kzen Networks has implemented a reference library for Ed25519 threshold signatures; Stellar[4], Near Protocol and Cosmos use the same curve but do not to implement cryptographic threshold signatures.

Schnorr Signatures

In Bitcoin, Schnorr signatures are a form of signature aggregation. Instead of using P2SH which grows linearly to the number of keys, signature aggregation allows for constant size signatures. And the verifier does not need to know the individual public keys of the signers, increasing privacy. Blockstream is helping pioneer this technique in Bitcoin.

There are several ways to implement m-of-n multisignature in Schnorr (section 5.3) with various trade offs, in some schemes users provide their own keys, whereas in others there must be a DKG ceremony. In general there is at least one round of communication for key generation and transaction signing, transaction signing also does not scale well with large a large m or n.

BLS Signatures

Short for Bohen-Lynn-Shacham signatures, they work very well for large signature sets. Meaning we can have a 2 of 10 or 2 of 1000 multisignature scheme with barely any difference in set up and signing times. For the setup phase the only thing necessary to do is generation of membership keys for each private key, this only requires one round of communication[5]. Because users supply their own private keys it is possible to use techniques such as HD Derivation for easy management of multiple keys. Users sign transactions offline and a single aggregator adds up the signatures and submits it.

This particular construction using membership keys is fairly new, another method is to leverage Shamir’s Secret Sharing (used by Dfinity and Dash) however either a trusted dealer or a DKG is necessary. A downside of BLS lies in the weeds, where finding an optimal pairing is inefficient, meaning signature verification is slow, a magnitude slower than ECDSA. Dive deep into BLS here.

Trade off space

When observing these techniques from a distance it seems that some on paper are superior to others. Unfortunately that is not the case when we dive into the trade off space. Some techniques are preferable for larger groups of signers, others more apt for low bandwidth environments. Here we explore a non exhaustive list of attributes to analyze the various techniques from above.

Preimage: Is there a private key that must be split?

Trusted Setup: Is there a single entity that generates the keys or can there be a distributed key generation scheme?

Detect Multisig: Can a viewer of the blockchain determine whether a particular address is a multisignature address?

HD Derivation: Is it possible to have hardware deterministic keys for the associated cryptographic process? (Can users use techniques like BIP32 so they only need to remember their seed rather than a bunch of private keys)

Weight: Is it possible to assign different weights to particular private keys? (ex: 1 of 2 multisig, where key holder A has a weight of 2 and key holder B has a weight of 1, meaning A does not need B to sign but B always requires A).

Visibility

• Privacy of Signers: Can a viewer of the blockchain determine who were the particular signers of a transaction
• Signature size: Do multi signature transactions require more on chain space, does the amount of space vary depending the number of signers?

Time

• Key generation time: How long does it take to generate the keys, does key generation time increase based on the number of parties?
• Key generation rounds: If key generation is interactive, how many times do participants need to interact with each other.
• Verification time: How long does it take to verify a signature
• Signing time: How long does it take to sign a transaction

Signing

• Interactive: How many rounds of communication are required to sign a transaction
• Curve Efficiencies: Even though some of these techniques work for all curves it is necessary to consider things such as curve efficiencies and cofactor selection.

Figure: The trade off space for the schemes discussed, note that there are several constructions for each scheme which leads to different attributes.

Future Developments

Although there are many different techniques that enable multisignature accounts for blockchains we must be cognizant of the design considerations in a protocol. Some of these techniques require changes to the underlying protocols, while others do not. Protocol designers should be aware of the implicit trade offs in both user experience and future proofing for advance in cryptography.

Fun fact: signatures have much more uses than for sending transactions. They are / can be used for block signing in Proof of Stake systems, aggregate signatures to have smaller blockchains, and transaction compression.

Fun questions

Now that you know more about cryptographic multisignatures here are some questions to ask yourself when deciding what kind of signatures scheme you should choose when implementing a protocol.

• Are there use cases where one wants to be able to differentiate between multisignature and single signature accounts on chain.
• Threshold cryptography provides the property where the individual key signers are unknown, where can this be beneficial or detrimental?
• Is it possible to have a signature scheme that allows for selective disclosure, where some transactions reveal the signers and other transactions do not?
• Is it possible to have a signature scheme that can reveal only a subset of the signers but not all?
• Is it possible to have a scheme where the signing parties are not able to determine who are the other signers in the interactive step?
• How does key management work when it is not possible to have HD wallets?
• For BLS one can use HD keys, however it is necessary to generate additional membership keys. What should protocol be when the user loses their membership key?
• Should multisig lie entirely in the cryptographic realm or should one there be a balance between smart contracts / scripts and cryptography
• Are there instances where signature size does not matter at all because signature are tossed or there is a novel form of compression?

Foot Notes

[0] Technically all blockchains do have a form of native multisignature assuming there are cryptographic signatures. However finding an efficient threshold signature scheme for any arbitrary signature algorithm can be rather difficult.

[1] Zcash currently uses P2SH, in the upcoming Blossom update it will switch to a custom cryptographic construction.

[2] Grin unique among cryptocurrencies to use a cryptography based multisignature, it is similar to Bitcoin’s confidential transactions. A downside of their approach is that it is custom to their protocol and hard to generalize.

[3] Monero only supports n-of-n and n-1-of-n schemes, the former being very similar to a splitkey.

[4] Stellar has multisignature but does not implement it in cryptography, instead it is achieved by using their scripting language.

[5] Note for UTXO models there is a one time interactive step for the generating the public key which is necessary for the unlocking script when users want to spend.

Thanks to Tarun Chitra, Joyce Yang, Dan Robinson, Jeremy Rubin, Jeremiah Andrews and countless others for review and explanations of various cryptographic techniques.