Bitcoin Forum
May 25, 2019, 02:46:41 PM *
News: Latest Bitcoin Core release: 0.18.0 [Torrent] (New!)
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Trying to get a deeper understanding of atomic swaps  (Read 346 times)
noobWithAComputer
Newbie
*
Offline Offline

Activity: 8
Merit: 18


View Profile
July 16, 2018, 12:43:59 PM
Merited by Welsh (5), danda (3), dbshck (2), vapourminer (1), qwk (1), ETFbitcoin (1), HeRetiK (1)
 #1

Hi together,

I'm an IT-student and writing a thesis about atomic swaps on BTC and BTC-like blockchains. For the thesis I decided to use BTC, LTC, BCH and DCR. These chains have a somehow similar codebase and the same scripting language (I'm not a professional, so there might be differences, but they are not that serious). And they all have a high enough marketcap to be relevant for atomic swaps.
So the goal of the thesis is to find hashed timelock contracts (HTLCs) and connect matching HTLCs from different chains to get the atomic swap. Therefore I first searched the web for anything on atomic swaps [1] and analyzed the input script of this transaction [2] to get a basic understanding how atomic swaps work and what they look like.
Then I wrote a go program to search for any script longer than simple P2PKH scripts. This gave me a list of many different scripts which I analyzed by hand to only take the HTLC ones. (Besides many multisig scripts, there is not much to find on BTC^^)
At this point I found multiple different types of HTLCs as listed below. Afterwards I crawled* BTC again saving all transactions with HTLC scripts, storing the interesting data like tx-id, input value, pubKeyHashes, the secrets and their hashes. I found about one hundret HTLCs on BTC so far.
I did the same for LTC and found about 400 HTLCs.
As far as I understood, the secrets of HTLCs have to be the same on both chains. So I wrote another go program to match the found HTLCs from BTC and LTC and got around 30 matches. The next steps would then be to crawl BCH and DCR and also match the HTLCs found there.

* Crawling in this case means that I start to search the blockchain backwards (to get the newest first, the beginning years are not that interesting in this case^^) until the beginning of 2017. So about 18 months. As stated in [1] the first known atomic swap between BTC and LTC was made on 19th April 2017 (or April 19th 2017 or 19.4.2017 or whatever you like). So there is not much sense in crawling any further.

My questions now are the following:

  • Why are there so many different types? Is it compatibility with other chains? Or what?
  • What are the differences between these types (besides length and hashing algorithm)?
  • What are the advantages and disadvantages of these types?
  • Why are there so many HTLCs on LTC and so few on BTC?
  • Do you know other such HTLC scripts?
  • Can you provide interesting resources on this topic?

I'm open to any constructive input and hope you have a few answers for me. Thank you in advance.

Type 1: sha256 secret, length=97byte
Code:
63 if
82 size
01 data1
20
88 equalverify
a8 sha256
20 data32
<secret_hash 32byte>
88 equalverify
76 dup
a9 hash160
14 data20
<pubkey_hash1 20byte>
67 else
04 data4
<timelock 4byte>
b1 checklocktimeverify
75 drop
76 dup
a9 hash160
14 data20
<pubkey_hash2 20byte>
68 endif
88 equalverify
ac checksig

Type 2a: sha256 secret, length=94byte
Code:
63 if
a8 sha256
20 data32
<secret_hash 32byte>
76 dup
a9 hash160
14 data20
<pubkey_hash1 20byte>
88 equalverify
ac checksig
67 else
04 data4
<timelock 4byte>
b1 checklocktimeverify
75 drop
76 dup
a9 hash160
14 data20
<pubkey_hash2 20byte>
88 equalverify
ac checksig
68 endif

Type 2b: sha256 secret, length=93byte
Code:
63 if
a8 sha256
20 data32
<secret_hash 32byte>
88 equalverify
76 dup
a9 hash160
14 data20
<pubkey_hash1 20byte>
67 else
04 data4
<timelock 4byte>
b1 checklocktimeverify
75 drop
76 dup
a9 hash160
14 data20
<pubkey_hash2 20byte>
68 endif
88 equalverify
ac checksig

Type 3: ripemd160 secret, length=81byte
Code:
63 if
a6 ripemd160
14 data20
<secret_hash 20byte>
88 equalverify
76 dup
a9 hash160
14 data20
<pubkey_hash1 20byte>
67 else
04 data4
<timelock 4byte>
b1 checklocktimeverify
75 drop
76 dup
a9 hash160
14 data20
<pubkey_hash2 20byte>
68 endif
88 equalverify
ac checksig

