Grin-Bitcoin Adaptor Signature Atomic Swap update thread

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

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

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

My concern isn’t over any particular feature of Grin, Bitcoin, or any other blockchain. Rather, it is about the ability of an attacker to deny service to a participant once they see the Revoke transaction posted. Maybe this is a small concern, such as an attack with the ability to fully shutdown a person’s internet acces, or otherwise prevent them from posting the Refund #2 transaction. Maybe this works by flooding the mempool, maybe its shutting off the power grid, maybe its RCE on Alice’s machine that prevents broadcast.

There are numerous scenarios where an attack could DoS a participant between the Revoke and Timeout transaction.

I hadn’t considered that scenario. Need to think about the tradeoffs more, and possible solutions. With relative timelocks, Alice would seemingly be at a total loss by waiting for Bob to post Timeout, and trying to also post Refund #2. The Timeout would be seen first by miners, and if Alice posts Refund #2 she reveals her nonce. Refund #2 will be seen as invalid (no Grin back to Alice), Bob will recover her nonce, and they will race to recover the Bitcoin transaction.

With absolute timelocks, the situation seems similar, but the race between Refund #2 and Timeout is closer. The consensus rules would allow whichever tx is seen first, as long as the timelock has passed.

Maybe I’m misunderstanding something still?

4 Likes

Update 2021/05/21-06/04

There has been more discussion over the atomic swap RFC, and revealed the need for modifications to my implementation.

I’ve spent time responding to discussion over the RFC, and working on implementing multiparty outputs.

Multiparty outputs are discussed in the Grin documentation, and are needed for some transactions in the Succinct Atomic Swap protocol. Originally, I thought the multisignature kernels were sufficient, they are not. Multiparty outputs are similar to multisignatures in other blockchains, allowing shared control over an output.

Multiparty outputs in Grin require an aggregate commitment over the output, using nonces from both participants. Multiparty rangeproofs are also needed, which thankfully are implemented at the cryptographic level (thanks @garyyu, @yeastplume, @yoss22!)

I’ve added functions to expose the cryptographic primitives to grin, and working on integrating them into transaction building in grin-wallet.

I’m still working on building the multiparty bulletproofs in grin-wallet, and need to add the Refund #2 and Timeout transactions for Succinct Atomic Swaps. Also, need to verify the correct outputs are spent in the Grin Success, Grin Revoke, Grin Refund, and Grin Timeout transactions. Each of those transactions spend from a shared output, so multiparty outputs need to be integrated into the atomic swap transaction flow.

A number of changes are needed for the slate format, so I’ll also be updating the RFC with a specification for Version5 slates (slates are currently Version4).

Thanks for reading

6 Likes

OK, I understand now what you mean, thanks for clarifying. Aside from the mempool fee issues we discussed, I don’t think there’s much that can be done. Perhaps communicating over Tor will make targeted attacks less likely? This problem seems inherent to any protocol that requires a participant to interact with the p2p network within a certain period of time.

“Seen first” is a propagation rule, not a consensus rule. It’s generally unsafe to make security assumptions based on propagation rules. If Alice talks to miners directly, and offers them a fee to mine her tx instead of Bob’s, then she gains the upper hand. Her nonce/secret won’t be revealed to Bob until her Grin tx is confirmed, and if she’s lucky enough to get a confirmation on the BTC tx before her Grin tx confirms, she will in fact walk away with all the coins.

I’m not sure if the non-interactive aggregation properties of Grin may make out-of-band transaction replacement harder (I suspect Alice can help miners to undo the aggregation of Bob’s tx, seeing as she knows the tx?), but ultimately this still doesn’t guarantee the attack won’t occur.

1 Like

That’s not necessarily the case. As soon as Alice’s tx is in a node’s mempool controlled by Bob, he has access to the final signature, and can retrieve Alice’s secret. Same in reverse for txes with Bob’s secret.

I fully agree about not relying on propagation rules for security, and it’s partially why I’m having trouble seeing the advantages of the Revoke flow, over just using the Success and Refund #1 txes (at least, when using absolute timelocks).

The Revoke flow makes a lot of sense when you have relative timelocks, because the order of accepted txes can be enforced by consensus. But I don’t see the advantage with absolute timelocks, since just using Success and Refund #1 seems to be sufficient (and simpler) to achieve a secure swap.

Is there an added benefit to using the Revoke flow with absolute timelocks?

1 Like

Update 2021/06/04-11

Over the last week, I have been working on changes for V5 slates. I moved the changes for atomic swap slate types into V5, along with multisig stuff. Also, added mutlisig transaction flow enum types, and slate types.

The next steps are to build multiparty outputs (multisig). Similar to atomic swap transactions, multisig transactions will require four communication rounds. This fits nicely, and should work well with the atomic swap transactions that require creating a multiparty output (Revoke).

The implementation should be pretty straightforward, so I hope to finish by early-to-mid next week. After multiparty outputs are done, just need to modify atomic swap Success and Refund #1 transactions to select and verify the multiparty output created by the Fund transaction.

To complete the SAS implementation, the Revoke, Refund #2, and Timeout transactions also need to be implemented.

