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

Original link: https:/ /blog.bitlayer.org/Adaptor_Signatures_and_Its_Application_to_Cross-Chain_Atomic_Swaps/

Author: mutourend, lynndell

1. Introduction

With the rapid development of Bitcoin’s Layer 2 expansion plan, the frequency of cross-chain asset transfers between Bitcoin and its Layer 2 corresponding network has increased significantly. This trend is driven by the higher scalability, lower transaction fees and high throughput provided by Layer 2 technologies such as Bitlayer. These advancements facilitate more efficient and economical transactions, thereby promoting wider adoption and integration of Bitcoin across a variety of applications. As a result, interoperability between Bitcoin and Layer 2 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 Layer 2, namely centralized cross-chain transactions and BitVM cross-chain bridge. and cross-chain atomic swaps. These three technologies are different in terms of trust assumptions, security, convenience, transaction limits, etc., and can meet different application needs.

Table 1. Comparison of cross-chain transaction technologies

Centralized cross-chain transaction: Users first transfer bits If the currency is paid to a centralized institution (such as a project party or an exchange), the centralized institution will pay the equivalent value of assets to the address specified by the user on the Layer 2 network, thus 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 entirely relies on the reliability and credibility of the centralized institution. If the centralized institution encounters technical failures, malicious attacks, or defaults, users' funds will face higher risks. In addition, centralized cross-chain transactions may also leak user privacy, and users need to consider carefully when choosing this method. Therefore, although its convenience and efficiency provide users with great convenience, 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 stage, users pay Bitcoin to a multi-signature address controlled by the BitVM Alliance to lock the Bitcoin. A corresponding number of tokens are minted in Layer 2, and the tokens are used to implement Layer 2 transactions and applications. When the user destroys the Layer 2 token, the operator will advance the payment. Subsequently, the Operator reimburses the corresponding number of Bitcoins in the multi-signature pool controlled by the BitVM Alliance. In order to prevent operators from doing evil, the reimbursement process adopts an optimistic challenge mechanism, that is, any third party can challenge malicious reimbursement behaviors and thwart evil behaviors. 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, with higher transaction fees. Therefore, the BitVM cross-chain bridge is only suitable for very large transactions, similar to the additional issuance of U, and therefore is used less frequently.

Cross-chain atomic swap: Atomic swap is a contract that implements decentralized cryptocurrency transactions. In this case, "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 four years, atomic swaps have remained in the realm of theory. Until 2017, 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, uncensored, has good privacy protection, and can achieve high-frequency cross-chain transactions, thus being widely used in decentralized exchanges. Currently, cross-chain atomic swap requires 4 transactions. Some solutions try to compress the number of transactions to 2, but this will increase the real-time online requirements for both parties to the exchange. Finally, cross-chain atomic swap technology mainly includes hash time locks and adapter signatures.

Cross-chain atomic swap based on Hash Time Lock (HTLC): The first project to successfully implement cross-chain atomic swap is Decred, which uses "hash lock" " and "time lock" realize the atomic exchange proposed by TierNolan with the help of on-chain scripts (or smart contracts). HTLC allows two users to conduct time-limited cryptocurrency transactions, i.e. the recipient must submit a cryptographic proof ("secret") to the contract within a specified time (determined by block number or block height), otherwise the funds will be returned to the sender By. If the recipient confirms the payment, the transaction is successful. Therefore, both participating blockchains are required to have "hash lock" and "time lock" functions.

Although HTLC atomic swap is a major breakthrough in the field of decentralized exchange technology, there are the following problems. These atomic swap transactions and the data related to them are performed on-chain, leading to user privacy leaks. In other words, every time there is an exchange, the same hash will appear on both blockchains, separated by just a few blocks. This means that observers can correlate currencies participating in an exchange, i.e. find the same hash value in blocks that are close to each other (TimeStamp-wise). When tracking currency across chains, it is easy to determine the source. Although this analysis does not reveal any relevant identifying data, third parties can easily infer the identities of the actors involved.

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

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

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

2. Adapter signature and cross-chain atomic exchange

2.1 Schnorr adapter signature and atomic exchange

p>

2.2 ECDSA Adapter Signature and Atomic Swap

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

3. Security issues and solutions

3.1 Random Number problems and solutions

3.1.1 Random number leakage problem

