Pages:
Author

Topic: Atomic swaps using cut and choose - page 2. (Read 12138 times)

sr. member
Activity: 420
Merit: 262
February 26, 2016, 03: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, 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 deCentralized consensus algorithm. Seems befitting and allows you James to monetize your work, since PoS coins are still quite popular for the time being (and with hubris I will joke that they will need DE to trade for my superior consensus algorithm invisible vaporcoin).

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.
legendary
Activity: 1232
Merit: 1094
February 26, 2016, 05: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.
legendary
Activity: 1176
Merit: 1134
February 26, 2016, 01: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, DECENTRALIZED crypto currency (including Bitcoin) is a delusion (any solutions?), and Satoshi didn't solve the Byzantine generals problem. 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
sr. member
Activity: 420
Merit: 262
February 26, 2016, 12: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, DECENTRALIZED crypto currency (including Bitcoin) is a delusion (any solutions?), and Satoshi didn't solve the Byzantine generals problem. 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.
legendary
Activity: 1176
Merit: 1134
February 25, 2016, 11:03:37 PM
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
sr. member
Activity: 420
Merit: 262
February 25, 2016, 10:32:09 PM

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.
legendary
Activity: 1176
Merit: 1134
February 25, 2016, 09:46:38 PM
sr. member
Activity: 420
Merit: 262
February 25, 2016, 08:15:57 PM
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, 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, even I nailed in 2013 the block size as the specific failure mode, and everyone was arguing at that time that I was loony. 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 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 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.
legendary
Activity: 1176
Merit: 1134
February 25, 2016, 03: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.
Yes scrutiny leads to progress.

"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
sr. member
Activity: 420
Merit: 262
February 25, 2016, 03: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.
legendary
Activity: 1176
Merit: 1134
February 25, 2016, 03: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.

Sorry your proposal must be scrapped.

Stick with the CLTV on both block chains. That is sound.
I understand hashrate is rentable.

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.
Just trying to calibrate things. If need be there can be a global tracking of pending trades relative to hashrates. And until there are much larger number of active trades, at any given time odds are that there wont be that many trades involving a specific coin. Even on high volume exchanges like btc38, often hours can go by without any trade for a specific coin.

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
sr. member
Activity: 420
Merit: 262
February 25, 2016, 02:52:40 AM
#99
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.

Sorry your proposal must be scrapped.

Stick with the CLTV on both block chains. That is sound.
I understand hashrate is rentable.

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.
legendary
Activity: 1176
Merit: 1134
February 25, 2016, 02:51:08 AM
#98
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.

Sorry your proposal must be scrapped.

Stick with the CLTV on both block chains. That is sound.
I understand hashrate is rentable.

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
sr. member
Activity: 420
Merit: 262
February 25, 2016, 02:46:38 AM
#97
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.
legendary
Activity: 1176
Merit: 1134
February 25, 2016, 02:43:30 AM
#96
sr. member
Activity: 420
Merit: 262
February 25, 2016, 02:13:24 AM
#95
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 OP_EQUALVERIFY OP_CHECKSIG

[...]

3) ... OP_2 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 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.
legendary
Activity: 1176
Merit: 1134
February 25, 2016, 01:57:28 AM
#94
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.
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.

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
legendary
Activity: 1176
Merit: 1134
February 25, 2016, 01:49:22 AM
#93
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 OP_EQUALVERIFY OP_CHECKSIG

[...]

3) ... OP_2 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 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.
I am glad we are now finding potential weak spots in the actual protocol!

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 OP_EQUALVERIFY 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
legendary
Activity: 1176
Merit: 1134
February 24, 2016, 10:55:46 PM
#92
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
  OP_CLTV OP_DROP OP_CHECKSIG
OP_ELSE
  OP_HASH160 OP_EQUALVERIFY 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 OP_2 OP_CHECKMULTISIG

4) Bob pays b Bitcoins to

Code:
OP_IF
  OP_CLTV OP_DROP OP_CHECKSIG
OP_ELSE
   OP_HASH160 OP_EQUALVERIFY 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
legendary
Activity: 1176
Merit: 1134
February 24, 2016, 10:36:35 PM
#91
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.
The simple act of spending the payment requires to disclose the information the other party needs to do their spend.

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."
OK, I think we take one issue at a 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 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
    OP_CLTV OP_DROP OP_CHECKSIG
OP_ELSE
    OP_HASH160 OP_EQUALVERIFY 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
Pages:
Jump to: