Atomic swaps using cut and choose

[jl777]

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

[TPTB_need_war]

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]

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.

[TierNolan]

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]

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

[TPTB_need_war]

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]

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

[TierNolan]

Remember the party that goes first in your protocol locks up his funds (e.g. UXTO) for the period of the timeout refund

You can have a single transaction that does both fees.  That way either neither pays the fee or both do.

The protocol would be

Step 1) Commit to hashes

Alice and Bob create 1000 key pairs.

Alice sends hash(alice_public_key_array) and hash(alice_fee_unlock)
Bob sends hash(bob_public_key_array) and hash(bob_fee_unlock)

TTP is the trusted third party.

The fee transaction has 3 output (plus any change outputs)

A) pays fee to Alice but requires <bob_fee_unlock>, otherwise it goes to TTP after 7 days
B) pays fee to Bob but requires <alice_fee_unlock>, otherwise it goes to TTP after 7 days
C) pays to TTP after 7 days

Output C is a 1 of 2 multisig to commit to hash(hash(bob_public_key_array) | hash(alice_public_key_array))

Note:  Both parties could exchange a list of TTPs and then pick one of the intersection.  The default software could assign the author as one and allow -add_ttp_key as an option (and probably -author_ttp_disable)

Step 2) Choose

Once the fee transaction is broadcast/confirmed, the choose step can happen.

Alice and Bob pick M and N.

Alice sends Bob <alice_public_key_array> and the private keys except key N.
Bob sends Alice <bob_public_key_array> and the private keys except key M.

Both parties verify the key pairs and then assume the one they didn't pick is probably ok.

As long as the key pairs were valid and the TTP is honest, then an attacker can reclaim his fees (less the TTP's fee).

Step 3) Deposit

Bob pays to an output which gives the money to Alice, unless he releases his private key within 2 days.

He can re-claim his deposit immediately, but that means he ends up bailing out of the protocol.

Step 4) Alice bail in

Alice pays her bail-in to a multisig.  If Bob reclaims his deposit, then she can reclaim her bail-in.

Step 5) Bob bails in

Bob pays his output.  He can reclaim his output after 1 day.  Alice can claim it immediately but then she has to release the fee unlock code and also give Bob her private key, so he can claim his output.

At the end of this step, Bob is stuck.  If he reclaims his deposit, then he lets Alice get her bail-in back and she can also claim his bail-in.

Step 6) Alice spends her output (and provides alice_priv_m).

For this step, Alice would also have to provide alice_fee_unlock, and alice_priv_m.  Bob can reclaim his fee and also claim his output (and his deposit).

Step 7) Bob can spend the altcoin output

For this step, Bob would also have to provide bob_fee_unlock, so Alice can reclaim his fee.

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

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.

[TierNolan]

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.

[TPTB_need_war]

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.

[jl777]

The coin days requirement should be reserved for usage by user option when there is an ongoing attack, as otherwise new users wont be able to trade.

Allow me to correct you on this non-sequitor. The newness of a user of a decentralized exchange doesn't require that user's UXTO is newly acquired.

I was thinking of someone that just got their first BTC locally. wouldnt that be too young to be used? maybe i dont understand the intended coinage well enough.

If we assume that a  lot of new users will be using the DE, they will be coming from the CE. And maybe they never had a local wallet, so they do a withdraw. patiently wait the confirms so it is in the wallet, then start a trade (after all they are doing this to use the DE) and then told "sorry you have to wait X amount of time since your dont have the right time of utxo"

I really want to avoid having what is potentially a mainstream real world case have such an error message to be expected

James

[jl777]

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.

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?

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

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.

If fraud was successful, then you could publish the locked output and show that the published private key didn't match the committed public key.

Certainly if a fraud is a success, then this is broadcast to all the nodes. I think even any delay from the earliest time a privkey could have been disclosed should send out warnings. That way within a few blocks any funny business is detected and everyone warned.

By using the sum of all fees paid by an account as insurance, then in the event that account steals from another, we could support an insurance claim (up to the limit of the fees paid by the attacker). This way as long as users can see the total fees paid by the other party, they will know how much coverage there is. Granted there are issues about an account building up large amounts of fees and then doing a large number in parallel, but that assumes there are that many that will match up at the same time. I guess this could be fixed by broadcasting all pending trades and adjusting the available insurance. Now we end up with just some propagation based edge cases where not all the pending amounts have been propagated before a trade is agreed to, right at the critical moment.

It feels like it is getting to edge cases that can be handled

James

[TPTB_need_war]

The cut and choose aspect is not requiring any details about bitcoin scripts. The idea is that one side commits to a large number of keypairs, the other side picks a random one and then the original side sends the privkeys to all keypairs except for the chosen one.

Probabilistically as long as the cost of the fee (which is required) must be more than the expected return. Current settings are 1000 keypairs and 1/777 as the fee, so there is about a 13% negative cashflow for anybody that tries to cheat on a large scale. Now whether preventing economically motivated attackers is enough or not, clearly it is a necessary problem to solve completely.

You have not explained to me what cut and choose solves, how it solves it, etc.. The quoted explanation is incomplete. I have no idea why cut and choose was even introduced as a replacement to TierNolan's original protocol which used a single hash.

I tried reading the original discussion where cut and choose was first introduced and it doesn't quickly register for me. I think because it was explained by example employing Bitcoin op codes which I don't understand and also perhaps there were some lapses in explanation due to the those in the discussion not writing down what was already clear to them in their minds (and I am not able to read minds). Perhaps if I tried harder I could reverse engineer what is being introduced, but in the interest of saving time, I wish one of you could explain it clearly.

I do understand the notion of an interactive probabilistic challenge function where the cheater can't cheat unless they can guess which challenge you will provide. The Compact Confidential Transactions uses this to prove in zero knowledge a number is contained within a much larger interval. This can when required be converted to non-interactive with the Fiat-Shamir transform. I just don't understand the application here.

[TPTB_need_war]

The coin days requirement should be reserved for usage by user option when there is an ongoing attack, as otherwise new users wont be able to trade.

Allow me to correct you on this non-sequitor. The newness of a user of a decentralized exchange doesn't require that user's UXTO is newly acquired.

I was thinking of someone that just got their first BTC locally. wouldnt that be too young to be used? maybe i dont understand the intended coinage well enough.

If we assume that a  lot of new users will be using the DE, they will be coming from the CE. And maybe they never had a local wallet, so they do a withdraw. patiently wait the confirms so it is in the wallet, then start a trade (after all they are doing this to use the DE) and then told "sorry you have to wait X amount of time since your dont have the right time of utxo"

I really want to avoid having what is potentially a mainstream real world case have such an error message to be expected

James

You are building a DE so that should mean that users have some coins on a block chain that they wish to trade. Who knows how long ago they acquired those coins. The Coin Days Destroyed is the time (# of blocks) elapsed since the UXTO was created.

Since this is suggested to be a user configurable setting which they set only on their own decentralized client (which filters which counter parties they accept to start the DE protocol), then user whose UXTO is very young, can set the threshold so their UXTO fulfills the chosen threshold. If the threshold isn't high enough, they incur more risk of being jammed. But also note that while they are being jammed, their UXTO is aging, so they can continually increase their chosen threshold if necessary to foil an attacker.

There is no disadvantage to offering the feature. An error msg will never be shown. The only effect is the number of available counter parties may shrink as the threshold is raised, as well the risk of jam attack decreases as the threshold is raised.

[jl777]

The coin days requirement should be reserved for usage by user option when there is an ongoing attack, as otherwise new users wont be able to trade.

Allow me to correct you on this non-sequitor. The newness of a user of a decentralized exchange doesn't require that user's UXTO is newly acquired.

I was thinking of someone that just got their first BTC locally. wouldnt that be too young to be used? maybe i dont understand the intended coinage well enough.

If we assume that a  lot of new users will be using the DE, they will be coming from the CE. And maybe they never had a local wallet, so they do a withdraw. patiently wait the confirms so it is in the wallet, then start a trade (after all they are doing this to use the DE) and then told "sorry you have to wait X amount of time since your dont have the right time of utxo"

I really want to avoid having what is potentially a mainstream real world case have such an error message to be expected

James

You are building a DE so that should mean that users have some coins on a block chain that they wish to trade. Who knows how long ago they acquired those coins. The Coin Days Destroyed is the time (# of blocks) elapsed since the UXTO was created.

Since this is suggested to be a user configurable setting which they set only on their own decentralized client (which filters which counter parties they accept to start the DE protocol), then user whose UXTO is very young, can set the threshold so their UXTO fulfills the chosen threshold. If the threshold isn't high enough, they incur more risk of being jammed. But also note that while they are being jammed, their UXTO is aging, so they can continually increase their chosen threshold if necessary to foil an attacker.

There is no disadvantage to offering the feature. An error msg will never be shown. The only effect is the number of available counter parties may shrink as the threshold is raised, as well the risk of jam attack decreases as the threshold is raised.

There a many people who have dozens of different altcoins and no wallet for any of them, or just a few. In fact most people fall in that category, where they have a few alts they have local wallets and still they buy alts on exchanges they dont have wallets for, with the intent of converting them before withdrawing.

Good point that it can be done without any error messages, but just a gradual increase in the potential matches that are possible. Maybe we can have a sunrise type of graphics to show that the longer you wait the more trades are possible

James

[TierNolan]

You have not explained to me what cut and choose solves, how it solves it, etc.. The quoted explanation is incomplete.

Cut and choose is required because there is no way to commit to releasing a private key.

You can commit to releasing the value of x such that hash(x) = y.

If both coins support CLTV, then you can commit to a hash and no cut and choose is required.

Few altcoins actually support it.  The cut and choose allows you to commit to releasing a private key for a given public key.  It's a cheat.

You commit to a hash of the private key.  The cut and choose is to make sure that the hash actually refers to a private key.

The other party can make an altcoin payment to a 2 of 2 multisig with confidence.  Since you committed to releasing the private key before the timeout, it eliminates the hold up risk.

[TPTB_need_war]

You have not explained to me what cut and choose solves, how it solves it, etc.. The quoted explanation is incomplete.

Cut and choose is required because there is no way to commit to releasing a private key.

You can commit to releasing the value of x such that hash(x) = y.

If both coins support CLTV, then you can commit to a hash and no cut and choose is required.

Understood.

Few altcoins actually support it.  The cut and choose allows you to commit to releasing a private key for a given public key.  It's a cheat.

You commit to a hash of the private key.  The cut and choose is to make sure that the hash actually refers to a private key.

The other party can make an altcoin payment to a 2 of 2 multisig with confidence.  Since you committed to releasing the private key before the timeout, it eliminates the hold up risk.

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

[TPTB_need_war]

1) Cut and choose

Bob generates 1000 keypairs and sends hash(bob_priv_n) and bob_pub_n to Alice for each n (1 to 1000).

Alice picks n from 1 to 1000 and Bob sends bob_priv_n for the 999 other n's.

If they are ok, then Alice assumes the pair she didn't see is valid.

Similarly, Alice generates 1000 key pairs and has Bob choose.

This gives the following public info.

  hash(bob_priv_n) matches bob_pub_n
  hash(alice_priv_m) matches alice_pub_m

There is a 0.1% chance of fraud for each attempt.  This means that fees must be at least 0.1% of the transaction value.  In that way, there is no incentive to cheat at the cut-and-choose.

Okay with this private message, I was able to better understand the mechanism but still I don't see what it solves.

TierNolan it would be helpful for readers to understand, if you stated the conceptual point, which is that each party is sent a challenge which they can't predict, and they release all but one of the private keys BEFORE committing to the multisig on the block chain. On the block chain they commit to the public key which corresponds to the one private key they have not yet seen (of course they can't commit to a public key for which they already know the counter party's private key because then the party that goes first to put his/her transaction on the block chain, could have his/her funds stolen as the counter party wouldn't need to reciprocate). Since each party could not predict the challenge, there is a 1/1000 probability that they have chosen a private key that was invalid.

