Atomic swaps using cut and choose

[jl777]

I do not comprehend why you guys are unable to specify the protocol completely in one page or post. I can't analyze piecemeal.

The finite state machine above defines rigorously all states and state transitions.

The bitcoin utxo requires both the temporary privkey and a signature from Bob's real privkey for the pubkey that the utxo pays to. To my knowledge you cant just use the onetime entropy from this output and use it to spend anything other than the specific transactions that are spent that require that magic number.

You could trust me and TierNolan on this point if you dont understand the bitcoin scripts.
The script at the high level is:

if ( temporary privkey is revealed and Bob has also signed the transaction )
   then you can spend this output

So knowing the temporary privkey is necessary, but insufficient to spent that specific UTXO. Also, it is a onetime use privkey that only the transactions involved in this swap will ever refer to. unless Bob mistakenly funds more utxo using the temporary privkey, there arent any other utxo to worry about. The specific utxo is already paying Bob, plus requires Bob to sign it.

In a market where coins without any working blockchain are trading hundreds of thousands USD per day, it seems a bit unrealistic to wait for sanity and technical updates. Why would they bother if they are already getting massive volumes and decent marketcaps? Especially if they dont have a dev team anymore.

If you don't think there is a massive demand for decentralized exchange, then why even bother.

I have no idea how you interpret what I wrote as there isnt demand. My point is many coins are being traded on central exchanges that dont even have a dev team, so assuming they will update to latest scripts will be a very long wait.

Meaning that it is necessary, but not necessarily sufficient to support altcoins without support for CLTV. And the only way to find out if there will be demand for DE is to get it to work with more than a few coins

James

[TPTB_need_war]

I do not comprehend why you guys are unable to specify the protocol completely in one page or post. I can't analyze piecemeal.

The finite state machine above defines rigorously all states and state transitions.

I do not (readily) comprehend the notation (and nor will I invest effort to learn or decipher the notation). I assume a proper specification would be more comprehensible to more people. However, do not feel obligated to do it for me. I can simply stop posting in the thread, which some parties might prefer any way.

The bitcoin utxo requires both the temporary privkey and a signature from Bob's real privkey for the pubkey that the utxo pays to.

This sentence is ambiguous to me. I would prefer a proper specification of what you are thinking about and attempting to describe.

You could trust me and TierNolan on this point if you dont understand the bitcoin scripts.

I do not trust anything which I can't verify and understand. But don't worry about me. If you are 100% sure, then no need for peer review. Right?

So knowing the temporary privkey is necessary, but insufficient to spent that specific UTXO. Also, it is a onetime use privkey that only the transactions involved in this swap will ever refer to. unless Bob mistakenly funds more utxo using the temporary privkey, there arent any other utxo to worry about. The specific utxo is already paying Bob, plus requires Bob to sign it.

I have no idea what part of the un(der)specified protocol you are referring to above.

In a market where coins without any working blockchain are trading hundreds of thousands USD per day, it seems a bit unrealistic to wait for sanity and technical updates. Why would they bother if they are already getting massive volumes and decent marketcaps? Especially if they dont have a dev team anymore.

If you don't think there is a massive demand for decentralized exchange, then why even bother.

I have no idea how you interpret what I wrote as there isnt demand. My point is many coins are being traded on central exchanges that dont even have a dev team, so assuming they will update to latest scripts will be a very long wait.

I understood your point and my point is if there is demand, then the market will fulfill that demand. Coins that are dying, will die. The market is able to route around such failure.

Of course if you can provide backward compatibility, then of course you may want to provide it. But if it can't be technical sound, then obviously it shouldn't be done. Not much to argue about.

[jl777]

I do not trust anything which I can't verify and understand. But don't worry about me. If you are 100% sure, then no need for peer review. Right?

We are trying to explain, but the solution requires understanding of precisely how bitcoin scripts work generally https://en.bitcoin.it/wiki/Script and most importantly the specific opcodes used. If you say you dont understand them and then say you cant verify, well it seems to lead to an impasse... So you need to trust me and Tier about the details of scripts or bite the bullet and dive into the details of the scripts. Tier is world leading expert at squeezing the most functions from scripts and making them do things even I didnt think were possible to do with them.

You can verify the high level design and trust that the scripts implement the AND requirement of the temporary privkey and Bob's signature using the real privkey that generated the pubkey that is part of the utxo.

We tried to explain in english, but these scripts are indeed quite confusing. I like to get them done once and for all and not deal with them if possible. Regardless of specs, if the scripts are not understood, I dont see how it can be fully verified.

Plz blame TierNolan for the scripts

IF
    <now + 2 days> CLTV DROP <Alice's real public key> CHECKSIG
