Idea for a mixer that can't run with your coins

[Murphant]

I have a proposal that might or might not be feasible in Bitcoin. I do not fully understand the capabilities of the Bitcoin script and would like to know if it supports such a functionality.

Say Alice wants to mix her coins with a mixing service but she does not trust that the mixer will not run off with her coins.

Alice produces an order that says the following:
    I will give you 10 btc from address A and you must send that amount minus the fees to addresses B and C in a specified time frame.
Alice signs this order and privately sends both the order and its signature to the mixer.
Alice sends 10 btc to the mixer in a special transaction T that locks her coins and is not accepted by the network until it fulfills one of these three properties
-Alice signs T, then the coins go to the mixer
-The mixer provides a proof that B and C have received the expected btc in the expected time frame and produces the signed order, then the coins go to the mixer
-A timeout (say 2 weeks) makes the coins go back to Alice

The result is the following
-If everything goes as planned, Alice signs T, T goes to the mixer, the mixer never publicizes the order and Alice has gained her anonymity
-If the mixer never pays B and C, Alice doesn't have to do anything and her coins are refunded as T refunds the coins to Alice after the expiration period.
-If the mixer pays as expected but Alice does not sign in a timely manner, the mixer can produce the signed order as well as the txs used to pay B and C and T pays the mixer. In this case, Alice loses her anonymity.

It seems to me that neither party can cheat the other out of its money, and both parties will want the transaction to go through. Does that seem right?


There are a few technical things that I am uncertain about
1. Can Alice lock the coins from A in such a manner?
2. Can a transaction be such that depending on how the are conditions met, the coins are output to different addresses?
3. Is is possible to make the script understand the contract and to "prove" that B and C were paid?

[1713514361]

1713514361

[1713514361]

1713514361

[1713514361]

1713514361

[1713514361]

1713514361

[1713514361]

1713514361

[gmaxwell]

This cannot be implemented in the script today due to disabled op_codes.  Even if it could be, the resulting transactions for the proof of payment redemption would be prohibitively large: They'd have to contain a SPV fragment for the mixer->b,c transaction plus some block headers, and the complete mixer->b,c transaction, and the script search for the right outputs and then check the fragments.

We could perhaps enable this with a soft-forking addition to add an opcode that verifies a SPV fragment, and constrain your protocol that Alice must know the exact transaction the mixer intends to make... e.g. under 400 bytes of data. Very interesting. I'd want to see other use cases for this.

(As an aside, your notation of "from address", "to address" suggest a pretty substantial misunderstanding of the Bitcoin system, likely inspired by block explorer sites that present things in terms of "address = account", this isn't how the protocol actually works.. but what you're describing could be restated in terms that do make sense in the Bitcoin protocol)

If script is ever extended to allow compact proofs of computation then what you're describing could work without huge transactions.  If the proof of computation is zero-knowledge then your protocol could be simplified further: instead of Alice releasing the coins in the faithful execution case the your second party could redeem them using a zero-knowledge proof that Alice's rules were followed, without actually revealing what those rules were.

[Murphant]

This cannot be implemented in the script today due to disabled op_codes.

Can you please be more precise as to which parts could not be done? Not that I don't believe you, I just want to see if I can go around them.

Even if it could be, the resulting transactions for the proof of payment redemption would be prohibitively large: They'd have to contain a SPV fragment for the mixer->b,c transaction plus some block headers, and the complete mixer->b,c transaction, and the script search for the right outputs and then check the fragments.

We can simplify for now by supposing that Alice will only receive her funds at address B. I understand that the Mixer -> B tx and the header of the block that contains it will have to be referenced, but I didn't expect it to be very large. I understand that the proof verification will be more computationally intensive for verifying nodes. I'm not sure I understand that a "SPV fragment" is and google isn't helping me much.

[...] constrain your protocol that Alice must know the exact transaction the mixer intends to make [...]

I agree that might be necessary.

As an aside, your notation of "from address", "to address" suggest a pretty substantial misunderstanding of the Bitcoin system, likely inspired by block explorer sites that present things in terms of "address = account", this isn't how the protocol actually works.. but what you're describing could be restated in terms that do make sense in the Bitcoin protocol

What I mean by "from address A" is "signed by A's private key" and what I mean by a "transaction to address B" is a "transaction that can only be spent by using B's private key". I understand that accounts are not unified and that the "balance" of an address rests in the number of txins it is able to spend. Am I missing or misrepresenting something? How would you rephrase these terms?

