Skip to content

ECDSA Adaptor Signature

Table of contents

Open Table of contents

What it is

A digital signature can be turned into an adaptor signature by modifying it such that it only verifies if a secret value is applied. The secret value will be publicly visible once it’s applied and the signature verified.

Having such a construction is useful in Blockchain applications where it can be leveraged to implement ”Scriptless Scripts” which are small programs that are enforced solely via digital signatures.

One such contractual enforcement is an atomic swap where two parties that don’t trust each other exchange pre-determined values of currencies with one another.

The example of an atomic swap will be used throughout this post to explain how adaptor signatures can be implemented with the Elliptic Curve Digital Signature Algorithm. While atomic swaps are one common use case for adaptor signatures, there’s more that can be implemented with the techniques we’ll explore.

In fact, adaptor signatures are a generic construction that can be used outside of Cryptocurrency / Blockchain use cases.

In our scenario we have two participants called Alice and Bob. Both agree on amounts of currencies they want to exchange with each other. While they deem each other trustworthy they want to be ensured that whoever initiates the value exchange gets paid as well and won’t be cheated.

This trust problem could be easily solved by introducing another, trustworthy third party that acts as an escrow and takes custody of Alice’s and Bob’s funds. Once both have deposited their currencies with the third party, it can distribute the right amount to Alice and Bob respectively. While this setup works in practice, it merely moves the trust question to a middleman.

With adaptor signatures we can implement a trustless system that provides the same guarantees as the escrow example while solely relying on Mathematics and Cryptography.

How it works

Before diving deeper into the specifics, it’s important to call out that a solid understanding of the Elliptic Curve Digital Signature Algorithm as well as the Two-Party ECDSA variant is necessary to follow along.

More specifically, the adaptor signature implementation described in this post is built on top of Yehuda Lindell’s ”Fast Secure Two-Party ECDSA Signing” construction which uses the Paillier Cryptosystem behind the scenes.

We’ll call the Elliptic Curve we’re working with EE. This curve is of order qq and has a generator GG. All calculations are done mod q\bmod\ q if not stated otherwise.

Note: The parameters Alice generates will use the subscript 1_1 while Bob’s parameters use the subscript 2_2 and 3_3.

Setup

The first step is for Alice and Bob to generate their private- and public keys. The private keys are generated by sampling a random value from Zq\mathbb{Z}_q while the respective public key is derived by multiplying the private key with the Elliptic Curve generator GG.

Alice computes:

a$Zqa \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q A=aGA = aG

While Bob computes:

b$Zqb \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q B=bGB = bG

Alice also generates a private- and public key pair for the Paillier Cryptoystem. She then encrypts her private key aa under her Paillier public key which will be denoted as enc(a)enc(a).

Bob on the other hand generates a second, secret value tt by sampling another random value from Zq\mathbb{Z}_q. He then derives its public value TT by multiplying tt with the generator GG.

Alice now shares her public key AA, her encrypted private key enc(a)enc(a) as well as her public key for the Paillier Cryptosystem with Bob. Bob in turn shares his public key BB and the public value TT of the secret tt he keeps to himself with Alice.

Now that both have each other’s public key, they can use the Elliptic Curve Diffie-Hellman protocol to derive a shared public key XX.

In Alice’s case, she computes:

X=aB=abG\begin{aligned} X &= aB \\ &= abG \end{aligned}

Whereas Bob calculates:

X=bA=baG\begin{aligned} X &= bA \\ &= baG \end{aligned}

Next up, Alice and Bob both need to separately sample another, random value kk from Zq\mathbb{Z}_q. This value is the “nonce” (number used once) that should never be reused. The nonce kk is also multiplied by the generator GG to derive the value RR which is a point on the Elliptic Curve EE.

Alice calculates:

k1$Zqk_1 \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q R1=k1GR_1 = k_1G

Bob does the same:

k2$Zqk_2 \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q R2=k2GR_2 = k_2G

The values R1R_1 and R2R_2 are then exchanged.

Given that Bob is in possession of the secret value tt, he generates a third value R3R_3 by multiplying his nonce value k2k_2 with the public value TT:

R3=k2TR_3 = k_2T

Doing so allows him to “hide” and share the secret value tt with Alice by sending R3R_3 to Alice.

Both, Alice and Bob now derive a shared value RR by following the same Elliptic Curve Diffie-Hellman protocol that was used to agree on the XX value. Note that while Alice uses the public value TT she got from Bob in her calculation, Bob uses the private value tt to derive the same value RR.

