Atomic swaps using cut and choose

[jl777]

continuing from https://bitcointalk.org/index.php?topic=1340621.msg13881127#msg13881127 as it seems the OP locked it for some reason...

Code:

   // Four initial states are BOB_sentoffer, ALICE_gotoffer, ALICE_sentoffer, BOB_gotoffer
    // the initiator includes signed feetx and deck of 777 keypairs
    // the responder chooses one of 777 and returns it with "BTCchose" message
    // 
    // "BTC<msg> are message events from other party (message events capped at length 8)
    // "lowercas" are special events, <TX> types: <fee>, <dep>osit, <alt>payment, <acl> is altcoin claim
    // "<TX>found" means the other party's is confirmed at user specified confidence level
    // BTC_cleanup state just unwinds pending swap as nothing has been committed yet
    
    // states instantdex_statecreate(s,n,<Name of State>,handlerfunc,errorhandler,<Timeout State>,<Error State>
    // a given state has a couple of handlers and custom events, with timeouts and errors invoking a bypass
    s = instantdex_statecreate(s,n,"BTC_cleanup",BOB_processfunc,0,0,0);
    s = instantdex_statecreate(s,n,"BOB_claimdeposit",BOB_processfunc,0,0,0);
    s = instantdex_statecreate(s,n,"ALICE_reclaim",BOB_processfunc,0,0,0);
 
    s = instantdex_statecreate(s,n,"BOB_sentoffer",BOB_processfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"BOB_sentprivs",BOB_processfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"BOB_gotoffer",BOB_processfunc,0,"BTC_cleanup",0);
    
    s = instantdex_statecreate(s,n,"ALICE_sentoffer",ALICE_processfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_gotoffer",ALICE_processfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_sentprivs",ALICE_processfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_wait3",ALICE_processfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_waitfee_privs",ALICE_processfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_waitdeposit_privs",ALICE_processfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_waitfee_deposit",ALICE_processfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_waitprivs",ALICE_processfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_waitfee",ALICE_processfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_waitdeposit",ALICE_processfunc,0,"BTC_cleanup",0);
    
    s = instantdex_statecreate(s,n,"BOB_sentdeposit",BOB_processfunc,0,"BTC_claimdeposit",0);
    s = instantdex_statecreate(s,n,"BOB_altconfirm",BOB_processfunc,0,"BTC_claimdeposit",0);
    s = instantdex_statecreate(s,n,"ALICE_sentalt",ALICE_processfunc,0,"BTC_claimdeposit",0);
    s = instantdex_statecreate(s,n,"ALICE_waitconfirms",ALICE_processfunc,0,"BTC_claimdeposit",0);
    s = instantdex_statecreate(s,n,"BOB_sentpayment",BOB_processfunc,0,"BTC_claimdeposit",0);
  
    s = instantdex_statecreate(s,n,"ALICE_claimedbtc",BOB_processfunc,0,0,0);
    s = instantdex_statecreate(s,n,"BOB_claimedalt",BOB_processfunc,0,0,0);

    // events instantdex_addevent(s,*n,<Current State>,<event>,<message to send>,<Next State>)
    instantdex_addevent(s,*n,"BOB_sentoffer","BTCchose","BTCprivs","BOB_sentprivs");
    instantdex_addevent(s,*n,"BOB_sentprivs","feefound","BTCdeptx","BOB_sentdeposit");
    instantdex_addevent(s,*n,"ALICE_sentoffer","BTCchose","BTCprivs","ALICE_sentprivs");
    
    // gotoffer states have sent BTCchose already
    instantdex_addevent(s,*n,"BOB_gotoffer","BTCchose","BTCprivs","BOB_sentprivs");
    instantdex_addevent(s,*n,"ALICE_gotoffer","BTCchose","BTCprivs","ALICE_sentprivs");
    
    // alice needs to wait for various items
    instantdex_addevent(s,*n,"ALICE_sentprivs","BTCdeptx",0,"ALICE_wait3");

    // following states cover all permutations of the three required events to make altpayment
    instantdex_addevent(s,*n,"ALICE_wait3","feefound",0,"ALICE_waitdeposit_privs");
    instantdex_addevent(s,*n,"ALICE_wait3","depfound",0,"ALICE_waitfee_privs");
    instantdex_addevent(s,*n,"ALICE_wait3","BTCprivs",0,"ALICE_waitfee_deposit");
    
    instantdex_addevent(s,*n,"ALICE_waitfee_privs","feefound",0,"ALICE_waitprivs");
    instantdex_addevent(s,*n,"ALICE_waitfee_privs","BTCprivs",0,"ALICE_waitfee");
    
    instantdex_addevent(s,*n,"ALICE_waitdeposit_privs","depfound",0,"ALICE_waitprivs");
    instantdex_addevent(s,*n,"ALICE_waitdeposit_privs","BTCprivs",0,"ALICE_waitdeposit");
    
    instantdex_addevent(s,*n,"ALICE_waitfee_deposit","depfound",0,"ALICE_waitfee");
    instantdex_addevent(s,*n,"ALICE_waitfee_deposit","feefound",0,"ALICE_waitdeposit");
    
    // wait for last event and send out altpayment
    instantdex_addevent(s,*n,"ALICE_waitprivs","BTCprivs","BTCalttx","ALICE_sentalt");
    instantdex_addevent(s,*n,"ALICE_waitfee","feefound","BTCalttx","ALICE_sentalt");
    instantdex_addevent(s,*n,"ALICE_waitdeposit","depfound","BTCalttx","ALICE_sentalt");

    // now Bob's turn to make sure altpayment is confirmed and send real payment
    instantdex_addevent(s,*n,"BOB_sentdeposit","BTCalttx",0,"BOB_altconfirm");
    instantdex_addevent(s,*n,"BOB_altconfirm","altfound","BTCpaytx","BOB_sentpayment");
    
    instantdex_addevent(s,*n,"ALICE_sentalt","BTCpaytx",0,"ALICE_waitconfirms");
    instantdex_addevent(s,*n,"ALICE_waitconfirms","bobfound",0,"ALICE_reclaim");
    instantdex_addevent(s,*n,"ALICE_waitconfirms","payfound","BTCprivM","ALICE_claimedbtc");
  
    // if BTCprivM doesnt come in, altcoin needs to be monitored for alice's claim
    instantdex_addevent(s,*n,"BOB_sentpayment","aclfound","BTCdone","BOB_claimedalt");
    instantdex_addevent(s,*n,"BOB_sentpayment","BTCprivM","BTCdone","BOB_claimedalt");
 

I haven't gone through it step by step but that is a good way to do it.

At any time each party is in a given state right?  Why are there 4 start states?  Shouldn't it just be that Bob is in one state and Alice is in another?

For example, Bob starts in BOB_start and Alice starts in Alice_waiting_for_trade_request, or something similar.

If a node receives an offer from another party, then it creates a thread to handle it, like a web-server right?

I guess that means that Alice effectively starts at Alice_received_trade_request, or equivalent.  Since the waiting_for_trade_request is implicit by listening on the socket.

Bob_start causes Bob to send his offer and then transition to Bob_offer_sent.

Bob_offer_sent could timeout within 30-60 seconds and cause Bob to transition to Bob_cancel_offer.  Alternatively, it Alice accepts the offer, they could transition to the fee and 777 pairs exchange.  There is no point in wasting processing if the other party isn't accepting the trade.

I guess it depends on how fine grained the state resolution should be.

Also, there could be a step where both sides decide who is Alice and who is Bob, since the person who offers the trade may not necessarily be Bob.

To avoid insanity I always designate the bitcoin side as Bob and the altcoin side as alice. That way all the directions and scripts are always the same.

Implementation wise, yes it is possible to have just one starting state for both sides, however we have the situation that either party can be the first one to place a quote in the orderbook, ie a bid or ask and this creates 4 possible starting states with 2 parties involved.

alice starts with bid, alice starts with ask, bob starts with bid, bob starts with ask.

notice that alice can be in two of these states at the same time, actually N of them as using the state machine approach each trade that is matched is its own state machine, relatively independent of others (some details like total available balance vs chance that more has been put in the orderbook than funds available, existing trades that are pending)

So that is why 4 possible starting states for when there are two sides to a trade. Internally I have two initial states that bifurcates depending on whether it is alice or bob. Also, before an exchange is ready to be put into the state machine, a lot of onetime prep needs to be done and I wanted the state machine to be as pure as possible and not be cluttered with initial setup.

James

[1714953327]

1714953327

[1714953327]

1714953327

[1714953327]

1714953327

[TierNolan]

Also, before an exchange is ready to be put into the state machine, a lot of onetime prep needs to be done and I wanted the state machine to be as pure as possible and not be cluttered with initial setup.

I notice that you have a single processing function (BOB_processfunc for Bob).  You could maybe reduce clutter by having a different handler for each state.

That is all implementation details but I realize that is half the battle.  The basic description doesn't require details on how to check signatures etc., but it is critical that each step is properly checked.

For example, the CPRKV BIP should very clearly define the formatting of the two keys.  Someone might be able to break the protocol by using badly encoded keys or something.

[yassin54]

continuing from https://bitcointalk.org/index.php?topic=1340621.msg13881127#msg13881127 as it seems the OP locked it for some reason...

Thanks!!  
watched again!!  

[jl777]

Also, before an exchange is ready to be put into the state machine, a lot of onetime prep needs to be done and I wanted the state machine to be as pure as possible and not be cluttered with initial setup.

I notice that you have a single processing function (BOB_processfunc for Bob).  You could maybe reduce clutter by having a different handler for each state.

That is all implementation details but I realize that is half the battle.  The basic description doesn't require details on how to check signatures etc., but it is critical that each step is properly checked.

For example, the CPRKV BIP should very clearly define the formatting of the two keys.  Someone might be able to break the protocol by using badly encoded keys or something.

Yes, the FSM was in first draft state and there is a tradeoff between very granular processfuncs vs. duplication of code, but I think the following is much improved and other than the exact transitions for all the possible errors after money is committed, I think it is solid. But I am not confident that I have all the error states for both sides being handled properly.

This is where the FSM is much better than English to specify things and is the "implementation details" that is fully in the specification area, especially when one missed error event can mean loss of funds!

It isnt so clear, but in the create state function you can specify new state to go to in the event of a timeout (max timeout for bob and half max for Alice?) and a different state if some other error happens, ie some unexpected event (not sure if that should just be ignored) or disconnection. We could specify all the possible types of errors that can happen and have a common error handling.

Anyway, here is revised FSM, with all timeout states invoked if we pass half maxtime for Alice or maxtime for Bob. Speaking of time, with the possible +/- 2 hours on the BTC timestamp if the timeout events trigger based on local clock on each node if we need to pad the cltv parameter by 2 hours to prevent race (or worse) conditions. And if we are adding 2 hours, how this affects the claim windows if maxtime is set to be 2 hours.

Code:

     // Four initial states are BOB_sentoffer, ALICE_gotoffer, ALICE_sentoffer, BOB_gotoffer
    // the initiator includes signed feetx and deck of 777 keypairs
    //
    // "BTCabcde are message events from other party (message events capped at length 8)
    // "lowercas" are special events, <TX> types: <fee>, <dep>osit, <alt>payment, <acl> is altcoin claim
    // "<TX>found" means the other party's is confirmed at user specified confidence level
    // BTC_cleanup state just unwinds pending swap as nothing has been committed yet
    
    // states instantdex_statecreate(s,n,<Name of State>,handlerfunc,errorhandler,<Timeout State>,<Error State>
    // a given state has a couple of handlers and custom events, with timeouts and errors invoking a bypass
    s = instantdex_statecreate(s,n,"BTC_cleanup",BTC_cleanupfunc,0,0,0); // from states without any commits
    s = instantdex_statecreate(s,n,"BOB_reclaim",BOB_reclaimfunc,0,0,0); // Bob's gets his deposit back
    s = instantdex_statecreate(s,n,"ALICE_reclaim",ALICE_reclaimfunc,0,0,0); // Alice retrieves alt payment
  
    s = instantdex_statecreate(s,n,"ALICE_claimedbtc",ALICE_claimbtcfunc,0,0,0); // mainstream cases
    s = instantdex_statecreate(s,n,"BOB_claimedalt",BOB_claimaltfunc,0,0,0);

    // 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",BOB_waitfeefunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_sentprivs",ALICE_waitfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_wait3",ALICE_waitfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"BOB_sentdeposit",BOB_waitBTCalttxfunc,0,"BTC_claimdeposit",0);

    // events instantdex_addevent(s,*n,<Current State>,<event>,<message to send>,<Next State>)
    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);
    s = instantdex_statecreate(s,n,"ALICE_sentoffer",BTC_waitdeckCfunc,0,"BTC_cleanup",0);
    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 BTCchose already (along with deck)
    s = instantdex_statecreate(s,n,"BOB_gotoffer",BTC_waitprivCfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_gotoffer",BTC_waitprivCfunc,0,"BTC_cleanup",0);
    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",BOB_waitfeefunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_sentprivs",ALICE_waitfunc,0,"BTC_cleanup",0);
    instantdex_addevent(s,*n,"BOB_sentprivs","feefound","BTCdeptx","BOB_sentdeposit");
    instantdex_addevent(s,*n,"ALICE_sentprivs","BTCdeptx",0,"ALICE_wait3");

    // following states cover all permutations of the three required events to make altpayment
    s = instantdex_statecreate(s,n,"ALICE_wait3",ALICE_waitfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_waitfee_privs",ALICE_waitfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_waitdeposit_privs",ALICE_waitfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_waitfee_deposit",ALICE_waitfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_waitprivs",ALICE_waitfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_waitfee",ALICE_waitfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_waitdeposit",ALICE_waitfunc,0,"BTC_cleanup",0);
    instantdex_addevent(s,*n,"ALICE_wait3","feefound",0,"ALICE_waitdeposit_privs");
    instantdex_addevent(s,*n,"ALICE_wait3","depfound",0,"ALICE_waitfee_privs");
    instantdex_addevent(s,*n,"ALICE_wait3","BTCprivs",0,"ALICE_waitfee_deposit");
    
    instantdex_addevent(s,*n,"ALICE_waitfee_privs","feefound",0,"ALICE_waitprivs");
    instantdex_addevent(s,*n,"ALICE_waitfee_privs","BTCprivs",0,"ALICE_waitfee");
    
    instantdex_addevent(s,*n,"ALICE_waitdeposit_privs","depfound",0,"ALICE_waitprivs");
    instantdex_addevent(s,*n,"ALICE_waitdeposit_privs","BTCprivs",0,"ALICE_waitdeposit");
    
    instantdex_addevent(s,*n,"ALICE_waitfee_deposit","depfound",0,"ALICE_waitfee");
    instantdex_addevent(s,*n,"ALICE_waitfee_deposit","feefound",0,"ALICE_waitdeposit");
    
    // wait for last event and send out altpayment
    instantdex_addevent(s,*n,"ALICE_waitprivs","BTCprivs","BTCalttx","ALICE_sentalt");
    instantdex_addevent(s,*n,"ALICE_waitfee","feefound","BTCalttx","ALICE_sentalt");
    instantdex_addevent(s,*n,"ALICE_waitdeposit","depfound","BTCalttx","ALICE_sentalt");

    // 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_reclaim",0);
    instantdex_addevent(s,*n,"BOB_sentdeposit","BTCalttx",0,"BOB_altconfirm");
 
    s = instantdex_statecreate(s,n,"BOB_altconfirm",BOB_waitaltconfirmfunc,0,"BTC_claimdeposit",0);
    instantdex_addevent(s,*n,"BOB_altconfirm","altfound","BTCpaytx","BOB_sentpayment");
    
    // 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,"BTC_claimdeposit",0);
    instantdex_addevent(s,*n,"ALICE_sentalt","BTCpaytx",0,"ALICE_waitconfirms");
    
    s = instantdex_statecreate(s,n,"ALICE_waitconfirms",ALICE_waitpayconf_or_bobreclaimfunc,0,"BTC_claimdeposit",0);
    instantdex_addevent(s,*n,"ALICE_waitconfirms","bobfound",0,"ALICE_reclaim");
    instantdex_addevent(s,*n,"ALICE_waitconfirms","payfound","BTCprivM","ALICE_claimedbtc");

    // Bob waits for privM either from Alice or alt blockchain
    s = instantdex_statecreate(s,n,"BOB_sentpayment",BOB_waitprivMfunc,0,"BTC_claimdeposit",0);
    instantdex_addevent(s,*n,"BOB_sentpayment","aclfound","BTCdone","BOB_claimedalt");
    instantdex_addevent(s,*n,"BOB_sentpayment","BTCprivM","BTCdone","BOB_claimedalt");
  

