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

ZeroSync is a Zero Knowledge Proof system developed by Starkware for Bitcoin.

Author: [email protected]

1. Preface

Zero-knowledge proof (ZKP) brings a rapid transformation to the scalability and privacy of blockchain. So far, the Ethereum community has been widely applying this technology and has made rapid progress. According to official data from L2beat, zksync and starknet, the two Layer 2 Ethereum chains based on zk-rollup technology, have a total TVL of 538 million as of now. It is worth noting that dYdX, a decentralized exchange based on the zk-rollup technology introduced by starknet, has a TVL of 338 million.

Currently, BTC has a market share of 46.69% and ETH has a market share of 18.39%. However, zero-knowledge proof is still virgin territory for Bitcoin. In addition, according to data, the overall block size of BTC 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, aims 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 in terms of commercial value, market demand, and technology.

• In-depth Analysis of ZeroSync Starkware’s Zero-Knowledge Proof System Developed for Bitcoin
• 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?

2. Introduction to ZeroSync

ZeroSync aims to solve 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 instantly, a toolkit for developers in the BTC ecosystem, and enhances protocols, applications, and services in the BTC ecosystem through zero-knowledge proof (ZKP). The technical team is exceptionally strong, and Andrew Milson, a member of the team, 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 cryptographic technology fields.

It is well known that setting up a Bitcoin node may be simple, but it requires downloading a large amount of block data from other nodes on the network, which usually 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 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 instantly. By leveraging zero-knowledge proof, anyone can verify the latest state of the chain immediately. The proof will not be affected by the inherent size of the chain itself. When the next block is mined, any prover can incrementally extend the proof to the previous state.

The significance of this proof system lies in its seamless connection with the immutability of Bitcoin. ZeroSync will serve as a tool to fill the aforementioned gap and provide the correct verification of the Bitcoin blockchain. It functions similar to a full node implementation, which not only obtains the final state after applying all the transactions in the blocks but also allows verification of this process at a later time. The ZKP system provides great flexibility on top of the rigid base layer of Bitcoin and introduces a series of new applications for exploration.

3. Three Stages of Zero-Knowledge Proof Technology

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

To achieve Bitcoin proof, the official team is using the Cairo language created by StarkWare, which is a language for creating verifiable 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 the developers of all STARK tools that support ZeroSync. As the implementation of state proof is very complex, the official ZeroSync team has divided it into three consecutive stages for rollout. So far, the official team has completed the prototypes of 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 SPV (Simplified Payment Verification) clients, the block header state proof only verifies the block header, the proof of work, and the difficulty adjustment. In addition, it enhances the block header chain by building a Merkle tree on all block headers, making the inclusion proof for all blocks and transactions concise. This state proof is relatively simple, lightweight, and has low computational costs. 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 BTC node status in just a few seconds.

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

Block Header Chain Verification Rules:

When a lightweight 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 the Proof of Work: The lightweight 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 is lower than the target value, it means that the proof of work for this block is valid.

2. Confirm the Order of the Chain: The lightweight client checks if the hash value of the previous block encoded in the current block matches 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 lightweight client checks if the timestamp of the block is within a reasonable range. Specifically, the timestamp of the block cannot be lower than the median timestamp of the previous 11 blocks, nor exceed the network time plus two hours.

4. Confirm the Correctness of the Target Value: Finally, the lightweight client checks if the target value encoded in the block is correct. If there are changes in the time interval between blocks, the new target value needs to be adjusted based on the timestamp.

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

Verifiable Computation for Block Header Validation:

ZeroSync achieves the above rules by implementing them 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 traces. 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 a few hundred to thousands of bytes, which can be verified on other blockchains, off-chain (for example, for node synchronization), or even in another STARK proof.

To generate a proof for multiple consecutive block headers, the official implementation batches their verification in a Cairo program, as long as the underlying prover has sufficient processing power. The entire Bitcoin chain can be proven by verifying several batch verification proofs in a new STARK proof.

2. Assumed Valid State Proof

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

An assumed valid block is an optimization technique 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 significant amount of computational resources and time.

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

It should be noted that assumed valid blocks do not change Bitcoin’s security model or consensus rules; 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 function normally, albeit with slower synchronization speed.

3. Full Node Proof

The double hashing of block headers using SHA256 is the most computationally expensive operation in block header validation. Current Bitcoin blocks can 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 a proof unless we use recursive proofs and also need to track a chain state (mainly composed of the Unspent Transaction Output set after each block), which needs to be updated during the validation process of each block.

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

In order to solve this problem, we can use a technique called accumulator, specifically a technique called UTreeXO, which is a range of Merkle mountains that can exchange tree nodes. In this way, we can reduce the input and output 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 be provided to the program along with a membership proof, which does not need to be included in the public input. This way, we can greatly reduce the size of the proof, 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 the proof. IVC can be imagined as a method of decomposing a big task into multiple small tasks. In this example, each “task” is to generate a proof for a block. Normally, each time a proof for a block is generated, verification is required. However, this method requires a lot of computational resources and time. Therefore, the technical team has proposed a new approach: first, generate proofs for 10 blocks in parallel, 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). In 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 next proof generation and verification 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 previous output state. This is like checking if each step’s result meets expectations to ensure the correctness of the entire process.

Verify all Bitcoin consensus rules, including all witness data. This is the most expensive proof in terms of computation, and it requires a lot of optimization of the prover to be feasible. The first major official application in the future will be to broadcast state proofs from space through Blockstream Satellite, so that people in almost any part of the world can synchronize to the Bitcoin blockchain immediately through full node proof.

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 UTXO (Unspent Transaction Output) set, can be used to synchronize Bitcoin full nodes quickly. Currently, the Starkware official team has reached the stage of “assuming valid nodes”, but transaction script verification has not yet been conducted, and the official team is working hard to achieve recursive verification. Initial test results can verify a block containing 108 transactions in about 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 significance, as shown in the following points:

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

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

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

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