Escrow without third parties

[Sergio_Demian_Lerner]

One of the uses of DAA (Destination Address Anonymization) is to create an p2p escrow without the need for third parties.

Suppose A wants to send X coins to B, and B in return must send Y virtual goods of some kind. B public address is Bpub

First A commits to sending X coins by choosing a random k and sending the money to the address Q=k*Bpub.
Then A creates a simple ZNP (zero knowledge proof) that Q is indeed the encryption of Bpub under a known k.
This can be done with the cut-and-choose method and the Fiat-Shamir heuristic to create a non-interactive proof.
(if you want more information of this method please ask me, it's very simple and a standard practice)

Then B knows that A has committed to the payment (A cannot get the money back and B cannot take it, so the money is blocked).
B sends the virtual goods to A. A releases the money by sending the value k to B.

I know this is not the only way to do an escrow in Bitcoin (and maybe not the best way), but is a new useful way.

Best regards, Sergio.

[commonancestor]

One of the uses of DAA (Destination Address Anonymization) is to create an p2p escrow without the need for third parties.

Suppose A wants to send X coins to B, and B in return must send Y virtual goods of some kind. B public address is Bpub

First A commits to sending X coins by choosing a random k and sending the money to the address Q=k*Bpub.
Then A creates a simple ZNP (zero knowledge proof) that Q is indeed the encryption of Bpub under a known k.
This can be done with the cut-and-choose method and the Fiat-Shamir heuristic to create a non-interactive proof.
(if you want more information of this method please ask me, it's very simple and a standard practice)

Then B knows that A has committed to the payment (A cannot get the money back and B cannot take it, so the money is blocked).
B sends the virtual goods to A. A releases the money by sending the value k to B.

If Q = k * Bpub, what is the relationship between Qpriv and Bpriv then? Or how is B going to learn Qpriv?

[etotheipi]

Just for reference (I can't tell how much of this you know already)

(1) Multi-signature transactions do exactly the same thing. 
--Buyer (A) commits X funds to a 2-of-2 multi-signature transaction including himself and the seller (B)
--B sends the goods. 
--If product is good - A signs transaction moving 2-of-2 funds to B, send to B which signs and broadcasts
--If produce is bad/returned -  B signs transaction moving 2-of-2 fund sto A, sends to A which signs and broadcasts
--If can't agree, funds are locked indefinitely

(2) There's a lot of issues with this setup, such as A being too lazy to sign the goods are received, or B scamming A into putting funds into a 2-of-2 transaction and then disappearing, or holding the funds ransom (A won't get any money back unless they sign a transaction to give B half of it).  There's been lots of discussions about it.  Of course, I will link to my own thread about it.

I apologize if your intent was simply to share the mathematical tricks you can do to achieve the same thing without multi-sig enabled on the network.  I find it very interesting, myself.  But M-of-N transactions are currently enabled on the network using BIP 16, which provides the same functionality (and actually more, because the math gets a lot more complicated and fuzzier if you try to include more parties).

[Mike Hearn]

I think in practice most escrow situations will want to involve a dispute mediator, once the infrastructure for that exists.

[Sergio_Demian_Lerner]

If Q = k * Bpub, what is the relationship between Qpriv and Bpriv then? Or how is B going to learn Qpriv?

QPriv = k*Bpriv

B learns Qpriv when A sends k to B.

[Sergio_Demian_Lerner]

Just for reference (I can't tell how much of this you know already)

(1) Multi-signature transactions do exactly the same thing. 
--Buyer (A) commits X funds to a 2-of-2 multi-signature transaction including himself and the seller (B)
--B sends the goods. 
--If product is good - A signs transaction moving 2-of-2 funds to B, send to B which signs and broadcasts
--If produce is bad/returned -  B signs transaction moving 2-of-2 fund sto A, sends to A which signs and broadcasts
--If can't agree, funds are locked indefinitely

Interesting, exactly the same functionality can be done with DAA:

--Buyer (A) commits X funds to a k*Bpub and publish the transaction, and sends the ZNP to B.
--B sends the goods. 
--If product is good - A sends k to B
--If produce is bad/returned -  B chooses a random z, sends X coins to z*Apub and the sends the ZNP to A. A sends k to B. B sends z to A.
--If can't agree, funds are locked indefinitely

No need for 2-of-2 multi-signature.
Maybe the two tools could be used together to do more advanced contracts!

[cbeast]

If a vendor is trusted and rated, then perhaps a down payment can be made with the rest locked in a 2-of-3 transaction. Three keys are created, one by the seller, one by the buyer, and one by an automated third party service. If the two parties are satisfied with their own resolution, then the private keys can go to whomever it belongs, if they cannot, then the third party is activated. I do not think a pure 2 party escrow can be created without the risk of tying up funds indefinitely. There is no sense in that.

[etotheipi]

If a vendor is trusted and rated, then perhaps a down payment can be made with the rest locked in a 2-of-3 transaction. Three keys are created, one by the seller, one by the buyer, and one by an automated third party service. If the two parties are satisfied with their own resolution, then the private keys can go to whomever it belongs, if they cannot, then the third party is activated. I do not think a pure 2 party escrow can be created without the risk of tying up funds indefinitely. There is no sense in that.

There is sense in that for small transactions where the cost of third-party arbitration might be more than the transaction itself.  Or if the transaction is especially sensitive and the parties do not wish to compromise their privacy.   Yes, the risk of permanent coin loss is not preferable, but I don't think it means that such contracts should never be used.  

There is a lot of value in the ability of the Bitcoin network to serve as an escrow service.  And the risk of the coins being totally lost is a huge incentive for the parties to complete the transaction agreeably (especially when you include risk deposits as I recommended, if it was feasible).  Sure, one party could die or have a HDD failure, but such events would be rare compared to the volume of other transactions that would benefit tremendously from it.  I can't think of anything that is more in the spirit of Bitcoin, than having the network itself serve as a replacement for third-party escrow services.

Interesting, exactly the same functionality can be done with DAA:

...

No need for 2-of-2 multi-signature.
Maybe the two tools could be used together to do more advanced contracts!

The point of multi-signature transactions in the Bitcoin network was so that you don't need any fancy math to achieve M-of-N transaction types.  I totally appreciate that such mathematical solutions exist, but it scope is extremely limited without getting insane (Mike Hearn has previously referenced papers on ECDSA thresholding schemes).

One of the biggest limitations of these mathematical solutions is that at the end, someone ends up with the full private key for the funds.  This means that if an agreement is made to split the money, one party has to trust the other to send them their share.  Alternatively, with BIP16/multi-sig, one party simply creates the transaction they would like to see spent (which can be any distribution of the encumbered funds) and then the other party only needs to sign and broadcast if they agree.

[Sergio_Demian_Lerner]

Emulating 2-3 multisig with DAA is easy too. You don't need to use OP_CHECKMULTISIG

Suppose the parties are A, B and C. Suppose any two of them can decide if the money should go to one of them.

1) A chooses a random Ak, B chooses a random Bk, C chooses a random Ck.
2) A does: 
- ABpub=Ak*BPub and sends a ZNP of that operation to B and C.
- ACpub=Ak*CPub and sends a ZNP of that operation to B and C.

3) B does: 
- BCpub=Bk*CPub and sends a ZNP of that op to A and C.
- BApub=Ak*APub and sends a ZNP of that op to A and C.