Schnorr/ECDSA adapter Signed pre-signatures all commit to a random number $r$ Ȓ = r ᐧ G. In addition, the zero-knowledge proof promises the random number $v$ that $Ṽ=v ᐧ G,V=v ᐧ Y$. If the random number is leaked, the private key will be leaked.

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

$ŝ  = r + c x.$

Calculate the private key $x$.

Similarly, in the ECDSA protocol, if the random number $r$ leaks, it can be calculated according to the equation

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

Calculate the private key to get $x$.

Finally, in the zero-knowledge proof protocol, if the random number $v$ is leaked, it can be determined according to the equation

$z := v + c r.$

Calculate the random number $r$, and then further calculate based on the random number $r$ Extract the private key $x$. Therefore, the random numbers need to be deleted immediately after use.

3.1.2 Random number reuse problem

For any two cross-chain transactions, if If the adapter signature protocol uses the same random number, the private key will be leaked. 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$ in the following system of equations is unknown

$ ŝ_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 , obtain the private key $x$.

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

$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 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 address the issue of random number reuse.

3.1.3 Solution: RFC 6979

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

$k = SHA256(sk, msg, counter) .$

In the above equation, for simplicity of expression, the hash value is only calculated for the private key sk, message msg and counter counter. The actual calculation process in RFC 6979 More hash calculations involved. 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, resolves significant security issues related to random number generation, and enhances the reliability and predictability of digital signatures. This makes it a valuable standard for applications requiring high security and compliance with strict operational requirements. Schnorr/ECDSA signatures have random number defects, and RFC 6979 needs to be used to prevent them. Therefore, adapter signatures based on Schnorr/ECDSA also have these problems, and the RFC 6979 specification also needs to be used to solve these problems.

3.2 Cross-chain scenario problems and solutions

3.2.1 UTXO and account model system Heterogeneous problems and solutions

As shown in Figure 1, Bitcoin uses the UTXO model to implement native ECDSA signatures based on the Secp256k1 curve. Bitlayer is EVM compatible with the Bitcoin L2 chain, uses the Secp256k1 curve, and supports native ECDSA signatures. Adapter Signature implements the logic required for BTC swaps, while the Bitlayer swap counterpart is powered by the power of Ethereum smart contracts.

Cross-chain atomic swaps based on adapter signatures, or at least semi-scriptless adapter signature schemes designed to work with the ECDSA curve, are not compatible with Ethereum. The reason is that Ethereum is an account model, not a UTXO model. Specifically, atomic swaps based on adapter signatures require that refund transactions must be pre-signed. However, in the Ethereum system, transactions cannot be pre-signed without knowing the nonce. Therefore, a party could send a transaction between the completion of the pre-signing and the execution of the transaction - which would invalidate the pre-signed transaction (since the nonce has already been used and cannot be reused).

In addition, from a privacy perspective, this means that the anonymity of Bitlayer swap is better than HTLC (both parties to the swap can find the contract). However, since one party is required to have a public contract, the anonymity of Bitlayer swap is lower than that of adapter signature. With no contract on one side, a swap transaction looks like any other transaction. However, on the side with the EVM contract, the transaction is obviously for asset swap. Although one party has a public contract, it is impossible to trace it back to another chain, even using sophisticated chain analysis tools.

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

Bitlayer currently supports native ECDSA signature and Schnorr signature verification can also be implemented through smart contracts. If you use native Bitlayer transactions, you cannot pre-sign refund transactions in atomic swaps; you need to use Bitlayer smart contract transactions to achieve atomic swaps. However, this process will sacrifice privacy, that is, transactions participating in atomic swaps in the Bitlayer system are traceable, but transactions in the BTC system cannot be traced. Dapp applications such as 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 algorithm, adapter signature security

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

Figure 2. Same curve, different algorithm, adapter signature

3.2.3 Different curve, adapter The signature is not secure

Assume that Bitcoin uses the Secp256k1 curve and ECDSA signature, while Bitlayer uses the ed25519 curve and Schnorr signature. In this case, adapter signature cannot be used. Because the curves are different, the order of the elliptic curve group is different, that is, the module coefficients are different. When Bob adapts $y$ to the ECDSA signature in the Bitcoin system, he calculates $s:= ŝ+y$. At this time, the value space of $y$ is the scalar space of the Secp256k1 elliptic curve group. Subsequently, Alice needs to use $y$ to perform a Schnorr signature on the ed25519 elliptic curve group. However, the cofactor of the ed25519 curve is 8, and the module coefficient is not equal to the module coefficient of the Secp256k1 elliptic curve group. Therefore, it is unsafe to use $y$ for Schnorr signatures on the ed25519 curve.

