Zero knowledge systems research vol.4, July 1st— July 31st
Written by Felix@StratifiedCapital
August, 2022
This report includes key analysis of research, articles and project updates in zero knowledge proof technology.
1、Research
(1)<Piranha: A GPU Platform for Secure Computation>
Secure multi-party computation (MPC) is an essential tool for privacy-preserving machine learning (ML). However, secure training of large-scale ML models currently requires a prohibitively long time to complete. Given that large ML inference and training tasks in the plaintext setting are significantly accelerated by Graphical Processing Units (GPUs), this raises the natural question: can secure MPC leverage GPU acceleration? A few recent works have studied this question in the context of accelerating specific components or protocols, but do not provide a general-purpose solution. Consequently, MPC developers must be both experts in cryptographic protocol design and proficient at low-level GPU kernel development to achieve good performance on any new protocol implementation.
We present Piranha, a general-purpose, modular platform for accelerating secret sharing-based MPC protocols using GPUs. Piranha allows the MPC community to easily leverage the benefits of a GPU without requiring GPU expertise. Piranha contributes a three-layer architecture: (1) a device layer that can independently accelerate secret-sharing protocols by providing integer-based kernels absent in current general-purpose GPU libraries, (2) a modular protocol layer that allows developers to maximize utility of limited GPU memory with in-place computation and iterator-based support for non-standard memory access patterns, and (3) an application layer that allows applications to remain completely agnostic to the underlying protocols they use.
On the device layer, we contribute low-level GPU kernels accelerating local, integer-based data shares. At the protocol layer, we implement functionality for three different linear secret-sharing (LSSS) MPC protocols at the protocol layer: SecureML [60] (2-party), Falcon [88] (3-party), and FantasticFour [23] (4-party). At Piranha’s application layer, we provide a protocol-agnostic neural network library that can be executed by any of the protocols. Piranha is modular in that it can support additional components beyond what we provide. To demonstrate the benefits of Piranha, we implement 3 state-of-the-art linear secret sharing MPC protocols for secure NN training: 2-party SecureML (IEEE S&P ’17), 3- party Falcon (PETS ’21), and 4-party FantasticFour (USENIX Security ’21). Compared to their CPU-based implementations, the same protocols implemented on top of Piranha’s protocol-agnostic acceleration exhibit a 16−48× decrease in training time. For the first time, Piranha demonstrates the feasibility of training a realistic neural network (e.g. VGG), end-to-end, using MPC in a little over one day. Piranha is open source and available at https://github.com/ucbrise/piranha.
(2) <Nirvana: Instant and Anonymous Payment-Guarantees>
Abstract: Given the high transaction confirmation latencies in public blockchains, cryptocurrencies such as Bitcoin, Ethereum, etc. are not yet suitable to support real-time services such as transactions on retail markets. There are several solutions to address this latency problem, with layer-2 solutions being the most promising ones. Existing layer-2 solutions, however, suffer from privacy and/or collateral issues when applied to retail environments where customer-merchant relationships are usually ephemeral. In this paper, we propose Nirvana, that can be combined with existing cryptocurrencies to provide instant, anonymous and unlinkable payment guarantees. Nirvana does not require any trusted third party. It conceals the identities of honest participants, thus ensuring customer anonymity within the system while only relying on efficient Groth-Sahai proof systems. We introduce a novel randomness-reusable threshold encryption that mitigates double-spending by revealing the identities of malicious users. We formally prove how our scheme provides customer anonymity, unlinkability of transactions and payment guarantees to merchants. Our experiments demonstrate that Nirvana allows for fast (zero-confirmation) global payments in a retail setting with a delay of less than ∼ 1.7 seconds.
1）Protocol overview
In order to explain Nirvana protocol, we assume that the set of authorities is already established and the merchants in the network have registered and formed a consortium. As illustrated in Figure 3, the protocol between a customer and a merchant proceeds as follows:
①In order to avail the services of Nirvana, the new customer begins by registering themselves with the majority of authorities.
②After successfully registering in the network, the customer deposits a collateral in Nirvana’s smart contract.
③Once the deposit is confirmed on the blockchain where Nirvana’s smart contract is deployed, the customer asks for a collateral certification, which is necessary to prove that the customer owns some collateral in Nirvana. This proof is used to generate payment guarantees for merchants.
④Upon receiving the certification request of the customer, the authorities check the smart contract to confirm if the customer deposited a collateral.
⑤Once confirmed, the authorities provide the customer with a signed certificate of their collateral’s existence in the network. Along with this confirmation, the customer is also assigned a signed list of witnesses in charge of tracking the collateral usage.
⑥During a transaction in the retail market, the customer makes a payment to the target merchant using the cryptocurrency of their choice. Once the payment is in pending state on the blockchain, the customer generates a payment guarantee by using the certified collateral and sends this to the target merchant along with the assigned list of witnesses and the transaction hash of their cryptocurrency payment.
⑦ The target merchant forwards this payment guarantee to the assigned witnesses who individually confirm that they have not seen a similar guarantee in the current epoch.
⑧Upon confirmation, each witness returns a signed payment guarantee to the merchant.
⑨On receiving signed payment guarantees from a majority of the witnesses, the merchant aggregates these signatures and accepts the payment guarantee and provides the customer with necessary services/products.
2) Performance Analysis
In this section, we demonstrate the performance of Nirvana. Based on the application, the costs incurred in each phase are divided into two parts, termed “offline phase” and “online phase”. The former includes the parameter generation, key generation and registration functions. The latter is solely responsible for spending and verification and is the main focus of this evaluation.
We implemented Nirvana by using the Charm-Crypto framework [AGM+13], a Python library for Pairing-based Cryptography and obtained the benchmarks on four AWS EC2 instances.
As can be seen in Tab. 1, we ran three sets of experiments, with the following location configurations:
①Nirvana located in Singapore, customer in California, merchant in Frankfurt and witnesses in London.
②Nirvana located in Singapore, customer in Frankfurt, merchant in London and witnesses in California.
③Nirvana located in Frankfurt, customer in London, merchant in California and witnesses in Singapore.
For the sake of convenience, during our implementation, we assumed that all witnesses are located in the same location. However, placing the witnesses in different locations would only add a small delay based on their distance from the merchant; in order to reflect this delay, we do sequential witness verification instead of parallel verification.
All our EC2 instances had the same computational configuration, i.e., an Ubuntu Server 20.04 LTS (HVM) with an Intel (R) Xeon(R) CPU @ 2.50 GHz and 16 GB of memory. We apply the Barreto-Naehrig (BN254) curve (also known as type F groups), 𝑦 2 = 𝑥 3 + 𝑏 with embedding curve degree 12 [BN06]. In this pairing group, the base field order is 256 bits. Based on our Python code¹ , the overhead of the spending and verification algorithm is summarized in Fig. 4.
Latency: Fig. 4 shows the almost constant relationship between the total number of witnesses for each collateral and their spending time. With spending time, we capture the Spend functionality in Algo. 1, where the customer generates the payment ciphertext and NIZK proofs to provide a payment guarantee to the merchant. It also includes the time required to send the payment guarantee to a merchant located in either of the locations in Tab. 1. As can be seen, the time required to generate a payment guarantee in Nirvana for merchants in Scenario 1 and 3 is almost identical because the distance between the customer and merchant in both scenarios is roughly the same (i.e., California to Frankfurt and London to California). The effect of distance is also reflected in Scenario 2 when the customer is in Frankfurt and the merchant is in London, with each payment guarantee only taking 350 ms on average to be spent as compared to ∼ 900 ms in the other two cases.
Fig. 4 shows the linear relationship between the total number of witnesses for each collateral and the verification time required by a merchant and witnesses. With verification time, we capture the 𝑉𝑓 functionality in Algo. 1, where the merchant verifies the NIZK proofs provided by the customer as a payment guarantee and waits for a majority of the witnesses to approve that this guarantee is unique. It also includes the time required to receive these proofs from the customer located in either location in Tab. 1. As can be seen, the time required to verify a payment guarantee in Nirvana for merchants located in all locations grows linearly with a total number of witnesses, with verification only requiring 990 ms on average in Scenario 1 with two witnesses and 1.3 s on average with 6 witnesses. This is due to the requirement of each individual witness to check their local storage for these guarantees, sign the guarantee if it is unique and finally send the signed guarantee to the merchant. Similar to spending, the distance between countries also effects the time taken to verify each payment guarantee. In scenario 1 of Tab. 1, the merchant and witnesses are located nearby, hence the verification only takes 990 ms when each collateral is assigned to two witnesses as compared to ∼ 1.25 s for both scenario 2 and 3. This is because of the latency incurred due to the geographical distance between, e.g., California and London.
Smart contract cost: Tab. 2 provides USD equivalents of the cost of executing functions (such as registration, etc.) on Nirvana’s smart contract. Since our smart contract can be deployed on any Ethereum Virtual Machine (EVM) supporting blockchain, we calculated the costs on both Ethereum (high Gas fees) and Celo (low Gas fees) using the current conversion rates and a Gas price (Gwei) of 27 for Ethereum and 2.42 for Celo.² As can be seen in Tab. 2, one-time registration of a customer costs them 107 400 Gas or $7.37 on Ethereum and $0.67 on Celo. This Gas cost is a bit high due to the requirement for customers to store a secret to enable victim merchants to redeem their collateral on the smart contract. However, this cost goes down for merchant registration since merchants do not need to store a secret to redeem their collaterals, hence only costing 54 317 Gas or $3.73 on Ethereum and $0.34 on Celo. In case a victim merchant wants to claim a malicious customer’s collateral, it costs them 34 972 Gas or $2.40 on Ethereum and $0.22 on Celo. Finally, if a merchant or customer want to withdraw their money from Nirvana’s smart contract, it costs them 22 525 Gas or $1.55 on Ethereum and $0.14 on Celo.
We acknowledge that Nirvana is not cost efficient when used on Ethereum; however, it is important to note that with the current ETH 2.0 roadmap³ , efforts are being made to lower the Gas fees on Ethereum and eventually make it more usable for Nirvana. More information on the functionality of Nirvana’s smart contract can be found in App. D.
(3)< zk-creds: Flexible Anonymous Credentials from zkSNARKs and Existing Identity Infrastructure >
Abstract: Frequently, users on the web need to show that they are, for example, not a robot, old enough to access an age restricted video, or eligible to download an ebook from their local public library without being tracked. Anonymous credentials were developed to address these concerns. However, existing schemes do not handle the realities of deployment or the complexities of real world identity. Instead, they make (often incorrect) assumptions, e.g., that the local department of motor vehicles will issue sophisticated cryptographic tokens to show users are over 18. In reality, there are multiple trust sources for a given identity attribute, their credentials have distinctively different formats, and many, if not all, issuers are unwilling to adopt new protocols.
We present and build zk-creds, a protocol that uses general-purpose zero-knowledge proofs to 1) remove the need for credential issuers to hold signing keys: credentials can be issued via a transparency log, Byzantine system, or even a blockchain; 2) convert existing identity documents into anonymous credentials without modifying documents or coordinating with their issuing authority; 3) allow for flexible, composable, and complex identity statements over multiple credentials. Concretely, identity assertions using zk-creds take less than 300ms in a real-world scenario of using a passport to anonymously access age-restricted videos.
2、Articles
(1) Aleo to test Virtual Machine ahead of mainnet launch
Layer 1 blockchain Aleo will launch the Aleo Virtual Machine (AVM), a computational platform to run privacy-focused apps on its network, as it looks to attract developers to its ecosystem. While Aleo is still in the testnet phase, next week it will introduce the AVM as part of its upcoming “testnet 3” launch scheduled between August and October. According to a note shared with The Block, the team sees the testnet as an opportunity to onboard new Aleo developers ahead of its mainnet launch in the fourth quarter of 2022. “Our focus is to build the absolute best developer framework for decentralized private applications,” Aleo co-founder and CEO Howard Wu said on the testnet 3 plan. The testnet is incentivized and will reward developers with token incentives for running applications. Similarly, it will also allocate bounty rewards for bug hunters during the testnet period.
(2) ZK in Identity
The beauty of ZKPs is that virtually any statement that you can think of can be proved in zero-knowledge (to be precise, any relation that can be verified in polynomial time can also be proved in zero-knowledge; stronger results are also known). While the non-interactive version of ZKPs are most suited to address confidentiality, privacy, state-growth, integrity, etc. issues on L1s, interactive proofs may make a lot of sense for many applications where blockchain-based identity assertions are needed.
The concert admission example above can be used to illustrate the point. There would just be one well-identified verifier for the ZK membership proof of NFT ownership (organizers of the concert who could very well choose to verify off-chain), as opposed to the hundreds or thousands of unidentified verifiers in a typical L1 setting. A prover can actively engage with the verifier and exchange several messages over the course of a session, breaking free of the inherent complexity trade-offs of non-interactive ZK proofs. Indeed, proofs don’t have to be short or the verifier complexity low, so the spectrum of ZK proofs beyond ZK-SNARKs (most popular kind of non-interactive proof system, which also has succinct proofs) can be fully explored. We would be able to make use of proof systems with much better prover complexity, underlying security assumptions, etc.
Please see the table below for a high-level comparison of different proof systems. As we go down the table, prover complexity and security assumptions get better while the proof size gets worse. While MPC-based ZK proof systems offer the best prover complexity and don’t need a trusted set-up, proofs are interactive and work for a specific verifier only (the one a prover interacts with), which may not be a problem when identity assertions have to be made to a specific party off-chain. (Several other characteristics of ZK proof systems like post-quantum security are not captured in the table.)
To conclude, identities in the world don’t have to be either blockchain-based or nonblockchain-based. Going forward, they can certainly be a combination of the two — and that would make privacy-preserving identity assertions even more interesting!
(3) Ethereum’s Rollup Race: What is a ‘True’ zkEVM?
1)EVM-equivalent vs. EVM-compatible
Polygon faced criticism last week when it announced that it would be launching the first EVM-equivalent ZK rollup to market. According to some onlookers, Polygon’s solution would be better described as EVM-compatible, not EVM-equivalent. So what is the difference between compatibility and equivalence?
The two leading Optimistic rollups for Ethereum, Artbitrum and Optimism, boast that they are EVM-equivalent. This means that the experience of developing on Arbitrum and Optimism is 100% identical to the experience of developing on Ethereum; developers have access to all of the same tools and frameworks that they use to develop on the Ethereum mainnet, and they won’t need to worry about their layer 1 contracts breaking if they are directly ported over to a layer 2 chain.
EVM-equivalence is a massive deal to developers since it means far less overhead when migrating from layer 1 to layer 2.
Users, too, see the benefits of EVM-equivalence. Rather than juggling rollup-specific wallets or other tools, users of EVM-equivalent chains, such as Optimism and Arbitrum, won’t need to abandon familiar apps like Metamask.
EVM-compatibility is a looser definition than EVM-equivalence. Rather than the developer and user experiences being exactly identical to that of Ethereum, EVM-compatible chains might not plug in to all of the same tools and software frameworks that are used on Ethereum.
Developers might need to rewrite their smart contracts in order to port them over to an EVM-compatible blockchain — sometimes in a completely different programming language than Ethereum’s native language, Solidity. Even if developers are still able to write their smart contracts using Solidity, certain operations might not be fully supported by the rollup, which can lead to bugs or other engineering headaches. Although users might be able to send assets back and forth between the EVMcompatible rollup and Ethereum, doing so might require a specialized wallet rather than Metamask.
2) Is Polygon EVM-equivalent?
When Polygon announced that it would be bringing the first EVM-equivalent zkEVM to market last week, some onlookers pointed out that the specifications provided by Polygon would be better described as EVM-compatible, not EVM-equivalent.
In a June Twitter thread, Scroll’s Luozhu Zhang described three different types of zkEVMs: bytecode level, language level and consensus level. All of the applications announced last week fall into the first two categories.
zkSync 2.0 falls into the language-level bucket. Developers can write smart contracts in Solidity, but zkSync will transpile that code into another language called Yul behind the scenes, which it then interprets in order to do all of the fancy cryptography that powers the zero-knowledge rollup under the hood. On the plus side, Matter Labs, the team behind zkSync, says that its system was engineered to provide the rollup certain advantages — particularly around how it generates computation-intensive cryptographic proofs.
On the negative end, zkSync, by most definitions, would be better described as EVM-compatible rather than EVM-equivalent. There’s a chance that zkSync won’t be 1:1 compatible with every single Ethereum tool out there, though Matter Labs insists that this shouldn’t be an issue in the long term.
Scroll and Polygon are both taking a bytecode-level approach to their zkEVMs. These approaches rip out the transpiler step completely, meaning they don’t convert Solidity code into a separate language before it gets compiled and interpreted. This means better compatibility with the EVM. But even here, there are distinctions that may make Scroll more of a “true” zkEVM than Polygon, depending upon who you ask.
As Messari explained in a report released last week, “part of the [‘true’ EVM] debate follows whether the EVM bytecode is being executed directly or interpreted first and then executed. In other words, if a solution does not mirror official EVM specs, it cannot be considered a true zkEVM. Within this definition, Scroll might be considered a ‘true zkEVM’ vs. the others.” According to Messari, “Polygon uses a new set of assembly codes to express each opcode, the human-readable translation of bytecode, which could allow the behavior of the code to be different on the EVM.” In other words, Polygon might be a bit further from EVM equivalence than its main bytecode competitor, Scroll. Yet Polygon will argue that it’s precisely these differences that will allow it to provide a better product than its competitors.
3、Project Updates
(1) Mina Ecosystem Updates — July 2022 | Mina Blog
1)Improving Node Stability
The latest beta release 1.3.2beta1 has been out for almost a month and is being tested on devnet. The last stable release, 1.3.1, has been running smoothly on Mainnet for well over two months. We’ve been focused on shipping performance improvements and addressing outstanding issues. We hope to promote 1.3.2 to stable in the coming weeks.
2) Berkeley QA Network
The Berkeley QA Network is ongoing and the QA task force is diligently participating and helping to address issues that occur. In the past month, we’ve redeployed the Berkeley QA Network and with the help of the community, found an issue. As a result, there has been some operational downtime on the QANet; however, O(1) engineers have identified the root cause and are working to roll out the fix. If you would like to participate in the QA network please chime in on the #devnet channel on Discord. We plan to make a few more redeployments to the QA network in the coming weeks so look out for more enhancements and fixes.
3) zkApp Protocol Readiness
O(1) Labs has worked on implementing key zkApp protocol features such as support for tokens, supporting zkApp events & sequence events, and zkApp composability (one zkApp calling another.) As we near feature completion, we are working on finalizing the acceptance criteria for each aspect of the protocol. The O(1) Labs engineering and testing teams have created a suite of acceptance tests and are writing test cases using sample zkApps.
4) SnarkyJS & zkApps
zkApp proving performance is now 200%-1,000% faster for non-recursive use cases! The O(1) Labs’ engineering team recently added support for preconditions, recursion, and events to SnarkyJS. Preconditions are available now; recursion & events will appear in the next release of SnarkyJS. Developers will be able to make use of these features on Berkeley Testnet. We’re currently writing documentation for these to be published on docs.minaprotocol.com in the coming weeks. Follow the new SnarkyJS changelog to see detailed updates as they occur.
5) Proof Systems
While a draft Rust API for Kimchi was released some time in June via the proofsystems repo, the decision was made to restructure the API to align the interfaces with the proven Snarky (oCaml) circuit writing API, which is used throughout the Mina protocol. While this change will delay the release of an API for Kimchi, it will improve the maintainability and will result in a cleaner transition to future Rust versions of Pickles and Snarky.
6) zkOracles
We’re thrilled to have welcomed a very talented Rust engineer with a background in MPC research who will be leading the implementation on zkOracles. In his first few weeks onboarding and ramping up on the project he has identified a few potential optimizations. We’ll continue to iterate on the design for zkOracles and look forward to beginning implementation work in the near future. In the meantime, the SnarkyJS team is working on an alternative oracle approach for developers to consume data from external sources within a zkApp in the near term.
(2) Announcing the Scroll pre-alpha testnet | Scroll Blog
1)What’s in the pre-alpha testnet?
This initial release will be run on a private PoA fork of Ethereum (the testnet L1) operated by Scroll. On top of this private chain, we will run a testnet Scroll L2 supporting the following features:
⚫ Users will be able to play with a few key demo applications such as a Uniswap fork with familiar web interfaces such as Metamask.
⚫ Users will be able to view the state of the Scroll testnet via block explorers.
⚫ Scroll will run a node that supports unlimited read operations (e.g. getting the state of accounts) and user-initiated transactions involving interactions with the predeployed demo applications (e.g. transfers of ERC-20 tokens or swaps of tokens).
⚫ Rollers will generate and aggregate validity proofs for part of the zkEVM circuits to ensure a stable release. In the next testnet phase, we will ramp up this set of zkEVM circuits.
⚫ Bridging assets between these testnet L1 and L2s will be enabled through a smart contract bridge, though arbitrary message passing will not be supported in this release. Scroll’s pre-alpha testnet will be the first chance for early users and developers to interact with our infrastructure and experience dapp workflows on Scroll. As we scale our node infrastructure, we will relax some of the performance-motivated restrictions and onboard more testers.
2) What’s next for Scroll?
Soon after our pre-alpha testnet, we will be deploying a more open and permissionless alpha testnet. This will be deployed on a public Ethereum testnet and will be open to the public. In particular, our community can expect the following features:
⚫ Allowing developers to deploy smart contracts
⚫ Allowing anyone to run an archival Scroll node
⚫ Generating and aggregating more pieces of the zkEVM proof to be verified on-chain
As we move step by step towards an eventual mainnet release, we will enable successively more pieces of our final architecture, including a decentralized Roller network and integrations with EVM-native developer tools. In the next few weeks, we will release a series of expository articles and posts explaining Scroll’s architecture and the technical vision that has informed Scroll’s development decisions. Stay tuned to learn more about these!
3) Scroll’s Release Philosophy
Scroll’s plan for scaling Ethereum and serving billions of users and developers is a long-term roadmap that requires careful consideration and execution. We firmly believe in the future of the zkEVM as a key to scaling Ethereum, and as such, are committed to releasing it in a way that allows us to work through any challenges in a focused manner and incorporate feedback alongside our roadmap. By giving users, developers and the broader community progressively more functionality to test instead of releasing all features at once, we aim to isolate any bugs and UX difficulties early and often, allowing us to build towards the most robust, scalable solution that will stand the test of time.
(3) 100 Days to Mainnet | Matter Labs
The features of zkSync 2.0:
⚫ zkSync is EVM and web3 compatible.
⚫ We support Solidity and Vyper: no security re-audit required.
⚫ Porting is effortless: 99% of tooling will work out of the box.
⚫ With zkSync your project will inherit the full security of Ethereum.
⚫ You will benefit from more transactions per second and lower gas fees.
⚫ Build on zkSync 2.0 now and be permanently future-proof.
¹ https://github.com/NirvanaPayments/Nirvana.
² https://ethgasstation.info/, https://explorer.bitquery.io/celo_rc1/gas.
³ https://ethereum.org/en/eth2/.
⁴ The table should only be used for some basic guidance and not to make any serious product/business decisions. Within a category itself, ZK systems could have different characteristics and can vary in performance quite a bit. The table is also NOT meant to capture all ZK systems but just some subset of them for illustrative purposes. We apologize for any glaring omissions.
References：
（1）https://eprint.iacr.org/2022/892
（2）https://eprint.iacr.org/2022/872
（3）https://eprint.iacr.org/2022/878
（4）https://www.theblock.co/post/160545/aleo-to-test-virtual-machine-ahead-ofmainnet-launch
（5）https://medium.com/delendum/zk-in-identity-980493401d80
（6）https://www.coindesk.com/tech/2022/07/27/ethereums-rollup-race-what-is-atrue-zkevm/
（7）https://minaprotocol.com/blog/ecosystem-updates-july-2022
（8）https://scroll.mirror.xyz/XQyXDgyxoefag6hcBgGJFz8qrb10rmSU-zUBvY3Q9_A
（9）https://blog.matter-labs.io/100-days-to-mainnet-6f230893bd73