ELSE
    HASH160 <hash(Bob's temp private key)> EQUALVERIFY <Bob's real public key 2> CHECKSIG
ENDIF

the above is the script. it is an if/else statement, the one that spends it selects which branch he wants to execute by pushing a 0 or 1 prior to executing the script, the following would be how to redeem the above script for the two cases:

<alice signature for real pubkey> 0
or
<bob signature for real pubkey> <bob's temp privkey> 1

http://www.cs.princeton.edu/~tongbinw/bitcoinIDE/build/editor.html is a cool script interpreter that allows you to single step through scripts. It doesnt handle all opcodes, but it is still quite useful.

So to spend the second output, Bob has to sign the tx and assuming it is using SIGHASH_ALL what is signed is the tx that has all the other inputs blanked and the output script substituted. https://en.bitcoin.it/wiki/Transaction explains with some details how to properly sign things, but it is quite messy and I was happy when I got it so I can sign arbitarily constructed tx json objects and it dealt with all the craziness required.

Anyway, bob gets the ~70 byte signature of the hash of the modified tx, adds a 0x01 (for SIGHASH_ALL) and pushes that to the stack along the temporary privkey and a 1 to choose the else path.

Now when both halfs are put together:

<bob signature for real pubkey> <temp privkey> 1  IF <now + 2 days> CLTV DROP <Alice's real public key> CHECKSIG ELSE  HASH160 <hash(Bob's temp private key)> EQUALVERIFY <Bob's real public key 2> CHECKSIG ENDIF

The above is the combined script that needs to evaluate to true.

pretending I am a script interpreter, the first three things go on the stack:

1
<temp privkey>
<sig>

Now the IF see the one (and eats it) and goes to the else branch since it is a 1 and not 0

stack is:
<temp privkey>
<sig>

