Bitcoin Forum

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.

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

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 (https://bitcointalk.org/index.php?topic=75481.0).

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).

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

QPriv = k*Bpriv

B learns Qpriv when A sends k to B.

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!

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.



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.

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.
 

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

Yes, that's true. Good point etotheipi !

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.

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.

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 :)


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

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


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)

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.

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 (https://bitcointalk.org/index.php?topic=99566.msg1088647#msg1088647) sort of does.

That conversation should address exactly that question.

Without buyer committing a risk deposit,  they have no reason to finish the transaction after receiving the goods.   They might have received a low-quality product and decided to spite the seller by leaving the coins locked.

Without the seller putting in a risk deposit, he can make bogus postings for merchandise for stuff he doesn't have and get victims to lock money into a 2-of-2 tx that he can then hold for ransom without any risk to himself "you're not getting any money back unless you sign this tx giving me half of it. "

Your proposal IS a three-party arrangement.  There's absolutely nothing wrong with it...  In fact I had a very similar idea a while back,  and I think it makes for a good third-party business model.  L

But there will always be demand for a true two-party solution.   That's where risk deposits are critical if they are going to happen at all.   

This is why most larger sales contracts require at least a down payment. The seller already sent the goods, so already has enough comitted to the contract. As far as bogus sellers, caveat emptor. That's why vendors should have a public rating system or better yet, a good relationship between the vendor and buyer. If the customer decided to stiff an honest merchant, then that merchant would lose more than the customer with the merchandise and the escrow. I can see what you are trying to do, I just don't have an analogy in normal business transactions to relate this too.

I'm looking for anyone that is working on a decentralized gambling system to provide "Provably Fair" random number generation for an automated 3rd party private key provider.

"Caveat Emptor" is exactly what Bitcoin is trying to avoid.  There's no reason for that when Bitcoin offers a very good solution that dramatically reduces the risk and splits the rest of it across both parties.  It's not perfect, but I'm also not talking about large transactions.

Hypothetical:  I want to buy a WoW sword from you for 1 BTC.  We've never met in real life.  In fact, I think you're kind of a creep, so there's no reason I want you to know any more information about me than you already do.  The problem is there are no third-parties that want to even touch this.  Many of them don't want to deal with digital goods, and even if they did, there's no way for them to verify that the exchange of the sword actually ever happened.  Not only that, but taking 0.2 BTC fee for arbitrating this transaction is a waste of time for them.  (and some transactions, one or both parties may not even want a third-party, for privacy reasons).

Does that mean this transaction shouldn't happen?  We could go back to the original way where one party (buyer or seller) assumes all the risk by sending their half first, and hope the second party follows through.  I think you're a creep (not really, though :)), so I'm not going to trust you.  There's no way I'd do this "the traditional way."   The risk-deposit idea offers a solution. 

I think the problem with this type of transaction is "who goes first?" How would you even layer this transaction? Who puts up the money first without someone getting suckered by someone backing out? If they can be done simultaneously, then fine, but how do you verify it? It just seems to be a very complicated process to design. Maybe this is a function of the NTimeLock?

I've been thinking that these escrows are not unique to Bitcoin and perhaps should be done by payment processors like PayPal, Dwolla and even MtGox first, just to see if people would use them.

Yes, it's possible to guarantee that all parties' money gets committed at exactly the same time.  All purchase money and risk deposits get broadcast in the exact same transaction.  That transaction is not valid until all relevant inputs are included and signed.

It's not trivial to implement, but once it's done, it can be fairly transparent to the user.  Gavin and I were discussing in that thread how it might be done under-the-hood.

See how I will use escrow without third parties (With NO fear)

1- The buyer and seller will commit risk deposit.
2- The risk deposit will have more value than the product being traded. Why?
Because the buyer could receive the product and not release the bitcoins. (The world has a lot of bad people)
3- All parts will have incentive to act honestly. Otherwise the two parts will lose money.

You can do more impressive things with ZNPs, https://en.bitcoin.it/wiki/User:Gmaxwell/why_hash_locked

But it's all just armwaving unless someone bothers writing code to actually do something useful that way.

In your proposal you say: " The reason this isn't something people are using yet is because while the academics have proven it to be possible actually converting complicated programs like compositions of ciphers and hash-functions into zero-knowledge proofs is apparently not something anyone has figured out how to do practically.".

Your proposal is, as you say, completely impractical. What you are saying in why_hash_locked (if possible) requires a huge amount of computation and probably 100 Megabytes message as proof.

A zero knowledge proof of knowledge of k in k*GPub is only a hundred bytes long, and takes only three EC multiplications to achieve. What more practical than that!!
You can do it either by Chaum-Pedersen protocol , Schnorr’s Id Protocol or even naive cut-and-choose.
(edit: The first two protocols were designed for the Poligh-Helman cipher, and must be adapted to ECC)

Please Max !!!

And also doesn't give you any assurance that the delivered good is as described, except via witholding— which can still be done if the good is as described: holdup / extortion: "Thanks for the car, if you want me to release the payment you'll need to prepare a transaction returning half of it, cheers!".  If you just want to have sender locked transactions you simply use a two of two output, or a plain hash locked transaction, absolutely no need for ZKP or anything fancy.

I completely agree with you about holdup / extortion.

But don't say that ZNPs are "impractical" . There are plenty of practical protocols that rely on ZNPs.