Free and easy week review 丨 RSA accumulator becomes SNARK system cost reduction weapon, DEX and other applications may become the biggest beneficiaries

Introduction: This week we will focus on sharing a new paper "Extended Verifiable Computing Using Efficient Set Accumulators" written by Stanford University Professor of Cryptography, Dan Boneh and others, to explore the potential improvements of RSA accumulators to the SNARK system.

In the weekly selection of hard-core technical articles, we will also see the content of zero-knowledge proof system overview, the security and scalability of sharded blockchains, and differences in smart contract types.

In addition, last week the 0.1 version of the Ethereum 2.0 specification was officially released, and the Bitcoin improvement proposal Taproot / Schnorr is also about to be ready, and has now entered the developer feedback stage.

(Picture from: tuchong.com)

• Do you know these 16 stalks about Bitcoin?
• US CFTC Chairman: Ripple (XRP) may be considered a security by the SEC
• Ba Shusong, Chief Chinese Economist at HKEx: Libra will make some economies increasingly dependent on fiscal policy

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

We know that blockchain systems generally face scalability issues, and on-chain work is obviously expensive, so many project parties have turned to off-chain technology.

A verifiable outsourcing system can offload a large amount of calculations to a remote server, but requires the remote server to provide a concise certificate (called SNARK) to prove that it performed the calculation correctly. We can find practical applications of these methods in multiple blockchain systems that use verifiable outsourcing to handle a large number of transactions off-chain.

This simplifies the on-chain work to verify a concise proof, which can confirm whether the transaction processing is completed correctly.

Recently, Dan Boneh, a professor of cryptography at Stanford University, and his students, Alex Ozdemir and Riad S. Wahby, published a paper entitled " Extended Verifiable Computing Using Valid Set Accumulators " in this research work. In the past, they combined existing technology and new technology to realize the RSA accumulator inside the SNARK system and use it as a replacement for the Melkle tree structure.

Experiments show that compared with existing methods that use Merkle trees to submit the current state, the newly proposed system can significantly reduce costs.

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

1.1 Introduction

Verifiable outsourcing is a technology that enables weak clients to outsource computing to powerful servers. The server returns the calculation result and a certificate indicating that the calculation was completed correctly. The proof must be concise, which means it must be short and cheap to verify.

Verifiable outsourcing is relevant in many cases, including weak IoT devices, wearables, and low-power devices.

Recently, verifiable outsourcing technologies have been deployed in blockchain environments. In these systems, a batch of k transactions (such as k = 1000) is outsourced to an untrusted server (called an aggregator) for processing. The aggregator (1) verifies that the transactions are valid (such as correctly signed), (2) calculates the updated global state generated by these transactions, and (3) generates a concise proof that the aggregator performed steps (1) and (2).

The updated status and concise proof are then sent to the blockchain. In this method, the (expensive) work on the chain is reduced to just verifying (fast, the time required has nothing to do with the number of transactions k) proof, and then recording the updated status.

Example systems operating in this manner include Rollup , Coda , Matter, and Zexe .

The above process is called verifiable outsourcing of status updates. More specifically, the status is a set of elements S = {x1, …, xM} from a universe X. The blockchain (or low-power device) stores only a concise summary of S, for example, the root of a Merkle tree whose leaves contain the elements of S. The untrusted but powerful aggregator stores the complete element group S.

When processing the above batch of transactions, the aggregator updates S to generate a new set S ', and then calculates a new Merkle digest for this S', which is responsible for sending it to the blockchain for verification and recording.

The proof of the aggregator establishes that its starting state S is consistent with the current digest, and the correct application of the transaction will generate an ending state S ', and the new digest is consistent with S'. The concise proof needed here is SNARK.

The Merkle tree is an example of an accumulator, which is a cryptographic primitive that allows a person to submit a set S and then prove that an element x is a member of the set S. Although the Merkle tree structure is widely used in today's universal verifiable state update applications, according to research, when S is medium or very large (such as | s | ≥ 210), the Merkle tree is not updated in large quantities. best choice.

In particular, researchers have shown that replacing Merkle trees with RSA accumulators can significantly improve proof time and reachable computations.

The following are the specific contributions of this thesis study:

1. A new operation is defined for the RSA accumulator, and it is called MultiSwap , which provides precise sequential semantics for batch verification status updates;
2. Integrate existing and new technologies to effectively implement MultiSwap (RSA Accumulator) in the SNARKs environment, which takes advantage of the latest progress in operating RSA accumulators;
3. This technique is used in two cases, the first is an off-chain batch technology called Rollup, and the second is a general-purpose RAM abstraction with persistent state;
4. Experimental evaluation of the proposed technology, comparing the implementation of the RSA accumulator with the Merkle tree on two benchmarks;

