The following transcripts are compiled from Fork It Issue 4Let’s Talk About MimbleWimble , in order to ensure the completeness of the reading, we took Zhang Ren as the first perspective, sorted out some of the content, and supplemented the technical details in the program (if there is any discrepancy with the content of the podcast, the content of this article shall prevail). In addition, various small details in the complete podcast program are also very interesting, please click the link to listen.

If you have other ideas about MimbleWimble, welcome to discuss with us in the comment area.

Finishing: Xiao Jie, Jin Xiaojia, Calibration: Wan Cenchen, Zhang Ren

Getting to know MimbleWimble

About two years ago, I discovered the MimbleWimble protocol. At that time, I thought it was very interesting and full of mystery.

This agreement is posted anonymously on Bitcoin's IRC Channel. The pseudonym author's name is Voldemort's name, and it is the name of Voldemort in the French version of "Harry Potter", called Tom Elvis Jedusor. The author put a Dot Onion in the Tor networkLinkofBlockstreamofAndrew PoelstraIn-depthResearch, which proves the security of the MimbleWimble system, is the real completion of this protocol. Therefore, the proposer of this agreement can take credit for Idea, and Andrew Poelstra should take half of the credit.

From the perspective of cryptographers, it is very unreasonable to store all transaction amounts in plain text on the blockchain. Moreover, it is also wasteful to store all the transactions that have been spent permanently on the hard disk to ensure the security of the protocol itself.

And MimbleWimble cleverly combined some previous designs to solve these two problems, giving people a very elegant feeling.

Define MimbleWimble¶

To understand MimbleWimble, you must first figure out its positioning,Its positioning is Privacy Coin, a cryptocurrency that can support privacy very well. I think there were only two Privacy Coins before MimbleWimble, one called Zcash and one called Monero. Others claiming to be Privacy Coin are not strong enough in technology.

But Zcash and Monero have the same problem: for their own privacy, they both need to maintain a set, which stores all transaction outputs that have been spent, and we can understand it as a "void list".

If you want to verify whether a new transaction is a valid transaction, you first need to check whether the transaction input of the new transaction is in the "void list". If the transaction input is already in the "void list", it proves that the transaction input has expired , and if it is not in the "void list", it proves that the transaction input is valid, the transaction will be recognized by the miners, and then the miners will put the transaction input into the "void list".

So for Zcash and Monero, they both face a very serious problem - the transaction output is always growing. If a public network full node wants to verify whether a new transaction is valid, it must store a complete set of transaction data. As the number of transactions accumulates, the amount of data will become larger and larger, and it will become very unfriendly to use.

The MimbleWimble protocol does not have this problem. It has better scalability than Zcash and Monero, and can cope with the problem of state growth.

For example, Grin Coin, which uses the MimbleWimble protocol, occupies very little hard disk space, and it can greatly compress the hard disk space occupied by spent transaction outputs.

If you simply delete the spent transaction output, then when verifying the validity of the block, you cannot verify whether the block is valid, nor can you verify the transaction signature. But this problem does not exist in the MimbleWimble protocol.

For MimbleWimble, after deleting the spent transaction output and the corresponding transaction input, the verification of the entire transaction graph is not affected at all, and all remaining signatures are still valid. And after deleting the transaction output that has been spent, the entire blockchain can still be verified by signature and workload.

You can simply understand that this is something like an Accumulator, which can compress many past cryptographic Proofs into a small proof, a bit like Merkle Tree, but it will be more efficient and performant than Merkle Tree.

3 misconceptions about MimbleWimble

Myth 1: Compressed space = better privacy?

Many people sell the feature of MimbleWimble's compressed hard disk storage space as better privacy, but in fact it does not achieve better privacy. If you choose to compress your hard disk space, and others choose not to compress, then they can still get a complete transaction graph, and they can dig out the transaction relationship of the transaction from it.

Of course, when deleting the hard disk storage space, it is still necessary to keep the original block data of the latest few days, because it is not known whether there will be forks, double-spend attacks, etc. When it is determined that the chain is long enough and the data will not be changed, the hard disk space that has been determined not to be changed can be compressed.

The full node in the network generally cuts the storage space by default, but the source code can also be modified so that it does not cut.

Myth 2: Can a single party disavow a transaction?

