Four fun approaches to blockchain scalability I am not a zksnark expert. What follows may be rubbish and any errors are mine. Many thanks to for reviewing this post. I recommend his . Also thanks to from Zcash for pointing several subtleties I overlooked. Disclaimer: Chris Reitwießner introductory article on zksnarks Ariel Gabizon Definition Let be a program which takes two inputs. The first input is meant to be public. The second input is a witness which can be kept private. We use for an output of . P i w o P Given a program , an input and an output , if a prover knows a witness such that then the prover can produce a proof where: P i o w o = P(i, w) (space density) The proof is very short (just a few hundred bytes even for a very large program; e.g. Zcash achieves 288 bytes) (time density) The proof verifies in time linear to the lengths of and i o (zero knowledge) The proof leaks nothing about the execution of or the contents of other than the existence of P w w Such proofs are called zksnarks. (As a technical aside, zksnarks are only known for verifier programs which run in polynomial time to the lengths of and . We are also assuming that the security parameter “lambda” is fixed.) P i w Intuition I like to think of zksnarks as simultaneously the equivalent of hashes and signatures for computation (extending the two cryptographic primitives beyond data). Like hashes, zksnarks “compress” computation into a short and quick to verify fingerprint. Like signatures, zksnarks “attest” for the validity of computation. cryptographic Below we show approaches using zksnarks to address scalability. These are mostly theoretical given today’s state-of-the-art. Verification of zksnarks is cheap but generation of the proofs is the real bottleneck. Research in the cryptography surrounding zksnarks has advanced at a fast pace in recent years. Orders-of-magnitude improvements have made Zcash a reality. It is possible that the approaches outlined below may become practical in a few years. blockchain 1) Fast sync Traditionally synching a blockchain requires bandwidth, storage and computation. For example in Bitcoin most of the computation is in checking signatures. With zksnarks the burden of explicitly verifying transaction signatures one-by-one can be removed. A single zksnark can attest for all the signatures of a block. This means the computation requirements for synching the Bitcoin can be significantly reduced. To see this let be the program where: P is a block hash i is a block w returns True if has hash and all transactions in have a valid signature, otherwise returns False P w i w P Assuming blocks are bounded in size (e.g. 1 MB) then zksnarks can be generated for whenever is True. Such zksnarks cryptographically prove that the signatures are valid, without having to verify (or even download!) the signatures. This is effectively SegWit on steroids. Notice that and are constant-sized (256 bits and 1 bit respectively) so proof verification takes constant time. P o i o 2) Ultra-light clients Traditionally a light client that wants to answer some question about a blockchain has to do two things. First it has to download the relevant blockchain data and second do the relevant computations on that data. For example a light client that wants to answer the question “Has this specific crowdfund reached its goal yet?” would download the crowdfund transactions and add up the amounts. With zksnarks a client can be cryptographically shown such facts without downloading data or doing computations on that data. This opens the door for “ultra-light” clients which have close-to-zero bandwidth, storage and computation resources, but nonetheless maintain cryptographic sovereignty. To see this let be a light-client query virtual machine where: P contains both a block hash specifying a blockchain to be queried, and a script (e.g. some web3 JavaScript) specifying a query for that blockchain i is the blockchain data required for the query, along with the required parts of the Patricia-Merkle tree for light-client verification w is the output of the script o Given a query and an output , one can produce a corresponding zksnark attesting for the validity of the query result. i o You can imagine a world where dedicated provers provide zksnarks-as-a-service for ultra-light clients. Because generating zksnarks can be expensive, specialised ASICs would speed up the process. Provers would become the new miners where the utility of specialised hardware shifts from providing security to providing scalability, and mining fees shift to “proving fees”. 3) Abstracting away code and storage Currently on Ethereum the code and storage of smart contracts (which together describe the state) are stored in full on the blockchain. This takes up resources and can be bad for privacy. It turns out zksnarks can condense the state of a smart contract into a single hash, obfuscating both the underlying code and storage. To see this, let be an Ethereum light-client verifier where: P is a triple of hashes. The first hash is a block hash specifying the blockchain in its current state. The second hash fingerprints the state of a smart contract as currently represented in the blockchain. Finally, is the hash of the state of the smart contract at some further time in the future. i h_now h_future has the state of the smart contract at time , plus the intermediary transactions that advance state from to , plus the parts of the Patricia-Merkle tree required to do light-client verification of the state w h_now h_now h_future returns True if the state corresponding to is valid, otherwise it returns False P h_future zksnarks can be produced for which prove the validity of state changes of a smart contract without revealing either the code of the smart contract or its storage. P 4) Universal state channels The technique above used to abstract away code and storage from the blockchain (pushing the state offchain, e.g. on IPFS) also allows for batching the state changes that happen between and . This construction is effectively a universal state channel. With the exception of the setup and settlement transactions, all activity happens offchain. h_now h_future The construction allows for state channels that only store a single hash on the blockchain, and where state changes are enforced on the blockchain with a single zksnark verification. You can imagine a blockchain (zEthereum?) which only stores hashes of smart contracts, and where the only opcode is for zksnark verification. is how hackers start their afternoons. We’re a part of the family. We are now and happy to opportunities. Hacker Noon @AMI accepting submissions discuss advertising & sponsorship To learn more, , , or simply, read our about page like/message us on Facebook tweet/DM @HackerNoon. If you enjoyed this story, we recommend reading our and . Until next time, don’t take the realities of the world for granted! latest tech stories trending tech stories