Most process functions should be self explanatory and I made it a linear flow as the protocol proceeds toward completion.

I think the following four claim states are what needs to always be atomic and with FSM we would be able to prove that either BTC_cleanup is called by both sides or BOB_claimdepositfunc and ALICE_claimaltfunc unwinds the swap or ALICE_claimbtcfunc and BOB_claimaltfunc completes the atomic swap.

James
 

[jl777]

Here are the scripts I am using:

both fees are standard payments: OP_DUP OP_HASH160 FEE_RMD160 OP_EQUALVERIFY OP_CHECKSIG

Alice altpayment: OP_2 <alice_pubM> <bob_pubN> OP_2 OP_CHECKMULTISIG

Bob deposit:
OP_IF
    <now + INSTANTDEX_LOCKTIME*2> OP_CLTV OP_DROP <alice_pubA0> OP_CHECKSIG
OP_ELSE
    OP_HASH160 <hash(bob_privN)> OP_EQUALVERIFY <bob_pubB0> OP_CHECKSIG
OP_ENDIF
 
Bob paytx:
OP_IF
    <now + INSTANTDEX_LOCKTIME> OP_CLTV OP_DROP <bob_pubB1> OP_CHECKSIG
OP_ELSE
    OP_HASH160 <hash(alice_privM)> OP_EQUALVERIFY <alice_pubA0> OP_CHECKSIG
OP_ENDIF

Naming convention are pubAi are alice's pubkeys (seems only pubA0 and not pubA1)
pubBi are Bob's pubkeys

privN is Bob's privkey from the cut and choose deck as selected by Alice
privM is Alice's counterpart
pubN and pubM are the corresponding pubkeys for these chosen privkeys

Alice timeout event is triggered if INSTANTDEX_LOCKTIME elapses from the start of a FSM instance. Bob timeout event is triggered after INSTANTDEX_LOCKTIME*2

James

[TierNolan]

Here are the scripts I am using:

both fees are standard payments: OP_DUP OP_HASH160 FEE_RMD160 OP_EQUALVERIFY OP_CHECKSIG

Fees should somehow incorporate the tradeId hash.  That way a trader can't use the same fee for multiple trades.

This could be incorporated into the public keys by multiplying key pairs by a random number selected by the other party.

Bob selects a key pair (fee_pri_bob, fee_pub_bob) and a random number fee_rand_bob.

Note: fee_pub_bob = fee_pri_bob * G

He sends fee_pub_bob and fee_rand_bob to Alice.

Alice computes the same and sends her EC point and random number back.

Bob uses the following key pair

Adjusted Private = fee_pri_bob * fee_rand_alice
Adjusted Public =  fee_pri_bob * fee_rand_alice * G =  fee_rand_alice * (fee_pri_bob * G) = fee_rand_alice * fee_pub_bob