Type 4a: hash160 secret, length=86byte
Code:
63 if
03 data3
<timelock 3byte>
b1 checklocktimeverify
75 drop
76 dup
a9 hash160
14 data20
<pubkey_hash2 20byte>
88 equalverify
ac checksig
67 else
76 dup
a9 hash160
14 data20
<secret_hash 20byte>
88 equalverify
ad checksigverify
82 size
01 data1
21 -> 33
88 equalverify
a9 hash160
14 data20
<pubkey_hash1 20byte>
87 equal
68 endif

Type 4b: hash160 secret, length=82byte
Code:
63 if
03 data3
<timelock 3byte>
b1 checklocktimeverify
75 drop
76 dup
a9 hash160
14 data20
<pubkey_hash2 20byte>
88 equalverify
ac checksig
67 else
76 dup
a9 hash160
14 data20
<secret_hash 20byte>
88 equalverify
ad checksigverify
a9 hash160
14 data20
<pubkey_hash1 20byte>
87 equal
68 endif

Type 5a: hash160 secret, length=81byte
Code:
63 if
a9 hash160
14 data20
<secret_hash 20byte>
88 equalverify
76 dup
a9 hash160
14 data20
<pubkey_hash1 20byte>
67 else
04 data4
<timelock 4byte>
b2 checksequenceverify
75 drop
76 dup
a9 hash160
14 data20
<pubkey_hash2 20byte>
68 endif
88 equalverify
ac checksig

Type 5b: hash160 secret, length=78byte
Code:
63 if
a9 hash160
14 data20
<secret_hash 20byte>
88 equalverify
76 dup
a9 hash160
14 data20
<pubkey_hash1 20byte>
67 else
01 data1
<timelock 1byte>
b2 checksequenceverify
75 drop
76 dup
a9 hash160
14 data20
<pubkey_hash2 20byte>
68 endif
88 equalverify
ac checksig

Type 6: hash160 secret, length=79byte
Code:
63 if
54 <timelock op>
b1 checklocktimeverify
75 drop
76 dup
a9 hash160
14 data20
<pubkey_hash2 20byte>
88 equalverify
ac checksig
67 else
76 dup
a9 hash160
14 data20
<secret_hash 20byte>
88 equalverify
ad checksigverify
a9 hash160
14 data20
<pubkey_hash1 20byte>
87 equal
68 endif

Type 7: multiple ripemd160 secrets, length=80 + n*23byte
Code:
63 if
a6 ripemd160
14 data20
<secret_hash1 20byte>
88 equalverify
a6 ripemd160
14 data20
<secret_hash2 20byte>
...
88 equalverify
a6 ripemd160
14 data20
<secret_hash_n 20byte>
88 equalverify
21 data33
<signature1 33byte>
ac checksig
67 else
04 data4
<timelock 4byte>
b1 checklocktimeverify
75 drop
21 data33
<signature2 33byte>
ac checksig
68 endif

Type 8: multiple ripemd160 secrets, length=81 + n*23byte
Code:
74 depth
60 16
87 equal
63 if
a6 ripemd160
14 data20
<secret_hash1 20byte>
88 equalverify
a6 ripemd160
14 data20
<secret_hash2 20byte>
...
88 equalverify
a6 ripemd160
14 data20
<secret_hash15 20byte>
88 equalverify
21 data33
<signature1>
67 else
03 data3
<timelock 3byte>
b1 checklocktimeverify
75 drop
21 data33
<signature2>
68 endif
ac checksig

[1] http://www.cryptovibes.com/crypto-news/charlie-lees-atomic-swap-between-litecoin-and-bitcoin-was-a-success/
[2] https://insight.bitpay.com/tx/0bb5a53a9c7e84e2c45d6a46a7b72afc2feffb8826b9aeb3848699c6fd856480
1558795601
Hero Member
*
Offline Offline

Posts: 1558795601

View Profile Personal Message (Offline)

Ignore
1558795601
Reply with quote  #2

1558795601
Report to moderator
1558795601
Hero Member
*
Offline Offline

Posts: 1558795601

View Profile Personal Message (Offline)

Ignore
1558795601
Reply with quote  #2

