Grin-Bitcoin Adaptor Signature Atomic Swap update thread

Development and Technical Discussion
1

Hi everyone, I’m starting this thread for weekly progress updates on atomic swaps using adaptor signatures.

Over the past week, I’ve made decent progress implementing the cryptographic primitives needed for ECDSA adaptor signatures.

Not sure if the changes would be welcome upstream for rust-secp256k1, so will open discussion through an issue/PR. Depending on how the discussion goes, I may end up re-implementing ECDSA adaptor signatures as a libsecp256k1 module. Then expose interfaces in rust-secp256k1. TBD

Some problems came up when trying to implement Positive ECDSA pre-signatures. Because pre-signatures are not verified normally, I’m having a problem with the dual Schnorr proofs when s is negated (to ensure |s| <= (q-1) / 2).

The concrete NIZK proof isn’t specified in the paper, and I designed the dual Schnorr proof based on the scheme specified in https://tools.ietf.org/html/rfc8235. It works when s is not negated, but fails when s is. Still working on how to modify the proof to make it work, and still retain all its security properties.

When verifying the pre-signature in a way closer to how the original ECDSA schemes are verified:

r == f({H(m) * s^-1}*g + {r * s^-1}*X)
when r = k*g during signing

the signature verifies even when s is negated (as expected). So, the problem is definitely in the Schnorr proof I’m working on.

Will keep working on the problem, since it is fundamental for the security of the adaptor signature scheme.

After I solve the issue with the dual Schnorr proofs, I’ll continue with implementing the witness extraction and adaption algorithms.

When those are finished most of the cryptographic primitives will be finished™ (still need more testing and refactoring). Then I can start working on integrating the signatures into mimblewimble/grin-wallet and a PoC wallet using rust-bitcoin/rust-wallet.

Please feel free to ask questions, and give feedback in this thread.

Thanks for reading :grinning_face_with_smiling_eyes:

22 Likes
2

Awesome!! You are going to do great things for grin, you could cut-through the energy with a knife :slight_smile:

2 Likes
3

Think I found a partial solution to the pre-signature verification issue.

During verification of the Schnorr proof, now check the proof with both k*G and -k*G. So, when s is conditionally negated, the negation of the reconstructed K' passes verification, otherwise the normal reconstructed K' passes verification.

I think this may be secure, but allowing for two variations of the public key (that are attacker controlled), still feels like it will cause problems.

No knowledge of the private key is leaked, and the SUF-CMA property holds (no changes to the message or signature pass verification).

A question to the more experienced cryptographers in the community: does this solution open any known attack vectors? If so, what are they?

If anyone can see a problem with the scheme, please let me know. I’ll keep thinking about it, as I would like to have a clean solution.

Here is the relevant code snippet: https://github.com/GeneFerneau/adaptor/blob/main/src/schnorr.rs#L133-L148

8 Likes
4

Update 2021/04/02-09

Figured out the issue with negating s in the pre-signing phase, basically was doing the negation in the wrong place. Instead, s needs to be conditionally negated when adapting (“decrypting” in Elements terminology) the adaptor signature into a normal ECDSA signature. Then, during extraction (“recovery” in Elements terminology) test for whether the recovered private key’s inverse is negative. If it is negative, that means s was negated adapting to an ECDSA signature. So, you negate the private key to recover the correct key. That took a couple days to figure out…

I also changed the modified Schnorr identification proofs to Chaum-Pedersen proofs, since Chaum-Pedersen is the correct primitive to use. Didn’t know before Alex Xiong answered a related question on the Crypto StackExchange.

Incidentally, Elements Project developers were simultaneously implementing ECDSA adaptor signatures (I was unaware until recently). Their implementation follows a different paper One-Time Verifiably Encrypted Signatures A.K.A. Adaptor Signatures by LL Fournier.

The implementation doesn’t include a zero-knowledge proof that the “encryption public key” has a known private key (what Fischlin proofs are used for in my impl), but it appears their impl is the “official” ECDSA adaptor signature. I raised the question of adding Fischlin proofs to their scheme, so maybe that will be addressed.

