Atomic swaps using cut and choose - page 5.

TPTB_need_war

sr. member

Activity: 420

Merit: 262

Quote from: jl777 on February 20, 2016, 07:59:02 AM

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.

TierNolan

legendary

Activity: 1232

Merit: 1094

Quote from: jl777 on February 20, 2016, 07:59:02 AM

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.

TierNolan

legendary

Activity: 1232

Merit: 1094

Quote from: TPTB_need_war on February 20, 2016, 07:07:38 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 , otherwise it goes to TTP after 7 days
B) pays fee to Bob but requires , 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 and the private keys except key N.
Bob sends Alice 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 Cool

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.

jl777

legendary

Activity: 1176

Merit: 1134

Quote from: TPTB_need_war on February 20, 2016, 07:07:38 AM

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 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.

I think we are both circling around (converging?) to a similar type of solution.

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

TPTB_need_war

sr. member

Activity: 420

Merit: 262

Quote from: jl777 on February 19, 2016, 05:06:25 PM

Quote from: TPTB_need_war on February 19, 2016, 04: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.

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 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. 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. 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.

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.

jl777

legendary

Activity: 1176

Merit: 1134

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
    s = instantdex_statecreate(s,n,"ALICE_claimedbtc",ALICE_claimbtcfunc,0,0,0,0);
    instantdex_addevent(s,*n,"ALICE_claimedbtc","aclfound","poll","BTC_cleanup");
    instantdex_addevent(s,*n,"ALICE_claimedbtc","poll","poll","ALICE_claimedbtc");
    
    s = instantdex_statecreate(s,n,"BOB_depclaimed",BOB_reclaimfunc,0,0,0,0); // deposit back
    instantdex_addevent(s,*n,"BOB_depclaimed","brefound","poll","BTC_cleanup");
    instantdex_addevent(s,*n,"BOB_depclaimed","poll","poll","BOB_depclaimed");

    s = instantdex_statecreate(s,n,"BOB_claimedalt",BOB_claimaltfunc,0,0,0,0);
    instantdex_addevent(s,*n,"BOB_claimedalt","bclfound","poll","BOB_depclaimed");
    instantdex_addevent(s,*n,"BOB_claimedalt","poll","poll","BOB_claimedalt");
    
    // if things go wrong, bob gets his deposit and fee back
    s = instantdex_statecreate(s,n,"BOB_feereclaimed",BOB_feereclaimfunc,0,0,0,0);
    instantdex_addevent(s,*n,"BOB_feereclaimed","bfrfound","poll","BTC_cleanup");
    instantdex_addevent(s,*n,"BOB_feereclaimed","poll","poll","BOB_feereclaimed");
    
    s = instantdex_statecreate(s,n,"BOB_reclaimed",BOB_reclaimfunc,0,0,0,0); // deposit back
    instantdex_addevent(s,*n,"BOB_reclaimed","brefound","poll","BOB_feereclaimed");
    instantdex_addevent(s,*n,"BOB_reclaimed","poll","poll","BOB_reclaimed");
    
    // if things go wrong, alice reclaims her altpayment or claims the deposit and then fee
     s = instantdex_statecreate(s,n,"ALICE_feereclaimed",ALICE_feereclaimfunc,0,0,0,0);
    instantdex_addevent(s,*n,"ALICE_feereclaimed","afrfound","poll","BTC_cleanup");
    instantdex_addevent(s,*n,"ALICE_feereclaimed","poll","poll","ALICE_feereclaimed");
  
    s = instantdex_statecreate(s,n,"ALICE_reclaimed",ALICE_reclaimfunc,0,0,0,0); // altpayment
    instantdex_addevent(s,*n,"ALICE_reclaimed","arefound","poll","ALICE_feereclaimed");
    instantdex_addevent(s,*n,"ALICE_reclaimed","poll","poll","ALICE_reclaimed");
    s = instantdex_statecreate(s,n,"ALICE_depositclaimed",ALICE_claimdepositfunc,0,0,0,0); // altpayment
    instantdex_addevent(s,*n,"ALICE_depositclaimed","adpfound","poll","ALICE_feereclaimed");
    instantdex_addevent(s,*n,"ALICE_depositclaimed","poll","poll","ALICE_depositclaimed");
    // end terminal [BLOCKING] states
    
    // need to create states before they can be referred to, that way a one pass FSM compile is possible
    s = instantdex_statecreate(s,n,"BOB_sentprivs",BTC_waitprivsfunc,0,"BTC_cleanup",0,0);
    s = instantdex_statecreate(s,n,"BOB_waitfee",BOB_waitfeefunc,0,"BTC_cleanup",0,0);
    s = instantdex_statecreate(s,n,"BOB_sentdeposit",BOB_waitBTCalttxfunc,0,"BOB_reclaimed",0,0);
    s = instantdex_statecreate(s,n,"BOB_altconfirm",BOB_waitaltconfirmfunc,0,"BOB_reclaimed",0,0);
    s = instantdex_statecreate(s,n,"BOB_sentpayment",BOB_waitprivMfunc,0,"BOB_reclaimed",0,0);
    s = instantdex_statecreate(s,n,"ALICE_sentprivs",BTC_waitprivsfunc,0,"BTC_cleanup",0,0);
    s = instantdex_statecreate(s,n,"Alice_waitfee",ALICE_waitfeefunc,0,"BTC_cleanup",0,0);
    s = instantdex_statecreate(s,n,"ALICE_waitdeposit",ALICE_waitdepositfunc,0,"BTC_cleanup",0,0);
    s = instantdex_statecreate(s,n,"ALICE_sentalt",ALICE_waitBTCpaytxfunc,0,"ALICE_reclaimed",0,0);
    s = instantdex_statecreate(s,n,"ALICE_waitconfirms",ALICE_waitpayconf_or_bobreclaimfunc,0,"ALICE_reclaimed",0,0);

    if ( 0 ) // following are implicit states and events handled externally to setup datastructures
    {
        //s = instantdex_statecreate(s,n,"BOB_idle",BTC_idlefunc,0,0,0);
        //s = instantdex_statecreate(s,n,"ALICE_idle",BTC_idlefunc,0,0,0);
        instantdex_addevent(s,*n,"BOB_idle","usrorder","BTCoffer","BOB_sentoffer"); // send deck
        instantdex_addevent(s,*n,"ALICE_idle","usrorder","BTCoffer","ALICE_sentoffer");
        instantdex_addevent(s,*n,"BOB_idle","BTCoffer","BTCdeckC","BOB_gotoffer"); // send deck + Chose
        instantdex_addevent(s,*n,"ALICE_idle","BTCoffer","BTCdeckC","ALICE_gotoffer");
    }
    // after offer is sent, wait for other side to choose and sent their deck, then send privs
    s = instantdex_statecreate(s,n,"BOB_sentoffer",BTC_waitdeckCfunc,0,"BTC_cleanup",0,1);
    s = instantdex_statecreate(s,n,"ALICE_sentoffer",BTC_waitdeckCfunc,0,"BTC_cleanup",0,1);
    instantdex_addevent(s,*n,"BOB_sentoffer","BTCdeckC","BTCprivC","BOB_sentprivs"); // send privs + Chose
    instantdex_addevent(s,*n,"ALICE_sentoffer","BTCdeckC","BTCprivC","ALICE_sentprivs");
    
    // gotoffer states have received deck and sent BTCdeckC already (along with deck)
    s = instantdex_statecreate(s,n,"BOB_gotoffer",BTC_waitprivCfunc,0,"BTC_cleanup",0,1);
    s = instantdex_statecreate(s,n,"ALICE_gotoffer",BTC_waitprivCfunc,0,"BTC_cleanup",0,1);
    instantdex_addevent(s,*n,"BOB_gotoffer","BTCprivC","BTCprivs","BOB_sentprivs"); // send privs
    instantdex_addevent(s,*n,"ALICE_gotoffer","BTCprivC","BTCprivs","ALICE_sentprivs");
    
    // to reach sentprivs, all paths must have sent/recv deck and Chose and verified cut and choose
    s = instantdex_statecreate(s,n,"BOB_sentprivs",BTC_waitprivsfunc,0,"BTC_cleanup",0,0);
    instantdex_addevent(s,*n,"BOB_sentprivs","BTCprivs","poll","BOB_waitfee");
    
    s = instantdex_statecreate(s,n,"ALICE_sentprivs",BTC_waitprivsfunc,0,"BTC_cleanup",0,0);
    instantdex_addevent(s,*n,"ALICE_sentprivs","BTCprivs","poll","Alice_waitfee");

    // [BLOCKING: fee] Bob waits for fee and sends deposit when it appears
    s = instantdex_statecreate(s,n,"BOB_waitfee",BOB_waitfeefunc,0,"BTC_cleanup",0,0);
    instantdex_addevent(s,*n,"BOB_waitfee","feefound","BTCdeptx","BOB_sentdeposit");
    instantdex_addevent(s,*n,"BOB_waitfee","poll","poll","BOB_waitfee");

    // [BLOCKING: fee and deposit] Alice waits for fee and then waits for deposit to confirm and sends altpayment
    s = instantdex_statecreate(s,n,"Alice_waitfee",ALICE_waitfeefunc,0,"BTC_cleanup",0,0);
    instantdex_addevent(s,*n,"Alice_waitfee","feefound","poll","ALICE_waitdeposit");
    instantdex_addevent(s,*n,"Alice_waitfee","poll","poll","Alice_waitfee");
    
    s = instantdex_statecreate(s,n,"ALICE_waitdeposit",ALICE_waitdepositfunc,0,"BTC_cleanup",0,0);
    instantdex_addevent(s,*n,"ALICE_waitdeposit","depfound","BTCalttx","ALICE_sentalt");
    instantdex_addevent(s,*n,"ALICE_waitdeposit","poll","poll","ALICE_waitdeposit");

    // [BLOCKING: BTCalttx and altfound] now Bob's turn to make sure altpayment is confirmed and send real payment
    s = instantdex_statecreate(s,n,"BOB_sentdeposit",BOB_waitBTCalttxfunc,0,"BOB_reclaimed",0,0);
    instantdex_addevent(s,*n,"BOB_sentdeposit","BTCalttx","poll","BOB_altconfirm");
 
    s = instantdex_statecreate(s,n,"BOB_altconfirm",BOB_waitaltconfirmfunc,0,"BOB_reclaimed",0,0);
    instantdex_addevent(s,*n,"BOB_altconfirm","altfound","BTCpaytx","BOB_sentpayment");
    instantdex_addevent(s,*n,"BOB_altconfirm","poll","poll","BOB_altconfirm");
    
    // [BLOCKING: BTCpaytx] now Alice's turn to make sure payment is confrmed and send in claim or see bob's reclaim and reclaim
    s = instantdex_statecreate(s,n,"ALICE_sentalt",ALICE_waitBTCpaytxfunc,0,"ALICE_reclaimed",0,0);
    instantdex_addevent(s,*n,"ALICE_sentalt","BTCpaytx","poll","ALICE_waitconfirms");
    
    s = instantdex_statecreate(s,n,"ALICE_waitconfirms",ALICE_waitpayconf_or_bobreclaimfunc,0,"ALICE_reclaimed",0,0);
    instantdex_addevent(s,*n,"ALICE_waitconfirms","bobfound","poll","ALICE_reclaimed");
    instantdex_addevent(s,*n,"ALICE_waitconfirms","payfound","BTCprivM","ALICE_claimedbtc");
    instantdex_addevent(s,*n,"ALICE_waitconfirms","poll","poll","ALICE_waitconfirms");

    // [BLOCKING: privM] Bob waits for privM either from Alice or alt blockchain
    s = instantdex_statecreate(s,n,"BOB_sentpayment",BOB_waitprivMfunc,0,"BOB_reclaimed",0,0);
    instantdex_addevent(s,*n,"BOB_sentpayment","btcfound","BTCdone","BOB_claimedalt");
    instantdex_addevent(s,*n,"BOB_sentpayment","BTCprivM","BTCdone","BOB_claimedalt");
    instantdex_addevent(s,*n,"BOB_sentpayment","poll","poll","BOB_sentpayment");

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