This means that Alice can verify that the public key is unique for this trade (since she can calculate fee_rand_alice * fee_pub_bob), but still doesn't know the matching private key. 

[jl777]

Here are the scripts I am using:

both fees are standard payments: OP_DUP OP_HASH160 FEE_RMD160 OP_EQUALVERIFY OP_CHECKSIG

Fees should somehow incorporate the tradeId hash.  That way a trader can't use the same fee for multiple trades.

This could be incorporated into the public keys by multiplying key pairs by a random number selected by the other party.

Bob selects a key pair (fee_pri_bob, fee_pub_bob) and a random number fee_rand_bob.

Note: fee_pub_bob = fee_pri_bob * G

He sends fee_pub_bob and fee_rand_bob to Alice.

Alice computes the same and sends her EC point and random number back.

Bob uses the following key pair

Adjusted Private = fee_pri_bob * fee_rand_alice
Adjusted Public =  fee_pri_bob * fee_rand_alice * G =  fee_rand_alice * (fee_pri_bob * G) = fee_rand_alice * fee_pub_bob

This means that Alice can verify that the public key is unique for this trade (since she can calculate fee_rand_alice * fee_pub_bob), but still doesn't know the matching private key. 

yes, I will add a tag to the feetx by:

<orderid> OP_DROP OP_DUP OP_HASH160 FEE_RMD160 OP_EQUALVERIFY OP_CHECKSIG

The orderid is unique to a specific orderbook entry. This way, once fee is paid for an atomic sequence, if it fails for whatever reason, you can reuse the feetx. If the feetx is locked to a specific Alice/Bob, that would increase the effect of a nuisance attack (just starting trades without intending to complete them) as the fee wont be able to be reused

James

[jl777]

optimized FSM a bit:

Code:

    s = instantdex_statecreate(s,n,"BTC_cleanup",BTC_cleanupfunc,0,0,0); // from states without any commits
    s = instantdex_statecreate(s,n,"BOB_reclaim",BOB_reclaimfunc,0,0,0); // Bob's gets his deposit back
    s = instantdex_statecreate(s,n,"ALICE_reclaim",ALICE_reclaimfunc,0,0,0); // Alice retrieves alt payment
  
    s = instantdex_statecreate(s,n,"ALICE_claimedbtc",ALICE_claimbtcfunc,0,0,0); // mainstream cases
    s = instantdex_statecreate(s,n,"BOB_claimedalt",BOB_claimaltfunc,0,0,0);

    // 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);
    s = instantdex_statecreate(s,n,"ALICE_sentprivs",ALICE_waitfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_wait3",ALICE_waitfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"BOB_sentdeposit",BOB_waitBTCalttxfunc,0,"BTC_claimdeposit",0);

    // events instantdex_addevent(s,*n,<Current State>,<event>,<message to send>,<Next State>)
    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);
    s = instantdex_statecreate(s,n,"ALICE_sentoffer",BTC_waitdeckCfunc,0,"BTC_cleanup",0);
    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 BTCchose already (along with deck)
    s = instantdex_statecreate(s,n,"BOB_gotoffer",BTC_waitprivCfunc,0,"BTC_cleanup",0);
    s = instantdex_statecreate(s,n,"ALICE_gotoffer",BTC_waitprivCfunc,0,"BTC_cleanup",0);
    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);
    instantdex_addevent(s,*n,"BOB_sentprivs","BTCprivs",0,"BOB_waitfee");
    s = instantdex_statecreate(s,n,"ALICE_sentprivs",BTC_waitprivsfunc,0,"BTC_cleanup",0);
    instantdex_addevent(s,*n,"ALICE_sentprivs","BTCprivs",0,"Alice_waitfee");

    s = instantdex_statecreate(s,n,"BOB_waitfee",BOB_waitfeefunc,0,"BTC_cleanup",0);
    instantdex_addevent(s,*n,"BOB_waitfee","feefound","BTCdeptx","BOB_sentdeposit");
    
    s = instantdex_statecreate(s,n,"Alice_waitfee",ALICE_waitfeefunc,0,"BTC_cleanup",0);
    instantdex_addevent(s,*n,"BOB_waitfee","feefound",0,"ALICE_waitfee_deposit");
   
    // following states cover all permutations of the three required events to make altpayment
    s = instantdex_statecreate(s,n,"ALICE_waitfee_deposit",ALICE_waitfunc,0,"BTC_cleanup",0);
    instantdex_addevent(s,*n,"ALICE_waitfee_deposit","depfound",0,"ALICE_waitfee");
    instantdex_addevent(s,*n,"ALICE_waitfee_deposit","feefound",0,"ALICE_waitdeposit");
    
    // wait for last event and send out altpayment
    instantdex_addevent(s,*n,"ALICE_waitfee","feefound","BTCalttx","ALICE_sentalt");
    instantdex_addevent(s,*n,"ALICE_waitdeposit","depfound","BTCalttx","ALICE_sentalt");

    // 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_reclaim",0);
    instantdex_addevent(s,*n,"BOB_sentdeposit","BTCalttx",0,"BOB_altconfirm");
 
    s = instantdex_statecreate(s,n,"BOB_altconfirm",BOB_waitaltconfirmfunc,0,"BTC_claimdeposit",0);
    instantdex_addevent(s,*n,"BOB_altconfirm","altfound","BTCpaytx","BOB_sentpayment");
    
    // 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,"BTC_claimdeposit",0);
    instantdex_addevent(s,*n,"ALICE_sentalt","BTCpaytx",0,"ALICE_waitconfirms");
    
    s = instantdex_statecreate(s,n,"ALICE_waitconfirms",ALICE_waitpayconf_or_bobreclaimfunc,0,"BTC_claimdeposit",0);
    instantdex_addevent(s,*n,"ALICE_waitconfirms","bobfound",0,"ALICE_reclaim");
    instantdex_addevent(s,*n,"ALICE_waitconfirms","payfound","BTCprivM","ALICE_claimedbtc");

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

