Original Title: Adaptor Signatures and Its Application to Cross-Chain Atomic Swaps

Original Authors: mutourend, lynndell

Introduction

With the rapid development of Bitcoin Layer2 scaling solutions, the frequency of cross-chain asset transfers between Bitcoin and its Layer2 corresponding networks has significantly increased. This trend is driven by the higher scalability, lower transaction fees, and high throughput provided by Layer2 technologies (such as Bitlayer). These advancements facilitate more efficient and cost-effective transactions, promoting broader adoption and integration of Bitcoin in various applications. Therefore, interoperability between Bitcoin and Layer2 networks is becoming a key component of the cryptocurrency ecosystem, driving innovation and providing users with more diverse and powerful financial tools.

As shown in Table 1, there are three typical schemes for cross-chain transactions between Bitcoin and Layer2: centralized cross-chain transactions, BitVM cross-chain bridges, and cross-chain atomic swaps. These three technologies differ in trust assumptions, security, convenience, transaction limits, and can meet different application needs.

Table 1. Comparison of Cross-Chain Transaction Technologies

Centralized Cross-Chain Transactions: Users first pay Bitcoin to a centralized entity (such as a project party or exchange), which then pays an equivalent asset on the Layer2 network to the user-designated address, completing the cross-chain asset transfer. The advantage of this technology lies in its speed and the relative ease of the matching process, as the centralized entity can quickly confirm and process transactions. However, the security of this method completely relies on the reliability and reputation of the centralized entity. If the centralized entity encounters technical failures, malicious attacks, or defaults, the user's funds face a higher risk. Additionally, centralized cross-chain transactions may also leak user privacy, requiring users to carefully consider this method. Therefore, despite its convenience and efficiency providing significant benefits to users, security and trust are the main challenges faced by centralized cross-chain transactions.

BitVM Cross-Chain Bridge: This technology is relatively complex. First, in the Peg-in phase, users pay Bitcoin to a multi-signature address controlled by the BitVM alliance, locking the Bitcoin. An equivalent number of tokens are minted on Layer2, and these tokens are used for Layer2 transactions and applications. When users destroy Layer2 tokens, the Operator advances the payment. Subsequently, the Operator reimburses the corresponding amount of Bitcoin from the multi-signature pool controlled by the BitVM alliance. To prevent malicious actions by the Operator, the reimbursement process employs an optimistic challenge mechanism, allowing any third party to challenge malicious reimbursement actions, thwarting wrongdoing. This technology introduces an optimistic challenge mechanism, making it relatively complex. Moreover, the optimistic challenge mechanism involves a large number of challenge and response transactions, resulting in higher transaction fees. Therefore, the BitVM cross-chain bridge is only suitable for large transactions, similar to the issuance of U, leading to lower usage frequency.

Cross-Chain Atomic Swaps: Atomic swaps are contracts that enable decentralized cryptocurrency trading. In this context, "atomic" means that a change in ownership of one asset effectively corresponds to a change in ownership of another asset. This concept was first proposed by TierNolan on the Bitcointalk forum in 2013. For four years, atomic swaps remained in the theoretical realm. It wasn't until 2017 that Decred and Litecoin became the first blockchain systems to successfully complete atomic swaps. Atomic swaps must involve two parties, and no third party can interrupt or interfere with the swap process. This means that the technology is decentralized, censorship-resistant, provides good privacy protection, and enables high-frequency cross-chain transactions, making it widely used in decentralized exchanges. Currently, cross-chain atomic swaps require four transactions, and some proposals attempt to reduce the number of transactions to two, but this increases the real-time online requirements for both parties involved in the swap. Finally, cross-chain atomic swap technology mainly includes hash time locks and adaptor signatures.

Hash Time Lock (HTLC) Based Cross-Chain Atomic Swaps: The first project to successfully implement cross-chain atomic swaps is Decred, which utilized "hash locks" and "time locks" to achieve the atomic swaps proposed by TierNolan through on-chain scripts (or smart contracts). HTLC allows two users to conduct time-limited cryptocurrency transactions, meaning that the recipient must submit cryptographic proof ("secret") to the contract within a specified time (determined by the number of blocks or block height), or the funds will be returned to the sender. If the recipient confirms the payment, the transaction is successful. Therefore, both blockchains involved must have "hash lock" and "time lock" functionalities.