The MimbleWimble protocol has a feature that its transaction construction method is interactive, which means that a transaction must be completed with the participation of both parties, which is very different from Bitcoin and Ethereum.

Take Grin, which implements the MimbleWimble protocol, as an example. If I give the exchange a sum of money, and the exchange does not do anything, it will not receive the money. Only when it participates in the protocol that interacts with me and completes the legal transaction can it receive the money.

If it constructs this legal transaction with me, it proves that it knows the existence of this transaction, so if there is no exchange to give me money, I can say no. This is also a misunderstanding of MimbleWimble by the outside world.

Misunderstanding 3: Transactions require both parties to be online at the same time?

This interactive transaction does not require both parties to the transaction to be online, and both parties to the transaction can completely send emails to complete the transaction structure.

Some time ago, I went to see the wallet demo of Grin Conf. The wallet stores the intermediate data in the transaction construction process as a file. For the person who enters, he can generate a file, and then send this file to the recipient of the transaction. After the transaction receiver receives the file, he can drag the file to his wallet client, construct the entire transaction in the client, and then send it back to the sender of the transaction as a file to complete the transaction construction. Therefore, both parties are required to participate, but it does not mean that both parties need to be online at the same time, and it can be an asynchronous process.

MimbleWimble technical details

Now let me talk about the technical details of MimbleWimble in detail.

MimbleWimble has three basic components. The first basic component is called CT (Confidential Transaction), the second basic component is called Coin Join, and the third is called OWAS (One Way Aggregate Signatures).

What we just talked about is part of OWAS. Now I will simply give you a brief overview starting from CT. CT is the most complicated, and the remaining two are relatively simple.

Confidential Transaction

The idea of ​​CT was first proposed by Blockstream CEO Adam Back. Adam Back is known as the godfather of Bitcoin because he is the inventor of the mining algorithm Hashcash, and he was cited by Satoshi Nakamoto in the paper.

For a miner or public network node, they are most concerned about whether a certain transaction is a valid transaction, and the transaction does not cause inflation in the system (no new money is created, for example, the sender spends 50 bitcoins, and the recipient recipients received 50 instead of 51). Other than that, they don't care about the exact amount of the transaction.

So the original idea of ​​Confidential Transaction is whether the transaction amount can be converted into ciphertext, while ensuring that the validity of the transaction is not affected.

Gregory Maxwell is another Co-founder of Blockstream and one of the first five core developers of Bitcoin. He really designed such a protocol, which encrypts the amount of the transaction in a way, but does not affect the validity of the transaction at all. sex.

The protocol can express the input or output of each transaction in the following form: (also called Pedersen Commitment)

• v*G+r*H

(where v is the amount, r is a random number representing the blinding factor, G is generator 1, and H is generator 2)

This is also called blinding the transaction amount, and the "amount" of the transaction is easy to understand. Generator 1 and Generator 2 are the two generators of elliptic curve cryptography. Before multiplying a value by the generator, it is the plain text. After multiplying by the generator, you can understand it as a simple encrypted cipher arts. This operation is one-way. Although everyone knows what the generator is, once it has been multiplied, it cannot be reversed, and no one knows what the original plaintext is. This problem is called the "discrete logarithm problem."

The blinding factor is a random number selected by the constructor of the transaction input or output. This random number is only known to you and cannot be told to others.

The advantage of blinding each transaction amount is that it can keep "additive homomorphism”, the formula is as follows:

• （v1*G + r1*H）+（v2*G + r2*H）=（v1 + v2）*G+（r1 + r2)*H

(where v1 and v2 are transaction amount 1 and transaction amount 2, r1 and r2 are blinding factor 1 and blinding factor 2, G is generator 1, and H is generator 2)

To put it simply, adding an encrypted number is equivalent to adding an encrypted number before encrypting it.

The most important thing so far is to understand what additive homomorphism is, that is, add first and then encrypt, and encrypt first and then add, the results obtained by two different operation sequences are the same. A person who does not know the specific amount can still verify the validity of the transaction, and can verify that the sum of the two amounts is correct.

When we need to add a transaction fee to a transaction, it is handed over to the miners in plain text, and there is no need for additional complicated encryption and decryption operations on the transaction fee. The miners add f*G to the Pedersen Commitment of the transaction output to verify whether the Pedersen Commitment of the transaction input can be balanced ( f represents the amount of the transaction fee).