The security risk is that a prover could provide a public key with no known private key, and the pre-signature verification would still pass. The verifier wouldn’t find out until the adapt/extract (decrypt/recover) phase. It also isn’t secure under the Universal Composability framework.

Either way, I will likely be adopting their impl going forward, since it includes standardization from BIP-0340. Will also raise an issue to see if anyone there is working on 2P-ECDSA, so that I don’t waste any more time duplicating work.

The next steps are to create the on-chain transactions for the atomic swaps on the Grin and Bitcoin chains. This will involve exposing libsecp256k1-zkp interfaces for ECDSA and Schnorr adaptor signatures to Rust (maybe this is already done, idk). With adaptor signatures exposed, can begin implementing the timelocked multisignatures using ECDSA-Schnorr and Schnorr-ECDSA adaptor multisignatures.

6 Likes
5

Update 2021/04/09-16

After discussion with @LLFourn and @jonasnick on GitHub, I understand the fundamental difference in approach between their ECDSA adaptor signature impl and mine. Their construction is secure, as long as it is not used to compose another scheme that relies on the Diffie-Hellman problem. If there is technical consensus to switch to Elements Project’s ECDSA adaptor signature impl, I’ll do so.

I have chosen to re-implement the generalized channel style ECDSA adaptor scheme in libsecp256k1-zkp, and am continuing with a Schnorr adaptor signature impl in the aggsig module. There is still some code cleanup in the ECDSA work, notably the extract algorithm allows for both the pre-signature s and its negation to extract the witness secret key.

Allowing the pre-signature s and -s to extract y decreases the search space by half for a brute-force attacker, which AFAIU takes one bit off the security of the scheme.

It doesn’t seem to seriously harm security, since an attacker could try s and -s anyway to achieve the same effect. While rejecting would drastically harm usability for honest users.

This is currently the biggest flaw I see in my impl. Only one version of the adapted signature s is allowed, and the rest of the scheme is SUF-CMA secure.

One possible solution is to simply reject high adapted s values in the adapt algorithm, instead of conditionally negating them. It will take more work to find a solution that doesn’t drastically hurt usablility, and remains SUF-CMA secure.

Edit: after reviewing the aggsig module, all the code is there for Schnorr adaptor signatures (many thanks @yeastplume @jaspervdm @garyyu!).

For the Schnorr adaptor signature impl, will use the aggsig module in secp256k1-zkp, and what’s outlined in the atomic swap section of the Grin docs. I may incorporate some of the BIP-340 stuff for nonce generation to create a “synthetic nonce” (the e value), since it hardens the scheme in low-entropy environments (like hardware wallets).

Synthetic nonce generation can be done in grin-wallet, other impls, or could use the HMAC-SHA256 based code in aggsig.

Now, can start integration work by adding a module to grin-wallet. Because I am working somewhat backwards from how I started (main impl in C, with Rust bindings), the integration into C/C++-based wallets should be even more straight-forward. However, integration into C/C++-based wallets will come after grin-wallet and rust-bitcoin/rust-wallet integration.

The main integration work of creating the multi-sig Bitcoin transaction should also be pretty straight-forward. Basically, the hash lock is replaced by a signature from the adaptor public key. The Grin side should be even easier, with maybe some additional slatepack types to support communication rounds. I’m optimistic for finishing the integration work next week to get to the point of making testnet transactions (it may end up taking longer).

Thanks for reading

12 Likes
6

Update 2021/04/16-23

This past week, I’ve been working on integrating atomic swaps into grin-wallet and grin.

My work is in these branches:

So far, the transaction flow for the main atomic swap transaction is done. Next, I need to add all the wiring to hook it up to the CLI app.

Also, need to build the multi-party timelocked transactions. I read the Succinct Atomic Swap (SAS) protocol after reviewing the NRD RFC. Wish I had come across the RFC and SAS sooner, since now it looks like I won’t need to use ECDSA adaptor signatures.

Basically, all the transactions in the SAS paper that are done on Bitcoin can be done on Grin using height_lock and NRD kernel transactions. Some of the transactions revealing adaptor secrets and NRD kernels will require two kernels.

