How to commit - release a transaction without trusting a third party

[ffe]

Let’s say you want to send coins to someone but do not want him to have the coins if he does not deliver a product. On the other hand, he does not want to mail you the product before getting the coins.

The answer is to use Sender Generated Conditional Keys.

If the sender can generate a public key for the receiver such that:

     1.   Only the receiver can generate the private part for it but only if he gets a separate piece of information from the sender.

     2.   The sender cannot generate the private part – hence once the transaction is out there the sender cannot recover the coins – only pass them on to the receiver.

Then we have a situation where there are coins sitting there that are committed and can only go to the receiver but the receiver cannot pick them up until he somehow satisfies the sender.

Two step transactions can be implemented by trusting a third party with your coins but sometimes you don’t want to trust a third party.

-----------------------------------------------------------
This is how Sender Generated Conditional Keys work:

Let Alice publish a certificate with a public key. (This cert has a key that is NOT a transaction key. It cannot be used in a normal fashion by other clients to send to.) Let "a" be the cert private key.  The cert public key is "A" (A=aQ where Q is the basis point in the cryptographic curve).  A is available in the Cert created by Alice.

Also, let Bob have a wallet and it has coins under a public key "Y" so the bitcoin block chain has a transaction transferring coins to Y and Bob has the private key, "y", which corresponds to Y but no one knows that Bob owns Y.

Bob wants to conditionally send some coins to Alice. He looks up the certificate for Alice and extracts A. Bob’s client generates a public key "X" from A, y, and "m" (m is randomness derived from parts of the transaction that transfers the coins).  X has the property that Alice can derive the private key "x" only if Bob gives Alice an extra piece of information. Alice can spend the coins in X by convincing Bob to give her the extra information then generating x and using it to sign a transaction spending the coins at some future time.

Bob generates X by first generating a secret, s, as follows:

     s=Hash(m,y,A)    

     X = sA

(Note sA is a cryptographic multiply in ECC). Only Bob can generate s.  Also, Bob cannot generate the private part of X but he can transfer coins to X. Bob convinces Alice he has committed the coins by generating a public key from s:

     S = sQ

And sending it to Alice. Alice cannot generate s. But using the public S she knows the coins are committed since:

     X = aS       (where a is her private key)

Once she satisfies Bob he gives her s and she generates x, the private part of X, as follows:

     x = sa (modulo a large prime determined by the ECC)

She can check that X = xQ and is satisfied.

“m” is chosen so that no two transactions produce the same s. Hence X will always be unique to that transaction. m would be a few bytes from the transaction that are unique to the transaction but are not dependent on X, the receiving key in the transaction. (This is important so we don’t have a circular definition for X).

[ThePiachu]

I'd say that a solution to this problem would be connected to this topic:
https://bitcointalk.org/index.php?topic=84569.0

Basically, both the sender and the receiver generate one keypair each. They exchange the public keys, add them together and use that sum to generate a Bitcoin address. The buyer sends coins to the address, the sender sees it and releases the goods. When the buyer gets the goods, he gives the sender their private key. The sender adds the private keys and obtains the private key needed to redeem the coins.

If the buyer cancels their purchase fairly, the sender sends their private key to let them get their coins back.

If the buyer and sender don't agree, neither of them get the coins.

There are only two ways to abuse this - if the sender is malicious, it makes the buyer send coins to an address they can't get their money out of (tricking them to loose money). If the buyer is malicious, they don't give their private key, meaning that the seller doesn't get paid, but the buyer doesn't get them back either.

[ffe]

There are only two ways to abuse this - if the sender is malicious, it makes the buyer send coins to an address they can't get their money out of (tricking them to loose money). If the buyer is malicious, they don't give their private key, meaning that the seller doesn't get paid, but the buyer doesn't get them back either.

Here the receiver can verify that the sender has committed by checking

     X = aS

At this point she knows only she could possibly generate the private part of x.

[etotheipi]

FYI, this topic has been discussed in a few different contexts, such as in this thread.  Obviously, multi-signature transactions are built into the network, so this kind of ECDSA magic is unnecessary, at least for simple 2-of-2 transactions.  Also, the 2-of-2 using ECDSA as you described requires one party to compromise their own private key to allow the other party to claim the entire encumbered amount.  There's no way to, say, split the money that is locked in the 2-of-2 transaction without one party trusting another.  Also, I don't like the idea of having wallets where some private keys are supposed to be revealed, while it's an epic fail for other keys to be revealed.  It works for Casascius physical Bitcoins, but I have personally decided it's not a good idea for general usage.