I’ll also be updating the RFC with more details about slate changes, and how each transaction is built (e.g. one slate per transaction vs. one slate for the Revoke + Refund #2 + Timeout txes).

Thanks for reading

8 Likes

Note that I specifically said “if Alice talks to miners directly”, meaning Alice circumvents the p2p network (and thus everyone’s mempool) and asks miners to mine her transaction directly. Perhaps my post will make more sense now, with that clarification in mind.

Well, I’ve been arguing that this isn’t secure. I’m not sure what more I can say to make the need for Revoke more clear. You need to wait for Revoke to confirm, and only then should you send Refund (regardless of whether you use abs. or rel. timelocks), otherwise it can cause race conditions where both secrets can get revealed. The example in my previous post (which is hopefully more clear now) even shows how you can gain a clear advantage in the race and potentially steal all coins by bypassing the mempool and talking to miners directly.

5 Likes

Beyond that, Refund #1 cannot be a single Grin tx since it has two separate spending conditions.

2 Likes

Yes, you bring up a good point. Refund #1 from the original diagram is actually purely there to allow for more efficient recovery, reducing the failure recovery case from 2 transactions to 1 in the case where your counterparty becomes unresponsive before Success is ever signed. In all cases it is entirely safe to simply drop Refund #1 from the spec (since Refund #2 always works), and this clearly seems appropriate for the specific case of Grin. Note that it’s also safe to broadcast Revoke and Refund #2 together IF Success was never signed, since then there’s no risk of race conditions.

4 Likes

So, is the atomic swap described in grin docs also insecure? If so, why?

1 Like

That one looks secure to me, but is much less attractive in that it requires two bitcoin transactions, and requires the bitcoin holder to start. Also, the hashlock reveals the nature of the transaction.

1 Like

For the hashlock, I would replace with a normal transaction signature under the aggregate secrets used in the atomic swap, so it would look like a normal transaction.

Could also wrap the Bitcoin transaction in a timelock, but not strictly needed. The Bitcoin tx timelock could even have an adaptor signature to reveal Bob’s secret for Alice to retrieve the locked Grin (either ECDSA or Schnorr adaptor signature, when taproot activates later this year).

Why would there need to be two Bitcoin transactions?

Why would the Bitcoin user have to start?

With using a signature under the aggregate swap secrets, the Grin side would need to go first (or Alice and Bob would need to exchange swap public keys out-of-band).

On a closer reading, it is not a hashlock, but a regular secret public key x*G. It is still abnormal in having a alternate timelocked spending condition.

I don’t know what you mean by wrapping here.

Because that’s how atomic swaps worked before S.A.S. Bob locks up bitcoin that either gets refunded or spent by Alice learning a secret.
S.A.S.manages to avoid the refund by first setting up a more complicated revoke mechanism on the other side.

That’s how that particular protocol is setup. You could make a variant where the Grin user starts though.

1 Like

Adding a timelock spending condition to the Bitcoin transaction (pseudo-script):

IF SIGNATURE(aliceSecret + bobSecret)
    SPEND_TO_ALICE
ELSE IF BLOCK_HEIGHT > SOME_HEIGHT AND SIGNATURE(bobPrivateKey)
    SPEND_TO_BOB

Couldn’t that be avoided with a single transaction similar to what is described above? Then there would just be the one funding Bitcoin transaction, and one locked transaction (which is the same situation as S.A.S.). With taproot, the alternate spending conditions could be hidden, only revealing the actual spend path used. So, it would look like any other taproot spend.

Update 2021/06/11-18

Over the last week, I have been working on multisig transaction building in grin-wallet. Also, made some minor tweaks to output building in grin.

Still working on the final pieces of multisig transaction building. All the backend API implementations are basically finished, and I’m going to work on adding the frontend APIs, RPCs, and wallet commands next.

Will also be adding an end-to-end test based on cmd_line_basic, to ensure everything works properly.

After all the pieces are in place for multisig transactions, I will modify the atomic swap transaction building to select and verify the multisig output. Then, it should be possible to test a variation of the atomic swaps described in the Grin documentation.

Once I have everything worked out, I’ll make updates to the RFC. There are a number of changes to slate formatting, the entire mutlisig output building, and some more details about the atomic swap that I need to add. Just want to get all the pieces in place before adding the RFC updates.

Thanks for reading

17 Likes

Update 2021/06/18-25

This week I added the remaining pieces for hooking up multisig output transactions and atomic swap transactions.

I’m currently debugging the end-to-end test, and it looks like there is a problem getting the multisig output transaction added to the PMMR. Not sure if it’s a problem with the test setup, or I’m doing something wrong in the impl.

Will keep debugging, hopefully will be able to figure it out. Will post update as soon as I solve the problem. Might be that I need to fix how the mutlisig output is spent, TBD.

I think all the pieces are in place (outside the above bug), so I’ll start writing up the necessary changes to the RFC.

Thanks for reading

14 Likes

Update 2021/06/25-07/09

Over the last two weeks, I have been fixing some broken tests. It took a while due to not being able to run doctests in a debugger (super annoying). All the tests appear to work now!

Also, spent some time cleaning up the commits in grin-wallet/#618 (main atomic swap PR). Everything should be ready for review code-wise, with maybe some straggling code cleanup issues. Functionally, everything is there.

I am still working on writing up the RFC changes for the atomic swap impl. I am not going to implement SAS, and leave that as work for someone else. I’ll be writing a separate RFC for an atomic swap scheme that more closely follows the description in Grin docs, since that is what I’ve implemented.

Thank you for all the support I’ve received from the Grin community during these past few months.

I’ll still be around, and will continue contributing to Grin. I won’t be requesting further funding for atomic swaps, but will finish the remaining work (mostly RFC stuff).

Thanks for reading

23 Likes

Thanks for all your time and effort!

4 Likes