ACCT using CLTV - More Effective than a sleeping pill!

[jl777]

There is an attack on the cut-and-choose.

An attacker could keep starting trades and perform the cut-and-choose step with 1 invalid pair.  If they get detected (99.9%), then they can abort the trade.

Since there is no fee paid for step 1, there is no cost to the attacker.

I have updated the protocol to add a step 0.  This slows things down since there is another commit step.

There is a tradeoff between complexity and performance.

If the altcoin supports CLTV, it could be used directly. 

It is possible that there is an improved protocol for altcoins which support the more flexible P2SH IsStandard rules.

I would split altcoins into 3 ranks.

Rank 1 coins support CLTV
Rank 2 coins skip the IsStandard check for P2SH outputs
Rank 3 coins only allow standard outputs, even for P2SH

Bitcoin moved from rank 3 to rank 2 about 18 months ago and to rank 1 with the release of CLTV.

On the other hand, a single protocol for all altcoins keeps things simple.

It would be necessary to be clear that there is a 0.1% chance of attack.  With the step 0 fee commit, it isn't in anyone elses interests to cheat.

This solves the issue I PM'ed you about and removes the costless locking up of funds. so I will update my code with that

James

[jl777]

Assuming I do launch something it will only be supporting the Rank 1 coins (i.e. the least complexity) and if that only includes BTC and LTC then I'm okay with that.

That seems reasonable for version 1, at least.  With CLTV, there is no cut-and-choose risk.

I wonder if something like the Lightening network could be accomplished.  In that case, trustless hubs could be created.  To perform the trade, the trade happens with the hubs acting as trade hubs.  The trade hubs could support multiple altcoins.

It would be a p2p network with 2 types of nodes (or at least 2 specialties).  As long as you connect to a few hubs, you could trade with anyone on the network.

Using zero-conf methods can eliminate the wait for blocktimes and for small value trades is probably ok.

I think it would be possible to have the payment channels do instant payments, but it would require dedicated nodes being the hubs. I guess if they are getting some fees, that would fund them and incentivize people to run them.

The thing I dont like about micropayment channels is that a lot of trades will get delayed if a hub goes offline. But with CLTV maybe a lot of the contortions required in the past can be cleaned up. I expect to have a debugged proof of concept by this weekend for the above plan, so if you can specify in a bit more about the lightening hubs, I can see about coding it up next week.

I did a proof of concept for this a year and a half ago, I called it subatomic trades.

Assuming we have enough hubs and not worry about their reliability (as long as hub failure just means a refund to unwind the trade), then before a node can start trading then setup a pair of micropayment channels for BTC and each coin they want to trade. Once that is setup, they can trade in either direction up to the limit of their deposit amount.

alice <-> hub.btc <-> bob
alice <-> hub.alt  <-> bob

bob and alice agree to trade, with bob sending bitcoins to alice and alice sending alts back
each side sends 1/777'th of the value to the hub
the hub forwards to the other node
when a fractional payment is received, the next payment is sent, until trade is complete

No party is ever at risk more than 0.13%
There is a lot more error states possible with this as the deposit might not be enough for a desired trade, reclaiming unused funds is part of the expected process, etc. However, now that I have the networking side working pretty good, I think the advantage of having a set of hubs with payment channels already setup would allow for nearly realtime trading. with 777 increments, the ping times will be the bottleneck, so estimating 300 millis ping time -> a few minutes...

which is not great, but maybe the number of increments can be reduced to 100, then we have trades completed in less than a minute and nice side effect is you can see a progress bar as the trade is completing

Of course, the above can probably be improved to make it much more usable.

James

[TierNolan]

Assuming I do launch something it will only be supporting the Rank 1 coins (i.e. the least complexity) and if that only includes BTC and LTC then I'm okay with that.

That seems reasonable for version 1, at least.  With CLTV, there is no cut-and-choose risk.

I wonder if something like the Lightening network could be accomplished.  In that case, trustless hubs could be created.  To perform the trade, the trade happens with the hubs acting as trade hubs.  The trade hubs could support multiple altcoins.