TierNolan

legendary

Activity: 1232

Merit: 1094

Quote from: jl777 on February 19, 2016, 04:05: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.

jl777

legendary

Activity: 1176

Merit: 1134

Quote from: TPTB_need_war on February 19, 2016, 04: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.

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.

TPTB_need_war

sr. member

Activity: 420

Merit: 262

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.

jl777

legendary

Activity: 1176

Merit: 1134

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:

{
    "txid" : "80a3afd3b9a325e03efffd3e1a87ae734b11fa1c62df8446f1965d2674151b34",
    "version" : 1,
    "time" : 1455894047,
    "locktime" : 0,
    "vin" : [
        {
            "txid" : "7b9b69c0926219f1267fc4dbfe2934aca8f493a3b961e75fcc9b897ec4d9c5e8",
            "vout" : 1,
            "scriptSig" : {
                "asm" : "3046022100a36015c8807725671688ae86dbeefbbce998816f662b8f0c0f8941f97a690806022100bf7e0d2ae774902a61d6938353974bf36f4f539006f6bb99172c4a72e1fdb0f401",
                "hex" : "493046022100a36015c8807725671688ae86dbeefbbce998816f662b8f0c0f8941f97a690806022100bf7e0d2ae774902a61d6938353974bf36f4f539006f6bb99172c4a72e1fdb0f401"
            },
            "sequence" : 4294967295
        }
    ],
    "vout" : [
        {
            "value" : 0.40030880,
            "n" : 0,
            "scriptPubKey" : {
                "asm" : "42798d71482300af OP_DROP OP_DUP OP_HASH160 ca1e04745e8ca0c60d8c5881531d51bec470743f OP_EQUALVERIFY OP_CHECKSIG",
                "type" : "nonstandard"
            }
        },
        {
            "value" : 0.58043605,
            "n" : 1,
            "scriptPubKey" : {
                "asm" : "OP_DUP OP_HASH160 5dba2c4ae40b488dcd1f3ff265dcd068aea43c79 OP_EQUALVERIFY OP_CHECKSIG",
                "reqSigs" : 1,
                "type" : "pubkeyhash",
                "addresses" : [
                    "RHpmwtFAqE3PV4rwAGkAGA2f1jXHdgp2Mu"
                ]
            }
        }
    ]
}