[jl777]

I have to add another metaevent to deal with the waiting states, as there is no incoming message to trigger it.

this allows to create states like:

Code:

    s = instantdex_statecreate(s,n,"BOB_waitfee",BOB_waitfeefunc,0,"BTC_cleanup",0);
    instantdex_addevent(s,*n,"BOB_waitfee","feefound","BTCdeptx","BOB_sentdeposit");
    instantdex_addevent(s,*n,"BOB_waitfee","poll","poll","BOB_waitfee");

BOB_waitfee will issue poll events to itself in a loop, until "feefound" event is generated (or timeout)

James

[jl777]

latest revision with all the "poll" events

Code:

   s = instantdex_statecreate(s,n,"BTC_cleanup",BTC_cleanupfunc,0,0,0,0); // from states without any commits
    
    s = instantdex_statecreate(s,n,"BOB_reclaim",BOB_reclaimfunc,0,0,0,0); // Bob's gets his deposit back
    instantdex_addevent(s,*n,"BOB_reclaim","brcfound","poll","BTC_cleanup");
    instantdex_addevent(s,*n,"BOB_reclaim","poll","poll","BOB_reclaim");

    s = instantdex_statecreate(s,n,"ALICE_reclaim",ALICE_reclaimfunc,0,0,0,0); // Alice retrieves alt payment
    instantdex_addevent(s,*n,"ALICE_reclaim","arcfound","poll","BTC_cleanup");
    instantdex_addevent(s,*n,"ALICE_reclaim","poll","poll","ALICE_reclaim");

    s = instantdex_statecreate(s,n,"ALICE_claimedbtc",ALICE_claimbtcfunc,0,0,0,0); // mainstream cases
    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_claimedalt",BOB_claimaltfunc,0,0,0,0);
    instantdex_addevent(s,*n,"BOB_claimedalt","bclfound","poll","BTC_cleanup");
    instantdex_addevent(s,*n,"BOB_claimedalt","poll","poll","BOB_claimedalt");

    // 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_reclaim",0,0);
    s = instantdex_statecreate(s,n,"BOB_altconfirm",BOB_waitaltconfirmfunc,0,"BOB_reclaim",0,0);
    s = instantdex_statecreate(s,n,"BOB_sentpayment",BOB_waitprivMfunc,0,"BOB_reclaim",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_reclaim",0,0);
    s = instantdex_statecreate(s,n,"ALICE_waitconfirms",ALICE_waitpayconf_or_bobreclaimfunc,0,"ALICE_reclaim",0,0);

    // events instantdex_addevent(s,*n,<Current State>,<event>,<message to send>,<Next State>)
    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");

    // 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");

    // 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");

    // 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_reclaim",0,0);
    instantdex_addevent(s,*n,"BOB_sentdeposit","BTCalttx","poll","BOB_altconfirm");
 
    s = instantdex_statecreate(s,n,"BOB_altconfirm",BOB_waitaltconfirmfunc,0,"BOB_reclaim",0,0);
    instantdex_addevent(s,*n,"BOB_altconfirm","altfound","BTCpaytx","BOB_sentpayment");
    instantdex_addevent(s,*n,"BOB_altconfirm","poll","poll","BOB_altconfirm");
    
    // 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_reclaim",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_reclaim",0,0);
    instantdex_addevent(s,*n,"ALICE_waitconfirms","bobfound","poll","ALICE_reclaim");
    instantdex_addevent(s,*n,"ALICE_waitconfirms","payfound","BTCprivM","ALICE_claimedbtc");
    instantdex_addevent(s,*n,"ALICE_waitconfirms","poll","poll","ALICE_waitconfirms");

    // Bob waits for privM either from Alice or alt blockchain
    s = instantdex_statecreate(s,n,"BOB_sentpayment",BOB_waitprivMfunc,0,"BOB_reclaim",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");
    instantdex_FSMtest(s,*n);

I also wrote a bruteforce tester

James

[jl777]

Some benchmarks of just the pure state machine:

BOB_gotoffer BOB_sentprivs BOB_waitfee BOB_waitfee BOB_waitfee BOB_waitfee BOB_waitfee BOB_waitfee BOB_sentdeposit BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_sentpayment BOB_claimedalt reached BTC_cleanup m.20 events most.20 ave 20.00
BOB_sentoffer BOB_sentprivs BOB_waitfee BOB_sentdeposit BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_sentpayment BOB_sentpayment BOB_claimedalt reached BTC_cleanup m.13 events most.34 ave 11.50
BOB_sentoffer BOB_sentprivs BOB_waitfee BOB_sentdeposit BOB_altconfirm BOB_sentpayment BOB_claimedalt reached BTC_cleanup m.8 events most.36 ave 11.50
BOB_gotoffer BOB_sentprivs BOB_waitfee BOB_waitfee BOB_sentdeposit BOB_altconfirm BOB_sentpayment BOB_claimedalt reached BTC_cleanup m.9 events most.36 ave 11.50
ALICE_sentoffer ALICE_sentprivs Alice_waitfee Alice_waitfee Alice_waitfee Alice_waitfee Alice_waitfee ALICE_waitdeposit ALICE_sentalt ALICE_waitconfirms ALICE_waitconfirms ALICE_claimedbtc reached BTC_cleanup m.13 events most.37 ave 11.50
ALICE_sentoffer ALICE_sentprivs Alice_waitfee ALICE_waitdeposit ALICE_waitdeposit ALICE_waitdeposit ALICE_waitdeposit ALICE_waitdeposit ALICE_waitdeposit ALICE_waitdeposit ALICE_sentalt ALICE_waitconfirms ALICE_claimedbtc ALICE_claimedbtc reached BTC_cleanup m.15 events most.37 ave 11.50
BOB_sentoffer BOB_sentprivs BOB_waitfee BOB_sentdeposit BOB_altconfirm BOB_sentpayment BOB_claimedalt reached BTC_cleanup m.8 events most.37 ave 11.50
BOB_gotoffer BOB_sentprivs BOB_waitfee BOB_sentdeposit BOB_altconfirm BOB_sentpayment BOB_claimedalt reached BTC_cleanup m.8 events most.37 ave 11.50
BOB_sentoffer BOB_sentprivs BOB_waitfee BOB_sentdeposit BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_altconfirm BOB_sentpayment BOB_claimedalt BOB_claimedalt reached BTC_cleanup m.12 events most.37 ave 11.50
BOB_sentoffer BOB_sentprivs BOB_waitfee BOB_waitfee BOB_waitfee BOB_waitfee BOB_waitfee BOB_sentdeposit BOB_altconfirm BOB_sentpayment BOB_claimedalt reached BTC_cleanup m.12 events most.37 ave 11.50
 most.37 ave 11.50
elapsed 4711.472 ave 0.000471

units are in milliseconds, so less than half a microsecond per FSM simulation. for each one I randomly choose from the starting states and then just use a random number for the next event until it reaches the terminal event (BTC_cleanup);

Above is from a run of 10 million iterations that took a bit less than 5 seconds, with  printouts of the states for every millionth test.

I think it is safe to say that it is fast enough and also that there are no dead ends in the state machine. I didnt do any coverage stats though, so there might be some orphaned states that are never used.

For the full test point of doing an atomic swap, I have things debugged now until it fails due to invalid transactions. Which is kind of expected as I havent connected up the unspents info to the atomic swap yet. First step is to just hardcode a few unspents for each side and make sure the FSM actually makes them complete a swap if all is well.

Then making the unspents come from internal wallet addresses, etc. It is already connected to the instantdex trading API as the "bitcoin" exchange.

The test sequence is to issue the following on one node:

curl --url "http://127.0.0.1:7778" --data "{\"agent\":\"iguana\",\"method\":\"addcoin\",\"newcoin\":\"BTC\"}"
curl --url "http://127.0.0.1:7778" --data "

{\"agent\":\"InstantDEX\",\"method\":\"sell\",\"exchange\":\"bitcoin\",\"base\":\"BTCD\",\"rel\":\"BTC\",\"price\":0.003,\"volume\":2,\"dotrade\":1}"

It just activates the coin and then submits a sell offer to the network.
Then on the other node:
http://127.0.0.1:7778/api/InstantDEX/orderbook?exchange=bitcoin&base=BTCD&rel=BTC&depth=11&allfields=1&ignore=

http://127.0.0.1:7778/api/InstantDEX/buy?exchange=bitcoin&base=BTCD&rel=BTC&price=.003&volume=2&dotrade=1&password=bob

The first one shows the orderbook (this is optional) and the second one is checked to see if it matches an existing order and if it does, initializes the state machine and sends a message to the other node.

FSM is followed by both sides, states change, even "poll" virtual event appeared to work. Been up for quite a while, so not sure when I will be awake next, but it feels like the home stretch.

The only "attack" that I know of is that an attacker who doesnt care about losing money to annoy people would also have to actively post offers at the best market price (ie. realtime price quotes) and then start trades, only to never complete them. Each "attack" will cost the attacker 0.13% but the "victim" can still recycle the fee that was used as the fee tx is based on the orderid of the offer being matched.

I dont see this as any practical attack as it costs fees and only delays the other nodes that try to do a trade with the attacker and quickly it will get blacklisted. Eventually I can add a historical reputation/percentage completion of started trades as all that info will be on the blockchain, so users can decide what type of nodes they will atomic with.

I will change the random deck back to 1000 so the 0.13% fee with have an expected loss of 13% and so will Bob bailing out and losing his deposit.

James

[jl777]

@TierNolan

What do you think about anonymint's idea of having a user settable coin age requirement for the feetx? The idea is to slow down the annoyance attacks.

Maybe a specific order of fee payment, ie make the initiator pay the fee first to prevent a proactive attacker from waiting for the other side to pay a fee and bail out.

With contingency plan of just issuing refunds for unused fees due to other side disconnecting, and future reputation systems, I dont see this as a big issue, but if there was a technical bullet that just knocks it out completely it would offer a better user experience.

So far when it is all debugged, I dont see any way either side can lose funds. The worst seems to be having some of your funds tied of for a few hours (I am thinking setting the max transaction time of 2 to 3 hours, with a max expiration time of around 8 hours. That way even if papercut attacker locks you up for the maxtime, there is still plenty of time to complete the trade with someone else.

The two places where blockchain confirmations are needed, I have made it adaptive on the bitcoin side as of smaller tx of 0.1 BTC or less it seems that as soon as it is confirmed that is good enoough and for larger ones 1 + sqrt(BTC value) confirms, so 1 BTC is 2 confirms, 4 BTC is 3 confirms, 9 BTC is 4 confirms, etc.

The altcoin side is so variable, I cant think of any better way than having the user specify it on a per coin basis, or even per trade basis.

If some wealthy vandal actually starts doing nuisance attacks, I think we can always institute a non-gameable reputation system or even a real insurance system

Anyway, first things first. Need to get it doing trades using a simple form as input.

James

[TierNolan]

What do you think about anonymint's idea of having a user settable coin age requirement for the feetx? The idea is to slow down the annoyance attacks.

That seems reasonable too.  You are forcing people to expend a finite resource, so they can't spam. 

It could be an issue for people who have just obtained coins and then have to wait a few days to build up coinage. 

Maybe a specific order of fee payment, ie make the initiator pay the fee first to prevent a proactive attacker from waiting for the other side to pay a fee and bail out.

I was thinking that it could be a joint transaction, like with CoinJoin.  Each side would say where they are getting the coins from and then once the tx is built, they can both sign it.  That means that the fee has to be on one of the two coins rather than each paying on their own coin.  This means you need to know the exchange rate, but that can be pulled directly from the trade itself.

I also like the concept of having the transaction finishing transactions allow recovery of the fees.

They could pay the fees to

Code:

IF
  HASH160 <bob_fee_unlock> EQUALVERIFY <alice_pub_key> CHECKSIG
ELSE
  <now + 2 days> CLTV
END

and

Code:

IF
  HASH160 <alice_fee_unlock> EQUALVERIFY <bob_pub_key> CHECKSIG
ELSE
  <now + 2 days> CLTV
END

This means that after 2 days, anyone can claim the output.  If the system becomes popular, that means that miners will take the outputs as fees.  Otherwise, someone could just try to be the first to claim them. 

The _fee_unlock codes would have to be agreed before the cut and choose happens.  They would need to be included in the claim transactions. 

The step 4 output, for example, becomes

Code:

OP_IF
  <now + 1 day> OP_CLTV OP_DROP <bob_pub_1002> OP_CHECKSIG
OP_ELSE
   OP_HASH160 <hash(alice_priv_m)> OP_EQUALVERIFY OP_HASH160 <alice_fee_unlock> OP_EQUALVERIFY <alice_pub_key_1001> OP_CHECKSIG
OP_ENDIF

The nice thing about this is that the fee can be made larger, since it is recovered if the trade completes.

The two places where blockchain confirmations are needed, I have made it adaptive on the bitcoin side as of smaller tx of 0.1 BTC or less it seems that as soon as it is confirmed that is good enoough and for larger ones 1 + sqrt(BTC value) confirms, so 1 BTC is 2 confirms, 4 BTC is 3 confirms, 9 BTC is 4 confirms, etc.

Seems reasonable, but the user should probably be given the option to set a minimum confirm delay.  The other party should be informed, so they don't think they are going to complete the trade in 2 mins and end up having to wait 1 hour for confirms.

[marcus_of_augustus]

watching.

[TPTB_need_war]

What do you think about anonymint's idea of having a user settable coin age requirement for the feetx? The idea is to slow down the annoyance attacks.

That seems reasonable too.  You are forcing people to expend a finite resource, so they can't spam.  

It could be an issue for people who have just obtained coins and then have to wait a few days to build up coinage.

What I suggested to jl777 in a PM, is that he make it (the coin age, a.k.a. "Coin Days Destroyed") a user-adjustable variable so that users can select the tradeoff between delay for themselves and those counter-parties available to trade with, and depending on the level of jamming present at that time. jl777 referred to it as a "rainy day" insurance, which seems an apt characterization of the suggestion.

I have my strong intuitive (generative essence) sense that I will find a flaw in any method of using a fee to block the attacker who wants to jam the protocol, because the fee can't be atomic with the trade (without also opening a jamming window of interaction), so a window of jamming is always opened. Whereas, the coin age is a finite resource which exists (is committed to) prior to the initiation of any protocol for trading. Also it is impossible to use a mixer to hide the identity of the attacker, since mixing will bump the coin age back to 0.

Note my suggestion hinges on the first interaction with the counter-party in the protocol must bump the coin age to 0 on the block chain (else only a local blacklist can be maintained which is much less robust defense). Otherwise the attacker can reuse the same resource over and over to jam with.

Jamming is the main obstacle I forsee impinging on the viability of TierNolan's decentralized exchange protocol. The next obstacle is the very limited scalability of transaction rate for existing block chains, but that is a holistic problem for crypto right now (meaning it MUST be solved else the crypto currency phenomenon dies).

[TPTB_need_war]

continuing from https://bitcointalk.org/index.php?topic=1340621.msg13881127#msg13881127 as it seems the OP locked it for some reason...

The likely reason it was closed is CIYAM got pissed at me (in another thread) and decided to have a temper tantrum (perhaps because I was also supposed to be talking to him soon in Skype about decentralized exchange).

[TierNolan]

What I suggested to jl777 in a PM, is that he make it (the coin age, a.k.a. "Coin Days Destroyed") a user-adjustable variable so that users can select the tradeoff between delay for themselves and those counter-parties available to trade with, and depending on the level of jamming present at that time. jl777 referred to it as a "rainy day" insurance, which seems an apt characterization of the suggestion.

Right.  I suggested something similar.  If 99% of trades that are initiated end up completing the cut-and-choose, then the risk is pretty low.  If a trader is burned, then it can push up the requirement for a fee.

It is a pity that there is no way to commit to a public key.

With coinage, you can actually have it consumed with a gossip network.  To "spend" the coinage, you can sign a message with the public key of the output.  If the person doesn't complete the trade, then you can broadcast the message (or just broadcast it immediately).  The message would contain the tradeId for the output and the current time.  It could reset the coinage to zero, for a weaker blacklist.

Both sides of the trade would lose coinage though.  A spammer should lose it faster than a normal user.

I have my strong intuitive (generative essence) sense that I will find a flaw in any method of using a fee to block the attacker who wants to jam the protocol, because the fee can't be atomic with the trade

You can make it connected with the trade by having the final steps in the protocol release the fee.  If the trade doesn't complete both sides lose money.

[TPTB_need_war]

On further thought, I have decided that my suggestion for coin age is useless by itself and I need to add the following to make it work as intended (while coin age remains necessary else the attacker could use a mixer to create new UXTO that escape the decentralized reputation system I will suggest below).

DoS by jamming is the paramount threat to decentralized exchange that needs to be solved first. If this isn't solved, then it isn't worth pursuing because for sure the government will be against exchanges which they can't regulate to enforce KYC, etc (this will become more so in 2017). Governments have unlimited funds to attack with (e.g. $4+ trillion went missing from the DoD budget and finances the DEEP STATE). Please don't tell me that Donald Rumsfeld and Bill Moyers aren't mainstream and reliable sources.

There is no way to solve the jamming problem by relying on the two block chains that are doing the trade, because someone always has to go first, thus someone will always get jammed. If the honest person never goes first, then no one will go first. Simple logic.

The only way I can hope to fix this problem is to have a separate block chain for recording the intention to enter a trade, and with this block chain track those UXTO which are bailing out and thus users can refuse to trade with them. Again this requires the coin age to prevent the attacker from using a mixer to subvert the tracking by UXTO. Also coin age is necessary so someone doesn't get inadvertently blocked forever due to some glitch on their end where they couldn't follow through on the protocol.

One way I contemplated is to have both parties sign the intention to trade, then they post it to this block chain. However, one might sign and the other might not, thus jamming the other party (in terms of computing the signature and the communication latency between the two parties). Also worse is that one party might sign more than one intention to trade or inadvertently do so if the attacker didn't sign immediately but later signed and published it to this block chain.

Thus the first requirement is we need a way for both to sign where the signature isn't valid if they both didn't complete the signing protocol. I am not sure if this can be accomplished. I would need to think about some variant of Shamir's How to Share a Secret crossed with "simultaneous contract signing". Something like a Diffie-Hellman exchange (but that is sharing a symmetric key) where either party can then sign on behalf of both parties proving that the Diffie-Helman exchange occurred.

If the prior paragraph can be achieved, then the jamming that remains is only on latency of the protocol in the prior paragraph, yet this is still a jamming problem. There is no way for the user who is being jammed to share his UXTO blacklist with other users since the attacker could Sybil attack such sharing.

So thus I conclude that decentralized exchange is probably not going to work unless there is some reputation system. But then when I consider reputation system designs, they can also be Sybil attacked. It seems the only possible solution would be a Web of Trust similar to PGP wherein I decide to trust those who trust me and vice versa. But the problem with Web of Trust in this context is the attacker can Sybil attack it by first gaining trust, then violating trust thus causing the Web of Trust to be unstable.

Sigh.  

If anyone can think of a solution at the conceptual level (never mind what block chains currently offer), I would love to read it.

So far decentralized exchange looks to be jammable in every design I've contemplated.

I have my strong intuitive (generative essence) sense that I will find a flaw in any method of using a fee to block the attacker who wants to jam the protocol, because the fee can't be atomic with the trade

You can make it connected with the trade by having the final steps in the protocol release the fee.  If the trade doesn't complete both sides lose money.

But my point is the jamming will come before that connection has been established.

Also if both sides lose money when one side bails, then the attacker can cause the innocent party to go bankrupt.

You are ostensibly dismissing the case of the attacker who can charge the cost of the attack to collective. Right at this moment, China's mining cartel controls an estimated 65% of Bitcoin's hashrate and they have vetoed every block size increase (even Classic's reasonable doubling to 2MB), and they apparently have very low electricity costs so it isn't unthinkable that with a "wink and a handshake" this electricity is coming for free from Three Gorges Dam. The fact that I have proven they must have lied about the bandwidth problem  (since of course they could put a pool abroad and just relay the hashes across the Great Firewall of China). One motivation could possibly be to force transaction fees higher and reap more profits.

So there is already circumstantial evidence that the attack scenario I am worried about is not impossible.

[jl777]

An attacker with infinite resources that doesnt care about monetary losses...

I claim that such an attacker can bring any network to a standstill. So defending against this is not a high priority in the beginning.

I like the simple approach where the fee (insurance) is prepaid before each trade. The fee is tagged with the orderid of the recipient of the offer, not the initiator of the trade. This means that a papercut attack cannot be done proactively, but only if somebody else initiates a trade with the attacker.

So, that means a reputation system will be effective as trading with newbie accounts will carry some small risk that they are a papercut attacker who set a trap.

By linking the fee to the orderid of the one that posted the bid/ask, that means the papercut attack only delays as the fee that was paid is still valid for completing the atomic swap with a real peer. The attacker cant reuse the fee paid, so this is assymetric in a good way.

Granted the victim will be out a fee if their bid expires without the trade being completed. We are talking about 0.13% in the event of an attack, so most of the time not even worth going through a claim process.

But maybe an active trader over time will accumulate a bunch of such failed fees, and I think if there was some sort of automated claim process for this, it solves the practical issues of this theoretical problem.

Before you start complaining that requires trust that this process will be honored, my response is that if this attack scenario remains hypothetical, then it is not an issue. If it does happen and the fees paid for failed swaps are not refunded, then that will damage the reputation of InstantDEX and so there is strong incentive to keep the customer's happy. Keep in mind it is the 0.13% fees that are lost due to an attacker that doesnt care about losing money and just wants to jam things. Typically non-economically viable attacks are not a big priority to solve. But I dont want there to be any obstacles to using InstantDEX, so I will commit to refund the fees paid for atomic swaps that dont complete, as long as the txfees needed to send out the refunds are less than 10% of the refund.

As opposed to having 100% of your capital at risk when you use centralized exchanges.

James

[hv_]

Pardon. Reading the header with SWAP and then parsing the story I finally understand you try to achieve just an "easy" crypto ccy SPOT trade (Even more correct a same day forward) by executing one of the "easiest" smart contract and already struggle with that?

Why not trying some betting stuff? (Sorry, just caspering around a bit  )
I really want to know and see such easy stuff working before more complex things should be developed, savely....

How about some 2factor like mechano?