In this case Alice calculates:

R=k1R3=k1k2T=k1k2tG\begin{aligned} R &= k_1R_3 \\ &= k_1k_2T \\ &= k_1k_2tG \end{aligned}

And Bob computes:

R=k2tR1=k2tk1G=k1k2tG\begin{aligned} R &= k_2tR_1 \\ &= k_2tk_1G \\ &= k_1k_2tG \end{aligned}

This value RR is a point on the Elliptic Curve EE which has an xx- and yy-coordinate. It’s therefore possible to define a value rr as the xx-coordinate of the point RR:

r=Rxr = R_x

To kick-off the value transfer, Alice and Bob need to prepare transactions in which they send the correct amount of currency to each other. This is done my hashing the corresponding message mm via a cryptographic hash function HH, the result of which can be interpreted as a point on the curve.

Alice hashes a message m1m_1 where she sends her funds to Bob:

z1=H(m1)z_1 = H(m_1)

While Bob hashes a message m2m_2 where he sends his funds to Alice:

z2=H(m2)z_2 = H(m_2)

Next up, both exchange the hashes they computed with each other.

Payment Preparation (Bob)

Now that Bob received the message hash z1z_1 which includes the intent of Alice sending funds to him, he can start to calculate two partial signatures s1s_1' and s2s_2' which can be used by Alice to initiate such value transfers.

The first partial signature s1s_1' will be used to send funds from Alice to Bob. Its constructed by first calculating the ciphertext c1c_1 as the encryption of k21z1k_2^{-1}z_1 under Alice’s Paillier public key:

c1=enc(k21z1)c_1 = enc(k_2^{-1}z_1)

Next up, the constant y1y_1 is derived:

y1=k21rby_1 = k_2^{-1}rb

This value y1y_1 is then used to calculate another ciphertext c1c_1' where Bob uses Alice’s encrypted private key (remember that Alice sent enc(a)enc(a) in the beginning of the protocol) to raise it to the power of yy.

c1=enc(a)y1=enc(ay1)=enc(ak21rb)\begin{aligned} c_1' &= enc(a)^{y_1} \\ &= enc(ay_1) \\ &= enc(ak_2^{-1}rb) \end{aligned}

In Paillier’s Cryptosystem, a ciphertext raised to a constant will decrypt to the product of the constant and the plaintext.

As a last step, Bob calculates the partial signature s1s_1' by multiplying the ciphertexts c1c_1 and c1c_1'.

s1=c1c1=enc(k21z1)enc(ak21rb)=enc(k21z1+k21rab)=enc(k21(z1+rab))\begin{aligned} s_1' &= c_1c_1' \\ &= enc(k_2^{-1}z_1)enc(ak_2^{-1}rb) \\ &= enc(k_2^{-1}z_1 + k_2^{-1}rab) \\ &= enc(k_2^{-1}(z_1 + rab)) \end{aligned}

In Paillier’s Cryptosystem, the product of two ciphertexts will decrypt to the sum of their plaintexts.

The second partial signature s2s_2' will be used to send funds from Bob to Alice. The process to calculate it follows the exact same steps that we’ve just discussed, which is why we won’t dive deeper into the specifics here.

c2=enc(k21z2)c_2 = enc(k_2^{-1}z_2) y2=k21rby_2 = k_2^{-1}rb c2=enc(a)y2=enc(ay2)=enc(ak21rb)\begin{aligned} c_2' &= enc(a)^{y_2} \\ &= enc(ay_2) \\ &= enc(ak_2^{-1}rb) \end{aligned} s2=c2c2=enc(k21z2)enc(ak21rb)=enc(k21z2+k21rab)=enc(k21(z2+rab))\begin{aligned} s_2' &= c_2c_2' \\ &= enc(k_2^{-1}z_2)enc(ak_2^{-1}rb) \\ &= enc(k_2^{-1}z_2 + k_2^{-1}rab) \\ &= enc(k_2^{-1}(z_2 + rab)) \end{aligned}

Both partial signatures s1s_1' and s2s_2' are the send to Alice.

Payment Preparation (Alice)

Alice now updates the partial signatures she received from Bob by decrypting them and multiplying them with k11k_1^{-1}:

