Free and easy weekly review 丨 Three minutes to understand the new zero-knowledge proof solution Virgo (Virgo)

Introduction: This week we will first understand the concept of zero-knowledge proof through two popular science articles, and then understand the new zero-knowledge proof scheme Virgo (Virgo) proposed by "Computer Security Godmother" Professor Song Xiaodong and others.

In the weekly selection of hard-core technology articles, we will also see the content of the annual summary of Bitcoin technology, the Eth2.0 relay network and fee mechanism, and the new ideas of the blockchain hierarchical model.

In addition, the new proposal proposed by V God may accelerate the overall implementation of ETH 2.0.

(Picture from: pexels.com)

• Long Baitao | Central Bank Digital Currency-Global Consensus and Division
• 8 Questions | Dr. Jin Jian of ICT: ID may trigger large-scale application of blockchain
• Central Bank's deployment of key tasks in 2020: introduction of a series of financial technology regulatory rules such as blockchain

The following is a selection review of last week's content, enjoy ~

I. Understanding zero-knowledge proofs, what does the new zero-knowledge proof scheme Virgo (Virgo) look like?

Regarding blockchain privacy issues, we often mention zero-knowledge proof (ZKP) schemes, which allow the prover to convince the verifier that a statement is true without revealing any additional information beyond the validity of the statement.

In recent years, zero-knowledge proof protocols have made tremendous progress in computing delegation, anonymous certificates, privacy-protected cryptocurrencies, and smart contracts. Before entering this week's academic paper sharing, we need to understand the concept of zero-knowledge proof, so first recommend two good popular science articles:

1Zero-knowledge proof study notes: background and origin

The article was provided by Dong Ze, a cryptographic scholar at Stanford University. It first started with the problem of insufficient privacy of Bitcoin, and then talked about the disadvantages of the two Bitcoin privacy improvement schemes, CoinJoin and Confidential Transaction (CT). Then he talked about The zero-knowledge proof scheme zk-SNARKs used by ZCash and its potential applications.

Article link: https://www.8btc.com/media/537030

2 Guo Yu: Understand zero-knowledge proof in 3 minutes. Why is it a double-edged sword?

The content of "Zero-knowledge proof, a missing link in blockchain technology" shared by Guo Yu, the founder of Abe Labs and Academic and Technical Committee member of the Digital Asset Research Institute (organized by Babbitt reporter), talked about the concept of zero-knowledge proof Origin, and the basic concept of zero-knowledge proofs using the map three coloring problem. In addition, on March 1, 2018, a fatal error in the paper [BCTV14] Appendix B of the ZCash team members can be used for infinite coinage, This also reminds people that the zero-knowledge proof protocol cannot be separated from formal verification.

Article link: https://www.8btc.com/article/537797

Although the research progress is significant, many zero-knowledge proof (ZKP) schemes still have some limitations, such as the zk-SNARKs mentioned above, which requires a trusted setup phase to generate structured reference strings (SRS ), And if the trap door is leaked, the security of the system will be compromised.

To address this problem, many recent zero-knowledge proof (ZKP) schemes have been designed to remove the need for trusted settings.

Four researchers from the University of California, Berkeley and Texas A & M (including Yupeng Zhang, Jiaheng Zhang, Tiancheng Xie, and Dawn Song (Song Xiaodong)) referred to this type of ZKP scheme as transparent zero-knowledge proof (ZKP) According to the protocol, they also proposed an efficient and transparent ZKP system with a simple proof size and verification time based on the double-effective interactive proof GKR scheme proposed by Goldwasser et al.

Link to original paper: https://eprint.iacr.org/2019/1482.pdf

This research paper has been accepted by IEEE S & P 2020, the top conference on security and privacy.

Doesn't it look "great and tired"? Let's take a closer look at what this agreement looks like!

According to the paper, the contribution of this research can be roughly divided into three points:

1. Transparent zero knowledge verifiable polynomial delegation : Researchers have proposed a new zero-knowledge verifiable polynomial delegation (zkVPD) scheme that does not require trusted settings. Compared with existing pairing-based key distribution schemes, this new scheme does not require trapdoors and linear-size public keys, which eliminates heavy cryptographic operations such as modular exponentiation and bilinear pairings;
2. Transparent zero knowledge argument : Researchers have effectively combined the new zkVPD protocol with the GKR protocol to obtain a transparent ZKP scheme, which uses only lightweight cryptographic primitives Language (such as a collision-resistant hash function, so it may be quantum-resistant);
3. On the basis of the new scheme, the researchers implemented a ZKP system called Virgo (Virgo) , which is an upgraded version of the researchers ’last ZKP scheme Libra (don't misunderstand, not Facebook Libra), and They also plan to open source the system;

Comparison of Virgo (Virgo) with other zero-knowledge proof schemes

Above, we briefly introduced the main contributions of this research. In order to save time, we directly skip very complicated technical descriptions and look at the conclusions. The main technical contribution in this research is a new proof with O (N log N) Time, Transparent zkVPD scheme for proof size and verification time (where N represents the size of the polynomial).

In addition, the zero-knowledge proof system Virgo (Virgo) implemented by the researchers is implemented in C ++. The transparent zkVPD protocol has about 700 lines of code, and the GKR part has 2000 lines of code.

After conducting experiments on a single server, the researchers compared it with six other ZKP solutions (including Libra, Ligero, Bulletproofs, Hyrax, Stark, and Aurora). The results are shown in the following figure:

Comparison of certifier (P) time, proof size, and verification (V) time between schemes

Among them, Virgo (Virgo) is optimized 7-10 times better than Libra on the first two benchmarks, and 3-5 times faster on the third benchmark. This optimization comes from researchers We newly proposed efficient zkVPD.

Compared with other transparent ZKP systems, from the perspective of the actual prover, Virgo is the best of these systems, it is at least an order of magnitude faster than other systems, and in comparison of verification time, Virgo's performance is also very outstanding.

For example, verifying a Merkle tree with 256 cotyledons and a circuit structure of 2 ^ 26 gates, Virgo only takes 50 milliseconds, and its verification time is competitive with ZK-Stark.

In terms of proof size, it is larger than Bulletproofs , similar to Hyrax, Stark, and Aurora.

Application scenarios of zkVPD and the new ZKP solution

Finally, in this paper, researchers proposed three application scenarios for the new scheme, which are as follows:

1. Verifiable secret sharing;
2. Improve the privacy of blockchain projects;
3. Large-scale zero-knowledge proof: In addition to the blockchain, there are many other applications that need to prove large-scale claims. For example, the US Defense Advanced Research Projects Agency (DARPA) recently intends to use ZKP to prove the behavior of complex programs without revealing sensitive information. And such applications need to extend the ZKP scheme to circuits with billions of gates.

Free and easy comments: In 2019, the field of zero-knowledge proof research has ushered in several new schemes, without the need for trusted settings, smaller verification sizes, and shorter prover (p) time and verification (v "Time" has become the "standard" of the excellent ZKP solution. Although the Virgo (Virgo) solution is tested under a single server, the results presented are surprising. As for the solution, The specific implementation and potential problems are waiting for researchers to explore carefully (especially its performance under multi-server conditions, which is not mentioned in the paper).

Second, hard core technical articles of the week

2.1 The Most Complete Annual Summary of Bitcoin Technology

A 2019 Bitcoin Technology Progress article summarized by Bitcoin Optech, which reviews nearly 9,000 commits (almost 2000 mergers) of the Bitcoin Technology project code base, more than 1,500 mailing list posts, thousands of lines of IRC logs, and many other public sources .

Here are the most significant technological advances each month:

January: BIP127 Reserve Certificate;

February: (1) Bitcoin Core compatible with hardware wallet interface, (2) Miniscript;

March: (1) consensus cleanup soft fork proposal, (2) Signet, (3) Lightning Loop;

April: (1) AssumeUTXO, (2) Trampoline payment;

May: (1) Taproot, (2) SIGHASH_ANYPREVOUT, (3) OP_CHECKTEMPLATEVERIFY;

June: (1) Erlay and other P2P relay improvements, (2) Lightning Network Watchtower;

July: Guix

August: No-Contract Treasury

September: (1) SNICKER, (2) Lightning Network vulnerability discovered;

October: LN anchor output;

November: (1) Bech32, (2) Remove OpenSSL from Bitcoin Core, (3) Remove BIP70 from Bitcoin Core;

December: Lightning Network Multipath Payment

Full text link: https://bitcoinops.org/en/newsletters/2019/12/28/

Easy and Easy Comment: It may be the most comprehensive article in the market that introduces the progress of Bitcoin technology in 2019. Bitcoin has ushered in a series of incremental improvement solutions, and many of them have been ignored by everyone and are interested. Can understand.

2, 2 dry goods | Eth2.0's repeater network and fee mechanism

A technical summary article (translated by IAN LIU & A Jian) ​​from Ethereum 2.0 researcher John Adler, which focuses on the Ethereum 2.0 relay network and fee mechanism. Among them, each proposal has different trade-offs and is adopted by different platforms. Therefore, a reasonable and comprehensive summary can make it easier for new researchers to get started.

Article link: https://www.8btc.com/media/539143

2.3 Vitalik: the base layer and the function escape speed, on the necessity of developing layer 1 and layer 2 in parallel

Ethereum co-founder Vitalik Buterin mentioned in his latest post "Basic Layer and Function Escape Speed" that "Keeping layer 1 simple and using layer 2 to make up for shortcomings" is not a solution to blockchain scalability and functionality The general answer to the question, because this idea does not take into account that the layer 1 blockchain itself must have sufficient scalability and functionality, otherwise the so-called layer 2 protocol is only a trusted intermediary. In this article, Vitalik put forward the concept of "function escape speed". He also stated that in the short term we need to develop layer 1 and layer 2 in parallel, and in the long term we should pay more attention to the development of layer 2.

Article link: https://www.8btc.com/article/539384

Free and easy comments: V God explained that layer 1 has three conditions (1, including a programming language that can verify any content, 2. Rich statefulness, 3. Full data scalability and low latency ), So that layer 2 can be deployed without a trusted intermediary, so he suggested that we still have to develop layer 1 and layer 2 in parallel in the short term .

It is generally believed that users do not have much requirements for the decentralized properties of layer 2, but if they can achieve decentralization with high performance, wouldn't it be beautiful? Alas, it seems to cause some security problems again. There are related comments under the original https://vitalik.ca/general/2019/12/26/mvb.html .

Technical Progress of Mainstream Blockchain Projects

3, 1 Vitalik Buterin released a heavy new proposal to make the ETH 1.0 chain as the shard 0, and migrate to ETH 2.0 faster

Last week, Ethereum co-founder Vitalik Buterin proposed a faster way to migrate ETH 1.0 data to ETH 2.0. This solution requires stateless clients, but does not require stateless miners and web assemblies. So less refactoring is needed, and ETH 1.0 will exist as shard 0 of ETH 2.0.

Original post: https://ethresear.ch/t/alternative-proposal-for-early-eth1-eth2-merge/6666/13

Easy and Easy Comment: This proposal is expected to accelerate the overall implementation of ETH 2.0, but its Phase 0 (Phase 0) seems to still have to wait for more than six months, and Ethereum will now face a very important update — — The “Muel Glacier” hard fork, which will remove the difficulty bomb, which will gradually restore the block time of Ethereum to about 14.3s, which is expected to occur in 3 days (afternoon on January 2, 2020 Beijing time) . (Tucao: Developers also have a holiday, this week's R & D progress updates only have this)

This week's exciting content is here, see you next week ~

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