If script is ever extended to allow compact proofs of computation (https://bitcointalk.org/index.php?topic=277389.0) then what you're describing could work without huge transactions.  If the proof of computation is zero-knowledge then your protocol could be simplified further: instead of Alice releasing the coins in the faithful execution case the your second party could redeem them using a zero-knowledge proof that Alice's rules were followed, without actually revealing what those rules were.

If the script ever gets extended in such a way, I believe that what you propose would be best indeed.

[Jocky]

Isn't it contraproductive to link Alice's old Bitcoin to the Bitcoin she receives in the blockchain?
If the coins are locked until another transaction has transpired, miners (and therefore everybody) will see that, even after said transaction has transpired.

People can search the blockchain to see if there was ever a condition that stated x Bitcoin had to be sent to Alice's address in order to unlock Bitcoins. Leaving Alices new 'mixed' bitcoin forever linked to her old ones.

Or do I see this wrong?

[gmaxwell]

This cannot be implemented in the script today due to disabled op_codes.

Can you please be more precise as to which parts could not be done? Not that I don't believe you, I just want to see if I can go around them.

Take a look at the script opcode list. Without the splice operators you have no way to construct the verification of a SPV proof of a transaction. (or to test a transaction to see if its the right one, though that part at least could be circumvented by just requiring the contracted transaction to end up exactly in the blockchain, it doesn't save you from having to verify a spv proof).

"balance" of an address rests in the number of txins it is able to spend. Am I missing or misrepresenting something? How would you rephrase these terms?

I'd avoid ever using the world "balance". Nothing in the system itself keeps any kind of balance or checks any kinds of balance. Txouts are created and consumed (calling them 'coins' is a common convention).

I'd describe what you're asking for is a way to create a transaction which can be redeemed by the agreement of  Alice and M,  OR Alice after N weeks, or M alone, if M provides proof of a particular coin being created in the chain.

[Murphant]

People can search the blockchain to see if there was ever a condition that stated x Bitcoin had to be sent to Alice's address in order to unlock Bitcoins. Leaving Alices new 'mixed' bitcoin forever linked to her old ones.

That will only happen if the mixer ends up proving that he sent the coins. With such a threat in mind, Alice would rather indeed sign whenever she has received the output coins (why wouldn't she anyways?), at which point the contract is never been made public as the mixer has no reason to do so and the association between Alice's old and new addresses is never included into the blockchain.  In other words, the "condition that stated x Bitcoins had to be sent to Alice" clause is never released in the blockchain if Alice signs.

However, as gmaxwell points out, it appears that this attaching of a contract and a proof to a transaction is not possible in Bitcoin at this point.

[gmaxwell]

I suggest calling this an "airgapped payment".   The minimum things we need to turn on in script to make this useful would also be very handy for improved security for cross chain payments.... on the order of no more than 400 bytes plus the size of a regular transaction, assuming the block size is not increased.

This is pretty viable... and though I don't think additions to script are that exciting (because people hardly use what we have. ) ... the use-cases enabling hash tree verification would enable are pretty interesting for such a simple change.

However, I had previously showed how to use hash-locking to do cross-chain trades without this functionality, and I believe I can do the same to this protocol:

Here is a hash-locked version of an air-gapped payment protocol which would work today.

Alice wants to pay Bob without a publicly visible connection between them, or even without Bob learning anything about Alice's coins.

Carol offers to help, but Alice and Bob do not trust Carol and Carol does not trust Alice or Bob. In fact they all don't trust each other. At all. (I mean, look around Bitcoin talk, would you trust anyone here?)

Bob picks a secret value X and computes its hash H(X)=HX tells the hash to Alice and Carol.

Alice puts funds into an escrow which can be redeemed:

• By Alice + Carol (normal)
• By Carol if Carol provides HX, X, Q  such that HX==H(X)  and H(HX+Q) == value specified in the escrow payment.

Before announcing this transaction, Alice has carol write her a nlocktimed alice+carol refund, so if Carol is a dead-beat Alice will get her funds back eventually.

Alice tells carol Q. And Carol is convinced that she can redeem this transaction without Alice's help if only she also knew X.

After that escrow payment is confirmed Carol then pays to Bob with a hash-locked transaction which can be redeemed:

• Bob + Carol (refund)
• Bob + he must provide X such that H(X) == the prior disclosed HX

Like above, Carol has Bob help him write a nlocktimed refund before she announces this transaction.

Tada. Bob redeems it and discloses X.

If Alice doesn't do the release, Carol will redeem via disclosing Q, which will link the transactions because then anyone can look for all the signature+hash transactions and find the HX+Q one.  Otherwise no one learns the correspondence, not even Bob, since he doesn't know Q.

[Peter Todd]

Ok, so as discussed on IRC, gmaxwell's clever idea doesn't work because OP_ADD/XOR/damn near anything is crippled.

But I've got a better idea:

Bob picks a secret value X and computes its hash H(X)=hx and tells that hash to Alice and Carol.

So Alice pays into the following scriptPubKey with tx1:

2 <alice> <carol> 2 CHECKMULTISIG

Next she signs a transaction, tx-alice-awol, spending that txout (remember tx mutability!) to the following scriptPubKey:

HASH160 <hx> EQUALVERIFY <carol> CHECKSIG

tx-alice-awol is not broadcast.

Carol then pays Bob with a transaction output of the following form:

HASH160 <hx> EQUALVERIFY 1 <carol> <bob> 2 CHECKMULTISIG

To redeem that output, Bob is forced to reveal X, which allows Carol to use tx-alice-awol to get the funds payed to her by Alice. (we have to allow Carol to take the txout back, or Bob could just sit on it forever)

Finally, once Alice sees that Bob has succesfully redeemed his txout, Alice also signs for her part of the tx1 output with SIGHASH_ANYONECANPAY|NONE, Carol saves this signature, which allows her to spend that txout later.

[gmaxwell]

In further discussion retep realized that the Bob side could also be 2-of-2 in the normal honest case, backed up by hidden spends that used hashlocking.

This turns the protocol in to a full on transaction teleportation which in the common case looks like really boring 2of2 escrows and not special at all, though it results in a three layer protocol where you have the common cases, plus a layer of time based refunds, and a layer of hash-locked cheating escapes, and now probably needs a proper state diagram.

The net/net is that alice can pay bob via carol, in a way that shows no direct connection between alice and bob to the public (unless someone cheats), and which no one can rip of anyone else, and where the public transactions in the no-cheating case look somewhat normal (they're 2-of-2 escrows).

[icedicedavid]

Why can't you add a feature to bitcoin-qt to generate say 100 addresses and randomly send funds back and forth a bunch of times. It'll cost some transaction fees but then wouldn't it mix the coins up pretty good?

[gmaxwell]

Why can't you add a feature to bitcoin-qt to generate say 100 addresses and randomly send funds back and forth a bunch of times. It'll cost some transaction fees but then wouldn't it mix the coins up pretty good?

No, that does basically nothing but waste network capacity. It's readily apparent in a transaction graph where the funds came from and went.

[icedicedavid]

Why can't you add a feature to bitcoin-qt to generate say 100 addresses and randomly send funds back and forth a bunch of times. It'll cost some transaction fees but then wouldn't it mix the coins up pretty good?

No, that does basically nothing but waste network capacity. It's readily apparent in a transaction graph where the funds came from and went.

Then what about creating multiple wallets and send funds between it back and forth? As long as it's local, you are not sending the coins to anyone else but yourself.

[Peter Todd]

Then what about creating multiple wallets and send funds between it back and forth? As long as it's local, you are not sending the coins to anyone else but yourself.

Picture a huge expanse of desert sand. In the middle of the sand is thousands of footprints crossing in every direction. Surely no-one could ever identify these indistinct and commingled tracks!

But our FBI investigator is smarter than that, and observes that while the middle of the sand is confusing, there is a clear border of untouched virgin sand, unmarred except for a single set of footprints entering, and a single set of footprints exiting...

[icedicedavid]

Then what about creating multiple wallets and send funds between it back and forth? As long as it's local, you are not sending the coins to anyone else but yourself.

Picture a huge expanse of desert sand. In the middle of the sand is thousands of footprints crossing in every direction. Surely no-one could ever identify these indistinct and commingled tracks!

But our FBI investigator is smarter than that, and observes that while the middle of the sand is confusing, there is a clear border of untouched virgin sand, unmarred except for a single set of footprints entering, and a single set of footprints exiting...

but as number of these footprint increases (number of wallet used), it'll look more just like a big patch of transactions, rather than a patch of footprint in the middle of the desert no?

[Peter Todd]

but as number of these footprint increases (number of wallet used), it'll look more just like a big patch of transactions, rather than a patch of footprint in the middle of the desert no?

Nope. No matter how many wallets you make the coins all came from the same place.

[Sergio_Demian_Lerner]

Interesting protocol, I will analyze more carefully. I suppose the retep version is the one being discussed.

[Sergio_Demian_Lerner]

I was thinking that the same can be accomplished by the protocol socrates1024 describes for p2p trading here https://bitcointalk.org/index.php?topic=193281.msg3315031#msg3315031.

The idea is that a p2p trade takes place, but for the same cryptocoins instead of two different cryptocoins.
Also only the traders know if they have exchanged coins or they have simulated a coin exchange.

Before they start the protocol they first choose randomly if they will simulate or not.
If it is a simulation, then pubkeyB is replaced by pubkeyA' in TX1 and pubkeyA is replaced by pubkeyB' in TX3.

In both cases it requires 4 transactions (2 bail ins and 2 trigger transactions).

How these two protocols compare ?

The socrates1024 is very easy to analyze.

[gmaxwell]

I was thinking that the same can be accomplished by the protocol socrates1024 describes for p2p trading here https://bitcointalk.org/index.php?topic=193281.msg3315031#msg3315031.

The idea is that a p2p trade takes place, but for the same cryptocoins instead of two different cryptocoins.
Also only the traders know if they have exchanged coins or they have simulated a coin exchange.

It can't— because you lose privacy that way. E.g. someone can look at the un-executed paths and see the hash-values and link them.

I moved the longer description to it's own thread: CoinSwap.