s1=k11dec(s1)=k11k21(z1+rab)\begin{aligned} s_1'' &= k_1^{-1}dec(s_1') \\ &= k_1^{-1}k_2^{-1}(z_1 + rab) \end{aligned} s2=k11dec(s2)=k11k21(z2+rab)\begin{aligned} s_2'' &= k_1^{-1}dec(s_2') \\ &= k_1^{-1}k_2^{-1}(z_2 + rab) \end{aligned}

Note that these updated partial signatures are still invalid because they need to be adapted to incorporate the secret value tt to turn them into a valid signature. This can only be done by Bob as he’s the only one who knows tt. We’ll write a proper proof which shows why that’s the case soon.

To incentive Bob to transact on-chain and therefore reveal the secret value tt, Alice sends the updated partial signature s1s_1'' back to Bob as this is the one which includes the hash z1z_1 of the message m1m_1 that transfers funds from Alice to Bob.

Signature Generation (Bob)

Once Bob receives s1s_1'' he can turn this updated, partial signature into a real signature by multiplying it with t1t^{-1}:

sb=t1s1=t1k11k21(z1+rab)\begin{aligned} s_b &= t^{-1}s_1'' \\ &= t^{-1}k_1^{-1}k_2^{-1}(z_1 + rab) \end{aligned}

Bob can now publish the signature (r,sb)(r, s_b) that transfers Alice’s funds to him. This signature can be validated with the ECDSA verification algorithm using the shared public key XX.

To do so, one calculates the values ubu_b, vbv_b and RbR_b as follows:

ub=sb1z1u_b = s_b^{-1}z_1 vb=sb1rv_b = s_b^{-1}r Rb=ubG+vbXR_b = u_bG + v_bX

The signature is valid if r=?Rbxr \overset{?}{=} R_{b_x}.

That is, if rr equals the xx-coordinate of the RbR_b value that was calculated during signature verification.

Once the signature is verified on-chain Alice can learn the value of tt.

Signature Generation (Alice)

By monitoring the Blockchain for Bob’s published signature (r,sb)(r, s_b) that pays him, Alice can extract the secret value tt by calculating:

t=(sb(s1)1)1=1sb(s1)1=1sb(1k11k21(z1+rab))=1t1k11k21(z1+rab)(1k11k21(z1+rab))=1t1k11k21(z1+rab)k11k21(z1+rab)=1t1k11k21(z1+rab)k11k21(z1+rab)=1t1=11t=t\begin{aligned} t &= (s_b(s_1'')^{-1})^{-1} \\ &= \frac{1}{s_b(s_1'')^{-1}} \\ &= \frac{1}{s_b\left(\frac{1}{k_1^{-1}k_2^{-1}(z_1 + rab)}\right)} \\ &= \frac{1}{t^{-1}k_1^{-1}k_2^{-1}(z_1 + rab)\left(\frac{1}{k_1^{-1}k_2^{-1}(z_1 + rab)}\right)} \\ &= \frac{1}{t^{-1}\frac{k_1^{-1}k_2^{-1}(z_1 + rab)}{k_1^{-1}k_2^{-1}(z_1 + rab)}} \\ &= \frac{1}{t^{-1}\frac{\cancel{k_1^{-1}k_2^{-1}(z_1 + rab)}}{\cancel{k_1^{-1}k_2^{-1}(z_1 + rab)}}} \\ &= \frac{1}{t^{-1}} \\ &= \frac{1}{\frac{1}{t}} \\ &= t \end{aligned}

Using tt, Alice can now calculate a valid signature by multiplying tt with the partial signature s2s_2'' that transfers funds from Bob to her:

sa=t1s2=t1k11k21(z2+rab)\begin{aligned} s_a &= t^{-1}s_2'' \\ &= t^{-1}k_1^{-1}k_2^{-1}(z_2 + rab) \end{aligned}

Alice can publish the signature (r,sa)(r, s_a) which transfers Bob’s funds to her. The signature can be validated with the ECDSA verification algorithm using the shared public key XX.

This is done the same way as it was done for Bob’s signature by calculating the values uau_a, vav_a and RaR_a:

ua=sa1z2u_a = s_a^{-1}z_2 va=sa1rv_a = s_a^{-1}r Ra=uaG+vaXR_a = u_aG + v_aX

The signature is valid if r=?Raxr \overset{?}{=} R_{a_x}.

I.e. if the value of rr equals the xx-coordinate of the RaR_a value that was calculated during signature verification.

ECDSA Adaptor Signature

Why it works

The key takeaway is that Alice and Bob both need to collaborate to create valid signatures.

