Signature Interpolation: A simple multi-party wallet generation technique supporting exactly two ECDSA signatures

ECDSA is the main signature scheme for many cryptocurrencies, including Bitcoin and Ethereum, and is widely used in the blockchain industry.

However, ECDSA does not support Signature Aggregation¹ making it difficult to support of Threshold Signatures² in those protocols.

In order to address that shortcoming of ECDSA, multi-signature primitives (a.k.a. multi-sig wallets) are usually implemented by collecting a set of independent ECDSA signatures which are then validated in an ad-hoc manner by the protocol implementation.

This leads to space inefficiency, as multiple signatures need to be stored. Moreover, the ad-hoc multi-signature implementation cannot be reconciled transparently with ECDSA signatures, making the protocol signature handling heterogeneous, non-interoperable, and feature-limited.

(For instance, on Ethereum a multi-sig wallet is usually implemented as a smart-contract. It has an address, but it cannot produce ECDSA signatures because its associated private key is unknown by design.)

Alternative signature schemes have been proposed to address those issues including Schnorr Signatures and Boneh-Lynn-Shacham (BLS) Signatures. However, until ECDSA is fully replaced, it remains important to work around its limitations.

A. The case for a 2-signature multi-sig wallet

On Ethereum, in order to save on transaction (gas) costs, some applications make use of off-chain signatures.

These are ECDSA signatures that are usually stored on a hosted database for later use. They represent some authorization that the user is providing to the given platform. These signature are kept in the database until a more important event occurs, when it is submitted for validation on-chain.

This is how most NTF marketplaces on Ethereum are implemented. Users just sign the sell order’s payload when listing an item for sale. And those signatures are stored off-chain by the marketplace service, rather than broadcast to the network.

When a buyer comes along, the marketplace service retrieves the signature from the off-chain database and bundles it on the buy transaction, which is then broadcast and validated on-chain. If the signature matches, as well as all pre-requisites apply (such as the user is the current owner of the NFT), the item is transferred from the buyer wallet to the seller wallet. Otherwise the operation simply fails.

Although this technique offers a very good trade off — an arbitrary number of listings can be created with virtually no upfront cost —, there are limitations though:

• It cannot be used by a smart contract, as the ECDSA signature needs to be generated from a private key (some see this as a feature rather than a bug, as it limits the interaction to final users);
• Cannot be used trustlessly by multiple participants, as ECDSA does not support Threshold Signatures, or at least not in general.

It must be noted that, for the specific use-case of buying NFTs from marketplaces that use off-chain signatures, as much as to overcome these limitations, we only need to produce exactly two ECDSA signatures:

1. A signature for the transaction that allows spending a given NFT by the marketplace’s smart contract;
2. An off-chain signature on the sell order’s payload for that very same NFT to be submitted to the marketplace’s listing service.

In this article, we show how it is possible for an arbitrary number of users to collective generate an Ethereum address for which they are able to trustlessly and securely sign exactly two ECDSA transactions.

Spoiler Alert: It does not make use of any advanced topic such as Homomorphic Encryption, Zero-Knowledge Proofs, or any overly-complicated setup ceremony.

B. How ECDSA signing works

The signature algorithm for ECDSA is fairly simple.

To sign a given message m we first compute its hash z and generate a hard-to-guess k (usually deterministically using RFC6979). It is of utmost importance that k remains secret and is never reused.

The signature is then composed of a pair of numbers (r, s).

The first number r is the x coordinate of the point [1] R = k × G where G is the base point that generates the elliptic curve subgroup.

(In the formula k × G, the × operation is overloaded as k is a number and G is an elliptic curve point. It means performing point addition of G to itself k times, where point addition is a well-defined operation, that given two points on the elliptic curve obtains a third point also on the curve. The key observation is that this operation is difficult to invert, given R it is practically impossible to derive k. Therefore R can be made public while k remains secret.)

The second number s is given by the formula [2] s = (z + r × d) / k, where d is the private key, which must also remain secret. From this formula we can derive that [3] k = (z + r × d) / s and [4] d = (-z + s × k) / r

(Note that, even though d and k are secret and, as long as they remain so, they cannot be derived from s. This allows s to be made public. However, given that the private key d is a constant, two different signatures (r, sa) and (r, sb) that reuse k can trivially reveal d by the equality (za + ra × d) / sa = (zb + rb × d) / sb obtained from [3]. Therefore we highlight again the importance of picking a distinct k for every signature.)

The public key Q is derived from the private key d as simply [5] Q = d × G. The associated cryptocurrency wallet address is usually derived from Q by hashing it.

From a valid signature (r, s) is is also possible to recover the signing public key Q using the formula [6] (-z / r) × G + (s / r) × R. This can be shown directly from [5], [4], and [1]:

Q = d × G
Q = ((-z + s × k) / r) × G
Q = (-z / r + s × k / r) × G
Q = (-z / r) × G + (s × k / r) × G
Q = (-z / r) × G + ((s / r) × k) × G
Q = (-z / r) × G + (s / r) × R

The explanation above is a quick summary of how the ECDSA cryptography works, just enough to further develop this article. We encourage the reader to review more in-depth materials that cover it.

C. Shared wallet setup

Assuming we have n participants, in order to setup a shared set of wallets each participant i must follow the steps below:

1. Generate two random secret values ka[i] and kb[i];
2. Derive their associated points Ra[i] = ka[i] × G and Rb[i] = kb[i] × G;
3. Compute their sum value kc[i] = ka[i] + kb[i];