remaining script: HASH160 <hash(Bob's temp private key)> EQUALVERIFY <Bob's real public key 2> CHECKSIG

The HASH160 does rmd160(sha256(<temp privkey>)) and replaces the top of stack:

rmd160(sha256(<temp privkey>))
<sig>

remaining script: <hash(Bob's temp private key)> EQUALVERIFY <Bob's real public key 2> CHECKSIG

the value from the output is pushed and the EQUALVERIFY pops off two and aborts if not equal. since both are the same it passes this test and we are down to the last check.

stack: <sig>
script:  <Bob's real public key 2> CHECKSIG

Now the CHECKSIG makes sure that it was signed by the privkey that generated the real pubkey

Hopefully that is enough detail and background so you can personally verify that even if Bob's temp privkey is broadcast to the world, it wont do anybody any good.

James

[TPTB_need_war]

Again I don't understand any of that.

I simply asked if Bob is transacting on a block chain without Bitcoin op codes, how can his payment to Alice be required (by the Bitcoin block chain) before he can finalize the transaction on the block chain with Bitcoin CLTV op code. It should be possible to explain this in English.

Stated in another way, what prevents Bob from finalizing the transaction on the block chain with Bitcoin CLTV op code, taking the funds from Alice, while also not issuing the reciprocal transaction paying to Alice on the other block chain?

What I am getting at is that is seems to me (my understanding of the cut & choose as underspecified in English) that Bob has not issued any transaction before Alice's transaction paying to Bob is confirmed on the block chain with Bitcoin CLTV op code. Thus the only way I can see that Bob can be required to issue that said transaction paying to Alice (when employing cut & choose on a block chain without Bitcoin op codes), is if the private key for signing the transaction for Bob paying to Alice (on the block chain without Bitcoin op codes) is revealed in order to finalize the already confirmed transaction for Alice paying to Bob (on the block chain with the CLTV Bitcoin op code). And I have already explained that would not be technically sound because anyone could spend Bob's UXTO (instead of it paying to Alice, and afaics Bob could pay himself). So obviously I must be unaware of some aspect of the protocol, because obviously you two would have realized that the above assumption would not be technically sound.

You can verify the high level design and trust that the scripts implement the AND requirement of the temporary privkey and Bob's signature using the real privkey that generated the pubkey that is part of the utxo.

That sentence is underspecified. What is a 'real privkey'? Aren't all private keys real. Could you please state what you really mean and take the time to form a sentence that specifies which block chain you are referring, how it relates the protocol steps, etc..

I can't verify the high level design because the high level algorithm is underspecified per my question above.

We tried to explain in english, but these scripts are indeed quite confusing.

It doesn't need to be confusing. Just takes time to slow down and formulate well thought out English description.

Einstein once said (paraphrasing), that an expert doesn't completely understand his own craft until he can explain it to a layman.

[jl777]

Thus the only way I can see that Bob can be required to issue that said transaction paying to Alice (when employing cut & choose on a block chain without Bitcoin op codes), is if the private key for signing the transaction for Bob paying to Alice (on the block chain without Bitcoin op codes) is revealed in order to finalize the already confirmed transaction for Alice paying to Bob (on the block chain with the CLTV Bitcoin op code).

I believe the red part is what causes the confusion.

What is being revealed is just a random number, NOT the privkey for signing the transaction.
This tx is made so this random number must be revealed for the tx to be valid.

I think this point needs to be understood first. The random number has both algebraic properties itself and it is part of the 1000 cut and choose dataset, but that really has little to do with the point you are complaining about.

James

[TPTB_need_war]

I would be grateful if you or TierNolan could actually answer my question?

Stated in another way, what prevents Bob from finalizing the transaction on the block chain with Bitcoin CLTV op code, taking the funds from Alice, while also not issuing the reciprocal transaction paying to Alice on the other block chain?

I seem to never get a straight answer.

[jl777]

I would be grateful if you or TierNolan could actually answer my question?

Stated in another way, what prevents Bob from finalizing the transaction on the block chain with Bitcoin CLTV op code, taking the funds from Alice, while also not issuing the reciprocal transaction paying to Alice on the other block chain?

I seem to never get a straight answer.

In order to spend the funds from Alice, bob has to disclose the random number Alice can use to spend the bitcoins

[TPTB_need_war]

I would be grateful if you or TierNolan could actually answer my question?

Stated in another way, what prevents Bob from finalizing the transaction on the block chain with Bitcoin CLTV op code, taking the funds from Alice, while also not issuing the reciprocal transaction paying to Alice on the other block chain?

I seem to never get a straight answer.

In order to spend the funds from Alice, bob has to disclose the random number Alice can use to spend the bitcoins

Afaics, you have not answered my question. Please read my question again. I didn't ask how Bob finalizes the payment from Alice to Bob. I asked, "while also not issuing the reciprocal transaction paying to Alice on the other block chain?". Alice can't spend Bitcoins, because Bob is issuing a transaction on a block chain that is not Bitcoin (and doesn't support CLVT).

Are you implying that Bob will issue his transaction first (paying to Alice) on the block chain without a CLVT op code? Then how does Bob get a refund if Alice doesn't complete her side of the transaction and how can Bob's transaction be verified against a hash of a random number when the CLVT op code isn't supported.

[jl777]

I would be grateful if you or TierNolan could actually answer my question?

Stated in another way, what prevents Bob from finalizing the transaction on the block chain with Bitcoin CLTV op code, taking the funds from Alice, while also not issuing the reciprocal transaction paying to Alice on the other block chain?

I seem to never get a straight answer.

In order to spend the funds from Alice, bob has to disclose the random number Alice can use to spend the bitcoins

Afaics, you have not answered my question. Please read my question again. I didn't ask how Bob finalizes the payment from Alice to Bob. I asked, "while also not issuing the reciprocal transaction paying to Alice on the other block chain?". Alice can't spend Bitcoins, because Bob is issuing a transaction on a block chain that is not Bitcoin (and doesn't support CLVT).

Are you implying that Bob will issue his transaction first (paying to Alice) on the block chain without a CLVT op code? Then how does Bob get a refund if Alice doesn't complete her side of the transaction and how can Bob's transaction be verified against a hash of a random number when the CLVT op code isn't supported.

The simple act of spending the payment requires to disclose the information the other party needs to do their spend.

Ignoring fees, at the high level:
1. bob sends in a deposit that alice verifies she can spend after a certain amount of time. However if bob follows the protocol, he can reclaim this refund before alice is eligible to.

2. alice verifies the above is in the blockchain so is assured that worst case she can get the deposit, which is 113% of the transaction amount, so she might actually prefer that. when assured she sends bob a payment that requires both secrets to be spent.

3. bob sees this on the altcoin chain and sends in a payment to alice that requires a secret from alice that would allow him to spend the payment from 2.

4. alice sees this real payment and then cashes in the bitcoins, but in doing so has to divulge the secret bob needs to spend the altcoins

5. bob gets the required secret from alice and spends the altcoins

So the high level concepts are to advance to each stage only when you are assured that the other side is following the protocol and the FSM is setup so that if either party bails at any point, the funds in limbo can be reclaimed.

To verify this, the bitcoin scripts must be understood in detail. I see no other way. Conceptually, it is a single pull, double throw switch where a single random number releases two transactions

James

[TPTB_need_war]

I would be grateful if you or TierNolan could actually answer my question?

Stated in another way, what prevents Bob from finalizing the transaction on the block chain with Bitcoin CLTV op code, taking the funds from Alice, while also not issuing the reciprocal transaction paying to Alice on the other block chain?

I seem to never get a straight answer.

In order to spend the funds from Alice, bob has to disclose the random number Alice can use to spend the bitcoins

Afaics, you have not answered my question. Please read my question again. I didn't ask how Bob finalizes the payment from Alice to Bob. I asked, "while also not issuing the reciprocal transaction paying to Alice on the other block chain?". Alice can't spend Bitcoins, because Bob is issuing a transaction on a block chain that is not Bitcoin (and doesn't support CLVT).

Are you implying that Bob will issue his transaction first (paying to Alice) on the block chain without a CLVT op code? Then how does Bob get a refund if Alice doesn't complete her side of the transaction and how can Bob's transaction be verified against a hash of a random number when the CLVT op code isn't supported.

The simple act of spending the payment requires to disclose the information the other party needs to do their spend.

Ignoring fees, at the high level:
1. bob sends in a deposit that alice verifies she can spend after a certain amount of time. However if bob follows the protocol, he can reclaim this refund before alice is eligible to.

You've apparently swapped the block chains of Alice and Bob relative to scenario I described. But that is okay, I will follow your choice, where Bob is transacting on the block chain with CLTV and Alice is not.

The transaction above signed by Bob I assume requires CLTV (Check-Lock-Time-Verify) since it must be refunded if it is not verified before the timeout of the lock.

2. alice verifies the above is in the blockchain so is assured that worst case she can get the deposit, which is 113% of the transaction amount, so she might actually prefer that. when assured she sends bob a payment that requires both secrets to be spent.

I don't understand how Alice can receive the CLTV output unless she already knows how to verify it. But if she knows how to verify it, then she can steal it at any time.

How can Alice send a payment that requires verification of two secrets if the other block chain doesn't support pay contingent on verification of hash preimage?

3. bob sees this on the altcoin chain and sends in a payment to alice that requires a secret from alice that would allow him to spend the payment from 2.

Bob issued the deposit in #1 and now he also issues another payment to Alice, but which is spendable by Alice contingent on knowing the preimage (secret) of a hash. Only Alice knows this secret preimage at this point until she reveals it. I thus understand this step #3.

4. alice sees this real payment and then cashes in the bitcoins, but in doing so has to divulge the secret bob needs to spend the altcoins

I am disputing whether Alice can make such a transaction available in step #2 if her altcoin doesn't support pay contingent on verification of hash preimage.

Edit: I understand you want to use a forfeitable deposit to ensure that Bob does step #3, since Alice has no way to refund step #2 (because her block chain doesn't support CLTV). I presume you are assuming that the altcoin supports pay contingent on verification of hash preimage. But I still don't see how the mechanics of the forfeitable deposit work? "I don't understand how Alice can receive the CLTV output unless she already knows how to verify it. But if she knows how to verify it, then she can steal it at any time."

[jl777]

I would be grateful if you or TierNolan could actually answer my question?

Stated in another way, what prevents Bob from finalizing the transaction on the block chain with Bitcoin CLTV op code, taking the funds from Alice, while also not issuing the reciprocal transaction paying to Alice on the other block chain?

I seem to never get a straight answer.

In order to spend the funds from Alice, bob has to disclose the random number Alice can use to spend the bitcoins

Afaics, you have not answered my question. Please read my question again. I didn't ask how Bob finalizes the payment from Alice to Bob. I asked, "while also not issuing the reciprocal transaction paying to Alice on the other block chain?". Alice can't spend Bitcoins, because Bob is issuing a transaction on a block chain that is not Bitcoin (and doesn't support CLVT).

Are you implying that Bob will issue his transaction first (paying to Alice) on the block chain without a CLVT op code? Then how does Bob get a refund if Alice doesn't complete her side of the transaction and how can Bob's transaction be verified against a hash of a random number when the CLVT op code isn't supported.

The simple act of spending the payment requires to disclose the information the other party needs to do their spend.

Ignoring fees, at the high level:
1. bob sends in a deposit that alice verifies she can spend after a certain amount of time. However if bob follows the protocol, he can reclaim this refund before alice is eligible to.

You've apparently swapped the block chains of Alice and Bob relative to scenario I described. But that is okay, I will follow your choice, where Bob is transacting on the block chain with CLTV and Alice is not.

The transaction above signed by Bob I assume requires CLTV (Check-Lock-Time-Verify) since it must be refunded if it is not verified before the timeout of the lock.

2. alice verifies the above is in the blockchain so is assured that worst case she can get the deposit, which is 113% of the transaction amount, so she might actually prefer that. when assured she sends bob a payment that requires both secrets to be spent.

I don't understand how Alice can receive the CLTV output unless she already knows how to verify it. But if she knows how to verify it, then she can steal it at any time.

How can Alice send a payment that requires verification of two secrets if the other block chain doesn't support pay contingent on verification of hash preimage?

3. bob sees this on the altcoin chain and sends in a payment to alice that requires a secret from alice that would allow him to spend the payment from 2.

Bob issued the deposit in #1 and now he also issues another payment to Alice, but which is spendable by Alice contingent on knowing the preimage (secret) of a hash. Only Alice knows this secret preimage at this point until she reveals it. I thus understand this step #3.

4. alice sees this real payment and then cashes in the bitcoins, but in doing so has to divulge the secret bob needs to spend the altcoins

I am disputing whether Alice can make such a transaction available in step #2 if her altcoin doesn't support pay contingent on verification of hash preimage.

Edit: I understand you want to use a forfeitable deposit to ensure that Bob does step #3, since Alice has no way to refund step #2 (because her block chain doesn't support CLTV). I presume you are assuming that the altcoin supports pay contingent on verification of hash preimage. But I still don't see how the mechanics of the forfeitable deposit work? "I don't understand how Alice can receive the CLTV output unless she already knows how to verify it. But if she knows how to verify it, then she can steal it at any time."

OK, I think we take one issue at a time.

The altcoin payment on the network that doesnt support CLTV is an ordinary multisig that uses the pubkeys from the temp privkeys. This is the key that allows the single pull double throw, the fact that on the BTC blockchain it is just a random number that hashes to the previously specified value.

It is actually the privkey that makes pubkey that is put into a 2of2 multisig.

I know you dont like scripts, but please bear with me:

OP_2 <alice_pubM> <bob_pubN> OP_2 OP_CHECKMULTISIG

The above is an original standard multisig, not even the p2sh form, so basically all altcoins using bitcoin 0.7 (or even 0.5?) support it.

the alice_pubM is the pubkey from the temporary privkey that was selected by bob during the cut and choose.

similarily bob_pubN is the pubkey from the temporary privkey that was selected by alice during the cut and choose.

In order to spend the 2 of 2 multisig, both privkeys are needed. Alice has the privkey for the alice_pubM and bob has the privkey for bob_pubN. So if during the protocol, either party gets the other privkey, then and only then can they spend this.

The protocol (and FSM based on it) follow blockchain verifiable steps to allow each side to progress incrementally to the next state where eventually either both sides can get their corresponding payments, or it unwinds and they get their funds back.

This is impossible at first sight, but this is where the evil genius of TierNolan comes in. The scripts for the deposit and payment that are timelocked to prevent the wrong side from being able to spend it, even if they have the required keys. So it does require both sides to actively protect their interests and do the spends that they are able to. If they dont, after the timer expires, the other side would.

But this is all automated in the protocol.

So if at the high level you can agree that it is theoretically possible that if we can setup the corresponding payment to the 2of2 multisig that enables the opposite party to spend the corresponding payment, we get atomicity. And that is what the atomic protocol purportedly does and thus requires scrutiny of the FSM and scripts to verify.

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

I know you dont like scripts, but hopefull the possibility of non-impossibilty is conveyed. In the above, the first case is only spendable by bob as it does a CHECKSIG against his pubkey, but it cannot be done until after the locktime passes.

the other case allows alice and only alice to spend it as her signature is verified, but it also requires alice to divulge the privM key, which once it is divulged can be used to sign the 2of2 multisig, along with verify that the cut and choose wasnt cheated on.

Granted, this is the point where alice can refuse, but in such case, time passes and bob can spend it just by waiting.

So this protocol barely works as if any script is wrong or cltv isnt existing or multisig doesnt work or ..., but assuming we didnt miss any case, it works, is atomic and blockchain verified, with the cut and choose offering a probabilistic penalty to make cheating at cut and choose uneconomical.

The intricacies of using conditional scripts that allow different parties to spend the same tx and requiring part of it to have a delay, is what is at the same time confusing, but also enables atomicity. Without the time delay, then yes the other party can spend right away. And getting it setup so the altcoin side uses only standard multisig is a thing of beauty.

I dont quite have it fully debugged, but so far I am only finding minor issues in the protocol itself. It has gone from an impractical "both coins must have CLTV" protocol that would allow trading just a few coins, to a protocol that should work with 100+ variety

James

[jl777]

Some details have changed, but the original spec from the other thread were this came from:

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.

2) Bob pays D to

Code:
OP_IF
  <now + 2 days> OP_CLTV OP_DROP <alice_pub_1001> OP_CHECKSIG
OP_ELSE
  OP_HASH160 <hash(bob_priv_n)> OP_EQUALVERIFY <bob_pub_1001> OP_CHECKSIG
OP_ENDIF

D should be more valuable than the value of the Bitcoins or altcoins. 

This is a promise by Bob to release bob_priv_n within 2 days (or lose his deposit).

3) Alice pays a altcoins to

Code:
OP_2 <bob_pub_n> <alice_pub_m> OP_2 OP_CHECKMULTISIG

4) Bob pays b Bitcoins to

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 <alice_pub_key_1001> OP_CHECKSIG
OP_ENDIF

Alice has 1 day to claim her output, but that means she must provide alice_priv_m.

5) Alice spends the output (and provides alice_priv_m).

6) Bob can spend the altcoin output (since he has both keys)

7) Bob reclaims his deposit