Both derived the same, shared public key XX without sharing their private keys aa and bb. Alice only shared an encrypted version of her private key enc(a)enc(a) which Bob utilizes to create partial signatures that incorporate both his and Alice’s private keys.

Even once Alice decrypts the partial signatures, she can’t learn anything about the individual private keys as they’re “masked” by multiplying them with the shared rr value and adding the hashed message zz to it:

dec(s1)=z1+rabdec(s_1') = z_1 + rab dec(s2)=z2+rabdec(s_2') = z_2 + rab

To make sure that Alice can’t cheat once Bob sends over the partial signatures which he asks Alice to turn into updated (almost valid) signatures, Bob also keeping a secret value tt to himself which needs to be incorporated into Alice’s updated partial signatures to finally turn them into real, valid signatures.

Bob needs to tweak the updated, partial signature he got form Alice with the value tt in order to transact on-chain and therefore receive funds from Alice. The minute he does so, tt is revealed and can be used by Alice to adapt the partial signature that pays her into a real signature she can then also use to transact on-chain and get the funds transferred from Bob.

The signature verification algorithm is exactly the same as the one that’s used in regular ECDSA.

Let’s start with Alice’s signature and its verification.

At first, remember that z2z_2 is the hash of the message that initiates a transfer of funds from Bob to Alice. This value is interpreted as a point on the Elliptic Curve EE.

Using the signature sas_a we can re-arrange it to isolate the multiplication of both kk values with tt:

sa=t1k11k21(z2+rab)×t×k1×k2satk1k2=z2+rab×sa1tk1k2=sa1(z2+rab)\begin{aligned} s_a &= t^{-1}k_1^{-1}k_2^{-1}(z_2 + rab) && \mid \times t \times k_1 \times k_2 \\ s_atk_1k_2 &= z_2 + rab && \mid \times s_a^{-1} \\ tk_1k_2 &= s_a^{-1}(z_2 + rab) \end{aligned}

We can now expand RaR_a and substitute tk1k2tk_1k_2 for sa1(z2+rab)s_a^{-1}(z_2 + rab). Doing so, we can see that Ra=tk1k2GR_a = tk_1k_2G:

Ra=uaG+vaX=uaG+vaabG=G(ua+vaab)=G(sa1z2+sa1rab)=sa1G(z2+rab)tk1k2=sa1(z2+rab)=tk1k2G\begin{aligned} R_a &= u_aG + v_aX \\ &= u_aG + v_aabG \\ &= G(u_a + v_aab) \\ &= G(s_a^{-1}z_2 + s_a^{-1}rab) \\ &= s_a^{-1}G(z_2 + rab) && \mid tk_1k_2 = s_a^{-1}(z_2 + rab) \\ &= tk_1k_2G \end{aligned}

Taking a look at the signature creation process, we can verify that this Elliptic Curve Point RaR_a is exactly the same as the on Alice and Bob derived from their kk and RR values.

The xx-coordinate of RaR_a is therefore equal to the rr value of the signature, which in turn makes the signature over the message m2m_2 valid.

The same logic applies to Bob’s signature and its verification. Given that we’ve just read an explanation as to how and why it works we won’t repeat it here but only show the mathematical proof.

sb=t1k11k21(z1+rab)×t×k1×k2sbtk1k2=z1+rab×sb1tk1k2=sb1(z1+rab)\begin{aligned} s_b &= t^{-1}k_1^{-1}k_2^{-1}(z_1 + rab) && \mid \times t \times k_1 \times k_2 \\ s_btk_1k_2 &= z_1 + rab && \mid \times s_b^{-1} \\ tk_1k_2 &= s_b^{-1}(z_1 + rab) \end{aligned} Rb=ubG+vbX=ubG+vbabG=G(ub+vbab)=G(sb1z1+sb1rab)=sb1G(z1+rab)tk1k2=sb1(z1+rab)=tk1k2G\begin{aligned} R_b &= u_bG + v_bX \\ &= u_bG + v_babG \\ &= G(u_b + v_bab) \\ &= G(s_b^{-1}z_1 + s_b^{-1}rab) \\ &= s_b^{-1}G(z_1 + rab) && \mid tk_1k_2 = s_b^{-1}(z_1 + rab) \\ &= tk_1k_2G \end{aligned}

Again, the xx-coordinate of RbR_b is equal to the rr value of the signature, which makes the signature over the message m1m_1 valid.

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.