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

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.

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

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 


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.

I didnt fully understand you solution. can you describe it in more detail?

James

From PM, because this is an important point that others might not realize:


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.

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)

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) =

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.

@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

The protocol puts all the fancy opcodes in the bitcoin side, only the basic scripts are assumed to work on the altcoin side

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 

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


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


HASH160 hashes his private key and then EQUALVERIFY verifies that it matches .

If Alice watches the network, then she will be able to obtain this information and so will get Bob's private key, as promised.

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.

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.

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.  

Understood.


I don't understand the mechanism. Please explain how the protocol accomplishes the goal.

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.

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

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.

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.

I am of the position that if you dont publish the keys you forfeit the fee. It seems if one side just stops for whatever reason, they cant prove they didnt cheat. So it is a reverse logic of guilty until proven innocent. It is all automated so as long as they run unmodified software, the only time it would happen is if they get disconnected for the entire 2hour period. If the trade is big enough, there is hopefully enough time to get to a local wifi hotspot to complete the trade.

Why wouldnt this approach work?

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.

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

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