# A light introduction to ZeroSync

As easy as setting up a Bitcoin node may be it requires downloading a massive amount of blocks from other peers in the network - often for multiple days. This process is necessary to ensure that the newly spun-up node eventually holds the correct state of the Bitcoin chain. However, by utilizing zero-knowledge proofs you would able to verify the latest state of the chain in an instant. At least as long as someone supplies such proof...

[ZeroSync](https://github.com/ZeroSync/ZeroSync) tries to fill the aforementioned gap as a tool to generate a proof attesting to the correct validation of a chain of Bitcoin blocks. It resembles a full node implementation that does not only yield you the final state after all transactions of the blocks were applied but also a way to verify this validation process at a later time.

We are first going to look into the light client version of ZeroSync that only validates block headers (which is everything not related to transactions) before we move on to the measures taken to allow the validation of entire blocks.

## Bitcoin's Block Header Validation
The chain of block headers provides everything a light client needs to validate the proof of work and the correct arrangement of blocks in the chain. When receiving a block header the light client checks it against Bitcoin's consensus rules:
1. The block hash has to be below the current target - a number that represents a hash with a certain amount of leading zeros. Often also referred to as the difficulty.
2. The encoded previous block hash of the current block is indeed the previous block's hash.
3. The block's timestamp is not below the median of the preceding eleven blocks' timestamps and not above the network time plus two hours.
4. The correct target is encoded in the block. In case a retarget happened the new target was correctly derived from the epoch timestamps.

While rules 1 and 2 directly enforce the correct formation and mining of the chain, rules 3 and 4 are required so that no one can adjust the target to their own will. Otherwise, they were able to mine new blocks at a faster rate than honest nodes by increasing the target (which can be done by decreasing the epoch's timestamp delta) or they could decrease the target to make it artificially harder to mine blocks.

## Verifiable Computation for Block Header Validation
By implementing the above rules in [Cairo](https://www.cairo-lang.org/), a language used to create provable programs, we can create a program that validates a single block and can generate a proof for it if, and only if, the validation was successful. We make use of an open-source prover for Cairo called [giza](https://github.com/maxgillett/giza) (and contribute to its implementation for recursive proofs) for proving the generated program and its execution trace. Due to the underlying STARK protocol, forging a proof of execution that attests to the correct validation of the block header is infeasible. A correct proof has a size of a few hundred kilobytes and can be verified on other blockchains, off-chain (e.g. for node syncing) or even in another STARK proof.

To generate a proof for multiple successive block headers we can batch their validation together in a [single Cairo program](https://github.com/lucidLuckylee/LightSync) as long as the underlying prover machine has enough processing power. A proof for the entire Bitcoin chain can be created by verifying several batch validation proofs in a new STARK proof - making use of so-called [recursive proofs](https://medium.com/@starkware/recursive-starks-78f8dd401025).


<p style="text-align: center;"><i> Batching batches: </i>Multiple batch proofs can be reduced into a single proof by verifying them recursively.</p>

## Approaching Entire Blocks
Hashing the block header twice with SHA256 is by far the most expensive operation of the block header validation. Current Bitcoin blocks can contain more than 2000 transactions and, therefore, validating them in a full node fashion is magnitudes more computationally expensive than validating the header - every transaction has to be hashed. We can no longer validate reasonable batches of blocks in a single proof without proof recursion and additionally have to keep track of a chain state (mostly composed of the UTXO set after each block) that has to be carried over between every block's validation.

### Coping with the UTXO Set
While STARK proofs are succinct such that they are easier to verify than validating the respective blocks, the chain state has to be part of each proof's public input and would blow up its size by multiple gigabytes. The Bitcoin UTXO set has two interesting properties: First of all, UTXOs can be later deleted from the set (a block uses them in a transaction) and each block only needs the information of a small subset of the UTXO set (because there is only a certain total amount of transaction inputs in a block). Therefore, we are using an accumulator - specifically [UTreeXO](https://dci.mit.edu/research/2019/6/6/utreexo-a-dynamic-hash-based-accumulator-optimized-for-the-bitcoin-utxo-set), a form of Merkle mountain range that can swap tree nodes and, by doing so, reduces the root recalculations after removing a leave from the UTXO set - to handle succinct state in- and output for every validation run. The state then only includes a list of UTreeXO root hashes that represent the whole UTXO set. In case a transaction in the currently validated block uses a specific UTXO it can be fed to the program via Cairo's hints (which are **not** part of the public input) together with a membership proof.

### Proof Scheme
We want to start by creating an own proof for every block so we have to find a way to eventually compress them as we did with the batches of the light version of ZeroSync. For now, this will be done in the most reduced and straightforward way: Every proof will be verified by the next one - essentially a tree with width one - and we will refer to this as incrementally verifiable computation (IVC).


<p style="text-align: center;"><i> Incrementally verifiable computation:</i> There is a recursive verifier attached to the block validation program that verifies the previous chain proof. Every proof includes the validation of the current block and the verification of all previous blocks. </p><br>

Note that this can be improved to be more dynamic and to allow the generation of proofs for subsequent blocks in parallel. We could replace each IVC step (so block validation) with a recursive proof tree over multiple block validation proofs and then only call the recursive verification part of the IVC step after the tree has compressed, e.g., 10 blocks into a single proof. These 10 blocks could have been generated in parallel, by simulating the block validation program written in Cairo by a different program that is not running in the Cairo virtual machine - so there is no proof of execution, but we can get the resulting output state. This state can be fed into the next block's validation while the current validation may still be running. Of course, the recursive verification in the tree would have to check that eventually all input states match the previous output state.

## Conclusion
We introduce ZeroSync a work-in-progress tool to generate STARK proofs of the Bitcoin blockchain with the first milestone to create a single proof for the entire chain. This proof in combination with the corresponding UTXO set can be used to instantly sync a bitcoin full node. At the current state the Bitcoin logic is implemented up to the point of an assume-valid node, so no transaction script validation yet, and we are working towards the recursive verification. The first benchmarks look promising and we are able to validate a block with 108 transactions in around 5 million of Cairo's steps.
ZeroSync is an open-source effort so do not hesitate to check out and contribute to [the repository](https://github.com/ZeroSync/ZeroSync) and [work in progress website](https://zerosync.org/) yourself. For further questions or remarks get in touch with [me](https://twitter.com/lucidLuckylee/) or [ZeroSync](https://twitter.com/ZeroSync_) via Twitter. We would love to hear from you!