Successful atomic cross chain protocol

[jl777]

Based on Tier Nolan's idea, I have made a way to atomically trade between BTC and NXT/NXTassets. I should be able to combine two such swaps so effectively a BTC <-> ALT (that supports p2sh) would be able to be done.

I lobbied for NXT to support pay on reveal of secret (to specific destination) where the funds are locked using rmd160(sha256(secret)) and it is released when the secret that hashes to that value is submitted.

It took several attempts to solve this and there could well still be some edge cases, and this will be going into InstantDEX as a meta-exchange called "wallet". So best to find any flaws before it goes into beta test.

Here is the protocol:

0. Alice and Bob agree to the terms of the trade and share the pubkeys of their published address. Bob sends the rmd160(sha256(onetimepubkey)) to Alice along with a NXT release on secret linked to the same hash.

1. Both calculate the same p2sh address which allows redemption via 2of2 multisig or normal spend by Bob's onetimepubkey

2. Alice sends to Bob an unsigned funding transaction to the p2sh address for the amount agreed upon.

3. Bob creates a multisig refund tx for the entire amount back to Alice timelocked into the future, signs and sends to Alice.

4. Alice verifies the refund is proper and if it is, broadcasts the funding transaction, which creates a spendable output

5. Due to malleability, Bob needs to wait until it has enough confirms (1 should be enough?) for the value being traded. When he is satisfied, he spends the funds from the p2sh address using the normal path and this publishes his pubkey.

6. Alice submits this pubkey to release the NXT side of the transaction.

The above is the theory, in reality there are a few nasty surprises. If you use timelock and have a sequenceid of -1, timelock is ignored and it gets into the blockchain right away and the input is marked as spent immediately. If you have a sequenceid that is not -1, it is rejected with {"code":-26,"message":"64: non-final"}. So, Alice will have to keep in pocket the refund transaction and make sure to submit it if Bob hasnt revealed his pubkey.
 
This was from a manual run:

Alice addr:14XrJHhqMvDszMMwKR2d6u5PPvDeRieQoG -> 03b4143b6e7a064a78bc66dab0ca72251fea3d6fd8db1f4c48b91996d7af62dd05
Bob addr: 17Y5rr67RpTtuCd929dS6muyKZmjqJZQpr -> 037387677a21b8ebb472ff2d00892098dcd990a9a21b09b8e22aefece8b1cbbdc0
Bob's onetime addr 1NBKFDmmHSpSzFnP9bX5bDWnm9zqD6nUv4 -> 03c8a7e64c763e908549aa0f93974ab346a559b486eba32bf14338542b4282b916 -> e84e0808b8cd32c38fa2093a490efabc6be53d7a

Both can now calculate p2sh address of 37FsSwJ59z5UuRjNFjtfNYWVFquBEsUGHC from the redeemscript:
OP_IF OP_2 03b4143b6e7a064a78bc66dab0ca72251fea3d6fd8db1f4c48b91996d7af62dd05 037387677a21b8ebb472ff2d00892098dcd990a9a21b09b8e22aefece8b1cbbdc0 OP_2 OP_CHECKMULTISIG
OP_ELSE OP_DUP OP_HASH160 e84e0808b8cd32c38fa2093a490efabc6be53d7a OP_EQUALVERIFY OP_CHECKSIG
OP_ENDIF

I just combined a standard 2of2 and standard pubkeyhash into an conditional, but having never dealt with p2sh till this weekend, nor with signing of bitcoin tx, it was quite a lot of work to get this working as there doesnt seem to be any real support for custom p2sh scripts. Anyway, thanks to jgarzik's libbcoin, I was able to get the signing working in a day and stumbled about figuring out the "obvious" things about p2sh scripts.

[As an aside, if there is a way to verify that e84e0808b8cd32c38fa2093a490efabc6be53d7a is from the third pubkey of a 2of3 multisig address, then there would have been no need for any custom redeemscript. Just normal spends to a 2of3 multisig would have worked (with bob having 2 of the three addresses). Unfortunately I think it is crypto hard to go from msig address + pubkeyhash and 2 of 3 pubkeys to the third pubkey. And if that is not possible, then Alice has no way to know that bob didnt just give her a bogus pubkeyhash]

