Free and easy week review | How will Coda compress data into 22KB

Write in front:

Imagine that there are 3 kinds of creatures, where A has a current weight of 500 KG, and its annual weight gain is 50KG, B has a current weight of 600 KG, and its current weight gain is 200 KG, and C has a current weight of 4.5 KG, and it is constant at This value, among them, your first reaction is to tend to accept (A, B or C)?

In the blockchain world, Bitcoin is equivalent to A, Ethereum is equivalent to B, and C is the Coda blockchain protocol from O (1) LABS that we will discuss this week. One is coinbase, Multicoin Capital , DragonFly Capital and other well-known capital in the circle are optimistic about a blockchain project, the size of the blockchain is constant at 22 KB (Note: does not include the client).

In the hardcore technical article selection section, we will also see the content about the wonderful question of Bitcoin 8, the privacy scheme ZK² Rollup and the Bitcoin Technology Weekly.

• Learn the Methodology of DAO Movement from the Swedish Pirate Party
• After the delisting of FTX, Binance entered the options market, why did it choose the "American option" that is different?
• DeFi Review: Maker's leap of faith

At the end of the article, we will share some research and development progress on Ethereum 1.X, Ethereum 2.0 and Layer 2.

(Picture from: tucheng.com)

1. 22 KB: How is the Coda blockchain protocol never "increased"?

For cryptocurrencies such as Bitcoin and Ethereum, the "decentralization" attribute comes at the expense of "scalability", because each node needs to process the history of the entire system after joining the network. With the passage of time, the time required to verify all the information of the blockchain will become very long. At the time of writing, Bitcoin's blockchain size exceeded 270 GB, which contained more than 500 million transactions, and It usually takes several days to download all the bitcoin history in the notebook.

Ethereum, which has a lot of status data, is even more bloated. The size of an Ethereum file node currently reaches about 4TB, while the GETH full node that only retains complete transaction history has reached about 300 GB.

These resource requirements are a great resistance to the operation of full nodes. As shown in the figure below, with the passage of time, although the user group of Bitcoin is growing, the number of its full nodes has not increased significantly. The total number of Ethereum nodes has shown a clear downward trend.

Instead, most users will run a light node (only verify the block header without verifying the transaction), or run an ultra-light node (do not verify anything, but rely on a trusted server), which is for the blockchain As far as the decentralized attributes are concerned, they are all disadvantageous.

From the above data, we can see that this problem does not seem to be so urgent for Bitcoin (hardware and network will also increase with time), but for Ethereum, this problem is particularly apparent Urgently, and therefore, research on the stateless client and zero-knowledge proofs, and many Ethereum researchers including V God are very concerned.

1.1 Some solutions about the scalability of blockchain

Through the examples of Bitcoin and Ethereum, we can find that the trade-off between decentralization and scalability has always been a key challenge.

The researchers have also proposed many solutions, and these solutions also have various trade-offs, such as the Lightning Network, Plasma, and Rollup solutions, which are to transfer transactions from the main chain to the off-chain, however, this still requires nodes to run Download the entire blockchain, and the Lightning Network and Plasma also exposed some problems, which limits their effectiveness.

Light nodes are another possible solution. They work by downloading block headers to determine the Merkle root of the database state with the strongest protocol state.

Fragmentation is another solution to increase capacity. However, a node is only fully deterministic about a fragment with complete data. In the case where the sharding node does not have complete data, these nodes must essentially trust the consensus node and operate as a light node. In addition, the cost of this technique is that every time the verifier changes, a new segment must be downloaded.

Another proposed solution is to rely on third-party nodes. In essence, this method requires trusting third parties, which is disadvantageous for anti-censorship and network activity.

1, 2 Coda's concise blockchain design

The developers from the O (1) Labs team and New York University designed a simple blockchain system called Coda, which can effectively verify the history of the system without relying on third-party suggestions. Each block contains concise proof that SNARK achieves this goal.

It is reported that Coda uses an account model (instead of the UTXO model used by Bitcoin), where the current state of the blockchain is a list of all account balances.

It is worth noting that each block of Coda contains a commitment to this state, not the entire state. Therefore, its full node does not have to store the entire state, and only the state commitment is given in the latest block header, which is enough Effectively verify account balance.

In Coda's concise blockchain, there are three main roles, they are:

1. Full node: This role will track and verify the blockchain summary;
2. Block producer: This role will be responsible for generating blocks;
3. Blockchain summary producer: This role is responsible for generating the blockchain summary;

Roughly speaking, we hope that the blockchain abstract can inherit the effectiveness of the underlying blockchain. In other words, the digest is valid if and only if the underlying blockchain is valid. In addition, given a blockchain abstract, we can derive its underlying blockchain through the concept of extractability.