Although HTLC atomic swaps represent a significant breakthrough in decentralized exchange technology, there are several issues. These atomic swap transactions and the associated data are all conducted on-chain, leading to user privacy leakage. In other words, each time a swap occurs, the same hash value appears on both blockchains, only a few blocks apart. This means that observers can link the currencies involved in the swap, finding the same hash values in blocks that are close to each other (TimeStamp-wise). When cross-chain tracing of currencies occurs, it is easy to determine the source. Although this analysis does not reveal any related identity data, third parties can easily infer the identities of the participants involved.

Adaptor Signature Based Cross-Chain Atomic Swaps: The second type of swap provided by BasicSwap is called "adaptor signature" atomic swaps, based on a paper titled "Bitcoin--Monero Cross-chain Atomic Swap" published by Monero developer Joël Gugger in 2020. This paper can be seen as an implementation of Lloyd Fournier's 2019 paper One-Time Verifiably Encrypted Signatures, A.K.A. Adaptor Signatures. Adaptor signatures are additional signatures that combine with the initial signature to reveal secret data, allowing both parties to simultaneously disclose two parts of data to each other, and are a key component that enables the scriptless protocol for Monero atomic swaps.

Compared to HTLC atomic swaps, adaptor signature-based atomic swaps have three advantages: first, the adaptor signature swap scheme replaces the on-chain scripts relied upon by "secret hash" swaps, including time locks and hash locks. In other words, the secret and secret hash in HTLC swaps have no direct correspondence in adaptor signature swaps. Therefore, they are referred to as "scriptless scripts" in the Bitcoin research community. Additionally, since such scripts are not involved, on-chain space usage is reduced, making adaptor signature-based atomic swaps lighter and cheaper. Finally, HTLC requires both chains to use the same hash value, while the transactions involved in adaptor signature swaps cannot be linked, achieving privacy protection.

This article first introduces the principles of Schnorr/ECDSA adaptor signatures and cross-chain atomic swaps. It then analyzes the random number security issues present in adaptor signatures and the system and algorithm heterogeneity issues in cross-chain scenarios, providing solutions. Finally, it extends the application of adaptor signatures to achieve non-interactive digital asset custody.

Adaptor Signatures and Cross-Chain Atomic Swaps

2.1 Schnorr Adaptor Signatures and Atomic Swaps

2.2 ECDSA Adaptor Signatures and Atomic Swaps

2.2.1 Zero-Knowledge Proof zk { v | Ṽ = v ᐧ G , V = v ᐧ Y }

Security Issues and Solutions

3.1 Random Number Issues and Solutions

3.1.1 Random Number Leakage Issue

The pre-signatures of Schnorr/ECDSA adaptor signatures commit to the random number r as Ȓ = r ᐧ G. Additionally, in the zero-knowledge proof, the random number v is committed as Ṽ = v ᐧ G, V = v ᐧ Y. If the random number leaks, it can lead to the leakage of the private key.

Specifically, in the Schnorr protocol, if the random number r leaks, the private key x can be calculated based on the equation

ŝ = r + cx.

Similarly, in the ECDSA protocol, if the random number r leaks, the private key x can be calculated based on the equation

ŝ = r^{-1}(hash(m) + R_x x).

Finally, in the zero-knowledge proof protocol, if the random number v leaks, the random number r can be calculated based on the equation

z := v + cr,

which can further be used to calculate the private key x. Therefore, the random number must be deleted immediately after use.

3.1.2 Random Number Reuse Issue

For any two cross-chain transactions, if the adaptor signature protocol uses the same random number, it can lead to private key leakage. Specifically, in the Schnorr protocol, if the same random number r is used, then in the following system of equations, only r and x are unknown:

ŝ1 = r + c1 x,

ŝ2 = r + c2 x.

Thus, the system of equations can be solved to obtain the private key x.

Similarly, in the ECDSA adaptor signature protocol, if the same random number r is used, then in the following system of equations, only r and x are unknown:

ŝ1 = r^{-1}(hash(m1) + R_x x),

ŝ2 = r^{-1}(hash(m2) + R_x x).

Thus, the system of equations can be solved to obtain the private key x.

Finally, in the zero-knowledge proof protocol, if the same random number v is used, then in the following system of equations, only v and r are unknown:

z1 = v + c1 r,