Alice feetx:

Code:

{
    "txid" : "c910a3a535ea9fa5360417378316687bdc6e0836f639a4e7cdaa7a2857447aff",
    "version" : 1,
    "time" : 1455894042,
    "locktime" : 0,
    "vin" : [
        {
            "txid" : "ba12c78637e5f23350cb4bb8148207f1e71ccfc8e92867931b25de141adc7e0c",
            "vout" : 1,
            "scriptSig" : {
                "asm" : "3045022100daa4b876cb75a10064d09d6dff0a8462974453c610175047f6650ec8dc05550c022025051a9691f97432e241c80fd394a2b469fc0420b8ae82b82d5858d7bcd133e801",
                "hex" : "483045022100daa4b876cb75a10064d09d6dff0a8462974453c610175047f6650ec8dc05550c022025051a9691f97432e241c80fd394a2b469fc0420b8ae82b82d5858d7bcd133e801"
            },
            "sequence" : 4294967295
        }
    ],
    "vout" : [
        {
            "value" : 0.40030880,
            "n" : 0,
            "scriptPubKey" : {
                "asm" : "0ec4cb45ab2ec327 OP_DROP OP_DUP OP_HASH160 ca1e04745e8ca0c60d8c5881531d51bec470743f OP_EQUALVERIFY OP_CHECKSIG",
                "type" : "nonstandard"
            }
        },
        {
            "value" : 0.11747422,
            "n" : 1,
            "scriptPubKey" : {
                "asm" : "OP_DUP OP_HASH160 74d61d299290b014fa9e609dd49978f9be54730b OP_EQUALVERIFY OP_CHECKSIG",
                "reqSigs" : 1,
                "type" : "pubkeyhash",
                "addresses" : [
                    "RKvxxfU8yBvfrUz6ucip8AvUBA712dNrEn"
                ]
            }
        }
    ]
}

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

