Random pad in "real" T_cashout

[osagga]

Random padding in "real" T_cashout

In theory (from the TumbleBit paper)

(step two of the Promise Protocol, page 13)

In the figure above, Bob is expected to generate the "real" cashout transactions using a "random pad" that provides entropy and randomness to the cashout transaction such that every hash of a "real" cashout is different than the other one.

The size of the random pad λ acts as a security parameter (according to the security proof on page 25-26) against the Tumbler being able to identify the fake set F (before Bob reveals the fake hashes in step 6).

If the Tumbler is able to distinguish the fake hashes from the real ones before sending the puzzles to Bob (step 5 of the protocol), then the Tumbler can give corrupted puzzles corresponding to the real set, and valid puzzles to the fake set. Therefore, Bob will not be able to spend the escrowed transaction (and it would be to late for Alice to not pay the Tumbler for the solution of the corrupted puzzle).

In implementation

In all of the TumbleBit implementations I have looked at so far (NTumbleBit and the Reference implementation), the size of the random pad λ used is really small such that the Tumbler can "easily" identify the fake set.

In NTumbleBit

https://github.com/osagga/NTumbleBit/blob/e1a01bf121cf490e72e215c7907194a7ff65fb89/NTumbleBit/PuzzlePromise/PromiseClientSession.cs#L257-L262

Each real cashout transaction has a field called "FeeVariation" that holds the value i. Then just before we hash the "real" cashout transaction, we form the T_cashout as follows:

https://github.com/osagga/NTumbleBit/blob/e1a01bf121cf490e72e215c7907194a7ff65fb89/NTumbleBit/PuzzlePromise/PromiseClientSession.cs#L63-L68

When generating the T_cashout, Bob subtracts i satochies from his output (in T_cashout). i here is the number of this specific "real" cashout transaction. For example, the first "real" cashout transaction will have i = 0 . Similarly, for the last "real" cashout transaction, i will be whatever the total number of "real" cashout transactions is (in NTumbleBit, the default number of real cashout transactions is 42 [1]), so i = 41.

Subtracting i from the output increases the fee that the miners will get when confirming the cashout transaction. Hence, this value is called "FeeVariation".

In Reference Implementation

A similar approach is taken, but instead of modifying the fee, Bob manipulates the sequence number that the cashout transaction has

        # Prepare reals
        self.reals = []      # hashes
        self.real_txs = []   # tx's in serial form
        for i in range(self.m):
            tx, sighash = get_unsigned_tx(funding_tx, redeem_script,
                          out_address, amount, n_sequence=i)
            self.reals.append(sighash)
            self.real_txs.append(tx)

(https://github.com/BUSEC/TumbleBit/blob/55829dc75c36554e710e723dedb510d62a57ca0c/reference_implementation/tumblebit/puzzle_promise.py#L251-L258)

As we can see, i is being passed as the sequence number. Therefore, the range of values the sequence number has are still within the same range as the total number of real transactions.

[osagga]

This attack will not quite work since the Tumbler cant construct the "real" cashout transaction without the destination wallet address of Bob.

In TumbleBit, Bob should always use ephemeral addresses when tumbling (check section IV of the TumbleBit paper). Therefore, assuming there's no way for the Tumbler to predict the wallet destination address for Bob besides brute forcing over the address space (2^160 in BTC), this attack is not "easy" and rather requires a lot of hardware power.

But I should also note that once the Tumbler finds the wallet address, identifying the fake set is rather "easy" as mentioned above. However, if the random pad was long "enough", then just finding the wallet address of Bob is not enough for the Tumbler to identify the fake set, the Tumbler would still need to find all the random pads that were used.

So overall, both implementation got away with using a short random pad and instead relied on the security provided by using an ephemeral wallet address. However, using a long random pad will still provide additional security in case there exists a faster way to predict wallet addresses than brute forcing over the address space.

[goldbe]

Yes, I agree. Actually now that you say this I remember going through this exact analysis about the emphemeral key resulting in enough randomness about a year ago. This should probably be documented somewhere in the ntumblebit repository so that others can avoid working through this again - is there a wiki page or some docs you can add to the repo??

[osagga]

Yes NTumbleBit has a wiki page (here), I'll try to add this report there. Thanks!

[osagga]

I have just added the report above to the NTumbleBit wiki here. Feel free to close this issue if you don't have any comments on the wiki page. Thanks!