This is atomic and it is recoverable if either party refuses to complete a step.

1) Either party refuses to perform cut-and-choose.

Nothing has been sent to either chain, so no harm done.

2) Bob refuses to pay deposit.

Nothing has been sent to either chain, so no harm done.

3) Alice refuses to bail-in.

Bob reclaims his D after 2 days.
Releasing bob_priv_n has no effect since there was no bail-in by Alice, so the key is never used.

4) Bob refuses to bail-in

If Bob reclaims his deposit, then Alice will have both private keys and can reclaim her bail-in.

If Bob fails to claim his deposit, then Alice gets that as compensation instead of her bail-in.  In that case, Bob loses his deposit and can't claim the altcoins.  This means he should reclaim his output.

5) Alice refuses to claim her Bitcoins

1 day later Bob can reclaim his Bitcoins

Alice gets her altcoins back or she gets D instead (if Bob doesn't reclaim his deposit).

6) Bob refuses to claim his altcoins

He loses his altcoins when he reclaims his deposit.  Alice already has his Bitcoins by this point.

He has an incentive to complete this step.

7) Bob refuses to claim his deposit

He loses his deposit and Alice gets it.

He has an incentive to complete this step.

For each step, there is either an incentive to complete the step or failure to complete the step causes the protocol to abort.  In an abort, the incentives are to perform a clean abort.