Knowledge point: Pedersen Commitment: Replace the unspent transaction output (UTXO) value expressed in plain text with encrypted Commitment, that is, make it possible for people to verify the validity of the transaction without revealing the transaction value.

Briefly summarize the two benefits of additive homomorphism. One is that there is no need to decrypt, and the validity of the transaction can be verified without knowing the specific transaction amount. The other is that it can be directly calculated with the transaction fee in plain text, and miners can directly see their own income. is, and it can be verified that this equation is valid.

Another point is that the sender of the transaction and the receiver of the transaction do not know each other's blinding factor, that is, the inputter of the transaction does not know the blinding factor of the outputter, and the outputter of the transaction does not know the blinding factor of the inputter blinding factor, but they know the transaction amount.

The result of this is that the transaction amount on both sides of the equation can be offset by balancing, but the blinding factor cannot be offset. If you subtract the output from the input, you end up with one term:

• （ro-ri）*H

(ro is the sum of the blinding factors of the transaction output, ri is the sum of the blinding factors of the transaction input, and H is the generator 2)

We can call it "remainder".

Note: Whether (ro-ri)*H or (ri-ro)*H equals the remainder is immaterial, depending on project-specific choices.

In MimbleWimble's Confidential Transaction, in order to prove that this transaction is not constructed indiscriminately (transaction exporter and importer both know their own blinding factors, and do not use other people's transaction output to construct their own transaction), there needs to be a way to solve.

It is relatively simple in Bitcoin, which is to directly sign the entire transaction with your own private key, proving that you participated in and constructed the transaction.

But the MimbleWimble approach is novel - you just have to prove that you know the blinding factor difference.
(Note: The blinding factor difference here is "sum of blinding of transaction output - sum of blinding factor of transaction input", which is the same concept below)

Because the importer and the exporter only know their own blinding factor but not the other party's blinding factor, they need an agreement to jointly prove that the difference between the blinding factor can be calculated by adding the knowledge of the two people together. This is equivalent to directly signing the entire transaction, which can prove that I did not construct the transaction indiscriminately.

To put it another way, if I can prove that I know the blinding factor difference, I also complete the authorized signing of the transaction without signing the transaction with the input private key.

In MimbleWimble, in fact, the blinding factor difference is used to sign a fixed string, such as 0, to prove that I know the blinding factor difference, and then I publish the remaining items at the same time.

The core of the above paragraph is that the knowledge of the blinding factor difference can replace the private key in the traditional transaction of Bitcoin.

There is an additional point, we need to have a Range Proof.

For the amount part, you need to prove that there is no negative number in the amount part, because we don’t want someone to construct a transaction where the transaction input is 1 and the transaction output is 2 and -1, which will create some money out of thin air.

In order to prove that there are no negative numbers in all the outputs of this transaction, each transaction output needs to have a Range Proof, a short zero-knowledge proof, to prove that all transaction outputs are less than a certain threshold and are all positive.

To give you an intuitive concept, the encrypted ciphertext of each transaction output is about 33 Bytes, but the Range Proof is now about 5 KB, and this is already an optimized result, because Range Proof is equivalent to a zero-knowledge proof , it's hard to make shorter.

Gregory Maxwell made the first version ofConfidential Transaction, he perfected the Range Proof, and then Benedikt Bünz, a student of Stanford University, proposed an improved version of the Range Proof, which is shorter than the original Gregory's Range Proof and has a faster verification speed. The improved version of Range Proof is calledBulletproofs, published in the top 1 meeting in the field of information security. Bulletproofs makes RangeProof much smaller, about 700 Bytes in size.

Pieter Wuille and Gregory Maxwell are both authors of this article. They helped Benedikt complete the implementation and testing of Bulletproofs, which also means that the latest cryptography advances are directly applied to MimbleWimble's Confidential Transaction structure.

Let's briefly review the first part now. MimbleWimble has three basic components. The first one is Confidential Transaction, which realizes the encryption of the amount, and directly uses the blinding factor difference to sign the private key to prove its knowledge of the remaining items, replacing Traditionally, the input private key is used to sign directly, and a Range Proof is also attached to the Confidential Transaction.

Coin Join

Now we start to talk about Coin Join, the second component of MimbleWimble.

