SNARK-relay is a first shot at proving Bitcoin transaction inclusion inclusion on Ethereum more efficiently.
Github repo: https://github.com/dec3ntral/snark-relay
Quick Overview (more details soon)
We use zkSNARKS are used to verify inclusion proofs in Bitcoin’s transaction Merkle tree. Specifically, we prove that a given set of double SHA256 hashes is indeed the correct path to a leaf in the Merkle tree containing all transaction identifiers in a block.
Our implementation supports Merkle trees up to a depth of 11 (can be extended to more), i.e., up to 2048 transaction per block.
We use the, ZoKrates toolkit to generate both prover and Solidiy verifier.
Performance
Our construction requires ~975k constraints.
The main bottleneck thereby is Bitcoin’s double SHA256, and the fact that we have no means to easily break out of a loop (which would allow to save costs on shallow trees).
Verification in Solidity has a constant cost of 600k gas.
Comparison
If we compare the SNARK approach to native Merkle tree verification in Solidity, we observe that the latter is currently cheaper: ~80k gas for a tree of depth 1, ~200k gas for a tree of depth 11.
The main difference however is the following: SNARK-relay costs 600k per SNARK. The native Solidity implementation costs up to 200k gas per verified transaction.
Outlook and Future Work
Following the evaluation, our goal is to pack more inclusion proofs into a single SNARK to amortize costs, possible using recursive composition.
After that, we want to try to prove sequences of PoW block headers (~175k gas per header in pure Solidity) and parts of Bitcoin’s spend script for UTXOs (~120k gas per parsed transaction in pure Solidity).
Acknowledgements
Huge thanks to Daniel Perez and Dominik Harz, with whom we developed this together.
This project was developed during the hackathon at the Zero-Knowledge Proofs Workshop in London, June 17th 2019, hosted by Binary District.
Relevant Links
- https://github.com/dec3ntral/snark-relay
- https://github.com/Zokrates/ZoKrates
- https://binarydistrict.com/events/workshop/development/zero-knowledge-proofs-workshop