1, 3 Simple blockchain structure based on SNARK

The core of the Coda protocol is the use of zk-SNARK, which serves as an unforgeable certificate to prove that the calculation is performed correctly without the need to prove the entire calculation. By creating a SNARK certificate, you can prove the block transaction history Accuracy, which effectively reduces the size of the block to a single SNARK (about 1kB).

Specifically, SNARK verifies all rules to reach consensus, which ensures:

1. The transaction is signed;
2. The transaction is valid;
3. Consensus rules (PoS variable random function and other rules);

Although the data volume of each block is about 1kB, it seems to be very small, but because the blockchain is dynamic, there will be new blocks constantly added to the chain, and O (1) Labs hopes that the block The chain is concise at any point in time, so when the blockchain "grows", we calculate a new SNARK proof, which not only verifies the new block, but also the existing SNARK proof itself.

Simply put, it is to create a SNARK for multiple SNARKs, which is used to verify the characteristics of any calculation, we call it recursive SNARK.

We can link these SNARK certificates together in a recursive structure and allow the blockchain to maintain a constant size of about 22 KB (SNARK + tail Merkle path).

Each time a new block is generated, a new SNARK certificate is created, and then by creating a single SNARK certificate containing the previous SNARK certificate, you can prove the entire transaction history of the blockchain, that is, this allows you to start from the original block Transition to the current state while maintaining the size of a single SNARK certificate.

And a recursive synthesis zk-SNARK (1kB), which proves the validity of the entire past history of the blockchain and the current state merkle root path (20kB), which together prove the validity of the user's balance.

In theory, this simple recursive combination is possible, but this has a fatal disadvantage, it is very expensive, although the execution speed of the SNARK verification program is very fast (only a few milliseconds on a desktop computer ), But generating SNARK proofs is very expensive.

In order to solve the above problem, Coda adopted a "cycle of elliptic curves" (cycle of elliptic curves) technology, in which two SNARK structures (called Tick and Tock) are designed so that each other can effectively verify each other's proof.

Among them, Tick SNARK is used to verify the state transition on the "basis" of the tree. Then, in order to effectively merge these proofs, you can use Tock SNARK to "encapsulate" each proof, and then use Tick SNARK to merge two Tock proofs. :

1. Basic SNARK : Tick SNARK used to verify a single state transition, we call it "basic" SNARK;
2. Merging SNARK : Tick SNARK used to merge two Tock proofs, we call it "merging" SNARK;
3. Encapsulated SNARK : Tock SNARK for encapsulated Tick certification, we call it "encapsulated" SNARK.