4) C does:
  CBpub=Ck*BPub and sends a ZNP of that op to A and B.
  CApub=Ck*APub and sends a ZNP of that op to A and B.

5) A creates the transaction with the script:

scriptPubKey:
   <ABpubKey> OP_CHECKSIG OP_IF OP_1 OP_VERIFY OP_ENDIF
   <ACpubKey> OP_CHECKSIG OP_IF OP_1 OP_VERIFY OP_ENDIF
   <BCpubKey> OP_CHECKSIG OP_IF OP_1 OP_VERIFY OP_ENDIF
   <BApubKey> OP_CHECKSIG OP_IF OP_1 OP_VERIFY OP_ENDIF
   <CApubKey> OP_CHECKSIG OP_IF OP_1 OP_VERIFY OP_ENDIF
   <CBpubKey> OP_CHECKSIG OP_IF OP_1 OP_VERIFY OP_ENDIF


5) Then for any party X and Y
- If X and Y wants to pay the money to Y, X privately send Xk to Y, and Y can get the money.
- If X and Y wants to pay the money to X,Y privately send Yk to X, and X can get the money.

As etotheipi posted while I was typing, math possibilities are endless and any secret sharing scheme can be implemented. Obviously if you think this is high-order math and it's too complicated, then don't use it. Although generally after is implemented, it's completely transparent to the user.
 