1558795601
Report to moderator
1558795601
Hero Member
*
Offline Offline

Posts: 1558795601

View Profile Personal Message (Offline)

Ignore
1558795601
Reply with quote  #2

1558795601
Report to moderator
PLAY OVER 3000 GAMES
LIGHTNING FAST WITHDRAWALS
PLAY NOW
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1558795601
Hero Member
*
Offline Offline

Posts: 1558795601

View Profile Personal Message (Offline)

Ignore
1558795601
Reply with quote  #2

1558795601
Report to moderator
danda
Full Member
***
Offline Offline

Activity: 194
Merit: 139


View Profile WWW
July 19, 2018, 08:36:27 AM
 #2

Interesting research.  Please keep posting your findings.   Do you plan to build/release a tool for people to make atomic swaps?

Well you clearly know more about atomic swaps than I do, but I would guess there are so many types because multiple parties have implemented them in isolation and for different blockchains.


mybitprices.info - wallet auditing tools
noobWithAComputer
Newbie
*
Offline Offline

Activity: 8
Merit: 18


View Profile
July 19, 2018, 09:53:06 AM
 #3

When I find the time to translate my work (I'm writing the thesis in german), I will post them here.

As I will start my Diplom thesis in a few months, I won't have the time to implement such a tool. But I hope my findings may help other people to do so.
HeRetiK
Legendary
*
Offline Offline

Activity: 1120
Merit: 1049


the forkings will continue until morale improves


View Profile
July 19, 2018, 01:01:40 PM
 #4

Lightning Network uses HTLCs as fundamental building blocks, so maybe this accounts for some of the HTLCs you are seeing that do not correlate to atomic cross-chain swaps? The first known mainnet LN transaction took place some time in late December 2017 [1] so that should be the first time that a LN related HTLC hit the blockchain. However there are currently more than 6000 LN channels open [2] so maybe LN opening / closing transaction don't satisfy your search criteria and thus don't show up in the first place.

[1] https://news.bitcoin.com/first-real-bitcoin-lightning-network-payment-completed-via-bitrefill/

[2] https://lnmainnet.gaben.win/

noobWithAComputer
Newbie
*
Offline Offline

Activity: 8
Merit: 18


View Profile
July 20, 2018, 09:41:43 AM
 #5

Interesting, thank you for these information.

I just checked the HTLCs I found and there was none in Dec 2017. So it seems the LN HTLCs have another structure. I will take a deeper look into this in the next days.
Kallisteiros
Copper Member
Member
**
Offline Offline

Activity: 85
Merit: 48


View Profile
July 21, 2018, 09:21:47 PM
Merited by ETFbitcoin (1), danda (1)
 #6

  • Why are there so many different types? Is it compatibility with other chains? Or what?
Different implementations of the same idea

Quote
  • What are the differences between these types (besides length and hashing algorithm)?
Type 1 stands out by its first instructions, ensuring the supplied secret preimage to the puzzle hash is 32 (0x20) bytes in length. It's there to mitigate the attack described here: https://gist.github.com/markblundeberg

Type 2a appears to be broken, couldn't figure this one out. It tries to compare hash160(puzzle_hash) == pubkey_hash1, with both values in the same script, which doesn't make sense.

Type 2b is the most straightforward. If sha256 of preimage matches the hash and signed by Bob, or timelock is unlocked and signed by Alice, allow to spend the output.

Type 3 is equivalent to 2b, except it uses ripemd160 puzzle instead of sha256.

Type 4a just swaps the conditions, which doesn't affect anything (except the switch value you put that will decide which branch of OP_IF will be executed). Plus, as in Type 1, it puts constraints on the secret preimage's size. You got the labels here wrong, by the way, <secret_hash 20byte> and <pubkey_hash1 20byte> should be swapped.

Type 4b is the same as 4a, minus the size check.

Type 5a uses CHECKSEQUENCEVERIFY instead of CHECKLOCKTIMEVERIFY, which is a minor difference. If you're at block 500, and you want to lock the coins until block 530, you can either say "530 CHECKLOCKTIMEVERIFY" or "30 CHECKSEQUENCEVERIFY" (I might have made an off-by-one error here though, check the BIP for the exact usage).

Type 5b: the only difference with 5a is timelock value size (instead of 4 byte integer, you can have it in a more compact form with only 1 byte integer, which will give you a lock period of up to 256 blocks).

Type 6: is exactly like Type 4b, only it uses a shorthand for pushing the timelock value. You also got the labels backwards here, swap <secret_hash> with <pubkey_hash1>.

Type 7 and 8: as you correctly noticed, they use several puzzles at once. Got no idea why. Maybe it has something to do with the puzzle datatype size constraints on the altcoin side of the exchange.



Quote
  • What are the advantages and disadvantages of these types?
They appear to be slight modifications of each other, primarily on the order of conditions, sometimes with additional verifications to avoid certain types of attacks.

Quote
  • Why are there so many HTLCs on LTC and so few on BTC?
LTC block time is much less than BTC's. Since atomic swaps is still an experimental technology, it makes sense to test them on a faster chain, paired with some other altcoin having the comparatively fast block time.

Quote
  • Do you know other such HTLC scripts?
Well, you scanned the whole blockchain, have you found any other type yet?  Smiley

Quote
  • Can you provide interesting resources on this topic?
My advice would be to learn how to read Bitcoin scripts, that way you will be able to understand what they do and how they compare to each other. You can start here: https://en.bitcoin.it/wiki/Script, or you can go deep into the guts of interpreter.cpp, where the actual magic happens.
mr_sparkles
Newbie
*
Offline Offline

Activity: 5
Merit: 0


View Profile
July 22, 2018, 04:54:31 PM
 #7

You might want to look into the privacy angle: i.e. atomic swaps that cannot be linked across chains by anyone other than the parties involved.

This is a good place to start: https://joinmarket.me/blog/blog/the-half-scriptless-swap/
noobWithAComputer
Newbie
*
Offline Offline

Activity: 8
Merit: 18


View Profile
July 23, 2018, 07:54:24 PM
 #8

Thank you all for your thoughts. Especially to Kallisteiros for your long post.

You are right about the swapped parameters in Type 4a/b and 6.

@mr_sparkles
I will look into it. This might be interesting.
noobWithAComputer
Newbie
*
Offline Offline

Activity: 8
Merit: 18


View Profile
September 21, 2018, 10:31:49 AM
Merited by ETFbitcoin (2), Cyrus (1), HeRetiK (1)
 #9

Hi together,

I finished my thesis now and have some results.

I put everything I accomplished in a git repo, so everybody can view my results. At the moment there is only the german thesis, but I will try to translate it within the next days.

I hope my work is usefull to somebody.

Git: https://github.com/noobWithAComputer/detect-atomic-swaps

Greetings.
ETFbitcoin
Legendary
*
Offline Offline

Activity: 1652
Merit: 1767

Use SegWit and enjoy lower fees.


View Profile WWW
September 21, 2018, 11:01:12 AM
Last edit: October 10, 2018, 04:34:19 AM by ETFbitcoin
 #10

Hi together,

I finished my thesis now and have some results.

I put everything I accomplished in a git repo, so everybody can view my results. At the moment there is only the german thesis, but I will try to translate it within the next days.

I hope my work is usefull to somebody.

Git: https://github.com/noobWithAComputer/detect-atomic-swaps

Greetings.

Nice work, even though i barely understand the topic, looking forward for English version. Also, just to be sure, has it been tested or peer reviewed?

You might be interested with Anonymous Atomic Swaps Using Homomorphic Hashing

I'm very sorry, that I was not able to translate it within a few days as I planned... And as it seems atm, it will take a few more weeks, as I have a lot on my table right now...

I hope to get it done this year, but I won't make any promises. Sorry Sad

Don't worry about it, take your time Smiley

noobWithAComputer
Newbie
*
Offline Offline

Activity: 8
Merit: 18


View Profile
September 21, 2018, 11:55:41 AM
 #11

I will start translating it today. Maybe I get it done this weekend. My thesis starts at the very beginning, so I hope even people who are not familiar with atomic swaps can under stand it.

As this is a thesis to a unimportant module in my course of studies, it was not peer reviewed and also not published (besides my personal git repo).

I will take a look at the homomorphic hashing stuff, this seems interesting, thanks.
noobWithAComputer
Newbie
*
Offline Offline

Activity: 8
Merit: 18


View Profile
October 09, 2018, 08:07:07 PM
 #12

I'm very sorry, that I was not able to translate it within a few days as I planned... And as it seems atm, it will take a few more weeks, as I have a lot on my table right now...

I hope to get it done this year, but I won't make any promises. Sorry Sad
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!