How to structure mutually conditional transactions?

[Cryddit]

Is it possible using pay-to-script-hash, to come up with an appropriate script for mutually conditional transactions?

What I mean is, you have the following scenario: 

Alice and Bob want to make transaction A, but if and only if Carol and Dave make transaction B.
Carol and Dave want to make transaction B, but if and only if Alice and Bob make transaction A.

All four parties want both transactions to go through, or neither.  But none of them wants to structure it as a single four-way transaction, because Alice and Bob are not allowed to know before both tx are broadcast which txouts Carol and Dave are about to use, and vice versa. 

Nobody cares, though, if the other pair do instead a similar transaction (same amount transferred) involving *different* txouts. As long as it isn't exactly transaction A or transaction B, they don't want their own transaction to go through.

They can cooperate to the extent of giving each other identifying information for their transactions; they can give each other partial hashes of their tx (ie, their hash matches their tx if you zero the part of their script that contains your hash) before broadcasting the tx.

[mandelbert]

Bitcoin transaction can have multiple inputs as well as multiple outputs. In your case, you can build one transaction with two inputs (A and C) and two outputs (B and D).

[Cryddit]

Nope.  Protocol doesn't work unless they are separate transactions. I mean, yes, the Bitcoin protocol works fine with a single transaction among four people.  But the particular trick I'm trying to do wouldn't.

[kokjo]

there is no situation where this would be useful...
It cannot be done within bitcoin, as txscripts are not dependent on the blockchain, or any other external state for that matter. txscripts only decides whatever a transaction is approved by the owner(s).

[Qoheleth]

I keep thinking I've got a solution, and then keep realizing that it doesn't actually do what you asked for.

This is a bit of a weird use case, though. Could you explain what you're trying to do at a higher level, such that these restrictions are necessary?

there is no situation where this would be useful...
It cannot be done within bitcoin, as txscripts are not dependent on the blockchain, or any other external state for that matter. txscripts only decides whatever a transaction is approved by the owner(s).

Yes, but you can use txscripts to make transactions dependent on each other using cryptographic techniques (e.g. CoinSwap, where hashes of secrets are used to make one transaction contingent on another).

The problem here is that I'm not familiar with any cryptographic techniques for simultaneously revealing information.

[alp]

Is it possible using pay-to-script-hash, to come up with an appropriate script for mutually conditional transactions?

What I mean is, you have the following scenario: 

Alice and Bob want to make transaction A, but if and only if Carol and Dave make transaction B.
Carol and Dave want to make transaction B, but if and only if Alice and Bob make transaction A.

All four parties want both transactions to go through, or neither.  But none of them wants to structure it as a single four-way transaction, because Alice and Bob are not allowed to know before both tx are broadcast which txouts Carol and Dave are about to use, and vice versa. 

Nobody cares, though, if the other pair do instead a similar transaction (same amount transferred) involving *different* txouts. As long as it isn't exactly transaction A or transaction B, they don't want their own transaction to go through.

They can cooperate to the extent of giving each other identifying information for their transactions; they can give each other partial hashes of their tx (ie, their hash matches their tx if you zero the part of their script that contains your hash) before broadcasting the tx.

A & B send to a 4-signature address and get a refund transaction from C&D that is timelocked in the future.
C & D send to a 4-signature address and get a refund transaction from A&B that is timelocked in the future.

Once all funds arrive, make a transaction that spends both going into 4-sig, invalidating the refunds.

If time expires, each pair can decide to execute a refund.

[kokjo]

Is it possible using pay-to-script-hash, to come up with an appropriate script for mutually conditional transactions?

What I mean is, you have the following scenario: 

Alice and Bob want to make transaction A, but if and only if Carol and Dave make transaction B.
Carol and Dave want to make transaction B, but if and only if Alice and Bob make transaction A.

All four parties want both transactions to go through, or neither.  But none of them wants to structure it as a single four-way transaction, because Alice and Bob are not allowed to know before both tx are broadcast which txouts Carol and Dave are about to use, and vice versa. 

Nobody cares, though, if the other pair do instead a similar transaction (same amount transferred) involving *different* txouts. As long as it isn't exactly transaction A or transaction B, they don't want their own transaction to go through.

They can cooperate to the extent of giving each other identifying information for their transactions; they can give each other partial hashes of their tx (ie, their hash matches their tx if you zero the part of their script that contains your hash) before broadcasting the tx.

A & B send to a 4-signature address and get a refund transaction from C&D that is timelocked in the future.
C & D send to a 4-signature address and get a refund transaction from A&B that is timelocked in the future.

Once all funds arrive, make a transaction that spends both going into 4-sig, invalidating the refunds.

If time expires, each pair can decide to execute a refund.

But none of them wants to structure it as a single four-way transaction,

[Qoheleth]

