Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Single Transaction Multisig Protocol for Bisq using UTXO swap #456

Open
ChrisSon15 opened this issue Jul 11, 2024 · 13 comments
Open

Single Transaction Multisig Protocol for Bisq using UTXO swap #456

ChrisSon15 opened this issue Jul 11, 2024 · 13 comments
Assignees
Labels
an:idea https://github.com/bisq-network/proposals/issues/182#issuecomment-596599174 re:protocol

Comments

@ChrisSon15
Copy link

ChrisSon15 commented Jul 11, 2024

This is a Bisq Network proposal. Please familiarize yourself with the submission and review process.

(There are some updates, if you want to jump into the latest you can click here)

Single Transaction Protocol for Bisq

Prelimery

Goal

Currently Bisq uses 4 transaction to make a normal trade. This causes a lot of fees, which in higher fee environment will get increasingly a problem. Also these 4 transactions reveal the bitcoin script used for the multisig. This could be a limitation for privacy. The goal of this protocol is to reduce fees and have more privacy using Taproot.

Work In Progress

This writing is just outlining the basic idea. Its not meant to be complete nor does it touch on implementation issues. Its sole purpose is to outline, that a single transaction protocol is feasible and which advantages / disadvantages it has. So this is only for collecting feedback, if this is a direction you want to go into further.

Paying fees

To keep this article short, I am omitting the problem of paying fees, as it can be added to the system quite easily afterwards and doesn't have much of an impact.
Actually I see different ways to collect fees, which may be detailed in another post.

  1. Lightning payment of Alice and Bob, they mutually check if the payment has been done.
    The invoice preimage given to bob from the LN receiver must be a signature for the transaction to be made.
  2. paying fees as part of the SingleTx. That's simple.
  3. Fee Payment for the Listing using LN.

Trade protocol, happy path

Alice and Bob deposit their amounts into 2of2 multisig.
Alice and Bob create random private keys, which are in no way connected to other private keys.
Note: In HD Wallets, which is the current standard, private keys are being derived from each other using a chaincode. So the sequence of private keys is deterministic.

For the alternative paths of this protocol, Alice and Bob need to prepare some pre-signed transactions. To do the signing process Alice and Bob use MuSig2 as Protocol.

A Schnorr based 2of2 multisignature, makes use of the additivity of the keys and their signatures. Instead of a script, we have a public key, which is the sum of Alice and Bobs pub keys. The combined key locks the taproot transaction output in a key path.

P' = PAlice + PBob

The resulting P' is calculated in the MuSig2 Protocol for signing the transaction for the alternate transactions.

The Linearity of the Elliptic Curve Operations ensures, that the corresponding secret key d' of P' can be computed by the secret keys of Alice dA and Bob dB.

d' * G = (dA + dB) * G = dA * G + dB * G = PA + PB = P'

remember

P = d * G

where
P is a Public key,
d is a secrect key,
G is the Generator point of the Elliptic Curve

this effectively means, that when Alice passes her private key to Bob, he can calculate the private key for P' and therefore has the private key for spending the multisig-output as he wants. So he has full control over the UTXO.

So the Single transaction of the Bisq trade will have all outputs secured by a pay to public key hash and the transfer of ownership will be conducted by passing the private key from one person to the other. Note that the SingleTx will have 2 outputs constructed like this, one output will be owned by the person which gets only the deposit back (the seller) and the other output will be owned by the buyer, which gets the trade amount and the deposit.

Once the transaction is confirmed on the blockchain, the out of bands payment can begin. This is usually the fiat payment. Once the fiat payment is received, the Seller of BTC (Alice) will confirm the payment.
Alice sends her secret key dA to Bob. As stated earlier, the secret key must be generated independent of other secret keys. Modern HD Wallets have a dependency of secret keys among them and revealing a secret key would reveal information about the other keys as well. This puts some burden on the wallet which can be used in this scenario. (Although random key generation is not a anything new to wallets, but the wallets needs to keep track of a randomly created secret key.)

Bob now has both secret keys and can compute d', therefore he has full control over the funds in the multisig transaction of the Bisq trade. Also, since he kept his secret key to himself, he knows that Alice can not control the funds of the multisig. This basically puts him into the situation, that he doesnt need to make a new transaction to send the funds out of the multisig. Bob can leave the funds in the multisig and spent the funds whenever and for whatever he wants, because he has the full private key to the funds and can sign any transaction with it.

diagram view of the Single Transaction, Deposit Tx

img_2

the alternative paths, Dispute Tx

However, sometimes one party is uncooperative or doesn't respond at all. For these cases we are preparing with pre-signed transactions. These transactions are called Dispute transaction. There is one transaction for Alice and one for Bob. They are very similar, but not the same.

Here is how the Dispute TX Alice would look like. It's called Dispute Tx Alice, because Alice can post it. Alice won't be able to post Dispute Tx Bob.
Input will be the output of the SingleTx from above, including the trade amount and both deposits.

Output 0:

  • amount: Seller deposit and trade amount.
  • Key spend: P' In case that Alice has given Bob the 2nd private key for P' already, but still posting this Dispute Tx Alice, then Bob is able to immediately transfer the output 0 to his wallet by using P' as key spend. Note this should not happen, as it has disadvantages for Alice.
  • Script spend (taproot leaf): The script starts with a timelock. With the timelock it is not possible to spent before a certain time t1 has elapsed since the dispute transaction has been mined. This timelock is implemented by an OP_CSV <relative time> instruction in the script. Additionally, the outputs is protected by requiring the signature of the arbitrator(s).

Script spend in detail:

  1. OP_CSV <relative time t1>
  2. OP_DROP
  3. <Arbitrator(s) PubKey>
  4. OP_CHECKSIGVERIFY
  5. <Alice PubKey>
  6. OP_CHECKSIGVERIFY
  7. <Bob PubKey>
  8. OP_CHECKSIG

In Step 3, instead of having one arbitrators pub key, we could have a threshold multisig with t out of k signatures from arbitrators. This ensures, that the trade only goes to the DAO (to the burningmen) after arbitrators have looked at the case. the pub keys therefore need to be known to the traders (they should be embedded in the bisq-software)