###
There is plain english description
FSM embodiment of the english description
and the scripts

Not sure what part you feel is not a "straight answer"

Maybe you can zoom in to a specific step (state) with a specific scenario? The problem is that this solution depends on exact behavior of the scripts, so without detailed understanding of them it is only possible to get a general idea. You probably dont want to see the 2000 lines of C code that implements this either.

I am trying to find an FSM visualizer so it can convert my FSM description into pretty circles and boxes with lines connecting them, but graphics apps are not my speciality.

the FSM spec is just to define the name of the state and the name of the state if things timeout using the createstate function. Once a state is created the addevent function adds an event to that state that it looks for and the next state it goes to along with the event message it sends to the other side.

James

[jl777]

This is a promise by Bob to release bob_priv_n within 2 days (or lose his deposit).

The insoluble flaw will always remain (no matter how you structure the deposit) that either Alice can refuse to do the succeeding transaction and thus Bob loses his deposit (and if the deposit is paid to Alice then she steals this amount), or if you allow Bob to refund the deposit, then Bob can refuse to do the next step after Alice issues her transaction and thus Alice will lose her funds.

2) ... OP_HASH160 <hash(bob_priv_n)> OP_EQUALVERIFY <bob_pub_1001> OP_CHECKSIG

[...]

3) ... OP_2 <bob_pub_n> <alice_pub_m> OP_2 OP_CHECKMULTISIG

