Addressing the Blockchain Trilemma with Zero-Knowledge Proof
In a distributed computing system, the Byzantine Fault Problem outlines the difficulty in achieving consensus among unreliable actors. Suppose an unreliable actor broadcasts a false value, say a transaction amount is way larger than the true amount. If this action impedes honest actors from agreeing on the true amount, a system-wide inconsistency occurs. Wouldn’t it be useful if actors can broadcast proofs guaranteeing their values’ validity? This may be done by revealing information within the proof that is only possible if the broadcasted value is true.
A written signature served as proof that a letter was written by the author. The problem is public knowledge of the signature makes it susceptible to forgery; it seems anything worth arguing for, like author identity, relies on representing private information within the proof. In digital applications, signatures are often public-private key pairs where the private key signs a message by hashing the message with key. The hashed value is attached to the message. The public key verifies the hash signature as only possible if the author was in possession of the private key. The act of solving a hard puzzle (creating the specific hashed value), made easy by secret information of the private key, lets a verifier believe the prover in this proof.
Generalizing from concealment of signatures, Zero Knowledge Proof (ZKP) lets a prover demonstrate knowledge of X without reveal. This family of techniques operates by obfuscating X by different equations into a set {X’} which can be freely communicated. A verifier receives {X’} from the prover, then poses a series of challenges using elements of {X’} whereby successful responses from the prover are only possible knowing the original X.
The need to represent knowledge without reveal arises when we consider anonymous blockchain participants collaborating in a trustless environment, e.g. proving someone was randomly selected for block proposal, proving the consistency for a block of transactions, and proving knowledge of transaction amounts for multiple transactions if the amounts are undisclosed.
A prover commits to a secret by hiding it from others while only presenting the obscured output called a cryptographic commitment. A proof of knowledge is created by a prover to convince a verifier knowledge of a secret. Successful verification of the proof implies the prover is honest and indeed knows the secret; conversely it is very hard for a prover to fabricate a verified proof without knowing the secret. A proof is zero knowledge if the verifier gained no additional information aside from the fact that the prover knows the secret, i.e. no information about the secret is leaked. A proof is interactive if the verifier challenges the prover over multiple rounds of communication. A non-interactive proof is verified by only examining the proof statement itself, and is more complex in construction.
Pentagon UFO video footage is a zero-knowledge proof of undiscovered flight knowledge. It is a proof insofar to replicate the same movements without UFO creator’s knowledge is nearly impossible, while convincing a verifier is to show it on camera. The footage is zero-knowledge: we learned nothing besides the prover knowing the necessary flight knowledge, we do not have the ability to recover the knowledge itself (though one may argue the maneuvers provide valuable scientific hints. The UFO’s teleportation / disappearance adheres to this property more). Lastly, the proof is non-interactive: we did not challenge the prover, the proof implicitly demonstrates the knowledge.
Scaling solutions among blockchain projects are also created with non-interactive, zero-knowledge proofs. ZKP solutions create a one-time cost during proof construction, while subsequent verifications are immediate for any verifier. Proofs are also memory compact. Because participants consistently verify the blockchain state, retrieve and store blockchain data, and reach consensus, a ‘prove once, verify always’ framework offers attractive scaling.
In the blockchain trilemma first presented by Vitalik Buterin, projects are hypothesized to cover only two properties out of three: security, scalability, and decentralization, and it is very hard to build a blockchain satisfying all three. ZKPs show a promising direction where security is maintained, while memory and compute costs are significantly lowered, leading to good scaling and better decentralization. For example, personal computers stand a better chance of contributing to consensus if computing costs are lowered.
Here are some projects that use ZKP implementations (in bold) to scale core mechanisms:
Algorand’s Pure Proof of Stake (PPoS) is an elegant consensus mechanism that is at its core a signature scheme with non-interactive, zero-knowledge properties. The block proposal committee consists of randomly selected Algo holders whose selection probability is weighted by their wallet balances. Random selection to be in the committee is dependent on user secret keys. Proof of selection, without secret key reveal, is enabled by Random Verifiable Functions.
In Ethereum 2.0’s zk-rollup, a layer 1.5 scaling solution, Zero-Knowledge Succinct Non-Interactive Argument of Knowledge or zk-SNARK, is a form of ZKP proving ETH participants correctly signed all transactions within a side chain block. zk-SNARK implicitly verifies transaction consistency within the block, obsoleting the need to dispute incorrect states while improving compression and computation. The block is published onto main chain in one transaction, reducing traffic.
Bulletproof is a newer zk-SNARK variant used to conceal transaction amounts in Monero. Similar to the zk-rollup, bulletproofs validate transaction quantities within a bundle of transactions meant to conceal sender-receiver relations called a ring. Since implementation in late 2018, bulletproof has lowered transaction memory by more than one magnitude and transaction costs from $1 to $0.07.
Verifiable Random Functions in Algorand
In Algorand, users run VRFs to discover their inclusion or exclusion in the block proposal and agreement committee for the next block. This self-selection process is analogous to drawing from a lottery, where the probability of inclusion is proportional to user stake in the network, i.e. their wallet’s Algo balance. The cost of checking a ticket’s winning status, hence a user’s committee membership, is negligible. To create a Proof of Stake consensus mechanism from first principles, we want to randomly sample users weighted by their stake. In a lottery system analogy, two questions arise:
1. How do we broadcast random values so participants may begin verifying their committee membership, i.e. what is our TV station to broadcast the lottery balls live?
2. After the winning numbers are shown, how do we verify but conceal the winners so an adversary cannot manipulate them?
To broadcast random values, say a random string X, the blockchain is the natural medium to do it. Each block contains a new random string according to which users may be drawn for the committee to propose the next block. If the random string selects by user ID, a function like
lottery( id, X ) = Y
Takes the user identity id and broadcasted randomness X as input, while outputting the outcome Y. To conceal the winners until block propagation, a secret Key SK may serve in place to determine the outcome while a public key PK helps observers to verify the outcome.
lottery( SK, X ) = Y
verify( PK, X, Y ) = 1 if and only if Y is a winning ticket, else 0
In fact, lottery systems use such signature schemes for anonymity and security.
Verifiable Random Function (VRF) is a non-interactive, zero knowledge proof that serves as a signature scheme here. A user P with secret key SK and public key PK may create a signature Y for a message X. Y is a pseudo-random string unique to the tuple ( SK, X ). Y’s uniqueness is a key property distinguishing VRF signature scheme from other signature schemes. With a protocol-wide message X, say a random string contained in the last block of a blockchain, one VRF signature per user is guaranteed. Item 2 in the list below explains why this is a necessary property.
The user uses their secret key and public random string to evaluate the outcome:
evaluate( SK, X ) = ( Y, ρ )
ρ serves as the proof-of-knowledge in a zero knowledge manner. The observer may verify with public knowledge PK, X, Y, and ρ:
verify( PK, X, Y, ρ ) = 1 if and only if ( SK, X ) evaluates to Y else 0
After user P generates Y with evaluate( SK, X ), an observer may check Y was indeed emitted by P with verify( ). Because the consensus is proof-of-stake, set a value S proportional to P’s stake. If Y in the interval [ 0, S ], then P was selected to be in next round’s committee.
Some implications are:
- Each block proposal committee samples a different number of Algorand users, independent of how previous committees were selected. An adversary cannot know committee membership (hence control the committee) under the honest majority assumption.
- In evaluate( SK, X ), X is a protocol-wide random string that is generated per block. Due to VRF’s unique signature property, each user has one possible ( SK, X ) input to create their ‘lottery ticket’ Y, so an adversary cannot attempt multiple inputs to receive a winning Y.
- Evaluate and verify are cheap functions to run. They enable a single RaspberryPi to participate in consensus, encouraging decentralization.
To expand on implication 3, VRF makes the Algorand protocol carbon neutral. In Sustainable Blockchain: Estimating the Carbon Footprint of Algorand’s Pure Proof-of-Stake, a number of valuable insights regarding PoW, PoS, and PPoS consensus mechanisms were made. The author puts forth energy and mining assumptions for Bitcoin, Ethereum, and Algorand to calculate their kilowatt-hour per transaction. Algorand expended a near-negligible amount of energy to transact, at 8 × 10e-7 kWh / transaction, due to its VRF powered consensus mechanism.
zk-SNARK
Zk-SNARK was introduced here. Later, a practical, easily verifiable implementation called Pinocchio was introduced. To self-study zk-SNARK, a careful reading of the article serieses in the following sequence is quite productive:
The first three parts of Why and How zk-SNARK Works by Maksym, then zkSNARKs in a nutshell by Christian Reitwiessner at the Ethereum Foundation, finally the complete tutorial culminating in the Pinocchio implementation with ellptic curves is this series by Ariel Gabizon.
Like an onion, the core SNARK is built on a verifier challenging a prover regarding knowledge of a specific polynomial’s coefficients. Building on that, homomorphic encryption over their communication imbues SNARK with ZKP notions of completeness, soundedness, and zero-knowledge. Finally, common reference strings between multiple verifiers and provers lead to non-interactivity.
The appendix section following the first resource by Maksym look to convince technical and non-technical readers that zk-SNARK machinery is intriguing and worthy of study.
zk-SNARK in ETH 2.0
In the Ethereum ecosystem, side chains such as the Uniswap decentralized exchange and decentralized applications (dAPPs) operate on plasma contracts; smart contracts that interact with the Ethereum main chain to reflect application activities. A major goal of ETH 2.0 is scaling the Ethereum main chain to handle transaction traffic from side chains. Transactions have frequently clogged the network in recent months, leading to higher fees for new transactions.
The obstacle in integrating side chain data is how transactions of the side chain may be speedily verified to be consistent with ETH transfers.
Vitalik Buterin mentions the zk-rollup proposal in The Dawn of Hybrid Layer 2 Protocols as a semi-layer 2 scaling solution. One idea (not zk-rollup) proposed to integrate side chain blocks tentatively, with a verification period during which a block may be challenged. Sounds familiar? This article on zk-SNARKS and zk-rollups notes the situation of a malicious validator who conducts a block withhold attack on the side chain, after which a user may detect and dispute. Disputes may delay future block creation and/or undo the disputed block.
Instead, we can include a ZKP into the block that verifies block consistency without a verification period. A zk-rollup aggregates multiple side chain transactions into a block containing a SNARK, and this appears on the ETH main chain as a single transaction. The key benefit is the existence of such a SNARK proof implicitly verifies the block content, and the SNARK is memory compact.
Vitalik’s 2019 post estimated the zk-rollup to improve ETH to 2000 tx/sec (a 30X improvement at the time of the article) while compressing each transaction to ~10 bytes.
Now in 2021, metrics from the 2.0 testnet may be drastically different. In another zk-rollup article Scaling Ethereum on L2: Optimistic Rollups and ZK-Rollups, a block of 1,000 transactions is reported to be verified in around 20 minutes. In the same article, an alternative scaling solution called Optimistic Rollup is explained. Lastly, the github repo to implement zk-rollup is here.
Bulletproofs in Monero
Monero transaction amounts and participants are private. To conceal participants, your output (out-going transaction) is bundled with past outputs in the network to form a ring, so any ring address may sign this spending to an observer, while receivers are hidden. Ring signature and stealth address are the respective technologies that enable these features, and is outside the scope of this article.
Bulletproof is a type of zk-SNARK. It is a non-interactive zero knowledge range proof. Bulletproof obfuscates transaction amounts in Monero. Being a range proof, the transaction amount is the secret, and it is proven to fall within a certain range. The Monero bulletproof ensures a ring of sent and received amounts sum to zero, with received amounts being positive. The true transaction amount is obfuscated by the sender (multiplication with an elliptic curve point) into a cryptographic commitment. Verification of the proof is a compact elliptic curve evaluation. Without cryptographic guarantees behind bulletproofs, an adversary generating such commitments with matching ring signatures may pass observer verification, leading to arbitrary spending in the network.
By clever algebraic properties, bulletproofs batch together efficiently for verification. One proof ( proving input / output transaction amounts sum to zero ) accounts for a large number of transactions, having proof size scaling logarithmically with the number of transactions. Its 2018 implementation decreased bytes per transaction, and transaction fee by orders of magnitude.
Conclusion
Hopefully this article has illustrated ZKP’s progress in the Blockchain Trilemma. In the Byzantine Fault Problem, ZKPs preserve the consistency property of a distributed computing system. By proving once, verify always, the proof framework bring down costs across blockchain protocols:
- Increased scalability, decentralization, and energy efficiency in Algorand consensus mechanism
- Skip dispute periods with zk-rollup, with more compact transaction storage and less side chain traffic in Ethereum 2.0
- verify transaction amounts for large number of transactions, allowing true amounts to be concealed in Monero
Appendix
Bulletproof Talkthrough
An overview of security implementations for Monero, and other properties: Monero: Sound Money, Safe Mode.
A video digging into bulletproof details: Dr. Sarang Noether Discusses Bulletproofs.
Proof of Knowledge of zk-SNARK (that is hopefully not zero-knowledge)
From first three articles in this article series by Maksym.
If verifier and prover claims to know the same polynomial poly(), the verifier may check prover’s knowledge by evaluating this polynomial at domain element x, send x to prover as a challenge, then check if the prover’s polynomial evaluation at x, poly(x), is correct. Slight differences between polynomial coefficients lead to different evaluations.
To build zero knowledge and non-interactivity onto this knowledge-of-polynomial framework, the verifier instead provides an evaluation of a co-factor polynomial t(x) assuming the relationship poly(x) / t(x) = h(x), where h(x) is an arbitrary polynomial containing co-factors in poly(x) not found in t(x). The prover responds with poly(x), h(x), to demonstrate knowledge of poly( ) this way.
There is a problem. After the verifier sends poly(x), the prover may spoof a response by constructing a polynomial p_fake(x) with the desired factorization p_fake(x) / t(x) = h_fake(x), or pick scalars as spoofed evaluations that satisfy this relation. Homomorphic encryption prevents this by encrypting values, e.g. the point of evaluation x, while permitting the encrypted values to be added or multiplied. Encryption E(x) have the form
E(x) = gˣ mod m
Where x is the secret to be encrypted, g the generator of a cyclic group, and the modulo operation mod is what makes the decryption of E(x) back into x difficult (in cryptography this is the famouse discrete logarithm problem).
The verifier samples a secret evaluation point x, computes t(x), and transmits encrypted powers of x: { E(x⁰), E(x¹), …, E(xᵈ) } to the prover. Without knowledge of x, i.e. without knowing where polynomial evaluation should occur, but with the means to perform arithmetic on these encrypted powers of x, an honest prover is able to use their knowledge of poly() coefficients to construct an analogous, encrypted evaluation of poly():
E( poly(x) ) = (E(x⁰)^C₀)(E(x)^C₁)…(E(xᵈ)^Cd)
In other words, the polynomial, through its coefficients, encodes specific relations preserved by the homomorphic mapping E( ). If the prover knows the polynomial, they must demonstrate knowledge of these relations. Equality holds after encryption if the coefficients { C₀, …, Cd } are correct. Likewise, the remainder polynomial h may be evaluated on the encrypted version of x. E( poly(x) ) and E( h(x) ) are sent back to the verifier where checking
E( poly(x) ) = E( h(x) ) E( t(x) )
Is just as good as checking poly(x) = h(x) t(x).
In this way, the prover’s spoofing method described earlier becomes invalid. Moreover, because polynomial arithmetic has moved to an encrypted space via the homomorphic mapping E(), the prover can obfuscate information of poly( ) by exponentiating his response E( poly(x) ), E( h(x) ) with a random value, while still satisfying the verifier’s equality check. The verifier gained no additional knowledge of poly( ) from this interaction, making it zero knowledge. A detailed explanation.
Non-interactivity is possible with common reference string (CRS) (detailed explanation here). Its key insight is that verifier secrets, and powers of the secret, after encryption, can be published as a stand-alone problem, this is the CRS and occurs during the protocol setup. Multiple participants may combine their CRS, hence their encrypted secrets and encrypted powers of secrets, into a composite CRS. An observer who trusts at least one verifier during the creation of the composite CRS may trust the proof procedure.
A prover, instead of interpreting the CRS as a composition of ‘locks’ to be solved in reverse order (computing the encrypted polynomial for the last verifier in the single verifier case, then repeat for the second to last verifier), instead generates one large encrypted polynomial using the encrypted powers of secrets from all participants and the prover’s polynomial coefficients (the knowledge to be demonstrated). This encrypted polynomial, representing the effort of the verifier group, is evaluated all at once ( obfuscation is added to achieve zero knowledge). The resulting polynomial and remainder polynomial, in their encrypted forms, is proof to any interested verifier.
A pre-bitcoin ‘cryptocurrency’
Peppercoin was developed by Algorand founder Dr. Silvio Micali.
