TumbleBit
Ethan Heilman
Leen AlShenibr
https://twitter.com/kanzure/status/784686167052709888
Hi. So I'm going to be talking about tumblebit. It's our untrusted private bitcoin payment system. Tumblebit provides payments which are private. They provide set anonymity when used as a classic tumbler. They are untrusted. The tumbler can't violate your privacy, and can't steal your coins. It's also scalable. It's compatible and works with today's bitcoin. There are no malleability concerns. We're going to rely on the constrained opcodes that currently exist in bitcoin.
There's two ways to use tumblebit. You can use it as a classic bitcoin tumbler, providing k-anonymity. This is a more private version of coinswap. It has four transactions that are confirmed in two blocks. It has an average mixing time of 20 minutes. And then we can use tumblebit as a payment hub. It provides unlinkability during a payment phase. Payments are confirmed in seconds because they are off-blockchain. We are using payment channels.
Before I explain tumblebit, I am going to do a brief reminder of a unidirectional payment hub and then I am going to evolve that into tumblebit. Alice and the hub have a undirectional payment channel implemented with two escrow transactions which are 2-of-2 multisig. Both parties on each end of the escrow need to sign off to spend that escrow. Alice wants to pay Bob through the payment hub so she does a claim transaction, payment hub creates a claim transaction as wlel; Alice signs the claim transaction to authorize it, the hub signs the other claim transaction. To close the channel, Alice can sign one and Bob signs one. There's a problem with this, which is that the payment hub could be malicious and not sign the second claim transaction and therefore walk away with the money. So one way to fix this is to make it atomic, so that either they both happen or they don't happen at all.
One way this is solved is with hashlocks. You have some value x, the claimed transaction can't happen without x. Bob can't take money until Bob learns x. So Alice creates a second hashlock that uses the same x, and when the payment hub claims the funds, it has to reveal the value x. Alice can tell Bob what the value of x is. So HTLCs are helpful.
The problem is that if you have a bunch of people using this, the payment hub can link the hashlocks. You can see Alice 1 is paying Bob 2 because they are both using the same hash value, hash input preimage. So it provides no privacy from the hub. So the main idea of tumblebit is to provide this in a way that is unlinkable, so that the hub can't see which transactions are atomic.
You can think of it as unlinkable or private HLTCs. The main cryptography that I am going to use for this is RSA. We use RSA puzzles, which are textbook encryptions of some value epsilon. The tumbler has a public key. It performs RSA operation on epsilon and generates z, our RSA puzzle. Notice that the tumbler has a secret key and because the tumbler is using RSA textbook encryption, only that can solve the puzzle. So if it is given a puzzle z, it can use its secret key and get epilson. A tumbler can initiate the puzzles and solve the puzzles.
We can use RSA blinding. Bob can blind his puzzle to Zstar. And sends Zstar to the tumbler. The tumbler can solve this and end up with a blinded solution epsilon star. Bob can unblind epsilon star to the original solution to z2. If Bob does this over tor, so that the tumbler doesn't realize that the tumbler is talking to Bob, then the tumbler can't link the puzzle it has solved. It knows it has solved a puzzle, but it does't know whether it was puzzle z1 or z2, because the puzzle sent to the tumbler was blinded.
Tumblebit is based around this idea. What the tumbler is going to do is the tumbler is going to say to Bob I will if you solve this RSA puzzle, I'll give you one bitcoin. And the tumbler says to Alice I'll sell solutions to RSA puzzles. So you can see how this might allow Alice to pay Bob. Alice pays 1 bitcoin to solve hte puzzle, Bob then redeems one bitcoin. On the right side here, we see that Bob is going to do the protocol where if he learns the solution to epsilon he will get a coin.
So first I'll explain how Bob does this, then I will show the fair exchange. So the tumbler is going to create an RSA puzzle with a solution epsilon. Then it uses an ECDSA signature and encrypts it under the solution to the RSA puzzle and creates ciphertext c. This signature is going to be a signature to a transaction that allows Bob to spend one bitcoin out of this escrow. So if Bob learns an epsilon, he can decrypt c to get sigma, so if he solves th RSA puzzle Bob can get a signature and he can use that signature to get one bitcoin. Bob blinds it, sends the blinded puzzle to Alice, Alice performs a protocol and gets the blinded solution, and Bob can now... decrypt the ciphertext to get the signature, and now he has a valid signature on that transaction and can get coins from there.
I'm going to talk about the fair exchange from Alice to tumbler. You can use zero knowledge contingent payments here. Alice wants to trade a solution here for some ... we don't use ZKCP. We are using 2048 RSA and it would be fairly slow in zkSNARKs. But this could part could be solved by a ZKCP, sure. So Alice sends the blinded puzzle to the tumbler. Similar to the tumbler's earlier actions, the tumbler is going to solve the blinded puzzle and get epsilon star. If the tumblere tells Alice the value of epsilon star, then Alice would be able to get coins oops. So it's going to send the ciphertext and y to Alice instead, so if Alice learns X she can decrypt Q and get epsilon star. Alice is going to create a transaction that gets 1 coin out of escrow, if the tumbler reveals value x, and then Alice can decrypt Q and get epislon star and send that back to Bob. The problem here is that the tumbler could not play fiar... maybe they generate c here that is some random value, and if Bob tries to decrypt it, he wouldn't get a valid signature. Oops.
So the way we solve this is two protocols. We have a puzzle promise protocol to convince Bob that the solution to a puzzle is a valid signature on a transaction. The other protocol is a puzzle solver protocol to convince Alice that the preimage x will allow her to learn epsilon star. Both of these protocols are similar, they use similar tricks. If I have time, I might go into the puzzle promise protocol. I'll be happy to show this.
Tumblebit has three phases. In the first phase all the payment channels are setup. Each of the Bobs are given ciphertext and RSA puzzles. We want to be able to make multiple payments. There are additional ciphertexts and RSA puzzles. Each one gives an additional bitcoin to increase the payment channel size. Each puzzle is locked until Bob unlocks it, and he can use the signature to unlock the next RSA puzzle. The next phase is where the payments happen, we imagine this to be one month or less than that. Let's say Alice pays 1 bitcoin to the tumbler using the fair exchange.. Bob uses that signature to increase the payment channel by 1 bitcoin, and unlock the next puzzle. Alice pays again, Bob gets another signature and unlocks another puzzle, gets another signature, and we can imagine lots of these payments happening. Also, we have a cash-out phase.
Our unlinkability definition is that... we refer to an interaction graph as any way that this could have happened between all the parties. We're unlinkable in that all interaction graphs compatible with the tumbler are equally likely. All of them are likely to have happened. There could be an extremely large set of interaction graphs where it ends up with this Bob getting the coins. The tumbler can't figure out which set of interactions led to those outcomes.
Tumblebit can also be used as a classic tumbler. You can't tell what the old address was. To run this as a classic tumbler, you would open a payment channel with one bitcoin to be used with only one payment. We have a equal number of payers and payees. Each participant makes just one payment. To solve the anonymity problem, other schemes have been proposed. Coinswap and coinshuffle are vulnerable to DoS attacks. Coinshuffle has a limited anonymity set because it's limited by the transaction size of a few hundred kilobytes.
We have implemented a proof-of-concept of the classic tumbler. We have source code available on github. Our implementation is perfomant. It consumes only 320 kilobytes of bandwidth. Most of the time is spent on the puzzle solving protocol. If you run tumblebit on the same machine, it takes only 0.6 seconds. If you run the server in Tokyo and Alice and Bob in Boston, then it takes 6 seconds. And through tor it takes 11 seconds.
In conclusion, tumblebit provides private untrusted scalable payments via today's Bitcoin. We have running code for the tumblebit classic tumbler. We run our code on bitcoin mainnet blockchain. You can look at our tumbles. We are working on our source code to make it safe and easy to use. We want to make it far more secure. We're trying to hire a full-time engineer. Email me if you're interested.
Also I want to explain one of the protocol. The puzzle solver protocol, remember this is the one that allows Alice to exchange a blinded solution for a -- a blinded puzzle for a blinded solution. We want it to be fair-exchange. We want Alice to pay the tumbler if and only if the tumbler provides a valid solution, and the tumbler reveals a solution only if Alice pays. So Alice gets this z star from Bob. And when she does, she's going to create what we call n real puzzles and n fake puzzles. The real puzzles are all blinded versions of z star, so they will be double blinded. The fake puzzles are going to be values that Alice chooses and that she then encrypts under the tumbler's public key-- so she knows the answer. She shuffles these together, and sends them to the tumbler. The tumbler doesn't know which are the real ones and which one is the answer that Alice wants. So the tumbler provides solutions for every one. Alice would be able to take the money. The tumbler is going to encrypt eah solution under a different x, hash all of them to get a hash output of y, and send them to Alice. So it's in this stage the tumbler is committing to these solutions wihtout revealing them. Then Alice is going to reveal whih one of them are fake, so she tells the tumbler, if oyu tell me the solution to these, I don't learn anything new so here are all the answers to the fake puzzles, the tumbler checks that they are the real answers to the fake puzzles, and it reveals the keys that allows Alice to decrypt the fake puzzles, and Alice can check that the fake puzzle solutions were computed correctly. So, Alice proves all the real puzzles unblind to the same puzzle, so she gives all the blinding factors to the tumbler to check that she can get only one answer. At this point they are good; Alice provides a transaction that asks for all the X's to the real puzzles. The tumbler provides the X's, the tumbler gets paid one bitcoin. Alice learns all the X's which you can use to decrypt all the Qs and learn epsilon star. If the tumbler computes any of the reals correctly, Alice learns epsilon star because they are all.. for z star.. If the tumbler can cheat Alice, then the tumbler must corrupt all the real puzzles, not just some of them. If the tumbler corrupts any of the fake puzzles, then Alice will know this. So the tumblr has to guess exactly which puzzles are the real puzzles. So the probability that the tumbler can do this successfully is tis.... ~1/(280). We chose this number because this is the collision resistance of RIPEMD160. So this is a very small number-- it can only happen with very low probability.
Q&A
Q: How do you track liquidity? How do you incentivize people? Do you pay them?
A: So the question is about incentives in setting up the system. I didn't talk about it, but it was always 1 coin for 1 coin. It's easy to build a fee into this. You would probably only want one or two of these. The more people use it, the better the anonymity provided.
Q: Very cool interesting work. I like the clever use of Chaumian e-cash here. I don't quite understand or on what basis you are assrting that this approach is less vulnerable to sybil attacks than other approaches like coinjoin. Maybe there's 1000 Alices and 1000 Bobs, but maybe 999 of Alices or 999 of Bobs are fake that the tumbler created. So how is this better than the coinjoin world?
A: In temrs of omparison to coinshuffle or coinjoin... a sybil attacker can abort. So if the sybil attacker doesn't win any particular round, it can start that round over again. Coinshuffle has some protections against this.
Q: ...
A: Coinshuffle gives them at least one abort, but not multiple aborts. If they have multiple sybils, they can do the abort. The other issue, which I didn't mention, we have these anonymous fee vouchers. In the classic tumbler mode, we place a cost on the sybils. If a sybil fails to deanonymize a particular round, it just fails and that round happens. Each time it wants to try, it has to pay money. It can't just leave and not pay. In the payment hub scheme, we require that people lock some coins in escrow. These payment channels like coinswap add on top of each other. If you want to add 30 sybils and 100 people want to play, you don't get to replace those 100 people, you just add 30 additional sybils. It doesn't degrade the protocol.