I now understand the intent of the cut & choose that Alice is 99.9% certain (precise % depends on number of key pairs in the challenge session of step #1) that <bob_pub_n> is signable with bob_priv_n, so that when Bob releases bob_priv_n after step #4 to refund his deposit, then Alice sure she can sign for Bob's transaction in order to spend it.

But that doesn't protect Alice. Bob can release his private key before step #4, thus refunding his deposit to himself and Alice's funds are forever locked because her block chain doesn't support CLTV.

I am glad we are now finding potential weak spots in the actual protocol!

Alice doesnt send the altpayment to the msig address until after she confirms the deposit is confirmed. Bob has to wait for maxtime period before he can claim it.

Bob has the altpayment, but cant spend it at this point. But as you say, he can claim the deposit. But notice that in order to claim his deposit back, he must reveal the privM to spend the script:

  OP_HASH160 <hash(bob_priv_n)> OP_EQUALVERIFY <bob_pub_1001> OP_CHECKSIG

Alice then is waiting to see this on the blockchain and can then reclaim the altpayment. If Bob tries to wait alice out, then she is able to cash in the deposit as the CLTV timeout expires.

This is why I implemented it as a state machine. That was as each step of the protocol is advanced, the choices to each side is limited and as near as we can tell, all paths lead to recovery of all funds or the trade completing.

Of course, it is possible that there is an undetected flaw and we look forward to identification of the state and event that exposes this flaw. However if each state of the FSM has no specific flaw, then as unlikely as it is, the entire protocol must work. The fact it is done as FSM should actually allow a mathematical proof to be created, but such math (graph theory?) is beyond me.

Once the FSM is validated, then as long as the code is properly detecting events then I think we get close to having a very solid and peer reviewed implementation.

Clearly, loss of capital is the biggest potential flaw and it must be certain that no such thing is possible before delving into the secondary attacks about locking up funds for limited periods of time, etc.

James

[jl777]

As I wrote many moons ago in this thread, there is simply no way to do DE unless both block chains support CLTV. I told you the generative essence reason is because there is no reference point:

And so will everyone else get Bob's private key and a miner who wins the block can spend his output before his transaction is confirmed on the block chain.

My point is that once Bob releases this private key, anyone can spend his UXTO to any payee else besides Alice. Thus I am asserting the cut & choose doesn't work, unless someone can explain to me my mistake.

Well I cannot respond to any general statement, so lets find specific flaws that exist as specific points in the protocol. I dont think you are able to prove a negative statement, so we must stick to specific states that can be abused.

The bitcoin utxo are protected by both the signatures that are required from the "real" privkey and the random number (alice_privM or bob_privN) from the protocol.

So maybe there is a flaw with some script as stated, but you seem to not hear that there are TWO DIFFERENT privkeys required to do most of the spends. One of them is the temporary privkey from the 1000 cutandchoose keypairs. The OTHER privkey is one that is NEVER disclosed, only used to sign the tx to spend it.

So the protocol does not allow anybody to spend it, only Bob can spend outputs meant for Bob and only Alice can spend output meant for her.

Your assertion that anybody can spend the funds is missing the fact that only Alice has the privkey needed to sign the tx and only Bob has the privkey needed to sign the tx, and those privkeys are NOT disclosed

James

[TPTB_need_war]

I deleted the prior version of this post a few moments after posting it, because I realized I had an error and I wanted to take a moment to think about it before reposting. I didn't realize jl777 has already replied within those few moments, until I had already deleted it and saw his post when the page reloaded.

This is a promise by Bob to release bob_priv_n within 2 days (or lose his deposit).

The insoluble flaw will always remain (no matter how you structure the deposit) that either Alice can refuse to do the succeeding transaction and thus Bob loses his deposit (and if the deposit is paid to Alice then she steals this amount), or if you allow Bob to refund the deposit, then Bob can refuse to do the next step after Alice issues her transaction and thus Alice will lose her funds. Or as I wrote days ago (see self quotes below), the private keys get revealed and anyone can spend a transaction to themselves.

2) ... OP_HASH160 <hash(bob_priv_n)> OP_EQUALVERIFY <bob_pub_1001> OP_CHECKSIG

[...]

3) ... OP_2 <bob_pub_n> <alice_pub_m> OP_2 OP_CHECKMULTISIG