A & B send to a 4-signature address and get a refund transaction from C&D that is timelocked in the future.
C & D send to a 4-signature address and get a refund transaction from A&B that is timelocked in the future.

Once all funds arrive, make a transaction that spends both going into 4-sig, invalidating the refunds.

If time expires, each pair can decide to execute a refund.

Here's the problem with this: in order for A&C's spent UTXOs to remain secret, the A->{ABCD} and C->{ABCD} transactions have to be secret as well, with A and C sharing only their TXID hash. Once you've set up all of this, A and C have to publish those transactions, and whoever publishes first reveals their UTXOs without guaranteeing that the other team will publish their own transaction and let the deal go through.

If you could solve the issue of simultaneously revealing A and C's spent UTXOs, there wouldn't be a need for anything more exotic than SIGHASH_ANYONECANPAY, because you could just make a single transaction with B and D's outputs, A and C could individually write their inputs and prove (using SNARKs or some other zero-knowledge mechanism) that an encrypted form decrypts to some valid input of the proper amount, and then the two teams simultaneously reveal their decryption keys, so the moment either team knows the other team's input, both teams have the full transaction and can submit it at will.

But how do you simultaneously reveal? That's the trick.

[kokjo]

But how do you simultaneously reveal? That's the trick.

Trusted third party...

[Cryddit]

Yah.  But I really don't like trusted third parties.  I'm trying to cut the current tribe of trusted third parties out of the deal in fact.

What I'm trying to do is set up the equivalent of a four-party transaction on two different blockchains -- where information can flow back and forth, but you cannot have a four-way transaction because two of the actors (or actually two of the wallets) are on one blockchain and two of the actors (or actually two of the wallets) are on the other. 

As an example of an application, consider the disarmingly simple proposal:

 "I'll send you 50 litecoin if you send me half a bitcoin." 

Each participant has a Bitcoin wallet and a Litecoin wallet, so they can do the individual movements.  The issue is whether they have to trust each other or not. Even with a modified protocol so a client can *see* both chains, or even with a modified blockchain so that key information from the other blockchain can be stored in the local blockchain and used by scripts, I don't see a good way to do it. 

If we come up with a solution for this problem, then we don't need coin exchanges to trade coins back and forth.   

I doubt this would ever happen with Bitcoin because I'm betting it would take a protocol modification and take a lot of security analysis to figure out how much risk an extra capability adds.  But if we can develop a modified protocol for altcoins that makes new coins freely and securely exchangable without a need for trusted third parties, that would rock.  Bitcoin could adopt it after the rough-n-ready risk testing is done on alts.

One possibility I've come up with is an "on-recieve script."  That is, a txout created with a stored script that runs immediately and automatically when a coin is sent to a prearranged txout.  You can put money in a txout with such a script, show the other participant a script that matches the hash so he knows what it is, and then either one of you could trigger it by sending a coin to the address.

So if we have an on-receive script that

* checks the block height or time to make sure an agreed-on interval has gone by and aborts if not,
* checks some 'oracle' information about the other blockchain to see if a transaction there has happened,
* and sends the coins stored in the scripted txout immediately to Bob if it has or Alice if it hasn't,

Then we have a situation where someone could present cryptographic proof that a given transaction has taken place in the other blockchain, store it in the 'oracle' location, immediate blockchain, and then either of them could trigger the script to run (either paying the seller or returning the buyers money) by sending a penny to the address specified in the scripted txout. 

There is one main problem with that idea.  "On-receive" scripts open a whole big can of worms that needs very careful security analysis. 

[kokjo]

There is one main problem with that idea.  "On-receive" scripts open a whole big can of worms that needs very careful security analysis. 

Correct. That is why transaction scripts does not depend on a external state. Also new script opcodes are not introduced lightly, they are essentially hard forks.

[Qoheleth]

Trading across chains (e.g. Litecoin for Bitcoin) has actually already been solved. Take a look at CoinSwap; the algorithm works even if A->B and C->D are on different chains!

At this point it's just a matter of someone actually implementing the protocol.

[kokjo]

Trading across chains (e.g. Litecoin for Bitcoin) has actually already been solved. Take a look at CoinSwap; the algorithm works even if A->B and C->D are on different chains!

At this point it's just a matter of someone actually implementing the protocol.

That requires a trusted thrid party.

[Qoheleth]

That requires a trusted thrid party.

It requires a trusted third party if you want the relationship between the two transactions to be secret. If all you're concerned about is "A gets B's litecoins, B gets A's bitcoins", then the only failure mode, even with a dishonest C, is that the trade doesn't go through, you've wasted a little time but not lost any money, and you find a new C.

Heck, you don't even need a separate person to be C; A or B can fill that role without any loss of atomicity (although, again, it means that A and B know who each other are).