It would be a p2p network with 2 types of nodes (or at least 2 specialties).  As long as you connect to a few hubs, you could trade with anyone on the network.

Using zero-conf methods can eliminate the wait for blocktimes and for small value trades is probably ok.

I think it would be possible to have the payment channels do instant payments, but it would require dedicated nodes being the hubs. I guess if they are getting some fees, that would fund them and incentivize people to run them.

The thing I dont like about micropayment channels is that a lot of trades will get delayed if a hub goes offline. But with CLTV maybe a lot of the contortions required in the past can be cleaned up. I expect to have a debugged proof of concept by this weekend for the above plan, so if you can specify in a bit more about the lightening hubs, I can see about coding it up next week.

I haven't fully look at the entire Lightening network rules.

One of their nice innovations is transaction canceling.  They pay to an output that can only be spent after a delay or by a 2 of 2 multisig.  If you give the 2nd private key to the person who has the first key, then the transaction is effectively cancelled.  If you broadcast the transaction, then the other person can spend the output.

It may require the relative version of checklocktime though (to do the delay).

I was mostly just thinking about possible options to speed things up.

Assuming we have enough hubs and not worry about their reliability (as long as hub failure just means a refund to unwind the trade)

I am not sure how that works.  I think Lightening might have a re-routing option.

alice <-> hub.btc <-> bob
alice <-> hub.alt  <-> bob

One of the extra things with an exchange is that both transactions must be happen atomically.  Lightening is a single way transaction.

bob and alice agree to trade, with bob sending bitcoins to alice and alice sending alts back
each side sends 1/777'th of the value to the hub
the hub forwards to the other node
when a fractional payment is received, the next payment is sent, until trade is complete

Yeah, that is the benefit of channels.  You can build up the transaction in parts.

which is not great, but maybe the number of increments can be reduced to 100, then we have trades completed in less than a minute and nice side effect is you can see a progress bar as the trade is completing

You could ramp it up.  The first step could be 0.1% and then ramp up the step size exponentially.

[TierNolan]

Lightning nodes effectively say "If you can find x such that Hash(x) = h within the next d days, then I will pay you b Bitcoins".  The node then says to the next link in the chain "If you can find x such that Hash(x) = h within the next (d - 1) days, then I will pay you b Bitcoins".

Finally, the recipient tells the last node what x is.  Each node passes it on to the next node.  This causes the money to be transferred.

Once the payment goes through, all nodes issue new transactions.  The new transactions don't change the state of the channel, but reset it back to the full timeout.  Once that happens, the previous transactions are revoked by sending special revoke codes.

If the same x is used for the channels on both coins, then I think it will allow a circle transfer.

[TierNolan]

I think it would be possible to have the payment channels do instant payments, but it would require dedicated nodes being the hubs. I guess if they are getting some fees, that would fund them and incentivize people to run them.

Looks like Lightning can handle multiple chains by having 2 transactions using the same hash.  The question is if legacy altcoins can handle lightning channels.  Cut-and-choose might allow bypassing the malleability problems.  It needs more thought.

The thing I dont like about micropayment channels is that a lot of trades will get delayed if a hub goes offline. But with CLTV maybe a lot of the contortions required in the past can be cleaned up. I expect to have a debugged proof of concept by this weekend for the above plan, so if you can specify in a bit more about the lightening hubs, I can see about coding it up next week.

Channels don't have to fully "lock" even if a hub goes down.

If only 10% of the funds in the channel are committed, then the other 90% can still be used.

If a transaction was broken down into 10 pieces, then a hub going down would only stall one of the pieces.

Hubs might even insure against nodes going down.  They could say that they will cover the loss if another hub that they routed through dies (or pay compensation if they go down).

[TierNolan]

This is a way to simulate a Lightning network on a Rank 2 altcoin.  The outputs would have to use P2SH in order to support the non-standard scripts.

Since the timeouts are in the days range, it would be enough to have 1 miner who will accept non-standard scripts.  Additionally, if cross chain Lightning was to become popular, the relaxing the IsStandard rules would be an easy change.

