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

Original author: mutourend, lynndell

Introduction

With the rapid development of Bitcoin Layer2 expansion solutions, the frequency of cross-chain asset transfers between Bitcoin and its Layer2 counterpart has increased significantly. This trend is driven by the higher scalability, lower transaction fees, and high throughput provided by Layer2 technologies such as Bitlayer. These advances promote more efficient and economical transactions, thereby promoting the wider 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 solutions for cross-chain transactions between Bitcoin and Layer2, namely centralized cross-chain transactions, BitVM cross-chain bridges, and cross-chain atomic swaps. These three technologies differ in terms of trust assumptions, security, convenience, and transaction amounts, and can meet different application requirements.

Table 1. Comparison of cross-chain transaction technologies

Centralized cross-chain transactions: Users first pay Bitcoin to a centralized institution (such as a project party or an exchange), and the centralized institution pays the equivalent assets to the user's specified address on the Layer2 network, thereby completing the cross-chain asset transfer. The advantage of this technology is that it is fast and the matching process is relatively easy because the centralized institution can quickly confirm and process the transaction. However, the security of this method depends entirely on the reliability and reputation of the centralized institution. If the centralized institution encounters technical failures, malicious attacks, or defaults, the user's funds are at high risk. In addition, centralized cross-chain transactions may also leak user privacy, requiring users to carefully consider when choosing this method. Therefore, although its convenience and efficiency provide great convenience to users, security and trust are the main challenges facing centralized cross-chain transactions.

BitVM cross-chain bridge:This technology is relatively complex. First, in the Peg-in stage, users pay Bitcoin to the multi-signature address controlled by the BitVM Alliance to lock Bitcoin. The corresponding number of tokens is minted in Layer2, and the token is used to implement Layer2 transactions and applications. When the user destroys the Layer2 token, the Operator will advance the payment. Subsequently, the Operator reimburses the corresponding number of Bitcoins to the multi-signature pool controlled by the BitVM Alliance. To prevent the Operator from doing evil, the reimbursement process adopts an optimistic challenge mechanism, that is, any third party can challenge malicious reimbursement behavior and thwart the evil behavior. This technology introduces an optimistic challenge mechanism, so the technology is relatively complex. In addition, the optimistic challenge mechanism involves a large number of challenge and response transactions, and the transaction fee is high. Therefore, the BitVM cross-chain bridge is only suitable for ultra-large transactions, similar to the issuance of U, and thus has a low frequency of use.

Cross-chain atomic swaps:Atomic swaps are contracts that enable decentralized cryptocurrency transactions. In this context, "atomic" means that a change in ownership of one asset actually means a change in ownership of another asset. The concept was first proposed by TierNolan on the Bitcointalk forum in 2013. For 4 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 exchange process. This means that the technology is decentralized, uncensorable, has good privacy protection, and can achieve high-frequency cross-chain transactions, which makes it widely used in decentralized exchanges. Currently, a cross-chain atomic swap requires 4 transactions. Some solutions attempt to reduce the number of transactions to 2, but this will increase the real-time online requirements for both parties. Finally, cross-chain atomic swap technologies mainly include hash time locks and adapter signatures. Cross-chain atomic swaps based on hash time locks (HTLCs): The first project to successfully implement cross-chain atomic swaps was Decred, which used "hash locks" and "time locks" to implement the atomic swap proposed by TierNolan with the help of on-chain scripts (or smart contracts). HTLC allows two users to conduct time-limited cryptocurrency transactions, that is, the recipient must submit a cryptographic proof ("secret") to the contract within a specified time (determined by the number of blocks or block height), otherwise the funds will be returned to the sender. If the recipient confirms the payment, the transaction is successful. Therefore, both participating blockchains are required to have "hash lock" and "time lock" functions.

While HTLC atomic swaps are a major breakthrough in the field of decentralized exchange technology, there are the following problems. These atomic swap transactions and the data associated with them are all conducted on-chain, resulting in user privacy leakage. In other words, the same hash value appears on both blockchains at each exchange, with only a few blocks apart. This means that an observer can link the currencies involved in the exchange, that is, find the same hash value in blocks close to each other (TimeStamp-wise). When tracking currencies across chains, it is easy to determine the source. Although this analysis does not reveal any relevant identity data, third parties can easily infer the identities of the participants involved.