In order to better understand this, we use a conversion system to illustrate, in this system, each state is just a hash H of the previous state. For x0 and x4, x4 = H (H (H (H (H (x0)))), the SNARK proof tree is shown below:

Intuitively, the blockchain update can be regarded as a state transition system, therefore, incrementally computable SNARK (Incrementally Computable SNARK) can build a concise blockchain.

1, 4 Snark optimization

In this section, we will introduce the two optimization schemes adopted by the Coda protocol. They are "parallel scan state" and "proof incentive", and they are all proposed for the following problems:

Problem: As shown in the figure below, to calculate Si, we need Si-1. Therefore, SNARK proves that the calculation is order-dependent, and the result is that simple implementation will be hindered by the time required to calculate the proof. In addition, Due to the high transaction latency (the time required to aggregate transactions into the SNARK proof), the memory requirements of the block proposer are very high.

Solution: Design technologies that maximize throughput. Specifically, Coda ’s goal is to maximize the speed of transaction processing and verification on the network, thereby attracting more users.

Optimization technique 1: parallel scanning status

We know that unprocessed blockchains are continuous in nature (ie, usually cannot be parallelized), but due to the incremental computability of SNARK, SNARK work can be parallelized. This is a key observation leading to the concept of "parallel scan state", in which case we separate the generated block from the calculated SNARK proof.

We maintain a special queue (called it a work queue), in which we propose new blocks. In other words, it is a queue of "SNARK jobs" to be performed by the network.

Then, the network will calculate SNARK proofs in parallel and calculate a proof tree, where the cotyledons correspond to the proofs that prove the validity of a single block, while the other proofs only prove the correctness of their sub-proofs. Finally, the root certificate verifies the correctness of all blocks corresponding to the cotyledons of the tree, as shown in the figure below,

Through careful parallel design, Coda can ensure that the throughput fully keeps up with the rate of transaction addition.

Optimization Technique 2: Incentive Proofer

We call the party that generates the SNARK certificate as the SNARK prover (or SNARKer for short), and then, in order to achieve the smallest possible transaction latency, we need to use incentives.

The incentive structure proposed by Coda is as follows: Every block producer who pushes a block to the work queue needs to pop a block by generating a certificate that verifies the block. It will issue a fee request and the SNARK certificate it generates. It also includes a transaction in the same block, which pays the fee to the prover of the calculation block snark. Usually, these fees are paid from the transaction fees that the block producer may receive.

In essence, every SNARK has an auction with the lowest price. Block producers want to pay as little proof fees as possible to SNARKer, and SNARKer wants to charge as much as possible for their proof.

Therefore, forcing one block producer to become the SNARK prover of another block at the same time is helpful to the stability of the system.

For a given certificate and related fee request, we require that the opponent cannot deceive the fee request, otherwise, the attacker can pretend to be the other party's certificate as his own proof or modify someone's fee request, and the knowledge signature is The cryptographic primitives that enable it to be implemented in Coda use a structure based on Bowe–Gabizon simulation to extract SNARK.

1, 5 Coda's experimental results and future work

According to the paper, the Coda protocol is written in OCaml language, and its SNARK is written in a special language called Snarky. The underlying gossip protocol is based on libp2p. The size of its testnet client is currently about 900 MB .

In the testnet stage, a total of 85 independent participants participated in the test, of which 49 were block producers and 8 were independent SNARK provers. During this period, a total of 24826 transactions (of which 17256 were from community members) were born, and 53120 blocks of SNARK proofs were generated. In general, Coda full nodes can achieve a constant size goal and maintain a Within the acceptable range.

For now, the research of the Coda protocol only focuses on payment systems, but its concept can theoretically be extended to any Turing complete function. For example, the framework can be extended to support user-defined tokens and multi-signature accounts. In addition, Coda ’s roadmap also includes upgrading the underlying SNARK system, such as research with common settings.

Free and easy comment: Coda's idea of ​​using zero-knowledge proof technology to implement a concise blockchain is certainly worth exploring, but its underlying implementation is very complicated, which will undoubtedly introduce some new technical problems. To reliably implement a blockchain that will never gain weight, a lot of research and experimental verification may be required.

References

1. https://codaprotocol.com/blog/coda-protocol-a-succinct-blockchain
2. Coda: Decentralized Cryptocurrency at Scale https://eprint.iacr.org/2020/352.pdf
3. https://github.com/CodaProtocol/coda/releases/tag/0.0.11-beta5

Second, a week of hard core technical articles

2. 1 Bitcoin Exotic 8 Question: Why was block 620826 born 1 second earlier than block 620825 ?

Regarding bitcoin, we sometimes encounter some difficult technical problems, such as "new blocks are born one second earlier than the old blocks", "different sizes of different full nodes at the same time" and other strange phenomena. Seek help from professional developers to help solve the puzzle. In this article, the translator selected 8 relatively interesting questions, and the great gods from the Bitcoin development community also gave wonderful answers.

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

2. 2 Privacy Scheme ZK² Rollup: How to realize high-speed and cheap privacy transactions on Ethereum

The privacy agreement team Aztec is developing the ZK-ZK rollup solution to achieve hundreds of privacy transactions per second on the Ethereum mainnet, while reducing the cost of each privacy transaction. This article introduces the concept of ZK² Rollup and implements Difficult.

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

2. 3 Bitcoin Technical Weekly Report: Statechain, Schnorr signature and BIP322

In this week's Bitcoin technical briefing, we first described a proposal to deploy statechain on Bitcoin without making changes to the consensus layer, and then summarized the analysis that helps prevent differential power consumption ( DPA) Discussion of the Schnorr nonce generator function attacked, and the proposed update on the BIP322 general signmessage. Finally, we will also introduce some updates on popular Bitcoin infrastructure projects.

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

3. Progress of Ethereum's one-week R & D update

Ethereum 1.X update content:

1. Alex Stokes explained how Ethereum 2.0 benefits from EIP2537 ;
2. OpenEthereum has an initial Alpha version;
3. Stateless Ethereum's updated technology tree : including alternative synchronization protocol, Witness specification prototype, EVM, and binary tree conversion;

Ethereum 2.0 update content:

1. Ben Edgington released the latest update on Ethereum 2.0;
2. Ethereum 2.0 progress update written by Danny Ryan;
3. The bounty campaign for the first stage of Ethereum 2.0 has begun;
4. The latest Prysmatic client update, restart the testnet to run the latest specifications;
5. The latest Lighthouse client update: 3x simultaneous acceleration, modification of specification errors, preparation for multi-client testnet;
6. User experience (UX) report on Ethereum 2.0 staking;

Layer2 update content:

1. What is Zeropool ? An optimistic rollup focused on privacy, its function is similar to the currency mixer;
2. Dharma is deploying a rollup chain using the specifications published on ethresearch;

This is the end of the sharing, see you next week ~

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