I now understand the intent of the cut & choose that Alice is 99.9% certain (precise % depends on number of key pairs in the challenge session of step #1) that <bob_pub_n> is signable with bob_priv_n, so that when Bob releases bob_priv_n before step #4 to refund his deposit, then Alice is sure she can sign for Bob's transaction in order to spend it back to herself. At that point Bob doesn't have Alice's private key, and Alice never releases this private key, thus only she can sign back her transaction to herself.

Whereas if Bob issues the reciprocal payment to Alice in step #4, Alice releases her private key (so she can claim Bob's payment from step #4) then Bob can sign using his private key (which remains private until he issues the refund for his deposit) to spend Alice's payment from step #3.

But the problem remains that when private keys are revealed, then anyone can spend the payment from Alice. One might argue that Bob will wait to refund the deposit until after the payment from Alice to Bob has been confirmed spent by Bob, but an attacker with sufficient hashrate can revert the order of the transactions and steal Bob's payment. Remember you are proposing to have many of these DE transactions occurring simultaneously and you are thus incentivizing someone to attack the block chain with hashrate to steal value. Normally even a 51% attacker can't steal someone else's coins (only double-spend their own coins), yet you are proposing to open a new attack vector funding 51% attacks with other people's coins! That is a non-starter, because it weakens the entire coin's security (because adds a new source of funding for 51% attacks). Perhaps you have just identified a reason that multi-sig transactions should always have their destination address hard-coded. I think you've identified a security hole in the current OP code for multi-sig.

Even if it were possible to structure a Bitcoin transaction such that Bob signs for his refund instead of releasing the private key, that wouldn't help you, because then Alice couldn't refund herself when Bob fails to do step #4.

As I wrote many moons ago in this thread, there is simply no way to do DE unless both block chains support CLTV. I told you the generative essence reason is because there is no reference point:

And so will everyone else get Bob's private key and a miner who wins the block can spend his output before his transaction is confirmed on the block chain.

My point is that once Bob releases this private key, anyone can spend his UXTO to any payee else besides Alice. Thus I am asserting the cut & choose doesn't work, unless someone can explain to me my mistake.

[jl777]

I deleted the prior version of this post a few moments after posting it, because I realized I had an error and I wanted to take a moment to think about it before reposting. I didn't realize jl777 has already replied within those few moments, until I had already deleted it and saw his post when the page reloaded.

This is a promise by Bob to release bob_priv_n within 2 days (or lose his deposit).

The insoluble flaw will always remain (no matter how you structure the deposit) that either Alice can refuse to do the succeeding transaction and thus Bob loses his deposit (and if the deposit is paid to Alice then she steals this amount), or if you allow Bob to refund the deposit, then Bob can refuse to do the next step after Alice issues her transaction and thus Alice will lose her funds. Or as I wrote days ago (see self quotes below), the private keys get revealed and anyone can spend a transaction to themselves.

2) ... OP_HASH160 <hash(bob_priv_n)> OP_EQUALVERIFY <bob_pub_1001> OP_CHECKSIG

[...]

3) ... OP_2 <bob_pub_n> <alice_pub_m> OP_2 OP_CHECKMULTISIG

I now understand the intent of the cut & choose that Alice is 99.9% certain (precise % depends on number of key pairs in the challenge session of step #1) that <bob_pub_n> is signable with bob_priv_n, so that when Bob releases bob_priv_n before step #4 to refund his deposit, then Alice is sure she can sign for Bob's transaction in order to spend it back to herself. At that point Bob doesn't have Alice's private key, and Alice never releases this private key, thus only she can sign back her transaction to herself.

Whereas if Bob issues the reciprocal payment to Alice in step #4, Alice releases her private key (so she can claim Bob's payment from step #4) then Bob can sign using his private key (which remains private until he issues the refund for his deposit) to spend Alice's payment from step #3.

But the problem remains that when private keys are revealed, then anyone can spend the payment from Alice. One might argue that Bob will wait to refund the deposit until after the payment from Alice to Bob has been confirmed spent by Bob, but an attacker with sufficient hashrate can revert the order of the transactions and steal Bob's payment. Remember you are proposing to have many of these DE transactions occurring simultaneously and you are thus incentivizing someone to attack the block chain with hashrate to steal value. Normally even a 51% attacker can't steal someone else's coins (only double-spend their own coins), yet you are proposing to open a new attack vector funding 51% attacks with other people's coins! That is a non-starter, because it weakens the entire coin's security (because adds a new source of funding for 51% attacks). Perhaps you have just identified a reason that multi-sig transactions should always have their destination address hard-coded. I think you've identified a security hole in the current OP code for multi-sig.

Even if it were possible to structure a Bitcoin transaction such that Bob signs for his refund instead of releasing the private key, that wouldn't help you, because then Alice couldn't refund herself when Bob fails to do step #4.

As I wrote many moons ago in this thread, there is simply no way to do DE unless both block chains support CLTV. I told you the generative essence reason is because there is no reference point:

And so will everyone else get Bob's private key and a miner who wins the block can spend his output before his transaction is confirmed on the block chain.

My point is that once Bob releases this private key, anyone can spend his UXTO to any payee else besides Alice. Thus I am asserting the cut & choose doesn't work, unless someone can explain to me my mistake.

I am not sure what specific attack you are saying exists, as I have explained about the two required signatures.

The only new attack vector I see that I have not already addressed (plz correct me if I missed any  specific attack) is the hashrate used to reverse transactions.

This is solved by waiting for enough confirms appropriate to the value of the tx.

Enough time is there in the protocol for an hour or two, so if needed, then 10 or even 30 confirms can be waited for before committing to the next step. If you are saying that now there are attackers that can undo 10 or 30 blocks, then I would need to see the type of hashrate is required for that and adjust the recommended number of confirms.

PLEASE stick to specific attacks. General statements are fine, but I cannot make any specific response. You say you are convinced it cant work in general, I say I think it can. OK, so no need to be opinion based, when there is a FSM with specific scripts

let us use the following as a reference to make sure we are speaking of the same states:

###
This is atomic and it is recoverable if either party refuses to complete a step.

1) Either party refuses to perform cut-and-choose.