The Bitcoin transaction can be a 2-of-2 OP_CHECKMULTISIG transaction using signatures under Ya (Grin adaptor public key) and Yb (Bitcoin adaptor public key).

I’ll implement the 3 transaction version of SAS, at least to start. This won’t require any watchtowers. After getting the 3 transaction version complete, I may work on the 2 transaction version. However, the 2 transaction version requires watchtowers/online user during the swap, and maintaining state of the adaptor signatures + secrets.

Thanks for reading

11 Likes
7

I agree that the 3 tx version is a lot more practical. It also doesn’t need relative timelocks, which is good in that NRD kernels are not activated on mainnet.

You mean the 2 tx version?! I would not bother with that one; I consider the online/watchtower requirement too onerous for only a 1 tx savings. It’s a different story for payment channels, where the requirement appears unavoidable.

3 Likes
8

Yeah :man_facepalming:, fixed in the edit.

9

Update 2021/04/23-30

Over the last week, I have been working more on adding an atomic swap transaction flow into grin-wallet.

You can see my work here:

Currently, I’m debugging a problem with the final kernel sums adding up correctly. The test in libwallet works, but the larger integration test of the owner/foreign APIs is failing on final transaction validation.

Update: fixed the error! I wasn’t reconstructing the transaction correctly in the third phase of the atomic swap. The code is currently messy, but works. I’m going to clean it up by compacting the slate in the first phase, and reconstructing properly in the third phase.

Working to clean up the code, and then moving onto testing/debugging the refund transaction flow. After that, can do the last bit of adding CLI and RPC commands for atomic swaps. Once that work is done, can try out doing an atomic swap on testnet.

Thanks for reading

16 Likes
10

Update 2021/04/30-05/14

Over the last two weeks, I have spent time finishing all the API and RPC endpoints.

I also refactored the init_atomic_swap and receive_atomic_tx endpoints to internally derive atomic nonce keys using an atomic ID.