This is the basics of a protocol.  

Step 1) fund deposits

Bob and Alice commit to hash(bob_priv_0) and hash(alice_priv_0) using the cut and choose.

On Bitcoin, Bob funds a transaction which pays D to 3 outputs.

Code:

OP_IF
  <now + 40 days> OP_CLTV <alice_pub_0> OP_CHECKSIG
OP_ELSE
  OP_HASH160 <hash(bob_priv_0)> OP_EQUALVERIFY <bob_pub_0> OP_CHECKSIG
OP_ENDIF

and

Code:

OP_IF
  <now + 20 days> OP_CLTV <alice_pub_0> OP_CHECKSIG
OP_ELSE
  OP_HASH160 <hash(bob_timelock_early)> OP_EQUALVERIFY <bob_pub_0> OP_CHECKSIG
OP_ENDIF

and

Code:

OP_IF
  <now + 30 days> OP_CLTV <alice_pub_0> OP_CHECKSIG
OP_ELSE
  OP_HASH160 <hash(bob_timelock_late)> OP_EQUALVERIFY <bob_pub_0> OP_CHECKSIG
OP_ENDIF

Alice also pays 3*D to the equivalent.

This means that they both promise to publish the private keys within 40 days and their timelocks within 20 and 30 days.  The timelocks are the key to simulating CLTV on legacy altcoins.

The two timelocks are needed due to the hash locking.  All hash locks time out after 20 days.  The revokes timeout after 30 days and the channel/bail-in times out after 40 days.

Step 2) Both bail-in

Alice and Bob fund a transaction with 2 outputs

Pays b

Code:

OP_2 <bob_pub_1> <alice_pub_0> OP_2 OP_CHECKMULTISIG

Pays a

Code:

OP_2 <bob_pub_0> <alice_pub_1> OP_2 OP_CHECKMULTISIG

After 40 days, Bob will be able to spend the first output and Alice will be able to spend the 2nd.

Step 3) Create balance transaction

Alice picks a value alice_n and Bob picks a value bob_n.  They compute the hashes and send the digests to the other party.

Create two transactions that spend both outputs of the bail-in transaction.

Bob.penalty.n has these outputs

a = Alice's balance
b = Bob's balance

Pays b to

Code:

OP_IF
  OP_HASH160 <hash(alice_timelock_late)> OP_EQUALVERIFY <bob_pub_n> OP_CHECKSIG
OP_ELSE
  OP_HASH160 <hash(bob_n)> OP_EQUAL_VERIFY <alice_pub_n> OP_CHECKSIG
OP_ENDIF

Pay a to

Code:

<alice_pub_n> OP_CHECKSIG

Alice.penalty.n has these outputs

Pays b

Code:

<bob_pub_n> OP_CHECKSIG

Pays a

Code:

OP_IF
  OP_HASH160 <hash(bob_timelock_late)> OP_EQUALVERIFY <alice_pub_n> OP_CHECKSIG
OP_ELSE
  OP_HASH160 <hash(alice_n)> OP_EQUAL_VERIFY <bob_pub_n> OP_CHECKSIG
OP_ENDIF

Alice signs Bob.penalty.0 and sends the signature to Bob.  Likewise, Bob sends the signature for Alice.penalty.0.

They both sign their transactions and each has one transaction with both signatures.

Once they have done this, they send the revoke code for the previous balance transaction (alice_(n-1) and bob_(n-1)).

With the revoke codes, the earlier transactions are worthless.  For example, if Bob broadcast Bob.penalty.n after sending bob_n to Alice, then she could spend the output before he had a chance to claim his output.

By creating new balance transactions, Bob and Alice can update the balance to any value that they want.  They need to make sure to send the revoke codes.

Step 4) Create hashlocked output

Bob (or Alice) can create hashlocked outputs.

It is the same as a balance transaction, but with an extra hashlocked output.

Bob.penalty.n has these outputs