Nothing has been sent to either chain, so no harm done.

2) Bob refuses to pay deposit.

Nothing has been sent to either chain, so no harm done.

3) Alice refuses to bail-in.

Bob reclaims his D after 2 days.
Releasing bob_priv_n has no effect since there was no bail-in by Alice, so the key is never used.

4) Bob refuses to bail-in

If Bob reclaims his deposit, then Alice will have both private keys and can reclaim her bail-in.

If Bob fails to claim his deposit, then Alice gets that as compensation instead of her bail-in.  In that case, Bob loses his deposit and can't claim the altcoins.  This means he should reclaim his output.

5) Alice refuses to claim her Bitcoins

1 day later Bob can reclaim his Bitcoins

Alice gets her altcoins back or she gets D instead (if Bob doesn't reclaim his deposit).

6) Bob refuses to claim his altcoins

He loses his altcoins when he reclaims his deposit.  Alice already has his Bitcoins by this point.

He has an incentive to complete this step.

7) Bob refuses to claim his deposit

He loses his deposit and Alice gets it.

He has an incentive to complete this step.

For each step, there is either an incentive to complete the step or failure to complete the step causes the protocol to abort.  In an abort, the incentives are to perform a clean abort.
###

Where in the above can either party get funds from the other that they shouldnt be able to?

James

[TPTB_need_war]

I don't want to repeat myself. You will destroy the security of the coin by enabling the hashrate attacker to steal other people's coins. This was not possible before (rather before an attacker could only attempt to double-spend his own coins), thus such an attack was not well funded. You are proposing to fund 51% attacks. I hope you understand that hashrate is rentable and the implications of that. Especially when you are proposing to exchange between altcoins which have very low hashrate security (note Alice's multi-sig occurs on the altcoin not on Bitcoin).

Sorry the cut & choose proposal must be scrapped.

Stick with the CLTV on both block chains where the destination addresses are hard-coded and thus can't be stolen by a hashrate attacker. That is technically sound.

[jl777]

I don't want to repeat myself. You will destroy the security of the coin by enabling the hashrate attacker to steal other people's coins. This was not possible before (rather before an attacker could only attempt to double-spend his own coins), thus such an attack was not well funded. You are proposing to fund 51% attacks. I hope you understand that hashrate is rentable and the implications of that.

Sorry your proposal must be scrapped.

Stick with the CLTV on both block chains. That is sound.

I understand hashrate is rentable.

Please explain how a 1BTC value for atomic swap is financing a 51% attack. How many coins can be attacked with 1BTC of hashrate? and realistically how many blocks can be reorged

we are not talking about doing 100BTC swaps as the norm. Most will be 1BTC worth or less

James

[TPTB_need_war]

I don't want to repeat myself. You will destroy the security of the coin by enabling the hashrate attacker to steal other people's coins. This was not possible before (rather before an attacker could only attempt to double-spend his own coins), thus such an attack was not well funded. You are proposing to fund 51% attacks. I hope you understand that hashrate is rentable and the implications of that.

Sorry your proposal must be scrapped.

Stick with the CLTV on both block chains. That is sound.

I understand hashrate is rentable.

Please explain how a 1BTC value for atomic swap is financing a 51% attack. How many coins can be attacked with 1BTC of hashrate? and realistically how many blocks can be reorged

we are not talking about doing 100BTC swaps as the norm. Most will be 1BTC worth or less

James

Why do you assume only one DE transaction will be ongoing on a block chain simultaneously. And why do you assume that DE transactions will be limited to 1 BTC.

[jl777]

I don't want to repeat myself. You will destroy the security of the coin by enabling the hashrate attacker to steal other people's coins. This was not possible before (rather before an attacker could only attempt to double-spend his own coins), thus such an attack was not well funded. You are proposing to fund 51% attacks. I hope you understand that hashrate is rentable and the implications of that.

Sorry your proposal must be scrapped.

Stick with the CLTV on both block chains. That is sound.

I understand hashrate is rentable.

Please explain how a 1BTC value for atomic swap is financing a 51% attack. How many coins can be attacked with 1BTC of hashrate? and realistically how many blocks can be reorged

we are not talking about doing 100BTC swaps as the norm. Most will be 1BTC worth or less

James

Why do you assume only one DE transaction will be ongoing on a block chain simultaneously. And why do you assume that DE transactions will be limited to 1 BTC.

Just trying to calibrate things. If need be there can be a global tracking of pending trades relative to hashrates. And until there are much larger number of active trades, at any given time odds are that there wont be that many trades involving a specific coin. Even on high volume exchanges like btc38, often hours can go by without any trade for a specific coin.

Also, how can a PoS coin be attacked using this? Does this mean that PoS coins are more secure as atomic altcoins than PoW?

I dont want to start a holy war re PoS vs PoW, just trying to quantify risks. If indeed an attacker can spawn 100BTC worth of swaps, use funds to buy hashrate to reverse tx, then indeed this needs to be addressed. Tracking pending trades or limiting to PoS coins comes to mind, but I am tired and that is just the initial reaction, there should be more potential solutions

James