The triple (kc[i], Ra[i], Rb[i]) should be made public to all participants. Note also none of the triple elements can reveal either ka[i] or kb[i]. Moreover, the triple can be validated by checking the equality kc[i] × G = Ra[i] + Rb[i] given by the distributive property of ×:

kc[i] × G = Ra[i] + Rb[i]
(ka[i] + kb[i]) × G = (ka[i] × G) + (kb[i] × G)

Once all participants have published their triples we can compute the composite triple (kc, Ra, Rb) where:

kc = kc[1] + … + kc[n]
Ra = Ra[1] + … + Ra[n]
Rb = Rb[1] + … + Rb[n]

From this common composite triple, participants can generate a set of shared wallets, each providing exact 2 signatures, as will be explained next.

An alternative derivation of the composite triple is by defining ka and kb as:

ka = ka[1] + … + ka[n]
kb = kb[1] + … + kb[n]

And it is easy to show that:

kc = ka + kb
Ra = ka × G
Rb = kb × G

These are mathematical equivalences important to be established. However, we should never explicitly compute either ka or kb.

D. Wallet generation from 2 signatures

Once the setup is performed, we are always able to sign two messages using the same public key. The procedure precisely derives that public key, for which the associated private key is unknown and can only be reconstructed if all participants reveal their secrets.

First, as prerequisite, we need to establish the two messages to be signed ma and mb, and from those we computer their respective hashes, za and zb.

(It is important to note that ma and mb must be know a priori and cannot depend on the actual public key signing them. This means that instead of generating signatures from a public key, we actually go quite the other way around.)

Then we can compute both signatures:

• The signature of ma is given by (ra, sa) where ra is the x coordinate of Ra and sa = (za + ra × (-zb / rb)) / kc.
• The signature of mb is given by (rb, sb) where rb is the x coordinate of Rb and sb = (zb + rb × (-za / ra)) / kc.

Next we can show, using [6], that the two signatures (ra, sa) and (rb, rb) belong to the same public/private key pair Qc/dc and therefore are valid:

For (ra, sa)

Qa = (-za / ra) × G + (sa / ra) × Ra
Qa = (-za / ra) × G + (sa / ra) × (ka × G)
Qa = ((-za + sa × ka) / ra) × G
Qa = da × G

where

da = (-za + sa × ka) / ra
da × ra + za = sa × ka
da × ra + za = ((za + ra × (-zb / rb)) / kc) × ka
da × ra + za = (za × ka + ra × ka × (-zb / rb)) / kc
kc × (da × ra + za) = za × ka + ra × ka × (-zb / rb)
kc × da × ra + kc × za = za × ka + ra × ka × (-zb / rb)
kc × da × ra + (ka + kb) × za = za × ka + ra × ka × (-zb / rb)
kc × da × ra + ka × za + kb × za = za × ka + ra × ka × (-zb / rb)
kc × da × ra + kb × za = ra × ka × (-zb / rb)
kc × da × ra × rb + kb × za × rb = ra × ka × -zb
kc × da × ra × rb = ra × ka × -zb + rb × kb × -za
da = (ra × ka × -zb + rb × kb × -za) / (kc × ra × rb)

For (rb, sb)

Qb = (-zb / rb) × G + (sb / rb) × Rb
Qb = (-zb / rb) × G + (sb / rb) × (kb × G)
Qb = ((-zb + sb × kb) / rb) × G
Qb = db × G

where

db = (-zb + sb × kb) / rb
db × rb + zb = sb × kb
db × rb + zb = ((zb + rb × (-za / ra)) / kc) × kb
db × rb + zb = (zb × kb + rb × kb × (-za / ra)) / kc
kc × (db × rb + zb) = zb × kb + rb × kb × (-za / ra)
kc × db × rb + kc × zb = zb × kb + rb × kb × (-za / ra)
kc × db × rb + (ka + kb) × zb = zb × kb + rb × kb × (-za / ra)
kc × db × rb + ka × zb + kb × zb = zb × kb + rb × kb × (-za / ra)
kc × db × rb + ka × zb = rb × kb × (-za / ra)
kc × db × rb × ra + ka × zb × ra = rb × kb × -za
kc × db × rb × ra = rb × kb × -za + ra × ka × -zb
db = (ra × ka × -zb + rb × kb × -za) / (kc × ra × rb)

Therefore

dc = da = db
Qc = Qa = Qb

And we are done! With this technique a set of n participants can create a shared wallet address for which 2 signatures are required, trustlessly.

(The shared wallet works like a multi-sig with threshold n, but with the limited capacity of signing exactly 2 messages which must be known a priori and for which the signatures become available instantly.)

Since this derivation procedure arrives at an arbitrary public key solely by attempting to create 2 valid signatures, we call it Signature Interpolation.

And now they are able to, as a group, list an NTF for sale by:

1. Sending the item to the sale wallet address (the hash of Qc);
2. Unlocking its expenditure by the marketplace contract (broadcasting ma with its signature (ra, sa) to the network);
3. And providing an off-chain authorization of the sale of that item (submiting mb with its signature (rb, sb) to the marketplace listing service).

Enjoy!

¹ Signature Aggregation is a builtin property of the signature scheme that allows combining signatures from two or more participants into a single collective signature.

² Threshold Signatures allow multiple participants to collaborate in order to generate keys and sign transactions, in a distributed fashion. The threshold is the size of the participant subset required to produce a valid signature. The scheme guarantees that no subset of participants of size smaller than the threshold can forge a collective signature.