z2 = v + c2 r.

Thus, the system of equations can be solved to obtain the random number r, which can further be used to solve for the private key x.

Similarly, if different users use the same random number, it can also lead to private key leakage. In other words, two users using the same random number can solve the system of equations to obtain each other's private keys. Therefore, RFC 6979 should be used to address the random number reuse issue.

3.1.3 Solution: RFC 6979

RFC 6979 specifies a method for generating deterministic digital signatures using DSA and ECDSA, addressing security issues related to generating random values k. Traditional DSA and ECDSA signatures rely on randomly generated random numbers k for each signing operation. If this random number is reused or generated improperly, it can jeopardize the security of the private key. RFC 6979 eliminates the need for generating random numbers by deterministically deriving k from the private key and the message to be signed. This ensures that when the same private key signs the same message, the signature is always the same, enhancing reproducibility and predictability. Specifically, the deterministic k is generated by HMAC. The process involves calculating the hash of the private key, message, and counter using a hash function (e.g., SHA256):

k = SHA256(s_k, msg, counter)

In the above equation, for simplicity, only the private key s_k, message msg, and counter counter are hashed, while the actual calculation process in RFC 6979 involves more hash computations. This equation ensures that k is unique for each message while being reproducible for the same inputs, reducing the risk of private key exposure associated with weak or compromised random number generators. Therefore, RFC 6979 provides a robust framework for deterministic digital signatures using DSA and ECDSA, addressing significant security issues related to random number generation and enhancing the reliability and predictability of digital signatures. This makes it a valuable standard for applications requiring high security and strict operational requirements. The Schnorr/ECDSA signatures have random number flaws that need to be mitigated using RFC 6979. Therefore, adaptor signatures based on Schnorr/ECDSA also face these issues and need to use the RFC 6979 specification to resolve them.

3.2 Cross-Chain Scenario Issues and Solutions

3.2.1 UTXO and Account Model System Heterogeneity Issues and Solutions

As shown in Figure 1, Bitcoin adopts the UTXO model and implements native ECDSA signatures based on the Secp256k1 curve. Bitlayer is an EVM-compatible Bitcoin L2 chain that also uses the Secp256k1 curve and supports native ECDSA signatures. Adaptor signatures implement the logic required for BTC swaps, while the corresponding Bitlayer swaps are supported by the powerful capabilities of Ethereum smart contracts.

Cross-chain atomic swaps based on adaptor signatures, or at least semi-scriptless adaptor signature schemes designed for ECDSA curves, are incompatible with Ethereum. The reason is that Ethereum uses an account model rather than a UTXO model. Specifically, in adaptor signature-based atomic swaps, refund transactions must be pre-signed. However, in the Ethereum system, if the nonce is unknown, pre-signing transactions is not possible. Therefore, one party can send a transaction between the completion of pre-signing and the execution of the transaction—this would invalidate the pre-signed transaction (as the nonce has been used and cannot be reused).

Moreover, from a privacy perspective, this means that the anonymity of Bitlayer swaps is superior to HTLC (as both parties of the swap can find the contract). However, since one party requires a public contract, the anonymity of Bitlayer swaps is lower than that of adaptor signatures. In the absence of a contract on one side, the swap transaction appears the same as any other transaction. However, on the side with the EVM contract, the transaction is clearly for an asset swap. Although one side has a public contract, it is impossible to trace it back to another chain even using complex chain analysis tools.

Figure 1. Cross-Chain Atomic Swaps in Heterogeneous Systems of UTXO and Account Models

Bitlayer currently supports native ECDSA signatures and can also implement Schnorr signature verification through smart contracts. If native Bitlayer transactions are used, refund transactions in atomic swaps cannot be pre-signed; Bitlayer smart contract transactions must be used to achieve atomic swaps. However, this process sacrifices privacy, meaning that transactions participating in atomic swaps in the Bitlayer system are traceable, but cannot be traced back to transactions in the BTC system. A Dapp application similar to Tornado Cash can be designed on the Bitlayer side to provide privacy services for transactions on the Bitlayer side in BTC and Bitlayer atomic swaps.

3.2.2 Same Curve, Different Algorithms, Adaptor Signature Security

