Hierarchical deterministic wallets with deniable encryption

Hierarchical deterministic wallets protect you from losing your bitcoins (or colored coins) accidentally: by storing encrypted backups of the single root of your wallet tree, you can later gain control of all the coins that you've ever received. See for example this short presentation.

However, there are other dangers beside accidental loss of your secret data. In particular, how will you protect yourself from a robber who threatens to harm you unless you decrypt your wallet file to let him steal your coins? The famous xkcd 538 cartoon describes a similar circumstance:

By using an hierarchical deterministic wallet, you can have a "hot" sub-tree where you maintain only a few coins for your daily transactions, so if for example the robber sees the wallet balance on your screen he will think that those are the only coins that you got. After you decrypt this sub-tree for the robber, the vast majority of your coins will remain safe.

Still, as we will see next, a savvy robber may examine the total size of your encrypted wallet data, infer that your hot sub-tree is a decoy, and try to force you to also decrypt your "cold" storage. Of course, to protect in advance against this scenario you can resort to the simple option of having a separate wallet file for cold storage, with the hope that the robber will be unaware of the separate file. But if you access your separate cold wallet with some frequency, you'll need to have a procedure to fetch and decrypt the cold wallet, so the robber may scan your other files or look for instructions that you prepared regarding cold storage access. For most people, keeping the cold storage as a totally obscure file that looks like junk is very risky, because they might delete it or forget how to use it.

Therefore, it is preferable to have an orderly solution that is safe for common people.

Users of encryption software such as TrueCrypt are probably familiar with the deniable encryption capability that enables having a decoy partition. The problem with it, as with the hot/cold wallet issue, is that the robber can see that the total amount of encrypted data is larger than the partition that you decrypted for him.

Maybe it is always possible to create a ciphertext with a decoy that is indistinguishable from a ciphertext without a decoy? Unfortunately, this cannot be done. Since it is simple enough to prove that it's impossible, let us provide a rigorous proof here (refer also to section 5 of this paper). As described in a bitcointalk post, the problem stems from the fact that symmetric encryption is highly efficient: the size of the encrypted data is the same as the size of the plain data. Suppose that you have two incompressible files f1 and f2 (i.e., files with high entropy) of same size. It is possible to encrypt f1 into a ciphertext c such that the sizes of f1 and c are the same. If you could create a ciphertext c0 of same size as f1 that can be decrypted into f1 by using the secret key k1 and can be decrypted into f2 by using another secret key k2, then you effectively compressed (f1,f2) into (c0,k1,k2). This is impossible because the key sizes do not depend on the file sizes but rather on a security parameter, for example you can use a 128-bit key to encrypt files of any size so that the encryption is unbreakable in less than ≈2^128 iterations. Therefore, we deduce that c0 must be larger than c, which completes the proof.

So the robber can distinguish between a user who creates both a decoy wallet hierarchy and a real wallet hierarchy, versus a user who creates only a real wallet hierarchy, because the encrypted data size of the first user will be larger.

To overcome this problem in a way that works well for ordinary people, my bitcointalk post above suggests the technique of encrypting junk data in popular wallet clients by default, so that even users who don't care about deniable encryption will have a wallet file that looks the same as wallets that do contain a decoy. Since the wallet data is just a collection of secret keys, what we're talking about here are small files of few dozens of kilobytes usually, so doubling the size is not much of a burden.

To protect against scenarios where the robber has a reason to suspect that the user did use deniable encryption, and therefore try to force the user to decrypt his decoy wallet, it might be preferable to concatenate some n<N ciphertexts of variable sizes, instead of two ciphertexts of equal size, where n is random and N is some fixed bound. This way, the attacker wouldn't even know how many decoy wallets are contained in the ciphertext.

Could there be even better ways to implement this kind of protection? Probably not. One suggestion is to store in your encrypted wallet file only master secret keys for root nodes of the hierarchical deterministic wallet, thereby not giving the robber any hints regarding what you're actually storing, as those secret keys are of a very small fixed size. However, you'll then need to re-scan your entire tree hierarchy every time that you view your wallet, e.g., to see if you received payments. In case the robber attacks you during the re-scan procedure, you'd be vulnerable. This is highly risky because the re-scan procedure is quite demanding, you cannot even be completely sure when to terminate the procedure because payments aren't necessarily in consecutive derived nodes (discussed for example at this bitcointalk post), and this uncertainty becomes aggravated in case the topology of your tree hierarchy is nonstandard. To add to that, if you wish to parse only the UTXO set instead of the entire blockchain from genesis, then you won't be able to list your transactions history (e.g., if you sent 20 BTC to Alice's address a month ago then you won't see that), and commonly people wouldn't want to lose this transactions history feature as they would otherwise can easily become confused regarding the status of their current balance. Therefore, this suggestion is inferior to storing the entire tree hierarchy of your wallet on disk with deniable encryption, so that you can type your real password and instantly gain access to your full wallet (and update it quickly in case your Bitcoin client already fetched the latest blocks), and then re-encrypt and thereby make your wallet instantly disappear without storing evidence that it ever existed. Moreover, an important objective is to protect people who aren't technically savvy, and requiring the re-scan procedure for normal usage is a bad idea because people would just leave their wallets loaded all the time in decrypted form, to avoid being bothered (similarly to people who attach sticky notes with passwords to their office computer screen because they've been asked to remember multiple passwords).

In addition to security against robbers, Bitcoin wallets with deniable encryption can also provide plausible deniability in the legal sense. For example, people who wish to gamble in places where it's unlawful, or make donations to illicit organizations, may prefer to conduct their financial activity under a deniable encryption layer.

The effect of colored coins on Bitcoin security