Cross-chain atomic swaps based on adapter signatures:The second type of swap provided by BasicSwap is called an “adapter signature” atomic swap, based on a 2020 paper by Monero developer Joël Gugger titled “Bitcoin–Monero Cross-chain Atomic Swap”. The paper can be said to be an implementation of Lloyd Fournier’s 2019 paper One-Time Verifiably Encrypted Signatures, A.K.A. Adaptor Signatures. An adapter signature is an additional signature that is combined with the initial signature to reveal secret data, enabling two parties to reveal two pieces of data to each other simultaneously, and is a key component of the scriptless protocol that makes atomic swaps of Monero pairs possible.

Compared with HTLC atomic swaps, adapter-signature-based atomic swaps have three advantages: First, the adapter-signature swap scheme replaces the on-chain scripts that the "secret hash" swap relies on, including time locks and hash locks. In other words, the secret and secret hash in the HTLC swap have no direct correspondence in the adapter-signature swap. Therefore, it is called "scriptless scripts" in the Bitcoin research community. In addition, since such scripts are not involved, the space occupied on the chain is reduced, making adapter-signature-based atomic swaps lighter and cheaper. Finally, HTLC requires that each chain use the same hash value, while the transactions involved in the adapter-signature atomic swap cannot be linked to achieve privacy protection.

This article first introduces the Schnorr/ECDSA adapter signature and the principle of cross-chain atomic swaps. Then, the random number security issues in the adapter signature and the system heterogeneity and algorithm heterogeneity problems in the cross-chain scenario are analyzed, and solutions are given. Finally, the adapter signature is extended and applied to achieve non-interactive digital asset custody.

Adapter Signature and Cross-Chain Atomic Swap

2.1 Schnorr Adapter Signature and Atomic Swap

2.2 ECDSA Adapter Signature and Atomic Swap

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

Security Issues and Solutions

3.1 Random number problems and solutions

3.1.1 Random number leakage problem

The pre-signature of the Schnorr/ECDSA adapter signature commits to the random number r Ȓ = r ᐧ G. In addition, the zero-knowledge proof commits to the random number v Ṽ = v ᐧ G, V = v ᐧ Y. If the random number is leaked, it will lead to the leakage of the private key.

Specifically, in the Schnorr protocol, if the random number r is leaked, it can be leaked according to the equation

ŝ = r + cx Calculate the private key x. Similarly, in the ECDSA protocol, if the random number r is leaked, the private key x can be calculated according to the equation ŝ = r^{-1}(hash(m)+R_x x). Finally, in the zero-knowledge proof protocol, if the random number v is leaked, the random number r can be calculated according to the equation z := v + cr, and the private key x can be further calculated based on the random number r. Therefore, the random number needs to be deleted immediately after use.

3.1.2 Random Number Reuse Problem

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

ŝ_1 = r + c_1 x,

ŝ_2 = r + c_2 x.

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

Similarly, in the ECDSA adapter signature protocol, if the same random number r is used, only r and x are unknown in the following set of equations

ŝ_1 = r^{-1}(hash(m_1)+R_x x)

ŝ_2 = r^{-1}(hash(m_2)+R_x x)

Therefore, 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, only v and r are unknown in the following set of equations

z_1 = v+c_1 r,

z_2 = v+c_2 r.

Therefore, the system of equations can be solved to obtain the random number r, and then the system of equations can be further solved to obtain the private key x.

By analogy, if different users use the same random number, the private key will also be leaked. In other words, two users using the same random number can solve the system of equations and obtain each other's private key. Therefore, RFC 6979 should be used to solve the random number reuse problem.

3.1.3 Solution: RFC 6979

RFC 6979 specifies a method for generating deterministic digital signatures using DSA and ECDSA, solving the security issues associated with generating random values k. Traditional DSA and ECDSA signatures rely on a random number k that is randomly generated for each signing operation. If this random number is reused or generated improperly, the security of the private key will be compromised. RFC 6979 eliminates the need to generate a random number by deterministically deriving k from the private key and the message to be signed. This ensures that the signature is always the same when the same private key is used to sign the same message, thereby enhancing reproducibility and predictability. Specifically, the deterministic k is generated by HMAC. The process involves a hash function (such as SHA256) calculating a hash value for the private key, message, and counter,

k = SHA256(sk, msg, counter)

