This week’s article will examine one of the more technical features of blockchain technology, which is often mentioned in the blockchain space, but only technical developers typically care about—zk-proofs. Recent breakthroughs in BSV have now made the technology open and accessible, so I hope to spend a bit of time explaining what they are and why they are significant for the whole industry.
What are ZK-proofs?
Besides just sounding like a very cool buzzword, zk-proofs (or zk-SNARKs as they are sometimes generally called) are basically a way in which a party (or prover) can prove their knowledge of something secret to a second party (a verifier) without revealing the actual thing in public. As such, this allows a buyer to buy a secret from a seller trustless if the purchase itself can be conducted in an atomic manner.
This turns out to be the fundamental keystone of all smart contracting technology on blockchains, as it allows for total privacy for smart contracts while at the same time transparency for the actual transactions.
Some blockchains like ZCash use ZKPs as part of their base protocol to enforce things like fixed inflation, coin supply, and distribution schedule, while others enable using ZKPs in their native scripting language, such as BSV and ETH1.
Even though ZKPs is a technology that has been around since the 1980s, their practical use on blockchains has been fraught with difficulties, mostly due to the tradeoffs in size and computational resources needed to generate and use them effectively. Traditional zk-SNARKs required a trusted ‘setup’ phase which, if compromised (via secrets leaking or a corrupted key), would compromise the whole system in a way that is difficult to detect. In addition, common implementations required significant computational resources to generate the proof (to the order of >10s seconds and >100MB to a couple of gigabytes of memory). All of these really prevented its use on Bitcoin, given the scaling limitations of BTC2 in terms of transactional block sizes and also the impracticality of having to wait 20s for the generation of proof for each transaction.
That said, the potential benefits of zk-proofs far outweigh their practical limitations, which is why many projects in blockchains are currently working on ways to deploy zk-proofs while mitigating their limitations.
Such benefits become clear when you consider the core goal of any blockchain: decentralization or the distribution of the calculation logic in the processing of smart contracts (in bitcoin, these are called simply predicate scripts or payment conditions). In theory, if zk-proofs were implemented as the base consensus protocol of a blockchain, then it would effectively become something like ZCash, and projects like Ethereum wouldn’t have to have every node calculating the same thing redundantly to be certain that a validator did not ‘cheat.’ Instead, a prover could just calculate the result of a contract execution, embed the zk-proof, and be done—at least in theory.
In practice, because of the sizes of the witness (the proof), it becomes increasingly prohibitive due to blockchain economics for platforms that cannot scale by volume, such as ETH, where the more complex (and thus useful) zk-proof applications would become too expensive to run due to gas fees that scale with the size of the data to be put on-chain and the amount of computation required. This has severely limited the application of zk-proofs on Ethereum. On BTC, the problem is that they have a hard limit on the size of the transactions and blocks, which also puts positive pressure on the cost of embedding such proofs onto the public blockchain.
However, with BSV, there are no such limitations, and thus, we have seen some significant breakthroughs in the development of native implementations of zk-proofs in recent months.
SCrypt, a project which pairs a Typescript-like smart contracting language and compiler to Bitcoin ASM (op-codes), has been pioneering the work on zk-proofs and their derivatives on BSV. What started as a theoretical proof of concept a year ago has become a plethora of tools and examples of leveraging the power of zk-proofs on bitcoin. I’ll briefly go over the milestones here in chronological order. Feel free to use this as a ‘reading list.’
1) November 2, 2021 — First, outlines how to theoretically construct a ZKKSP where proof can be used to have an outsourced party help a buyer find a private key that results in the desired vanity address. This can be done without the seller of the information knowing the actual private key (which would defeat the purpose) while at the same time allowing the buyer not to have to do the computational work themselves to derive the key for the desired vanity address.
2) August 6, 2022 — Almost a year later, a massive breakthrough in creating recursive ZKPs can be applied to problems in which a total aggregate problem can be solved in small steps. Each step then can produce an equivalently small ZKP, which just proves the ‘change’ from the previous solution. In this way, instead of calculating a very LARGE single proof which would be prohibitive in many ways as outlined above, a proof can be ‘additive .’This is also useful for problems in which the answer is not discrete, but lies on a continuum and can be infinitely refined, such as optimization problems, where the buyer is willing to pay for a sufficiently ‘good enough’ solution. Work then can be paid for incrementally instead of being a ‘winner-take-all’ form. Work can be distributed among a pool of workers, each contributing their part and being paid for their partial contributions. For example, calculating a Fibonacci series or finding successive digits of pi, or running BitTorrent!
3) November 10, 2022 — Sudoku puzzle! Named as the first ‘practical’ application of ZKPs in bitcoin (that includes all bitcoin chains), last week, sCrypt released the application of a ZKP to outsource the solution for a Sudoku puzzle. While spoken about in theory for the last year or more, this is finally something to see the code in reality.
With this example, developers can now, in a trustless manner, outsource general problems to the public as a stateless bounty, and the provider of the solutions can safely collect the bounty in a way that does not require any escrow or intermediaries. This deserves a bit of pause and reflection because this is what people have been trying to get to work for a while.
An improvement over a previous implementation which required a setup process between a buyer and the seller (which practically speaking means it couldn’t be easily used as a pseudonymous bounty), this version can be done in a single bounty transaction posted by the buyer, and collected by a pseudonymous seller in a single transaction.
While this example uses Sudoku as a puzzle to solve, any puzzle which can be easily verified can use this method.
Think of traveling salesmen solutions for logistic companies or solving chess endgames for profit! Or even something like putting a bounty on creating a more efficient sorting algorithm? Or as a way to incentivize genetic algorithms to evolve into doing something useful like boolean operations? (Both of which have simple algorithmic methods of verifying that they are indeed valid solutions).
4) November 14, 2022 — Proof of Reserves — Given the recent collapse of Defi giant FTX, many companies have started talking about implementing proof of reserves to show to the world that it has control of the assets that it claims they should and additionally everyone that it owes liabilities to can ‘be counted’ to ensure that their assets cover all of their liabilities. This outlines how it might be done on Bitcoin.
5) November 26, 2022 — Pay for Decryption key — the Swiss army knife of ZKP!
This one is the true multi-tool of blockchains… the ability to pay for a private key in a trustless manner. The applications of this would likely deserve an article on its own. Unsavory hackers have exploited this use case in the past with attacks such as cryptolocker where a hacker encrypts all your private data on your computer and demands a ransom to allow you to decrypt it again by selling you a private decryption key. Adding insult to injury, for many victims who paid the ransom in bitcoins, the hacker would still refuse to deliver the private key, leaving the victim out of pocket, and with data loss. With the ability to trustlessly exchange a private key, both by confirming that the seller has control of the needed key and that the payment for the key cannot happen if the key is not released at the same time, this allows for many use cases, from trustless digital market place exchanges to inheritance and digital legacy planning. This is the generic “escrow” smart contract that can be used to construct most other complex contracts.
6) Bitcoin zkBattleship — Finally, any discussion of online gaming using ZKPs wouldn’t be complete without an example where not requiring an ‘oracle’ of knowledge to know the state of the shared game board, such as Battleship, really shines. These kinds of games can be extended to most card games where there is a ‘dealer’ state, namely, who keeps track of which players have which cards? This example shows its implementation using the Battleship game, where the blockchain manages the ‘game state’ in a trustless manner.
As can be seen by the recent rapid-fire posts from the SCrypt team, the technology is fast developing and has yet to mature, along with the development of easier tools to help fledging developers get started on writing smart contracts on bitcoin, which use ZKPs. But the floodgates are now officially open. Let the games begin!
/djc
Wall Street Technologist
[1] Notably missing is BTC, as they disabled the needed language features
[2] Also, as mentioned before, BTC Core has not re-enabled the original Bitcoin 2009 op-codes to make this possible.
Watch: The BSV Global Blockchain Convention presentation, Smart Contracts and Computation on BSV
New to blockchain? Check out CoinGeek’s Blockchain for Beginners section, the ultimate resource guide to learn more about blockchain technology.
