In-depth Analysis of ZeroSync Starkware’s Zero-Knowledge Proof System Developed for Bitcoin

ZeroSync Starkware's Zero-Knowledge Proof System for Bitcoin is analyzed in depth.

Author | [email protected]

1. Preface

Zero-knowledge proofs (ZKPs) bring a rapid transformation to the scalability and privacy of blockchain. So far, the Ethereum community has been widely adopting this technology and has made rapid progress. According to official data from L2beat, the two layer-two Ethereum public chains, zksync and starknet, which use zk-rollup technology, have a total TVL of 538 million as of now. It is worth noting that the decentralized exchange dYdX, which is also based on the zk-rollup technology introduced by starknet, has a TVL of 338 million.

As of now, BTC has a market share of 46.69%, and ETH has a market share of 18.39%. However, zero-knowledge proofs are still virgin territory for Bitcoin. In addition, according to data, the overall size of the BTC blockchain is 500.16GB, and the computational power required to prove a blockchain with hundreds of GB of memory is extremely expensive. Therefore, ZeroSync, created by Starkware, was created to fill this market gap and bring the zero-knowledge proof system to Bitcoin, expanding the BTC ecosystem through a compact and efficient proof system. ZeroSync has unimaginable growth potential from the perspectives of commercial value, market demand, and technology.

• Interpretation and Comparison of the EU’s Cryptocurrency Market Regulation Act (MiCA)
• Halving Narrative and Reflexivity LTC falls instead of rises, can BTC halving still bring a bull market?
• Hashed Partner The next bull market will be mainly driven by the Asian market, and bottom-up innovation may emerge in Asia.

2. Introduction to ZeroSync

ZeroSync aims to address scalability, accessibility, and privacy issues in the Bitcoin ecosystem through zero-knowledge proof technology. The official team provides a proof system that synchronizes the state of the Bitcoin chain in real-time, toolkits for developers in the BTC ecosystem, and enhances protocols, applications, and services in the BTC ecosystem through zero-knowledge proofs (ZKPs). The technical team is exceptionally strong, and team member Andrew Milson successfully generated the first open-source proof on the StarkNet network using Sandstorm and miniSTARK, further promoting the development of open-source technology in the blockchain and cryptography field.

As we all know, while setting up a Bitcoin node may be simple, it requires downloading a large amount of block data from other nodes on the network, which often takes several days. This time-consuming process is necessary to ensure that the newly launched node eventually holds the correct state of the Bitcoin chain. The computational power required to prove a 500GB blockchain of BTC is also extremely expensive. However, if compressed, it will eventually form a compact and efficient proof. Once such a proof is generated, any number of nodes in the BTC network can use it to synchronize with the network in real-time. By leveraging zero-knowledge proofs, anyone can immediately verify the latest state of the chain. The proof will not be affected by the inherent size of the chain itself. When the next block is mined, any prover can incrementally expand the proof to the previous state.

The significance of this proof system is that it seamlessly connects with the immutability of Bitcoin. ZeroSync will serve as a tool to fill the aforementioned gap and provide correct verification of the Bitcoin blockchain. It functions similar to a full node implementation, not only obtaining the final state after applying all the blocks’ transactions, but also verifying this verification process at a later time. The ZKP system provides great flexibility on top of the rigid base layer of Bitcoin and introduces a range of new applications for exploration.

3. Three Stages of State Proof Technology

ZeroSync is based on STARK proofs, which are relatively simple compared to other proof systems. STARK relies only on hash functions and polynomials, without the need for new cryptographic assumptions. Most importantly, there is no requirement for a trust setup.

To achieve Bitcoin proof, the official team is using the Cairo language created by StarkWare. Cairo is a language for creating provable programs. The technical team can create a program that verifies a single block, and a proof is generated only when the verification is successful. The official team is working closely with developers of all STARK tools that support ZeroSync. Implementing the chain state proof is complex, so the official team has divided it into three consecutive stages for release. As of now, the official team has completed prototypes for the first two stages.

1. Block Header Proof