On top of that, I believe that being able to split the encumbered money is important:  I am firm believer that both parties need a "risk deposit."  That the initial 2-of-2 fund is seeded with, say, 20% of the transaction value from both parties (can do more or less depending on how much the parties don't trust each other).  At the end of the transaction, if everything went as planned, both parties get their risk deposit back -- Alice puts in 1.2X and Bob puts in 0.2X;  at the end of the exchange, they both sign a tx sending 0.2X to Alice, 1.2X to Bob.  But if it doesn't go smoothly, then both parties lose their deposit and the tx money.  Therefore, there is every incentive for both parties to resolve the transaction agreeably.  

This avoids:  
(1) Lazy Alice:  Alice receives the goods but then is too lazy to sign the transaction completing the transfer to Bob (or in your case, sending the private key to Bob).  She might do this maliciously if she is disatisfied with the product, and if she has no risk deposit, it costs her nothing to screw over Bob.

(2) Prankster Bob:  Bob advertises that he has products to sell with no intention of selling anything.  Alice puts 100 BTC into a 2-of-2 tx, and then Bob disappears leaving the money stranded.  Or Bob comes back and offers to split the money with her, since she'll get nothing back if she doesn't agree.  Etc.  With a risk deposit, Bob has to put his own money into the tx to demonstrate that he is serious about the transaction.  And using special hash codes, it's possible for both Alice and Bob to inject the money "simultaneously" so that neither party risks putting money in before the other.

(3) The risk deposit could serve as a pre-paid fee for third-party arbitration, if a third-party was included on the transaction.  A common agreement might be that third-party Charles, might arbitrate any transaction that has at least 10% risk deposit from both parties.  Charles takes that 20% as its fee only if arbitration is needed.

Gavin doesn't like the idea of coins being lost, and thinks there should be a MAD option (mutually assured destruction), to allow the coins to be recycled if things go awry.  I'm still not entirely convinced that's necessary, but it's not a bad idea.  I guess we never actually resolved "the best way" to do this...

[ffe]

FYI, this topic has been discussed in a few different contexts, such as in this thread.  Obviously, multi-signature transactions are built into the network, so this kind of ECDSA magic is unnecessary, at least for simple 2-of-2 transactions.  Also, the 2-of-2 using ECDSA as you described requires one party to compromise their own private key to allow the other party to claim the entire encumbered amount.  There's no way to, say, split the money that is locked in the 2-of-2 transaction without one party trusting another.  Also, I don't like the idea of having wallets where some private keys are supposed to be revealed, while it's an epic fail for other keys to be revealed.  It works for Casascius physical Bitcoins, but I have personally decided it's not a good idea for general usage.

On top of that, I believe that being able to split the encumbered money is important:  I am firm believer that both parties need a "risk deposit."  That the initial 2-of-2 fund is seeded with, say, 20% of the transaction value from both parties (can do more or less depending on how much the parties don't trust each other).  At the end of the transaction, if everything went as planned, both parties get their risk deposit back -- Alice puts in 1.2X and Bob puts in 0.2X;  at the end of the exchange, they both sign a tx sending 0.2X to Alice, 1.2X to Bob.  But if it doesn't go smoothly, then both parties lose their deposit and the tx money.  Therefore, there is every incentive for both parties to resolve the transaction agreeably.  

This avoids:  
(1) Lazy Alice:  Alice receives the goods but then is too lazy to sign the transaction completing the transfer to Bob (or in your case, sending the private key to Bob).  She might do this maliciously if she is disatisfied with the product, and if she has no risk deposit, it costs her nothing to screw over Bob.

(2) Prankster Bob:  Bob advertises that he has products to sell with no intention of selling anything.  Alice puts 100 BTC into a 2-of-2 tx, and then Bob disappears leaving the money stranded.  Or Bob comes back and offers to split the money with her, since she'll get nothing back if she doesn't agree.  Etc.  With a risk deposit, Bob has to put his own money into the tx to demonstrate that he is serious about the transaction.  And using special hash codes, it's possible for both Alice and Bob to inject the money "simultaneously" so that neither party risks putting money in before the other.

(3) The risk deposit could serve as a pre-paid fee for third-party arbitration, if a third-party was included on the transaction.  A common agreement might be that third-party Charles, might arbitrate any transaction that has at least 10% risk deposit from both parties.  Charles takes that 20% as its fee only if arbitration is needed.

Gavin doesn't like the idea of coins being lost, and thinks there should be a MAD option (mutually assured destruction), to allow the coins to be recycled if things go awry.  I'm still not entirely convinced that's necessary, but it's not a bad idea.  I guess we never actually resolved "the best way" to do this...

You're right. There are much better ways of doing this if you can mess with the standard client. It was a quick idea to show what you can do with a DH type shared secret between the sender and receiver.


Just a minor note. The sender is not revealing his private key. He's revealing a one time secret unique to that transaction.
Another note. This transaction is utterly anonymous as far as third parties are concerned, yet it allows the sender to prove to the receiver that he has committed his coins.

Nevertheless it is severely flawed due to the possible loss of coins. I agree with Gavin on this.

[etotheipi]

Oh, I apologize.  I started reading the thread and it looked like the same proposals I've seen before where both parties just compute the DHSS value with private*public and use that as the public key -- requiring one person to have both private keys to be able to spend it.  One party reveals their private key to allow the other party to redeem it.

Your technique is definitely an improvement.  And you're right about the anonymity: standard multi-sig transactions (BIP 16) reveal both original addresses when the coins are redeemed.