1, 2 About the accumulator

Cryptographic accumulators can present a collection of values ​​(such as a vector, a collection, or multiple collections) as a concise summary.

This abstract is binding, which informally means that it is computationally impossible to vaguely express the set represented by the abstract.

In addition, accumulators allow concise proof of membership and, in some cases, non-membership.

The Merkle tree is one of the most famous vector accumulators. To recap, it is a binary tree structure. It stores the vector in the labels of the cotyledons, and the labels associated with the internal nodes of this tree are the result of applying the anti-collision hash H to the child labels;

Updating the labels of cotyledons is closely related: given a member proof of the old value, the new digest is calculated by replacing the old leaf with the new leaf, and then calculating the hash along the path.

Merkle trees do not support concise non-member proofs.

For a vector containing 2 ^ m values, the cost of verifying k member proofs is k · m evaluations of H, and the cost of k cotyledon updates is 2 · k · m evaluations. Member certifications and updates cannot be saved in batches.

Regarding the RSA accumulator, we can read this article " Deeply Exploring the" Blockchain Slimming Method "RSA Accumulator ".

Note: This research work focuses on SNARK-type zero-knowledge proofs, which are also compatible with Zaatar, Ligero, Bulletproofs, Sonic, and Aurora, but not compatible with STARK or systems built on GKR and CMT, such as vRAM, Hyrax, and Libra.

1.3 Application of MultiSwap

In the paper, the researchers also discussed two applications of MultiSwap, one of which is verifiable outsourcing for smart contracts: blockchain systems such as Ethereum implement smart contracts, and a major practical limitation of this approach is that, Computing, storage, and network traffic are very expensive for smart contracts, and one solution is Rollup, which is an example of verifiable computing.

The smart contract delegates the job of checking transactions to an untrusted aggregator, and then checks that the proof of this job is correct. To this end, the user submits the transaction γi and sends it to the aggregator, rather than directly to the smart contract.

The aggregator combines these transactions into a batch {γi}, and then generates a proof π that proves the computation that validates the batch and updates the global state Ψ. Finally, the aggregator submits relevant information to the smart contract. For smart contracts, checking this proof is much cheaper than verifying each transaction individually.

The following figure shows the Rollup cost comparison using Merkle and MultiSwap:

Another application is efficient persistent RAM. The paper mentions:

"Pantry-style RAM, although expensive, provides a unique capability to pass the full state of RAM from one proof to another. This enables execution in persistent state, recursively verifiable state machines, and other useful applications Calculations. Unfortunately, the high cost (under constraints) of the hash function limits the number of Pantry-like RAM operations that can be used for calculations, especially for large RAMs. With the batch RSA accumulator construction, it is possible Solve this problem. "