a = Alice's balance
b = Bob's balance
h = hashlocked funds (Alice's in this example)

Pays b-h to

Code:

OP_IF
  OP_HASH160 <hash(alice_timelock_late)> OP_EQUALVERIFY <bob_pub_n> OP_CHECKSIG
OP_ELSE
  OP_HASH160 <hash(bob_n)> OP_EQUAL_VERIFY <alice_pub_n> OP_CHECKSIG
OP_ENDIF

Pay a to

Code:

<alice_pub_n> OP_CHECKSIG

Pay h to

Code:

OP_HASH160 <hash(unlock)> OP_EQUAL_VERIFY <alice_pub_n> OP_CHECKSIG

Alice.penalty.n has these outputs

Pays b-h

Code:

<bob_pub_n> OP_CHECKSIG

Pays a

Code:

OP_IF
  OP_HASH160 <hash(bob_timelock_late)> OP_EQUALVERIFY <alice_pub_n> OP_CHECKSIG
OP_ELSE
  OP_HASH160 <hash(alice_n)> OP_EQUAL_VERIFY <bob_pub_n> OP_CHECKSIG
OP_ENDIF

Pays h

Code:

OP_IF
  OP_HASH160 <hash(alice_timelock_late)> OP_EQUALVERIFY <bob_pub_n> OP_CHECKSIG
OP_ELSE
  OP_IF
    OP_HASH160 <hash(bob_timelock_early)> OP_EQUALVERIFY OP_HASH160 <hash(unlock)> OP_EQUAL_VERIFY <alice_pub_n> OP_CHECKSIG
  OP_ELSE
    OP_HASH160 <hash(alice_n)> OP_EQUAL_VERIFY <bob_pub_n> OP_CHECKSIG
  OP_ENDIF
OP_ENDIF

They do the same signing, so Bob has a fully signed Bob.penalty.n and Alice has a fully signed Alice.penalty.n.

Once that is done, they revoke the previous transactions.  Like the balance transaction, this one is revokable.

Unlike the Lightning network, the hashlock timeout is fixed.

If Alice was to obtain <unlock>, then they can revert to a balance transaction and then cancel this transaction.

Additionally, the channel can support multiple hash locked outputs (in either direction) by adding more outputs.

The process is always to create a new transaction and then cancel the old state.

When they finally decide to cancel the transaction, they can just sign a transaction which splits the funds accordingly.

[TierNolan]

I created a BIP that would remove the need for cut-and-choose.

[TierNolan]

When using a deposit for channel establishment, it is possible to reclaim the deposit once the root transaction is locked (if both cooperate).

Bob pays D to the following output

Code:

IF
   <now + 1 day> CLTV EQUALVERIFY <Alice's public key> OP_CHECKSIG
ELSE
  OP_IF
    HASH160 <hash(alice_deposit_lock)> EQUALVERIFY 
    HASH160 <hash(bob_deposit_lock)> EQUALVERIFY 
  ELSE
    HASH160 <hash(bob_priv_key> EQUALVERIFY
  ENDIF
  <Bob's public key> OP_CHECKSIG
ENDIF    

Alice pays the same to the equivalent.

Bob can reclaim his deposit by publishing his private key for the multisig.  If Alice has given him her deposit lock code, then he can claim it using that and keep his private key secret.  In that case, he must inherently release his deposit lock code.  The process is symmetric.

Once the multisig output has been properly committed on the altchain, Bob and Alice can sign a stable refund transaction with a locktime in the future (it can be more than 1 day).  Once they have completed that step, the deposit is no longer needed.  At that point they can swap deposit unlock codes.  If one of them withholds their lock code after receiving the other party's code, they can't make use of it without inherently releasing their code.

The effect is that the deposit would only be locked for a short period of time during setup rather than being locked for the entire protocol.

I think the step "Create a multisig output with a locked refund on the altchain" could be made different for the different grades of coin and then the rest of any protocol kept the same.

[jl777]

Very nice!

I decided to put these protocols into state machines, as it is very easy to misunderstand a step in the process. The following is an undebugged set of states and transitions of the cut and choose:

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

A few more states are needed for full recovery in all the different cases, but I think the mainstream cases are very close to correct.

James

[TierNolan]

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.