The idea of ​​Coin Join is very simple. When I have two transactions, the left and right sides of each transaction equation can be balanced:Adding the left and right sides of the two transaction equations together is still a legal transaction. Say one transaction has input 1 and output 1, and another transaction has input 2 and output 2. We construct a new transaction, which has two inputs, input 1 and input 2, and two outputs, output 1 and output 2, which is also a legal transaction.

Coin Join was first proposed by Gregory Maxwell, which is a solution for better privacy in the early days of Bitcoin.

But when Gregory Maxwell proposed the Coin Join protocol, everyone had a big question, that is, there is only one balancing method for each input and each output of a transaction. For example, the input of a transaction is 8 BTC, the output is 3 and 5, and the input of another transaction is 20 BTC, the output is 10 and 10, we put the input and output of these two transactions together, people can still It can be seen that which output corresponds to which input first, so Coin Join itself does not provide much privacy

But when it is combined with Confidential Transaction to encrypt all transaction input and output, it can provide very good privacy.

The Coin Join protocol is very simple, but there will be a problem in directly connecting it with CT. If we use the traditional signature method (the validity of each transaction is signed with the private key corresponding to the public key entered in the transaction), we It is entirely possible to determine which input corresponds to which output based on the address used for the signature.

Therefore, Coin Join plus Confidential Transaction is naturally required to choose another signature method, which is to directly use the remaining items as the public key, use the difference of the blinding factor as the private key, and use this public-private key pair to sign 0. This solves the situation where the input and output can be linked directly through the signature of the transaction.

It is possible for Zcash to implement smart contracts for zero-knowledge proofs in the future, but it will be very slow. In the Cash scenario, I personally think that Bitcoin’s support for smart contracts is sufficient, because Bitcoin has some basic verification functions. We can arrange and combine these functions to complete the verification tasks required by many smart contracts in the real world.

Grin Coin's smart contract support capability at design time is worse than that of Bitcoin and Zcash. But this also motivates researchers to think about how to implement smart contracts in a system where there is no address identifier and many transactions will be deleted.

There is another problem with Coin Join. I mentioned before that 0 is signed. If it is really signed 0, you can directly add the two signatures together to make a new legal signature. However, during the actual operation of the protocol, it is found that it is not good to use 0 as a signature, but a field with a fixed format should be signed.

Because the object of each transaction signature is different, it is not possible to directly add these signatures together. So how can it be possible to connect transactions together with Coin Join to form a huge transaction without affecting transaction verification? After connecting together, is there any way for us to reconstruct which transaction input corresponds to which transaction output?

One Way Aggregate Signatures

This involves his third technology, called One Way Aggregate Signatures, one-way aggregate signatures.

The single-item aggregate signature splits the difference x of the blinding factor into two items x1 and x2, where x1*H is public as a public key. Of course, x1 itself is not public, and a signature is needed to prove that I know x1. x2 is directly public, proving that I also know x2 . x1*H + x2*H is equal to the previous remainder.

Now after splitting the difference between the blinding factors into two items, x1*H is called Kernel Excess, x2 is called Kernel Offsets, and Kernel Offsets is the offset.

What is the benefit of splitting the difference of a blinding factor into two parts?

When all transactions in a block form a large Coin Join transaction, those Kernel Offsets that are disclosed as plain text can be directly added together, thus throwing away the information of each transaction.

For those parts that need to be signed, because the signed parts are not all signed to 0, but to a fixed field signature, they cannot be aggregated together, and these signatures need to be stored separately. That is to say, all Kernel Offsets are added together, and only one Kernel Offset is stored in a block, but Kernel Excess is still stored separately. A Kernel Excess and a signature of a fixed field using x1 are stored in the Kernel of each transaction.

The advantage of this is that when you get a huge Coin Join transaction block, you can re-combine the aggregation items of Kernel Offsets and all signatures to verify that all transactions in this block are valid. And because the Kernel Offsets have been combined, there is no way to disassemble the added Offsets. We have no way to know which input and output each signature corresponds to, so One Way Aggregate Signatures is implemented.

Let me explain again, the fundamental function of One Way Aggregate Signatures is that when you get many transaction inputs and outputs in a block, you have no way to judge which transaction inputs and outputs were originally a transaction. Its method is to divide the difference of the blinding factor of each transaction into two parts, one is to prove that I know it with a signature, and the other is to directly publish the plain text to prove that I know it. For the item that directly publishes the plaintext, for all transactions, they can be directly added together.

Here I will add the concept of Cut Through.