In the above equation, for simplicity, only the private key sk, message msg, and counter counter are hashed. The actual calculation process in RFC 6979 involves more hash calculations. This equation ensures that k is unique for each message while being reproducible for the same input and reduces the risk of private key exposure associated with weak or compromised random number generators. Therefore, RFC 6979 provides a powerful framework for deterministic digital signatures using DSA and ECDSA, addresses significant security issues associated with random number generation, and enhances the reliability and predictability of digital signatures. This makes it a valuable standard for applications that require high security and meet strict operational requirements. Schnorr/ECDSA signatures have random number flaws that need to be guarded against using RFC 6979. Therefore, Schnorr/ECDSA-based adapter signatures also have these problems and also need to use the RFC 6979 specification to address these problems.

3.2 Cross-chain scenario problems and solutions

3.2.1 UTXO and account model system heterogeneity problems and solutions

As shown in Figure 1, Bitcoin uses the UTXO model and implements native ECDSA signatures based on the Secp256k1 curve. Bitlayer is EVM-compatible with the Bitcoin L2 chain, using the Secp256k1 curve and supporting native ECDSA signatures. The adapter signature implements the logic required for BTC exchange, while the Bitlayer exchange counterpart is supported by the powerful functions of Ethereum smart contracts.

Cross-chain atomic swaps based on adapter signatures, or at least semi-scriptless adapter signature schemes designed for ECDSA curves, are incompatible with Ethereum. The reason is that Ethereum is an account model, not a UTXO model. Specifically, refund transactions are required to be pre-signed in atomic swaps based on adapter signatures. However, in the Ethereum system, it is impossible to pre-sign a transaction without knowing the nonce. Therefore, one party can send a transaction between the time the pre-signature is completed and the transaction is executed - which will invalidate the pre-signed transaction (because the nonce has been used and cannot be reused).

In addition, from a privacy perspective, this means that Bitlayer swaps are more anonymous than HTLCs (the contract is available to both parties of the swap). However, the need for one party to have a public contract makes Bitlayer swaps less anonymous than adapter signatures. On the side without a contract, the swap transaction looks like any other transaction. However, on the side with the EVM contract, the transaction is clearly for an asset swap. Although one party has a public contract, it is impossible to trace it back to another chain, even with sophisticated chain analysis tools.

Figure 1. UTXO and account model heterogeneous system cross-chain atomic swap

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 are required to implement atomic swaps. However, this process will sacrifice privacy, that is, transactions participating in atomic swaps in the Bitlayer system are traceable, but cannot be traced back to transactions in the BTC system. Dapp applications such as Tornado Cash can be designed on the Bitlayer side to provide privacy services for transactions on the Bitlayer side in atomic swaps between BTC and Bitlayer.

3.2.2 Same curve, different algorithms, adapter signature security

As shown in Figure 2, assume that both Bitcoin and Bitlayer use the Secp256k1 curve, but Bitcoin uses Schnorr signatures, while Bitlayer uses ECDSA. In this case, the adapter signature based on Schnorr and ECDSA is provably secure. Assuming that given the ECDSA and Schnorr signature oracles, a simulator S can be constructed to break ECDSA, then given only the ECDSA signature oracle, a simulator S can be constructed to break ECDSA. However, ECDSA is secure. Similarly, assuming that given the ECDSA and Schnorr signature oracles, a simulator S can be constructed to break Schnorr signatures, then given only the ECDSA signature oracle, a simulator S can be constructed to break Schnorr signatures. However, Schnorr signatures are secure. Therefore, in the cross-chain scenario, the adapter signature uses the same curve but different signature algorithms, which is safe. In other words, the adapter signature allows one end to use ECDSA and the other end to use Schnorr signature.

Figure 2. Same curve, different algorithm, adapter signature

3.2.3 Different curves, adapter signature is not safe

Assume that Bitcoin uses the Secp256k1 curve and ECDSA signature, while Bitlayer uses the ed25519 curve and Schnorr signature. In this case, the adapter signature cannot be used. Due to the different curves, the order of the elliptic curve group is different, that is, the modular coefficients are different. 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 signature on the ed25519 elliptic curve group. However, the cofactor of the ed25519 curve is 8, and the modulus coefficient is not equal to the modulus coefficient of the Secp256k1 elliptic curve group. Therefore, it is unsafe to use y to perform Schnorr signature on the ed25519 curve.

Digital Asset Custody Application

There are three parties involved in digital asset custody, namely, Alice, the buyer, Bob, the seller, and the custodian. Using adapter signatures, non-interactive threshold digital asset custody can be achieved, and a subset of threshold spending strategies can be instantiated without interaction. This subset consists of 2 types of participants: participants who participate in initialization, and participants who do not participate in initialization, the latter is called the custodian. The custodian cannot sign arbitrary transactions, but only sends secrets to one of the supported parties.