Right now, Bitcoin mining is still subsidized to a considerable degree, because newly minted coins comprise the vast majority of each block reward. When this initial distribution of the money supply subsides and becomes insignificant, the Bitcoin miners will earn their revenues from transaction fees.

For the Bitcoin network to be secure against an attacker who has a large amount of hashpower, the transaction fees should be high enough to make it lucrative for honest miners to participate in the mining process. When this is the case, there will be a suitable amount of honest mining power devoted to the security of the Bitcoin network, which would make external attacks more costly.

In the way that the Bitcoin network has been operating so far, the miners impose flat fees whose main purpose is to make it costly to attack Bitcoin by bloating the blockchain and UTXO set. Since the block reward subsidy (currently 25 BTC) is still much greater than the fees that the market can bear, miners don't care much for dealing with more involved transaction fees policies. In fact, there are miners who consider it financially lucrative to avoid validating the transaction data altogether. For example, see what happened with the BIP66 forks here and here (in this case SPV mining lead to a financial loss, a better strategy would be to validate the previous block after starting to solve the current block).

As long as the Bitcoin network continues to operate as it always has, meaning that miners impose only flat fees to counter blockchain bloat attacks, there isn't any particular difference between colored and uncolored transactions in relation to the security of the Bitcoin system.

However, the subsidy will be 0.78 BTC in less than 20 years, which means that in the not so distant future we will see miners impose transaction fees policies that maximize their profits. A useful policy is to demand fees that are proportional to the amount of BTC transacted, which would allow most people to do low-value transactions for a low fee, and collect more significant fees from high-value transactions.

What would then happen when colored coins transactions take place on the Bitcoin network?

When high-value colored coins are transacted on the Bitcoin network, it implies that the Bitcoin system has a higher value and therefore there are greater incentives to attack it. If the honest miners are unaware of this extra value and are not compensated for it, then the total amount of honest mining power will be derived according to a value that is lower than the actual value of the Bitcoin system. This would make Bitcoin prone to double-spending attacks.

To see that this is the case, consider the simple scenario where the miners impose a fixed flat fee per transaction, while the value that is being transferred in the transactions increases further and further. Here, the honest miners will continue to earn the same amount, while it becomes increasingly lucrative for an attacker to obtain hashpower that would be under her control. This is because the attacker could then spend her valuable (colored or uncolored) coins and receive other goods in return, and then utilize her hashpower to create a competing chain in which she double-spends those high-value coins back to herself.

The straightforward way to avoid this bad outcome is by having Bitcoin miners that aren't color-oblivious. This means that if a valuable colored asset is traded on public exchanges for a certain price, then the Bitcoin miners will recognize transactions that transfer this asset, and therefore demand a fee that is proportional to its price.

But what if the asset is traded in an inner circle that is inaccessible to the general public? The Bitcoin transaction may contain an encrypted message of this trade by using OP_RETURN to store arbitrary data. One may claim that secretive assets are likely to represent less value than publicly traded assets...

Worse still, the asset may be publicly traded, but the Bitcoin transaction will encode the transfer by using a time-lock encryption. Thus, individual miners would wish to collect the attached fee by adding this transaction to the current block that they try to solve, even though the content of transaction could be seen only later (e.g., in a few hours). Here too, one may try to argue that the value of such assets is likely to be lower than the value of real-time publicly traded assets.

So, should we conclude that Bitcoin miners can be forced into being color-oblivious, which would make them impose too low fees and thereby damage the security of Bitcoin? Not necessarily.

In fact, when you put unrecognizable trades inside arbitrary OP_RETURN (or bare multisig) data, it does not necessarily imply that you lower your fees this way. Instead, it may imply that you increase the fees of everyone else who incorporates OP_RETURN data into their transactions. How come? Miners may arrive at an informed decision regarding how to charge an appropriately high flat fee for all transactions that contain arbitrary data. One possible way to do it is as follows. The Bitcoin miners can adjust an estimate V as the total amount of value that is transmitted as OP_RETURN data in a given time window (for example two weeks), by having each solved block cast a vote for the value of V, and setting V as the average of the votes in the time window. The miners would then demand a fixed fee cV/N where c is a protocol constant and N estimates the number of OP_RETURN transaction in the time window. This would hurt those who wish transact a relatively low value via OP_RETURN encoding, but the Bitcoin miners on the whole will collect fees that are adequate for the security of the network. To avoid the tragedy of the commons (refer e.g. to Proof of Activity paper), Bitcoin nodes can deploy a hard protocol rule that considers blocks with arbitrary data but less than cV/N fee to be invalid.

Another point is that perhaps in the future tagging-based colored coins will be supported by the Bitcoin network, see e.g. this presentation for illustrations. This would mean that all of the Bitcoin full nodes (rather than only color-aware nodes) need to do a little extra work to verify that colored transactions are valid, thereby allowing lite clients (like mobile phones) to do color verifications efficiently. For ordinary/uncolored transactions, full nodes wouldn't need to do any extra work. Since inaccessible or time-encrypted colored transactions are incompatible with tagging-based support, this makes them less valuable.

Going forward, it is difficult to predict the total amount of hashpower that will be dedicated to securing the Bitcoin network. The current hashpower amount is quite high relative to the popularity of Bitcoin, hence double-spending attacks do not take place in the present. One possibility is that the added value that will be transacted on Bitcoin via colored coins remains low enough relative to the security threshold that honest miners will provide anyway. Else, as discussed above, there are technical proposals that the Bitcoin network can adopt to become more resilient to attacks that may occur as a result of this added value. In summary, colored coins don't present any immediate danger, but in case colored coins become highly popular they might put the security of Bitcoin at risk, thus requiring the Bitcoin network to incorporate modifications that would make it more robust.