Discussion & Feedback on adapting Bitcoin<->Monero atomic swap protocol for Algorand <-> Monero

[HashMapsData2Value]

Introduction

Recently I came across this paper: Bitcoin–Monero Cross-chain Atomic Swap by Joël Gugger. It describes a protocol for performing an atomic swap between Bitcoin (BTC) and Monero (XMR), a blockchain famous for its privacy-preserving properties. The company Comit deployed an MVP, which is described in this blog post and this video presentation. Joël, aka H4sh3d, also made this presentation. The current development is being done by Farcaster (led by H4sh3d) here, a collection of microservices for running cross-chain atomic swaps.

I've been trying to wrap my head around this protocol, fascinated by the possibilities. I confess however that I do not understand all the details of this protocol, not being a cryptographer. Somehow I did come up with a suggestion for a protocol that could be used on Algorand, requiring the addition of one Opcode to the Algorand source code - an inverted ed25519verify, aka ed25519verifyinv. Edit: Alternatively, an ed25519skpkverify.

I'd love it if it the experts at Algorand could take a look into this, poke holes or suggest a better way to adapt the protocol. The Bitcoin one is different, having some UTXO stuff, and also makes use of ZKP for some stuff, I believe due to the fact that Bitcoin uses Secp256k1 elliptic curves and Monero, like Algorand, uses ed25519 elliptic curves.

About Monero

In Monero, transactions are completely anonymous and it is not possible to view the balances of others. They pride themselves on being "what Bitcoin was meant to be in the first place".

There are many who appreciate Monero for the privacy it allows, for various reasons, but who struggle to get access to it. The only way - until the release of that MVP - to get XMR has been through one of the murkier exchanges, or by mining it yourself. If we could somehow find a way to go from Algo -> XMR, it would be a benefit to our community. We'd be able to "break the chains", i.e. break the connections between account transactions on the Algorand blockchain, that otherwise allow analyzers - including scammers, malicious people - to tie accounts together. Algo could flow from account A ("life savings"), into Monero, then into account B ("payments account") back on Algorand, without anyone able to draw any kind of connection. The described protocol, assuming it is valid, could be done trustlessly in such a way that two people, anonymous to each other, could orchestrate the whole thing without having to exchange any more information than is necessary.

Adaptor Signatures and VES

One issue with Monero is that there are no smart contracts or even a scripting language. There are just pure transactions going back and forth. This has hampered efforts to create cross-chain DEXes and do atomic swaps using hashed time locked contracts (HTLC). One solution that has emerged, however, is called Adaptor Signatures, or One-Time Verifiable Encrypted Signatures (VES). The paper referred in Joël's paper on this subject is this paper by Lloyd Fournier. They allow for smart contract logic without smart contracts (aka, scriptless scripts), by doing a form of multi-party computation that at each step intentionally leaks information that another actor can make use of. Information like the contents of a private key.

Monero is an UTXO blockchain, though fungible unlike Bitcoin. You generate Spend Keypair (pk_S, sk_S) and View Keypair (pk_V, sk_V). To transact to someone, you send Monero to their public spend key pk_S which they can spend themselves with sk_S. If you have access to sk_V you can view the contents of all the transactions that have entered into pk_S. We will make use of this in the protocol.

Protocol

We have the following two actors:

• Alice (A) has Algo and wants XMR
• Bob (B) has XMR and wants Algo

They communicate with each other and determine the amount of Algo and XMR to swap, considering the exchange rate and fees and so on. (Of course, either one of them could be a DEX with a lot of liquidity.)

Monero prep-work

On Monero, both Alice and Bob generate a Spend keypair ((pk_S_A, sk_S_A), (pk_S_B, sk_S_B)) and a View keypair ((pk_V_A, sk_V_A), (pk_V_B, sk_V_B)). They exchange all the keys EXCEPT for the private spend keys (sk_S_A and sk_S_B).

Both can combine the keys and create NEW keypairs! pk_S_A + pk_S_B ≡ pk_S, sk_V_A + sk_V_B ≡ sk_V. With sk_V they can both view the XMR stored in pk_S. However, since they do not have the other person's secret spend key, they cannot construct sk_S, the spend key that actually allows you to spend the XMR inside pk_S. (Note that pk_S is still empty.)

Algorand prep-work

On Algorand, Alice creates an escrow smart contract that will contain the Algo Bob wants. The smart contract can be interacted with in different ways, depending on when. Alice and Bob agree on a time t_0, time t_1 and a safety margin m blocks. Bob also provides his Algorand account address.

We presume that there is an opcode called the ed25519verifyinv. The current ed25519verify opcode allows you to pass in data A, signature B and public key C. Assuming that the signature B has indeed been signed with the private key to C, ed25519verify will return a 1.

ed25519verifyinv instead takes in data A, signature B and privkey C. The data A has actually been signed with a pubkey and providing the right private key C will have ed25519verifyinv return 1.

Edit: Alternatively, we could use ed25519skpkverify. ed25519skpkverify instead takes in an ed25519 private key A and a public key B. You can imagine that B has been hardcoded into the smart contract at its deployment, representing either pk_S_A (Alice Refunds) or pk_S_B (Bob Claims). It generates a public key C from the private key A. If B == C, ed25519skpkverify returns 1.

At first glance this sounds crazy - by definition we want the PRIVATE key to stay private, performing this operation means intentionally leaking the private key the entirety of the Algorand blockchain and the world at large... Yes, that is the point.

Alice specifies the smart contract in the following way:

From start until t_0, the following can be done:

• Alice can refund the Algo from the smart contract account back into her account, PROVIDED that ed25519verifyinv(A, B, input-C) returns 1. A is some random data, signature B corresponds to A signed with pk_S_A. Thus, input-C MUST be sk_S_A,
• Alice can call a function Ready which sets a boolean.