Code implementation: According to the researchers, they have implemented a Rust code library containing multiple precision operations, RSA accumulators, and Merkle trees. The total code involved is about 10,000 lines. ( Https://github.com/alex-ozdemir/bellman-bignat )

Regarding the implementation of MultiSwap, the researchers also carried out experimental evaluation and compared it with the Merkle tree structure. The following figure shows the comparison results:

Constraint count v. Swap number, "Merkle m" is expressed as a Merkle tree with 2 ^ m cotyledons

Verifiable operands under 10 ^ 9 quantity constraints (the higher the number, the better)

Constraint count v. Number of transactions, "Merkle m" is expressed as a Merkle tree with 2 ^ m cotyledons

Constraint count v. Number of transactions, "Merkle m" is represented as a Merkle tree with 2 ^ m cotyledons. Ribbon indicates change from 0% to 100% depending on the write load

Discussions and conclusions

Researchers have stated that they have proven that RSA accumulators can be cheaper to construct than Merkle trees in medium to large verifiable state applications.

There are two considerations: First, the RSA accumulator requires a trusted setting. In fact, most SNARK constructs require a trusted setting, so this is not a big burden. In addition, deployers can reduce trust requirements by generating RSA modules using multi-party calculations. A conjecture alternative to avoiding credible settings is to use a class group of imaginary quadratic order.

In addition, exploring effective constraint implementation will be their focus in the future.

Free and easy comments: This research can theoretically effectively reduce the cost of blockchain systems that use Rollup's verifiable outsourcing technology, and the relevant code has been open source. At the same time, the author of the paper, Alex Ozdemir, is also actively maintaining the code base and decentralizing transactions. Applications such as DEX may be the most direct beneficiaries. Personally, in the next few years, DEX may usher in rapid development.

Second, hard core technical articles of the week

2. 1 The Cambrian cryptography proved a big explosion. How should dozens of zero-knowledge proof systems be selected ?

Professor Eli Ben-Sasson, the co-founder and chief scientist of StarkWare, outlined in this article nearly 20 zero-knowledge proof systems and gave his views on these proof systems, saying:

1. The symmetric CI system can perform arithmetic operations on any field, thereby improving efficiency;
2. Only symmetric systems are reasonable post-quantum security systems;
3. New asymmetric assumptions will be the basis for higher risk for financial infrastructure;
4. The asymmetric circuit dedicated system (Groth16) is the shortest, it is shorter than all asymmetric universal systems and all symmetric systems.

It concluded:

"Systems that require asymmetric cryptographic assumptions that lead to shorter proof times but higher proof costs, they have newer assumptions that are susceptible to quantum computing, many of which are opaque and rely only on Symmetrically hypothesized systems, which make them computationally efficient, transparent, and possibly post-quantum safe, and according to the Lindy effect, they may also be the most future proof. "

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

Free and easy comments: There is no perfect zero-knowledge proof system, and some only have trade-offs. From the perspective of code maturity, SNARK may be the best choice at present. The research we mentioned above is also performed on SNARK, while STARK is It has better scalability characteristics, but it is still in the early stages of exploration.

2, 2 Dry Goods | Security and Scalability in Commission-Based Sharded Blockchain

A technical article (converted by haiki & Ajian) from ConsenSys Layer 2 scalability researcher John Adler, which aims to analyze the security and scalability in a sharded blockchain in a simple and understandable way The tension between.

The article concluded that:

"Commission-based sharding requires stateless execution (which has not been proven to be feasible in itself), plus proof of error and proof of data availability. However, when considering the spread of transactions, we found that scalability can only be achieved by applying Security can only be achieved by moving to the p2p network layer, which is very fragile against malicious opponents. Whether we can overcome this obstacle is still an open research question. "

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

Free and easy comments: The sharding solution seems to solve the dilemma of scalability, but in the process of landing, it will encounter a lot of problems, which requires researchers to spend a lot of energy to overcome them one by one.

2.3 Technical Analysis: What is the difference between smart contracts on Ethereum, Bitcoin and Bitcoin Cash ?

The article focuses on the prominent differences between smart contracts on the three platforms: ETH, BTC, and BCH. Ethereum is the most widely used and most commonly used smart contract platform. Bitcoin provides a more basic version of smart contracts through its stateless script system. This stateless system is more efficient to verify, but has fewer features. Bitcoin Cash has the same foundation as Bitcoin, but adds new features that try to compromise between valid verification and useful smart contracts.

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

Free and easy comments: In terms of smart contracts, Ethereum has the most features and its largest steps. Bitcoin is slowly moving towards efficiency and privacy based on the principle of "stability", while BCH is at Between the two, the three have taken different paths and may have different results.

Technical Progress of Mainstream Blockchain Projects

3.1 The final version of Ethereum 2.0 specification 0.1 is released! A key step away from going online in 2.0 years

Ethereum 2.0 coordinator Danny Ryan officially released the final version of the Ethereum 2.0 specification 0.1 last week.

It is reported that this version focuses on the integration of the IETF BLS standard into the eth2 specification, and the developer also said that some revision work will be carried out in February-March.

Link: https://www.8btc.com/article/545177

Free and easy comments: According to Justin Drake, the unofficial deadline for Ethereum 2.0 Phase 0 is July 30. At present, this expected time point is more reliable. The possibility of June to July is more likely. Big.

3.2 Pieter Wuille: Taproot / Schnorr proposal to enhance Bitcoin privacy is ready

Bitcoin code maintainer Pieter Wuille said in a recent report speech that the Taproot / Schnorr proposal to enhance Bitcoin's privacy is about to be prepared and has now entered the developer feedback stage. After the feedback is completed, the proposal will enter the implementation stage.

https://bitcoinops.org/en/newsletters/2020/01/08/

Free and easy comments: The development of Bitcoin ’s Taproot / Schnorr proposal has finally come to an end. As the core of version 0.20.0 is expected to be officially released around half the time (May), these large-change proposals are unlikely Included, then we can only look forward to seeing the Taproot / Schnorr proposal in the next version 0.21.0.

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!