Because all the transaction outputs that have been spent appear once on the left side of the equation in the block and once again on the right side, we can cross out the terms that are on both sides of the equation. The concept of Cut Through is that the transaction output that has already been spent can be deleted in the block. When there are many blocks, we can delete the transaction input and output of different transactions across blocks to achieve compression The purpose of hard disk storage space.

However, Mimblewimble will have several points that are difficult to aggregate. One is the Range Proof of all transaction outputs. As time goes on, there will be more and more UTXOs in the Mimblewimble system, and each transaction output has its own Range Proof. Proof, to prove that my output is non-negative.
(Note: UTXO does not increase monotonically over time. What is expressed here is that as time progresses, the number of users increases and UTXO increases.)

When you need to verify the validity of UTXO, you need to calculate these Range Proofs from beginning to end, which is equivalent to more time and storage space for verifying the validity of a single transaction output than Bitcoin.

Therefore, the bottleneck of Mimblewimble calculation and storage space is Range Proof. In addition, after the blinding factor is split into two items, each new transaction has its own signature, and this non-aggregatable item cannot be compressed.

When you traverse the entire blockchain, it will also affect the verification time, and the above are the two items that most affect Scaling.

Concrete implementation of MimbleWimble - Grin

Next, let's talk about the specific implementation of MimbleWimble—Grin, whose mining algorithm is called Cuckoo Cycle.

Simply put, Cuckoo Cycle is two very long hash tables, each table has many nodes, and many threads are connected between the two hash tables in a pseudo-random manner.

Hash table 1 can only be connected with hash table 2, and hash table 2 can only be connected with hash table 1. The elements of table 1 cannot be connected, and the elements of table 2 cannot be connected.

Puzzle itself is to find a circle with a length of exactly 42, that is, node A in table 1 is connected to node B in table 2, node B in table 2 is connected to node C in table 1, and so on to find a circle of length for 42.

The original purpose of this design is to allow the Puzzle itself to occupy as much memory space as possible before starting to solve it.

Because if you want to know which points in Table 1 are connected to a node in Table 2, the best way is to count all the edges first, save them in a certain data structure, and then search in this data structure, so that It can ensure that a large memory space needs to be opened before searching, so as to avoid the calculation of Puzzle is only related to the use of CPU, and the original intention of large memory space is also to cause certain difficulties for ASIC.

But with the development of time, everyone realized that ASIC will exist anyway, so some improvements were made based on the best algorithm to solve this problem at that time, so that Puzzle can also be counted with ASIC. It will choose a protocol that is not very friendly to ASICs at the initial stage of the protocol, but after two years it will be completely replaced with an improved version of the protocol that is very convenient for ASICs.

Here is one more point, as a student of cryptographers (I am not a cryptographer, but my boss is), the most shocking thing about Cuckoo Cycle is that at the beginning of the design, it only has intuition, and there is no mathematical proof which The algorithm must be the fastest. These algorithms for solving Cuckoo Cycle were all discussed when Cuckoo Cycle was already famous.

So when there is no mathematical proof, it is entirely possible that a person suddenly invented a particularly fast algorithm to solve Cuckoo Cycle, so that all Grin Coins were dug by him alone. This is also a problem for Grin at the moment

This was also a lesson for me. In 2013, I spent a year trying to design my own PoW algorithm, which was very close to Cuckoo Cycle, but what tormented me at the time was that I couldn’t find a mathematical proof that a certain algorithm must solve Puzzle It is the fastest, so I never posted the last article. Thinking about it now, I feel very sorry, because this kind of immature idea can be thrown out for everyone to discuss, maybe some good ideas can be discussed, and not everything needs to be proved by mathematics.

So when I heard about the design of Cuckoo Cycle some time ago, I was filled with emotion.

So far, the details about MimbleWimble have been covered.

Pick Time

In the final sharing session, I would like to share with you my experience of studying for a Ph.D. in Belgium, hoping to inspire you who are interested in academics.

Recommended reading:

Recommended reading:

• Zhang Ren's Consensus Security Analysis Article"Developing Common Criteria: Assessing the Security of PoW Consensus Protocols"

• Zhang Ren analyzed consensus protocol articles from the perspective of bandwidth utilization"Nervos CKB Consensus Protocol NC-Max: Breaking Through the Limit of Nakamoto Consensus Throughput"