[cbeast]

If the third party service is too expensive, perhaps a TOR based automated service can be created that arbitrates with a coin flip.

[Sergio_Demian_Lerner]

One of the biggest limitations of these mathematical solutions is that at the end, someone ends up with the full private key for the funds.  This means that if an agreement is made to split the money, one party has to trust the other to send them their share.

Yes, that's true. Good point etotheipi !

[etotheipi]

As etotheipi posted while I was typing, math possibilities are endless and any secret sharing scheme can be implemented. Obviously if you think this is high-order math and it's too complicated, then don't use it. Although generally after is implemented, it's completely transparent to the user.

I do agree that there are a lot of possibilities, and that much of this could be implemented transparently.  I was even considering doing something like this with Armory before BIP 16, to create 1-of-2 wallet pairs and 2-of-2 wallet pairs.  But it's still limited in flexibility and scalability.  Not to mention, that you've now also created a script with 6 public keys instead of 3, and one party will get control of 100% of the funds at the end (see last paragraph in my previous post).

I sincerely apologize that I distracted your mathematical thread with this.  I think this kind of mathematical discussion is great in the D&TD forum, and it should continue.  I just wanted to make sure that those reading this thread are aware that such functionality was explicitly designed into the network already.

[DeathAndTaxes]

If the third party service is too expensive, perhaps a TOR based automated service can be created that arbitrates with a coin flip.

That would be the worst of both options.  You made it an "auto-win" for scammers and a loser for almost anyone else. 

With a 2 of 2 a scammer has no little economic incentive to enter the agreement.  If the scammer has absolutely no rep (and thus no cost on the tx) it could be economically viable to use a 2 of 2 escrow as hostage to get some free funds.  That can be negated by requiring one or both parties to put a deposit into the escrow.  The scammer now has something at risk (either reputation, or the deposited funds).  If the deposit is more than the expected value of future extortion the "game" is now a net loss for the scammer.

Generally people don't work against their own economic interests.

However with a coin flip on deadlock the scammer will win 50% of the time.  It is unlikely any extortion attempt would be successful 50% of the time so you have improved the odds.

If we consider all the disputed transactions and grouped them into the following categories which do you think makes up the lions share:
* one party is intentionally at fault (scammer)
* both parties generally believe they are in the right (failure to communicate)
* some technical issue (lost wallet, one party dies, funds are stolen before payment, etc)

I would argue that the first case is the overwhelming majority of disputed payments.  The scam and run scenario.  A coin flip hurts the prevention of that scenario.    Go after the biggest problem first.

[commonancestor]

If Q = k * Bpub, what is the relationship between Qpriv and Bpriv then? Or how is B going to learn Qpriv?

QPriv = k*Bpriv

B learns Qpriv when A sends k to B.

If I generate a key pair, and find a ratio between our public keys, then I can use the ratio with my private key to find your private key . Ok maybe the twist is that the ratio must be an integer number but it still sounds bit strange. On the other hand this may imply that if there are not enough possible multipliers of bitcoin addresses, then B could just try some limited range k = (1, 2, ..., 1000?) and find out k himself.
Anyway, thanks for answer and further I am not going to challenge this because I am not a good cryptographer

