TumbleBit for the tumble-curious

Posted by: Adam Gibson | in Bitcoin, Cryptography | 10 months, 3 weeks ago | 2 comments

New ideas about achieving fungibility in Bitcoin or similar systems are coming at a furious rate; it's pretty difficult to keep up. One idea that was published recently I found to be particularly interesting - TumbleBit. The linked paper has the full description, both theoretical and practical, and even links to working code (that's a bit of a rarity unfortunately). If you're capable of reading the paper in full, you won't really need this blogpost, but I know most aren't, yet some are still very curious, so here we are.

Maybe even better than the working code is the POC tumble transactions, linked in the github README, that show how the model has been used to delink 800 inbound payments from 800 outbound  (equal sized) payments in a single tumble run. This nicely illustrates how the blockchain-level separation achieved gives rise to a great scalability-of-mixing win.

Apologies in advance for the length! The intention is to get into the guts of the protocol, although missing a few details in that respect. If the post achieves anything, it's mainly a matter of translating the mathematics into English; hopefully it can convince you that what TumbleBit achieves, while seeming very implausible at first glance, does actually work, practically. If it inspires you, I'd like to strongly encorage reading the original paper; I'd also strongly welcome any corrections!

Goal of the system

1. The classic tumbler model

Existing bitcoin "mixers", "washers", "tumblers" have a fully centralized model: not only centralized in that clients/customers do all negotiation with a central server, but most importantly trust that central server with their funds, and their information. The negatives of this model are so obvious that we needn't dwell on them here; the positives are however worth reflecting on - centralized services solve a coordination problem, but in the context of Bitcoin mixing a more profound issue is addressed - mixing within one transaction (see Coinjoin, including all variants) does not break linkages so much as fuse them; a confusion effect. A mixer, albeit it's very hard to do this well, can completely break linkages between money sent in and money sent out. Of course like any anonymity supporting system, it is limited by the anonymity set (if you are the only user of mixer server A you're not getting great anonymity!), but in principle it has that much more powerful effect of link "severage". To be fair, CoinSwap also has this property, but I haven't investigated this enough to comment yet (the paper does make a few high level comparative comments).

TumbleBit proposes to remove the main negative feature of the 'standard' mixer model - the trust (both types - trust in holding funds, trust in knowing linkages), while still keeping the breaking of linkages on-chain. In its first proposed model, which it calls the "classic tumbler model", a set of users can join in a tumbling session, send in coins, wait, and then receive completely disconnected coins later - without worrying that the tumbler's going to run away with the money or know whose coins are whose.

2. The unlinkable payments hub model

I won't be investigating this in this document; refer to the original paper for more details.

The crypto, dumbed down

Here's the "magic" version. Even if you don't read the main paper, take a look at Fig. 1 in reference to this, it may help it to make more sense; although it'll take the rest of this blog post to properly explain it:

  • Alice puts 1 coin into escrow with T
  • T puts 1 coin into escrow with Bob
  • Bob gets an encrypted signature on a transaction to pay
     him (Bob) 1 coin from the escrow with T. He can't yet broadcast/spend it; Bitcoin itself doesn't handle encrypted signatures!
  • Bob sends the encrypted (and blinded) decryption key for the signature to Alice.
  • Alice does a "fair exchange" to get the decryption key
    for the encrypted signature from T, in exchange for paying T 1 coin, from her escrow.
  • Alice can effectively pay Bob by handing over the decryption key (it's still blinded).
  • If Bob gets the blinded decryption key, he can unblind it, then use it to decrypt the encrypted signature for his payout.
  • Then Bob broadcasts his payout to the blockchain, receiving 1 coin. This transaction is completely separate from Alice's pay-in.

Now let's go through the pieces that need explaining:

Escrow transactions

The escrow transactions have a high-level logic like this:

IF: time is past refund time: allow spends back to escrow creator
ELSE IF: correct hash preimages provided: allow spend to the receiver.

or:

IF: time is past refund time: allow spends back to escrow creator
ELSE IF: transaction is signed by 2 of 2 (creator, receiver)

Basically in this kind of escrow, you commit the funds by actually spending into an address that is redeemed by a Bitcoin script like (one of) the above; you can be safe in the knowledge that if your counterparty disappears, or you choose not to pay, you can just grab the coins back any time after the expiry of the "refund time" (implemented using Bitcoin's OP_CHECKLOCKTIME_VERIFY in TumbleBit). On the other hand, the "other guy" (which could be one of the T or Bob in the high-level description above) can take the money if certain conditions are fulfilled. You can see that an escrow transaction in itself is not enough for "trustless" exchange, but it takes a key role in setting that up.

Technical detail - Bitcoin scripts:

For reference, here is the Bitcoin Script used in Tumblebit for one such transaction, on Alice's side; feel free to ignore it if you're not au fait with Bitcoin Script:

OP_IF
OP_RIPEMD160 h1 OP_EQUALVERIFY
...
OP_RIPEMD160 h15 OP_EQUALVERIFY
T_pubkey
OP_CHECKSIG
OP_ELSE
locktime
OP_CHECKLOCKTIMEVERIFY
OP_DROP
alice_pubkey
OP_CHECKSIG

Since these redeem scripts are large (see the h1 .. h15 - that's 15x20 byte hashes), they are encapsulated in P2SH addresses

A successful redemption would be revealing the hash preimages, looking something like this:

OP_0 signature OP_TRUE preimage1 ... preimage15

The OP_TRUE here tells the script to check the first "IF" condition.

Blinding

RSA is the oldest of the standard asymmetric cryptographic algorithms, and still in use today. It has a fundamental malleability, which is in many ways a weakness, but also is useful. Consider that RSA encryption and decryption operations are just a matter of exponentiation: \(E = m^{e}\ \textrm{mod} N\). Here \(m\) is the message to be encrypted, \(e, N\) is the public key and \(E\) is the result; just replace \(e\) with \(d\), where \(d\) is the private/secret key, for decryption.

Such a simple mathematical structure is termed "malleable" because \(E(m_1) \times E(m_2) = E(m_1 \times m_2)\). Whilst this can result in terrible security problems (see e.g. textbookRSA, along with much more advanced variations on the theme), it also creates useful functionality, the most striking example of which is perhaps the idea of the blind signature, first put forward by David Chaum. (Side note: in RSA, signing is basically the same as decryption, i.e. raising a hash to the exponent \(d\) but let's not get lost in the details). A blind signature is allows a central authority to sign data which is hidden from them; although superficially that sounds terrible, it can work well in systems where a user has data (A, B) where A can be verified by the authority while B can be kept private.

Chaum quickly applied the idea to digital cash, and indeed the whole story of "cryptographic money" seems to mostly start with Chaum's ideas, generally called "Chaumian cash", with a central mint authorised to blind-sign transfers of this cash, thus keeping privacy for the user. This crystallised in digicash in the 1990s (which then famously blew up at least partly due to its centralized model).

This same RSA blinding mechanism can also be used in an encryption, rather than a signing context. Just "compose" encryption with a blinding factor: take an message \(m\), and "blind" it with a random number \(r\), then encrypt it; you get \(E_b = (m r)^{e}\ \textrm{mod}N\), which due to malleability is the same as \(E(m) \times E(r)\). Interestingly (as this will be very important), you don't have to be the owner of the original message to do the blinding: if you're given \(E(m)\) but don't know \(m\), you can still blind it by encrypting your blinding factor with the public key and simply multiplying to get \(E_b\) without first knowing the message.

How it's used here

This allows you to delink the encryption and decryption operation performed by a central server \(T\), whose public key you are using. Bob may have \(E(m)\), and wants to know \(m\) but doesn't want to reveal which \(m\) he is decrypting.  So he simply generates a random \(r\), and blinds his encrypted message with \(E(r)\) and passes that blinded encryption to \(T\). What \(T\) would pass back as the decryption is \(mr\), and since \(r\) is random, \(T\) gets no information about what he's decrypting. To get \(m\), Bob of course simply divides the result by \(r\) (unlike factoring or root taking, division is not a problem in modular arithmetic, you use the Extended Euclidean Algorithm or similar).

In TumbleBit we go further, though: Bob doesn't directly ask \(T\) for the decryption - after first blinding as above, he passes the blinded encrypted value to Alice. It's Alice who then requests the decryption, in "fair exchange" for her payment (see more on this below), and passes back the still blinded decryption \(mr\) to Bob, who then unblinds as before. Introducing this intermediary doesn't create additional problems, but makes it possible for Bob to receive his decryption without revealing what it was a decryption of, which is neat.

This is the idea that TumbleBit uses to achieve unlinkable payments;  in principle the TumbleBit server has no idea who paid who.

Fair Exchange

This is the most important part of the system, and so I'm going to make an effort to explain it in some detail. At a very high level, it's using commitments - I promise to have X data, by passing over a hashed or encrypted version, but I'm not yet giving it to you - and interactivity - two-way messaging, in particular allowing commitments to occur in both directions. Folded in is the idea of "cut and choose" (see the paper for references) which makes cheating not literally impossible but vanishingly improbable to achieve successfully.

The Puzzle Promise Protocol

You, Bob, want Thomas the tumbler to sign a transaction that pays you money, but you don't want him to know which transaction he's signing. Sounds impossible to do securely for both sides, right?

A brief refresher on how signing works: a transaction is a long list of bytes in a special format, including inputs, outputs and other sundry information. When we ECDSA-sign, in order to authorize the transaction on the whole Bitcoin network, we (and this is true for all kinds of digital signatures) don't literally sign the message - in this case the full transaction - but instead sign a hash of it (in Bitcoin it's double-SHA256, but we'll just call it \(H()\)).

Here's what you do:

  • Bob and Thomas set up an escrow transaction: Thomas puts 1 coin into escrow, redeemable either after a timeout or with the signature of both Bob and Thomas attached. Bob will need this to construct his redeeming transaction, so Thomas passes this transaction across without yet broadcasting it.
  • You set up a list of "fake" transaction hashes. These will be hashes of FIXED_STRING_FOR_ALL_FAKES123456, where the string is what is says, and the numbers represent some random bytes, different for every case. This list will be long e.g. there will be 42 of them in the current proposal for TumbleBit. The purpose of the random data is to make sure the output of \(H\) is unpredictable (this is called the "hiding" property of a commitment). Call this list \(FH\), fake hashes.
  • Then, we set up a list of "real" transaction hashes (again, 42 in this particular case); they will all be the same, that's to say, hashes of valid spending transactions, paying me, Bob, 1 BTC, out from one of the escrow type transactions mentioned above. Each one will be random because each one will have a new, freshly generated Bitcoin address as the receiving address, so we again get the "hiding" property here. ECDSA signatures of these hashes will actually authorize spending on the Bitcoin network. Call this list \(RH\), real hashes.
  • Next, you take these two lists and join them into one list, with the order completely jumbled up. Send the scrambled list over to Thomas. You're sending: \(RH_{11}, FH_{7}, FH_{41}, RH_{32}, \ldots\). (side note: he also sends a commitment to the positions in the list which are fakes/reals, but we'll skip this).
  • Thomas then ECDSA-signs all of them. At this stage he doesn't know which signatures he's just generated will be real transactions and which not. He's certainly not just going to send the signatures back to you - since then you can spend the ones you know are real, for free! Note that he couldn't figure out which were real from examining the hashes - remember, you used completely random output addresses, so at the moment he just knows he has some ECDSA signatures, all valid, some of which which would be spendable, some not. He can't just check on his Bitcoin node; to broadcast a transaction, you need the actual transaction itself, not just the signature(s)!
  • Next, Thomas encrypts each of these signatures with a unique encryption key. Here he can just use ordinary symmetric encryption, more specifically he can XOR each signature with a randomly generated key (but forget the details - just encrypts with a secret key only he knows), which we'll call \(\epsilon_i\) where \(i\) runs over the length of the list, in this case from 1 to 84. And we'll call the encrypted signatures \(c_i\). Next, Thomas will RSA-encrypt all the secret keys and make a similar list: \(z_i = \textrm{RSA}(\epsilon_i)\).
  • Thomas will send the list of pairs \(c_i, z_i\) back to Bob at this point. Note how both those values are encrypted (although differently), so Bob has zero information at this point.
  • Bob will now do a "reveal" step: he tells which 42 out of the 84 he originally sent, were the fakes (he remembered the indexes in his jumbled list, e.g. in the example above index 2 (\(FH_7\)) was a fake). To allow Thomas to verify that they were indeed fake, he sends the specific random "hiding" bytes he used for each fake entry (shown with the "123456" placeholder above).
  • Given this revelation, Thomas can verify Bob's honesty: he can go through each identified fake commitment and perform \(H(\textrm{FIXED_STRING_FOR_ALL_FAKES}||r_i)\) where \(r_i\) is the random padding for that specific fake in the set. This hash should match the one he was originally sent, otherwise Bob didn't follow protocol and is dropped.
  • Here's the cool thing: because Thomas now knows those entries were fake, he can safely reveal to Bob the decryptions specifically for the now recognized fakes. This is the bit that forced him to honestly and properly ECDSA-sign all the original hashes. If he had selectively mis-signed some of the original set of hashes, he would be relying on probability to "luck out" that the ones he didn't sign properly didn't appear in this list. But probability really works against this kind of fraud, as long as the lists of fakes and reals are long enough: the probability of successful cheating by luck is actually \(\frac{1}{\binom{84}{42}}\), which gives a chance of success of \(\simeq 2^{-80}\), or 80 bit security to put it another way.
  • So assuming he acted honestly, Thomas can send across the \(\epsilon_i\) secret keys for those fakes. Bob then validates: first, he checks that \(z_i = \textrm{RSA}(\epsilon_i)\). Then, he checks that the signature he gets by decrypting \(c_i\) using that decrypted secret key, validates (he just uses some Bitcoin software for example to do the ECDSA-secp256k1 verification on that signature). He does this for every now-known-to-be-fake entry in his list, so 42 times. If any of these checks fail, he aborts, as Thomas was not following protocol.
  • Bob now knows with 80 bit security that the remaining 42 encrypted signatures he possesses are what they claim to be, and the same for the RSA-encrypted secret keys (\(z_i\)) that would unlock those signatures.
  • Thomas broadcasts the escrow transaction now; he knows that Bob will be able to spend out of it if all goes well in the next step, otherwise he (Thomas) will just get the funds back after timeout.

You might be wondering what gives with having 42 separate valid real transactions (with as-yet un-decrypted signatures to go with them). This is an issue in two senses - 1, we only want Bob to be able to spend once, but Bitcoin itself, combined with Thomas the tumbler using different public keys for each instance of the protocol, handles the potential double-spend issue, and 2 - for the next step we want Bob to be requesting a decryption of just one RSA-encrypted key; this part is handled using what is called an "RSA Quotient test"; for "brevity" (hah!), I will omit this, but the details are in the paper.

So how does Bob get hold of at least one of those secret keys (\(\epsilon_i\)) that would enable him to decrypt the signature and broadcast his transaction? He asks Alice!

The Puzzle-Solver protocol

  • Bob sends Alice his \(z_1\). First, note this can be on a "side-channel"; Thomas need know nothing about which Bob talks to which Alice. Second, he doesn't directly send his \(z_1\); he uses blinding! He sends \(y = z_1 \times \textrm{RSA}(r_1)\), so he knows that (if/when) he gets the decryption back, he can unblind it, and neither Alice nor, more crucially, Thomas need know what exactly he was decrypting (see the above section on RSA blinding).
  • Alice's next set of steps is very similar to what Bob did before:
  • Make a list of 15 real puzzles: \(d_i = y \times \textrm{RSA}(r_i)\) where the \(r_i\)s are random; note here we're not hashing, but making RSA encryptions, but just as before we have to "hide" by appending random data.
  • Make a list of 285 fake puzzles: \(\delta_i = \textrm{RSA}(\rho_i)\), the \(\rho_i\) again being random. The reason for the strange numbers (15, 285) instead of (42, 42) will be explained at the end (see note 1).
  • As before, Alice scrambles the lists and sends to Thomas, remembering which were real and which fake.
  • As before, Thomas does the "real" job in secret: in this case, instead of ECDSA-signing something, he's RSA-decrypting all the values sent to him, using the RSA private key which only he possesses. Call these decryptions (the thing Alice wants) \(s_i\), where \(i\) runs from 1 to 300. For each of these, he chooses a new secret symmetric encryption key and encrypts the \(s_i\)s to get \(c_i\)s. He also makes hashes of the secret keys, \(h_i\).
  • Thomas sends the list of pairs \(c_i, h_i\) to Alice. As before, he's now bound to these decryptions, without revealing them to Alice.
  • As before, Alice tells Thomas which 285 of the provided 300 were fakes; she sends him the values \(\rho_i\) from above. Thomas checks that, for the specified indices in the list, \(\textrm{RSA}(\rho_i)=\delta_i\) (excuse a slight abuse of notation, of course Thomas had no distinction originally between \(d_i\) and \(\delta_i\)). This part is unobvious but really important: it checks that Thomas is not going to unwittingly give Alice decryptions as part of the fake set, after which she could abort the remaining steps and get those decryptions for free. Because Alice was able to provide the pre-encrypted \(\rho_i\) in its entirety, she already knew the decryption, and it can't have been either \(y\) or \(y \times \textrm{RSA}(r_i)\) (a blinded value).
  • Thomas, now knowing the fake set, as before, "reveals" the solutions for the fake set: he sends to Alice the secret keys used to encrypt the solutions.
  • Alice takes each \(c_i\) in the fake set, uses the provided secret keys to decrypt them to \(s_i\) and verifies that they are equal to \(\textrm{RSA}(\rho_i)\) in each case. She also verifies that \(h_i\) is the hash of that secret key. Now she has the same kind of probabilistic certainty of honest behaviour from Thomas that Bob had in the puzzle-promise protocol.
  • Alice now posts a transaction of exactly the form described in the "Escrow transaction" section above - it pays out either back to her after a timeout, or to Thomas if he provides in the redeeming transaction, the preimages of the hashes \(h_i\) for all 15 in the "real" set (but remember their position in the original list was jumbled).
  • Alice then is ready to transfer to Thomas the actual blinded puzzle itself: \(y\), as well as the random pads/blinds \(r_i\) for 1 to 15 in the real set.
  • Thomas verifies that \(d_i = y \times \textrm{RSA}(r_i)\). He can then broadcast a transaction redeeming 1 coin using the 15 hash preimages (what is called above "secret keys"), which will then be visible on the blockchain.
  • Alice, on seeing this transaction on the blockchain, picks up the hash preimages, and uses them to decrypt to obtain the RSA decryption of \(y\): From \(c_i\), use the secret key to decrypt to \(s_i\), then divide by \(r_i\) to get the RSA decryption of y. (see note 2)
  • Alice can now pay Bob by passing over the decrypted value (in the simplest model, remember, Alice = Bob); he divides by the blinding factor he used to get the original decryption key \(\epsilon_1\), which he knows from the Puzzle-Promise protocol he can use to obtain a valid ECDSA signature on his redeeming transaction, which he then broadcasts. Done!

Notes:

  1. Why 15/285? This is because the key transaction at the end, in which Thomas broadcasts the hash preimages, which are secret keys, for Alice to read, must be valid on the Bitcoin blockchain, and it cannot contain hundreds of secret key values; for 128 bit keys, 16 bytes are used per key, so 15 of these requires 240 bytes; if the number was much larger, it would not be feasible. So to ensure 80 bit security, we need \(1/\binom{m+n}{n} \simeq 2^{-80}\), and if \(n=15\), this means \(m\) must be much larger, around 285 here.
  2. Note that it's vital he checks that \(y\) is the same for all the "real" cases; otherwise he could be unwittingly providing more than one puzzle solution to Alice for only 1 coin! As mentioned earlier, Alice cannot "cheat" this because she is unable to create RSA encryptions, even with blinding, without knowing the original message (a bit like the inability to create hash preimages).

Final thoughts - privacy, scalability, practicality

  • RSA operations are notoriously expensive; for a classic tumbler I can't imagine a realistic scenario where this will matter. It might matter for a payments hub model in which a lot of (especially off-blockchain) transaction events are happening; the paper gives some performance data on this.
  • The classic tumbler model assumes fixed denominations; I doubt that this could be avoided in such a model, although I haven't thought about it much. The effect of things like 800 in - 800 out transaction sets of fixed size, and with proper delinkage, is so powerful though, and combined with the centralization-for-coordination-but-not-requiring-trust, might well mean that this problem is offset. One could imagine just doing a "mix" of a fixed chunk of one's funds at regular intervals, for example. But more on "coordination":
  • The paper asserts that TumbleBit requires "no coordination" (Table 1) in contrast to other models requiring peer-to-peer coordination. This is true in one sense, but I think a little misleading, since all parties have to agree on an amount size and a time to do the mix - not with each other, but with the TumbleBit server. This is in contrast to Joinmarket, where amounts are set by the user of the service, and liquidity is provided by passive waiting ("Makers") by those who expect to be rewarded for that. I think the balance is in TumbleBit's favour, compared to Joinmarket and other Coinjoin coordinating protocols, but the proof of the pudding is in the eating!
  • Scalability: can be considered in two contexts: in the context of mixing in particular, this is potentially a huge win over other untrusted models, like Coinjoin, where Bitcoin transaction size limits a set of counterparties to 10-20 realistically. This is a gain of 1-2 orders of magnitude. For the general use of Bitcoin scalability, it might be a model that helps but only in the same sense as other payment channel solutions, so again, I'm keeping that out of scope.
  • Network level anonymisation: Alice and Bob will likely be one person in a classic tumbler mode, so if that's the case, it's important that the roles "Alice" and "Bob" are not just dumbly coming over the same naked IP address, since then we lose the property of "unlinkability to the tumbler server". Theoretically this is just a detail, but it might be important to consider in practice, from a usability perspective.
  • When trying to achieve privacy you need to avoid both amount- and timing- correlation. The amount- part is implicit in the current scheme; the timing part should be OK too; the pay-ins on Alice's side and the pay-outs on Bob's side are separate, so I suspect with a little bit of design care one can avoid the situation where the same party acting as Alice and Bob is acting at the "same" time in such a distinguishable way that one could easily see who is acting as Alice_1 and Bob_1, so to speak.

Current rating: 5

Comments

Adlai Chandrasekhar 10 months, 3 weeks ago

CoinJoin's participation set is limited for a single transaction, which is why JoinMarket provides a tumbler option which does multiple joins over a long time period. Greg Maxwell has analogized (https://bitcointalk.org/index.php?topic=997891.0) the graph created by multiple coinjoins to a CLOS network[1], which could have an arbitrarily large mapping of inputs to outputs despite each node having a fixed size, by simply increasing the number of nodes and layers.

[1] https://en.wikipedia.org/wiki/Clos_network

Link | Reply
Currently unrated

Adam Gibson 10 months, 3 weeks ago

Yup, good point, and I only didn't mention it inasmuch as there was too much stuff to go in here. There's a meaningful cost in using this approach though, as we observe directly in JM.

Link | Reply
Currently unrated

New Comment

required

required (not published)

optional