Using zero-knowledge proofs, ZeroSync seeks to radically reduce the computational costs of bootstrapping a fully-validating Bitcoin client.
This is an opinion editorial by Shinobi, a self-taught educator in the Bitcoin space and tech-oriented Bitcoin podcast host.
Zero-knowledge proofs (ZKPs) are something that have been discussed in this space for over a decade. Even Satoshi Nakamoto themselves was aware of them as a primitive that could be used, and the idea of applying them to Bitcoin was discussed as early as 2010 when they were still active.
In my mind, they have always been one of the potential “long-term” features of Bitcoin that never really had a solid, concrete implementation but could wind up panning out and creating an enormous amount of value and utility for the work put into implementing them. Who wouldn’t think that cryptographically proving that some statement is true, or that you possess some information without revealing it, is very valuable? Especially when you can do so for very complicated things with relatively small proofs?
Complicated and large smart contracts/scripts to lock bitcoin with in the end necessitate putting proportionally-large pieces of witness data on the blockchain in order to spend those coins. That can either be literally large amounts of data, or it can also be data that is expensive to compute and verify. This is a conventionally-held tradeoff of blockchains: The more complicated the condition you want to require to spend coins, the more expensive to verify or more data is required to spend them.
ZKPs have always been held up as a way to change that, allowing highly-complicated script conditions to be proven with a small or constant amount of data that, when verified, shows definitively that those conditions were met. This is because of the fundamental asymmetry between proving and verifying using ZKPs.
To give a concrete example that is as simple as possible, ring signatures are a very basic form of ZKP. The idea is to provide a signature provably made by one key within a large group of keys without revealing exactly which one. By properly defining a signature algorithm, a single signature can be produced that can be verified against the entire set of public keys and shown to have been produced by one of them but obscuring which one.
That, at a very high level, is how ZKPs work. You construct a protocol to prove something, that includes a way for the person asserting a fact to provide a proof and the person to which they are asserting it to verify it. In the case of ring signatures, it is a signature algorithm that validates against a set of public keys without specifying which one. That is the key point: You prove something without actually revealing the information that would conventionally prove it (in this case, a signature from a single public key).
Table of Contents
After years of discussing the possibilities, progress is finally being made on bringing ZKPs to Bitcoin in the form of the ZeroSync project. The interesting part though is it has nothing to do with locking or spending coins. There isn’t any ZKP OP code coming, or any type of way to lock coins on chain using them. It’s being applied to helping full nodes accomplish a much faster initial sync.
This is a big undertaking though and is not something that is going to happen all at once. As I said above in describing ring signatures, a ZKP requires a protocol be designed for each specific thing you are trying to prove. There is no “zero-knowledge proof” that can arbitrarily prove anything, because each one needs its own unique proof protocol to sufficiently validate a specific type of computation or assertion about some kind of data.
ZeroSync is working on iteratively constructing three proofs that will, when finished, provide a full verification of the historical blockchain without requiring a user to actually download and process it. The great part about this is that absolutely no consensus change to the Bitcoin protocol is required to accomplish this. Everything happens simply at the application level, i.e., in the software you run. It still validates and implements the exact same consensus rules as a conventional Bitcoin node. When complete, anyone can simply choose to use such a ZeroSync node and be sure the UTXO set they download is valid. Or you can just keep running Bitcoin Core and fully validate everything in the conventional way.
Block Header Proofs
The first proof the ZeroSync team is working on, which should by this time be released, covers the validity of block headers. It proves that each block in the chain correctly met the difficulty requirement at the time, and tracks each difficulty change to ensure that every block meets the appropriate target. This also will introduce a huge benefit for Simplified Payment Verification (SPV) wallet architecture in the process.
Each Bitcoin block is essentially a Merkle tree of every transaction in the block, plus the header that contains some other data and the root of that Merkle tree. ZeroSync’s block header proof will, in the process of construction, also apply such a Merkle tree to each individual block header in the chain. So, the same way that every transaction is committed to with a Merkle tree, leading to a single hash, every block in the blockchain will be committed to a single hash using a Merkle tree. This will allow much more compact SPV proofs. Currently, to implement SPV, a user must keep a full copy of every block header in the blockchain and, when provided a transaction and the Merkle tree path from it to the block header, can use that to verify that it was actually committed to in a block.
With block header proofs, users wouldn’t even need to have a copy of the block headers to verify that a transaction is committed to inside of the blockchain. They simply add on a Merkle path from the block header that the transaction is in to the root hash of the current blockchain Merkle tree and it provides the same security guarantees combined with a ZKP of block header proof validity.
Verifying Block Contents
The second proof is focused on the actual validity of the contents of the block, however, like the Assume Valid function of Bitcoin Core, it does not prove the validity of the witness data. It will check and verify transaction size limit, coin inflation rules, etc., but doesn’t provide a proof that the signatures, hash locks and other witness data are correct. This proof, however, will incorporate Utreexo in order to integrate the UTXO set at each block height into the overall ZKP protocol for the chain.
The first proof would simply show you that the block headers are valid, but that says nothing about the coin supply or the UTXO set. This second proof would allow a UTXO set to be delivered to a user with a ZKP that proves all of the block headers leading to that UTXO set are valid, as well as including a commitment to each UTXO set and all changes to it proving that each transition from one to the next is also valid. This would allow for a full sync up to the Bitcoin Core default Assume Valid height with just the UTXO set at that block height and a tiny proof, all with the exact same trust model as downloading all of that and verifying the full blocks directly.
Verifying Every Piece Of Witness Data
Lastly, the final proof will incorporate both the ZKP for the block headers and build on top of the ZKP for Assume Valid to include proving the validity of every piece of witness data in the historical chain. After this stage, technically speaking, a node using the final ZeroSync proof system will actually be able to bootstrap with a single proof and a UTXO set with a stronger verification model than Bitcoin Core by default.
Normally, Bitcoin Core uses the default Assume Valid block height to skip witness validation for any block before it (though the user can override with assumevalid=0 and validate witnesses for every block), but a ZeroSync node would have a correctness proof for every block’s witness data.
The only issue with this last proof is that the computational complexity to actually construct it is much higher than that of the previous two. Verifying a proof is simple and quick, requiring only the ZKP and verifier, but constructing it actually requires taking the full, raw data that would constitute a conventional proof (in this case, the entire historic blockchain) and actually processing it to construct a ZKP for it. Adding the witness data into the proof currently is very expensive. In order to achieve this roadmap goal a lot of optimization is going to be required. But, let’s say that it proves intractable to do so. This project would still provide a massive amount of value in allowing users to “zero sync” up to the default Assume Valid block height and then conventionally verify the rest of the chain from there to the tip.
Reducing Bitcoin’s Computational Costs
If its roadmap is successful, this project could have a massive effect on reducing the computational costs for Bitcoin users to bootstrap a fully-validating Bitcoin client. Given that the blockchain is currently almost 500 GB in size, there is a very restrictive cost that prevents a large number of users from running a validating client. You need to have the bandwidth available to download it, and in many parts of the world, bandwidth is still prohibitively expensive. You also need a device powerful enough to process that data, and in many parts of the world, people have nothing but a smartphone in terms of digital devices that can connect to the internet.
ZeroSync could bring that cost down to a few gigabytes for the UTXO set and a ZKP proof so small that it could fit on a 1.44 MB floppy disk. And it requires no consensus changes or forks whatsoever to do it.
Now, to wrap up, I want to make a kind of cheeky point: ZeroSync is built utilizing the Cairo language developed by Starkware, a Turing-complete language that can be used to build zero-knowledge systems for arbitrary computations. Starkware is a company developing ZKPs for the Ethereum ecosystem, specifically developing zero-knowledge rollups as a second layer solution. ZeroSync building out a ZKP-verified syncing client for Bitcoin might wind up being the first time a real material development from an altcoin actually produces a valuable improvement that folds back into the Bitcoin ecosystem.
ZKPs can wind up being a very powerful tool for Bitcoin even without incorporating them into the consensus layer, or using them as a way to actually lock and spend bitcoin. Hopefully, ZeroSync is able to achieve its roadmap goals and produce the quick sync client its team is working on. Afterwards, there’s even more that could be done to deploy ZKPs in the Bitcoin ecosystem besides bootstrapping a node.
This is a guest post by Shinobi. Opinions expressed are entirely their own and do not necessarily reflect those of BTC Inc or Bitcoin Magazine.