On the one hand, the custodian can only choose from several fixed settlement transactions, and cannot sign new transactions with one of the other participants. Therefore, this secret release mechanism makes non-interactive threshold custody less flexible than threshold Schnorr signatures. On the other hand, 2-of-3 spending strategies can be set using threshold Schnorr signatures. However, the threshold Schnorr signature protocol requires three parties to run a decentralized key generation protocol. Therefore, the asset custody protocol based on adapter signatures has the advantage of being non-interactive.

4.1 Non-interactive asset custody based on adapter signatures

Figure 3. Non-interactive asset custody based on adapter signatures

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

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

2. Alice chooses a random value t_A and sends a Schnorr pre-signature (\hat{R}_A,\hat{s}_A) of a transaction with an adapator of t_A ᐧ G to Bob. The transaction is to send the funding output to Bob. Alice also sends Bob a ciphertext, which contains a verifiably encrypted \textbf{C = Enc(E_c, t_A) of the secret t_A and adjusts the escrow public key E to E_c = E + hash(E, c)G. In this process, after Bob receives Alice's pre-signature, he adds his own signature, which does not satisfy 2-of-2 MuSig and cannot spend the funding output. The funding output can only be spent if Bob knows t_A (provided by the escrow party) or Alice signs a full signature and sends it to Bob.

3. In response, Bob repeats step (2) based on his adaptor secret t_B. The transaction signed by Bob now sends the funding output to Alice.

4. Alice and Bob both verify the validity of the received ciphertext and confirm that the ciphertext is an encryption of the secret E_c, and then sign and broadcast the funding transaction. Verifiable encryption eliminates the need for a custodian to participate in the setup phase and does not require the 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 and use the adjusted private key e+hash(E, c) to decrypt and send t_A/t_B 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 its adaptor secret t_A or t_B. Thus, one of the parties, with the help of the custodian, can complete the adapter signature and broadcast the settlement transaction.

4.2 Verifiable Encryption

The classical verifiable encryption scheme based on discrete logarithms (Practical Verifiable Encryption and Decryption of Discrete Logarithms) cannot be used for Secp256k1 adaptors because it only supports verification of specially structured groups.

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

Purify was originally proposed to create a MuSig protocol with a deterministic nonce (DN), requiring each signer to use zero-knowledge proof that its nonce is the result of correctly applying a pseudo-random function (PRF) to the public key and message. Purify PRF can be efficiently implemented in the arithmetic circuits of the Bulletproofs zero-knowledge protocol to create a verifiable encryption scheme for discrete logarithms on Secp256k1. In other words, verifiable encryption using zkSnark.

Juggling encryption consists of four steps: (1) Split the discrete logarithm x into multiple segments x_k of length l, such that x = \sum _k 2^{(k-1)l} x_k; (2) Use the public key Y to perform ElGamal encryption on the segments x_k ᐧ G \{ D_k, E_k\} = \{ x_k ᐧ G + r_k ᐧ Y, r_k ᐧ G \}; (3) Create a range proof for each x_k ᐧ G to prove that D_k is a Pedersen commitment x_k ᐧ G + r_k ᐧ Y, and its value is less than 2^l; (4) Use the sigma protocol to prove that \{sum D_k, sum E_k\} is a range proof for x_k ᐧ G. Correct encryption of x_k ᐧ G.

During the decryption process, decrypt each x_k ᐧ G from \{D_k, E_k\}, and then exhaustively search for x_k (value range is [0, 2^l)).

Purify needs to execute a PRF in Bulletproofs, which is relatively complicated, while Juggling is theoretically simpler. In addition, the difference between the two in proof size, proof time and verification time is very small.

Summary

This paper describes in detail the principles of Schnorr/ECDSA adapter signature and cross-chain atomic swap. In-depth analysis of the random number leakage and duplication problems in adapter signatures, and proposed the use of RFC 6979 to solve these problems. In addition, a detailed analysis is made on the cross-chain application scenarios. Not only should the difference between the UTXO model and the account model of the blockchain be considered, but also whether the adapter signature supports different algorithms and curves. Finally, the adapter signature is extended to realize non-interactive digital asset custody, and the involved cryptographic primitives - verifiable encryption are briefly introduced.

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.

「Original link」

欢迎加入律动 BlockBeats 官方社群：

Telegram 订阅群：https://t.me/theblockbeats

Telegram 交流群：https://t.me/BlockBeats_App

Twitter 官方账号：https://twitter.com/BlockBeatsAsia