If a vendor is trusted and rated, then perhaps a down payment can be made with the rest locked in a 2-of-3 transaction. Three keys are created, one by the seller, one by the buyer, and one by an automated third party service. If the two parties are satisfied with their own resolution, then the private keys can go to whomever it belongs, if they cannot, then the third party is activated. I do not think a pure 2 party escrow can be created without the risk of tying up funds indefinitely. There is no sense in that.

I also like the 2-of-3 method because it covers strange situations.

[Sergio_Demian_Lerner]

If I generate a key pair, and find a ratio between our public keys, then I can use the ratio with my private key to find your private key .

Yes, but the ratio is an integer value, modulo a prime p. 
finding such ratio is a very difficult problem.

On the other hand this may imply that if there are not enough possible multipliers of bitcoin addresses, then B could just try some limited range k = (1, 2, ..., 1000?) and find out k himself.

There so many k values that is not possibly to find the right k value by brute force. (in Bitcoin curve, there are 2^256 possible k values)

About Bitcoin's curve is secp256k1:
" taking the name secp256k1 apart, sec comes from the standard, p means that the curve coordinates are a prime field, 256 means the prime is 256 bits long, k means it is a variant on a so-called Koblitz curve, and 1 means it is the first (and only) curve of that type in the standard." (see Hal comment, https://bitcointalk.org/?topic=2699.0)

[cbeast]

If the third party service is too expensive, perhaps a TOR based automated service can be created that arbitrates with a coin flip.

That would be the worst of both options.  You made it an "auto-win" for scammers and a loser for almost anyone else. 

With a 2 of 2 a scammer has no little economic incentive to enter the agreement.  If the scammer has absolutely no rep (and thus no cost on the tx) it could be economically viable to use a 2 of 2 escrow as hostage to get some free funds.  That can be negated by requiring one or both parties to put a deposit into the escrow.  The scammer now has something at risk (either reputation, or the deposited funds).  If the deposit is more than the expected value of future extortion the "game" is now a net loss for the scammer.

Generally people don't work against their own economic interests.

However with a coin flip on deadlock the scammer will win 50% of the time.  It is unlikely any extortion attempt would be successful 50% of the time so you have improved the odds.

If we consider all the disputed transactions and grouped them into the following categories which do you think makes up the lions share:
* one party is intentionally at fault (scammer)
* both parties generally believe they are in the right (failure to communicate)
* some technical issue (lost wallet, one party dies, funds are stolen before payment, etc)

I would argue that the first case is the overwhelming majority of disputed payments.  The scam and run scenario.  A coin flip hurts the prevention of that scenario.    Go after the biggest problem first.

It doesn't have to be a 2 sided coin. Think of it as insurance. The service might payout to the vendor a percentage based on agreed terms. Depending on the relationship between the buyer and seller it could be 50-99. It's like insurance. In fact either side can scam, but depending on each reputation in the community it might hurt if arbitration is used a lot. The vendor already has a down payment and not as much to lose. The arbitration service can even keep track of arbitration stats and publish them anonymously if desired.

[interlagos]

I think the proper solution for two-party escrow should revolve around the idea that in order to initiate the deal both parties (seller and buyer) should first interlock small percentage of coins in a way that they will get them back once the deal is done. The payment for the deal should be put on top of that. This should create incentive for both parties to behave nicely and unlock the funds, so that they can get their original coins back.

Is it possible to come up with technical solution for this via multiple-sig or math tricks?

[cbeast]

I think the proper solution for two-party escrow should revolve around the idea that in order to initiate the deal both parties (seller and buyer) should first interlock small percentage of coins in a way that they will get them back once the deal is done. The payment for the deal should be put on top of that. This should create incentive for both parties to behave nicely and unlock the funds, so that they can get their original coins back.

Is it possible to come up with technical solution for this via multiple-sig or math tricks?

I've seen this idea before. Could you give a real world scenario where this would be useful?

[etotheipi]

I think the proper solution for two-party escrow should revolve around the idea that in order to initiate the deal both parties (seller and buyer) should first interlock small percentage of coins in a way that they will get them back once the deal is done. The payment for the deal should be put on top of that. This should create incentive for both parties to behave nicely and unlock the funds, so that they can get their original coins back.

Is it possible to come up with technical solution for this via multiple-sig or math tricks?

I've seen this idea before. Could you give a real world scenario where this would be useful?

Gavin and I have debated this topic thoroughly.  I believe the no-third-party escrow scenario is not only possible, but real-world-usable between two untrusted parties using this idea. I coined them "risk deposits" (or someone else did, I don't remember).  So far, I have not seen any evidence of why this concept wouldn't work (though, there are multiple ways to do it).

I will link to my own thread about it where Gavin and I discussed how it might work:  https://bitcointalk.org/index.php?topic=75481.0

The upside is that it is secure and feasible:  both parties can commit their risk deposits along with the payment as a single transaction.  It's all-or-nothing, so no one party can get screwed.  Then both parties have high incentive to agreeably complete the transaction.  In my own words:  "if it costs money to be a dick, there will be a lot less dickery".

The downside, of course, is that's it's complicated.  And it's different.  Committing money even as the seller is weird, and many people would be hesitant to use it (mainly due to a lack of understanding, or unwillingness to have extra money locked up).  These are real criticisms that I can only say one thing about:  Bitcoin itself is both "different" and "complicated".  Users who are knowledgeable should and would be willing to learn this technique to buy and sell stuff to strangers on the internet with high confidence.

I still recommend third-parties, and the risk-deposit is a nice way to already have third-party-arbitration fees available for the third-party if they are needed.  But I still think the two-party version should be ironed out and feasible (and I'd like to simplify it as much as possible in Armory).

[cbeast]

I think the proper solution for two-party escrow should revolve around the idea that in order to initiate the deal both parties (seller and buyer) should first interlock small percentage of coins in a way that they will get them back once the deal is done. The payment for the deal should be put on top of that. This should create incentive for both parties to behave nicely and unlock the funds, so that they can get their original coins back.

Is it possible to come up with technical solution for this via multiple-sig or math tricks?

I've seen this idea before. Could you give a real world scenario where this would be useful?

Gavin and I have debated this topic thoroughly.  I believe the no-third-party escrow scenario is not only possible, but real-world-usable between two untrusted parties using this idea. I coined them "risk deposits" (or someone else did, I don't remember).  So far, I have not seen any evidence of why this concept wouldn't work (though, there are multiple ways to do it).

I will link to my own thread about it where Gavin and I discussed how it might work:  https://bitcointalk.org/index.php?topic=75481.0

The upside is that it is secure and feasible:  both parties can commit their risk deposits along with the payment as a single transaction.  It's all-or-nothing, so no one party can get screwed.  Then both parties have high incentive to agreeably complete the transaction.  In my own words:  "if it costs money to be a dick, there will be a lot less dickery".

The downside, of course, is that's it's complicated.  And it's different.  Committing money even as the seller is weird, and many people would be hesitant to use it (mainly due to a lack of understanding, or unwillingness to have extra money locked up).  These are real criticisms that I can only say one thing about:  Bitcoin itself is both "different" and "complicated".  Users who are knowledgeable should and would be willing to learn this technique to buy and sell stuff to strangers on the internet with high confidence.

I still recommend third-parties, and the risk-deposit is a nice way to already have third-party-arbitration fees available for the third-party if they are needed.  But I still think the two-party version should be ironed out and feasible (and I'd like to simplify it as much as possible in Armory).

I wasn't asking why a 2 of 2 escrow is needed, I was asking why *both* parties need to lock money which the conversation with Gavin does not address, but my solution sort of does.