|
Title: Atomic swaps using cut and choose Post by: jl777 on February 14, 2016, 10:53:32 PM continuing from https://bitcointalk.org/index.php?topic=1340621.msg13881127#msg13881127 as it seems the OP locked it for some reason...
Code: // Four initial states are BOB_sentoffer, ALICE_gotoffer, ALICE_sentoffer, BOB_gotoffer Quote I haven't gone through it step by step but that is a good way to do it. To avoid insanity I always designate the bitcoin side as Bob and the altcoin side as alice. That way all the directions and scripts are always the same.At any time each party is in a given state right? Why are there 4 start states? Shouldn't it just be that Bob is in one state and Alice is in another? For example, Bob starts in BOB_start and Alice starts in Alice_waiting_for_trade_request, or something similar. If a node receives an offer from another party, then it creates a thread to handle it, like a web-server right? I guess that means that Alice effectively starts at Alice_received_trade_request, or equivalent. Since the waiting_for_trade_request is implicit by listening on the socket. Bob_start causes Bob to send his offer and then transition to Bob_offer_sent. Bob_offer_sent could timeout within 30-60 seconds and cause Bob to transition to Bob_cancel_offer. Alternatively, it Alice accepts the offer, they could transition to the fee and 777 pairs exchange. There is no point in wasting processing if the other party isn't accepting the trade. I guess it depends on how fine grained the state resolution should be. Also, there could be a step where both sides decide who is Alice and who is Bob, since the person who offers the trade may not necessarily be Bob. Implementation wise, yes it is possible to have just one starting state for both sides, however we have the situation that either party can be the first one to place a quote in the orderbook, ie a bid or ask and this creates 4 possible starting states with 2 parties involved. alice starts with bid, alice starts with ask, bob starts with bid, bob starts with ask. notice that alice can be in two of these states at the same time, actually N of them as using the state machine approach each trade that is matched is its own state machine, relatively independent of others (some details like total available balance vs chance that more has been put in the orderbook than funds available, existing trades that are pending) So that is why 4 possible starting states for when there are two sides to a trade. Internally I have two initial states that bifurcates depending on whether it is alice or bob. Also, before an exchange is ready to be put into the state machine, a lot of onetime prep needs to be done and I wanted the state machine to be as pure as possible and not be cluttered with initial setup. James Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 14, 2016, 11:51:02 PM Also, before an exchange is ready to be put into the state machine, a lot of onetime prep needs to be done and I wanted the state machine to be as pure as possible and not be cluttered with initial setup. I notice that you have a single processing function (BOB_processfunc for Bob). You could maybe reduce clutter by having a different handler for each state. That is all implementation details but I realize that is half the battle. The basic description doesn't require details on how to check signatures etc., but it is critical that each step is properly checked. For example, the CPRKV BIP should very clearly define the formatting of the two keys. Someone might be able to break the protocol by using badly encoded keys or something. Title: Re: Atomic swaps using cut and choose Post by: yassin54 on February 15, 2016, 09:58:53 AM continuing from https://bitcointalk.org/index.php?topic=1340621.msg13881127#msg13881127 as it seems the OP locked it for some reason... Thanks!! :)watched again!! ;) Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 15, 2016, 11:27:27 AM Also, before an exchange is ready to be put into the state machine, a lot of onetime prep needs to be done and I wanted the state machine to be as pure as possible and not be cluttered with initial setup. I notice that you have a single processing function (BOB_processfunc for Bob). You could maybe reduce clutter by having a different handler for each state. That is all implementation details but I realize that is half the battle. The basic description doesn't require details on how to check signatures etc., but it is critical that each step is properly checked. For example, the CPRKV BIP should very clearly define the formatting of the two keys. Someone might be able to break the protocol by using badly encoded keys or something. This is where the FSM is much better than English to specify things and is the "implementation details" that is fully in the specification area, especially when one missed error event can mean loss of funds! It isnt so clear, but in the create state function you can specify new state to go to in the event of a timeout (max timeout for bob and half max for Alice?) and a different state if some other error happens, ie some unexpected event (not sure if that should just be ignored) or disconnection. We could specify all the possible types of errors that can happen and have a common error handling. Anyway, here is revised FSM, with all timeout states invoked if we pass half maxtime for Alice or maxtime for Bob. Speaking of time, with the possible +/- 2 hours on the BTC timestamp if the timeout events trigger based on local clock on each node if we need to pad the cltv parameter by 2 hours to prevent race (or worse) conditions. And if we are adding 2 hours, how this affects the claim windows if maxtime is set to be 2 hours. Code: // Four initial states are BOB_sentoffer, ALICE_gotoffer, ALICE_sentoffer, BOB_gotoffer Most process functions should be self explanatory and I made it a linear flow as the protocol proceeds toward completion. I think the following four claim states are what needs to always be atomic and with FSM we would be able to prove that either BTC_cleanup is called by both sides or BOB_claimdepositfunc and ALICE_claimaltfunc unwinds the swap or ALICE_claimbtcfunc and BOB_claimaltfunc completes the atomic swap. James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 15, 2016, 12:40:04 PM Here are the scripts I am using:
both fees are standard payments: OP_DUP OP_HASH160 FEE_RMD160 OP_EQUALVERIFY OP_CHECKSIG Alice altpayment: OP_2 <alice_pubM> <bob_pubN> OP_2 OP_CHECKMULTISIG Bob deposit: OP_IF <now + INSTANTDEX_LOCKTIME*2> OP_CLTV OP_DROP <alice_pubA0> OP_CHECKSIG OP_ELSE OP_HASH160 <hash(bob_privN)> OP_EQUALVERIFY <bob_pubB0> OP_CHECKSIG OP_ENDIF Bob paytx: OP_IF <now + INSTANTDEX_LOCKTIME> OP_CLTV OP_DROP <bob_pubB1> OP_CHECKSIG OP_ELSE OP_HASH160 <hash(alice_privM)> OP_EQUALVERIFY <alice_pubA0> OP_CHECKSIG OP_ENDIF Naming convention are pubAi are alice's pubkeys (seems only pubA0 and not pubA1) pubBi are Bob's pubkeys privN is Bob's privkey from the cut and choose deck as selected by Alice privM is Alice's counterpart pubN and pubM are the corresponding pubkeys for these chosen privkeys Alice timeout event is triggered if INSTANTDEX_LOCKTIME elapses from the start of a FSM instance. Bob timeout event is triggered after INSTANTDEX_LOCKTIME*2 James Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 15, 2016, 02:46:12 PM Here are the scripts I am using: both fees are standard payments: OP_DUP OP_HASH160 FEE_RMD160 OP_EQUALVERIFY OP_CHECKSIG Fees should somehow incorporate the tradeId hash. That way a trader can't use the same fee for multiple trades. This could be incorporated into the public keys by multiplying key pairs by a random number selected by the other party. Bob selects a key pair (fee_pri_bob, fee_pub_bob) and a random number fee_rand_bob. Note: fee_pub_bob = fee_pri_bob * G He sends fee_pub_bob and fee_rand_bob to Alice. Alice computes the same and sends her EC point and random number back. Bob uses the following key pair Adjusted Private = fee_pri_bob * fee_rand_alice Adjusted Public = fee_pri_bob * fee_rand_alice * G = fee_rand_alice * (fee_pri_bob * G) = fee_rand_alice * fee_pub_bob This means that Alice can verify that the public key is unique for this trade (since she can calculate fee_rand_alice * fee_pub_bob), but still doesn't know the matching private key. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 15, 2016, 03:06:10 PM Here are the scripts I am using: both fees are standard payments: OP_DUP OP_HASH160 FEE_RMD160 OP_EQUALVERIFY OP_CHECKSIG Fees should somehow incorporate the tradeId hash. That way a trader can't use the same fee for multiple trades. This could be incorporated into the public keys by multiplying key pairs by a random number selected by the other party. Bob selects a key pair (fee_pri_bob, fee_pub_bob) and a random number fee_rand_bob. Note: fee_pub_bob = fee_pri_bob * G He sends fee_pub_bob and fee_rand_bob to Alice. Alice computes the same and sends her EC point and random number back. Bob uses the following key pair Adjusted Private = fee_pri_bob * fee_rand_alice Adjusted Public = fee_pri_bob * fee_rand_alice * G = fee_rand_alice * (fee_pri_bob * G) = fee_rand_alice * fee_pub_bob This means that Alice can verify that the public key is unique for this trade (since she can calculate fee_rand_alice * fee_pub_bob), but still doesn't know the matching private key. <orderid> OP_DROP OP_DUP OP_HASH160 FEE_RMD160 OP_EQUALVERIFY OP_CHECKSIG The orderid is unique to a specific orderbook entry. This way, once fee is paid for an atomic sequence, if it fails for whatever reason, you can reuse the feetx. If the feetx is locked to a specific Alice/Bob, that would increase the effect of a nuisance attack (just starting trades without intending to complete them) as the fee wont be able to be reused James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 15, 2016, 08:44:12 PM optimized FSM a bit:
Code: s = instantdex_statecreate(s,n,"BTC_cleanup",BTC_cleanupfunc,0,0,0); // from states without any commits Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 16, 2016, 03:40:48 AM I have to add another metaevent to deal with the waiting states, as there is no incoming message to trigger it.
this allows to create states like: Code: s = instantdex_statecreate(s,n,"BOB_waitfee",BOB_waitfeefunc,0,"BTC_cleanup",0); BOB_waitfee will issue poll events to itself in a loop, until "feefound" event is generated (or timeout) James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 16, 2016, 07:12:48 PM latest revision with all the "poll" events
Code: s = instantdex_statecreate(s,n,"BTC_cleanup",BTC_cleanupfunc,0,0,0,0); // from states without any commits I also wrote a bruteforce tester James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 16, 2016, 10:38:12 PM Some benchmarks of just the pure state machine:
BOB_gotoffer BOB_sentprivs BOB_waitfee BOB_waitfee BOB_waitfee BOB_waitfee BOB_waitfee BOB_waitfee BOB_sentdeposit BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_sentpayment BOB_claimedalt reached BTC_cleanup m.20 events most.20 ave 20.00 BOB_sentoffer BOB_sentprivs BOB_waitfee BOB_sentdeposit BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_sentpayment BOB_sentpayment BOB_claimedalt reached BTC_cleanup m.13 events most.34 ave 11.50 BOB_sentoffer BOB_sentprivs BOB_waitfee BOB_sentdeposit BOB_altconfirm BOB_sentpayment BOB_claimedalt reached BTC_cleanup m.8 events most.36 ave 11.50 BOB_gotoffer BOB_sentprivs BOB_waitfee BOB_waitfee BOB_sentdeposit BOB_altconfirm BOB_sentpayment BOB_claimedalt reached BTC_cleanup m.9 events most.36 ave 11.50 ALICE_sentoffer ALICE_sentprivs Alice_waitfee Alice_waitfee Alice_waitfee Alice_waitfee Alice_waitfee ALICE_waitdeposit ALICE_sentalt ALICE_waitconfirms ALICE_waitconfirms ALICE_claimedbtc reached BTC_cleanup m.13 events most.37 ave 11.50 ALICE_sentoffer ALICE_sentprivs Alice_waitfee ALICE_waitdeposit ALICE_waitdeposit ALICE_waitdeposit ALICE_waitdeposit ALICE_waitdeposit ALICE_waitdeposit ALICE_waitdeposit ALICE_sentalt ALICE_waitconfirms ALICE_claimedbtc ALICE_claimedbtc reached BTC_cleanup m.15 events most.37 ave 11.50 BOB_sentoffer BOB_sentprivs BOB_waitfee BOB_sentdeposit BOB_altconfirm BOB_sentpayment BOB_claimedalt reached BTC_cleanup m.8 events most.37 ave 11.50 BOB_gotoffer BOB_sentprivs BOB_waitfee BOB_sentdeposit BOB_altconfirm BOB_sentpayment BOB_claimedalt reached BTC_cleanup m.8 events most.37 ave 11.50 BOB_sentoffer BOB_sentprivs BOB_waitfee BOB_sentdeposit BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_sentpayment BOB_claimedalt BOB_claimedalt reached BTC_cleanup m.12 events most.37 ave 11.50 BOB_sentoffer BOB_sentprivs BOB_waitfee BOB_waitfee BOB_waitfee BOB_waitfee BOB_waitfee BOB_sentdeposit BOB_altconfirm BOB_sentpayment BOB_claimedalt reached BTC_cleanup m.12 events most.37 ave 11.50 most.37 ave 11.50 elapsed 4711.472 ave 0.000471 units are in milliseconds, so less than half a microsecond per FSM simulation. for each one I randomly choose from the starting states and then just use a random number for the next event until it reaches the terminal event (BTC_cleanup); Above is from a run of 10 million iterations that took a bit less than 5 seconds, with printouts of the states for every millionth test. I think it is safe to say that it is fast enough and also that there are no dead ends in the state machine. I didnt do any coverage stats though, so there might be some orphaned states that are never used. For the full test point of doing an atomic swap, I have things debugged now until it fails due to invalid transactions. Which is kind of expected as I havent connected up the unspents info to the atomic swap yet. First step is to just hardcode a few unspents for each side and make sure the FSM actually makes them complete a swap if all is well. Then making the unspents come from internal wallet addresses, etc. It is already connected to the instantdex trading API as the "bitcoin" exchange. The test sequence is to issue the following on one node: curl --url "http://127.0.0.1:7778" --data "{\"agent\":\"iguana\",\"method\":\"addcoin\",\"newcoin\":\"BTC\"}" curl --url "http://127.0.0.1:7778" --data " {\"agent\":\"InstantDEX\",\"method\":\"sell\",\"exchange\":\"bitcoin\",\"base\":\"BTCD\",\"rel\":\"BTC\",\"price\":0.003,\"volume\":2,\"dotrade\":1}" It just activates the coin and then submits a sell offer to the network. Then on the other node: http://127.0.0.1:7778/api/InstantDEX/orderbook?exchange=bitcoin&base=BTCD&rel=BTC&depth=11&allfields=1&ignore= http://127.0.0.1:7778/api/InstantDEX/buy?exchange=bitcoin&base=BTCD&rel=BTC&price=.003&volume=2&dotrade=1&password=bob The first one shows the orderbook (this is optional) and the second one is checked to see if it matches an existing order and if it does, initializes the state machine and sends a message to the other node. FSM is followed by both sides, states change, even "poll" virtual event appeared to work. Been up for quite a while, so not sure when I will be awake next, but it feels like the home stretch. The only "attack" that I know of is that an attacker who doesnt care about losing money to annoy people would also have to actively post offers at the best market price (ie. realtime price quotes) and then start trades, only to never complete them. Each "attack" will cost the attacker 0.13% but the "victim" can still recycle the fee that was used as the fee tx is based on the orderid of the offer being matched. I dont see this as any practical attack as it costs fees and only delays the other nodes that try to do a trade with the attacker and quickly it will get blacklisted. Eventually I can add a historical reputation/percentage completion of started trades as all that info will be on the blockchain, so users can decide what type of nodes they will atomic with. I will change the random deck back to 1000 so the 0.13% fee with have an expected loss of 13% and so will Bob bailing out and losing his deposit. James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 16, 2016, 10:52:22 PM @TierNolan
What do you think about anonymint's idea of having a user settable coin age requirement for the feetx? The idea is to slow down the annoyance attacks. Maybe a specific order of fee payment, ie make the initiator pay the fee first to prevent a proactive attacker from waiting for the other side to pay a fee and bail out. With contingency plan of just issuing refunds for unused fees due to other side disconnecting, and future reputation systems, I dont see this as a big issue, but if there was a technical bullet that just knocks it out completely it would offer a better user experience. So far when it is all debugged, I dont see any way either side can lose funds. The worst seems to be having some of your funds tied of for a few hours (I am thinking setting the max transaction time of 2 to 3 hours, with a max expiration time of around 8 hours. That way even if papercut attacker locks you up for the maxtime, there is still plenty of time to complete the trade with someone else. The two places where blockchain confirmations are needed, I have made it adaptive on the bitcoin side as of smaller tx of 0.1 BTC or less it seems that as soon as it is confirmed that is good enoough and for larger ones 1 + sqrt(BTC value) confirms, so 1 BTC is 2 confirms, 4 BTC is 3 confirms, 9 BTC is 4 confirms, etc. The altcoin side is so variable, I cant think of any better way than having the user specify it on a per coin basis, or even per trade basis. If some wealthy vandal actually starts doing nuisance attacks, I think we can always institute a non-gameable reputation system or even a real insurance system Anyway, first things first. Need to get it doing trades using a simple form as input. James Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 16, 2016, 11:47:10 PM What do you think about anonymint's idea of having a user settable coin age requirement for the feetx? The idea is to slow down the annoyance attacks. That seems reasonable too. You are forcing people to expend a finite resource, so they can't spam. It could be an issue for people who have just obtained coins and then have to wait a few days to build up coinage. Quote Maybe a specific order of fee payment, ie make the initiator pay the fee first to prevent a proactive attacker from waiting for the other side to pay a fee and bail out. I was thinking that it could be a joint transaction, like with CoinJoin. Each side would say where they are getting the coins from and then once the tx is built, they can both sign it. That means that the fee has to be on one of the two coins rather than each paying on their own coin. This means you need to know the exchange rate, but that can be pulled directly from the trade itself. I also like the concept of having the transaction finishing transactions allow recovery of the fees. They could pay the fees to Code: IF and Code: IF This means that after 2 days, anyone can claim the output. If the system becomes popular, that means that miners will take the outputs as fees. Otherwise, someone could just try to be the first to claim them. The _fee_unlock codes would have to be agreed before the cut and choose happens. They would need to be included in the claim transactions. The step 4 output, for example, becomes Code: OP_IF The nice thing about this is that the fee can be made larger, since it is recovered if the trade completes. Quote The two places where blockchain confirmations are needed, I have made it adaptive on the bitcoin side as of smaller tx of 0.1 BTC or less it seems that as soon as it is confirmed that is good enoough and for larger ones 1 + sqrt(BTC value) confirms, so 1 BTC is 2 confirms, 4 BTC is 3 confirms, 9 BTC is 4 confirms, etc. Seems reasonable, but the user should probably be given the option to set a minimum confirm delay. The other party should be informed, so they don't think they are going to complete the trade in 2 mins and end up having to wait 1 hour for confirms. Title: Re: Atomic swaps using cut and choose Post by: marcus_of_augustus on February 17, 2016, 03:32:13 AM watching.
Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 18, 2016, 12:43:20 PM What do you think about anonymint's idea (https://bitcointalk.org/index.php?topic=1319681.msg13647053#msg13647053) of having a user settable coin age requirement for the feetx? The idea is to slow down the annoyance attacks. That seems reasonable too. You are forcing people to expend a finite resource, so they can't spam. It could be an issue for people who have just obtained coins and then have to wait a few days to build up coinage. What I suggested to jl777 in a PM, is that he make it (the coin age, a.k.a. "Coin Days Destroyed") a user-adjustable variable so that users can select the tradeoff between delay for themselves and those counter-parties available to trade with, and depending on the level of jamming present at that time. jl777 referred to it as a "rainy day" insurance, which seems an apt characterization of the suggestion. I have my strong intuitive (generative essence) sense that I will find a flaw in any method of using a fee to block the attacker who wants to jam the protocol, because the fee can't be atomic with the trade (without also opening a jamming window of interaction), so a window of jamming is always opened. Whereas, the coin age is a finite resource which exists (is committed to) prior to the initiation of any protocol for trading. Also it is impossible to use a mixer to hide the identity of the attacker, since mixing will bump the coin age back to 0. Note my suggestion hinges on the first interaction with the counter-party in the protocol must bump the coin age to 0 on the block chain (else only a local blacklist can be maintained which is much less robust defense). Otherwise the attacker can reuse the same resource over and over to jam with. Jamming is the main obstacle I forsee impinging on the viability of TierNolan's decentralized exchange protocol. The next obstacle is the very limited scalability of transaction rate for existing block chains, but that is a holistic problem for crypto right now (meaning it MUST be solved else the crypto currency phenomenon dies). Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 18, 2016, 01:13:31 PM continuing from https://bitcointalk.org/index.php?topic=1340621.msg13881127#msg13881127 as it seems the OP locked it for some reason... The likely reason it was closed is CIYAM got pissed at me (in another thread) (https://bitcointalk.org/index.php?topic=1361602.msg13888054#msg13888054) and decided to have a temper tantrum (perhaps because I was also supposed to be talking to him soon in Skype about decentralized exchange). Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 18, 2016, 02:39:37 PM What I suggested to jl777 in a PM, is that he make it (the coin age, a.k.a. "Coin Days Destroyed") a user-adjustable variable so that users can select the tradeoff between delay for themselves and those counter-parties available to trade with, and depending on the level of jamming present at that time. jl777 referred to it as a "rainy day" insurance, which seems an apt characterization of the suggestion. Right. I suggested something similar. If 99% of trades that are initiated end up completing the cut-and-choose, then the risk is pretty low. If a trader is burned, then it can push up the requirement for a fee. It is a pity that there is no way to commit to a public key. With coinage, you can actually have it consumed with a gossip network. To "spend" the coinage, you can sign a message with the public key of the output. If the person doesn't complete the trade, then you can broadcast the message (or just broadcast it immediately). The message would contain the tradeId for the output and the current time. It could reset the coinage to zero, for a weaker blacklist. Both sides of the trade would lose coinage though. A spammer should lose it faster than a normal user. Quote I have my strong intuitive (generative essence) sense that I will find a flaw in any method of using a fee to block the attacker who wants to jam the protocol, because the fee can't be atomic with the trade You can make it connected with the trade by having the final steps in the protocol release the fee. If the trade doesn't complete both sides lose money. Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 18, 2016, 02:43:34 PM On further thought, I have decided that my suggestion for coin age is useless by itself and I need to add the following to make it work as intended (while coin age remains necessary else the attacker could use a mixer to create new UXTO that escape the decentralized reputation system I will suggest below).
DoS by jamming is the paramount threat to decentralized exchange that needs to be solved first. If this isn't solved, then it isn't worth pursuing because for sure the government will be against exchanges which they can't regulate to enforce KYC, etc (this will become more so in 2017). Governments have unlimited funds to attack with (e.g. $4+ trillion went missing from the DoD budget (https://www.youtube.com/watch?v=xU4GdHLUHwU) and finances the DEEP STATE (http://billmoyers.com/episode/the-deep-state-hiding-in-plain-sight/)). Please don't tell me that Donald Rumsfeld and Bill Moyers aren't mainstream and reliable sources. There is no way to solve the jamming problem by relying on the two block chains that are doing the trade, because someone always has to go first, thus someone will always get jammed. If the honest person never goes first, then no one will go first. Simple logic. The only way I can hope to fix this problem is to have a separate block chain for recording the intention to enter a trade, and with this block chain track those UXTO which are bailing out and thus users can refuse to trade with them. Again this requires the coin age to prevent the attacker from using a mixer to subvert the tracking by UXTO. Also coin age is necessary so someone doesn't get inadvertently blocked forever due to some glitch on their end where they couldn't follow through on the protocol. One way I contemplated is to have both parties sign the intention to trade, then they post it to this block chain. However, one might sign and the other might not, thus jamming the other party (in terms of computing the signature and the communication latency between the two parties). Also worse is that one party might sign more than one intention to trade or inadvertently do so if the attacker didn't sign immediately but later signed and published it to this block chain. Thus the first requirement is we need a way for both to sign where the signature isn't valid if they both didn't complete the signing protocol. I am not sure if this can be accomplished. I would need to think about some variant of Shamir's How to Share a Secret (http://cs.jhu.edu/~sdoshi/crypto/papers/shamirturing.pdf) crossed with "simultaneous contract signing". Something like a Diffie-Hellman exchange (but that is sharing a symmetric key) where either party can then sign on behalf of both parties proving that the Diffie-Helman exchange occurred. If the prior paragraph can be achieved, then the jamming that remains is only on latency of the protocol in the prior paragraph, yet this is still a jamming problem. There is no way for the user who is being jammed to share his UXTO blacklist with other users since the attacker could Sybil attack such sharing. So thus I conclude that decentralized exchange is probably not going to work unless there is some reputation system. But then when I consider reputation system designs, they can also be Sybil attacked. It seems the only possible solution would be a Web of Trust similar to PGP wherein I decide to trust those who trust me and vice versa. But the problem with Web of Trust in this context is the attacker can Sybil attack it by first gaining trust, then violating trust thus causing the Web of Trust to be unstable. Sigh. :'( If anyone can think of a solution at the conceptual level (never mind what block chains currently offer), I would love to read it. So far decentralized exchange looks to be jammable in every design I've contemplated. I have my strong intuitive (generative essence) sense that I will find a flaw in any method of using a fee to block the attacker who wants to jam the protocol, because the fee can't be atomic with the trade You can make it connected with the trade by having the final steps in the protocol release the fee. If the trade doesn't complete both sides lose money. But my point is the jamming will come before that connection has been established. Also if both sides lose money when one side bails, then the attacker can cause the innocent party to go bankrupt. You are ostensibly dismissing the case of the attacker who can charge the cost of the attack to collective. Right at this moment, China's mining cartel controls an estimated 65% of Bitcoin's hashrate and they have vetoed every block size increase (even Classic's reasonable doubling to 2MB), and they apparently have very low electricity costs so it isn't unthinkable that with a "wink and a handshake" this electricity is coming for free from Three Gorges Dam. The fact that I have proven they must have lied about the bandwidth problem (since of course they could put a pool abroad and just relay the hashes across the Great Firewall of China). One motivation could possibly be to force transaction fees higher and reap more profits. So there is already circumstantial evidence that the attack scenario I am worried about is not impossible. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 18, 2016, 06:35:14 PM An attacker with infinite resources that doesnt care about monetary losses...
I claim that such an attacker can bring any network to a standstill. So defending against this is not a high priority in the beginning. I like the simple approach where the fee (insurance) is prepaid before each trade. The fee is tagged with the orderid of the recipient of the offer, not the initiator of the trade. This means that a papercut attack cannot be done proactively, but only if somebody else initiates a trade with the attacker. So, that means a reputation system will be effective as trading with newbie accounts will carry some small risk that they are a papercut attacker who set a trap. By linking the fee to the orderid of the one that posted the bid/ask, that means the papercut attack only delays as the fee that was paid is still valid for completing the atomic swap with a real peer. The attacker cant reuse the fee paid, so this is assymetric in a good way. Granted the victim will be out a fee if their bid expires without the trade being completed. We are talking about 0.13% in the event of an attack, so most of the time not even worth going through a claim process. But maybe an active trader over time will accumulate a bunch of such failed fees, and I think if there was some sort of automated claim process for this, it solves the practical issues of this theoretical problem. Before you start complaining that requires trust that this process will be honored, my response is that if this attack scenario remains hypothetical, then it is not an issue. If it does happen and the fees paid for failed swaps are not refunded, then that will damage the reputation of InstantDEX and so there is strong incentive to keep the customer's happy. Keep in mind it is the 0.13% fees that are lost due to an attacker that doesnt care about losing money and just wants to jam things. Typically non-economically viable attacks are not a big priority to solve. But I dont want there to be any obstacles to using InstantDEX, so I will commit to refund the fees paid for atomic swaps that dont complete, as long as the txfees needed to send out the refunds are less than 10% of the refund. As opposed to having 100% of your capital at risk when you use centralized exchanges. James Title: Re: Atomic swaps using cut and choose Post by: hv_ on February 18, 2016, 09:42:01 PM Pardon. Reading the header with SWAP and then parsing the story I finally understand you try to achieve just an "easy" crypto ccy SPOT trade (Even more correct a same day forward) by executing one of the "easiest" smart contract and already struggle with that?
Why not trying some betting stuff? (Sorry, just caspering around a bit ;D) I really want to know and see such easy stuff working before more complex things should be developed, savely.... How about some 2factor like mechano? Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 18, 2016, 09:54:03 PM Pardon. Reading the header with SWAP and then parsing the story I finally understand you try to achieve just an "easy" crypto ccy SPOT trade (Even more correct a same day forward) by executing one of the "easiest" smart contract and already struggle with that? The reason it isnt easy is that there are two independent blockchains. Why not trying some betting stuff? (Sorry, just caspering around a bit ;D) I really want to know and see such easy stuff working before more complex things should be developed, savely.... How about some 2factor like mechano? If using just one blockchain, things become much easier James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 19, 2016, 12:53:08 AM An attacker with infinite resources that doesnt care about monetary losses... I claim that such an attacker can bring any network to a standstill. So defending against this is not a high priority in the beginning. But this is not a symmetric analogy. An attacker may only want to (discretely) jam decentralized exchanges, not (boisterously) bring the entire internet crashing down. I like the simple approach where the fee (insurance) is prepaid before each trade. The fee is tagged with the orderid of the recipient of the offer, not the initiator of the trade. This means that a papercut attack cannot be done proactively, but only if somebody else initiates a trade with the attacker. So, that means a reputation system will be effective as trading with newbie accounts will carry some small risk that they are a papercut attacker who set a trap. By linking the fee to the orderid of the one that posted the bid/ask, that means the papercut attack only delays as the fee that was paid is still valid for completing the atomic swap with a real peer. The attacker cant reuse the fee paid, so this is assymetric in a good way. Granted the victim will be out a fee if their bid expires without the trade being completed. We are talking about 0.13% in the event of an attack, so most of the time not even worth going through a claim process. But maybe an active trader over time will accumulate a bunch of such failed fees, and I think if there was some sort of automated claim process for this, it solves the practical issues of this theoretical problem. Before you start complaining that requires trust that this process will be honored, my response is that if this attack scenario remains hypothetical, then it is not an issue. If it does happen and the fees paid for failed swaps are not refunded, then that will damage the reputation of InstantDEX and so there is strong incentive to keep the customer's happy. Keep in mind it is the 0.13% fees that are lost due to an attacker that doesnt care about losing money and just wants to jam things. Typically non-economically viable attacks are not a big priority to solve. But I dont want there to be any obstacles to using InstantDEX, so I will commit to refund the fees paid for atomic swaps that dont complete, as long as the txfees needed to send out the refunds are less than 10% of the refund. As opposed to having 100% of your capital at risk when you use centralized exchanges. James Sounds like InstantDEX would have an incentive to attack the victim since victim won't bother to apply for 0.13% refund, so victim will try again and thus pay 0.26% fees. If you refund, then attacker has no cost of jamming, or do you have a way to identify which party was the attacker? How can you differentiate a glitch/slowness in the network from a true jamming attack. What if the attacker DDoS attacks the victim and victim can complete the protocol. An attacker can build reputation before attacking, by trading with himself, i.e. reputation can be Sybil attacked. Sorry I have thought deeply and there is no solution for decentralized exchange. Although I love it ideologically and I was very positive on you doing it, I unfortunately have to conclude that is not viable and should be abandoned. I am trying to help you not waste time on deadends. I invested my effort precisely because I wanted to help you. Title: Re: Atomic swaps using cut and choose Post by: bitcoin-esperanto on February 19, 2016, 01:37:20 AM continuing from https://bitcointalk.org/index.php?topic=1340621.msg13881127#msg13881127 as it seems the OP locked it for some reason... Thanks!! :)watched again!! ;) wow it's really hard for a newbie :o Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 19, 2016, 01:45:51 AM But this is not symmetric analogy. An attacker may only want to (discretely) jam decentralized exchanges, not (boisterously) bring the entire internet crashing down. Quote Sounds like InstantDEX would have an incentive to attack the victim since victim won't bother to apply for 0.13% refund, so victim will try again and thus pay 0.26% fees. why would InstantDEX want to attack its own users? That seems quite counterproductive. The volumes of an attackfree DE is much more than double one plagued by attacks. Due to the nature of the internet, over time there will be failed transactions, so eventually the users will recoup the fees. There is no permanent gain of fees from failed trades, so it is a liability on the books. There is no gain for InstantDEX to abuse its own customers. Quote If you refund, then attacker has no cost of jamming, or do you have a way to identify which party was the attacker? How can you differentiate a glitch/slowness in the network from a true jamming attack. What is the attacker DDoS attacks the victim and victim can complete the protocol. Once things are automated, probably just allow for automated refunds, it is all pretty much at dust levels so the only concern is the customer support time. With an automated system, it wont be any big burden. The attacker would be the one who is responding to a match offer, so if an address has 1000 failed trades out of 2000, it wouldn be easy to notice that. Worst case, even if the attacker doesnt lose money, they dont gain anything. Quote An attacker can build reputation before attacking, by trading with himself, i.e. reputation can be Sybil attacked. I have a reputation system that cannot be sybil attacked, trading with yourself wont do any good. And before you say its not possible, let me say that it is, at least one that will be very expensive for the attacker and that is what it is all about, making the attacks cost more than the expected return. Quote Sorry I have thought deeply and there is no solution for decentralized exchange. Although I love it ideologically and I was very positive on you doing it, I unfortunately have to conclude that is not viable and should be abandoned. I am trying to help you not waste time on deadends. I invested my effort precisely because I wanted to help you. Sorry, you are wrong. Maybe it will be the first time this happens? I believe that it is quite difficult to prove a negative, in spite of your claims. While I just need to make it work, and since I have quite a lot of techniques at my disposal, I am very optimistic I will get it to work.You have no economically viable attack. Just because something is possible, that doesnt mean it is certain to happen, especially when it is economically non-viable. In crypto, the math protects us, so as long as the math yields a negative expected return, it wont attract the money motivated attackers. And if idealogical attackers conduct a permanent attack, I will just have to resort to adding highly leveraged and encrypted comms to make it very cost prohibitive to conduct any large scale attack. It would be a pain to do, but if needed, the DE can be conducted via zero knowledge networking. I really dont think we can dismiss a project before the real world performance is established. If the failure rate is 90%, of course it wont be used. If the failure rate is 0.1%, then I dont think that will be a large deterrent. The question is what will the real world failure rate be. I claim that NOBODY is able to predict this ahead of time. I prefer to get a real world results before making any decisions based on theory. Until there is some significant volume being traded, it seems nonsensical for it to be attacked like that. And by the time there is a significant volume being traded, the more advanced defenses will be ready. In order for it to fail, either InstantDEX itself would have to attack its own users or there needs to be an attacker from day one who doesnt care about costs, interfering with every single trade AND that I wont be able to devise defenses against this. Defenses can be via reputation system, insurance system, refund system, technically leveraged protections, among others. And all will have to fail with a constant and permanent attacker always interfering with significant numbers of trades. You really believe this is 100% certain to happen? James Title: Re: Atomic swaps using cut and choose Post by: hv_ on February 19, 2016, 07:46:40 AM I'd say it is same issue with Casper:
Decentral: You need a trustless clrearing system / notary in between - some say that 'could work' with some betting design.... Central: Easy but open to hackers. Think of the actual process in trading as is: - Client (has ccy1) & wants to change it to ccy2 - Client needs to deposit (maybe partial) ccy1 first at market maker's account (market maker that could offer ccy2 vs ccy1) - Market maker activates client to trade since now there is a credit limit = reduced counter party risk to market maker - Client hits market maker (pays a fee for that service incl settlemet cost) - Market maker might send real time confirmation notice to client (last chance to cancel?) - Settlement is initiated by market maker (or escrow service) - atomic How can you put some code around all that in a decentral way ? Title: Re: Atomic swaps using cut and choose Post by: hv_ on February 19, 2016, 09:14:37 AM I'm not sure if that helps (if anything does at all) at all but I read that part here with the ..interactively verifying the presence of data in a foreign blockchain ...
"The Power of Binary Search In the next two sections, I will give two specific examples. One is about interactively verifying the presence of data in a foreign blockchain, the second is about verifying general (deterministic) computation...." in https://blog.ethereum.org/2016/02/17/smart-contracts-courts-not-smart-judges/ Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 19, 2016, 11:31:48 AM I'm not sure if that helps (if anything does at all) at all but I read that part here with the ..interactively verifying the presence of data in a foreign blockchain ... It is not easy to be monitoring multiple chains at once as not only are there the data sync issues, but also just the logistics of running N daemons."The Power of Binary Search In the next two sections, I will give two specific examples. One is about interactively verifying the presence of data in a foreign blockchain, the second is about verifying general (deterministic) computation...." in https://blog.ethereum.org/2016/02/17/smart-contracts-courts-not-smart-judges/ That is why I am developing iguana, a single lightweight multicoin daemon/applications all rolled into a single unified codebase. That just happens to be able to be cross compiled into a chrome app as it has virtually no external dependencies James P.S. I am getting BTC sync times from scratch of about half hour Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 19, 2016, 03:52:57 PM An attacker with infinite resources that doesnt care about monetary losses... I claim that such an attacker can bring any network to a standstill. So defending against this is not a high priority in the beginning. I was very sleepy when I wrote my prior post. I understand your point. You want to design a protocol that is at least immune to jamming against any attacker other than one that has super powers. Yet the attacker with even meager resources could cause honest participants to lose fees and so they might get turned off from the system. For example, centralized exchanges may have this incentive. Or specific coins might have this incentive to jam DE on other coins (especially those who hadn't yet been listed on a major exchange). So you proposed to refund fees to those honest participants. You admitted that users might not be prone to apply for a refund since 0.13% is so small. And I pointed out the DE would maybe have a financial incentive (while appearing to be the good guys) to jam each honest participant say 50% of the time, to increase fees to 0.26%. I am trying to think of a way to make this practical and robust enough, unless we are facing a prolonged attack from a super power. I like the ideological intent of DE. I will now review your latest reply with a clearer mind. Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 19, 2016, 04:04:55 PM Another potential solution is pegged assets on the same block chain, for those coins you want to trade with:
TPTB, have you contemplated the only immutable DEX in the top 10? Is that trading BTC on the Bitcoin block chain with BTS on the BitShares block chain? Or rather is it trading BitBTC pegged asset on the BitShares block chain (which afaics would avoid the jamming issue)? If the latter, then it is isn't decentralized cross-chain exchange, which is what I was referring to. Afaics, that seems to avoid the jamming issue. Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 19, 2016, 04:29:49 PM Afaics, that seems to avoid the jamming issue. I wonder if this would be a reasonable refund policy. Both parties generate 1000 key_pairs = (private keys, hash(private keys)) Both parties exchange hash(1000 key pairs). The fee transaction contains hash(alice_key_pair_hash | bob_key_pair_hash). This is included in the fee transaction somehow. To claim the fee refund, the person has to submit the 1000 key pairs and [other_party]_key_pair_hash. That allows you verify that they had actually generated 100% valid pairs. Someone who tries to attack the cut-and-choose cannot reclaim their fee. They have to trust you to do that though, but that is probably ok, since it is just the fee. Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 19, 2016, 05:06:15 PM They have to trust you to do that though, but that is probably ok, since it is just the fee. Then the centralized KYC pressure point is on the fee provider. So long-term this doesn't prevent KYC being forced (which one might argue is good, so government won't be against). Although one might envision many fee providers appearing over time (which can't drive fees too low because that would encourage jamming). It does apparently solve the problem of centralized exchanges running fractional reserves and failing. I am not sure if there is not a jamming attack in the protocol to establish the fee transactions? The pegged assets alternative I offered in the prior post would probably still benefit from this "DE" design for exchanging the BitBTC to BTC. Note that centralized exchange isn't the only alternative, as for example a BitUSD could be converted potentially on the street. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 19, 2016, 05:30:13 PM Afaics, that seems to avoid the jamming issue. I wonder if this would be a reasonable refund policy. Both parties generate 1000 key_pairs = (private keys, hash(private keys)) Both parties exchange hash(1000 key pairs). The fee transaction contains hash(alice_key_pair_hash | bob_key_pair_hash). This is included in the fee transaction somehow. To claim the fee refund, the person has to submit the 1000 key pairs and [other_party]_key_pair_hash. That allows you verify that they had actually generated 100% valid pairs. Someone who tries to attack the cut-and-choose cannot reclaim their fee. They have to trust you to do that though, but that is probably ok, since it is just the fee. What is the limit on script size? Maybe there is a way to make a redeem script that requires all the keypairs? OP_IF <now + INSTANTDEX_LOCKTIME*4 + 2hrs> OP_CLTV OP_DROP <TierNolan magic script> <alice_pubA0> OP_CHECKSIG OP_ELSE OP_IF <now + INSTANTDEX_LOCKTIME*4 + 2hrs> OP_CLTV OP_DROP <TierNolan magic script> <bob_pubA0> OP_CHECKSIG OP_ELSE OP_HASH160 <hash(bob_privN)> OP_EQUALVERIFY OP_HASH160 <hash(alice_privM)> OP_EQUALVERIFY <INSTANTDEX_PUBKEY> OP_CHECKSIG OP_ENDIF OP_ENDIF The idea of the above is that if the trade has completed, then both privN and privM are available for the InstantDEX server to claim the fee. For those who scream about needing a centralized server, in the event of downtime, all that happens is a delay in fee spend. In the event of a failed atomic swap the peers who are trading can reclaim the fee after twice the normal maxtime, I also added 2hrs to deal with the clock drift. Could we just use the redeem using secret rmd160 of the merkel root of all the cut and choose? Not sure how the papercut attacker wouldnt be able to claim the refund. If so it would be a trustless automatable refund process that only the victim can use. I think even if the attacker can also reclaim the fees, that is lesser of the two evils as compared to the victim not being able to collect the fees. It sounds like there is a way for the one who attacked cant claim though? James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 19, 2016, 05:36:15 PM Sorry I have thought deeply and there is no solution for decentralized exchange. Although I love it ideologically and I was very positive on you doing it, I unfortunately have to conclude that is not viable and should be abandoned. I am trying to help you not waste time on deadends. I invested my effort precisely because I wanted to help you. Sorry, you are wrong. Maybe it will be the first time this happens? I believe that it is quite difficult to prove a negative, in spite of your claims. While I just need to make it work, and since I have quite a lot of techniques at my disposal, I am very optimistic I will get it to work. I wrote that because I see an inviolable generative essence that there is no reference point. Both parties to the exchange trade are equal in status without a trusted third party. You can see this has been proven by academics for any "simultaneous contract signing". I had seen a PPT with references to the literature and can't find it now, but for example here is another paper: Quote from: http://www.computing.surrey.ac.uk/personal/st/J.Heather/research/papers/ContractSigning.pdf I’m Not Signing That! James Heather and Daniel Hill 1 Introduction Often it is desirable to have a procedure to allow two parties to sign a contract simultaneously. The obvious danger of having one party sign before the other is that the second party may refuse to sign until it becomes to his advantage to do so. For instance, suppose the contract is for Alice to buy 1,000 shares in Fudge Labs, Inc., from Bob, at £1 per share, in a year’s time. If Alice signs first, Bob may then delay signing until the end of the year. If the price has fallen, he will sign, the contract will be binding on both parties, and he will make a profit; if the price has risen, he will not sign. A similar problem will arise if Bob signs first. Because the market changes over time, anything that allows one party the option of delaying the decision on whether to commit will cause problems. Simultaneity in message transmission is, in most practical situations, im- possible to achieve, making cryptographic contract-signing protocols difficult to realize. A trusted third party can be employed to receive the two signatures and then distribute them, but it is clearly advantageous to construct a protocol that does not require action on the part of a third party unless there is suspicion of foul play by one of the parties involved in the contract. In this paper, we examine a cryptographic contract-signing protocol that aims to solve these problems by making the probability that one party can abuse the protocol arbitrarily small. We demonstrate that the protocol has a curious weakness: two rational agents whose rationality is common knowledge will refuse to run the protocol at all. Or this paper (which you may want to read as it talks about probabilistic solutions): Quote from: Kremer, S., Raskin, J.F.: Game Analysis of Abuse-free Contract Signing In 1980, Even and Jacobi [8] showed no deterministic contract signing protocol exists, without participation of a trusted third party (TTP). You have no economically viable attack. Only of we ignore externalities (external economic motivation). The same applies to the erroneous claim (https://bitcointalk.org/index.php?topic=1319681.msg13488432#msg13488432) that proof-of-stake is as secure as proof-of-work. Just because something is possible, that doesnt mean it is certain to happen, especially when it is economically non-viable. As non-viable as Nxt being controlled by a dictator and Bitshares being controlled by two centralized exchanges. The question is what will the real world failure rate be. I claim that NOBODY is able to predict this ahead of time. IMHO, we should endeavor to analyze that before expending great effort on implementation. Btw, I am not belittling the toolset you've developed, our shared ideological motivation, etc.. Just trying to be level-headed and rational. My point was that purely DE will not work. You and TierNolan are apparently proposing a slightly centralized design with a trusted third party. It is well known in literature that TTP and/or probabilistic protocol is necessary. Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 19, 2016, 05:52:12 PM These are the same 1000 key pairs used for the cut and choose right? Yes. Both parties commit to the hash before the choose part of the cut and choose. You actually just need to commit to the public keys. The fee transaction would contain hash(hash(alice's public keys) | hash(bob's public keys)). Quote What is the limit on script size? Maybe there is a way to make a redeem script that requires all the keypairs? 520 bytes for P2SH outputs. That is technically the scriptPubKey. The redeem script can be longer, I think. The problem is that you need to check that the private key matches the public key. That can't be done with script. Quote The idea of the above is that if the trade has completed, then both privN and privM are available for the InstantDEX server to claim the fee. For those who scream about needing a centralized server, in the event of downtime, all that happens is a delay in fee spend. Automatic refund of the fee on trade completion is definitely possible. I don't think you can get automatic refund from the 1000 key commitment though. That would justify some of the fee going to the author, since he provides a service (other than coding). Quote Not sure how the papercut attacker wouldnt be able to claim the refund. The attacker can only claim the refund if the attacker creates a valid set of 1000 key pairs. At least it protects from attackers trying to do cut and choose with one invalid pair. If the (potential) attackers follows each of these strategies - 1000 valid pairs committed -- can reclaim most of the fee - 999 valid, 1 invalid pairs committed -- 0.1% chance of successful fraud -- 99.9% chance of losing the entire fee Note: in the 2nd case, the party that was attacked can reclaim their share of the fee As long as fee * 0.99 is greater than (trade value) * 0.001, then it is not worth attacking. That means that fee > trade_value / 990. Both parties lose the bitcoin tx minimum fee and also the refund service/author's fee Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 19, 2016, 05:57:13 PM Here is a simple solution to the fees:
Alice fee: OP_IF <now + INSTANTDEX_LOCKTIME*4 + 2hrs> OP_CLTV OP_DROP <alice_pubA0> OP_CHECKSIG OP_ELSE OP_HASH160 <hash(bob_privN)> OP_EQUALVERIFY OP_HASH160 <hash(alice_privM)> OP_EQUALVERIFY <INSTANTDEX_PUBKEY> OP_CHECKSIG OP_ENDIF Bob fee: OP_IF <now + INSTANTDEX_LOCKTIME*4 + 2hrs> OP_CLTV OP_DROP <bob_pubA0> OP_CHECKSIG OP_ELSE OP_HASH160 <hash(bob_privN)> OP_EQUALVERIFY OP_HASH160 <hash(alice_privM)> OP_EQUALVERIFY <INSTANTDEX_PUBKEY> OP_CHECKSIG OP_ENDIF If the trade completes, InstantDEX server has 2*INSTANTDEX_LOCKTIME to spend the fee (maybe this could be changed to 24hrs minimum) If the trade doesnt complete, the Bob can reclaim his fee and Alice can reclaim her fee at leisure. However, I remember a few cases were maybe both secrets are divulged even though the trade hasnt been completed, but those were cases the trade failed anyway. No complicated logic, just a time window where fees for completed trades can be collected and if not the one that sent the fee can reclaim it. A nice improvement would be if the attacker wouldnt be able to claim it, but even without that this negates the papercut effect and just becomes an annoyance attack and the attacker has no economic gain from this. James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 19, 2016, 06:17:35 PM Please note I added this to my prior post. I will delete this post after you've read it. I think the blockchain acts as the trusted third party here, especially with the interlocks where each side waits for confirmations.My point was that purely DE will not work. You and TierNolan are apparently proposing a slightly centralized design with a trusted third party. It is well known in literature that TTP and/or probabilistic protocol is necessary. the latest fee scripts are not centralized in any way, though if the InstantDEX doesnt spend the fees that it gets, then the deterrent effect of the fees are gone, so there is arguably a slight centralization to make the disincentives work. However, no central party is needed in the mainstream case of the trades completed. No central party is needed in case the trade doesnt complete (as both parties redeem the fee). Sure looks like a good practical first version approach James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 19, 2016, 06:34:38 PM These are the same 1000 key pairs used for the cut and choose right? Yes. Both parties commit to the hash before the choose part of the cut and choose. You actually just need to commit to the public keys. The fee transaction would contain hash(hash(alice's public keys) | hash(bob's public keys)). Quote What is the limit on script size? Maybe there is a way to make a redeem script that requires all the keypairs? 520 bytes for P2SH outputs. That is technically the scriptPubKey. The redeem script can be longer, I think. The problem is that you need to check that the private key matches the public key. That can't be done with script. Quote The idea of the above is that if the trade has completed, then both privN and privM are available for the InstantDEX server to claim the fee. For those who scream about needing a centralized server, in the event of downtime, all that happens is a delay in fee spend. Automatic refund of the fee on trade completion is definitely possible. I don't think you can get automatic refund from the 1000 key commitment though. That would justify some of the fee going to the author, since he provides a service (other than coding). Quote Not sure how the papercut attacker wouldnt be able to claim the refund. The attacker can only claim the refund if the attacker creates a valid set of 1000 key pairs. At least it protects from attackers trying to do cut and choose with one invalid pair. If the (potential) attackers follows each of these strategies - 1000 valid pairs committed -- can reclaim most of the fee - 999 valid, 1 invalid pairs committed -- 0.1% chance of successful fraud -- 99.9% chance of losing the entire fee Note: in the 2nd case, the party that was attacked can reclaim their share of the fee As long as fee * 0.99 is greater than (trade value) * 0.001, then it is not worth attacking. That means that fee > trade_value / 990. Both parties lose the bitcoin tx minimum fee and also the refund service/author's fee Each side can commit to the field product of all the priv keys (https://bitcointalk.org/index.php?topic=1357845.msg13919273#msg13919273), ie. use the method in the link to get a combined product (100ns per fmul op), so 1000 multiplies will take 100 microseconds. then a hash of this is put into the feetx as data (push drop). Each side also includes in the paymenttx the field product of all but one privkeys (which they both have before any big money is exchanged). On redeem, the protocol would be to include the missing privkey as data so it can be verified that the hash(privkey multiplied by the all but one field product) matches the data in the feetx. This allows a reputation system to track how many trades were started by each address, how many failed, how many were properly redeemed, how many were improperly redeemed. sybil attacking accts will all have very low completed trades, so users just need to beware of newbie accts. James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 19, 2016, 08:05:34 PM @TierNolan
Did I read this right: https://bitcointalk.org/index.php?topic=1331275.msg13941835#msg13941835 RBF is opted into if sequenceid is used? Doesnt that mean using CLTV or CSV or microchannels that use sequenceid is forced to accept RBF? If so, doesnt that break the entire premise for atomic tx James Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 19, 2016, 08:49:33 PM RBF is opted into if sequenceid is used? Doesnt that mean using CLTV or CSV or microchannels that use sequenceid is forced to accept RBF? If so, doesnt that break the entire premise for atomic tx The rules are sequence = 0xFFFFFFFF means final (ignore locktime) and no replace by fee sequence = 0xFFFFFFFE means non-final (can use locktime) but opts out of replace by fee sequence = 0x80000000 - 0xFFFFFFFD means opt-in to replace by fee sequence = 0x00000000 - 0x7FFFFFFF is intended for use with relative locktime (plus probably RBF) Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 19, 2016, 09:05:47 PM RBF is opted into if sequenceid is used? Doesnt that mean using CLTV or CSV or microchannels that use sequenceid is forced to accept RBF? If so, doesnt that break the entire premise for atomic tx The rules are sequence = 0xFFFFFFFF means final (ignore locktime) and no replace by fee sequence = 0xFFFFFFFE means non-final (can use locktime) but opts out of replace by fee sequence = 0x80000000 - 0xFFFFFFFD means opt-in to replace by fee sequence = 0x00000000 - 0x7FFFFFFF is intended for use with relative locktime (plus probably RBF) That seems to break 90%+ of whatever uses sequenceid (assuming you dont like the RBF behavior), like CSV. Not sure but it might break SIGHASH_SINGLE signed tx, and possibly some or all coinshuffle protocols as the presence in any input affects the entire tx Hopefully you can influence the right people to dramatically scale down the RBF's hogging of 31.99 of the 32 bits. Just give it the LSB if it is just a flag? James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 19, 2016, 09:32:27 PM Creating custom bitcoin tx and signing them from scratch took a while to debug, but finally the protocol is generating:
I set the fee in BTCD for now: Bob feetx: Code: {Alice feetx: Code: {For now I am just using local bitcoind/BitcoinDarkd to isolate the atomic logic with known working daemons. Then I can switch to using iguana any bugs will be isolated to the new iguana code. Once that is done, then there wont be a need to run multiple daemons, but since the atomic swap can work with any pair of the local daemons, I think i will have an earlier release that assumes local daemons. Much pain the debugging is, but making steady progress. I did see the deposit and payment tx get created, but without the "poll" event things get stuck waiting, so I need to switch to proper event generation in a way that will be compatible with both iguana and bitcoind Once that is done, assuming the state machine is correct, it should be a matter to verify the refund handling. I will assume that my post above with the double secret fee release to InstantDEX and cltv reclaim of fee by Alice/Bob is adequate. It does require changing where the feetx is generated (after both sides choose) but before even the deposit is committed to. James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 19, 2016, 09:37:43 PM It seems what ever design you contemplate employing a fee can always be gamed by an attacker so that he pays no cost.
The attacker can make his own DE and receive the fees. So then he attacks the other DEs (which are honest) 100% of the time but doesn't attack his own DE (or attacks he own less frequently) thus all users migrate to his DE. Thus he is losing much less in attack fees than he is gaining from fees. Since more than one attacker can do this to each other, no one will use DE. P.S. I knew that there would be a leak in fees that would maintain my conclusion that DE is fundamentally impossible. Sorry when I come to these sort of generative essence conclusions they stick. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 19, 2016, 10:06:25 PM It seems what ever design you contemplate employing a fee can always be gamed by an attacker so that he pays no cost. By this logic no cryptocoin would exist. The attacker can make his own DE and receive the fees. So then he attacks the other DEs (which are honest) 100% of the time but doesn't attack his own DE (or attacks he own less frequently) thus all users migrate to his DE. Thus he is losing much less in attack fees than he is gaining from fees. Since more than one attacker can do this to each other, no one will use DE. P.S. I knew that there would be a leak in fees that would maintain my conclusion that DE is fundamentally impossible. Sorry when I come to these sort of generative essence conclusions they stick. Instead of all out war all the time, maybe some sort of truce would be made? Why would everyone running a DE want to spend all that time attacking the other DE's just to get attacked back and then nobody's works. Seems like MAD. I notice your attack scenarios are getting more and more convoluted as now the attacker needs to run a DE themselves to make it even a potential issue. So things are improving. It also might be possible to make it so the attacker wont be able to get their fee back, but no script for that yet. However, you must have missed my post where it is possible to identify the attacker. It would be after the fact, but that allows a reputation system to be created and as long as people are careful about filling orders from newbies, there wont be much problems. James P.S. Using your logic, no central exchange would exist as they would all be Ddosing each other all the time. You dont need to pay exchange fees to Ddos an website. Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 19, 2016, 10:36:47 PM It seems much much worse. RBF is enabled if any input has any value other than -1 or -2 That seems to break 90%+ of whatever uses sequenceid (assuming you dont like the RBF behavior), like CSV. If the MSB is set to zero, then it switches to relative locktime (i.e. check sequence verify). However, I am not sure if RBF is enabled in that case. As I understand it, the RBF opt-in is only applied to the inputs in question. If any of the inputs opt-out, then the transaction has opted out and is locked once it enters the memory pool. I am not sure how it interacts with SIGHASH_SINGLE. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 20, 2016, 10:07:58 AM getting back on track for the atomic swap. With the change in fee handling, I had to add some states and I realized I had a few missing. Working backwards from all the terminal states, I think we have:
Code: // if all goes well both alice and bob get to claim the other's payments The BTC_cleanup state is the ultimate destination for all statemachines and it takes care of cleaning up memory, removing from active queues, adding to trade history, etc. Basically, if all goes well we just have both alice and bob making their corresponding claims and the FSM leading into those states seems pretty complete. All the above are states after the corresponding tx has been claimed, these tx are side effects automatically invoked at the appropriate state transitions. Maybe it is a good idea to have a way to table drive those too, but I think there is very little leeway as to when any tx can be done. The error states look like Bob reclaims deposit and fee (not sure if there is another possible path?) and Alice has two (reclaim altpayment and fee) or (claim deposit and fee) Hopefully I didnt miss any terminal states and once all these are set, then finalizing the events that transition into these states will finalize the FSM to handle all possible error paths. James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 20, 2016, 12:07:38 PM It seems what ever design you contemplate employing a fee can always be gamed by an attacker so that he pays no cost. The attacker can make his own DE and receive the fees. So then he attacks the other DEs (which are honest) 100% of the time but doesn't attack his own DE (or attacks he own less frequently) thus all users migrate to his DE. Thus he is losing much less in attack fees than he is gaining from fees. Since more than one attacker can do this to each other, no one will use DE. P.S. I knew that there would be a leak in fees that would maintain my conclusion that DE is fundamentally impossible. Sorry when I come to these sort of generative essence conclusions they stick. By this logic no cryptocoin would exist. Instead of all out war all the time, maybe some sort of truce would be made? Why would everyone running a DE want to spend all that time attacking the other DE's just to get attacked back and then nobody's works. Seems like MAD. I notice your attack scenarios are getting more and more convoluted as now the attacker needs to run a DE themselves to make it even a potential issue. So things are improving. It also might be possible to make it so the attacker wont be able to get their fee back, but no script for that yet. However, you must have missed my post where it is possible to identify the attacker. It would be after the fact, but that allows a reputation system to be created and as long as people are careful about filling orders from newbies, there wont be much problems. James P.S. Using your logic, no central exchange would exist as they would all be Ddosing each other all the time. You dont need to pay exchange fees to Ddos an website. DDoS is not an analogy to jamming. Remember the party that goes first in your protocol locks up his funds (e.g. UXTO) for the period of the timeout refund (which is orders-of-magnitude greater delay than processing a DDoS packet and the attackers delay is asymmetrically orders-of-magnitude smaller) while waiting for the counter party to reciprocate. In bandwidth DDoS, the attacker must have enough bots to saturate the bandwidth of the victim, which is a significant resource. In malformed requests DDoS, the cost to the victim of verifying needs to the symmetric to the cost of the attacker to sign the request. I wrote a white paper (https://github.com/shelby3/hashsig/blob/master/DDoS%20Defense%20Employing%20Public%20Key%20Cryptography.md) about how DDoS can be ameliorated with proper design in the crypto currency setting. Please make sure you understand the relevance of the word 'asymmetry' of costs for the attacker versus the victim w.r.t. DoS. Seems that running a DE in your original fee-based scheme (which I allege is broken) is quite simple as it only involves offering a payto address. Sorry to be a pain, but really you should thank those who do peer review and help you from wasting your time. I'd really appreciate a more cordial and rational response. Getting irrationally upset at those who try to help you, is what the retards over in the Altcoin Discussion forum do, and I know you are too mature and do not possess that behavior. Please remember in the past when you made similar arguments about why proof-of-stake was not attackable, which ended up being wrong as evidenced by the current top-down governance of Nxt and Bitshares. Those of us who take the time to analyze and point out egregious flaws do it because we want correct solutions, not because we are haters. If those we help, hate back on us, the entire discussion forums descends into stupid noise. Please even if you have vested interests, still try to remain fair and rational. This is a scientific discussion, and let's not conflate it with other matters such as any investment you've already made in DE. I can't do my work in a rational, scientific way if I have to worry about each person's ego and vested interests that I might offend by writing rationally. I didn't see where you could identify the attacker in your protocol without incurring any possibility of bailing out and jamming. Perhaps you can explain that more succinctly (without all the cut & choose employing Bitcoin op codes since I don't comprehend Bitcoin op codes thus I can't understand the cut & choose in the way you guys have explained it thus far, although I think I understand the concept which is to probabilistically reveal the preimage). Any way, I was thinking about this more because I know you are invested in DE and I really want to help you find a solution. Of course I don't feel good about the situation where you are invested and it is fundamentally flawed. It is not like I get some great joy in finding flaws. I get great joy in finding solutions that don't have flaws. I can't help it that there is so much flawed work being done in the crypto currency realm. It is the nature of the beast, because crypto logic is complex and there are a lot hair-brained ideas being promulgated. For example, Blockstream's side-chains reduce the security to the weakest chain due to chain reorganizations and the fact that proof-of-work is probabilistic and thus never final (e.g. lie in wait long-con attack). Blockstream is even investing so much effort to push Segregated Witness which enables them to version the block chain with soft forks, thus it looks like a trojan horse so they can get the changes they want to enable this broken concept of side-chains (https://bitcointalk.org/index.php?topic=1319681.msg13720883;topicseen#msg13720883). Speak these rational truths and many people get pissed off and posts get removed by the moderator. Any way, I think I have thought of a solution for DE. The key is to identify the attacker immediately so that all decentralized parties can apply my upthread blocking "Coin Days Destroyed" suggestion (https://bitcointalk.org/index.php?topic=1364951.msg13925984#msg13925984). The "Coin Days Destroyed" becomes the reference point that is signed by the owner of the resource, which thus apparently escapes from my generative essence conceptualization of the problem set (https://bitcointalk.org/index.php?topic=1364951.msg13940253#msg13940253). So change to the protocol is the provider of the hash sends to the trade's counter party to sign it (hashed with the other party's UXTO address) so the counter party's UXTO can be identified. Then the hash provider (the potential jamming victim) posts this information in a timed refundable transaction to the block chain (spending to the payee contingent on releasing the hash). If the attacker never posts the reciprocal transaction on the other block chain, this enables anyone to identify that attacker and apply the Coin Days Destroyed filtering that I proposed upthread. Note this eliminates the need for any fee. But I assume you can find some justification for a fee, such as perhaps keeping your source code for the DE app closed source and/or offering a centralized fee structure for matching orders, limit orders, etc.. You won't be able to steal funds, which afaik is the most significant advantage of DE over CE. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 20, 2016, 12:59:02 PM Any way, I think I have thought of a solution for DE. I think we are both circling around (converging?) to a similar type of solution.The key is to identify the attacker immediately so that all decentralized parties can apply my blocking "Coin Days Destroyed" suggestion upthread. So change the protocol is the provider of the hash sends to the trade's counter party to sign it (hashed with the other party's UXTO address) so the counter party's UXTO can be identified. Then the hash provider (the potential jamming victim) posts this information in a timed refundable transaction to the block chain (spending to the payee contingent on releasing the hash). If the attacker never posts the reciprocal transaction on the other block chain, this enables anyone to identify that attacker and apply the Coin Days Destroyed filtering that I proposed upthread. Note this eliminates the need for any fee. But I assume you can find some justification for a fee, so as perhaps keeping your source code for the DE app closed source and/or offering a centralized fee structure for matching orders, limit orders, etc.. You won't be able to steal funds, which afaik is the most significant advantage of DE over CE. The cut and choose aspect is not requiring any details about bitcoin scripts. The idea is that one side commits to a large number of keypairs, the other side picks a random one and then the original side sends the privkeys to all keypairs except for the chosen one. Probabilistically as long as the cost of the fee (which is required) must be more than the expected return. Current settings are 1000 keypairs and 1/777 as the fee, so there is about a 13% negative cashflow for anybody that tries to cheat on a large scale. Now whether preventing economically motivated attackers is enough or not, clearly it is a necessary problem to solve completely. With both sides doing the above, each side has a privkey that can be used. I call it privAm and privBn, for Alice m and Bob n. These privkeys enable proof that you didnt cheat by sneaking in a fake keypair. It cannot be disclosed until after the protocol is past all the possible refund claims and the actual payments as they all hinge on these privkeys. To commit to them, a hash of the privkey is included in the protocol for each side, before any big money is committed. For now, let us agree that a vandalism oriented attack can tie up other's fees, but allowing the victim to recoup the fee for failed trades is adequate. It is 0.13% of the trade, so for the normal user not a big deal, but this small fee adds up to the friction that makes cheating uneconomical. The enforcement of fee collection for only the swaps that complete is by requiring the InstantDEX account to proactively spend the fees using both privAm and privBn, which are disclosed in the cases of successful swaps. [there might be some cases where a failed swap also ends up disclosing both privkeys, but not sure if it is even possible. if it is an additional time window would need to be created]. After the time window (probably 24hrs), both bob and alice can recoup their fees. By doing it once per day, there can be a single fee reclaim tx to aggregate all fees from the failed trades. This reduces the bitcoin txfees needed and a user can actually delay for however long they want. Might need to add another secret to the fee reclaim script to prevent the other party from reclaiming, but the high level concept is that if the trade goes through, the fee is paid and if not the fee is reclaimed. By making it so the fees are not sent until after both sides commit to their set of keypairs, we can identify the attacker. The method is for the field product of the privkeys to be made part of the protocol. We have the privAm * (privkeys other than privA) and the hash(privAm), so given the former two we can verify the hashes match. The privAm is disclosed after it is not a sensitive secret anymore. If cheating was going on, the hashes wont match and the corresponding party immediately punished. As soon as a failed proof of commitment is detected, this violation can be broadcast to all the nodes, who immediately update reputation score. With such a realtime feedback, it does not seem likely that an attacker can do any prolonged attack from the same address. Sybil attacks are reduced in effect dramatically if the nodes all know the historical performance of that account. Zero activity would mean potential attacker. non-zero activity (and by activity I mean fees paid to eliminate any advantage from self-trading) would enable the attacker to start attacking, but after the first failure to disclose, he is blacklisted in realtime. Similarily attackers who just want to tie up your funds for the deposit or payment (not the fee) it is a different attack. They cant both follow the keypairs commitment protocol and also prevent the trade from completing as in order to prove your commitment, you need to disclose the privAm or privBn. The coin days requirement should be reserved for usage by user option when there is an ongoing attack, as otherwise new users wont be able to trade. But it would rapidly exhaust the utxo the attacker can use in addition to being blacklisted, and losing funds. I believe the following fee policy solves the incentives issue, especially penalizing the attacker. Fee policy: 1. When both sides have committed to their set of keypairs, the fee is paid 2. If the trade completes, the fee goes to InstantDEX account 3. If the trade doesnt complete the party that followed the protocol can recover the fee With the above three rules, there is not even a fee tied up, until both parties have committed. Once committed, both parties will have to complete the protocol or get flagged and I think a penalty of forfeiting the fee is needed to enforce economic unviability for attacks. pseudo-code for a payment script would be: if ( elapsedtime < day && privAm disclosed && privBn disclosed ) InstantDEX claims the fees; // this is the case where trade has been completed else if ( elapsedtime >= day ) { if ( no privAm ) Bob claims his fee else if ( no privBn ) Alice claims her fee } Separately, for all failed trades, the keypairs commitments are verified and any violations detected are broadcast to the network. (Or all the peers can monitor all the other trades) Any feedback regarding economically motivated attackers is much appreciated. James Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 20, 2016, 01:19:52 PM Remember the party that goes first in your protocol locks up his funds (e.g. UXTO) for the period of the timeout refund You can have a single transaction that does both fees. That way either neither pays the fee or both do. The protocol would be Step 1) Commit to hashes Alice and Bob create 1000 key pairs. Alice sends hash(alice_public_key_array) and hash(alice_fee_unlock) Bob sends hash(bob_public_key_array) and hash(bob_fee_unlock) TTP is the trusted third party. The fee transaction has 3 output (plus any change outputs) A) pays fee to Alice but requires <bob_fee_unlock>, otherwise it goes to TTP after 7 days B) pays fee to Bob but requires <alice_fee_unlock>, otherwise it goes to TTP after 7 days C) pays to TTP after 7 days Output C is a 1 of 2 multisig to commit to hash(hash(bob_public_key_array) | hash(alice_public_key_array)) Note: Both parties could exchange a list of TTPs and then pick one of the intersection. The default software could assign the author as one and allow -add_ttp_key as an option (and probably -author_ttp_disable) Step 2) Choose Once the fee transaction is broadcast/confirmed, the choose step can happen. Alice and Bob pick M and N. Alice sends Bob <alice_public_key_array> and the private keys except key N. Bob sends Alice <bob_public_key_array> and the private keys except key M. Both parties verify the key pairs and then assume the one they didn't pick is probably ok. As long as the key pairs were valid and the TTP is honest, then an attacker can reclaim his fees (less the TTP's fee). Step 3) Deposit Bob pays to an output which gives the money to Alice, unless he releases his private key within 2 days. He can re-claim his deposit immediately, but that means he ends up bailing out of the protocol. Step 4) Alice bail in Alice pays her bail-in to a multisig. If Bob reclaims his deposit, then she can reclaim her bail-in. Step 5) Bob bails in Bob pays his output. He can reclaim his output after 1 day. Alice can claim it immediately but then she has to release the fee unlock code and also give Bob her private key, so he can claim his output. At the end of this step, Bob is stuck. If he reclaims his deposit, then he lets Alice get her bail-in back and she can also claim his bail-in. Step 6) Alice spends her output (and provides alice_priv_m). For this step, Alice would also have to provide alice_fee_unlock, and alice_priv_m. Bob can reclaim his fee and also claim his output (and his deposit). Step 7) Bob can spend the altcoin output For this step, Bob would also have to provide bob_fee_unlock, so Alice can reclaim his fee. Step 8) Bob reclaims his deposit Bob can reclaim his deposit, since the info released is stale at this point. So, by the time Bob's deposit is locked, Alice has paid a fee transaction and has also locked her bail-in. I think that is reasonable. Quote So change to the protocol is the provider of the hash sends to the trade's counter party to sign it (hashed with the other party's UXTO address) so the counter party's UXTO can be identified. Then the hash provider (the potential jamming victim) posts this information in a timed refundable transaction to the block chain (spending to the payee contingent on releasing the hash). If the attacker never posts the reciprocal transaction on the other block chain, this enables anyone to identify that attacker and apply the Coin Days Destroyed filtering that I proposed upthread. I think having a gossip system for this is reasonable. All parties in the exchange have an incentive to know about fraud happening. Coinage means that a person can't just clear their bad rep by spending the output to another output. Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 20, 2016, 01:58:35 PM Separately, for all failed trades, the keypairs commitments are verified and any violations detected are broadcast to the network. (Or all the peers can monitor all the other trades) Violations of cut and choose mean that the party doesn't publish the keys. That means you can't prove it. What you need to do is show that the person agreed to pay the fee and then refused to build the transaction. The proof would be the signed fee transaction but missing the other party's signature. The accused party could then respond by publishing the full transaction and "clear their name". If fraud was successful, then you could publish the locked output and show that the published private key didn't match the committed public key. Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 20, 2016, 02:16:50 PM The coin days requirement should be reserved for usage by user option when there is an ongoing attack, as otherwise new users wont be able to trade. Allow me to correct you on this non-sequitor. The newness of a user of a decentralized exchange doesn't require that user's UXTO is newly acquired. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 20, 2016, 03:04:33 PM The coin days requirement should be reserved for usage by user option when there is an ongoing attack, as otherwise new users wont be able to trade. Allow me to correct you on this non-sequitor. The newness of a user of a decentralized exchange doesn't require that user's UXTO is newly acquired. If we assume that a lot of new users will be using the DE, they will be coming from the CE. And maybe they never had a local wallet, so they do a withdraw. patiently wait the confirms so it is in the wallet, then start a trade (after all they are doing this to use the DE) and then told "sorry you have to wait X amount of time since your dont have the right time of utxo" I really want to avoid having what is potentially a mainstream real world case have such an error message to be expected James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 20, 2016, 03:14:39 PM Separately, for all failed trades, the keypairs commitments are verified and any violations detected are broadcast to the network. (Or all the peers can monitor all the other trades) Violations of cut and choose mean that the party doesn't publish the keys. That means you can't prove it. Why wouldnt this approach work? Quote What you need to do is show that the person agreed to pay the fee and then refused to build the transaction. By providing the final privkey during the protocol, it is proven that that person didnt cheat. We probably need a few cases to deal with Bob bailing out before Alice had to disclose her privkey, probably via some blame states.The proof would be the signed fee transaction but missing the other party's signature. The accused party could then respond by publishing the full transaction and "clear their name". Quote If fraud was successful, then you could publish the locked output and show that the published private key didn't match the committed public key. Certainly if a fraud is a success, then this is broadcast to all the nodes. I think even any delay from the earliest time a privkey could have been disclosed should send out warnings. That way within a few blocks any funny business is detected and everyone warned.By using the sum of all fees paid by an account as insurance, then in the event that account steals from another, we could support an insurance claim (up to the limit of the fees paid by the attacker). This way as long as users can see the total fees paid by the other party, they will know how much coverage there is. Granted there are issues about an account building up large amounts of fees and then doing a large number in parallel, but that assumes there are that many that will match up at the same time. I guess this could be fixed by broadcasting all pending trades and adjusting the available insurance. Now we end up with just some propagation based edge cases where not all the pending amounts have been propagated before a trade is agreed to, right at the critical moment. It feels like it is getting to edge cases that can be handled James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 20, 2016, 04:25:26 PM The cut and choose aspect is not requiring any details about bitcoin scripts. The idea is that one side commits to a large number of keypairs, the other side picks a random one and then the original side sends the privkeys to all keypairs except for the chosen one. Probabilistically as long as the cost of the fee (which is required) must be more than the expected return. Current settings are 1000 keypairs and 1/777 as the fee, so there is about a 13% negative cashflow for anybody that tries to cheat on a large scale. Now whether preventing economically motivated attackers is enough or not, clearly it is a necessary problem to solve completely. You have not explained to me what cut and choose solves, how it solves it, etc.. The quoted explanation is incomplete. I have no idea why cut and choose was even introduced as a replacement to TierNolan's original protocol which used a single hash. I tried reading the original discussion where cut and choose was first introduced and it doesn't quickly register for me. I think because it was explained by example employing Bitcoin op codes which I don't understand and also perhaps there were some lapses in explanation due to the those in the discussion not writing down what was already clear to them in their minds (and I am not able to read minds). Perhaps if I tried harder I could reverse engineer what is being introduced, but in the interest of saving time, I wish one of you could explain it clearly. I do understand the notion of an interactive probabilistic challenge function where the cheater can't cheat unless they can guess which challenge you will provide. The Compact Confidential Transactions uses this to prove in zero knowledge a number is contained within a much larger interval. This can when required be converted to non-interactive with the Fiat-Shamir transform. I just don't understand the application here. Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 20, 2016, 04:43:02 PM The coin days requirement should be reserved for usage by user option when there is an ongoing attack, as otherwise new users wont be able to trade. Allow me to correct you on this non-sequitor. The newness of a user of a decentralized exchange doesn't require that user's UXTO is newly acquired. I was thinking of someone that just got their first BTC locally. wouldnt that be too young to be used? maybe i dont understand the intended coinage well enough. If we assume that a lot of new users will be using the DE, they will be coming from the CE. And maybe they never had a local wallet, so they do a withdraw. patiently wait the confirms so it is in the wallet, then start a trade (after all they are doing this to use the DE) and then told "sorry you have to wait X amount of time since your dont have the right time of utxo" I really want to avoid having what is potentially a mainstream real world case have such an error message to be expected James You are building a DE so that should mean that users have some coins on a block chain that they wish to trade. Who knows how long ago they acquired those coins. The Coin Days Destroyed is the time (# of blocks) elapsed since the UXTO was created. Since this is suggested to be a user configurable setting which they set only on their own decentralized client (which filters which counter parties they accept to start the DE protocol), then user whose UXTO is very young, can set the threshold so their UXTO fulfills the chosen threshold. If the threshold isn't high enough, they incur more risk of being jammed. But also note that while they are being jammed, their UXTO is aging, so they can continually increase their chosen threshold if necessary to foil an attacker. There is no disadvantage to offering the feature. An error msg will never be shown. The only effect is the number of available counter parties may shrink as the threshold is raised, as well the risk of jam attack decreases as the threshold is raised. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 20, 2016, 04:56:30 PM The coin days requirement should be reserved for usage by user option when there is an ongoing attack, as otherwise new users wont be able to trade. Allow me to correct you on this non-sequitor. The newness of a user of a decentralized exchange doesn't require that user's UXTO is newly acquired. I was thinking of someone that just got their first BTC locally. wouldnt that be too young to be used? maybe i dont understand the intended coinage well enough. If we assume that a lot of new users will be using the DE, they will be coming from the CE. And maybe they never had a local wallet, so they do a withdraw. patiently wait the confirms so it is in the wallet, then start a trade (after all they are doing this to use the DE) and then told "sorry you have to wait X amount of time since your dont have the right time of utxo" I really want to avoid having what is potentially a mainstream real world case have such an error message to be expected James You are building a DE so that should mean that users have some coins on a block chain that they wish to trade. Who knows how long ago they acquired those coins. The Coin Days Destroyed is the time (# of blocks) elapsed since the UXTO was created. Since this is suggested to be a user configurable setting which they set only on their own decentralized client (which filters which counter parties they accept to start the DE protocol), then user whose UXTO is very young, can set the threshold so their UXTO fulfills the chosen threshold. If the threshold isn't high enough, they incur more risk of being jammed. But also note that while they are being jammed, their UXTO is aging, so they can continually increase their chosen threshold if necessary to foil an attacker. There is no disadvantage to offering the feature. An error msg will never be shown. The only effect is the number of available counter parties may shrink as the threshold is raised, as well the risk of jam attack decreases as the threshold is raised. There a many people who have dozens of different altcoins and no wallet for any of them, or just a few. In fact most people fall in that category, where they have a few alts they have local wallets and still they buy alts on exchanges they dont have wallets for, with the intent of converting them before withdrawing. Good point that it can be done without any error messages, but just a gradual increase in the potential matches that are possible. Maybe we can have a sunrise type of graphics to show that the longer you wait the more trades are possible James Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 20, 2016, 06:53:06 PM You have not explained to me what cut and choose solves, how it solves it, etc.. The quoted explanation is incomplete. Cut and choose is required because there is no way to commit to releasing a private key. You can commit to releasing the value of x such that hash(x) = y. If both coins support CLTV, then you can commit to a hash and no cut and choose is required. Few altcoins actually support it. The cut and choose allows you to commit to releasing a private key for a given public key. It's a cheat. You commit to a hash of the private key. The cut and choose is to make sure that the hash actually refers to a private key. The other party can make an altcoin payment to a 2 of 2 multisig with confidence. Since you committed to releasing the private key before the timeout, it eliminates the hold up risk. Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 21, 2016, 05:44:36 PM You have not explained to me what cut and choose solves, how it solves it, etc.. The quoted explanation is incomplete. Cut and choose is required because there is no way to commit to releasing a private key. You can commit to releasing the value of x such that hash(x) = y. If both coins support CLTV, then you can commit to a hash and no cut and choose is required. Understood. Few altcoins actually support it. The cut and choose allows you to commit to releasing a private key for a given public key. It's a cheat. You commit to a hash of the private key. The cut and choose is to make sure that the hash actually refers to a private key. The other party can make an altcoin payment to a 2 of 2 multisig with confidence. Since you committed to releasing the private key before the timeout, it eliminates the hold up risk. I don't understand the mechanism. Please explain how the protocol accomplishes the goal. Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 21, 2016, 05:57:37 PM 1) Cut and choose Bob generates 1000 keypairs and sends hash(bob_priv_n) and bob_pub_n to Alice for each n (1 to 1000). Alice picks n from 1 to 1000 and Bob sends bob_priv_n for the 999 other n's. If they are ok, then Alice assumes the pair she didn't see is valid. Similarly, Alice generates 1000 key pairs and has Bob choose. This gives the following public info. hash(bob_priv_n) matches bob_pub_n hash(alice_priv_m) matches alice_pub_m There is a 0.1% chance of fraud for each attempt. This means that fees must be at least 0.1% of the transaction value. In that way, there is no incentive to cheat at the cut-and-choose. Okay with this private message, I was able to better understand the mechanism but still I don't see what it solves. TierNolan it would be helpful for readers to understand, if you stated the conceptual point, which is that each party is sent a challenge which they can't predict, and they release all but one of the private keys BEFORE committing to the multisig on the block chain. On the block chain they commit to the public key which corresponds to the one private key they have not yet seen (of course they can't commit to a public key for which they already know the counter party's private key because then the party that goes first to put his/her transaction on the block chain, could have his/her funds stolen as the counter party wouldn't need to reciprocate). Since each party could not predict the challenge, there is a 1/1000 probability that they have chosen a private key that was invalid. But I still don't understand how this forces the counter party to release the private key within the timed interval? Just because the counter party proves he knows the hash of his private key doesn't prove he will reveal or sign with it. I am totally dumbfounded as to how this solves anything. ??? Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 21, 2016, 06:04:29 PM I don't understand the mechanism. Please explain how the protocol accomplishes the goal. This just looks at half of the cut and choose system. Bob picks 1000 key pairs and sends Alice hash(1000 public keys) Bob also spends 10 cents in fees, which he loses if he cheats. Alice picks a number from 1 to 1000 and select one of the key pairs. Bob then sends Alice the 1000 public keys and 999 of the private keys. Alice checks that the public keys hashes to hash(1000 public keys) from before. She also checks that the 999 private keys match the public keys. She doesn't know if private key N actually hashes to public key N, but she assumes it does. There is no point in Bob lying about the 1000 public keys, since he will have to show them. If he does lie about the private keys, there is no point in having more than 1 false private key. If he has 2 or more private keys that don't match, then he is guaranteed to be caught. So, Bob has two choices - He can honestly create the 1000 key pairs In that case the protocol works as required. - He can have one of the private keys not match the public key In this case, there is a 99.9% chance of being caught. He loses any fee he has committed. There is a 0.1% chance he will get away with it. At best, this means that he gets all the money (other than the deposit, since there is no hold-up risk there). This gives an expected payout of (value of the trade) * 0.001 - fee * 0.999. If the trade is less than 990 times larger than the fee, then the expected value of cheating is negative. Increasing the size of the fee would help. The key for the cut and choose to work is that Bob must commit to 1000 pairs(pay the fee) before Alice tells him her choice. Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 21, 2016, 06:10:02 PM I don't understand the mechanism. Please explain how the protocol accomplishes the goal. This just looks at half of the cut and choose system. Bob picks 1000 key pairs and sends Alice hash(1000 public keys) Bob also spends 10 cents in fees, which he loses if he cheats. Alice picks a number from 1 to 1000 and select one of the key pairs. Bob then sends Alice the 1000 public keys and 999 of the private keys. Alice checks that the public keys hashes to hash(1000 public keys) from before. She also checks that the 999 private keys match the public keys. She doesn't know if private key N actually hashes to public key N, but she assumes it does. There is no point in Bob lying about the 1000 public keys, since he will have to show them. If he does lie about the private keys, there is no point in having more than 1 false private key. If he has 2 or more private keys that don't match, then he is guaranteed to be caught. So, Bob has two choices - He can honestly create the 1000 key pairs In that case the protocol works as required. - He can have one of the private keys not match the public key In this case, there is a 99.9% chance of being caught. He loses any fee he has committed. There is a 0.1% chance he will get away with it. At best, this means that he gets all the money (other than the deposit, since there is no hold-up risk there). This gives an expected payout of (value of the trade) * 0.001 - fee * 0.999. If the trade is less than 990 times larger than the fee, then the expected value of cheating is negative. Increasing the size of the fee would help. The key for the cut and choose to work is that Bob must commit to 1000 pairs(pay the fee) before Alice tells him her choice. But afaics this doesn't bind Bob to release or sign with the one private key which was not revealed. So it seems the cut and choose adds nothing that just asking Bob for a single public key for the 2 of 2 multi-sig would accomplish or what am I missing ??? Also fees don't work, because the attacker can run a DE as I explained upthread. Afaics the generative essence is inviolable. Both parties must provide a reference point at the start of a protocol by having both parties sign their hash (or public key for 2 of 2 multi-sig) as I suggested upthread. Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 21, 2016, 06:11:48 PM Just because the counter party proves he knows the hash of his private key doesn't prove he will reveal it. I am totally dumbfounded as to how this solves anything. ??? Once you have proven that the digest is hash(private_key). You can then commit to releasing x should have hash(x) = h. For example, Bob pays a large deposit to this output Code: IF With cut and choose, Alice is sure that hash(Bob's private key) actually is for his private key. If Bob doesn't spend that output within 2 days, then Alice can take his deposit (since the CLTV in the top line will have expired). However, the only way to spend that output is to provide the private key. To spend the output he signs it using Code: <Bob's signature using private key 2> <Bob's private Key> HASH160 hashes his private key and then EQUALVERIFY verifies that it matches <hash(Bob's private key)>. If Alice watches the network, then she will be able to obtain this information and so will get Bob's private key, as promised. Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 21, 2016, 07:24:04 PM I told you I don't understand Bitcoin op codes, therefor I don't understand your post.
Also you said the point of cut and choose is when CLTV is not available. But then you using CLTV in your example above ??? Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 21, 2016, 07:53:33 PM I told you I don't understand Bitcoin op codes, therefor I don't understand your post. The protocol puts all the fancy opcodes in the bitcoin side, only the basic scripts are assumed to work on the altcoin sideAlso you said the point of cut and choose is when CLTV is not available. But then you using CLTV in your example above ??? Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 21, 2016, 08:15:36 PM @TierNolan
As the implementation is filling out, I found another minor attack vector, the slippage attack. Assuming all other parts of the protocol is followed, there is just one place where one side is granting the other an at the money put option without paying anything for this. Some sort of black-scholes option premium is needed. Scenario: Alice and Bob agree to trade ALT at 0.02 BTC We get to where Bob's payment has confirmed and he is waiting for Alice to send payment. Now Alice runs a modified client that is checking poloniex to wait until the price goes below 0.02 until sending the response. In half the cases the timeout is reached, but as long as the slippage is more than the fee, Alice has gained. This is why the shorter the time window to complete the better, but since BTC blocktimes are unpredictable, I think 1 hour is the shortest time we can set the altcoin sides timeout and I am still not sure what to do about the +/-2 hours leeway on bitcoin timestamps and how that affects CLTV http://www.fintools.com/resources/online-calculators/options-calcs/options-calculator/ using volatility of 25% and 5% riskless interest rate, a one day at the money put option's value us about 0.5%, which is more than 3 times the fee. So actually at the one hour timeframes the 0.13% fee is actually right around the put option value! So maybe this isnt a problem after all. Maybe Alice needs to pay a bit higher fee for the option premium in addition to the insurance fee for the cut and choose. I think if Alice paid the same value fee for BTC and altcoin, that takes care of this asymmetry. Bob has a much weaker slippage attack surface. He is not getting a call option, but some sort of hybrid (not sure of name, maybe a half straddle butterfly) If price goes against him, he delays sending, but then Alice wont complete so he wont gain, but now Alice paid for the put option and not benefiting from it... OK, so this needs some tweaking of fees, maybe an extra one inserted into the protocol, but the shorter the timeframe the smaller this problem is, so I want to get as streamlined of an ordermatch working first James Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 21, 2016, 08:23:11 PM I told you I don't understand Bitcoin op codes, therefor I don't understand your post. Ok the code means that the output can be claimed under two conditions: - Alice can claim the output, but she must wait 2 days - Bob can claim the output, but to do so he must also provide x such that hash(x) = <hash(bob's private key)> Bob is the one that funds that output. It is his deposit. If we waits more than 2 days, Alice will claim the output using option 1. This means that he must claim the output before then. However, to do that, he has to provide x. Assuming that the cut and choose worked, then x is guaranteed to be the private key. Quote Also you said the point of cut and choose is when CLTV is not available. But then you using CLTV in your example above ??? The trade is from Bitcoin to an altcoin. All the complexity is to leverage Bitcoin's script to allow trading with an obsolete altcoin. Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 21, 2016, 08:24:40 PM As the implementation is filling out, I found another minor attack vector, the slippage attack. Yeah, this is a known problem. The price of the trade would have to take it into account. There could be 2 prices. Buy Bitcoin as Bob Sell Bitcoin as Bob (or even 4, since there would be a spread) Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 21, 2016, 08:28:48 PM From PM, because this is an important point that others might not realize:
Well if an attacker runs a DE and I dont attack back, then that DE works, so at least there will be one DE that works The attacker can set the effective minimum fee (even it is multiples higher than the advertized fee due to jammed trades), by ratio of how much they attack their own (or another's) DE. So in essence the attacker can shut down all DE, by making sure he earns just enough on his DE to offset his attack costs on other DE, but this is a moving target that eventually ends up in all users giving up and abandoning DEs. There only needs to be one attacker. Edit: I think I offered a solution upthread. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 21, 2016, 10:41:51 PM From PM, because this is an important point that others might not realize: I didnt fully understand you solution. can you describe it in more detail?Well if an attacker runs a DE and I dont attack back, then that DE works, so at least there will be one DE that works The attacker can set the effective minimum fee (even it is multiples higher than the advertized fee due to jammed trades), by ratio of how much they attack their own (or another's) DE. So in essence the attacker can shut down all DE, by making sure he earns just enough on his DE to offset his attack costs on other DE, but this is a moving target that eventually ends up in all users giving up and abandoning DEs. There only needs to be one attacker. Edit: I think I offered a solution upthread. James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 22, 2016, 09:59:33 PM With cut and choose, Alice is sure that hash(Bob's private key) actually is for his private key. How does the cut & choose exchange prove that Bob's has provided a hash of a private key and not a hash of something else ??? If Bob doesn't spend that output within 2 days, then Alice can take his deposit (since the CLTV in the top line will have expired). However, the only way to spend that output is to provide the private key. To spend the output he signs it using Code: <Bob's signature using private key 2> <Bob's private Key> HASH160 hashes his private key and then EQUALVERIFY verifies that it matches <hash(Bob's private key)>. If Alice watches the network, then she will be able to obtain this information and so will get Bob's private key, as promised. And so will everyone else get Bob's private key and a miner who wins the block can spend his output before his transaction is confirmed on the block chain. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 22, 2016, 11:10:15 PM With cut and choose, Alice is sure that hash(Bob's private key) actually is for his private key. How does the cut & choose exchange prove that Bob's has provided a hash of a private key and not a hash of something else ??? If Bob doesn't spend that output within 2 days, then Alice can take his deposit (since the CLTV in the top line will have expired). However, the only way to spend that output is to provide the private key. To spend the output he signs it using Code: <Bob's signature using private key 2> <Bob's private Key> HASH160 hashes his private key and then EQUALVERIFY verifies that it matches <hash(Bob's private key)>. If Alice watches the network, then she will be able to obtain this information and so will get Bob's private key, as promised. And so will everyone else get Bob's private key and a miner who wins the block can spend his output before his transaction is confirmed on the block chain. There is no way to know for sure that the hash of the privkey was provided until it works when it is revealed. That is why the fee is required, so that any attack by cheating has a negative expected return. I changed to 2000 keypairs, so with a 1/777 fee, the expected return is a loss of about 20%. This presupposes there are anywhere near 2000 trades that can be done. Since newbie accounts will only be traded with reluctantly, it will take time to build up an account with 1000+ trades. And what is achieved? You have lost 1000+ fees, you steal from who you traded with (worth 777 fees), still you lost 200+ fees. The account you built up is blacklisted and the victim is compensated from the fees that have been paid by the attacker. Any balance is forfeited. So any cut and choose attacker will be helping the InstantDEX bank account and the victim would just need to wait a bit extra before being reimbursed. No financial harm to the victim, financial gain to InstantDEX, financial loss to the attacker. Another point. The 2000 keypairs acts as PoW. It takes several seconds to calculate them all, so you would need one CPU core per attack. Its not like you can simply notify 2000 other peers that you want to start a trade. The initiator has to calculate all the keypairs upfront. Only if a node decides to accept this incoming offer, will the similar calcs need to be done on the receiving side. Due to the time it takes, probably need to put in some checks for the desirability of the initiating side, but that is for later. I have a strong feeling that losing 20% will be a pretty strong deterrent, in fact I am hoping we will get a bunch of idealogical cut and choose attackers who want to disrupt the DE without regard to losing money. I can then use those funds to pay for bots that will be making bids, just waiting to be cheated on. In fact, this could create a massive positive feedback loop and the net result is that the DE is unusable by people, but the bots make the attacker pay thousands of BTC in fees, forever. Not a great result, but I think I can live with that. James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 22, 2016, 11:14:37 PM From PM, because this is an important point that others might not realize: The cut and choose attack is very cash negative. The papercut attack appears to be the biggest attack vector now.Well if an attacker runs a DE and I dont attack back, then that DE works, so at least there will be one DE that works The attacker can set the effective minimum fee (even it is multiples higher than the advertized fee due to jammed trades), by ratio of how much they attack their own (or another's) DE. So in essence the attacker can shut down all DE, by making sure he earns just enough on his DE to offset his attack costs on other DE, but this is a moving target that eventually ends up in all users giving up and abandoning DEs. There only needs to be one attacker. Edit: I think I offered a solution upthread. I think just making InstantDEX a TTP (trusted third party) with full discretion as to the disposition of fees will solve this. Granted it requires trusting that I wont abuse the DE users, myself, but we are talking about the fee here not the trading capital. If this really is an issue that people wont trust that I wont papercut attack the DE users, then we would need some other method. Since you already have a solution, I could just use that too. Does this mean there are no attacks left? James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 22, 2016, 11:18:48 PM As the implementation is filling out, I found another minor attack vector, the slippage attack. Yeah, this is a known problem. The price of the trade would have to take it into account. There could be 2 prices. Buy Bitcoin as Bob Sell Bitcoin as Bob (or even 4, since there would be a spread) Otherwise, the burden of estimating the black-scholes value being granted falls on the user. I guess I could just have a standard spread factor that is added, but it is variable depending primarily on the other party to the trade. It seems that the fully precise system will need realtime monitoring of past behavior, tracked by fees paid, number of transactions, volumes of transactions, number of "disconnects", etc. But all this would be a layer on top of the atomic swap, so I dont think I need to worry about it for now. Maybe someone will want to help coding the insurance tracking aspect of this. James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 23, 2016, 10:07:03 AM debugging is progressing slower than normal. just takes too long per iteration, I have time to respond to messages... then time passes and with all the printouts a bit hard to know how the test did.
anyway, have it going back and forth in the state machine until it is waiting for the feetx to confirm. [note to FSM debuggers: it REALLY helps to spell the name of the state it is in correctly!] Due to the variety of ways the feetx can go, I made things so it can be put in a variety of places without too much work. For now, I just want to see an automated swap complete. James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 23, 2016, 11:28:15 PM And so will everyone else get Bob's private key and a miner who wins the block can spend his output before his transaction is confirmed on the block chain. These are onetime throwaway private keys and the output is hardwired to Bob's address, so if anybody else does the spend it pays to Bob anyway. I think I am having difficulty analyzing due to not having one complete specification of the entire protocol with all justifications in one post or web page, and trying to understand it piecewise instead of holistically. Also I've been running around past 2 days to doctors, testing laboratories, and clinics. In the original version of TierNolan's protocol, my understand is Bob obviously pays Alice, not himself. Bob and Alice each have some UXTO they want to spend to each other on separate block chains. Alice constructs a CLTV payment to Bob contingent on releasing a hash preimage and waits for Bob to construct an identical transaction which he can do once he sees Alice's transaction is confirmed. Once Alice sees Bob's transaction is confirmed, she releases the hash preimage so both transactions become finalized. The cut & choose alternative is apparently proposed to handle the case where Bob's block chain doesn't support a CLTV opcode. Apparently the conceptual idea that Alice pays (hardwired to Bob as the payee) with CLTV to a 2 of 2 multi-sig, where the second multi-sig requires Bob's private key. Apparently Bob releases this private key when he spends his UXTO to Alice, thus Alice is sure Bob can be paid unless he pays her. My point is that once Bob releases this private key, anyone can spend his UXTO to any payee else besides Alice. Thus I am asserting the cut & choose doesn't work, unless someone can explain to me my mistake. My proposed tweak or improvement to the original protocol to eliminate jamming is that Bob signs a message indicating he is starting the protocol with Alice, contingent on Alice submitting her CLTV transaction within the current block number. Alice includes this signature in the meta data of her transaction on the block chain. Thus if Bob doesn't issue his CLTV transaction, then he is jamming and his UXTO can be filtered by using the Coin Days Destroyed setting. Note do not permanently filter Bob, because it is possible he wasn't able to fulfill his obligation due to network outage or for other valid reason. Edit: I don't see an intractable problem with not supporting altcoins that don't add CLTV support. Altcoins will add it, lest they fall behind what the market wants. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 24, 2016, 04:00:57 AM Remember the party that goes first in your protocol locks up his funds (e.g. UXTO) for the period of the timeout refund You can have a single transaction that does both fees. That way either neither pays the fee or both do. The protocol would be Step 1) Commit to hashes Alice and Bob create 1000 key pairs. Alice sends hash(alice_public_key_array) and hash(alice_fee_unlock) Bob sends hash(bob_public_key_array) and hash(bob_fee_unlock) TTP is the trusted third party. The fee transaction has 3 output (plus any change outputs) A) pays fee to Alice but requires <bob_fee_unlock>, otherwise it goes to TTP after 7 days B) pays fee to Bob but requires <alice_fee_unlock>, otherwise it goes to TTP after 7 days C) pays to TTP after 7 days Output C is a 1 of 2 multisig to commit to hash(hash(bob_public_key_array) | hash(alice_public_key_array)) Note: Both parties could exchange a list of TTPs and then pick one of the intersection. The default software could assign the author as one and allow -add_ttp_key as an option (and probably -author_ttp_disable) Step 2) Choose Once the fee transaction is broadcast/confirmed, the choose step can happen. Alice and Bob pick M and N. Alice sends Bob <alice_public_key_array> and the private keys except key N. Bob sends Alice <bob_public_key_array> and the private keys except key M. Both parties verify the key pairs and then assume the one they didn't pick is probably ok. As long as the key pairs were valid and the TTP is honest, then an attacker can reclaim his fees (less the TTP's fee). Step 3) Deposit Bob pays to an output which gives the money to Alice, unless he releases his private key within 2 days. He can re-claim his deposit immediately, but that means he ends up bailing out of the protocol. Step 4) Alice bail in Alice pays her bail-in to a multisig. If Bob reclaims his deposit, then she can reclaim her bail-in. Step 5) Bob bails in Bob pays his output. He can reclaim his output after 1 day. Alice can claim it immediately but then she has to release the fee unlock code and also give Bob her private key, so he can claim his output. At the end of this step, Bob is stuck. If he reclaims his deposit, then he lets Alice get her bail-in back and she can also claim his bail-in. Step 6) Alice spends her output (and provides alice_priv_m). For this step, Alice would also have to provide alice_fee_unlock, and alice_priv_m. Bob can reclaim his fee and also claim his output (and his deposit). Step 7) Bob can spend the altcoin output For this step, Bob would also have to provide bob_fee_unlock, so Alice can reclaim his fee. Step 8) Bob reclaims his deposit Bob can reclaim his deposit, since the info released is stale at this point. So, by the time Bob's deposit is locked, Alice has paid a fee transaction and has also locked her bail-in. I think that is reasonable. I see a script some posts later that should be Bob's deposit script, but I hope you can enumerate all the required scripts? I want to make sure I am not using scripts from an older iteration. The code now has a matched set of sendtx and verifytx functions, so as long as the proper scripts are used, it can adapt to a large range of protocol changes. To help with debugging, I am making a manual way to just approve a tx in the state machine, so by manually kicking it to the next state, we can complete the swaps. Also, I will add ways to go into the reclaim states so we can verify the other side can indeed reclaim. Thanks! It does seem the above protocol solves all the practical issues, but I am confused a bit by "As long as the key pairs were valid and the TTP is honest, then an attacker can reclaim his fees (less the TTP's fee)." I think we want to allow the TTP to not allow an attacker (as evidenced by non-submission of privN) to be able to reclaim any fees. The following are the identified attack vectors: 1. Cut and choose attacker (has largest monetary attack on victim) 2. Papercut attacker (delays or prevents victims from reclaiming fees) 3. Liquidity attacker (locks up funds for long time and makes victim not have access to funds for a while) 4. Slippage attacker (waits to complete protocol based on market movements) To combat these attacks: 1. cumulative fees paid must be significantly more than expected gains and any identified attacker punished with forfeiture of any credits. 2. victims should be able to reclaim/reuse any fees paid for trades that dont complete, or instead of reclaiming, the fees can build credits 3. This seems difficult to punish as the protocol can be followed but with maximum delay allowed, so by reducing the reference time to 1hr/2hrs, it minimized the negative effect 4. With shorter maxtime for the protocol, this effect is minimized, plus users will need to adjust their bid/asks to compensate Isnt there a way to prevent attacker from recouping any fees via TTP What is the recommedation for a timestamp padding for the CLTV due to the +/- 2 hour timestamp tolerance? James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 24, 2016, 04:08:14 AM My point is that once Bob releases this private key, anyone can spend his UXTO to any payee else besides Alice. Thus I am asserting the cut & choose doesn't work, unless someone can explain to me my mistake. The "private key" is just one of 1000 temporary ones, so it only applies to the set of transactions from this atomic swap.The spend requires to have both the temporary private key and a signature that matches the destination pubkey. Presumably only Bob is able to sign the spend with the real privkey that matches the pubkey the output pays. The protocol has evolved to solve the real world issues identified, so while the concepts are still the same, a lot of details have changed. Also, waiting for all the popular coins to update could be a long wait. I am working on a universal solution, at least as universal as possible. In a market where coins without any working blockchain are trading hundreds of thousands USD per day, it seems a bit unrealistic to wait for sanity and technical updates. Why would they bother if they are already getting massive volumes and decent marketcaps? Especially if they dont have a dev team anymore. James Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 24, 2016, 09:31:33 AM This protocol changes the deposit script so that Bob can reclaim the deposit at anytime. Are you sure there arent any race conditions where Bob can wait to see the unconfirmed tx on the altcoin side and then reclaim his deposit? I think it does, but this definitely requires changing the FSM. I may have got it wrong, need to check. Quote I see a script some posts later that should be Bob's deposit script, but I hope you can enumerate all the required scripts? I want to make sure I am not using scripts from an older iteration. The code now has a matched set of sendtx and verifytx functions, so as long as the proper scripts are used, it can adapt to a large range of protocol changes. I probably need to do a definitive version somewhere. Quote It does seem the above protocol solves all the practical issues, but I am confused a bit by "As long as the key pairs were valid and the TTP is honest, then an attacker can reclaim his fees (less the TTP's fee)." I think we want to allow the TTP to not allow an attacker (as evidenced by non-submission of privN) to be able to reclaim any fees. The purpose of the fee is to protect the cut-and-choose step. As long as the 1000 key pairs are valid, the TTP will refund, even if the entire protocol is not completed. The TTP could publish the keys at that stage. Quote Isnt there a way to prevent attacker from recouping any fees via TTP The attacker could submit their 1000 key pairs to prove that they didn't cheat at cut-and-choose. The TTP would refund (most of) their fee. Quote What is the recommedation for a timestamp padding for the CLTV due to the +/- 2 hour timestamp tolerance? You could do a block height + timestamp check? Code: <now + 2 hours> CLTV <now + 12 blocks> CLTV .... Care needs to be take, as that could push the early person past the long time person. I wonder if using Bitcoin as the time-server is possible. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 24, 2016, 09:38:34 AM This protocol changes the deposit script so that Bob can reclaim the deposit at anytime. Are you sure there arent any race conditions where Bob can wait to see the unconfirmed tx on the altcoin side and then reclaim his deposit? I think it does, but this definitely requires changing the FSM. I may have got it wrong, need to check. Quote I see a script some posts later that should be Bob's deposit script, but I hope you can enumerate all the required scripts? I want to make sure I am not using scripts from an older iteration. The code now has a matched set of sendtx and verifytx functions, so as long as the proper scripts are used, it can adapt to a large range of protocol changes. I probably need to do a definitive version somewhere. Quote It does seem the above protocol solves all the practical issues, but I am confused a bit by "As long as the key pairs were valid and the TTP is honest, then an attacker can reclaim his fees (less the TTP's fee)." I think we want to allow the TTP to not allow an attacker (as evidenced by non-submission of privN) to be able to reclaim any fees. The purpose of the fee is to protect the cut-and-choose step. As long as the 1000 key pairs are valid, the TTP will refund, even if the entire protocol is not completed. The TTP could publish the keys at that stage. Quote Isnt there a way to prevent attacker from recouping any fees via TTP The attacker could submit their 1000 key pairs to prove that they didn't cheat at cut-and-choose. The TTP would refund (most of) their fee. Quote What is the recommedation for a timestamp padding for the CLTV due to the +/- 2 hour timestamp tolerance? You could do a block height + timestamp check? Code: <now + 2 hours> CLTV <now + 12 blocks> CLTV .... Care needs to be take, as that could push the early person past the long time person. I wonder if using Bitcoin as the time-server is possible. so either 15 blocks or 2 + 2 hours, 15 BTC blocks seems pretty secure and should be at least one hour. But in case it is really slow, then 4 hours side would be ready, allowing for a 2 hour timestamp difference. I realized both nodes can share their timestamps to make sure they are within a few minutes so no need to deal with -2 hours vs +2 hours for Alice and Bob, they will both be assumed to be relatively in sync, so I think just 2 + 2 hours is needed for the CLTV time based expiration to give at least a 2 hour time window. The altcoin side would then have plenty of time before the 4 hours or 15 blocks Did I get that right? James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 24, 2016, 09:43:44 AM The following is the current FSM. I wish there was a way to generate graphics for it, but not familiar with a good way to do that.
With the various tweaks along the way, I fear it has drifted a bit, but at least here is a rigorous definition of the atomic FSM. It is a bit tricky as some things are implicit (sending of the tx) but the events for a state responsible for that transition is usually a direct map from the protocol description Code: // Two initial states are BOB_idle and ALICE_idle If you want to specify the protocol using FSM description, that would eliminate any ambiguities and blatant mistakes by silly coders like me. :) James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 24, 2016, 11:22:26 AM My point is that once Bob releases this private key, anyone can spend his UXTO to any payee else besides Alice. Thus I am asserting the cut & choose doesn't work, unless someone can explain to me my mistake. The "private key" is just one of 1000 temporary ones, so it only applies to the set of transactions from this atomic swap. The spend requires to have both the temporary private key and a signature that matches the destination pubkey. Presumably only Bob is able to sign the spend with the real privkey that matches the pubkey the output pays. I do not comprehend why you guys are unable to specify the protocol completely in one page or post. I can't analyze piecemeal. My point is that Alice has to be sure that Bob will issue his payment to Alice, and that he can't be capable of spending the payment from Alice to Bob before issuing the counter payment. As understand the cut & choose protocol, Alice signs the CLTV to a 2 of 2 multi-signature where Bob must reveal his private key in order to finalize that payment from Alice to Bob. But I also assume the payment from Bob to Alice (on the other block chain) must use the same private key, else otherwise Alice has no way to be sure that Bob has paid her as well. Thus I assert that once Bob releases his private key, any one could spend his UXTO to another party. This is getting really tiring go round and round with posts and not having a complete specification of the cut & choose protocol. The protocol has evolved to solve the real world issues identified, so while the concepts are still the same, a lot of details have changed. It would help if one of you would provide all the details in proper specification, because it is very difficult for someone to analyze that which is underspecified (and a moving target). Also, waiting for all the popular coins to update could be a long wait. I am working on a universal solution, at least as universal as possible. I do not believe a universal solution exists. But I will await clarification. In a market where coins without any working blockchain are trading hundreds of thousands USD per day, it seems a bit unrealistic to wait for sanity and technical updates. Why would they bother if they are already getting massive volumes and decent marketcaps? Especially if they dont have a dev team anymore. If you don't think there is a massive demand for decentralized exchange, then why even bother. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 24, 2016, 11:43:56 AM I do not comprehend why you guys are unable to specify the protocol completely in one page or post. I can't analyze piecemeal. The finite state machine above defines rigorously all states and state transitions.The bitcoin utxo requires both the temporary privkey and a signature from Bob's real privkey for the pubkey that the utxo pays to. To my knowledge you cant just use the onetime entropy from this output and use it to spend anything other than the specific transactions that are spent that require that magic number. You could trust me and TierNolan on this point if you dont understand the bitcoin scripts. The script at the high level is: if ( temporary privkey is revealed and Bob has also signed the transaction ) then you can spend this output So knowing the temporary privkey is necessary, but insufficient to spent that specific UTXO. Also, it is a onetime use privkey that only the transactions involved in this swap will ever refer to. unless Bob mistakenly funds more utxo using the temporary privkey, there arent any other utxo to worry about. The specific utxo is already paying Bob, plus requires Bob to sign it. Quote In a market where coins without any working blockchain are trading hundreds of thousands USD per day, it seems a bit unrealistic to wait for sanity and technical updates. Why would they bother if they are already getting massive volumes and decent marketcaps? Especially if they dont have a dev team anymore. If you don't think there is a massive demand for decentralized exchange, then why even bother. Meaning that it is necessary, but not necessarily sufficient to support altcoins without support for CLTV. And the only way to find out if there will be demand for DE is to get it to work with more than a few coins James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 24, 2016, 11:51:57 AM I do not comprehend why you guys are unable to specify the protocol completely in one page or post. I can't analyze piecemeal. The finite state machine above defines rigorously all states and state transitions. I do not (readily) comprehend the notation (and nor will I invest effort to learn or decipher the notation). I assume a proper specification would be more comprehensible to more people. However, do not feel obligated to do it for me. I can simply stop posting in the thread, which some parties might prefer any way. The bitcoin utxo requires both the temporary privkey and a signature from Bob's real privkey for the pubkey that the utxo pays to. This sentence is ambiguous to me. I would prefer a proper specification of what you are thinking about and attempting to describe. You could trust me and TierNolan on this point if you dont understand the bitcoin scripts. I do not trust anything which I can't verify and understand. But don't worry about me. If you are 100% sure, then no need for peer review. Right? So knowing the temporary privkey is necessary, but insufficient to spent that specific UTXO. Also, it is a onetime use privkey that only the transactions involved in this swap will ever refer to. unless Bob mistakenly funds more utxo using the temporary privkey, there arent any other utxo to worry about. The specific utxo is already paying Bob, plus requires Bob to sign it. I have no idea what part of the un(der)specified protocol you are referring to above. In a market where coins without any working blockchain are trading hundreds of thousands USD per day, it seems a bit unrealistic to wait for sanity and technical updates. Why would they bother if they are already getting massive volumes and decent marketcaps? Especially if they dont have a dev team anymore. If you don't think there is a massive demand for decentralized exchange, then why even bother. I have no idea how you interpret what I wrote as there isnt demand. My point is many coins are being traded on central exchanges that dont even have a dev team, so assuming they will update to latest scripts will be a very long wait. I understood your point and my point is if there is demand, then the market will fulfill that demand. Coins that are dying, will die. The market is able to route around such failure. Of course if you can provide backward compatibility, then of course you may want to provide it. But if it can't be technical sound, then obviously it shouldn't be done. Not much to argue about. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 24, 2016, 01:11:55 PM Quote I do not trust anything which I can't verify and understand. But don't worry about me. If you are 100% sure, then no need for peer review. Right? We are trying to explain, but the solution requires understanding of precisely how bitcoin scripts work generally https://en.bitcoin.it/wiki/Script and most importantly the specific opcodes used. If you say you dont understand them and then say you cant verify, well it seems to lead to an impasse... So you need to trust me and Tier about the details of scripts or bite the bullet and dive into the details of the scripts. Tier is world leading expert at squeezing the most functions from scripts and making them do things even I didnt think were possible to do with them. You can verify the high level design and trust that the scripts implement the AND requirement of the temporary privkey and Bob's signature using the real privkey that generated the pubkey that is part of the utxo. We tried to explain in english, but these scripts are indeed quite confusing. I like to get them done once and for all and not deal with them if possible. Regardless of specs, if the scripts are not understood, I dont see how it can be fully verified. Plz blame TierNolan for the scripts :) IF <now + 2 days> CLTV DROP <Alice's real public key> CHECKSIG ELSE HASH160 <hash(Bob's temp private key)> EQUALVERIFY <Bob's real public key 2> CHECKSIG ENDIF the above is the script. it is an if/else statement, the one that spends it selects which branch he wants to execute by pushing a 0 or 1 prior to executing the script, the following would be how to redeem the above script for the two cases: <alice signature for real pubkey> 0 or <bob signature for real pubkey> <bob's temp privkey> 1 http://www.cs.princeton.edu/~tongbinw/bitcoinIDE/build/editor.html is a cool script interpreter that allows you to single step through scripts. It doesnt handle all opcodes, but it is still quite useful. So to spend the second output, Bob has to sign the tx and assuming it is using SIGHASH_ALL what is signed is the tx that has all the other inputs blanked and the output script substituted. https://en.bitcoin.it/wiki/Transaction explains with some details how to properly sign things, but it is quite messy and I was happy when I got it so I can sign arbitarily constructed tx json objects and it dealt with all the craziness required. Anyway, bob gets the ~70 byte signature of the hash of the modified tx, adds a 0x01 (for SIGHASH_ALL) and pushes that to the stack along the temporary privkey and a 1 to choose the else path. Now when both halfs are put together: <bob signature for real pubkey> <temp privkey> 1 IF <now + 2 days> CLTV DROP <Alice's real public key> CHECKSIG ELSE HASH160 <hash(Bob's temp private key)> EQUALVERIFY <Bob's real public key 2> CHECKSIG ENDIF The above is the combined script that needs to evaluate to true. pretending I am a script interpreter, the first three things go on the stack: 1 <temp privkey> <sig> Now the IF see the one (and eats it) and goes to the else branch since it is a 1 and not 0 stack is: <temp privkey> <sig> remaining script: HASH160 <hash(Bob's temp private key)> EQUALVERIFY <Bob's real public key 2> CHECKSIG The HASH160 does rmd160(sha256(<temp privkey>)) and replaces the top of stack: rmd160(sha256(<temp privkey>)) <sig> remaining script: <hash(Bob's temp private key)> EQUALVERIFY <Bob's real public key 2> CHECKSIG the value from the output is pushed and the EQUALVERIFY pops off two and aborts if not equal. since both are the same it passes this test and we are down to the last check. stack: <sig> script: <Bob's real public key 2> CHECKSIG Now the CHECKSIG makes sure that it was signed by the privkey that generated the real pubkey Hopefully that is enough detail and background so you can personally verify that even if Bob's temp privkey is broadcast to the world, it wont do anybody any good. James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 24, 2016, 09:38:44 PM Again I don't understand any of that.
I simply asked if Bob is transacting on a block chain without Bitcoin op codes, how can his payment to Alice be required (by the Bitcoin block chain) before he can finalize the transaction on the block chain with Bitcoin CLTV op code. It should be possible to explain this in English. Stated in another way, what prevents Bob from finalizing the transaction on the block chain with Bitcoin CLTV op code, taking the funds from Alice, while also not issuing the reciprocal transaction paying to Alice on the other block chain? What I am getting at is that is seems to me (my understanding of the cut & choose as underspecified in English) that Bob has not issued any transaction before Alice's transaction paying to Bob is confirmed on the block chain with Bitcoin CLTV op code. Thus the only way I can see that Bob can be required to issue that said transaction paying to Alice (when employing cut & choose on a block chain without Bitcoin op codes), is if the private key for signing the transaction for Bob paying to Alice (on the block chain without Bitcoin op codes) is revealed in order to finalize the already confirmed transaction for Alice paying to Bob (on the block chain with the CLTV Bitcoin op code). And I have already explained that would not be technically sound because anyone could spend Bob's UXTO (instead of it paying to Alice, and afaics Bob could pay himself). So obviously I must be unaware of some aspect of the protocol, because obviously you two would have realized that the above assumption would not be technically sound. You can verify the high level design and trust that the scripts implement the AND requirement of the temporary privkey and Bob's signature using the real privkey that generated the pubkey that is part of the utxo. That sentence is underspecified. What is a 'real privkey'? Aren't all private keys real. Could you please state what you really mean and take the time to form a sentence that specifies which block chain you are referring, how it relates the protocol steps, etc.. I can't verify the high level design because the high level algorithm is underspecified per my question above. We tried to explain in english, but these scripts are indeed quite confusing. It doesn't need to be confusing. Just takes time to slow down and formulate well thought out English description. Einstein once said (paraphrasing), that an expert doesn't completely understand his own craft until he can explain it to a layman. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 24, 2016, 10:45:49 PM Thus the only way I can see that Bob can be required to issue that said transaction paying to Alice (when employing cut & choose on a block chain without Bitcoin op codes), is if the private key for signing the transaction for Bob paying to Alice (on the block chain without Bitcoin op codes) is revealed in order to finalize the already confirmed transaction for Alice paying to Bob (on the block chain with the CLTV Bitcoin op code). I believe the red part is what causes the confusion.What is being revealed is just a random number, NOT the privkey for signing the transaction. This tx is made so this random number must be revealed for the tx to be valid. I think this point needs to be understood first. The random number has both algebraic properties itself and it is part of the 1000 cut and choose dataset, but that really has little to do with the point you are complaining about. James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 24, 2016, 11:21:40 PM I would be grateful if you or TierNolan could actually answer my question?
Stated in another way, what prevents Bob from finalizing the transaction on the block chain with Bitcoin CLTV op code, taking the funds from Alice, while also not issuing the reciprocal transaction paying to Alice on the other block chain? I seem to never get a straight answer. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 25, 2016, 12:04:32 AM I would be grateful if you or TierNolan could actually answer my question? In order to spend the funds from Alice, bob has to disclose the random number Alice can use to spend the bitcoinsStated in another way, what prevents Bob from finalizing the transaction on the block chain with Bitcoin CLTV op code, taking the funds from Alice, while also not issuing the reciprocal transaction paying to Alice on the other block chain? I seem to never get a straight answer. Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 25, 2016, 12:10:14 AM I would be grateful if you or TierNolan could actually answer my question? Stated in another way, what prevents Bob from finalizing the transaction on the block chain with Bitcoin CLTV op code, taking the funds from Alice, while also not issuing the reciprocal transaction paying to Alice on the other block chain? I seem to never get a straight answer. In order to spend the funds from Alice, bob has to disclose the random number Alice can use to spend the bitcoins Afaics, you have not answered my question. Please read my question again. I didn't ask how Bob finalizes the payment from Alice to Bob. I asked, "while also not issuing the reciprocal transaction paying to Alice on the other block chain?". Alice can't spend Bitcoins, because Bob is issuing a transaction on a block chain that is not Bitcoin (and doesn't support CLVT). Are you implying that Bob will issue his transaction first (paying to Alice) on the block chain without a CLVT op code? Then how does Bob get a refund if Alice doesn't complete her side of the transaction and how can Bob's transaction be verified against a hash of a random number when the CLVT op code isn't supported. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 25, 2016, 12:21:08 AM I would be grateful if you or TierNolan could actually answer my question? Stated in another way, what prevents Bob from finalizing the transaction on the block chain with Bitcoin CLTV op code, taking the funds from Alice, while also not issuing the reciprocal transaction paying to Alice on the other block chain? I seem to never get a straight answer. In order to spend the funds from Alice, bob has to disclose the random number Alice can use to spend the bitcoins Afaics, you have not answered my question. Please read my question again. I didn't ask how Bob finalizes the payment from Alice to Bob. I asked, "while also not issuing the reciprocal transaction paying to Alice on the other block chain?". Alice can't spend Bitcoins, because Bob is issuing a transaction on a block chain that is not Bitcoin (and doesn't support CLVT). Are you implying that Bob will issue his transaction first (paying to Alice) on the block chain without a CLVT op code? Then how does Bob get a refund if Alice doesn't complete her side of the transaction and how can Bob's transaction be verified against a hash of a random number when the CLVT op code isn't supported. Ignoring fees, at the high level: 1. bob sends in a deposit that alice verifies she can spend after a certain amount of time. However if bob follows the protocol, he can reclaim this refund before alice is eligible to. 2. alice verifies the above is in the blockchain so is assured that worst case she can get the deposit, which is 113% of the transaction amount, so she might actually prefer that. when assured she sends bob a payment that requires both secrets to be spent. 3. bob sees this on the altcoin chain and sends in a payment to alice that requires a secret from alice that would allow him to spend the payment from 2. 4. alice sees this real payment and then cashes in the bitcoins, but in doing so has to divulge the secret bob needs to spend the altcoins 5. bob gets the required secret from alice and spends the altcoins So the high level concepts are to advance to each stage only when you are assured that the other side is following the protocol and the FSM is setup so that if either party bails at any point, the funds in limbo can be reclaimed. To verify this, the bitcoin scripts must be understood in detail. I see no other way. Conceptually, it is a single pull, double throw switch where a single random number releases two transactions James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 25, 2016, 02:22:45 AM I would be grateful if you or TierNolan could actually answer my question? Stated in another way, what prevents Bob from finalizing the transaction on the block chain with Bitcoin CLTV op code, taking the funds from Alice, while also not issuing the reciprocal transaction paying to Alice on the other block chain? I seem to never get a straight answer. In order to spend the funds from Alice, bob has to disclose the random number Alice can use to spend the bitcoins Afaics, you have not answered my question. Please read my question again. I didn't ask how Bob finalizes the payment from Alice to Bob. I asked, "while also not issuing the reciprocal transaction paying to Alice on the other block chain?". Alice can't spend Bitcoins, because Bob is issuing a transaction on a block chain that is not Bitcoin (and doesn't support CLVT). Are you implying that Bob will issue his transaction first (paying to Alice) on the block chain without a CLVT op code? Then how does Bob get a refund if Alice doesn't complete her side of the transaction and how can Bob's transaction be verified against a hash of a random number when the CLVT op code isn't supported. Ignoring fees, at the high level: 1. bob sends in a deposit that alice verifies she can spend after a certain amount of time. However if bob follows the protocol, he can reclaim this refund before alice is eligible to. You've apparently swapped the block chains of Alice and Bob relative to scenario I described. But that is okay, I will follow your choice, where Bob is transacting on the block chain with CLTV and Alice is not. The transaction above signed by Bob I assume requires CLTV (Check-Lock-Time-Verify) since it must be refunded if it is not verified before the timeout of the lock. 2. alice verifies the above is in the blockchain so is assured that worst case she can get the deposit, which is 113% of the transaction amount, so she might actually prefer that. when assured she sends bob a payment that requires both secrets to be spent. I don't understand how Alice can receive the CLTV output unless she already knows how to verify it. But if she knows how to verify it, then she can steal it at any time. How can Alice send a payment that requires verification of two secrets if the other block chain doesn't support pay contingent on verification of hash preimage? 3. bob sees this on the altcoin chain and sends in a payment to alice that requires a secret from alice that would allow him to spend the payment from 2. Bob issued the deposit in #1 and now he also issues another payment to Alice, but which is spendable by Alice contingent on knowing the preimage (secret) of a hash. Only Alice knows this secret preimage at this point until she reveals it. I thus understand this step #3. 4. alice sees this real payment and then cashes in the bitcoins, but in doing so has to divulge the secret bob needs to spend the altcoins I am disputing whether Alice can make such a transaction available in step #2 if her altcoin doesn't support pay contingent on verification of hash preimage. Edit: I understand you want to use a forfeitable deposit to ensure that Bob does step #3, since Alice has no way to refund step #2 (because her block chain doesn't support CLTV). I presume you are assuming that the altcoin supports pay contingent on verification of hash preimage. But I still don't see how the mechanics of the forfeitable deposit work? "I don't understand how Alice can receive the CLTV output unless she already knows how to verify it. But if she knows how to verify it, then she can steal it at any time." Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 25, 2016, 03:36:35 AM I would be grateful if you or TierNolan could actually answer my question? Stated in another way, what prevents Bob from finalizing the transaction on the block chain with Bitcoin CLTV op code, taking the funds from Alice, while also not issuing the reciprocal transaction paying to Alice on the other block chain? I seem to never get a straight answer. In order to spend the funds from Alice, bob has to disclose the random number Alice can use to spend the bitcoins Afaics, you have not answered my question. Please read my question again. I didn't ask how Bob finalizes the payment from Alice to Bob. I asked, "while also not issuing the reciprocal transaction paying to Alice on the other block chain?". Alice can't spend Bitcoins, because Bob is issuing a transaction on a block chain that is not Bitcoin (and doesn't support CLVT). Are you implying that Bob will issue his transaction first (paying to Alice) on the block chain without a CLVT op code? Then how does Bob get a refund if Alice doesn't complete her side of the transaction and how can Bob's transaction be verified against a hash of a random number when the CLVT op code isn't supported. Ignoring fees, at the high level: 1. bob sends in a deposit that alice verifies she can spend after a certain amount of time. However if bob follows the protocol, he can reclaim this refund before alice is eligible to. You've apparently swapped the block chains of Alice and Bob relative to scenario I described. But that is okay, I will follow your choice, where Bob is transacting on the block chain with CLTV and Alice is not. The transaction above signed by Bob I assume requires CLTV (Check-Lock-Time-Verify) since it must be refunded if it is not verified before the timeout of the lock. 2. alice verifies the above is in the blockchain so is assured that worst case she can get the deposit, which is 113% of the transaction amount, so she might actually prefer that. when assured she sends bob a payment that requires both secrets to be spent. I don't understand how Alice can receive the CLTV output unless she already knows how to verify it. But if she knows how to verify it, then she can steal it at any time. How can Alice send a payment that requires verification of two secrets if the other block chain doesn't support pay contingent on verification of hash preimage? 3. bob sees this on the altcoin chain and sends in a payment to alice that requires a secret from alice that would allow him to spend the payment from 2. Bob issued the deposit in #1 and now he also issues another payment to Alice, but which is spendable by Alice contingent on knowing the preimage (secret) of a hash. Only Alice knows this secret preimage at this point until she reveals it. I thus understand this step #3. 4. alice sees this real payment and then cashes in the bitcoins, but in doing so has to divulge the secret bob needs to spend the altcoins I am disputing whether Alice can make such a transaction available in step #2 if her altcoin doesn't support pay contingent on verification of hash preimage. Edit: I understand you want to use a forfeitable deposit to ensure that Bob does step #3, since Alice has no way to refund step #2 (because her block chain doesn't support CLTV). I presume you are assuming that the altcoin supports pay contingent on verification of hash preimage. But I still don't see how the mechanics of the forfeitable deposit work? "I don't understand how Alice can receive the CLTV output unless she already knows how to verify it. But if she knows how to verify it, then she can steal it at any time." The altcoin payment on the network that doesnt support CLTV is an ordinary multisig that uses the pubkeys from the temp privkeys. This is the key that allows the single pull double throw, the fact that on the BTC blockchain it is just a random number that hashes to the previously specified value. It is actually the privkey that makes pubkey that is put into a 2of2 multisig. I know you dont like scripts, but please bear with me: OP_2 <alice_pubM> <bob_pubN> OP_2 OP_CHECKMULTISIG The above is an original standard multisig, not even the p2sh form, so basically all altcoins using bitcoin 0.7 (or even 0.5?) support it. the alice_pubM is the pubkey from the temporary privkey that was selected by bob during the cut and choose. similarily bob_pubN is the pubkey from the temporary privkey that was selected by alice during the cut and choose. In order to spend the 2 of 2 multisig, both privkeys are needed. Alice has the privkey for the alice_pubM and bob has the privkey for bob_pubN. So if during the protocol, either party gets the other privkey, then and only then can they spend this. The protocol (and FSM based on it) follow blockchain verifiable steps to allow each side to progress incrementally to the next state where eventually either both sides can get their corresponding payments, or it unwinds and they get their funds back. This is impossible at first sight, but this is where the evil genius of TierNolan comes in. The scripts for the deposit and payment that are timelocked to prevent the wrong side from being able to spend it, even if they have the required keys. So it does require both sides to actively protect their interests and do the spends that they are able to. If they dont, after the timer expires, the other side would. But this is all automated in the protocol. So if at the high level you can agree that it is theoretically possible that if we can setup the corresponding payment to the 2of2 multisig that enables the opposite party to spend the corresponding payment, we get atomicity. And that is what the atomic protocol purportedly does and thus requires scrutiny of the FSM and scripts to verify. OP_IF <now + INSTANTDEX_LOCKTIME> OP_CLTV OP_DROP <bob_pubB1> OP_CHECKSIG OP_ELSE OP_HASH160 <hash(alice_privM)> OP_EQUALVERIFY <alice_pubA0> OP_CHECKSIG OP_ENDIF I know you dont like scripts, but hopefull the possibility of non-impossibilty is conveyed. In the above, the first case is only spendable by bob as it does a CHECKSIG against his pubkey, but it cannot be done until after the locktime passes. the other case allows alice and only alice to spend it as her signature is verified, but it also requires alice to divulge the privM key, which once it is divulged can be used to sign the 2of2 multisig, along with verify that the cut and choose wasnt cheated on. Granted, this is the point where alice can refuse, but in such case, time passes and bob can spend it just by waiting. So this protocol barely works as if any script is wrong or cltv isnt existing or multisig doesnt work or ..., but assuming we didnt miss any case, it works, is atomic and blockchain verified, with the cut and choose offering a probabilistic penalty to make cheating at cut and choose uneconomical. The intricacies of using conditional scripts that allow different parties to spend the same tx and requiring part of it to have a delay, is what is at the same time confusing, but also enables atomicity. Without the time delay, then yes the other party can spend right away. And getting it setup so the altcoin side uses only standard multisig is a thing of beauty. I dont quite have it fully debugged, but so far I am only finding minor issues in the protocol itself. It has gone from an impractical "both coins must have CLTV" protocol that would allow trading just a few coins, to a protocol that should work with 100+ variety James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 25, 2016, 03:55:46 AM Some details have changed, but the original spec from the other thread were this came from:
1) Cut and choose Bob generates 1000 keypairs and sends hash(bob_priv_n) and bob_pub_n to Alice for each n (1 to 1000). Alice picks n from 1 to 1000 and Bob sends bob_priv_n for the 999 other n's. If they are ok, then Alice assumes the pair she didn't see is valid. Similarly, Alice generates 1000 key pairs and has Bob choose. This gives the following public info. hash(bob_priv_n) matches bob_pub_n hash(alice_priv_m) matches alice_pub_m There is a 0.1% chance of fraud for each attempt. This means that fees must be at least 0.1% of the transaction value. In that way, there is no incentive to cheat at the cut-and-choose. 2) Bob pays D to Code: OP_IF <now + 2 days> OP_CLTV OP_DROP <alice_pub_1001> OP_CHECKSIG OP_ELSE OP_HASH160 <hash(bob_priv_n)> OP_EQUALVERIFY <bob_pub_1001> OP_CHECKSIG OP_ENDIF D should be more valuable than the value of the Bitcoins or altcoins. This is a promise by Bob to release bob_priv_n within 2 days (or lose his deposit). 3) Alice pays a altcoins to Code: OP_2 <bob_pub_n> <alice_pub_m> OP_2 OP_CHECKMULTISIG 4) Bob pays b Bitcoins to Code: OP_IF <now + 1 day> OP_CLTV OP_DROP <bob_pub_1002> OP_CHECKSIG OP_ELSE OP_HASH160 <hash(alice_priv_m)> OP_EQUALVERIFY <alice_pub_key_1001> OP_CHECKSIG OP_ENDIF Alice has 1 day to claim her output, but that means she must provide alice_priv_m. 5) Alice spends the output (and provides alice_priv_m). 6) Bob can spend the altcoin output (since he has both keys) 7) Bob reclaims his deposit This is atomic and it is recoverable if either party refuses to complete a step. 1) Either party refuses to perform cut-and-choose. Nothing has been sent to either chain, so no harm done. 2) Bob refuses to pay deposit. Nothing has been sent to either chain, so no harm done. 3) Alice refuses to bail-in. Bob reclaims his D after 2 days. Releasing bob_priv_n has no effect since there was no bail-in by Alice, so the key is never used. 4) Bob refuses to bail-in If Bob reclaims his deposit, then Alice will have both private keys and can reclaim her bail-in. If Bob fails to claim his deposit, then Alice gets that as compensation instead of her bail-in. In that case, Bob loses his deposit and can't claim the altcoins. This means he should reclaim his output. 5) Alice refuses to claim her Bitcoins 1 day later Bob can reclaim his Bitcoins Alice gets her altcoins back or she gets D instead (if Bob doesn't reclaim his deposit). 6) Bob refuses to claim his altcoins He loses his altcoins when he reclaims his deposit. Alice already has his Bitcoins by this point. He has an incentive to complete this step. 7) Bob refuses to claim his deposit He loses his deposit and Alice gets it. He has an incentive to complete this step. For each step, there is either an incentive to complete the step or failure to complete the step causes the protocol to abort. In an abort, the incentives are to perform a clean abort. ### There is plain english description FSM embodiment of the english description and the scripts Not sure what part you feel is not a "straight answer" Maybe you can zoom in to a specific step (state) with a specific scenario? The problem is that this solution depends on exact behavior of the scripts, so without detailed understanding of them it is only possible to get a general idea. You probably dont want to see the 2000 lines of C code that implements this either. I am trying to find an FSM visualizer so it can convert my FSM description into pretty circles and boxes with lines connecting them, but graphics apps are not my speciality. the FSM spec is just to define the name of the state and the name of the state if things timeout using the createstate function. Once a state is created the addevent function adds an event to that state that it looks for and the next state it goes to along with the event message it sends to the other side. James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 25, 2016, 06:49:22 AM This is a promise by Bob to release bob_priv_n within 2 days (or lose his deposit). The insoluble flaw will always remain (no matter how you structure the deposit) that either Alice can refuse to do the succeeding transaction and thus Bob loses his deposit (and if the deposit is paid to Alice then she steals this amount), or if you allow Bob to refund the deposit, then Bob can refuse to do the next step after Alice issues her transaction and thus Alice will lose her funds. 2) ... OP_HASH160 <hash(bob_priv_n)> OP_EQUALVERIFY <bob_pub_1001> OP_CHECKSIG [...] 3) ... OP_2 <bob_pub_n> <alice_pub_m> OP_2 OP_CHECKMULTISIG I now understand the intent of the cut & choose that Alice is 99.9% certain (precise % depends on number of key pairs in the challenge session of step #1) that <bob_pub_n> is signable with bob_priv_n, so that when Bob releases bob_priv_n after step #4 to refund his deposit, then Alice sure she can sign for Bob's transaction in order to spend it. But that doesn't protect Alice. Bob can release his private key before step #4, thus refunding his deposit to himself and Alice's funds are forever locked because her block chain doesn't support CLTV. Alice doesnt send the altpayment to the msig address until after she confirms the deposit is confirmed. Bob has to wait for maxtime period before he can claim it. Bob has the altpayment, but cant spend it at this point. But as you say, he can claim the deposit. But notice that in order to claim his deposit back, he must reveal the privM to spend the script: OP_HASH160 <hash(bob_priv_n)> OP_EQUALVERIFY <bob_pub_1001> OP_CHECKSIG Alice then is waiting to see this on the blockchain and can then reclaim the altpayment. If Bob tries to wait alice out, then she is able to cash in the deposit as the CLTV timeout expires. This is why I implemented it as a state machine. That was as each step of the protocol is advanced, the choices to each side is limited and as near as we can tell, all paths lead to recovery of all funds or the trade completing. Of course, it is possible that there is an undetected flaw and we look forward to identification of the state and event that exposes this flaw. However if each state of the FSM has no specific flaw, then as unlikely as it is, the entire protocol must work. The fact it is done as FSM should actually allow a mathematical proof to be created, but such math (graph theory?) is beyond me. Once the FSM is validated, then as long as the code is properly detecting events then I think we get close to having a very solid and peer reviewed implementation. Clearly, loss of capital is the biggest potential flaw and it must be certain that no such thing is possible before delving into the secondary attacks about locking up funds for limited periods of time, etc. James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 25, 2016, 06:57:28 AM Quote from: TPTB_need_war link=topic=1364951.msg14002053#msg14002053 As I wrote many moons ago in this thread, there is simply no way to do DE unless both block chains support CLTV. I told you the generative essence reason is because there is no reference point: Well I cannot respond to any general statement, so lets find specific flaws that exist as specific points in the protocol. I dont think you are able to prove a negative statement, so we must stick to specific states that can be abused.And so will everyone else get Bob's private key and a miner who wins the block can spend his output before his transaction is confirmed on the block chain. My point is that once Bob releases this private key, anyone can spend his UXTO to any payee else besides Alice. Thus I am asserting the cut & choose doesn't work, unless someone can explain to me my mistake. The bitcoin utxo are protected by both the signatures that are required from the "real" privkey and the random number (alice_privM or bob_privN) from the protocol. So maybe there is a flaw with some script as stated, but you seem to not hear that there are TWO DIFFERENT privkeys required to do most of the spends. One of them is the temporary privkey from the 1000 cutandchoose keypairs. The OTHER privkey is one that is NEVER disclosed, only used to sign the tx to spend it. So the protocol does not allow anybody to spend it, only Bob can spend outputs meant for Bob and only Alice can spend output meant for her. Your assertion that anybody can spend the funds is missing the fact that only Alice has the privkey needed to sign the tx and only Bob has the privkey needed to sign the tx, and those privkeys are NOT disclosed James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 25, 2016, 07:13:24 AM I deleted the prior version of this post a few moments after posting it, because I realized I had an error and I wanted to take a moment to think about it before reposting. I didn't realize jl777 has already replied within those few moments, until I had already deleted it and saw his post when the page reloaded.
This is a promise by Bob to release bob_priv_n within 2 days (or lose his deposit). The insoluble flaw will always remain (no matter how you structure the deposit) that either Alice can refuse to do the succeeding transaction and thus Bob loses his deposit (and if the deposit is paid to Alice then she steals this amount), or if you allow Bob to refund the deposit, then Bob can refuse to do the next step after Alice issues her transaction and thus Alice will lose her funds. Or as I wrote days ago (see self quotes below), the private keys get revealed and anyone can spend a transaction to themselves. 2) ... OP_HASH160 <hash(bob_priv_n)> OP_EQUALVERIFY <bob_pub_1001> OP_CHECKSIG [...] 3) ... OP_2 <bob_pub_n> <alice_pub_m> OP_2 OP_CHECKMULTISIG I now understand the intent of the cut & choose that Alice is 99.9% certain (precise % depends on number of key pairs in the challenge session of step #1) that <bob_pub_n> is signable with bob_priv_n, so that when Bob releases bob_priv_n before step #4 to refund his deposit, then Alice is sure she can sign for Bob's transaction in order to spend it back to herself. At that point Bob doesn't have Alice's private key, and Alice never releases this private key, thus only she can sign back her transaction to herself. Whereas if Bob issues the reciprocal payment to Alice in step #4, Alice releases her private key (so she can claim Bob's payment from step #4) then Bob can sign using his private key (which remains private until he issues the refund for his deposit) to spend Alice's payment from step #3. But the problem remains that when private keys are revealed, then anyone can spend the payment from Alice. One might argue that Bob will wait to refund the deposit until after the payment from Alice to Bob has been confirmed spent by Bob, but an attacker with sufficient hashrate can revert the order of the transactions and steal Bob's payment. Remember you are proposing to have many of these DE transactions occurring simultaneously and you are thus incentivizing someone to attack the block chain with hashrate to steal value. Normally even a 51% attacker can't steal someone else's coins (only double-spend their own coins), yet you are proposing to open a new attack vector funding 51% attacks with other people's coins! That is a non-starter, because it weakens the entire coin's security (because adds a new source of funding for 51% attacks). Perhaps you have just identified a reason that multi-sig transactions should always have their destination address hard-coded. I think you've identified a security hole in the current OP code for multi-sig. Even if it were possible to structure a Bitcoin transaction such that Bob signs for his refund instead of releasing the private key, that wouldn't help you, because then Alice couldn't refund herself when Bob fails to do step #4. As I wrote many moons ago in this thread, there is simply no way to do DE unless both block chains support CLTV. I told you the generative essence reason is because there is no reference point: And so will everyone else get Bob's private key and a miner who wins the block can spend his output before his transaction is confirmed on the block chain. My point is that once Bob releases this private key, anyone can spend his UXTO to any payee else besides Alice. Thus I am asserting the cut & choose doesn't work, unless someone can explain to me my mistake. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 25, 2016, 07:43:30 AM I deleted the prior version of this post a few moments after posting it, because I realized I had an error and I wanted to take a moment to think about it before reposting. I didn't realize jl777 has already replied within those few moments, until I had already deleted it and saw his post when the page reloaded. I am not sure what specific attack you are saying exists, as I have explained about the two required signatures.This is a promise by Bob to release bob_priv_n within 2 days (or lose his deposit). The insoluble flaw will always remain (no matter how you structure the deposit) that either Alice can refuse to do the succeeding transaction and thus Bob loses his deposit (and if the deposit is paid to Alice then she steals this amount), or if you allow Bob to refund the deposit, then Bob can refuse to do the next step after Alice issues her transaction and thus Alice will lose her funds. Or as I wrote days ago (see self quotes below), the private keys get revealed and anyone can spend a transaction to themselves. 2) ... OP_HASH160 <hash(bob_priv_n)> OP_EQUALVERIFY <bob_pub_1001> OP_CHECKSIG [...] 3) ... OP_2 <bob_pub_n> <alice_pub_m> OP_2 OP_CHECKMULTISIG I now understand the intent of the cut & choose that Alice is 99.9% certain (precise % depends on number of key pairs in the challenge session of step #1) that <bob_pub_n> is signable with bob_priv_n, so that when Bob releases bob_priv_n before step #4 to refund his deposit, then Alice is sure she can sign for Bob's transaction in order to spend it back to herself. At that point Bob doesn't have Alice's private key, and Alice never releases this private key, thus only she can sign back her transaction to herself. Whereas if Bob issues the reciprocal payment to Alice in step #4, Alice releases her private key (so she can claim Bob's payment from step #4) then Bob can sign using his private key (which remains private until he issues the refund for his deposit) to spend Alice's payment from step #3. But the problem remains that when private keys are revealed, then anyone can spend the payment from Alice. One might argue that Bob will wait to refund the deposit until after the payment from Alice to Bob has been confirmed spent by Bob, but an attacker with sufficient hashrate can revert the order of the transactions and steal Bob's payment. Remember you are proposing to have many of these DE transactions occurring simultaneously and you are thus incentivizing someone to attack the block chain with hashrate to steal value. Normally even a 51% attacker can't steal someone else's coins (only double-spend their own coins), yet you are proposing to open a new attack vector funding 51% attacks with other people's coins! That is a non-starter, because it weakens the entire coin's security (because adds a new source of funding for 51% attacks). Perhaps you have just identified a reason that multi-sig transactions should always have their destination address hard-coded. I think you've identified a security hole in the current OP code for multi-sig. Even if it were possible to structure a Bitcoin transaction such that Bob signs for his refund instead of releasing the private key, that wouldn't help you, because then Alice couldn't refund herself when Bob fails to do step #4. As I wrote many moons ago in this thread, there is simply no way to do DE unless both block chains support CLTV. I told you the generative essence reason is because there is no reference point: And so will everyone else get Bob's private key and a miner who wins the block can spend his output before his transaction is confirmed on the block chain. My point is that once Bob releases this private key, anyone can spend his UXTO to any payee else besides Alice. Thus I am asserting the cut & choose doesn't work, unless someone can explain to me my mistake. The only new attack vector I see that I have not already addressed (plz correct me if I missed any specific attack) is the hashrate used to reverse transactions. This is solved by waiting for enough confirms appropriate to the value of the tx. Enough time is there in the protocol for an hour or two, so if needed, then 10 or even 30 confirms can be waited for before committing to the next step. If you are saying that now there are attackers that can undo 10 or 30 blocks, then I would need to see the type of hashrate is required for that and adjust the recommended number of confirms. PLEASE stick to specific attacks. General statements are fine, but I cannot make any specific response. You say you are convinced it cant work in general, I say I think it can. OK, so no need to be opinion based, when there is a FSM with specific scripts let us use the following as a reference to make sure we are speaking of the same states: ### This is atomic and it is recoverable if either party refuses to complete a step. 1) Either party refuses to perform cut-and-choose. Nothing has been sent to either chain, so no harm done. 2) Bob refuses to pay deposit. Nothing has been sent to either chain, so no harm done. 3) Alice refuses to bail-in. Bob reclaims his D after 2 days. Releasing bob_priv_n has no effect since there was no bail-in by Alice, so the key is never used. 4) Bob refuses to bail-in If Bob reclaims his deposit, then Alice will have both private keys and can reclaim her bail-in. If Bob fails to claim his deposit, then Alice gets that as compensation instead of her bail-in. In that case, Bob loses his deposit and can't claim the altcoins. This means he should reclaim his output. 5) Alice refuses to claim her Bitcoins 1 day later Bob can reclaim his Bitcoins Alice gets her altcoins back or she gets D instead (if Bob doesn't reclaim his deposit). 6) Bob refuses to claim his altcoins He loses his altcoins when he reclaims his deposit. Alice already has his Bitcoins by this point. He has an incentive to complete this step. 7) Bob refuses to claim his deposit He loses his deposit and Alice gets it. He has an incentive to complete this step. For each step, there is either an incentive to complete the step or failure to complete the step causes the protocol to abort. In an abort, the incentives are to perform a clean abort. ### Where in the above can either party get funds from the other that they shouldnt be able to? James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 25, 2016, 07:46:38 AM I don't want to repeat myself. You will destroy the security of the coin by enabling the hashrate attacker to steal other people's coins. This was not possible before (rather before an attacker could only attempt to double-spend his own coins), thus such an attack was not well funded. You are proposing to fund 51% attacks. I hope you understand that hashrate is rentable and the implications of that. Especially when you are proposing to exchange between altcoins which have very low hashrate security (note Alice's multi-sig occurs on the altcoin not on Bitcoin).
Sorry the cut & choose proposal must be scrapped. Stick with the CLTV on both block chains where the destination addresses are hard-coded and thus can't be stolen by a hashrate attacker. That is technically sound. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 25, 2016, 07:51:08 AM I don't want to repeat myself. You will destroy the security of the coin by enabling the hashrate attacker to steal other people's coins. This was not possible before (rather before an attacker could only attempt to double-spend his own coins), thus such an attack was not well funded. You are proposing to fund 51% attacks. I hope you understand that hashrate is rentable and the implications of that. I understand hashrate is rentable.Sorry your proposal must be scrapped. Stick with the CLTV on both block chains. That is sound. Please explain how a 1BTC value for atomic swap is financing a 51% attack. How many coins can be attacked with 1BTC of hashrate? and realistically how many blocks can be reorged we are not talking about doing 100BTC swaps as the norm. Most will be 1BTC worth or less James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 25, 2016, 07:52:40 AM I don't want to repeat myself. You will destroy the security of the coin by enabling the hashrate attacker to steal other people's coins. This was not possible before (rather before an attacker could only attempt to double-spend his own coins), thus such an attack was not well funded. You are proposing to fund 51% attacks. I hope you understand that hashrate is rentable and the implications of that. I understand hashrate is rentable.Sorry your proposal must be scrapped. Stick with the CLTV on both block chains. That is sound. Please explain how a 1BTC value for atomic swap is financing a 51% attack. How many coins can be attacked with 1BTC of hashrate? and realistically how many blocks can be reorged we are not talking about doing 100BTC swaps as the norm. Most will be 1BTC worth or less James Why do you assume only one DE transaction will be ongoing on a block chain simultaneously. And why do you assume that DE transactions will be limited to 1 BTC. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 25, 2016, 08:00:15 AM I don't want to repeat myself. You will destroy the security of the coin by enabling the hashrate attacker to steal other people's coins. This was not possible before (rather before an attacker could only attempt to double-spend his own coins), thus such an attack was not well funded. You are proposing to fund 51% attacks. I hope you understand that hashrate is rentable and the implications of that. I understand hashrate is rentable.Sorry your proposal must be scrapped. Stick with the CLTV on both block chains. That is sound. Please explain how a 1BTC value for atomic swap is financing a 51% attack. How many coins can be attacked with 1BTC of hashrate? and realistically how many blocks can be reorged we are not talking about doing 100BTC swaps as the norm. Most will be 1BTC worth or less James Why do you assume only one DE transaction will be ongoing on a block chain simultaneously. And why do you assume that DE transactions will be limited to 1 BTC. Also, how can a PoS coin be attacked using this? Does this mean that PoS coins are more secure as atomic altcoins than PoW? I dont want to start a holy war re PoS vs PoW, just trying to quantify risks. If indeed an attacker can spawn 100BTC worth of swaps, use funds to buy hashrate to reverse tx, then indeed this needs to be addressed. Tracking pending trades or limiting to PoS coins comes to mind, but I am tired and that is just the initial reaction, there should be more potential solutions James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 25, 2016, 08:06:05 AM Also, how can a PoS coin be attacked using this? Does this mean that PoS coins are more secure as atomic altcoins than PoW? Unlike hashrate (electricity), stake only has to be purchased once and attack forever, so therefor rental prices for stake should be much lower (since stake costs less than hashrate). I think we solved the jamming problem with CLTV version of DE. So there was a positive outcome from this thread. I am happy that DE can work. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 25, 2016, 08:21:06 AM Also, how can a PoS coin be attacked using this? Does this mean that PoS coins are more secure as atomic altcoins than PoW? Unlike hashrate (electricity), stake only has to be purchased once and attack forever, so therefor rental prices for stake should be much lower (since stake costs less than hashrate). I think we solved the jamming problem with CLTV version of DE. So there was a positive outcome from this thread. I am happy that DE can work. "stake costs less than hashrate" this appears to be the same as saying donuts cost less than springs. Sometimes the stake required to attack will cost more than hashrate and vice versa. So it all depends on the specific coins being talked about. And I am not thinking it is so easy to cause deep reorgs at will. It could be that the DE for low security coins needs to be done over longer periods of time and in small increments, ie overlapped micropayment channels. I am not conviced by general statements, especially when they have counterexamples that prove they are incorrect. I can easily name many PoS coins that are more expensive to obtain stake enough to attack against a set of PoW coins whose hashrate is lower. Sorry, general scare statements dont work on me. Only specific failure cases, which can then be generalized and solutions usually devised. I know that if I just say, sure in theory it wont work and dont push for a solution, then it would limit things to BTC <-> LTC and gradually more and more, so at worst it is a slow process, but we dont have to outrun the bear, we just need to be more secure than a CE. James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 26, 2016, 01:15:57 AM I think we solved the jamming problem with CLTV version of DE. So there was a positive outcome from this thread. I am happy that DE can work. Yes scrutiny leads to progress. I think we should celebrate TierNolan's original protocol, the implementation of CLTV in Bitcoin recently, and now my added improvement of "Coin Days Destroyed" to squelch jamming. DE can be a reality! Hooray! I am excited about you implementing this. All altcoins that are excited too, need to implement CLTV. Also, how can a PoS coin be attacked using this? Does this mean that PoS coins are more secure as atomic altcoins than PoW? Unlike hashrate (electricity), stake only has to be purchased once and attack forever, so therefor rental prices for stake should be much lower (since stake costs less than hashrate). "stake costs less than hashrate" this appears to be the same as saying donuts cost less than springs. Sometimes the stake required to attack will cost more than hashrate and vice versa. So it all depends on the specific coins being talked about. I am making a mathematical asymptotic argument similar conceptually to the arguments about Big O and Big Theta computational complexity classes (wherein at any particular/small values the conclusion might be opposite of the asymptotic reality). The point is mathematical structure in that stake only has to be purchased once, whereas electricity has to be paid continuously. Thus in terms of mathematical structure (all other variables the same, e.g. market cap, etc), then hashrate will be structurally more expensive than stake. Stake is not as secure as hashrate because stake is paid once for an eternal attack and hashrate must be paid continuously else the attack ends (is finite in duration). In short, stake enables an infinite duration attack (at no extra cost) and thus stake is free and hashrate is finite and thus it is not free. If you don't believe that, then just consider that one can short a PoS coin (thus recovering the cost of the stake making it less than free) and the market is likely to sell off the coin during any stake-based attack because the market understands the only way to overcome the attack is to fork the coin. Whereas with PoW, the market may ignore the attack because it will be ephemeral unless the attacker can profit from the attack enough to pay for the ongoing cost of the electricity. This is the fundamental reason that PoS is not secure. Apparently some PoS coins have been attacked with stake (https://bitcointalk.org/index.php?topic=1319681.msg13488432#msg13488432), and the common case are the exchanges which control huge amounts of stake. And I am not thinking it is so easy to cause deep reorgs at will. It could be that the DE for low security coins needs to be done over longer periods of time and in small increments, ie overlapped micropayment channels. I presume I did not adequately explain the economic argument. The point is that once you incentivize profitable PoW attacks, the attacker can now sustain an attack indefinitely (or the DE is abandoned). Thus there is no longer period of time which is sufficient (from a mathematical structural perspective, although there might be particular cases that are secure, you can't state them with equations that enable reliable decisions). I understand you want to find some reasonable middle ground, but I presume you would play with fire if you pursued this similar to those who argued that PoS was an acceptable middle ground (yet even today we see that Bitshares' DPOS is probably controlled by a few exchanges and I think someone told me Nxt is controlled by a dictator). I comprehend and am aware of the stance that says nothing is perfect and choose some practical middle ground. But I argue we can do better than some muddled middle ground where for example Bitcoin is already controlled by a Chinese mining cartel that has 65% of the hashrate and is provably lying about the Great Firewall of China being a hindrance for them (their motivation is obviously to make higher profits with higher transaction fees by constraining block size). This outcome I predicted in 2013 (https://bitcointalk.org/index.php?topic=340686.0), even I nailed in 2013 the block size as the specific failure mode (https://bitcointalk.org/index.php?topic=340686.msg3681159#msg3681159), and everyone was arguing at that time that I was loony (https://bitcointalk.org/index.php?topic=336350.0). Their % of the hashrate will increase on the next block reward halving this year, because the marginally profitable miners are the first to go (and I suspect the Chinese mining cartel is getting subsidized electricity with political connections/corruption). You can make the reasonable argument that the insecurity of the proposed cut & choose algorithm only impacts those altcoins without CLTV and thus it is better than no DE for those coins. In that case, maybe I can agree with that. But do fully acknowledge the Pandora's box security threat so enabled (but at least isolated to those who trade for those altcoins). Thus I don't think it will be a very popular case, if proper disclosures are made. Who would trade BTC for an altcoin where they might lose their funds due to an attack (particularly even a long-range lie-in-wait attack) and where the developers of that altcoin are unable to add the CLTV op code. I am not conviced by general statements, especially when they have counterexamples that prove they are incorrect. I can easily name many PoS coins that are more expensive to obtain stake enough to attack against a set of PoW coins whose hashrate is lower. Of course there are scenarios where a PoW coin pays less % of debasement to mining thus requires less cost for a short-term attack than a PoS coin with a huge market cap. This is primarily because Satoshi's PoW design is incorrect. I have a solution to this by making mining unprofitable so that no debasement is paid for mining. Both the current PoS and PoW designs are flawed. That is one of the major innovations I am working on. Sorry, general scare statements dont work on me. The generative essence statement I made upthread was referring to the fact that given no reference point, DE would not be secure,. Without a reference point, nothing can be proven about crypto currency (e.g. double-spends can't be prevented, etc), thus the requirement for a reference point is essential (even Satoshi's PoW suffers from the fact that it is probabilistic and didn't solve the Byzantine General's Problem (https://bitcointalk.org/index.php?topic=1183043.msg13823607#msg13823607) because it can't identify an attack from a non-attack because the longest chain rule is self-referential). I can make such a general statement and be 100% certain there is no possible exception, because it is a fundamental inviolable mathematical structural issue. The reference points are provided by my upthread "Coin Days Destroyed" suggestion a few days ago and the point yesterday in this thread about hard-coding the destination addresses in the CLTV. In order words, those reference points do not depend on future confirmations, but are past history (the age of the UXTOs being spent) and future invariants (the hard-coded destinations). I was just starting treatment for fatty liver disease (https://bitcointalk.org/index.php?topic=1219023.msg14010428#msg14010428) over the past 2 days (along with running around getting a diagnosis and other foggy brain matters) so apologies that only this morning did I feel alert enough to write a coherent explanation such as this. Only specific failure cases, which can then be generalized and solutions usually devised. I know that if I just say, sure in theory it wont work and dont push for a solution, then it would limit things to BTC <-> LTC and gradually more and more, so at worst it is a slow process, but we dont have to outrun the bear, we just need to be more secure than a CE. There is a distinction between theory and inviolable mathematical structure. I will give you another example that I learned when I started to teach myself cryptography over the past 3 years. That is zero knowledge proofs are impossible without an asymmetric trap door function, i.e. they can't be done with hash functions. That is not theory. It is an inviolable fact due to the mathematical structure. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 26, 2016, 02:46:38 AM I think we solved the jamming problem with CLTV version of DE. So there was a positive outcome from this thread. I am happy that DE can work. Yes scrutiny leads to progress. I think we should celebrate TierNolan's original protocol, the implementation of CLTV in Bitcoin recently, and now my added improvement of "Coin Days Destroyed" to squelch jamming. DE can be a reality! Hooray! I am excited about you implementing this. All altcoins that are excited too, need to implement CLTV. Also, how can a PoS coin be attacked using this? Does this mean that PoS coins are more secure as atomic altcoins than PoW? Unlike hashrate (electricity), stake only has to be purchased once and attack forever, so therefor rental prices for stake should be much lower (since stake costs less than hashrate). "stake costs less than hashrate" this appears to be the same as saying donuts cost less than springs. Sometimes the stake required to attack will cost more than hashrate and vice versa. So it all depends on the specific coins being talked about. I am making a mathematical asymptotic argument similar conceptually to the arguments about Big O and Big Theta computational complexity classes (wherein at any particular/small values the conclusion might be opposite of the asymptotic reality). The point is mathematical structure in that stake only has to be purchased once, whereas electricity has to be paid continuously. Thus in terms of mathematical structure (all other variables the same, e.g. market cap, etc), then hashrate will be structurally more expensive than stake. Stake is not as secure as hashrate because stake is paid once for an eternal attack and hashrate must be paid continuously else the attack ends (is finite in duration). In short, stake enables an infinite duration attack (at no extra cost) and thus stake is free and hashrate is finite and thus it is not free. If you don't believe that, then just consider that one can short a PoS coin (thus recovering the cost of the stake making it less than free) and the market is likely to sell off the coin during any stake-based attack because the market understands the only way to overcome the attack is to fork the coin. Whereas with PoW, the market may ignore the attack because it will be ephemeral unless the attacker can profit from the attack enough to pay for the ongoing cost of the electricity. This is the fundamental reason that PoS is not secure. Apparently some PoS coins have been attacked with stake (https://bitcointalk.org/index.php?topic=1319681.msg13488432#msg13488432), and the common case are the exchanges which control huge amounts of stake. And I am not thinking it is so easy to cause deep reorgs at will. It could be that the DE for low security coins needs to be done over longer periods of time and in small increments, ie overlapped micropayment channels. I presume I did not adequately explain the economic argument. The point is that once you incentivize profitable PoW attacks, the attacker can now sustain an attack indefinitely (or the DE is abandoned). Thus there is no longer period of time which is sufficient (from a mathematical structural perspective, although there might be particular cases that are secure, you can't state them with equations that enable reliable decisions). I understand you want to find some reasonable middle ground, but I presume you would play with fire if you pursued this similar to those who argued that PoS was an acceptable middle ground (yet even today we see that Bitshares' DPOS is probably controlled by a few exchanges and I think someone told me Nxt is controlled by a dictator). I comprehend and am aware of the stance that says nothing is perfect and choose some practical middle ground. But I argue we can do better than some muddled middle ground where for example Bitcoin is already controlled by a Chinese mining cartel that has 65% of the hashrate and is provably lying about the Great Firewall of China being a hindrance for them (their motivation is obviously to make higher profits with higher transaction fees by constraining block size). This outcome I predicted in 2013 (https://bitcointalk.org/index.php?topic=340686.0), even I nailed in 2013 the block size as the specific failure mode (https://bitcointalk.org/index.php?topic=340686.msg3681159#msg3681159), and everyone was arguing at that time that I was loony (https://bitcointalk.org/index.php?topic=336350.0). Their % of the hashrate will increase on the next block reward halving this year, because the marginally profitable miners are the first to go (and I suspect the Chinese mining cartel is getting subsidized electricity with political connections/corruption). You can make the reasonable argument that the insecurity of the proposed cut & choose algorithm only impacts those altcoins without CLTV and thus it is better than no DE for those coins. In that case, maybe I can agree with that. But do fully acknowledge the Pandora's box security threat so enabled (but at least isolated to those who trade for those altcoins). Thus I don't think it will be a very popular case, if proper disclosures are made. Who would trade BTC for an altcoin where they might lose their funds due to an attack (particularly even a long-range lie-in-wait attack) and where the developers of that altcoin are unable to add the CLTV op code. I am not conviced by general statements, especially when they have counterexamples that prove they are incorrect. I can easily name many PoS coins that are more expensive to obtain stake enough to attack against a set of PoW coins whose hashrate is lower. Of course there are scenarios where a PoW coin pays less % of debasement to mining thus requires less cost for a short-term attack than a PoS coin with a huge market cap. This is primarily because Satoshi's PoW design is incorrect. I have a solution to this by making mining unprofitable so that no debasement is paid for mining. Both the current PoS and PoW designs are flawed. That is one of the major innovations I am working on. Sorry, general scare statements dont work on me. The generative essence statement I made upthread was referring to the fact that given no reference point, DE would not be secure,. Without a reference point, nothing can be proven about crypto currency (e.g. double-spends can't be prevented, etc), thus the requirement for a reference point is essential (even Satoshi's PoW suffers from the fact that it is probabilistic and didn't solve the Byzantine General's Problem (https://bitcointalk.org/index.php?topic=1183043.msg13823607#msg13823607) because it can't identify an attack from a non-attack because the longest chain rule is self-referential). I can make such a general statement and be 100% certain there is no possible exception, because it is a fundamental inviolable mathematical structural issue. The reference points are provided by my upthread "Coin Days Destroyed" suggestion a few days ago and the point yesterday in this thread about hard-coding the destination addresses in the CLTV. In order words, those reference points do not depend on future confirmations, but are past history (the age of the UXTOs being spent) and future invariants (the hard-coded destinations). I was just starting treatment for fatty liver disease (https://bitcointalk.org/index.php?topic=1219023.msg14010428#msg14010428) over the past 2 days (along with running around getting a diagnosis and other foggy brain matters) so apologies that only this morning did I feel alert enough to write a coherent explanation such as this. Only specific failure cases, which can then be generalized and solutions usually devised. I know that if I just say, sure in theory it wont work and dont push for a solution, then it would limit things to BTC <-> LTC and gradually more and more, so at worst it is a slow process, but we dont have to outrun the bear, we just need to be more secure than a CE. There is a distinction between theory and inviolable mathematical structure. I will give you another example that I learned when I started to teach myself cryptography over the past 3 years. That is zero knowledge proofs are impossible without an asymmetric trap door function, i.e. they can't be done with hash functions. That is not theory. It is an inviolable fact due to the mathematical structure. And if BTC data from recent past is good enough for a generative essence from infinite depth reorgs, then if a timeout is set to be past that, dont we have the finite time from attacks (PoW and PoS) and avoid the mathematical apocalypse you write about above. And so, if the DE submitted OP_RETURN data into all the supported altcoins with data from BTC, wouldnt all such chains get a backstop? Considering you said it was impossible on multiple occasions, there must be some basic error with the above. Just like there are external factors that need to be considered for attacks, there can be external factors that can be injected into the defense. So, let us assume we have a bi-directional generative essences of protection. The altcoin chains put into their blockchain data from BTC blockchain of recent past (-2hrs?) and the BTC blockchain in turn puts altcoin data into its blockchain. OP_RETURN can be used on all to put a hash or two in all chains. This creates a supernetwork of interlinked blockchains, doesnt it? With all of them backstopped by BTC making it the foundation technically for all the blockchains. But maybe I misunderstood your objection and the above has a fatal flaw? My analysis is that the DE allows people to trade without using a third party escrow (CE function) and this is more decentralizing as the funds are now mostly in peoples wallets instead of a big giant pile in Big Vern's accounts. So if you are claiming that DE is bad, then I think you need to consider that a CE centralized trading funds across ALL the coins that are traded at once. With DE, let us accept your assertion that it will allow some attacker to reorg any chain at will to any depth, as I am sure I couldnt have solved an impossible problem with this post vs. the practical cost of setting it up. Even with this point asserted, I claim that DE provides a better environment as an attack event affects just that one coin, not ALL coins at the DE. So unless the existing situation of aggregated CE dependency is better for altcoins without CLTV, the DE is an improvement. AND much more importantly, if an altcoin starts trading using the DE, this provides a much stronger impetus for them to add CLTV as compared to the possibility of trading on the DE. My analysis incorporates the big picture that includes getting altcoins to upgrade. As for the coins without dev teams... At least they can keep trading via DE even after all the CE get hacked to bits or discontinue them. Doesnt the DE thus improve the situation for the altcoins? From the BTC maximalist point of view, if a lagging altcoin gets out of favor since it is continually attacked, then the DE acts as a spur to evolve. But primarily the DE reduces the concentration of deposits in the CE and gives people more options. James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 26, 2016, 03:32:09 AM I think if the user can set the timeout values they can decide to accept the risk of blockchain reorg'ed after the swap. Users typically can't make such settings from any knowledgeable stance. They are ignorant of the tradeoffs and technical issues. I firmly believe you must make this decision for them (at least the default), because I believe they will blame you (the decentralized exchange concept) for any failure. I speak from decades of experience of making B2C (not B2B) commercial software for customers. NXT PoS limits any reorgs to 720 blocks, so for NXT if the timeout is set above 720 blocks, then it will be beyond the reach of any attack. That seems reasonable since checkpoints are required in PoS due to people selling their stake and then doing a long-range attack with stake they no longer own based on reorganization of historical transactions that create stake. Anyone who is buying NXT should hopefully understand the tradeoffs of a PoS system (centralized governance, advantage of less electrical consumption, my arguments against PoS in my prior post, etc). Couldnt any coin use data from the BTC blockchain from some hours in the past to create a backstop from massive reorg? By using the massive PoW of BTC, a PoS or weaker PoW would get an externally verifiable reference? Why couldnt that be used as the generative essence you say is required? [...] But maybe I misunderstood your objection and the above has a fatal flaw? I assume you mean writing some meta-data into the stronger block chain, that the weaker block chain could refer to as evidence. The hindrance is that decentralized block chains have no external reference point. There is no way to enforce that a particular block in one chain came before a block (nor within some # of blocks after a block) on another chain. Block chains are self-referential, and that is precisely why we need CLTV to implement decentralized exchange. It is also why Blockstream's side chains have security which is as weak as the weakest side chain (because a reorganization in one chain erases coins that have already been reserved in other chains for maintaining the one-to-one exchange peg), which is btw why afaics Side chains are implausible (hopefully this post won't get deleted by the moderator, hehe). My analysis is that the DE allows people to trade without using a third party escrow (CE function) and this is more decentralizing as the funds are now mostly in peoples wallets instead of a big giant pile in Big Vern's accounts. So if you are claiming that DE is bad, then I think you need to consider that a CE centralized trading funds across ALL the coins that are traded at once. I have agreed. Remember what I wrote upthread: I am trying to think of a way to make this practical and robust enough, unless we are facing a prolonged attack from a super power. I like the ideological intent of DE. I will now review your latest reply with a clearer mind. You won't be able to steal funds, which afaik is the most significant advantage of DE over CE. Thanks to TierNolan et al, we already have a solution employing CLTV on both chains and even squelched the hypothetical jamming with "coin age" filtering. I even wrote that I am excited about you implementing it. I think you are trying to argue for cut & choose, but that is not the only way to do DE. We already have a technically sound solution for DE as stated. I have also stated that the (innovative and clever but yet still economically) technically flawed cut & choose protocol variant might be acceptable if the user understands the risks. With DE, let us accept your assertion that it will allow some attacker to reorg any chain at will to any depth, as I am sure I couldnt have solved an impossible problem with this post vs. the practical cost of setting it up. Even with this point asserted, I claim that DE provides a better environment as an attack event affects just that one coin, not ALL coins at the DE. Seems to me the problem of financially incentivizing long-range chain reorganizations by enabling the attacker to steal coins from the 2 of 2 multisig, will infect every coin. Similarly to how Side chains devolves to the security of the weakest chain. However, a key distinction is that Side chains depend on a fungible one-to-one peg, so the catastrophe is much more pervasive because the failure isn't isolated to the participants to the exchange between chains but to the value of all the coins on the chains. So unless the existing situation of aggregated CE dependency is better for altcoins without CLTV, the DE is an improvement. Much better altcoins are forced to add CLTV and do DE correctly. Why encourage them to be lazy. Let them die with CE (centralized exchange) if they are too damn lazy to implement CLTV. You do what ever you want, but you open Pandora's box. If you need to support Nxt, then I say go ahead. But generally supporting DE via the flawed cut & choose seems unsavory to me, but it is of course your decision. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 26, 2016, 04:03:37 AM I assume you mean writing some meta-data into the stronger block chain, that the weaker block chain could refer to as evidence. The hindrance is that decentralized block chains have no external reference point. There is no way to enforce that a particular block in one chain came before a block (nor within some # of blocks after a block) on another chain. Block chains are self-referential, and that is precisely why we need CLTV to implement decentralized exchange. OK, so we are in agreement on most everything.I want to better understand the above as it seems the main issue to prevent much stronger security. I apologize if I am asking kindergarten level questions on this, but I dont understand the external reference point impossibility. Please bear with me. I like concrete examples: At noon, BTC block noon_txid appears. This is available to the entire bitcoin p2p network. At first it is a bit vulnerable to a reorg due to any pair of linked blocks would override it. After the next block, it would take 3 blocks to overtake, etc. So after 2 hours, we are past the timestamp variance and also have 10+ blocks protected by zillions of hashes. ALL the altcoin chains can refer to this noon_txid. Let us call it noon_txid_inalt. I am pretty sure this is possible to do. And I am pretty sure that the presence of noon_txid_inalt proves that it came AFTER noon_txid. Please let us ignore odds of sha256 collisions. In my previous post, I said bi-directional. So the BTC blockchain now gets the noon_txid_inalt and puts that into its blockchain (a bit past 2PM). call this the noon_altconfirm txid. I claim that we now know that noon_txid happened before noon_txid_inalt which happened before noon_altconfirm txid. It looks like I can segregate blockchain events on different blockchains into definite categories of time ordering of "before" and "after" What part of the above is insufficient to satisfy the requirements for the external reference? James Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 26, 2016, 05:14:37 AM I assume you mean writing some meta-data into the stronger block chain, that the weaker block chain could refer to as evidence. The hindrance is that decentralized block chains have no external reference point. There is no way to enforce that a particular block in one chain came before a block (nor within some # of blocks after a block) on another chain. Block chains are self-referential, and that is precisely why we need CLTV to implement decentralized exchange. OK, so we are in agreement on most everything. I want to better understand the above as it seems the main issue to prevent much stronger security. I apologize if I am asking kindergarten level questions on this, but I dont understand the external reference point impossibility. Please bear with me. Apologies in advance to readers that I will spew a lot of words about the phrase, "kindergarten level questions". I just feel awkward because I don't desire to measure myself or others that way. My intent is all about maximizing production (of myself and others). And I have weaknesses and commit lapses of logic (or insufficient research) sometimes/often. I didn't mean to belittle anyone's sincere inquiries. Apologies if that seemed to be my tone upthread. To any degree that I felt frustration upthread, it was due to for example when someone conflates 'theory' with "highly abstract mathematical structural fact" and my frustration being not with them (for how can they understand my confidence in some insight if I don't explain it to them) because it is my problem if I am too low on energy or time to explain that distinction. Again it isn't the fault of another person that sometimes I am thinking/articulating in abstractions. And I don't make any claim about relative knowledge or capabilities (except to trolls and intentionally condescending people who deserve to have a mirror put in their face, which is not you James). I just tend to think in abstractions often, but not always (obviously I also think in terms of implementation and example cases otherwise I wouldn't have also written 100,000+ lines of commercially successful code as you have James). I just grow weary sometimes, because verbiage on forums has to repeated over and over for each person. I have 10,000+ posts already on this site. Lol. James your effort on implementing DE is worthy of my reciprocal effort (as you know I've told you that I hope your DE is available for the altcoin I am working on). Apologies the past few days have been exhausting/distracting/struggle for me as I alluded to about my health. Also I am reasonably burned out from too many posts on these forums over the past 3 years in contagion with the chronic health debacle/suffering I've been battling. Again apologies if I don't always communicate with perfect attention to apparent tone and with careful/optimum eludication. I like concrete examples: At noon, BTC block noon_txid appears. This is available to the entire bitcoin p2p network. At first it is a bit vulnerable to a reorg due to any pair of linked blocks would override it. After the next block, it would take 3 blocks to overtake, etc. So after 2 hours, we are past the timestamp variance and also have 10+ blocks protected by zillions of hashes. ALL the altcoin chains can refer to this noon_txid. Let us call it noon_txid_inalt. I am pretty sure this is possible to do. And I am pretty sure that the presence of noon_txid_inalt proves that it came AFTER noon_txid. Please let us ignore odds of sha256 collisions. In my previous post, I said bi-directional. So the BTC blockchain now gets the noon_txid_inalt and puts that into its blockchain (a bit past 2PM). call this the noon_altconfirm txid. I claim that we now know that noon_txid happened before noon_txid_inalt which happened before noon_altconfirm txid. It looks like I can segregate blockchain events on different blockchains into definite categories of time ordering of "before" and "after" What part of the above is insufficient to satisfy the requirements for the external reference? There is no way to prove that the consensus of the weaker block chain placed those meta-data records in the stronger block chain. There is some meta-data, but it is meaningless, because consensus is the entire challenge of decentralized protocols that require consensus. Off topic note that per the CAP theorem, Bitcoin forsakes Partition tolerance in order to achieve Consistency and Availability of consensus. You can think of the other block chain as being another partition. We've been discussing these abstract theoretical issues over in the Altcoin Discussion forum in threads such as The Ethereum Paradox (https://bitcointalk.org/index.php?topic=1361602.0), DECENTRALIZED crypto currency (including Bitcoin) is a delusion (any solutions?) (https://bitcointalk.org/index.php?topic=1319681.0), and Satoshi didn't solve the Byzantine generals problem (https://bitcointalk.org/index.php?topic=1183043.0). Also include some discussions between monsterer, smooth, and myself in my vaporcoin's thread. So I have the advantage of a few months of discussions about these abstract topics. Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 26, 2016, 06:57:25 AM There is no way to prove that the consensus of the weaker block chain placed those meta-data records in the stronger block chain. There is some meta-data, but it is meaningless, because consensus is the entire challenge of decentralized protocols that require consensus. Off topic note that per the CAP theorem, Bitcoin forsakes Partition tolerance in order to achieve Consistency and Availability of consensus. You can think of the other block chain as being another partition. We've been discussing these abstract theoretical issues over in the Altcoin Discussion forum in threads such as The Ethereum Paradox (https://bitcointalk.org/index.php?topic=1361602.0), DECENTRALIZED crypto currency (including Bitcoin) is a delusion (any solutions?) (https://bitcointalk.org/index.php?topic=1319681.0), and Satoshi didn't solve the Byzantine generals problem (https://bitcointalk.org/index.php?topic=1183043.0). Also include some discussions between monsterer, smooth, and myself in my vaporcoin's thread. So I have the advantage of a few months of discussions about these abstract topics. So the issue is not time sequence, but the fact that it is hard to know if the weaker chain put the data in there as part of a consensus or as part of an attack? If that is the issue, I am confused why we care so much about it? The metadata in the altcoin chain refers to the BTC data, so why does it matter who put it there? It either matches the BTC data or it doesnt. If it matches, it creates a verifiable time sequence. If it doesnt match, then it would be ignored. Could you make a simple example that shows how an attacker can bypass the BTC "clock" and double spend? I dont think using bitcoin as the reference clock violates the CAP theorem as it defines the bitcoin data as definitive source of data, so Consistency is achieved, along with availability. [I dont want to get into whether bitcoin itself has done this or that with byzantine whatchamacallits] Maybe to solve the Partition part, the metadata for the altcoin metadata needs to get back into the BTC chain. We are talking about a slow process, but even if it takes a day for all the back and forth, it seems that it isnt impossible. I just dont understand what exactly is needed. Maybe it is like spontaneous creation of life from inert chemicals which is (nearly) impossible [please it is just an example, dont want to get into any creation/evolution debate either!], but once it is there, it is hard to stop it from replication. And kind of hard to deny that it exists. Since we now have bitcoin, maybe building on it allows to achieve the desired result (better altcoin security) without any violation of proven theorems by changing the problem. James P.S. CAP seems to vary from principle, conjecture, to theorem based on exact and precise definitions, I dont know if bitcoin is the exactly same behavior as in the proven CAP theorem, or if a bitcoin + extra is unable to change it to be beyond the confines of what is proven. I dont like to fight against math proofs, but if there is any level of abstraction in the proof then it is usually possible to "work around" it by transforming the problem to a different problem that isnt proven impossible. Since I am not trying to disprove the CAP theorem, but rather create a cross chain security mechanism that isnt covered by the CAP theorem proper Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 26, 2016, 10:50:50 AM I don't want to repeat myself. You will destroy the security of the coin by enabling the hashrate attacker to steal other people's coins. You mean that you could steal all trades that sell a particular altcoin by rewinding that altcoin? That means that the altcoin probably has low hash protection. It is a good point though that rewind risk does need to be incorporated into the system. The current implementation has steps that are zero-confirm, you wouldn't want to do that with high value trades. It is slower, but worth it due to the higher risk. A rule of thumb is that 1 block "costs" whatever the block reward is (inc fees). At the moment, it costs 25 BTC to mine a bitcoin block. You could set the minimum confirms to k * (trade_value) / (25 BTC). The k parameter is some protection against multiple trades being attacked together. With a k of 10, a 2.5BTC trade would have a min confirms of 1 block. A 100 BTC trade would have a requirement of 40. If the altcoin pays out 0.5BTC of value per block, then 50 confirms would be required on the altcoin. This is an extra requirement. There would be a minimum number of confirms, no matter how small the trade. Since the fee can be done on bitcoin, which has strong protection, these confirms would be mostly for the altcoin confirm. Another attack would be to stall the altcoin chain. You could make blocks and push up the difficulty so it stalls. I think these attacks mean that the altcoin is weakly protected already. Even a centralised exchange could have problems. They pay you in altcoins and the transaction gets rewound. Having said that, they would probably refund the money. They also do the "lots of confirms" thing. For weak altcoins, exchanges require deposits to have lots of confirms. Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 26, 2016, 08:42:17 PM NXT PoS limits any reorgs to 720 blocks, so for NXT if the timeout is set above 720 blocks, then it will be beyond the reach of any attack. That seems reasonable since checkpoints are required in PoS due to people selling their stake and then doing a long-range attack with stake they no longer own based on reorganization of historical transactions that create stake. Anyone who is buying NXT should hopefully understand the tradeoffs of a PoS system (centralized governance, advantage of less electrical consumption, my arguments against PoS in my prior post, etc). It seems cut & choose with a fee is an appropriate DE protocol for any proof-of-stake coins with frequent checkpoints (that don't support CLTV), which in NXT's case appears to be enforced by nodes that are always online and can form objective reality from the chain they've seen while being online. In other words (an issue which we have discussed and identified in the linked threads I mentioned in my prior post), NXT's 720 block rule is ambiguous to nodes who've recently come online (they don't know which chain was first to appear and can be lied to by a node that has always been online, i.e. propagation is not objective reality to offline nodes), but afaik with proof-of-stake typically there are a more permanent set of nodes (dictators or elected delegates in Bitshare's DPoS) who control the chain, i.e. the coins are essentially centralized. Yesterday monsterer pointed out how PoS can be controlled with even less than 50% of the hashrate (https://bitcointalk.org/index.php?topic=1319681.msg13488432#msg13488432), so kudos to monsterer for articulating our prior insight with more clarity on the weakness of PoS. So an imperfect DE protocol is arguably appropriate for an imperfect So what I am saying is I think you can monetize. I don't know how to monetize with the dual CLTV technically sound protocol (with my suggested "coin age" filtering improvement to squelch jamming attacks), as it seems to not require a fee. Cut & choose seems to be inappropriate for proof-of-work coins due to the longer-range lie-in-wait rented hashrate attack on the probabilistic longest-chain-rule (LCR), unless they too are essentially centralized and have some frequent checkpoints generated by some form (either concentrated hashrate in always online nodes/pools that enforce checkpoints or lead developers who release checkpoints frequently) of centralized control. Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 26, 2016, 09:26:08 PM The reference points are provided by my upthread Although the "coin age" reference points are not absolute, i.e. could be rewritten by a chain reorganization attack, this will not reduce the squelching effect on a jamming attack, because that hashrate attack costs electricity (in PoW) and with the dual CLTV DE protocol, the attacker is not reimbursed. The hard-coded destinations of a dual CLTV DE protocol obviously can't be altered by any hashrate attack so thus are absolute reference points. Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 26, 2016, 11:17:48 PM There is no way to prove that the consensus of the weaker block chain placed those meta-data records in the stronger block chain. There is some meta-data, but it is meaningless, because consensus is the entire challenge of decentralized protocols that require consensus. Off topic note that per the CAP theorem, Bitcoin forsakes Partition tolerance in order to achieve Consistency and Availability of consensus. You can think of the other block chain as being another partition. We've been discussing these abstract theoretical issues over in the Altcoin Discussion forum in threads such as The Ethereum Paradox (https://bitcointalk.org/index.php?topic=1361602.0), DECENTRALIZED crypto currency (including Bitcoin) is a delusion (any solutions?) (https://bitcointalk.org/index.php?topic=1319681.0), and Satoshi didn't solve the Byzantine generals problem (https://bitcointalk.org/index.php?topic=1183043.0). Also include some discussions between monsterer, smooth, and myself in my vaporcoin's thread. So I have the advantage of a few months of discussions about these abstract topics. So the issue is not time sequence, but the fact that it is hard to know if the weaker chain put the data in there as part of a consensus or as part of an attack? If that is the issue, I am confused why we care so much about it? The metadata in the altcoin chain refers to the BTC data, so why does it matter who put it there? It either matches the BTC data or it doesnt. If it matches, it creates a verifiable time sequence. If it doesnt match, then it would be ignored. Could you make a simple example that shows how an attacker can bypass the BTC "clock" and double spend? Because the altcoins are not confirmed spent on the Bitcoin block chain. The altcoin chain is free to disagree with the Bitcoin block chain. The point about relative ordering of blocks between two chains (i.e. two partitions) is relevant to why it is impossible to enforce that the altcoin chain must follow the Bitcoin block chain's consensus. If you think out how you would attempt to specify a protocol for the altcoin chain so that it must obey the Bitcoin consensus, you will soon realize that it is impossible because no external truth exists in a block chain. I dont think using bitcoin as the reference clock violates the CAP theorem as it defines the bitcoin data as definitive source of data, so Consistency is achieved, along with availability. [I dont want to get into whether bitcoin itself has done this or that with byzantine whatchamacallits] Maybe to solve the Partition part, the metadata for the altcoin metadata needs to get back into the BTC chain. We are talking about a slow process, but even if it takes a day for all the back and forth, it seems that it isnt impossible. I just dont understand what exactly is needed. Maybe it is like spontaneous creation of life from inert chemicals which is (nearly) impossible [please it is just an example, dont want to get into any creation/evolution debate either!], but once it is there, it is hard to stop it from replication. And kind of hard to deny that it exists. Since we now have bitcoin, maybe building on it allows to achieve the desired result (better altcoin security) without any violation of proven theorems by changing the problem. James P.S. CAP seems to vary from principle, conjecture, to theorem based on exact and precise definitions, I dont know if bitcoin is the exactly same behavior as in the proven CAP theorem, or if a bitcoin + extra is unable to change it to be beyond the confines of what is proven. I dont like to fight against math proofs, but if there is any level of abstraction in the proof then it is usually possible to "work around" it by transforming the problem to a different problem that isnt proven impossible. Since I am not trying to disprove the CAP theorem, but rather create a cross chain security mechanism that isnt covered by the CAP theorem proper Sorry but you will need to read and understand deeply the threads I linked to. We've analyzed this already and it is an inviolable mathematical structure. Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 26, 2016, 11:41:34 PM Gmaxwell just released a system for committing to an information exchange.
https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-payments-announcement/ http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-February/012471.html I think that solves the exchange problem. In the article, they say it takes around 20 seconds to build up the proof for 5 SHA256 operations. In the zero knowledge proofs, you can prove that you ran a program. The program of interest here would be Code: boolean check(byte[] bob_priv_key) {Bob could send Alice {BOB_PUB_KEY, BOB_PRIV_KEY_HASH, <proof>} and Alice could check that the proof proves that the program was run correctly and that it returned true. It's a zero-knowledge-proof, which means that it gives Alice no info about bob_priv_key, but proves that Bob knows an input into the program that will get it to return true. Since elliptic curve calculations are more complex than hashing operations, I think it might not be viable, but would work in theory. [Edit] Gmaxwell suggested using one of the schemes from here (http://lists.linuxfoundation.org/pipermail/lightning-dev/2015-November/000344.html). [Edit2] The lightning dev list has some discussions about an opcode for checking public/private matches. They call it CHECKPRIVPUBPAIR rather than CHECKPRIVATEKEYVERIFY. http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-November/011827.html Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 27, 2016, 01:44:18 AM Gmaxwell just released a system for committing to an information exchange. https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-payments-announcement/ http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-February/012471.html I think that solves the exchange problem. Indeed I predicted that ;) But credit gmaxwell's Coin Witness thread (https://bitcointalk.org/index.php?topic=277389.0) for making me aware of the SNARKs technology in 2013. Generalized scripting is going to open up 51% attack vectors that didn't exist in a more pure crypto currency usage of a block chain: I didn't intend to post in this thread again, but seems I remember Monero would soon add multi-sig, and I wanted to make you aware of a potential 51% attack hole enabled by multi-sig: https://bitcointalk.org/index.php?topic=1364951.msg14002317#msg14002317 I don't know how many of you read the post linked in the above quote, so I wanted to again draw attention to this insoluble problem for scripting on a block chain. Scripting opens a Pandora's box that destroys the normal security model for block chains. This is more damning than the problem of needing to centralize verification of scripts, because afaics it is entirely insoluble (unless you centralize authorization of which scripts are allowed to run). The only possible solution I can think of is to make all scripts run as zero knowledge black boxes so that the miners are unable to see any of the data in the block chain. The only way to do this is zk-snarks. Remember I wrote in 2014 that I thought zk-snarks were essential for block chain 2.0 smart contracts. Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 27, 2016, 01:53:47 AM You could set the minimum confirms to k * (trade_value) / (25 BTC). The k parameter is some protection against multiple trades being attacked together. You'd have to base these thresholds on a computation of how many other DE are operating on the same blocks, but then an attacker can DE trade to himself to fool your algorithm into an unbounded value of k (as high as the attacker wants to make it). There are no solutions like that. The only solution is don't use cut & choose except where checkpoints are trusted, or develop the zero knowledge black box solution. Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 27, 2016, 02:22:43 AM [Edit] Gmaxwell suggested using one of the schemes from here (http://lists.linuxfoundation.org/pipermail/lightning-dev/2015-November/000344.html). Oh that reminds me what I meant to write in this thread when I woke up this morning but I got sidetracked. The reason we can't allow Bob to sign instead of revealing his private key in order to reclaim his deposit, is because then the payments in the protocol can only be made contingent on revealing the private key. There is no way to put the deposit first on the block chain yet also have signing it require also signing the other transactions in the protocol, because those "other transactions" are not yet in the block chain when the deposit is confirmed (thus the deposit can't refer to transactions which are not yet confirmed as this would either be a security hole or would be impossible to pre-hash since the transaction paying Bob from Alice is not committed to a destination address). Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 27, 2016, 03:38:12 PM There are no solutions like that. The only solution is don't use cut & choose except where checkpoints are trusted, or develop the zero knowledge black box solution. The attack is more general and it doesn't specifically attack the cut-and-choose system, I think. - Offer to sell A altcoins for B Bitcoins to 1000 people - Perform the atomic trades - You now have 1000*B Bitcoins and lost your A altcoins - Victims made sure there was 10*A worth of hashing confirmations on their transactions before moving to the next step - You spend 50*A altcoins to buying hashing to rewind up to 50*A worth of blocks, which is more than their protection - This rewinds history and your 1000*A altcoins are now yours again A defense against this would be to mark the multisigs that are being used as anchors. Rather than 2 of 2, you could use 2 of 3 with the 3rd key being a standard value. You can then set k based on how many trades are happening on the altcoin chain. As long as cross chain transfers are much smaller than real transfers, then this is less of a problem. Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on February 29, 2016, 01:53:27 AM A defense against this would be to mark the multisigs that are being used as anchors. Rather than 2 of 2, you could use 2 of 3 with the 3rd key being a standard value. You can then set k based on how many trades are happening on the altcoin chain. Attacker can make anchors for nearly free (large transaction values relative to transaction fees): ...but then an attacker can DE trade to himself to fool your algorithm into an unbounded value of k (as high as the attacker wants to make it). Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 29, 2016, 03:33:14 AM A defense against this would be to mark the multisigs that are being used as anchors. Rather than 2 of 2, you could use 2 of 3 with the 3rd key being a standard value. You can then set k based on how many trades are happening on the altcoin chain. Attacker can make anchors for nearly free (large transaction values relative to transaction fees): ...but then an attacker can DE trade to himself to fool your algorithm into an unbounded value of k (as high as the attacker wants to make it). Wouldnt that require the attacker to conduct all attacks simultaneously using properly aged UTXO? Or are we assuming arbitrary depth of reorging the altcoin is available to attacker to deploy at anytime? Since the attacker wouldnt get the BTC until the trades complete, it seems he would have to borrow the BTC to buy the hashrate. And if an altcoin can be rewritten at will with the attacker's existing resources, what secures that chain without atomic swaps? I guess the probability of successful attack creates some expected value, but I am having a hard time correlating the hashcosts for coins with decent trading volumes and the likely number of open trades at any given time. If the success of attack is not 100%, then that raises the risk of lost capital. I think realistic cost estimates are needed to attack the various chains and compare it to trading volume and amount of time that would be at risk James Title: Re: Atomic swaps using cut and choose Post by: jl777 on February 29, 2016, 03:52:32 AM Some practical estimates:
Most top 100 bitcoin compatible altcoins trade a total of $1000 to $25000 per day, some get a lot more volume but usually it is due to CNY trading. The second 100 ranked trade $5000 or less as a guideline. The CE risk is that 100% of all funds for all coins and in this aspect, even if it the only aspect, makes the DE much safer to trade. http://www.coindesk.com/court-cryptsy-ceo-predicted-exchange-failure/ vs blockchains to see where all the funds are. just the open disclosure would make DE superior, even if DE had all the same risks as CE. But I argue that DE risk is dramatically less due to the fragmenting of the funds across all coins. Also, the attacker is only able to make money by selling altcoins for BTC en masse to a lot of buyers which is quite a bit harder than the reverse Let us say an exchange DE or CE gets 10% of the trading market and roughly $100,000 per day is traded. This would translate to a lot more on deposit, hard to estimate what percentage of trades are vs amount on deposit, if it is 10:1, then that means $1 million is at risk at this CE, all the time, from reorg attacks like DE and many other attacks and internal theft and simply flight of owner. Now the DE, let us assume 100% of a coin is at risk, it is $2500 in this context. But actually it would be just the trades that are pending and if average trades complete in one hour or so, it might be $100. With a budget of $100 or even $2500, I am having a hard time seeing that it would be a cash positive expectation if the process isnt fully automated. Even with a fully automated system, the cost to rent hashrate varies in realtime based on supply/demand and it is not like you can buy arbitrary amounts at a fixed cost. My feeling is that like the cut and choose itself, it is all about positive expected return from conducting the attack and opportunity cost. Unless attacking the DE offers positive expected ROI, it is the same thing as saying someone can attack cut and choose and continue to lose money. Can you estimate the hashrate it would take to attack some middlemarket coin,or rather, what coin could be attacked with a $2500 budget? Wouldnt the attacker need to pregenerate the blocks ahead of time? if so, there is a very big risk of not being able to make the trades to take advantage of this alternate chain. or can he wait until he has all the trades pending, then buy the hashrate, hope he is able to build a stronger attackchain with his double spends, then complete all the swaps, push the attack chain to reverse the altcoin payments. Now he gets back the altcoins used for the trade, which had to be of equal value to the BTC gained, so he is stuck with altcoins for a chain that got attacked. maybe that will cause it to lose value and add more risk. There seem to be quite a few "ifs" that all have to work out and the reward is 5BTC, not any 5000 BTC. So this seems an attack scenario for the financially challenged attacker, unless I am dramatically overestimating the cost to conduct the attack. James Title: Re: Atomic swaps using cut and choose Post by: TierNolan on February 29, 2016, 10:38:16 AM This problem isn't really specific to currency trades. An attacker could buy lots of stuff with an altcoin and then roll back all the payments a week later.
One of the weaknesses of an altcoin is that it has less security. The exchange creates a large market of things that you can (irreversibly and quickly) buy with the altcoins. The underlying issue is that the altcoin has low security. The concept behind the POW system is that a single POW can cover lots of trades. This breaks down if enough people get together to try to double spend. They can split the cost of double spending over all the attackers. Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on March 02, 2016, 07:56:04 PM This problem isn't really specific to currency trades. An attacker could buy lots of stuff with an altcoin and then roll back all the payments a week later. There are some egregious distinctions.
Title: Re: Atomic swaps using cut and choose Post by: TierNolan on March 02, 2016, 10:45:39 PM There are some egregious distinctions.
(Again, I don't see how this attack is specific to cut and choose.) The problem is fundamental to block chain crypto-currencies. They inherently use a single validation (POW) to cover lots of transactions. The security assumption is that no one attacker can controls enough of the transactions to make roll back worth it. Title: Re: Atomic swaps using cut and choose Post by: TPTB_need_war on March 03, 2016, 02:38:57 AM There are some egregious distinctions.
(Again, I don't see how this attack is specific to cut and choose.) The problem is fundamental to block chain crypto-currencies. They inherently use a single validation (POW) to cover lots of transactions. The security assumption is that no one attacker can controls enough of the transactions to make roll back worth it. I will repeat again that the reason is that cut & choose (in theory) alters the economics of a 51% attack and thus (in theory) alters the security of the entire block chain where cut & choose is deployed (or other similar script ... which is why I have posited that multi-sig and for sure Turing-complete scripting is a generalized block chain security hole and scripts in zero knowledge may be the only way to close to hole). Agreed that the security of block chains is predicated on there no being one (or coordinated) attacker with sufficient resources to perform a sufficiently long-range, lie-in-wait block reorganization. And this is predicated on the cost of the attack AND the potential gain from the attack. Cut & choose alters the economics of the plausibility of the gain from an attack. Mining concentration into pools (which may even be Sybil attacked so we don't know which pools are controlled by the same entity or which cooperate nefariously) coupled with hashrate rental capacities means that an attack is plausible except that these attackers don't want to be identified on a well established block chain (e.g. Bitcoin), because they don't want the community to fight them or otherwise destroy the viability of the block chain (e.g. the Chinese mining cartel allegedly controls 65% of Bitcoin's hashrate). With cut & choose, the 51% attacker can resign the DE transactions on the altcoin to pay to himself, but there is no way to prove which transactions were the attacker and which were the victim. Propagation is not proof, because nodes can lie about propagation and even be a Sybil attacked on the veracity of reported propagation. The only unequivocal proof is the longest chain rule (LCR). Thus although we can't prove which of the double-spends are the victim, the victims can provably indicate that they took an order for a good or service from an attacker whom they can identify. Because if the attacker can't receive the good or service, then the attacker can't gain any income from the 51% attack. But with cut & choose, the attacker can't be identified. Please understand the salient distinction. One general problem that I've observed numerous times in the block chain arena, is the very smart coders and mathematicians/cryptographers seem to have blind spots on economics (and even on the importance (https://bitcointalk.org/index.php?topic=1378533.msg14035614#msg14035614) of degrees-of-freedom in design). P.S. note I added a 4th bulleted point as quoted above. Title: Re: Atomic swaps using cut and choose Post by: jl777 on May 23, 2016, 06:13:15 PM I am finally close to finishing the iguanacore, the RPC layer is going through testing and so far all bugs found have been easy to fix.
So I am back to debugging the atomic swap and now have the state machine going through 80% of the process, but I am doing it in a loopback mode for now so I dont have to wait for new blocks and can just use the same unspents over and over for testing. One issue with fully decentralized exchange is that people will lose their connections and the need to properly resume a pending trade needs to be solved. Assuming a power loss, then any temporary keypairs would need to be preserved so the funds can be properly claimed. Worst case is if a powerloss causes HDD corruption and you are in the protocol phase where you need the keys to claim it, you are losing funds. So, this means a robust key storage and recovery mechanism is needed. Or is it? What I came up with is a deterministic keypairs system that allows recreating all temporary keys used for a specific swap, using just the accounts main keypair. I am assuming that proper care about backing up the main keypair is done. Since there is a lot of divulging of the temporary keypairs going on, I wanted to make sure that neither the main keypair is compromised and also that this method doesnt open up an attack vector. I am thinking that since it has algebraic structure, it makes things a bit harder to spoof, but I cant see any direct way of the other party verifying things directly. Here is the process: bits256 instantdex_derivekeypair(struct supernet_info *myinfo,bits256 *newprivp,uint8_t pubkey[33],bits256 privkey,bits256 orderhash) { bits256 sharedsecret; sharedsecret = curve25519_shared(privkey,orderhash); vcalc_sha256cat(newprivp->bytes,orderhash.bytes,sizeof(orderhash),sharedsecret.bytes,sizeof(sharedsecret)); return(bitcoin_pubkey33(myinfo->ctx,pubkey,*newprivp)); } A chain of keypairs are generated that starts from the main account keypair and that one needs to be protected. Each iteration of the chain uses the derivekeypair function. The orderhash is SHA256 of the orderbook entry that is being swapped. I am using the nodes orderbook entry, but maybe it is better to use the other party's entry, or a combine value. Probably the combined value is best, that way the keypairs chain is only for the exact swap. The first step is to make a shared secret using the orderbook hash as the "pubkey" and the main account's privkey as the privkey. The curve25519 is used for speed and it does an SHA256 of the actual shared secret field element, so that protects the main privkey as well as curve25519 + SHA256 does. This shared secret is put through another round of SHA256 with the orderhash and that is used as the privkey to generate an secp256k1 pubkey. There is a small chance of failure here as not all 256bit value are valid privkeys, but that is taken care of with the outer loop. The outer loop does the following: for (n=0; n<keypairs_needed; n++) { pubi = instantdex_derivekeypair(myinfo,&swap->privkeys[n],pubkey,privkey,hash); privkey = swap->privkeys[n]; if ( pubkey[0] != firstbyte ) continue; ... } the first iteration, the privkey is the main account privkey, but after each iteration, the privkey is what is calculated in the prior iteration. Since each new privkey requires a shared secret using the main privkey, only the owner of that privkey is able to generate each iteration. Also, I set all of Bob's privkey's so that the pubkey starts with 0x03 and Alice's starts with 0x02. that allows to use it as an extra consistency check and with the libsecp256k1 library, the time it takes is not really noticeable for generating about double the keypairs. this check also catches the case where the privkey is illegal as the first byte will be 0x00 Now comes the part I think might have some issues the part above that is in the "..." calc_rmd160_sha256(secret160,swap->privkeys[n].bytes,sizeof(swap->privkeys[n])); memcpy(&txid,secret160,sizeof(txid)); len += iguana_rwnum(1,(uint8_t *)&swap->deck[m][0],sizeof(txid),&txid); len += iguana_rwnum(1,(uint8_t *)&swap->deck[m][1],sizeof(pubi.txid),&pubi.txid); m++; txid is a unit64_t and it is the lower 64bits of the bits256. I calculate both the rmd160+sha256 of the privkey and also the lower 64bits of the secp256k1 pubkey. These are the cut and choose keypairs that are sent to the other side. and all but the chosen one is sent back in full privkey form so the above uint64's can be verified. maybe there is no need to send both variants and just one will suffice, but I have a feeling that with this additional constraint, it might be possible to get some proof that the chosen keypair is valid, prior to funds being committed via pederson commitments or something like that. James Title: Re: Atomic swaps using cut and choose Post by: iamnotback on August 03, 2016, 12:25:45 PM Any way, I think I have thought of a solution for DE. The key is to identify the attacker immediately so that all decentralized parties can apply my upthread blocking "Coin Days Destroyed" suggestion (https://bitcointalk.org/index.php?topic=1364951.msg13925984#msg13925984). The "Coin Days Destroyed" becomes the reference point that is signed by the owner of the resource, which thus apparently escapes from my generative essence conceptualization of the problem set (https://bitcointalk.org/index.php?topic=1364951.msg13940253#msg13940253). So change to the protocol is the provider of the hash sends to the trade's counter party to sign it (hashed with the other party's UXTO address) so the counter party's UXTO can be identified. Then the hash provider (the potential jamming victim) posts this information in a timed refundable transaction to the block chain (spending to the payee contingent on releasing the hash). If the attacker never posts the reciprocal transaction on the other block chain, this enables anyone to identify that attacker and apply the Coin Days Destroyed filtering that I proposed upthread. Note this eliminates the need for any fee. But I assume you can find some justification for a fee, such as perhaps keeping your source code for the DE app closed source and/or offering a centralized fee structure for matching orders, limit orders, etc.. You won't be able to steal funds, which afaik is the most significant advantage of DE over CE. The above was an error. The reason had been stated before that above post was made as follows: One way I contemplated is to have both parties sign the intention to trade, then they post it to this block chain. However, one might sign and the other might not, thus jamming the other party (in terms of computing the signature and the communication latency between the two parties). Also worse is that one party might sign more than one intention to trade or inadvertently do so if the attacker didn't sign immediately but later signed and published it to this block chain. For example, an attacker could sign an intent to trade, but if I don't acknowledge it, then I would be implicated as the attacker. But if I sign an intent to trade and the attacker doesn't acknowledge it, then the attacker isn't implicated. So either way, it is flawed and doesn't solve the jamming problem that makes DEX (decentralized exchange between blockchains) implausible. Bitshares' OpenLedger is decentralized exchange on the same blockchain employing pegged assets, but that is not equivalent (for one reason being that pegged assets do not precisely track the value of the asset they are supposedly pegged to). I have devised another methodology for DEX which relies on selecting a mutual trusted party which cryptographically can't steal nor lockup the funds. This is a compromise between centralized exchanges (which can steal/lose funds) and purely DEX which can be jammed. jl777 is aware of the algorithm I have in mind. Title: Re: Atomic swaps using cut and choose Post by: tempus on November 23, 2016, 06:44:28 PM Maybe somebody here is interested + skilled?
Lykke offer: https://i.imgur.com/NdHGMOX.png Details can be found here: https://streams.lykke.com/Project/ProjectDetails/b134b15b54e745559f26c217bef5a2f8 Title: Re: Atomic swaps using cut and choose Post by: tempus on January 09, 2017, 09:40:52 AM There were participants but no submissions - therefore a second modified round:
https://i.imgur.com/yIE7zSC.png https://streams.lykke.com/Project/ProjectDetails/5b33b9661c254022a8d0cb222b0d503b Title: Re: Atomic swaps using cut and choose Post by: Traxo on May 31, 2018, 08:08:20 AM @anonymint has apparently devised a secure and sound solution for cross-chain DEX:
https://steemit.com/cryptocurrency/@anonymint/scaling-decentralization-security-of-distributed-ledgers Note he will not be able to discuss it with you here because he is perma-banned from bitcointalk.org. Title: Re: Atomic swaps using cut and choose Post by: marcus_of_augustus on May 31, 2018, 08:57:01 AM @anonymint has apparently devised a secure and sound solution for cross-chain DEX: https://steemit.com/cryptocurrency/@anonymint/scaling-decentralization-security-of-distributed-ledgers Note he will not be able to discuss it with you here because he is perma-banned from bitcointalk.org. .... you mean he finally did something instead of just talking about it? Let's see shall we? |