As shown in Figure 2, suppose both Bitcoin and Bitlayer use the Secp256k1 curve, but Bitcoin uses Schnorr signatures while Bitlayer uses ECDSA. In this case, the adaptor signatures based on Schnorr and ECDSA are provably secure. Suppose given an ECDSA and Schnorr signature oracle, one can construct a simulator S to break ECDSA, then given only the ECDSA signature oracle, one can construct a simulator S to break ECDSA. However, ECDSA is secure. Similarly, suppose given an ECDSA and Schnorr signature oracle, one can construct a simulator S to break Schnorr signatures, then given only the ECDSA signature oracle, one can construct a simulator S to break Schnorr signatures. However, Schnorr signatures are secure. Therefore, in cross-chain scenarios, if adaptor signatures use the same curve but different signature algorithms, they are secure. In other words, adaptor signatures allow one end to use ECDSA while the other end uses Schnorr signatures.

Figure 2. Same Curve, Different Algorithms, Adaptor Signature

3.2.3 Different Curves, Adaptor Signatures Not Secure

Suppose Bitcoin uses the Secp256k1 curve and ECDSA signatures, while Bitlayer uses the ed25519 curve and Schnorr signatures. In this case, adaptor signatures cannot be used. The different curves lead to different orders of the elliptic curve groups, i.e., different modulus coefficients. When Bob adapts y to the ECDSA signature in the Bitcoin system, he calculates s := ŝ + y. At this point, the value space of y is the scalar space of the Secp256k1 elliptic curve group. Subsequently, Alice needs to use y to perform Schnorr signatures on the ed25519 elliptic curve group. However, the ed25519 curve has a cofactor of 8, and its modulus coefficient is not equal to that of the Secp256k1 elliptic curve group. Therefore, using y to perform Schnorr signatures on the ed25519 curve is not secure.

Digital Asset Custody Applications

Digital asset custody involves three parties: buyer Alice, seller Bob, and the custodian. Using adaptor signatures enables non-interactive threshold digital asset custody, instantiating a subset of threshold spending policies without requiring interaction. This subset consists of two types of participants: those who participate in initialization and those who do not, referred to as custodians. Custodians cannot sign arbitrary transactions but only send secrets to one of the supported parties.

On one hand, custodians can only choose from a few fixed settlement transactions and cannot sign new transactions with any of the other parties. Therefore, this secret release mechanism makes the flexibility of non-interactive threshold custody less than that of threshold Schnorr signatures. On the other hand, threshold Schnorr signatures can set up a 2-of-3 spending policy. However, the threshold Schnorr signature protocol requires three parties to run a decentralized key generation protocol. Therefore, the asset custody protocol based on adaptor signatures has a non-interactive advantage.

4.1 Non-Interactive Asset Custody Based on Adaptor Signatures

Figure 3. Non-Interactive Asset Custody Based on Adaptor Signatures

As shown in Figure 3, Alice and Bob want to create a 2-of-3 transaction output with a custodian, which contains a hidden policy. Depending on condition c, either Alice or Bob can spend this transaction output. If there is a dispute between Alice and Bob, the custodian (with public key E and private key e) decides which of Alice or Bob gets the asset.

1. Create an unsigned funding transaction that sends BTC to a 2-of-2 MuSig output between Alice and Bob.

2. Alice chooses a random value tA and sends a Schnorr pre-signature (\hat{R}A, \hat{s}A) for the transaction that sends the funding output to Bob, where the adaptor is tA ᐧ G. Alice also sends Bob a ciphertext containing the secret tA and adjusts the custodian public key to Ec = E + hash(E, c) G, with the ciphertext being the verifiable encryption C = Enc(Ec, tA). In this process, after receiving Alice's pre-signature, Bob adds his signature, which does not satisfy the 2-of-2 MuSig, thus preventing him from spending the funding output. Bob can only spend the funding output if he knows t_A (which can be provided by the custodian) or if Alice sends him a complete signature.

3. Correspondingly, Bob repeats step (2) based on his adaptor secret t_B. At this point, the transaction signed by Bob is to send the funding output to Alice.

4. Both Alice and Bob verify the validity of the received ciphertext, confirming that the ciphertext is an encryption of the secret against E_c, and then sign and broadcast the funding transaction. Verifiable encryption allows the custodian to be uninvolved in the setup phase and does not require a public contract c.