jl777

legendary

Activity: 1176

Merit: 1134

Quote from: TierNolan on February 19, 2016, 03:49:33 PM

Quote from: jl777 on February 19, 2016, 03:05:34 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)

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.

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

TierNolan

legendary

Activity: 1232

Merit: 1094

Quote from: jl777 on February 19, 2016, 03:05:34 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)

jl777

legendary

Activity: 1176

Merit: 1134

@TierNolan

Did I read this right: https://bitcointalksearch.org/topic/m.13941835

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

jl777

legendary

Activity: 1176

Merit: 1134

Quote from: TierNolan on February 19, 2016, 12:52:12 PM

Quote from: jl777 on February 19, 2016, 12:30:13 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

as written this needs to wait for a new opcode, so cant be done for a while.

Each side can commit to the field product of all the priv keys (https://bitcointalksearch.org/topic/m.13919273), 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

jl777

legendary

Activity: 1176

Merit: 1134

Quote from: ?? on ??

Please note I added this to my prior post. I will delete this post after you've read it.

Quote from: TPTB_need_war on February 19, 2016, 12:36:15 PM

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.

I think the blockchain acts as the trusted third party here, especially with the interlocks where each side waits for confirmations.

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

jl777

legendary

Activity: 1176

Merit: 1134

Here is a simple solution to the fees:

Alice fee:
OP_IF
   OP_CLTV OP_DROP OP_CHECKSIG
OP_ELSE
   OP_HASH160 OP_EQUALVERIFY OP_HASH160 OP_EQUALVERIFY OP_CHECKSIG
OP_ENDIF

Bob fee:
OP_IF
   OP_CLTV OP_DROP OP_CHECKSIG
OP_ELSE
   OP_HASH160 OP_EQUALVERIFY OP_HASH160 OP_EQUALVERIFY 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

TierNolan

legendary

Activity: 1232

Merit: 1094

Quote from: jl777 on February 19, 2016, 12:30:13 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

TPTB_need_war

sr. member

Activity: 420

Merit: 262

Quote from: jl777 on February 18, 2016, 08:45:51 PM

Quote from: TPTB_need_war on February 18, 2016, 07:53:08 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: jl777 on February 18, 2016, 08:45:51 PM

You have no economically viable attack.

Only of we ignore externalities (external economic motivation). The same applies to the erroneous claim that proof-of-stake is as secure as proof-of-work.

Quote from: jl777 on February 18, 2016, 08:45:51 PM

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.

Quote from: jl777 on February 18, 2016, 08:45:51 PM

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.

jl777

legendary

Activity: 1176

Merit: 1134

Quote from: TierNolan on February 19, 2016, 11:29:49 AM

Quote from: TPTB_need_war on February 19, 2016, 11:04:55 AM

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.

These are the same 1000 key pairs used for the cut and choose right?
What is the limit on script size? Maybe there is a way to make a redeem script that requires all the keypairs?

OP_IF
OP_CLTV OP_DROP OP_CHECKSIG
OP_ELSE
OP_IF
OP_CLTV OP_DROP OP_CHECKSIG
OP_ELSE
OP_HASH160 OP_EQUALVERIFY OP_HASH160 OP_EQUALVERIFY 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

TPTB_need_war

sr. member

Activity: 420

Merit: 262

Quote from: TierNolan on February 19, 2016, 11:29:49 AM

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.

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