Bob sends to Alice: e84e0808b8cd32c38fa2093a490efabc6be53d7a
NXT tx: 1117487717739855000 hashed_secret:   cc863b881f35bbeca374b25d018d4e17dc4aa19b Hash:   RIPEMD160_SHA256

and Signed refund tx in pocket: 0100000001a9b3602a28960f1d855d1f52eea54f5e8b6fff469d54083ce433962b1c16dfe100000 000f800483045022100d1439b9170a6d14e07dc6a11dd5c1aab80df302fe4f1de77e12c7859ba20 361f02202dcc946b75995b62fb798b68e9bd443988c4004187f3c5cae52831b9415a712c0147304 40220754d43345edbeffd25cdfc6cbed16f59b1ef25c02092ff1752f0386e6a624e3d022075ef75 78ccb2bbd0a8c58394ed7e4c5803b6ee66691623342fe19862146fda9f01514c6363522103b4143 b6e7a064a78bc66dab0ca72251fea3d6fd8db1f4c48b91996d7af62dd0521037387677a21b8ebb4 72ff2d00892098dcd990a9a21b09b8e22aefece8b1cbbdc052ae6776a914e84e0808b8cd32c38fa 2093a490efabc6be53d7a88ac68a510ec550130750000000000001976a91426be0216d0089626b3 fc3a81f7d844f31a47e0fd88ac34b20500

then Alice broadcasts funding tx e1df161c2b9633e43c08549d46ff6f8b5e4fa5ee521f5d851d0f96282a60b3a9

Bob sees it on the blockchain and spends: 176026872b52b952c4649ee0b44026f87e2282aaaea7994117659a699662ae0a which reveals 03c8a7e64c763e908549aa0f93974ab346a559b486eba32bf14338542b4282b916.

Alice see's Bob's spend and submits an NXT phasing approval tx.

Prior to Alice funding the p2sh address, at worst some of Bob's temporary NXT reserves are held up for a time. After the trade is funded, we have a few cases:

a) Bob spends, Alice approves, both are happy
b) Bob doesnt spend to his address, then after timelock, Alice is able to submit the timelocked refund
c) edge cases: ?

clearly the timelocks need to be set properly, maybe 10 BTC blocks ahead and make it double the estimated time on the NXT side

All steps other than 5, can happen in seconds, so this is a BTC block timeframe in the mainstream case, 10 BTC blocks in the refund case. Not bad for a fully decentralized trade.

Once I verify a timelocked tx I am making can be submitted after the specified block, then I will fully integrate this into InstantDEX

James

[jl777]

4. Alice verifies the refund is proper and if it is, broadcasts the funding transaction, which creates a spendable output

Bitcoin refund transactions have a known problem. A refund transaction works only for a specific txid, but the funding txid included in a block can be something else (malleability), which would cause the refund transaction to become useless. Do you have a solution for this?

I dont think there is a problem with the way I am doing it. require Bob to wait for the funding tx to be confirmed in the blockchain. At that point malleability is not an issue. So if Alice is trying to cheat by making the funding tx invalid, Bob never spends the funds (since the funds arent there he cant spend them anyway) and as long as he never uses the onetime address (prior to finish height), then his side of the tx within the NXT phased tx will never get confirmed.

The sequence is:

Bob sends Alice the pubkeyhash and a phased tx that can only be approved when the pubkey to that pubkeyhash is revealed and this must happen for Bob to be able to spend the output.

The unspent output is created by Alice, but only the unsigned txbytes and the txid is sent to Bob.

He can then send to Alice a signed refund transaction using the 2of2 multisig side. Alice verifies everything is good at this point she has a fully signed refund transaction, but she cannot submit it to the network yet as it is timelocked.

At this point if she fiddles with the funding txid taking advantage of malleability, then she is just making it so that she cant get her refund, so it doesnt seem to make sense for her to do. And even if she did, Bob wont spend the funds until it is in the blockchain.

The edge case is that it gets into the blockchain and then reorgs, giving Alice a chance to make it malleable, but Bob already disclosed his pubkey. However, Bob controls the timing of his spend (up to timelock deadline), so he can wait until he is comfortable with the risks.

The malleability is a nasty issue, but unless anybody can find a specific malleability that breaks the protocol, it would seem that I have solved this.

Alice is the one that creates the funding transaction and the refund will be based on the txid for this, so it is only Bob that is at risk and he controls this by making sure there are enough confirms.

Does anybody see a malleability issue that isnt solved by the protocol?

James

[jl777]

So if Alice is trying to cheat by making the funding tx invalid

The known problem is the refund transaction being invalid, not the funding transaction. Bob quits, and Alice has no valid refund transaction.  (I didn't read your protocol carefully, but there is a fundamental problem with a refund transaction, at least at the moment.)

[jl777]

So if Alice is trying to cheat by making the funding tx invalid

The known problem is the refund transaction being invalid, not the funding transaction. Bob quits, and Alice has no valid refund transaction.  (I didn't read your protocol carefully, but there is a fundamental problem with a refund transaction, at least at the moment.)

If Bob quits, then how does that invalidate the refund transaction?

Alice creates funding tx and doesnt broadcast this until she is satisfied that the refund tx (and phased tx) are all valid.

Funding tx -> Refund tx, but also Bob can spend the Funding tx -> Bob's spending

But in the latter case, the pubkeyhash is revealed and Alice can approve the phasedtx

Alice creates the funding tx, Alice broadcasts the funding tx, the refund tx uses the funding tx as its input. If Bob bails after he signed the refund tx, then Alice would wait for her refund tx to mature and then submit it. By giving control over the funding tx to the party that relies on it, I think this is they key reason that my protocol works. Having NXT involved in the process acts as a sort of an independent third party as it makes Bob's side totally atomic and with one side totally atomic it is possible (just barely) to make Alice's side secure.

So what is the fundamental problem?

James

[jl777]

It seems that bitcoin still allows unrelated third parties to change the txid and while this would just be vandalism, it sure would be nice to close this exposure.

I posted a proposed solution for this, which hopefully can be included in an upcoming hardfork
https://bitcointalk.org/index.php?topic=303088.msg12349816#msg12349816

James

[jl777]

Thanks for everybody's feedback, its good to know I am not alone.

Anyway, it seems that there is the possibility that some vandal to just intercept, modify and rebroadcast transactions, which would invalidate the refund transaction and if Bob can wait out the expiration time for the other half of the trade, he could cash in the coins safely.

I sure hope some BIP in upcoming hardfork will fix this problem as allowing unrelated third parties to change the txid is just wrong.

So for big money transactions, even a small risk like this is not a good thing. Alternative is to break up the trade into multiple pieces, which already can be done just by not trading increments larger than pain threshold.

I will also add an optional third signer for the multisig address, so that in the event that the txid was changed via malleability, the refund will be processed. Since if the refund is processed, then Bob is not out anything and if he just spends the funds, Alice can approve the NXT tx, so it might even be something safe enough to automate.

James

[spartacusrex]

You are not alone... 

I'd love a solution.

The Only one I could think if, is as you mention at the end, to have a 3rd signer.

So you would make a 2-of-3 address, and if there is a TXN malleability issue, AND the other party tries to blackmail you (which he may not do), then you can always fall back on the 3rd signer to process the refund.

BUT - the issue with that is that you and the 3rd signer could send the funds whenever you like, without waiting for the required locktime. So the 2nd Party, the one you are trying to trade with, would then be at the mercy of the first and 3rd signer..
 
I can't think of a way of preventing the 3rd signer from 'not' signing until a reasonable amount of time has passed, as otherwise the other party would not get involved in the first place. Other than TRUST of course.

I wanted to implement this in an exchange, as I'm sure many of us do, but it's just not quite there yet..

..

OP_CHECKLOCKTIME !? When please..?

[jl777]

You are not alone... 

I'd love a solution.

The Only one I could think if, is as you mention at the end, to have a 3rd signer.

So you would make a 2-of-3 address, and if there is a TXN malleability issue, AND the other party tries to blackmail you (which he may not do), then you can always fall back on the 3rd signer to process the refund.

BUT - the issue with that is that you and the 3rd signer could send the funds whenever you like, without waiting for the required locktime. So the 2nd Party, the one you are trying to trade with, would then be at the mercy of the first and 3rd signer..
 
I can't think of a way of preventing the 3rd signer from 'not' signing until a reasonable amount of time has passed, as otherwise the other party would not get involved in the first place. Other than TRUST of course.

I wanted to implement this in an exchange, as I'm sure many of us do, but it's just not quite there yet..

..

OP_CHECKLOCKTIME !? When please..?

other than during the malleability attack last year, how often are random third parties messing with txids of others? There seems to be no gain from this, so just vandalism?

It just seems like preventing tampering of txid by unrelated third parties should be fixed after all these years. Any other solution is just a workaround and needless complexity

James

[TierNolan]

Anyway, it seems that there is the possibility that some vandal to just intercept, modify and rebroadcast transactions, which would invalidate the refund transaction and if Bob can wait out the expiration time for the other half of the trade, he could cash in the coins safely.

Yes, this is the big malleability problem.  You can't be sure the transaction you send to the blockchain is the same as the one that gets included.

The ideal malleability solution is use normalized txids.  This means not including the signatures when referring to previous transactions. 

txid = hash(full transaction)
norm-txid = hash(transaction with signatures set to zero length strings)

There is also a plan to introduce a new OP_CHECKSIG (and VERIFY) opcode.  One of its properties is that it will replace all the txids in a transaction to the n-txids that would have been used if n-txids had been used since block 0.

This closes the malleability problem, since everything else is signed by the creator of the transaction.

OP_CHECKLOCKTIMEVERIFY will solve the problem too.  It also removes the need for refund transactions to create the timelocking.

[spartacusrex]

Is it possible to create 2 txns with the same normalised txid ?

[jl777]

Is it possible to create 2 txns with the same normalised txid ?

I have seen two pairs of identical txids, back around block 90000 and they are in the blockchain

To fix this once and for all, would need to have a first come first served allocation of txid, so duplicates would be rejected. Kind of a mess if a reorg happens though...

[TierNolan]

Is it possible to create 2 txns with the same normalised txid ?

There are two coinbase transactions that are identical and the first one is now unspendable.

After that, a new rule was added that the coinbase must have the height of the block included in the coinbase.  This means that every coinbase transaction is different and so they all have different hashes.

I guess that norm-txids would be the same for 2 coinbases, since the height would be stripped.  The definition would have to define the extraNonce field in the coinbase as not a signature and not delete it.

[jl777]

Is it possible to create 2 txns with the same normalised txid ?

There are two coinbase transactions that are identical and the first one is now unspendable.

After that, a new rule was added that the coinbase must have the height of the block included in the coinbase.  This means that every coinbase transaction is different and so they all have different hashes.

I guess that norm-txids would be the same for 2 coinbases, since the height would be stripped.  The definition would have to define the extraNonce field in the coinbase as not a signature and not delete it.

I am assuming that any fix for the third party malleability of txids will be months away, if not a year+.
Also, I assume that the percentage of transactions that have been malleabled is <1%

Using a third party arbiter as a third signer in 2of3 multisig would prevent funds being locked forever and also there would be strict deterministic rules on Alice making a claim. However... Both Bob and Alice would have to trust that the arbiter wont collude with the other.

Assuming the above is true, there seems to be only one solution

James

[TierNolan]

I am assuming that any fix for the third party malleability of txids will be months away, if not a year+.

OP_CHECKLOCKTIMEVERIFY is intended "soon".  The plan was for deployment to happen immediately after the last soft fork. 

The block size debate has slowed deployment.

[jl777]

I am assuming that any fix for the third party malleability of txids will be months away, if not a year+.

OP_CHECKLOCKTIMEVERIFY is intended "soon".  The plan was for deployment to happen immediately after the last soft fork. 

The block size debate has slowed deployment.

I'm a bit confused how OP_CHECKLOCKTIMEVERIFY would fully solve things. If the refund transaction is using that, then it needs to refer to the funding txid, but the funding txid cant be in the blockchain until the refund is locked.

So what prevents the funding txid to be malleabled by vandal invalidating the refund? Also, does the OP_CHECKLOCKTIMEVERIFY defer checking for its inputs until the locktime expires? Otherwise it seems that the funding txid needs to be in the blockchain first.

[TierNolan]

I'm a bit confused how OP_CHECKLOCKTIMEVERIFY would fully solve things. If the refund transaction is using that, then it needs to refer to the funding txid, but the funding txid cant be in the blockchain until the refund is locked.

It is an alternative way to get the same functionality (and some other stuff too).

Alice's create a transaction that pays to

Code:

OP_IF
    <one month in the future> OP_CHECKLOCKTIMEVERIFY OP_DROP <Alice's public key> OP_CHECKSIG
OP_ELSE
    OP_HASH160 <Hash160(x)> OP_EQUALVERIFY <Bob's public key> OP_CHECKSIG
OP_ENDIF

After one month, Alice can spend the output

Code:

<Alice's signature> OP_1

The OP_1 forces the first part of the OP_IF to fire.  The OP_CHECKLOCKTIMEVERIFY causes the script to fail unless one month has passed [*].  Otherwise, the OP_CHECKSIG verifies Alice's signature.

Alternatively, Bob can spend the output by providing

Code:

<Bob's signature> <x> OP_0

The OP_0 forces the OP_ELSE part of the IF to be used.  Bob must provide x in order to spend his output.

Alice can then use it to spend Bob's equivalent output on the other chain.


[*]  Technically, it makes sure the spending transaction's locktime is at least that far in the future, which has the same effect.

[jl777]

I'm a bit confused how OP_CHECKLOCKTIMEVERIFY would fully solve things. If the refund transaction is using that, then it needs to refer to the funding txid, but the funding txid cant be in the blockchain until the refund is locked.

It is an alternative way to get the same functionality (and some other stuff too).

Alice's create a transaction that pays to

Code:

OP_IF
    <one month in the future> OP_CHECKLOCKTIMEVERIFY OP_DROP <Alice's public key> OP_CHECKSIG
OP_ELSE
    OP_HASH160 <Hash160(x)> OP_EQUALVERIFY <Bob's public key> OP_CHECKSIG
OP_ENDIF

After one month, Alice can spend the output

Code:

<Alice's signature> OP_1

The OP_1 forces the first part of the OP_IF to fire.  The OP_CHECKLOCKTIMEVERIFY causes the script to fail unless one month has passed [*].  Otherwise, the OP_CHECKSIG verifies Alice's signature.

Alternatively, Bob can spend the output by providing

Code:

<Bob's signature> <x> OP_0

The OP_0 forces the OP_ELSE part of the IF to be used.  Bob must provide x in order to spend his output.

Alice can then use it to spend Bob's equivalent output on the other chain.


[*]  Technically, it makes sure the spending transaction's locktime is at least that far in the future, which has the same effect.

cool!
The funding and refundtx are the same one. Yes, this is much cleaner solution. I hope it is available this year

[TransaDox]

OP_IF
    <one month in the future> OP_CHECKLOCKTIMEVERIFY OP_DROP <Alice's public key> OP_CHECKSIG
OP_ELSE
    OP_HASH160 <Hash160(x)> OP_EQUALVERIFY <Bob's public key> OP_CHECKSIG
OP_ENDIF


After one month, Alice can spend the output

Is there any use-case when this "return to sender if/when expired" would not be desirable as a default transaction?

[TierNolan]

The funding and refundtx are the same one. Yes, this is much cleaner solution. I hope it is available this year

Right.  The script is extended so that it can implement the functionality directly.

From what I have seen, the Lightening Network still requires refund transactions for some of their more complex operations, even with OP_CHECKLOCKTIMEVERIFY, so malleability still should be fixed.

Is there any use-case when this "return to sender if/when expired" would not be desirable as a default transaction?

Not sure of any.  The reason for it is to help with "hold-up" risk where one party disappears and/or refuses to complete the protocol.