if Bob and the arbitrator collude, worst case they can send the money to the DAO (to Burningmen), but that won't give them an advantage, the same thing could happen in the current Bisq system as well.

privacy

The happy path was constructed with privacy in mind. One taproot transaction with a script less multisig. The transaction has 2 inputs and 4 outputs, which is not very typical. However, it doesn't have a multisig-utxo, only normal key-spends. That still gives it a good privacy, as taproot transaction are very common nowadays. Here is an overview of the Output types used on the blockchain from the 90 days before 2024-06-01. To enhance the privacy further, it would probably be feasible to make 2 transaction instead of one. The 2 transaction would have 1 input and 2 outputs each, which would make them look like ordinary transactions with change. Another adaptor signature scheme would probably needed to implement this.
Moody2024-06-01

use of normal segwit v0 transactions

If privacy would not be an issue, then the transaction for the happy path could be constructed differently. In that case, it could be made with segwit v0 as well. Instead of the scriptless multisig we could have a script multisig. And instead of passing the private key to transfer the ownership of the scritless multisig, Bob could send a signature for his Public Key in the MultiSig. This Signature would need to have SIGHASH_NONE || SIGHASH_ALLCANPAY. With this sighash type the signature will only verify against the own input, no output and no other inputs will be part of the message to check. Practically is this like a blank check for the other side, it enables Alice to create any transaction, she just needs to sign her pub key in the multisig with her key. Alice must sign her pub key with SIGHASH_ALL. At least one Signature in a transaction needs to have SIGHASH_ALL, otherwise the transaction could be changed by anybody seeing the transaction in the mempool, before its mined.

deposit transactions

In the section 'Happy Path' I described only one part of the initial transaction, basically the exchange of private keys. However, the seller deposits the trade amount and a deposit, the buyer deposits only an deposit as escrow. After the deal, the buyer should have control over a deposit and the buyer shall have sole control over the funds and a deposit, assuming the deposit from both parties have the same amount. This means they need to exchange control for the respective utxos at the same time in an atomic way. If the seller sends the private key to the buyer, but the buyer stays inctive, then the seller will not get access to a deposit. The deposit for him cannot be moved by anyone, because he still has one of two keys, but he cant move it either.
How do Alice and Bob exchange their private keys for the deposit in an atomic way?

Before exchanging the private key for P' and Q', Alice and Bob need to sign a swap transaction for each other in a way atomic swap are handled to ensured that both swap transactions will happen or none of them. Alice swap transaction will send Bod's deposit to an address of her wallet. (At the end Alice will get Bob's deposit and Bob will get Alice deposit, they are of the same amount).

Alice and Bob don't get the same type of payout transaction. Alice gets a transaction signed from Bob in such a way, that if she posts the transaction to the mempool, Bob can see the signature which Alice needs to add. In an atomic swap scenario Bob can take this special constructed signature to sign his swap transaction.

This can be achieved using adaptor signature and works in details like this:

secret atomic UTXO swap without transaction

The transfer of ownership in this protocol is basically swapping control of 2 UTXOs, by exchanging private keys for 2 multisigs. In case of Taproot these multisigs are the Points P' and Q'.

Alice and Bob have initially 1 of the 2 private keys for each point P' and Q'. For swapping the UTXOs they need to give each other one of the 2 keys. If Alice gives Bob the private key for P' first, there is nothing that can stop Bob from aborting the protocol and leaving Alice behind without the private key from Bob for Q'. An atomic swap with adaptor signature can secure this handover. Therefore, we construct 2 transactions 'SwapTx Bob' and 'SwapTx Alice'. SwapTx Alice will have a single output with a pay to public key hash to Alice. Same for Bob.

adaptive schnorr signatures

Here is an outline of how the adaptive signature conceptually works. Note: this is just an overview, you may skip this section if you are familiar with adaptive schnorr signatures, because we won't need to implement it, the swap will be done by the library we will use.

Alice signature for Swap Tx Alice is

(1) sA = r' + hash(R' || PA || mA) * dA

where dA is private key of Alice

PA = dA * G # public key of Alice

R' = r' * G # a random nonce

mA # is the serialisation of SwapTx Alice using SIGHASH_ALL

We change this signature and introduce a random scalar t:

r' = rA + t; T = t * G: R' = RA + T

with that we rewrite (1) to

(2) sA = rA + t + hash( RA + T || PA || mA) * dA

this is a valid signature with Sig( sA, RA + T )
But Alice is not going to send this signature to Bob, instead she calculates the adaptor signature:

(3) s' = sA - t

(A) Alice sends the adaptor to Bob:

(s',RA,T)

(B) The important things is that Bob now can verify that the adaptor is actually a correct adaptor for signing the transaction mA and PA. He verifies it by multiplying (2) with G:

sA * G = RA + T + hash( RA + T || PA || mA) * PA

with (3) we get

<=> s' * G = RA + hash( RA + T || PA || mA ) * PA

Bob has all variables to verify that this equation is true.
Now Bob constructs an adaptive signature for his transaction mB and public key PB.

sB = rB + hash( RB + T || PB || mB) * dB

the variable's meanings are analogous to (1), just using index B for Bob.

(C) Bob sends the following adaptor to Alice:

( sB, RB, T )

technically he wouldn't need to send T, as Alice has that already.
Note: this adaptor is, again, not a valid signature. But Alice can make it a valid signature, because she knows t. The signature can only be used for the Parameters RB + T, PB and mB because the signature is commited to those values in the hash.

Alice can construct from that adaptor signature and knowing t:

(sB + t) * G = RB + T + hash(RB + T || PB || mB) * PB

(D) which is a valid signture for the transaction SwapTx Bob. The signature is

(4) Sig( sB+t, RB + T )

(E) Alice can broadcast Bob's transaction now. Since she is broadcasting to a public blockchain, Bob can see the Signature (4) on the blockchain once its mined and he learns t from (4) because he already knows sB. Everybody else will not detect, that there is a adaptive signature going on, because only Bob knows about sB.

(F) By learning t, Bob can now deduct from (3) and (1), multiplying with G:

(s' + t) * G = sA * G = RA + T + hash( RA + T || PA || mA) * PA = R' + hash( R' || PA || mA) * PA

which gives him the signature for Alice transaction (SwapTx Alice):

Sig( sA, R' )

(G) So Bob can broadcast the SwapTx Alice and get his Payout.

adaptive Signatures in multisigs using MuSig2

Above we saw the conceptual overview of adaptive signatures for singlesigs actually. For multisigs it turns out to be a little bit more complex. So I simplified the description here to show how the atomic swap works in general. The version of adaptive signature with MuSig2 can be found here.
In practice we won't need to programm all these steps, we have library support from libsecp256k1-zkp, for example. But finding suitable libraries is still to be done.

analysis of the alternative paths while swapping UTXOs

Above we saw the happy path, if everybody behaves as expected. Having those steps setup and explained, gives us now the possibility to analyse what can possibly go wrong.

  1. In (A) Alice sends her Adaptor signature to Bob (keeping the adaptor t private). If Alice doesn't do this step, then Bob can broadcast the Dispute Tx transaction.
  2. (B) Bob verifies the Adaptor, if it fails he broadcasts the Dispute Tx.
  3. (C) Bob sends his adaptive signature. if he fails to do so, Alice can broadcast the Dispute Tx.
  4. Alice constructs and verifies the signature (D). If that fails she broadcasts the Dispute Tx. Then she broadcasts Bob's SwapTx (E).
  5. Bob observes the blockchain, if he does find his SwapTx, he calculates the adapter t (F) and then he broadcasts Alice SwapTx (G)
  6. Alice (she can broadcast the Bob's SwapTx at any time) now sends her private key for P' to Bob. If she fails to, Bob can still broadcast the Dispute Tx.
  7. Bob is now in possession of both private keys for P' and can send the money secured by P' where ever he wants. If he sends his money to a different place before giving Alice his private key for Q', then Alice is not able to use the Dispute Tx any more, because one of the inputs of the Dispute Tx is already spent. But in that case she can use the SwapTx Bob to get her money. If Bob times out at this point, then she could use the Dispute Tx or the SwapTx Bob.
  8. At this point Bob, unfortunately, does not have an incentive to follow the protocol further. But he also doesn't have an incentive to cancel it. So I assume in most cases Bob will continue and send his private key for Q' to Alice.

I assume that the Swap Txs will never be used, because it doesn't give anyone an advantage. But they need to be there to secure the protocol.

Distribution Transactions

Both trades have the ability to post a dispute transaction. The dispute transactions have 2 inputs from the deposit transaction, so Alice and Bob must put their stake a risc when posting the dispute transaction. Note that the dispute transactions for Alice and Bob are slightly different. When Alice posts her Dispute transaction, Bob can claim his fund directly, if he has both keys already, since P' is the key spend of output 0. But Alice cannot get her out of the Dispute Tx. Whoever posts the Dispute Tx, that persons funds will go for sure to the DAO. That protects Bob from a malicious Alice trying to send his funds risc free for herself into arbitration. The script output of the Dispute Tx has actually a OP_CSV <t1> included. This actually gives Bob some time to actually send the funds away if he has the private key for P' before the next pre-signed transaction (the distribution transaction) is mined. For Alice (and Bob's) dispute transaction there are 2 distribution transactions, one for each output. So if Bob has transferred output 0 away using the second private key for P', then still Distribution Tx1 can be used to send the funds of Alice to the DAO.

Advantages

  • privacy. A lot of effort has been put into privacy for the users. Its is scriptless and only uses one transaction, see below.
  • The happy path is scriptless. That means as opposed to current Bisq, you cannot be sure that a certain transaction on the blockchain is using this protocol or not. As long as the trade doesn't go into arbitration. But that should be the exception.
  • Single transaction for happy path. This makes the trade also difficult to detect, since there is no pattern of intertwined transactions. Specifically, in the current Bisq system there is a time-based connection between the fiat payment and the pay-out transaction. Whereas in this protocol the transfer of ownership is done without transaction on the blockchain and therefore without trace.
  • lower fees. The current Bisq trade needs 4 transactions, so the fees of this protocol are much lower.

Disadvantages

  • After the trade is successfully executed, Alice and Bob have their funds locked in P' and Q' respectively. They can send that at any time with any transaction they construct. However, the Dispute Tx can still be posted. This is unfortunate and not very comforting that someone, after the fact, can still post a valid transaction. Misuse of the Dispute Tx after the trade is over is not wise because

    • the time delay enables the other side to secure the funds.
    • the arbitrator is the only person(s) which can transfer the money further and if not malicious he will contact the other trader first.
    • most important: The trader posting the Dispute Tx can be punished, since his funds will go to the DAO and misuse will be detected and punished accordingly.
  • To make normal use of the transferred funds, they should appear in the wallet. However, this may not work with each wallet. And may even need some custom wallet feature for handling this. Effectively that could mean that only the build in wallet may handle this protocol. This topic would need some further investigation.

Conclusion

This protocol would provide a lot of on-chain privacy for bisq trades. The usability would increase, since the transfer of ownership is instant and does not need a transaction to be mined. The fees would considerably decrease. This is at least for the happy path. This article here is just an outline and has to be detailed more, especially regarding implementation issues. So the purpose of this artile is to get feedback is this is something that you guys are interested in. If so, I would be glad to take it further. Bisq2 needs a multisig protocol and I think this ia a very cutting edge approach.

@Conza88
Copy link

Conza88 commented Jul 12, 2024

👀👍👏

@pazza83 pazza83 added an:idea https://github.com/bisq-network/proposals/issues/182#issuecomment-596599174 re:protocol labels Jul 12, 2024
@HenrikJannsen
Copy link

HenrikJannsen commented Jul 13, 2024

@ChrisSon15 Thanks a lot for the proposal and the great write-up! Very promising idea!

Here my comments:

Actually I see different ways to collect fees, which may be detailed in another post.

For Bisq 2 we have the intention to find an alternative revenue source but so far those ideas are not matured enough to discuss it publicly. But in general the intention is to remove the friction (and other negative implications) of the trade fee payment as part of the trade.

In Bisq 2 sellers building up reputation by burning BSQ are indirectly paying trade fees for the buyers (by factoring in their costs for reputation into the sell price).

Other ideas are to extend the existing proof of work DOS protection system of the P2P network (Bisq 2) to allow other options of access control to the network. As PoW causes a small cost to any network participant which makes abuse like DoS more difficult as costs increase with the attack intensity, we could add burned BSQ as an alternative option (Burning BSQ can be delegated to LN or other payments in a similar way as we use the distributed burningmen concept). As said those ideas are not worked out enough to discuss more in details... just wanted to share that you see we are exploring alternatives to trade fee payments.

Additionally, the outputs is protected by requiring the signature of the arbitrator(s).

Beside the advantage that the arbitrator protects additionally against malicious traders publishing the dispute transaction I don't see a reason from a security POV for adding a 3rd party. Having a 3rd party being in partial control of users funds cause some uncertain risks from legal/regulatory POV and we prefer to avoid that.

The transaction has 2 inputs and 4 outputs, ...

If we do not prepare the input utxo (as in the moment by the trade fee tx) there might be multiple inputs from each trader, which would be better for avoiding fingerprinting the tx. Also we could add random outputs to the traders if needed for improving privacy (at some small tx cost increase).

...Bob could send a signature for his Public Key in the MultiSig. This Signature would need to have SIGHASH_NONE || SIGHASH_ALLCANPAY.

I assume you refer to the deposit tx here. I fear don't understand that. This would allow Alice to spend all the outputs to herself, no?

Beside those smaller questions/comments it looks sound to me as far as I understand it.

Would be great to get feedback from @alvasw and @stejbac as they are much more familiar with the cryptography behind all that.

I have not followed closely the MuSig development, but I am wondering how much battle-tested it is as its very new cryptography? Do you think that risk should be considered in the benefit/costs analysis when compared to standard MultiSig (privacy gain vs. potential security risk)?

Would be great if you can continue to fine-tune and work out the details of the protocol.

Are you also on Matrix? I am @boilingfrog:matrix.org on Matrix.

@ChrisSon15
Copy link
Author

Additionally, the outputs is protected by requiring the signature of the arbitrator(s).

Beside the advantage that the arbitrator protects additionally against malicious traders publishing the dispute transaction I don't see a reason from a security POV for adding a 3rd party. Having a 3rd party being in partial control of users funds cause some uncertain risks from legal/regulatory POV and we prefer to avoid that.

good point. I would rather have the arbitrator not play a role in this as well. Without arbitrators pub key, the funds can be sent to the DAO at any time after the trade. May be it's a non issue, because the other trader will have no incentive. Actually, the other trader could be penalised for doing so. So I guess, we could drop that.

The transaction has 2 inputs and 4 outputs, ...

If we do not prepare the input utxo (as in the moment by the trade fee tx) there might be multiple inputs from each trader, which would be better for avoiding fingerprinting the tx. Also we could add random outputs to the traders if needed for improving privacy (at some small tx cost increase).

yes, I'll remove that sentence. Good idea to break fingerprinting by adding outputs and/or inputs.

...Bob could send a signature for his Public Key in the MultiSig. This Signature would need to have SIGHASH_NONE || SIGHASH_ALLCANPAY.

I assume you refer to the deposit tx here. I fear don't understand that. This would allow Alice to spend all the outputs to herself, no?

Yes, I am refering to the Deposit Tx, I should make that more clear in the text. It would allow Alice to spend the output, which was signed by Bob in this way, to herself or to spend it however she wants. Because a signature of type SIGHASH_NONE || SIGHASH_ALLCANPAY means, it can be used in any transaction. With this, Bob can allow Alice to use that output whenever for whatever she wants, without giving her the private key. That would be a bit smarter, but unfortunately, it requires a script output and therefore would be bad for privacy.

Beside those smaller questions/comments it looks sound to me as far as I understand it.

Would be great to get feedback from @alvasw and @stejbac as they are much more familiar with the cryptography behind all that.

I have not followed closely the MuSig development, but I am wondering how much battle-tested it is as its very new cryptography? Do you think that risk should be considered in the benefit/costs analysis when compared to standard MultiSig (privacy gain vs. potential security risk)?

Musig2 is defined in BIP-327 Status Draft. Implementation is in secp256k1 which is still a PR. A library which would make the implementation accessible for JVM is secp256k1-kmp. So by the time we would implement it, it will probably be released. AFAIK, the techniques are already used in lightning, but not sure. Once it's released in secp256k1, I think it's good to use.

Would be great if you can continue to fine-tune and work out the details of the protocol.

Are you also on Matrix? I am @boilingfrog:matrix.org on Matrix.

Yes, I am on Matrix: @crisson15:matrix.org, I will DM you.

@HenrikJannsen
Copy link

@ChrisSon15

As you mentioned above ACINQ/secp256k1-kmp#107, I wanted to let you know that a JVM compatible lib is not required as we plan to run the wallet as an independent process to the Bisq desktop app and not compiled into it (to avoid security risks in case a p2p app is running in the same jvm as the wallet). This gives us more options to choose a wallet library.

We have already support for bitcoind and Electrum (but for the light-wallet use-case we are looking for a more powerful library like BDK). A library supporting compact block filters next to Electrum/Esplorer would be good. If you have any suggestion in that regards please share. After the upcoming release we wanted to start working on Bisq Multisig protocol and choosing the wallet lib would be one of the first tasks.

@HenrikJannsen
Copy link

HenrikJannsen commented Jul 17, 2024

While trying to understand the protocol in more detail I though its easier to me to layout the steps in more detail.

@ChrisSon15 Can you confirm that the below is correct?

I think the 2nd taproot spend condition in the deposit tx is missing (the path which goes to dispute tx).

Setup

Alice is Bitcoin seller and offer maker
Bod is Bitcoin buyer and offer taker
It is assumed that there will be a second protocol pair with the maker and taker roles inverted with slight differences.

I ignore the change outputs, assuming the deposit tx inputs are the exact amounts needed. Also assume deposit amounts are the same (not sure if different amounts would have an impact).
I change the name for the secret key from d to p and q for the second output, to associate easier the secret key to the public key.
In the below protocol flow no optimizations in reducing rounds are included to keep it as simple as possible.
There is also not put much effort in security analysis yet, as first I want to be sure to understand the protocol.

Phase 1: Generate keys and send public keys and inputs to peer

Alice:

Creates secret key pA and public key PA
Creates secret key qA and public key QA
Sends PA, QA and inputsA to Bob

Bob:

Creates secret key pB and public key PB
Creates secret key qB and public key QB
Sends PB, QB and inputsB to Alice

Phase 2: Create derived pub keys and create DepositTx

Alice:

Creates P' from PA and PB and Q' from QA and QB
Use inputsA and inputsB to create a transaction spending to 2 WPKH outputs with pub keys P' and Q'. Output 0 (spendable with P') holds the trade amount+deposit intended to be consumed by Bob in the happy path, Output 1 (spendable with Q') holds the deposit intended to be consumed by Alice in the happy path.
At this point she has the transaction ID for crafting follow-up transactions. She does not sign her inputs yet until the follow up transactions are in place. Both outputs require the other peers secret key to be able to spend them.

TODO: I guess we miss a Taproot leaf for the alternative spend condition by the dispute transactions (P2SH).

Bob:

Same as above.

Phase 3: Create 2 dispute transactions: DisputeTxA and DisputeTxB

Alice:

Creates DisputeTxA with the 2 outputs from the deposit tx.

Output 0:

  • amount: Deposit and trade amount.
  • Key spend: P' In case that Alice has given Bob the 2nd private key for P' already, but still posting DisputeTxA, then Bob is able to immediately transfer the output 0 to his wallet by using P' as key spend. Note this should not happen, as it has disadvantages for Alice.
  • Script spend (taproot leaf): The script starts with a timelock. With the timelock it is not possible to spent before a certain time t1 has elapsed since the dispute transaction has been mined. This timelock is implemented by an OP_CSV instruction in the script.

Script spend in detail:

    OP_CSV <relative time t1>
    OP_DROP
    <Alice PubKey>
    OP_CHECKSIGVERIFY
    <Bob PubKey>
    OP_CHECKSIG

Output 1:

  • amount: Deposit amount.
  • Script spend (taproot leaf): Same script as above
    As there is no Key spend option it is guaranteed that the deposit goes to the distribution tx.

Bob:

Creates DisputeTxB with the 2 outputs from the deposit tx.

Output 0:

  • amount: Deposit amount.
  • Key spend: Q' In case that Bob has given Alice the 2nd private key for Q' already, but still posting DisputeTxB, then Alice is able to immediately transfer the output 1 to her wallet by using Q' as key spend. Note this should not happen, as it has disadvantages for Bob.
  • Script spend (taproot leaf): Same as above at DisputeTxA

Output 1:

  • amount: Deposit and trade amount.
  • Script spend (taproot leaf): Same script as above in DisputeTxA
    As there is no Key spend option it is guaranteed that the deposit and trade amount goes to the distribution tx.

Phase 4: Create 4 versions of distribution transactions

Alice:

Creates DistributionTx_1A with output 0 from DisputeTxA using the script spend leaf.

  • Input amount: Deposit and trade amount.
  • n WPKH outputs to distributed burning-men with the associated amounts per BM

Creates DistributionTx_2A with output 1 from DisputeTxA using the script spend leaf.

  • Input amount: Deposit amount.
  • n WPKH outputs to distributed burning-men with the associated amounts per BM

Bob:

Creates DistributionTx_1B with output 0 from DisputeTxB using the script spend leaf.

  • Input amount: Deposit amount.
  • n P2PK outputs to distributed burning-men with the associated amounts per BM

Creates DistributionTx_2B with output 1 from DisputeTxB using the script spend leaf.

  • Input amount: Deposit and trade amount.
  • n P2PK outputs to distributed burning-men with the associated amounts per BM

Phase 5: Create swap transactions: SwapTxA and SwapTxB

Alice:

SwapTxA spends output 0 from DepositTx (trade amount and deposit) to a WPKH output to Bob.

Bob:

SwapTxB spends output 1 from DepositTx (deposit amount) to a WPKH output to Alice.

The interactive process to create the adapter signature for both transactions give Alice the required signature to sign and broadcast SwapTxB, guaranteeing that she gets back her deposit.

She will not do that before she has received the Fiat trade amount as otherwise Bob can learn from the published SwapTxB the missing secret data to construct the signature for SwapTxA where he receives the trade amount and deposit.

In the happy path Alice will send p' to Bob (after having received he fiat payment) so Bob can consume output 0. After that Bob is expected (but not forced by the protocol) to send q' to Alice so that Alice can consume output 1 (refund of deposit).

If Bob would fail to send q' to Alice, then Alice can publish SwapTxB and receives back her deposit by that. Her disadvantage is that she cannot benefit from the single transaction property as she need to publish that SwapTxB which has a predefined output to her. Thought that cost is small and for Bob there is no incentive to not follow the happy path protocol.

What follows is the signing of the chained transactions and exchange of signatures.
After all transactions are prepared the traders can start the trade.

@ChrisSon15
Copy link
Author

ChrisSon15 commented Jul 17, 2024

This is a great writeup and hits the nail on the head. Good way of putting it into a more procedural way and leaving out uneccessary stuff. We can use your post to detail out the further specifics.

Although you suggested to leave away the security considerations for understanding the protocol, there is one issue which does influence the flow of the protocol:

Alice:
Creates secret key pA and public key PA Creates secret key qA and public key QA Sends PA, QA and inputsA to Bob

This would enable Bob to do a rogue key attack.

Rogue Key Attack in short:

Alice send her public key Pa to Bob. Bob generates a public key Pb, but instead of sending it to Alice, he computes P' = Pb - Pa. and sends P' to Alice.
Alice tries to compute the combined public key Pc by adding her key to it. Pc = P' + Pa. But Bob now can compute Pc by Pc = P' + Pa = Pb - Pa + Pa = Pb. So Bob has full control over the 'aggregated' key.

We can mitigate this by using Musig2, which calculates the aggregated key in a secure way and lets us compute aggregated signatures, which we can use to sign the Dispute Tx.

TODO: I guess we miss a Taproot leaf for the alternative spend condition by the dispute transactions (P2SH).

The aggregated signature which is computed by the Musig2 Algorithm can be used to unlock the output of the Deposit Tx. So the Dispute Tx of Alice references the Deposit Tx output 0 as Input. To spend it can present the signature of P' (which is the an aggregated PubKey). That signature needs to be calculated be Alice and Bob jointly using the Musig2 Algorithm.

So we are not missing a Taproot leaf for the dispute Tx as spend condition. But actually that might be a good idea. That might be an optimisation, which I need to think of. But it has the downside, that if we have a tapleaf, then the aggregated key needs to have a tweak. And that might complicate things down the road, when we are generating the adaptor signature. I will look into it.

This brings me to another point I just saw. In my original post in the Dispute Transactions I reused the aggregated keys P' in Dispute Tx Alice. But since the key spend in the Dispute Tx needs a tweak, because there is a tapleaf, it can not be the same public key as in the Deposit Tx. Let me fix this tomorrow. (So P' in Deposit Tx and P' in Dispute Tx need to be different)

Phase 4

  • Input amount: Deposit amount.
    ...

This is only a minor thing regarding the naming. Since Inputs do not have an amount, I would suggest to rename this to 'amount of outpoint' or 'amount of referenced output'.

If you don't have further requests for change, I would like to update your post (and mine) to reflect the latest changes and clarifications.

@stejbac
Copy link

stejbac commented Jul 18, 2024

I think that some simplifications to the protocol should be possible. In particular, it should be possible to remove SwapTx Alice and arrange to have pA revealed directly by the broadcast of SwapTx Bob. This is because Bob learns the random scalar t chosen by Alice in step (2) once she broadcasts SwapTx Bob. So Alice could instead send the scalar

pA + t

to Bob, as well as the curve point T, without leaking any information about pA to Bob, who could then verify the sum by multiplying by G to get the known curve point:

PA + T.

Then revealing t would also reveal pA.

In that case, I'm not sure the swap tx would be used that infrequently in practice, instead of directly exchanging private keys, as Bob could be offline when the seller confirms payment and Alice could be impatient to get her security deposit back. Not that it really matters from Bob's perspective and could be considered a normal trade closure.

I would also be inclined to use something similar to the warning, redirect and claim txs from the Bisq 1 v5 trade protocol upgrade (#421), with the warning txs taking the place of the two dispute txs, except spending both deposit inputs, having an absolute locktime, and with everything using Taproot instead. The redirect txs would take the place of the distribution txs. Then the keyspend path of the escrow warning tx output can be used to punish the counterparty and claim the entire escrow if they try to use it after the exchange of private keys at the end of the trade. This has the advantage, I think, of better handling the common case of one of the traders becoming unresponsive, without having to involve arbitrators or the DAO at all. (Since then one uses the claim tx to claim the entire escrow.)

In that case, one has a single tx protocol that is in some sense an extension of the obvious Taproot & MuSig2-enabled two-tx protocol that would arise from porting over the Bisq 1 v5 protocol and getting rid of the maker & taker fee txs, but with a change made to the structure of the deposit and payout txs as follows:

Instead of having,

  1. A deposit tx with 1 multisig output and a payout tx with 1 multisig input & 2 payout outputs,

one now has,

  1. A deposit tx with 2 multisig outputs and a swap tx with 1 multisig input & 1 payout output (to the seller), with the first deposit multisig output automatically becoming the buyer's payout when the swap tx is published.

Interestingly, both deposit-payout structures have the same tx size cost if p2tr, MuSig2 and keyspends are used exclusively, and should have identical security. Then, the extension to the two-tx protocol (arising from the second structure only) would be the option to exchange private keys at the end and elide the swap/payout tx, turning it into a one-tx protocol.

@ChrisSon15
Copy link
Author

This is great bringing in the view of Bisq1 v5 trade protocol (#421). That protocol has similar Transactions and I will rename the transaction to match those names:

  • Dispute Tx -> Warning Tx
  • Distribution Tx -> Redirect Tx

I found 4 items in your post requesting a change to the protocol:

  1. Dropping Swap Tx Alice and transferring the secret pA through the adaptor in the signature of Swap Tx Bob, which enables Bob to learn the secret pa and then is able to move his funds (P'). I think this is a great optimization. I hope that the library we will use will be able to do this non-standard way of adaptor signature, but that's an implementation detail.
  2. You mentioned the Swap Tx could even be the normal close of the trade. Great idea. Posting the Swap Tx would even invalidate the Warning Tx, because one input is spend already. That makes the Warning Tx impossible, which is good at that stage. Closing the trade with the Swap Tx has the disadvantage, that Alice has one more transaction. But at the same time the advantage that she can use the funds right after she sees the funds on her account, as you said. Also, this makes the protocol safer, as Arbitration is not possible anymore.
  3. You said the Warning Tx should pay out both output to P'. So in case of Alice posting the Warning Tx Alice after the trade closes (and after key exchange), then Bob can claim all funds for himself as punishment for Alice not following the protocol correctly. - Yes, this is justified IMO. And as with Allow non-absent Trade Peer to Claim Funds Before Arbitration #421 has good effect if other side is unresponsive.
  4. You wrote the Warning Tx should have absolute time instead of relative time. But what if Alice is not responsive and Bob waits until the absolute time has elapsed, then posts the Warning Tx. Then he can immediately post the Redirect Tx and everything is distributed to the burning men. This renders the Warning Tx useless.

Instead of having,

  1. A deposit tx with 1 multisig output and a payout tx with 1 multisig input & 2 payout outputs,

one now has,

  1. A deposit tx with 2 multisig outputs and a swap tx with 1 multisig input & 1 payout output (to the seller), with the first deposit multisig output automatically becoming the buyer's payout when the swap tx is published.

yes, that's at the heart of the protocol, leaving the funds in 2 outputs. Then swapping them using an atomic swap on the same chain.

@pazza83
Copy link

pazza83 commented Jul 19, 2024

@ChrisSon15 thanks for posting this. If we could combine 'reducing the number of trades from 4 to 1' with 'allowing the non-absent trade peer to claim funds prior to arbitration' that would be fantastic. This would make a significant improvement to the trade protocol.

I have some questions regarding data loss.

In the proposed protocol if Alice has completed a trade with Bob, but not spent her output, and then suffers a hard drive crash, will she be able to access the unspent output from her seed phrase alone?

Similar question; Alice is half way through a trade with Bob when she suffers a hard drive crash. Bob having not received payment from Alice publishes the Warning Tx. What does Alice require to publish her Redirect Tx?

Should the trade be sent to the burning men will this transaction have a minimum of two inputs one from Alice and one from Bob. Thereby ensuring both Alice and Both can prove ownership of the trade by signing a message for their respective address used to fund the trade?

Just trying to work out if data loss will be a bigger issue than currently where 99% of the time everything can be resolved if a user has access to their seed phrase.

@ChrisSon15
Copy link
Author

@ChrisSon15 thanks for posting this. If we could combine 'reducing the number of trades from 4 to 1' with 'allowing the non-absent trade peer to claim funds prior to arbitration' that would be fantastic. This would make a significant improvement to the trade protocol.

yes, Steven was mentioning it, we could merge the two.

I have some questions regarding data loss.

In the proposed protocol if Alice has completed a trade with Bob, but not spent her output, and then suffers a hard drive crash, will she be able to access the unspent output from her seed phrase alone?

No.
A Backup of the generated private key would be necessary, but the private key is not part of the derivation path (hence not recoverable from seed code)

Similar question; Alice is half way through a trade with Bob when she suffers a hard drive crash. Bob having not received payment from Alice publishes the Warning Tx. What does Alice require to publish her Redirect Tx?

At that point the Redirect Tx is fully signed, so she only need to post it. No computation or anything else, just send the string of the transaction to mempool.

Should the trade be sent to the burning men will this transaction have a minimum of two inputs one from Alice and one from Bob. Thereby ensuring both Alice and Both can prove ownership of the trade by signing a message for their respective address used to fund the trade?

If the funding came from an address (PKH transaction) then yes, but that might not be the case. In every case, the Warning Tx has a PubKey from Alice and Bob, so that would be the prime candidate for a prove of ownership.

Just trying to work out if data loss will be a bigger issue than currently where 99% of the time everything can be resolved if a user has access to their seed phrase.

good point.

@ChrisSon15
Copy link
Author

ChrisSon15 commented Jul 20, 2024

Here is a revised drawing with the suggestions from @HenrikJannsen and @stejbac, tried to merge the ideas from #421 into this.
STx3 drawio
Changes:

  1. Naming changed, from Deposit Tx to Warning Tx, from Distribution Tx to Redirect Tx
  2. I omitted the change outputs.
  3. Warning Tx changed:
  4. it has now only one output. If alice posts the Warning Tx after key have exchanged, she will be punished by losing her deposit to Bob.
  5. key spend has now PubKey UB instead of P' because P' from Deposit Tx cannot be reused. Alice has to give Bob uB when they are exchanging private keys.
  6. script spend 0: Arbitrator doesn't need to sign for redirecting to burning men.
  7. script spend 1 is new: If Bob is unresponsive, Alice can claim all for her.
  8. Claim Tx is new, this is not presigned. I Bob is unresponsive, Alice can send the funds to her wallet, as there is only her PubKey needed in script spend 1
  9. Only one Swap Tx. Swap Tx Bob can reveal the secret pA to Bob directly, so no need for second Swap Tx.

@ChrisSon15
Copy link
Author

Sequential description of the trade protocol

In the initial post I was describing more the concepts. Since then, there were a couple of changes to the protocol. So I want to describe here an updated version of the protocol. Also, I am now getting more in details describing it in a sequential way. I describe everything from Alice perspective only.

Happy path

image

Phase 1, Taking the offer - preparation

It starts when the offer is taken. I assume Alice is selling and Bob is buying.

Round 1 - construction of pre-signed transactions

Now we construct all pre-signed transactions, then we do the signing. The signing of the funding transaction comes last.

Alice creates random private keys pA,qA,rA and sA, then the corresponding public keys PA,QA,RA and SA
(pA and qA are for the Deposit Tx, while rA and sA are for the Warning Txs)

Alice sends to Bob:

  • the outpoint of her funding transaction
  • the pubkey 'Alice PubKey1' for use in the Warning Tx, output 0, script spend 0
  • the pubkey 'Alice PubKey2' for use in the Warning Tx, output 0, script spend 1

From Bob she receives his funding outpoint and his Pubkey for use in Warning Tx, output 0, script spend 0.

Round 2 - MuSig2 aggregate Keys

Alice engages with Bob to run the MuSig2 Algorithm to calculate the aggregated public keys P',Q',R' and S',
through using the KeyAgg Algorithm with KeySort from BIP-327.

Alice creates the ¸Deposit Tx`, the Warning Tx Alice/Bob and the Redirect Tx Alice/Bob. She sends the Txids to Bob. Then she verifies that the Txids which Bob send to her, are equal.

Round 3 - signing of pre-signed transactions

Alice signs the 'Redirect Tx Bob' with her pubkey 'Alice Pubkey1' which is in the Warning Tx, Output 0, script send 0. She sends this to Bob. She verifies that the signature which Bob sends is actually valid to send her Redirect Tx Alice. (so she is able to satisfy the input of the Redirect Tx).

Alice and Bob jointly sign the Warning Txs with the keys P' and Q' using the MuSig2 Algorithm. So Alice and Bob have the signatures to post their respective Warning Tx.
Bob sends his Signature for Warning Tx Alice to Alice. Alice will execute the MuSig2 signing for the Warning Tx Alice to generate the aggregated Signature. She will not send Bob her Signature for Warning Tx Alice, so Bob cannot broadcast Warning Tx Alice.

Round 4 - Atomic Swap

The atomic swap is using adaptor signatures and only 2 preparation steps can be made at this point (see the original description of adaptive signatures, Step (A) and (B)).
Alice uses a signing API like secp256k1-zkp
to produce the adaptor signature. As secret adaptor (called t usually) she chooses pA, that will reveal her secret partial key of P' to Bob and would enable Bob to spend the Deposit Tx, output 0.
Note, that the pA is not revealed to anybody else than Bob in this scheme. This is not very important since no outsider would have a benefit from knowing pA anyway.

Alice sends the public adaptor (s',RA, PA) to Bob. (see step (A) in the initial post, section 'adaptive schnorr signature')
Bob verifies the adaptor (see step (B) ).

Round 5 - posting to the blockchain

Alice sends Bob her signature for the funding transaction and she receives Bobs signature.

Alice broadcasts the Deposit Tx to Mempool.

Phase 2 sending of Fiat Payment

After the Deposit Tx is confirmed on the blockchain, Bob sends the Fiat payment to Alice.

Phase 3 Alice received the payment

Once Alice realised that she received the money, the protocol can continue.

Round 6 - rest of Atomic Swap Tx

Now the rest of the atomic swap sub-protocol is executed (that's from Step (C) onwards in my initial post, section 'adaptive schnorr signatures'): Bob sends the adaptor signature to Alice (called pre-signature in secp256k1-zkp). This signature is not a valid signature. Alice can make it a valid signature by adding pA to it and if she does that and uses the signature, then Bob can learn pA.

Round 7 - Key exchange

Following the normal protocol, Alice sends now the keys pA and rA to Bob. In case Bob cancels the protocol at this point, she can use the Swap Tx.

Alice receives the private keys qB and sB from Bob.

Alice now has qA and qB. Having both private keys for the Multisig Q'. So Alice is able to create any transaction to freely spend the Deposit Tx, output 1, which is the Buyer deposit.
To see this amount in her wallet, the wallet needs to be able to import the keys.
Also, Alice has sA nad sB. So if Bob broadcasts the Warning Tx Bob, then she can claim the money with constructing a transaction from output 0, key spend S'.

Alternative paths

before round 5, posting to the blockchain

After Alice has sent Bob the signature for the Deposit Tx, Bob could abort the protocol and not send his signature to Alice. At any point in the future he could post the Deposit Tx to mempool, then try to get all amount if Alice is not reacting. Alice can mitigate this, When she does not get the signature from Bob, she should send her funding output to a new address of herself to make the signed transaction useless.

after round 5 posting to the blockchain, but before round 7 (incl.)

If the Deposit Tx is broadcast, then if there is any derivation from the protocol, the Warning Tx Alice can be posted. The Warning Tx has 3 spent conditions:

  1. The key spend is to make sure that the Warning Tx is not posted after the key exchange happened (Round 7). Because with possession of the keys, Bob can spend the funds to his wallet at any time.
  2. After the time duration t1 has elapsed after mining the Warning Tx Alice, the script spend 0-condition gets active. Alice or Bob can send the funds into arbitration with the pre-signed transaction Redirect Tx Alice. Please note that both parties can send the funds into arbitration at this point.
  3. After time duration t2 with t2>t1 has elapsed, the script spend 1-condition gets active. In case Bob has been inactive (which means that he didn't use the key spend or the script spend 0 to move the funds into his wallet), Alice can construct a new transaction (called Claim Tx Alice) and send the funds into her possession. So a trade partner may lose all the funds to the other trade partner if unresponsive. Please see the further discussion about this case here.

after round 7 SwapTx

As part of the key exchange, Alice will get a signed transaction Swap Tx. If she uses that, a Warning Tx is not possible anymore. By broadcasting the transaction to mempool, she reveals the secret pAto Bob, so he is able to spend Deposit Tx, output 0.

Alternative closing of the protocol

The protocol is designed to be closed after round 7. But it could also end with round 6 if the Swap Tx is used, which could be defined as an legal close of the protocol, even though its no exactly a single transaction protocol in that case.

Mitigations

Communication rounds for traders

This communication protocol needs about 7 rounds. One round of communication is similar to a request/response cycle. Phase 1 needs 5 rounds. So it is necessary for practical reasons, that both traders are online at the same time to fulfill these communication cycles in a timely manner. Right now with Bisq this is the case anyway, so there is no change.
Phase 2 has no rounds.
Phase 3 has 2 rounds. This may be handled asynchronously but a better user experience would be if both are online again. This is up to discussion of how to exactly implement the protocol. Right now leave the computer on for a longer time is already an issues for Bisq. But as a note: This is only an issue with desktops. Mobile devices and server (either for web interfaces or as personal node like Umbrel) are always on. The Bitcoin space is moving into a direction of using more advanced cryptographic schemes. In this protocol we are using script-less scripts (MuSig2) and zero knowledge proofs (schnorr adaptive signatures are a simple zkp) this does need more active participation of the protocol participants. So moving forward (even with Lightning) this will be an issue to solve.

Watchtowers

When the protocol ends after round 7, it is still technically possible that oe trade uses a Warning Tx. To get advantage of this, the other trader needs to wait the time duration t2 to be able to use a Claim Tx and get the money out. He would take the risc that the first trader detects the transaction and uses his keys for multisig S' to send the mones to his possession. That would leave the attacker with a loss of his deposit at least. So I think this is unlkely to happen in the wild, we can still further secure this scenario. @stejbac suggested that watchtowers could be used, see wathtowers...

@HenrikJannsen
Copy link

I added a discussion post about an idea how to integrate BDK into Bisq 2: bisq-network/bisq2#2860

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
an:idea https://github.com/bisq-network/proposals/issues/182#issuecomment-596599174 re:protocol
Projects
None yet
Development

No branches or pull requests

5 participants