But I still don't understand how this forces the counter party to release the private key within the timed interval?

Just because the counter party proves he knows the hash of his private key doesn't prove he will reveal or sign with it. I am totally dumbfounded as to how this solves anything.  

[TierNolan]

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

This just looks at half of the cut and choose system.

Bob picks 1000 key pairs and sends Alice hash(1000 public keys)

Bob also spends 10 cents in fees, which he loses if he cheats.

Alice picks a number from 1 to 1000 and select one of the key pairs.

Bob then sends Alice the 1000 public keys and 999 of the private keys.

Alice checks that the public keys hashes to hash(1000 public keys) from before.  She also checks that the 999 private keys match the public keys.

She doesn't know if private key N actually hashes to public key N, but she assumes it does.

There is no point in Bob lying about the 1000 public keys, since he will have to show them.

If he does lie about the private keys, there is no point in having more than 1 false private key.  If he has 2 or more private keys that don't match, then he is guaranteed to be caught.

So, Bob has two choices

- He can honestly create the 1000 key pairs

In that case the protocol works as required.

- He can have one of the private keys not match the public key

In this case, there is a 99.9% chance of being caught.  He loses any fee he has committed.

There is a 0.1% chance he will get away with it.  At best, this means that he gets all the money (other than the deposit, since there is no hold-up risk there).

This gives an expected payout of (value of the trade) * 0.001 - fee * 0.999.  If the trade is less than 990 times larger than the fee, then the expected value of cheating is negative.

Increasing the size of the fee would help.

The key for the cut and choose to work is that Bob must commit to 1000 pairs(pay the fee) before Alice tells him her choice.

[TPTB_need_war]

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

This just looks at half of the cut and choose system.

Bob picks 1000 key pairs and sends Alice hash(1000 public keys)

Bob also spends 10 cents in fees, which he loses if he cheats.

Alice picks a number from 1 to 1000 and select one of the key pairs.

Bob then sends Alice the 1000 public keys and 999 of the private keys.

Alice checks that the public keys hashes to hash(1000 public keys) from before.  She also checks that the 999 private keys match the public keys.

She doesn't know if private key N actually hashes to public key N, but she assumes it does.

There is no point in Bob lying about the 1000 public keys, since he will have to show them.

If he does lie about the private keys, there is no point in having more than 1 false private key.  If he has 2 or more private keys that don't match, then he is guaranteed to be caught.

So, Bob has two choices

- He can honestly create the 1000 key pairs

In that case the protocol works as required.

- He can have one of the private keys not match the public key

In this case, there is a 99.9% chance of being caught.  He loses any fee he has committed.

There is a 0.1% chance he will get away with it.  At best, this means that he gets all the money (other than the deposit, since there is no hold-up risk there).

This gives an expected payout of (value of the trade) * 0.001 - fee * 0.999.  If the trade is less than 990 times larger than the fee, then the expected value of cheating is negative.

Increasing the size of the fee would help.

The key for the cut and choose to work is that Bob must commit to 1000 pairs(pay the fee) before Alice tells him her choice.

But afaics this doesn't bind Bob to release or sign with the one private key which was not revealed. So it seems the cut and choose adds nothing that just asking Bob for a single public key for the 2 of 2 multi-sig would accomplish or what am I missing  

Also fees don't work, because the attacker can run a DE as I explained upthread.

Afaics  the generative essence is inviolable. Both parties must provide a reference point at the start of a protocol by having both parties sign their hash (or public key for 2 of 2 multi-sig) as I suggested upthread.