After t_0, until t_1, the following can be done:

• IF Ready was NOT set, Alice can still refund. Bob does nothing.
• IF Ready was set, Alice cannot refund. Bob can CLAIM the Algo to his own account, PROVIDED that ed25519verifyinv(A, B, input-C) returns 1. In this case, B corresponds to A (random data) signed with pk_S_B. Thus, input-C MUST be sk_S_B.

After t_1:

• Alice can refund, without any conditions.

Protocol Begins

Alice and Bob have shared all the information with each other.

1. Alice deploys the smart contract specified above. She also seeds the smart contract with some amount of Algo.

2. Alice has access to pk_V and is constantly scanning the Monero blockchain to see if Bob has filled pk_S with the right amount of XMR.

3. • IF at t_0 - m (safety margin to give some breathing room) Bob has still not filled up pk_S to the right amount, Alice will refund her Algo back to herself, leaking her sk_S_A to the world. Or if Alice had simply changed her mind and wanted to cancel. Bob, scanning the Algorand blockchain, notices, grabs sk_S_A, combines it with his sk_S_B and constructs sk_S, giving him access to any XMR he had locked up in pk_S. END.

• IF Alice instead is content with the XMR Bob locked up in pk_S, she calls Ready.

• IF Alice does nothing they enter t_0 regardless.

• Bob claims the Algo, leaking his sk_S_B. Alice combines it with her sk_S_A and constructs sk_S, giving HER control over the XMR in pk_S. She can choose to keep them there, secure in that Bob cannot claim them, or she can send them elsewhere. END.

• OR Bob doesn't claim the Algo, for whatever reason. Alice just waits long enough (t1+) and she can get all of her Algo back, but in such a way that she does NOT leak her sk_S_A. Bob, unless he is able to persuade Alice to hand over her sk_S_A, will thus never be able to recover the XMR he locked up. This creates an incentive for Bob to stick to the timeline. END.

Weakness

One problem lies in 3a, where Alice might lock up her funds and, if she somehow gets disconnected from Algorand, could end up with Bob simply claiming her funds without having locked up any XMR. There is in fact an incentive on Bob to attack Alice. Alice needs to be vigilant and online.

On the other hand, if Bob gets disconnected and is unable to claim in time, Alice will simply regain her Algo. While she will have punished Bob, there is not the same incentive to sabotage him, beyond somehow preventing his claim transaction from staying in the mempool until t_1+. The mechanism design of Algorand's PPoS makes it very difficult for Alice to target any specific block proposer. And the fast speed, and instant finality, of Algorand significantly lowers the opportunity.

Finally, I don't know how easy it would be to add the inverted ed25519verify, aka ed25519verifyinv, function; and what it would mean in terms of opcode budget size.

Edit: I think it would be easy to implement ed25519skpkverify. LibSodium already offers this and it is hardly very different from how we generate accounts in Algorand. Question is the opcode consumption.

Conclusion

Thoughts, comments?

[HashMapsData2Value]

Here's an Ethereum implementation of the swap daemon, my thanks to Elizabeth/Noot for sharing it with me. It provides more context and highlights a potential issue I did not think of, that of Bob claiming and Alice refunding at the same time. If Bob's transaction gets stuck in the mempool, visible to Alice for a brief period before her refund goes through, she could construct _pkS and grab the XMR just before her refund also goes through, netting her the Algo as well. Thus by the time Bob gets access to _pkS it has already been emptied.

I have amended the proposal above to add the Ready. Also, both Bob and Alice should have sufficient safety margins to each time stamp (t_0, t_1) to avoid transactions getting stuck in the mempool and crossing over to the next chunk of time.

[HashMapsData2Value]

https://forum.algorand.org/t/question-regarding-ed25519verify-and-if-its-possible-to-invert-it/6637/4

After doing some digging seems like you can derive the pk from the sk anyway and LibSodium, which go-algorand uses under the hood, offers the following function:

• https://libsodium.gitbook.io/doc/public-key_cryptography/public-key_signatures#extracting-the-seed-and-the-public-key-from-the-secret-key
• https://github.com/jedisct1/libsodium/blob/6d566070b48efd2fa099bbe9822914455150aba9/src/libsodium/crypto_sign/ed25519/sign_ed25519.c#L53

So implementing an opcode that verifies that a particular secret key corresponds to a particular public key would be easy.

But maybe there is a better way to implement this adaptor signature stuff?

Edit: Good news: I confirmed with Noot that they actually used to verify the ed25519 directly. Doing this on Ethereum turned out to be too gas intensive so they switched to the dleq/zkp solution.

[HashMapsData2Value]

https://github.com/HashMapsData2Value/gjallarbru/blob/main/contracts/algo-ed25519/contract.py

(Obv the new opcode isn't there. Instead of doing Txn.note() == Alice/Bob partial public key, the Txn.note() would contain the private key which would then be used to generate a public key which is compared to the one loaded in at app creation.)

[kayabaNerve]

Any new opcode is unnecessary, even for the above mentioned protocol which does have on chain verification of a sk -> pk relation, as ed25519verify can be abused as a scalarmul verifier so long as it's possible to verify a signature has a R value of the identity point. See my comment on the linked issue for that.

On chain verification of a sk -> pk relation itself is unnecessary though as adaptor signatures would naturally leak the private keys. This design should be limited to a proof of concept and that alone. The referenced Ethereum implementation explicitly moved to adaptor signatures, and this work which is ed25519 native should follow that from the start as it has a lower bar to accomplish, especially when it's proposed alternative is hard forking Algorand. It'd also be more flexible given its ability to not change on chain smart contracts, yet be able to add support for BTC/ETH (secp256k1), as said support would be purely off chain.