The identifier is constructed with the prefix 0x04 0x6d 0x77 0x61 0x74 0x6f 0x6d 0x69 0x63 (hex encoding of the bytes for depth of four then “mwatomic”. The derive path of a 32-bit unsigned integer is appended, with ability to extend to a 64-bit unsigned integer. Currently, this means each masked keychain can derive over four billion unique atomic nonce keys.

I added a scalable cuckoo filter (improvement on Bloom filters) to ensure users do not reuse atomic nonces. The filter is save to the local wallet database, and cannot be reconstructed if the wallet is deleted.

The filter uses an added dependency (scalable_cuckoo_filter), for faster development. It’s a fairly small implementation, and I can implement if the dependency is unwanted. If I redo the implementation, the deletion algorithms can also be removed, since we don’t need it for atomic swaps.

I found a paper on vacuum filters, which also seem like a good replacement. If anyone has other recommendations for a better algorithm, please let me know.

If a user performs atomic swaps, then deletes and recovers a wallet, it is recommended to use a
new keychain mask for performing future atomic swaps. I will add a warning to the CLI + RPC commands describing the danger of reusing atomic nonces. Basically, reuse can result in loss of funds, because the other party will already have the revealed nonce, if the reuse is with the same participant.

Currently working on adding CLI commands (send_atomic, receive_atomic), and fixing the RPC doctests.

For some reason, all but two of the RPC doctests are failing. This seems unrelated to my work. Priority is on implementing the remaining CLI commands (countersign_atomic, finalize_atomic). send_atomic works for both the refund and main transaction, and I will add a message to the refund transaction flow finalize_atomic about not posting the transaction unless a refund is desired. Will be adding tests for all the commands, just like I have for everything else so far.

Next, I will continue work on the CLI commands, add more documentation, do a full local test, and then a testnet atomic swap.

After the implementation + test swap, I’ll start working on an RFC of the 4-round (8 in total, main + refund) atomic swap.

I’ve been thinking of a way to reduce to three rounds, but it doesn’t seem possible.

The party revealing the atomic nonce must sign the transaction twice (once for the adaptor signature, once for the full signature revealing the atomic nonce). The party retrieving the atomic nonce must interact twice, once before the adaptor signature is created, once after the adaptor signature has been created. If anyone has ideas about how to reduce the number of rounds, please post in this thread, or on the RFC (when posted).

Thanks for reading.

13 Likes
11

Is there a high level overview of your succinct atomic swap protocol yet that you can share, that shows the role of this “atomic nonce” ?

Would it be reasonable to extend it to 64 bits and not bother with any filter since the odds of reuse would be too small?

1 Like
12

I’ll be working on the RFC this week, hopefully have something ready to post by Friday (maybe sooner).

So moving to 64 bits would just take a little reworking of how the main keypath is derived, but nothing major.

The main reason for the filter isn’t the entropy provided by the bit-length, though. The atomic ID is user controllable, meaning an adversarial partner could maliciously choose an atomic ID they know the other party has used in the past (maybe they swapped with them before). The atomic ID also doesn’t need to be generated randomly, using a counter is perfectly secure.

Without automatic defenses (the filter), it would be pretty trivial to trick someone into using the same nonce multiple times. Reusing the same nonce means the other party already knows the nonce, so could recover the funds without completing the new swap.

2 Likes
13

Update 2021/05/14-21

This last week has been a little less active.

Opened PRs for Succinct Atomic Swaps in:

Still need to work out some stray errors in the doctests for grin-wallet, but the main impl is functional.

Will be working on fixing those tests, and revisions suggested by reviewers of the PRs. So far, @tromp and @phyro have provided constructive feedback (thank you!)

The main change will likely be dropping the atomic IDs and associated filter in order to generate atomic nonces closer to generating blinding factors and signature nonces. I think the domain separation (adding the static prefix to the identifier) is still a good idea. It helps when a user restores a wallet, and forgets which atomic nonces they have already revealed.

A user would have no indication of atomic nonce reuse, and the prefix at least offers some mitigation (i.e. a user is unlikely to use keys with the atomic swap prefix for normal transactions). In the case of a wallet restore, they could recover UTXOs from the recovered wallet into a fresh wallet, before performing any more atomic swaps.

The atomic ID is also used to coordinate atomic swaps between the refund and main transaction. So, I will also need to figure out how to do the coordination with purely locally derived atomic nonces.

As always, thanks for reading.

13 Likes
14

Nice work, good to see SAS being implemented :+1:

Assuming I understood your implementation correctly, this can be simplified further to a single key (also better for anonymity). You can just use MuSig on Ya and Yb (MuSig here prevents key negation, or alternatively you can just sign with both keys). This may be non-obvious, but this works for ECDSA because you never actually have to perform a multisig spend – either Alice or Bob will end up with the full Ya + Yb key and can then make a normal ECDSA signature with it.

10 Likes
15

That is so cool! I was thinking about the possibility of 2P-ECDSA or using MuSig when/if Schnorr is activated on Bitcoin, but your solution is so much cleaner. I’ll definitely use that, and make note in the RFC to just add Ya + Yb as the signing public key on the other chain.

Thanks so much :heart:

8 Likes
16

@RubenSomsen I have been discussing a modification to SAS with @tromp, to reveal Bob’s secret in the Timeout transaction.

My suggestion: add an adaptor signature to Timeout, so that Bob reveals his secret when recovering the coin from the transaction in the Revoke -> Timeout flow. This allows Alice to recover the Bitcoin (in the Grin-Bitcoin swap), and effectively turns Revoke -> Timeout into a longer version of the Success flow. It also prevents an attack vector where Alice posts a Revoke transaction, and Bob performs a DoS against Alice. Bob could then recover the Grin, and the Bitcoin would be locked forever; assuming Alice nor Bob never reveals their nonce, and no timeout exists on the Bitcoin transaction.

One problem that @tromp sees with my suggestion is that Alice could intercept Bob’s Timeout transaction, recover the Bitcoin, and DoS Bob from recovering the Grin. This works because Alice could recover Bob’s nonce from the full signature in the Timeout, and the adaptor signature I’m suggesting.

I think that the DoS @tromp describes (please correct me if I’m not representing things correctly) is valid, but is also present for any adaptor signature reveal. So, adding the adaptor signature to Timeout doesn’t present any new assumptions over the other reveals present in the protocol (Success, Refund).

What are your thoughts on the modification? @tromp suggested that such a change needs careful scrutiny, and I fully agree. Looking forward to your response.

1 Like
17

Hi @gene, thanks for the clear description.

It sounds like I’m not familiar enough with the DoS issues in Grin to fully comprehend this problem. Is it the case that in Grin one can indefinitely delay transactions from confirming? That does sound like a problem. In Bitcoin Alice can use CPFP to guarantee that both the Revoke tx and Refund tx #2 to go through in a timely manner, even if the initial fees are too low.

As you may have suspected, this is deliberately not in the design. If you were to reveal Bob’s nonce in the timeout tx, the problem you run into is that Alice can try to fight you for the money by simultaneously sending out Refund tx #2. Now both nonces are revealed, and chaos ensues (one possible outcome is they both try to outbid each other, and all the money from both outputs goes to miners).

You could argue that this is a negative outcome for both parties, so it will be avoided, but this still seems unsatisfactory. Even without malice, this situation could occur by mistake, and then both parties will be punished for the mistake of one. One can also imagine scenarios where someone deliberately ruins swaps like this in order to e.g. cause reputational damage to the swap protocol.

Note by the way that the protocol is staged with multiple transactions to avoid this exact problem. If you did decide to accept the associated risks, the protocol can actually be simplified. You would only need the success tx (T0, revealing Bob’s nonce), one refund tx (T1, revealing Alice’s nonce) and the timeout tx (T2, optionally revealing Bob’s nonce), all spending directly from the on-chain tx.

I hope this helps.

1 Like
18

Not easily. Once broadcast, and present in mempools, a tx is bound to be included in a subsequent block. The attacker would have to fill up the mempool with days worth of txs to prevent new ones from fitting.

Once Grin blocks start filling up, we can revisit the mempool logic to
achieve the same functionality in Grin. One suggestion I made is a RBF where the replacement has a higher fee_shift (essentially a tx priority level).

In fact the Grin protocol already kinda behaves like that. Since Grin has no relative timelocks yet, we replaced the ones on Refund #1 and Timeout by absolute timelocks. Now when Alice wants to do Refund #1, she just waits for its timelock and then performs the aggregation of Revoke and Refund #1. Similarly, Bob can perform the aggregation of Revoke and Timeout when the time is right. So we might as well remove the separate Revoke.

So we end up with something like

+----------+             +-------------+  1 day        +----------+
| 87k Grin |  --Fund-->  | 87k Grin    |  --Refund-->  | 87k Grin |
| Alice    |             | Alice + Bob |  reveals      | Alice    |
+----------+             +-------------+  secretA      +----------+

                              |    |
                              |    +--Timeout-------+
                              |      2 days         v
                              |
                              |                +----------+
                              +--Success---->  | 87k Grin |
                               reveals         | Bob      |
                               secretB         +----------+



+-------+         +-------------------+
| 1 BTC |  ---->  | 1 BTC             |
| Bob   |         | secretA + secretB |
+-------+         +-------------------+
4 Likes
19

Hi @tromp, thanks for explaining the concern regarding delaying transactions. Some kind of fee-bumping mechanism does seem like the only solution to that. Note that RBF might not be sufficient in a multisig setting where participants are adversaries (i.e. Alice and Bob might not agree on bumping the fee).

So then Alice runs the risk of Bob simultaneously sending Succes and both secrets becoming known. Alice can avoid this by sending Revoke first, instead of aggregating. Again, you could certainly choose to simply accept this risk, but to me it seems wise to prevent this from occurring.

Nice graphic. That looks correct to me.

2 Likes
20

Ah, yes; I overlooked that the purpose of the separate revoke is to take away Bob’s option to execute the Success transaction before Alice reveals her secret. I agree we shouldn’t take the risk.

2 Likes