Block Header: Each block contains the hash of the previous block and the timestamp of the current block, forming a chain structure that can be traced back to the first block in chronological order.

Similar to an SPV (Simplified Payment Verification) light client, the block header state proof only verifies the block header, proof of work, and difficulty adjustment. Additionally, it enhances the block header chain by constructing a Merkle tree on all block headers, making the inclusion proof of all blocks and transactions concise. This state proof is relatively simple, lightweight, and has low computational cost. The official team has already completed the block header proof system, and the block header verification process using the official website’s demo can synchronize the BTC node state in just a few seconds.

Demo link: https://zerosync.org/headers-chain.html

Rules for Verifying Block Header Chain:

When a light client receives block header information from the Bitcoin network, it needs to perform a series of checks to verify the validity of the blocks and the correct order of the chain. This process can be simplified into the following four steps:

1. Verify Proof of Work: The light client first checks if the hash value of the block is lower than the current target value, which is related to the mining difficulty of the block. If the hash value of the block is lower than the target value, it indicates that the proof of work for this block is valid.

2. Confirm Chain Order: The light client checks if the hash value of the previous block encoded in the current block is consistent with the actual hash value of the previous block. This step is used to confirm the correct order of the blocks in the chain.

3. Check the timestamp: The light client will check if the timestamp of the block is within a reasonable range. Specifically, the timestamp of the block cannot be lower than the median of the timestamps of the previous 11 blocks, nor can it exceed the network time plus two hours.

4. Confirm the correctness of the target value: Finally, the light client will check if the encoded target value in the block is correct. If the time interval between blocks changes, the new target value needs to be adjusted according to the timestamp.

These four steps ensure the validity of blocks in the Bitcoin network and the correct order of the chain, while preventing malicious nodes from cheating by modifying the target value.

Verifiable computation of block header:

ZeroSync implements the above rules in Cairo. The official implementation uses an open-source Cairo prover called Giza (and contributes to the implementation of recursive proofs) to prove the generated program and its execution trace. Due to the underlying STARK protocol, this protocol ensures that it is impossible to forge a proof of execution of a forged proof, and the size of a correct proof is hundreds to thousands of bytes, which can be verified on other blockchains, off-chain (such as for node synchronization), or even in another STARK proof.

To generate a proof for multiple consecutive block headers, the official implementation verifies them in batches in a Cairo program, as long as the underlying prover has sufficient processing power. Several batch verification proofs can be verified in a new STARK proof to create a proof for the entire Bitcoin chain.

2. Assumed Valid State Proof

This step mimics the “assume valid” option in Bitcoin Core. It verifies all consensus rules of Bitcoin except for transaction signature. More precisely, all witness data is assumed to be valid. In addition, this proof uses Utreexo to enhance the commitment of the UTXO set on the chain. The team completed the initial prototype of this state proof in February 2023.

The assumed valid block is an optimization technique used to speed up the synchronization of Bitcoin full nodes. This technique allows nodes to skip signature verification for certain blocks during the synchronization process, saving a lot of computational resources and time.

In practice, if a new full node knows that a certain block is valid when it starts (usually due to software default settings or user manual settings), then the node can skip signature verification and directly accept these blocks until it synchronizes to the known valid block. After that, the node will still perform normal signature verification for all blocks.

It should be noted that assumed valid blocks do not change the security model or consensus rules of Bitcoin, they are just an optimization. Even if the user does not set any assumed valid blocks, or the set assumed valid blocks are not on the longest blockchain, Bitcoin nodes can still work normally, although the synchronization speed will be slower.

3. Full Node Proof

Performing double SHA256 hash on the block header is the most computationally intensive operation in block header verification. Current Bitcoin blocks may contain over 2000 transactions. Therefore, fully validating these transactions is much more complex than just validating the block header, as each transaction requires a hash operation. We cannot verify a large number of blocks in one proof unless we use recursive proofs and also need to track a chain state (mainly composed of the set of unspent transaction outputs after each block), which needs to be updated in the verification process of each block.

