## 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 $E$. This curve is of order $q$ and has a generator $G$. All calculations are done $\bmod\ q$ if not stated otherwise.

**Note:** The parameters Alice generates will use the subscript $_1$ while Bob’s parameters use the subscript $_2$ and $_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 $\mathbb{Z}_q$ while the respective public key is derived by multiplying the private key with the Elliptic Curve generator $G$.

Alice computes:

$a \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q$ $A = aG$While Bob computes:

$b \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q$ $B = bG$Alice also generates a private- and public key pair for the Paillier Cryptoystem. She then encrypts her private key $a$ under her Paillier public key which will be denoted as $enc(a)$.

Bob on the other hand generates a second, secret value $t$ by sampling another random value from $\mathbb{Z}_q$. He then derives its public value $T$ by multiplying $t$ with the generator $G$.

Alice now shares her public key $A$, her encrypted private key $enc(a)$ as well as her public key for the Paillier Cryptosystem with Bob. Bob in turn shares his public key $B$ and the public value $T$ of the secret $t$ 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 $X$.

In Alice’s case, she computes:

$\begin{aligned} X &= aB \\ &= abG \end{aligned}$Whereas Bob calculates:

$\begin{aligned} X &= bA \\ &= baG \end{aligned}$Next up, Alice and Bob both need to separately sample another, random value $k$ from $\mathbb{Z}_q$. This value is the “nonce” (number used once) that should never be reused. The nonce $k$ is also multiplied by the generator $G$ to derive the value $R$ which is a point on the Elliptic Curve $E$.

Alice calculates:

$k_1 \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q$ $R_1 = k_1G$Bob does the same:

$k_2 \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q$ $R_2 = k_2G$The values $R_1$ and $R_2$ are then exchanged.

Given that Bob is in possession of the secret value $t$, he generates a third value $R_3$ by multiplying his nonce value $k_2$ with the public value $T$:

$R_3 = k_2T$Doing so allows him to “hide” and share the secret value $t$ with Alice by sending $R_3$ to Alice.

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

In this case Alice calculates:

$\begin{aligned} R &= k_1R_3 \\ &= k_1k_2T \\ &= k_1k_2tG \end{aligned}$And Bob computes:

$\begin{aligned} R &= k_2tR_1 \\ &= k_2tk_1G \\ &= k_1k_2tG \end{aligned}$This value $R$ is a point on the Elliptic Curve $E$ which has an $x$- and $y$-coordinate. It’s therefore possible to define a value $r$ as the $x$-coordinate of the point $R$:

$r = 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 $m$ via a cryptographic hash function $H$, the result of which can be interpreted as a point on the curve.

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

$z_1 = H(m_1)$While Bob hashes a message $m_2$ where he sends his funds to Alice:

$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 $z_1$ which includes the intent of Alice sending funds to him, he can start to calculate two partial signatures $s_1'$ and $s_2'$ which can be used by Alice to initiate such value transfers.

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

$c_1 = enc(k_2^{-1}z_1)$Next up, the constant $y_1$ is derived:

$y_1 = k_2^{-1}rb$This value $y_1$ is then used to calculate another ciphertext $c_1'$ where Bob uses Alice’s encrypted private key (remember that Alice sent $enc(a)$ in the beginning of the protocol) to raise it to the power of $y$.

$\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 $s_1'$ by multiplying the ciphertexts $c_1$ and $c_1'$.

$\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 $s_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.

$c_2 = enc(k_2^{-1}z_2)$ $y_2 = k_2^{-1}rb$ $\begin{aligned} c_2' &= enc(a)^{y_2} \\ &= enc(ay_2) \\ &= enc(ak_2^{-1}rb) \end{aligned}$ $\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 $s_1'$ and $s_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 $k_1^{-1}$:

$\begin{aligned} s_1'' &= k_1^{-1}dec(s_1') \\ &= k_1^{-1}k_2^{-1}(z_1 + rab) \end{aligned}$ $\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 $t$ to turn them into a valid signature. This can only be done by Bob as he’s the only one who knows $t$. 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 $t$, Alice sends the updated partial signature $s_1''$ back to Bob as this is the one which includes the hash $z_1$ of the message $m_1$ that transfers funds from Alice to Bob.

### Signature Generation (Bob)

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

$\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, s_b)$ that transfers Alice’s funds to him. This signature can be validated with the ECDSA verification algorithm using the shared public key $X$.

To do so, one calculates the values $u_b$, $v_b$ and $R_b$ as follows:

$u_b = s_b^{-1}z_1$ $v_b = s_b^{-1}r$ $R_b = u_bG + v_bX$The signature is valid if $r \overset{?}{=} R_{b_x}$.

That is, if $r$ equals the $x$-coordinate of the $R_b$ value that was calculated during signature verification.

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

### Signature Generation (Alice)

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

$\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 $t$, Alice can now calculate a valid signature by multiplying $t$ with the partial signature $s_2''$ that transfers funds from Bob to her:

$\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, s_a)$ which transfers Bob’s funds to her. The signature can be validated with the ECDSA verification algorithm using the shared public key $X$.

This is done the same way as it was done for Bob’s signature by calculating the values $u_a$, $v_a$ and $R_a$:

$u_a = s_a^{-1}z_2$ $v_a = s_a^{-1}r$ $R_a = u_aG + v_aX$The signature is valid if $r \overset{?}{=} R_{a_x}$.

I.e. if the value of $r$ equals the $x$-coordinate of the $R_a$ value that was calculated during signature verification.

## 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 $X$ without sharing their private keys $a$ and $b$. Alice only shared an encrypted version of her private key $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 $r$ value and adding the hashed message $z$ to it:

$dec(s_1') = z_1 + rab$ $dec(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 $t$ 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 $t$ in order to transact on-chain and therefore receive funds from Alice. The minute he does so, $t$ 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 $z_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 $E$.

Using the signature $s_a$ we can re-arrange it to isolate the multiplication of both $k$ values with $t$:

$\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 $R_a$ and substitute $tk_1k_2$ for $s_a^{-1}(z_2 + rab)$. Doing so, we can see that $R_a = tk_1k_2G$:

$\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 $R_a$ is exactly the same as the on Alice and Bob derived from their $k$ and $R$ values.

The $x$-coordinate of $R_a$ is therefore equal to the $r$ value of the signature, which in turn makes the signature over the message $m_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.

$\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}$ $\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 $x$-coordinate of $R_b$ is equal to the $r$ value of the signature, which makes the signature over the message $m_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.

- Wikipedia - Elliptic Curve Digital Signature Algorithm
- Wikipedia - Paillier Cryptosystem
- Pedro Moreno-Sanchez - Scriptless Scripts with ECDSA
- Andrew Poelstra - Lightning in Scriptless Scripts
- Bitcoin Optech - Adaptor Signatures
- Conduition - The Riddles of Adaptor Signatures
- YouTube - Generalized Channels from Limited Blockchain Scripts and Adaptor Signatures
- Ichiro Kuwahara - Adaptor Signature - Schnorr Signature and ECDSA
- Ichiro Kuwahara - Adaptor Signature on ECDSA
- Ichiro Kuwahara - Adaptor Signature in Discreet Log Contracts on ECDSA
- Yehuda Lindell - Fast Secure Two-Party ECDSA Signing
- Discreet Log Contracts - ECDSA Adaptor Signatures