MIMBLEWIMBLE: A way to improve Bitcoin transaction privacy

MIMBLEWIMBLE (A method to improve the privacy of Bitcoin transactions)

(Translator's note: Mimblewimble is a curse in Harry Potter)

Original author: Tom Elvis Jedusor

(Translator's note: This name is also the French name of Voldemort in Harry Potter, so it is speculated to be a pseudonym)

July 19, 2016

Translator: Huang Shiliang

August 19, 2016

introduce

Bitcoin is the first widely used financial system where anyone can access and verify all the necessary data about the system's state. It accomplishes this feat by storing all transaction data in a public database called the "blockchain," but anyone who actually wants to check the state of the system must download all the data and trace back every transaction. Also, most of these transactions do not affect its final actual state (each time they create an output, they destroy a previous transaction).

At the time of writing, the blockchain contains nearly 150 million transactions, which contains only 4 million unspent outputs that are recorded duplicated.

It would be better if the auditor only needed to check the output data itself, but this is impossible because an output is valid if and only if it is the last in a chain of "previous outputs", each of which is connected to the previous output. In other words, the entire blockchain must be fully verified before the final state can be confirmed.

Additionally, these transactions are “cryptographically atomic”, and it is clear what went into each transaction and what happened. The “transaction graph” leaks a lot of information, and there are many companies that specialize in analyzing transactions, whose business model is to regulate and control these layers of the market. This makes transactions very impersonal and even dangerous to users.

Several solutions have been proposed. Greg Maxwell discovered that encrypting transaction amounts can make transactions anonymous while still allowing others to verify that the amounts are correct. ^[1] Dr. Maxwell also created CoinJoin, a system that allows Bitcoin users to mix multiple transactions together, obfuscating the transactions. Nicolas van Saberhagen developed a system that can mask transaction inputs, further obfuscating the transactions (without mixing the coins). ^[3] Noether later combined these two methods to create "Maxwell's 'confidential transactions' and van Saberhagen's black box operations." ^[4]

These solutions are great, and they would make Bitcoin very secure to use. But the problem is that with large amounts of data, it gets worse. Confidential transactions require multi-byte proofs for each output, and van Saberhagen signatures require saving every output, so it's impossible to tell when a transaction was completed.

Dr. Maxwell’s CoinJoin already had the problem of requiring interaction. Dr. Yuan Horas Mouton solved this problem by making transactions freely mergeable ^[5] , but he needed to use pairing-based cryptography that potentially slowed down transactions, which was even more difficult to believe. He called this “One-Way Aggregate Signature” (OWAS).

One-way aggregate signatures are a great way to mix transactions in blocks. Imagine that we could mix transactions across blocks (and perhaps glue data) so that when an output is created and destroyed, it is the same as if it had never existed. Then, to verify the entire chain, users only need to know when money enters the system (new coins generated by the block reward of each block, either Monero, or Bitcoin for sidechain pegs ^[6] ) and when it finally becomes an unspent output; the rest can be moved and forgotten. Then, we can use confidential transactions to hide the amounts and one-way aggregate signatures, thereby obfuscating the transaction graph and allowing users to fully verify the blockchain using much less space (compared to the current Bitcoin blockchain). Imagine again that we don’t need to rely on pairing passwords or new conjectures, but just use ordinary hash signatures like Bitcoin. Here is my suggestion.

Because it is used to prevent the blockchain from leaking all the information of its users, I called my invention Mimblewimble ^[7] .

Confidential Transactions and One-Way Aggregate Signatures (OWAS)

The first thing we will do is remove Bitcoin Script. It sounds sad, but it is so powerful that mixing transactions using general script is impossible. We will show that Dr. Maxwell's confidential transactions (after some minor modifications) are sufficient to construct spends and even mix transactions without interaction. The same is true for One-Way Aggregate Signatures (OWAS), which allow relay nodes to charge some transaction fees or let recipients change transaction fees. We can implement these additional features that Bitcoin cannot achieve for free.

We first explain to the reader how confidential transactions work. First, the amount is encoded via the following equation:

C = r*G + v*H

Among them, C is a Pedersen commitment (Translator's note: From the context, C is the transaction amount encrypted by the ECDSA algorithm), G and H are fixed values ​​that are unrelated to the generation of the elliptic curve cryptographic function (ECDSA), v is the amount, and r is a secret random blinding key. ( Translator's note: This formula encrypts the transaction amount. For example, if the actual transaction amount is 1BTC , then v=1BTC . C is an amount obtained after encryption by the ECDSA algorithm to hide the actual amount. The two parameters G and H are also two values ​​generated by the ECDSA algorithm. r is similar to a password. Only when G , H and r are gathered together can v be derived from C. )

Associated with the output is a rangeproof, where v is in the range [0, 2^64], so users cannot crack it using brute force.

To verify a transaction, the validator will add all outputs, add f*H (f is the explicitly given transaction fee), and subtract all input fees. The result must be 0, which means that the overall transaction has not been generated or destroyed.

We note that to create this transaction, the user must know all the "commitments entries" The sum of r-values. Therefore, the r-values ​​(and their sum) can act as a key. If we can make the r-output value known only to the payee, we have an authentication system! Unfortunately, if we follow the rules, it is impossible for all "commits" to add up to 0, because the payee knows the sum of their r-values ​​and therefore knows that the payee's r-values ​​add up to a negative number. Therefore, we allow the transaction sum to be a non-zero value K * G, and require an empty string signature as the key to prove that the amount part is zero.

We let a transaction have as many K*G values ​​as it wishes, each with a signature, and add them up during verification.

When creating a transaction, the payer and payee of the transaction should follow the following rules:

1. The sender and the receiver agree on the transaction amount. This is called b.

2. The payee creates a transaction using all inputs, changes the outputs, and sends the “total blinding factor” (the change in r minus the input r) along with the transaction to the payee. So the total value of “commitments” is r*G – b*H.

3. The payee randomly chooses r as their output, and all values ​​add up to b minus the transaction fee, and then adds them all to the transaction (including the range of values). The total input is now k*G – fee*H, and only the payee knows k.

4. The payee will use k to sign and add it to the transaction, and give a clear fee. In this way, the entire transaction is completed.

Transactions created in this way now support one-way aggregate signatures (OWAS). To demonstrate, suppose we have two transactions, k1*G and k2*G, which have a surplus , and these are signed. Then, the inputs and outputs of the two transactions can be mixed, k1*G and k2*G are mixed with each other, and this becomes a valid transaction again. It is impossible to find the input and output values ​​in this mixed transaction to find the corresponding input and output in the original transaction

Because of this, we changed our Bitcoin block format to the following:

1. A clear amount of new currency (block rewards or bitcoins for sidechain pegs) and other required data. If a sidechain peg involves a transaction, does the transaction submit a specific k*G value? (Translator's note: This is indeed a question here, and the author may also be unsure about this.)

2. Inputs for all transactions.

3. Outputs of all transactions.

4. k*G value in all transactions.

Because it doesn't matter what the original transaction boundaries are, these are all mixed together. In addition, the values ​​in Listings 2, 3, and 4 should be in alphabetical order, because it allows for quick checking and prevents the creator of the block from leaking any of the original transaction information.

Note that we can identify outputs by their hash value, not their position in the transaction, so this can be easily changed. Therefore, to avoid confusion, it should be forbidden to have two identical unspent outputs at the same time.

Cross-block Mixed Transactions

Now we have used Dr. Maxwell’s Confidential Transactions to create a noninteractive version of Dr. Maxwell’s CoinJoin, but we haven’t seen the final miracle. He said we need another idea, namely, transaction cut-through ^[8] . Again , we create a noninteractive version and show how it works with a few blocks .

We can now imagine each block as one big transaction. To verify this, we take all the output commitments as a whole, and then subtract all the input commitments, the K*G value, and the number of times all explicit inputs are present H. We see that a new transaction can be mixed from two blocks, and when we mix the transactions within a single block, the result is a valid transaction. In addition, when the outputs from the first block are put into the second block, some of the output commitments are exactly equal to their input commitments. When we remove these two commitments, we still get a valid transaction. In fact, it is not necessary to check the rangeproof of the deleted output.

Extending this idea from the genesis block to the latest block, we can see that every non-explicit input has been deleted along with its associated output. What remains are the unspent outputs, the total amount of explicit inputs, and each K*G value. All of this data can be treated as a transaction: all unspent output commitments, subtract the K*G value, verify the total amount of explicit inputs (if there is anything to verify here), and then subtract their number of times H. If the sum is 0, it can be judged that the entire blockchain is correct.

What does this mean? When a user starts and downloads the entire blockchain, the following data is required for each block:

1. A clear amount of new coins (block rewards or sidechain anchor coins) and other required data.

2. All unspent outputs of a transaction will appear in the original block, along with a merkle proof of each output.

3. k*G value of all transactions.

Bitcoin now has about 423,000 blocks, which takes up 80GB of hard disk space. This data can verify all transactions. This data is 150 million transactions and 5 million unspent non-confidential output values. If the same amount of transactions is on the Mimblewinmble chain, let's estimate how much space it would take. Each unspent output requires 3Kb of space to store rangeproof and Merkle proof, and each transaction also takes 100 bytes to store: a K*G value and a signature. The block header and the explicit total amount can be ignored. All of this adds up to a total of 30GB - including all confidential transactions and the transaction graph of osmanthus cake!

Questions and intuition

In recent weeks, I have been having dreams about problems and always waking up in a cold sweat.

In fact, the situation is not bad.

Problem: If you delete the output of a transaction, users cannot verify the rangeproof and may end up with a negative amount.

Answer: This is not a problem. After verifying all transactions, it can be confirmed that all negative amounts will be offset. It is precisely because there has been no illegal inflation in the past that users can safely use SPV, knowing that there will be no inflation now.

Problem: If you delete the input, you will double spend.

Answer: In fact, this means that: there may be some people who claim that there are unspent outputs that have been spent before. But this is impossible, otherwise the total amount of the mixed transaction cannot be zero.

There is an exception. When the total output amount is zero, it is possible that the two outputs are opposite in positive and negative, and this pair of data can be used again. Therefore, in order to prevent consistency problems, transactions with a total output amount of 0 should be prohibited. Just add H to each output so that all amounts are at least 1.

Future research

Here are some questions I cannot answer at the time of this writing.

1. What kind of scripting support is there for this application? We need to convert the script operations into some form of discrete value information.

2. We need users to check all k*G values, and in fact all the data they need comes from k*G. Without using signatures, are there other discrete value proofs that can be mixed?

3. When a user downloads the blockchain, there is a denial of service option where the attacker will give byte data and provide the wrong unspent output. The user will see that the final sum is not equal to 0, but will not be able to find out what the problem is.

Now users may just download the blockchain from Torrent or from data shared by other users, in which case they should be able to obtain correct data.

(Translator's note: The docx and pdf versions of the translation can be downloaded from Baidu Netdisk: http://pan.baidu.com/s/1o8dEf7G Password: 7jes)

[[2]] https://bitcointalk.org/index.php?topic=279249.0[[2]]

Notes (↵ returns to text)

1. https://people.xiph.org/~greg/confidential_values.txt↵

2. https://cryptonote.org/whitepaper.pdf↵

3. https://eprint.iacr.org/2015/1098.pdf↵

4. https://download.wpsoftware.net/bitcoin/wizardry/horasyuanmouton-owas.pdf↵

5. http://blockstream.com/sidechains.pdf↵

6. http://fr.harrypotter.wikia.com/wiki/Sortilège_de_Langue_de_Plomb↵

7. https://bitcointalk.org/index.php?topic=281848.0↵