4. Digital asset custody application

Digital asset custody has three participants, namely : Buyer Alice, seller Bob and escrow party. Using adapter signatures enables non-interactive threshold digital asset custody and instantiates a subset of threshold spending strategies without interaction. This subset consists of two types of participants: participants who participate in initialization and participants who do not participate in initialization. The latter are called custodians. The custodian cannot sign arbitrary transactions and only sends secrets to one of the supporting parties.

On the one hand, the custodian can only choose among several fixed settlement transactions and cannot sign new transactions with one of the other parties. This secret release mechanism therefore makes non-interactive threshold hosting less flexible than threshold Schnorr signatures. On the other hand, a 2-of-3 spending policy can be set up using threshold Schnorr signatures. However, the threshold Schnorr signature protocol requires three parties to run the decentralized key generation protocol. Therefore, asset escrow protocols based on adapter signatures have the advantage of being non-interactive.

4.1 Non-interactive asset hosting based on adapter signature

Figure 3. Non-linearity based on adapter signature Interactive Asset Escrow

As shown in Figure 3, Alice and Bob want to create a 2-of-3 transaction output with a stealth strategy that contains an escrow square. 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 someone between Alice and Bob 2-of-2 MuSig output.

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

3. Correspondingly, Bob repeats step (2) based on his adapter secret $t_B$. The transaction signed by Bob at this time is to send the funding output to Alice.

4. Both Alice and Bob verify the validity of the received ciphertext and confirm that the ciphertext is an encryption of the secret $E_c$, thus Sign and broadcast the funding transaction. Verifiable encryption eliminates the need for a custodian to participate in the setup phase and does not require a public contract $c$.  

5. When there is a dispute, Alice and Bob can send the ciphertext and condition c to the custodian, and the custodian can The actual situation is determined, and the adjusted private key $e+hash(E, c)$ is used 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 want. If there is a dispute, either party may contact the escrow and request its adapter secret $t_A$ or $t_B$. Therefore, one of the parties, with the help of the escrow party, can complete the adapter signature and broadcast the settlement transaction.

4.2 Verifiable Encryption

Classic verifiable encryption scheme based on discrete logarithms (Practical Verifiable Encryption and Decryption of Discrete Logarithms) cannot be used with Secp256k1 adapters, as it only supports verification of specially structured groups.

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

Purify was originally proposed to create the MuSig protocol with a deterministic nonce (DN), requiring each signer to use zero-knowledge to prove that its nonce is a false The result of the random function (PRF) being correctly applied to the public key and message. Purify PRF can be efficiently implemented in the arithmetic circuit of Bulletproofs zero-knowledge protocol for creating verifiable encryption schemes on discrete logarithms on Secp256k1. In other words, use zkSnark to implement verifiable encryption.

Juggling encryption includes four steps: (1) Divide the discrete logarithm $x$ into multiple segments $x_k$ of length $l$, Make $x = \sum _k 2^{(k-1)l} x_k$; (2) Use the public key $Y$ to perform ElGamal encryption on the fragment $x_k ᐧ  G$ $\{ D_k, E_k\} = \ { x_k ᐧ  G + r_k ᐧ  ᐧ 

In the decryption process, $\{D_k, E_k\}$ is decrypted to get each $x_k ᐧ  G$, and then $x_k is searched exhaustively $ (the value range is $[0, 2^l)$).

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

5. Summary

This article discusses the Schnorr/ECDSA adapter signature and cross-chain atomic exchange. The principles are described in detail. An in-depth analysis of the random number leakage and duplication problems in adapter signatures was conducted, and the use of RFC 6979 was proposed to solve these problems. In addition, it analyzes in detail that in cross-chain application scenarios, not only the difference between the UTXO model and the account model of the blockchain should be considered, but also whether the adapter signature supports different algorithms, different curves and other issues. Finally, the adapter signature is extended and applied to realize non-interactive digital asset custody, and the cryptographic primitives involved - 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 adapter 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.