Although STARK proofs are concise, making them easier to verify than corresponding blocks, the chain state must be a part of the public input for each proof, which can increase its size by several gigabytes. Dealing with the growth of the UTXO set is an important issue, as an oversized UTXO set can affect node performance and storage requirements. Handling a large UTXO set may require nodes to have more storage space and longer synchronization times, thus affecting the efficiency and scalability of the entire blockchain network.

To address this issue, we can use a technique called accumulators, specifically a technique called UTreeXO, which is a form of Merkle Mountain Range that allows for the swapping of tree nodes. This way, we can reduce the inputs and outputs required for each verification and only need to include a list of UTreeXO root hashes representing the entire UTXO set. If a transaction uses a specific UTXO, it can provide a membership proof along with it to the program, which doesn’t need to be included in the public input. This way, we can significantly reduce the size of the proofs and improve the efficiency and scalability of the Bitcoin network.

Proof mechanism:

Here, the technical team is trying to use a technique called Incrementally Verifiable Computation (IVC) to optimize the generation and verification process of proofs. IVC can be imagined as a method of breaking down a large task into multiple smaller tasks. In this example, each “task” is the generation of a proof for a block. In normal circumstances, a verification is required for each proof generated. However, this approach requires a lot of computing resources and time. Therefore, the technical team has proposed a new method: first, parallelize the generation of proofs for 10 blocks, and then compress these 10 proofs into a single proof. This compression process is like a tree, where each branch (proof) points to a central point (compressed proof). This way, the verification process only needs to be performed on this single proof, greatly reducing the complexity and time of computation. Then, this compressed proof can be used as input for the verification of the next block. This approach ensures that the generation and verification of the next proof can start while the previous proof is still running, thereby improving efficiency. Finally, to ensure data consistency, the verification process must check if all input states match the output state of the previous proof. This is like checking if each step’s result matches the expected result to ensure the correctness of the entire process.

Verifying all of Bitcoin’s consensus rules, including all witness data, is the most computationally expensive proof and requires significant optimization of the prover to be feasible. The first major official application in the future will be broadcasting state proofs from space via Blockstream Satellite, allowing people almost anywhere on Earth to synchronize with the Bitcoin blockchain immediately through full node proofs.

4. Summary:

ZeroSync can generate STARK proofs for the Bitcoin blockchain and aims to create a single proof for the entire chain. This proof, combined with the corresponding set of unspent transaction outputs (UTXOs), can be used to synchronize Bitcoin full nodes quickly. Currently, the official team at Starkware has reached a stage of “assumed-valid nodes,” but transaction script verification has not yet been conducted. The official team is working hard to achieve recursive validation. Initial test results were able to verify a block containing 108 transactions in approximately 5 million Cairo steps. ZeroSync is an open-source project that addresses scalability, accessibility, and privacy issues in the Bitcoin ecosystem through zero-knowledge proof technology. Once successful, it will have profound implications, as outlined below:

1. Improve the efficiency and scalability of the Bitcoin network: By using ZeroSync, Bitcoin network nodes can synchronize the latest chain state immediately without downloading and verifying all block data. This will greatly increase the synchronization speed of the Bitcoin network, allowing more users and devices to participate, thereby improving the scalability of the Bitcoin network.

2. Enhance the security and privacy of the Bitcoin network: ZeroSync utilizes ZKP technology to verify transaction validity without revealing any specific transaction information, greatly enhancing the privacy of the Bitcoin network. In addition, due to the non-interactivity of ZKP, even if there is malicious behavior between the prover and verifier, it cannot affect the correctness of the proof, thereby improving the security of the Bitcoin network.

3. Drive the development of the Bitcoin ecosystem: ZeroSync not only serves as a tool that allows developers to more conveniently develop and deploy Bitcoin applications but also enhances protocols, applications, and services in the Bitcoin ecosystem, driving its development.

As the project continues to be developed, Web3CN will continue to track ZeroSync and bring you exclusive updates and research consultations.

References:

https://geometry.xyz/notebook/A-light-introduction-to-ZeroSync

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