5. In the event of a dispute, Alice and Bob can send the ciphertext and condition c to the custodian, who can then make a judgment based on the actual situation, using the adjusted private key e + hash(E, c) to decrypt and send tA / tB to Bob / Alice.

If there is no dispute, Alice and Bob can spend the 2-of-2 MuSig output as they wish. If there is a dispute, either party can contact the custodian and request their adaptor secret tA or tB. Therefore, with the custodian's assistance, one party can complete the adaptor signature and broadcast the settlement transaction.

4.2 Verifiable Encryption

Classical verifiable encryption schemes based on discrete logarithms (Practical Verifiable Encryption and Decryption of Discrete Logarithms) cannot be used for Secp256k1 adaptors, as they only support verification of specially structured groups.

Currently, there are two promising ways to achieve verifiable encryption based on Secp256k1 discrete logarithms, namely Purify and Juggling.

Purify was initially proposed to create a MuSig protocol with deterministic nonces (DN), requiring each signer to use zero-knowledge proofs to demonstrate that their nonce is the result of correctly applying a pseudorandom function (PRF) to the public key and message. The Purify PRF can be efficiently implemented in the arithmetic circuits of Bulletproofs zero-knowledge protocols to create verifiable encryption schemes over Secp256k1 discrete logarithms. In other words, verifiable encryption is achieved using zkSnark.

Juggling encryption involves four steps: (1) splitting the discrete logarithm x into multiple segments xk of length l such that x = \sumk 2^{(k-1)l} xk; (2) using the public key Y to ElGamal encrypt the segments xk ᐧ G as \{Dk, Ek\} = \{xk ᐧ G + rk ᐧ Y, rk ᐧ G\}; (3) creating range proofs for each xk ᐧ G, proving that Dk is a Pedersen commitment to xk ᐧ G + rk ᐧ Y and that its value is less than 2^l; (4) using sigma protocols to prove that \{sum Dk, sum Ek\} is the correct encryption of xk ᐧ G.

During the decryption process, each xk ᐧ G is decrypted from \{Dk, Ek\}, and then xk is exhaustively searched (with a value range of [0, 2^l)).

Purify requires executing a PRF within Bulletproofs, which is relatively complex, while Juggling is theoretically simpler. Additionally, the differences in proof size, proof duration, and verification duration between the two are minimal.

Conclusion

This article provides a detailed description of the principles of Schnorr/ECDSA adaptor signatures and cross-chain atomic swaps. It thoroughly analyzes the random number leakage and reuse issues present in adaptor signatures and proposes the use of RFC 6979 to address these issues. Furthermore, it analyzes the cross-chain application scenarios, considering not only the differences between the UTXO model and account model of blockchains but also whether adaptor signatures support different algorithms and curves. Finally, it extends the application of adaptor signatures to achieve non-interactive digital asset custody and briefly introduces the cryptographic primitives involved—verifiable encryption.

References

1. Gugger J. Bitcoin - Monero cross-chain atomic swap [J]. Cryptology ePrint Archive, 2020.

2. Fournier L. One-time verifiably encrypted signatures aka adaptor signatures [J]. 2019, 2019.

3. https://crypto-in-action.github.io/ecdsa-blockchain-dangers/190816-secp256k1-ecdsa-dangers.pdf

4. Pornin T. Deterministic usage of the digital signature algorithm (DSA) and elliptic curve digital signature algorithm (ECDSA) [R]. 2013.

5. Komlo C, Goldberg I. FROST: flexible round-optimized Schnorr threshold signatures [C]// Selected Areas in Cryptography: 27th International Conference, Halifax, NS, Canada (Virtual Event), October 21-23, 2020, Revised Selected Papers 27. Springer International Publishing, 2021: 34-65.

6. https://github.com/BlockstreamResearch/scriptless-scripts/blob/master/md/NITE.md

7. https://particl.news/the-dex-revolution-basicswap-and-private-ethereum-swaps/

8. Camenisch J, Shoup V. Practical verifiable encryption and decryption of discrete logarithms [C]// Annual International Cryptology Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003: 126-144.

9. Nick J, Ruffing T, Seurin Y, et al. MuSig-DN: Schnorr multi-signatures with verifiably deterministic nonces [C]// Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. 2020: 1717-1731.

10. Shlomovits O, Leiba O. JugglingSwap: scriptless atomic cross-chain swaps [J]. arXiv preprint arXiv:2007.14423, 2020.