Dismantle MimbleWimble's privacy magic (part I)

First, how does MimbleWimble come

The development process of MimbleWimble is a bit similar to Bitcoin. It is the result of a long-awaited start, that is, a certain topic, or a certain kind of discussion has been discussed for a long time. Finally, there is a person or a paper, and the total amount of the paper is on the way. The research results are combined into a set of operational protocols: before the advent of Bitcoin, many people discussed decentralized e-cash, such as Wei Dai; and Adam Beck developed "Hash Cash" HashCash, as well as time stamps. (timestamp), public and private key research results, plus Satoshi's breakthrough in the consensus algorithm – Nakamoto Consensus, and bitcoin; before the MimbleWimble agreement, in fact, many members of the Bitcoin core development organization, I started to think that Bitcoin did achieve "peer-to-peer cash transactions," but it was not enough to maintain the privacy of peer-to-peer transactions. Many researchers have been able to graphically analyze one or more from transaction graphs and web crawlers. The historical transaction of the account, and who is close to the precise speculative trader or group. Therefore, in the bitcoin transaction, the characteristics of the transaction account, transaction amount and transaction traceability will threaten the transaction anonymity, and the traceability of the transaction itself makes the currency itself not fungic. The characteristics of being criticized by people.

Therefore, in the bitcoin core community BitcoinCore, many people have proposed various agreements or new methods to promote the privacy of Bitcoin, but they are more like the nature of individual projects, not one. A blockchain system that immediately allows a currency to be used directly. Until one day, in the IRC (Internet Relay Chat) channel of bitcoin, there is a bit named Tom Elvis Jedusor (French version of the Buddha), through the Tor network put a txt file, which is commonly known as In the white paper, he named a protocol called MimbleWimble (the spell of the tongue in Harry Potter, you can't say anything~~), and speculates, through ConfidentialTransactions (confidential trading, CT), CoinJoin, One-way aggregate signatures (OWAS), etc. can complete the "private transaction" and process the data through the cut-through method to increase the "state growth problem". After he left the white paper called MimbleWimble, he evaporated. However, his white paper still left a lot of problems, and there is no perfect mathematics to prove the feasibility of his idea. It was finally made by Andrew Poelstra of BlockStream. The article is perfect and a more complete version of the paper is presented. (Right, BlockStream will be seen all the time. Without this company, I don’t think there will be a MW agreement).

So overall, MimbleWimble is a group of experts and enthusiasts who have long been concerned about privacy issues in the Bitcoin community. They are constantly proposing various improvements. Finally, some people have integrated these methods and have been verified. The process of constructing bitcoin is somewhat similar, but he is a protocol, and the actual implementation must wait until Grin and BEAM are two private cryptocurrencies.

• Lightning Network (on)|How to break through the ternary impossible: Re-implement the principle of lightning network technology with Solidity language
• V God personally wrote an article explaining the US Treasury’s Encrypted Assets Supervision Act
• Twitter Featured: Facebook Encryption Project Launched This Month; Wu Jihan will launch a new company Matrix by the end of July

From Bitcoin transactions, you can analyze the individual groups and why

Transaction map presented by a bitcoin account in R language

Second, deconstruct the three major parts of MimbleWimble

Mimblewimble is a Transformer assembled from many parts. I will introduce in this chapter how the various parts of MW work to complete the agreement. According to the agreement, I think MW's private currency trading has three trading characteristics.

1. No transaction amount

2. No transaction address

3. In one block, multiple transactions are merged, there is no way to see the details of each single transaction.

To accomplish this feature: you must have three large parts separately:

1.Confidential Transactions (secret transaction, referred to as CT)

2.CoinJoin (coin trading)

3. One-way Aggregate Signatures (OWAS)

Through these three important major agreements, the privacy transaction is completed, and finally, through Cut-through, it responds to the accumulated problem of the accumulated chain status. This is also the privacy of MimbleWimble which still needs to store many status data than Zcash and Monero. The currency is also excellent.

Since he is a blockchain protocol created specifically for privacy coins, let's first introduce the contents of a block:

1. The merkle tree of transaction input and range proofs encrypted by ECDSA

2. Merck tree with EDSSA encrypted transaction output and range proof

3. Trading kernel: a residual value of excess value (s) and the kernel offsets of the sum, mining costs.

4. Block head, block height

In fact, it should be seen here that there are structural differences between the MW and other blockchain blocks, and here too, all the parts of MimbleWimble are deconstructed:

1, ConfidentialTransactions confidential transactions

First, introduce the Confidential Transactions (hereinafter referred to as CT). CT was originally introduced by Blockstream's Adam Back. The addition of the "additional homomorphism" was generated in the bitcoin transaction. Later, this method was issued by Gregory Maxwell in the name of Confidential Transactions. The anonymous Fodi was added to the MW agreement. His most basic concept is to encrypt the transaction output and transaction output in any protocol in an elliptical curve.

So in MimbleWimble, each transaction input and transaction output is written in the form of Pedersen Commitment:

As written above, we can know that C (Pedersen Commitment, Pedersen may be from TPPedersen's paper) is a value generated by the transaction amount v by ECDSA (Elliptic Curve Digital Signature Algorithm, ECDSA). This value is well known. However, the input value seen through the elliptic curve will no longer be a simple amount. I will divide the above formula into the following three points:

1. r is the so-called blinding factor (blinding_factor), used as a private key, can not be known by anyone else, this private key also represents your ownership of this transaction value.

2. G and H are two points on the elliptic curve, and r*G is the public key of r on G. We can't know the r value through r*G. This is the so-called discrete logarithm. The problem, we don't know the private key because we know the public key. Remember not to confuse the multiplication here with the simple multiplication of 5*6=30.

3. v is the amount of the transaction, only the other party to the transaction will know, but the miners and others will not know. Here the elliptic curve ensures one thing, the transaction amount v and the blinding factor r are not known by means of a reverse push.

Now that you know how the deal looks, we will quickly see how we can get the deal verified.

1-1, the magic of hidden transaction amount: Additively Homomorphic

In MimbleWimble, every transaction still follows the concept of UTXO (Unspent Transaction Output). If you know a bit about Bitcoin, you should still have the impression. When we say that a user’s wallet “receives” bitcoin, it means that the wallet is found. A UTXO that can be spent using the key controlled by the wallet, you can simplify it to input=output. Suppose today that in your Bitcoin transaction, your account has 10 BTC, you use 7BTC for the seller, and 3BTC is for change (in order to simplify the first transaction).

  Input 1 (10) = output 1 (7) + output 2 (3) 

However, today we are in the MW transaction, the amount can not be known by outsiders, this time the transaction still has to follow the form of V1 + V2 = V3, this time homomorphic encryption (HomomorphicEncryption) comes in handy, obeyed in CT It is only the additively homomorphic in homomorphic encryption. The meaning of addition homomorphism is to encrypt and then add = first add and then encrypt, so we can see that the evolution of the equation is as follows:

  V1+V2=V3
 => V1*H+V2*H=(V1+V2)*H=V3*H 

At this time, the nature of the addition homomorphism subtly verifies that one thing is that we don't need to know the original v1 and v2, and the value of v3, just need to know V1*H+V2*H=V3*H to verify V1+v2=v3, so he can successfully hide the transaction amount.

But there is another problem here. How do we prevent the other party of the transaction and the subsequent verifier from knowing my private key in the case of input=output, and at the same time let them verify that I know the private key?

Maybe after reading you, you don't necessarily know where the problem is. Let's take a look at this question first:

Today Alice assumes that there are 24 coins and the blinding factor is 81, then his Pedersen Commitment will be

  81*G+24*H 

If Alice passes Bob to the number 7 of coins, then the formula will become (ps. Here we ignore the miners' fees)

  AB=(81*G + 24*H)-(81*G + 7*H)=0*G-17*H 

This will turn into saying that Bob will know that the blinding factor is 81, so your private key is exposed. So in a real MW transaction, you can't let this happen, or even the cost of your change may be taken away, so when Alice wants to trade with Bob, he must set up another one for the money he is looking for. Blindness factor, for example, we set another blinding factor to 8, remember that this 8 still can't let him know, and when you pass it to Bob, Bob will also specify a private key number (here assuming Bob's The blind factor is 23), although Bob will not know what your blinding factor is at this time, but we can use the characteristics of the two sides of the equation to subtract zero to verify the correctness of the difference between the blinding factors you give. . So the calculation at this time becomes like this:

  Alice(24)-Alice(17)-AlicetoBob(7)
 81*G+24*H-(8*G+17*H)-(23*G+7*H)=50*G+0*H 

At this time, the verified mining union received the remainder of 50*G. At this time, the excess value is 50, 50*G (remaining) and 50 (blinding factor difference) is just a public key. With the private key. (Remember that in this part of the transaction, there is no miner fee).

1-2. Avoid the magic of making excess money: Range Proof

Today we can confirm that the transaction amount can be hidden by the addition of homomorphism, and that the verified miners can verify that the transaction equations are equal on both sides, but there is still a problem that affects the validity of the transaction, even if If the two ends are equal, or the money that may be created out of thin air, it may be difficult to imagine at a time, then you can look at the following set of input and output equations:

Today's formula above also meets the conditions of input equal to output, but I can find that the original 5 blocks become 15 blocks, and the middle 10 blocks are because they are created out of thin air. And at this time, the negative number, corresponding to the elliptic curve may also be any value, so it will not be detected. At this time, another part was used in the confidential transaction, called RangeProof. RangeProof was first proposed by blockstream's Gregory Maxwell. Range Proof will be attached to each transaction input and output. With a simple zero-knowledge proof, you can ensure that you can prove each without knowing the amount. The single input and output are all a number of 0<x<2^64 to ensure that no additional amount is generated. However, the size of the zero-knowledge proof that must be attached to each input and output is larger than the transaction itself, and if the miner is to synchronize to the entire block, it must be verified from start to finish. The Range Proof of the transaction is verified, so the size of the Range Proof itself has become an object that must be improved. Therefore, Stanford student Benedikt Bünz later developed Bulletproof, which has a smaller capacity and a faster instruction cycle. The measured system size of the i7–6820HQ system is only 688 bytes, which was developed by Maxwell. The Range Proof, which has about 5kb, has a very large capacity improvement, but it is still very large compared to the difference of 33 bytes per transaction.

By now we can have a concept to understand how transactions that don't know the amount are validated:

1. The miner's addition homomorphism through PedersenCommitment ensures that the input and output of the equation are equal to the output without knowing the transaction amount.

2. Use RangeProof to determine if a transaction input or output that does not know the amount is indeed greater than zero to avoid creating new money out of thin air.

This article reprints the public number: Blockchain Research Laboratory

We will continue to update Blocking; if you have any questions or suggestions, please contact us!