Verifiable AI(ZKML) through Recursive ZK-Snarks and folding schemes
Introduction
This article delves into the exciting realm of Verifiable AI, focusing on the integration of Recursive ZK-Snarks and folding schemes. The primary objective is to combine the inference process of a neural network model within zero-knowledge circuits. These circuits, written in circom, provide a powerful framework for folding repeated inferences into a single instance, thereby enhancing efficiency and privacy.
Table of Contents
· Introduction
· Table of Contents
· OK I know ZK, but what the hell is ZKML?
· What is Nova?
· How can Nova be used in Verifiable AI (ZKML)?
∘ Case 1
∘ Case 2
· How is Banana SDK using ZKML and Nova?
∘ Private Face Id
∘ Guardian for Transaction Screening
· Conclusion
OK I know ZK, but what the hell is ZKML?
ZK-Snarks have gained significant traction in blockchain applications due to their succinctness and security. In the field of Machine Learning, Deep Learning, and AI, ZK-Snarks offer tremendous potential. As the utilization of AI tools such as ChatGPT and MidJourney continues to rise, ensuring the integrity of these systems and the content they generate becomes crucial. ZK-Snarks provide a viable solution for achieving this verification. However, the question remains: how can we effectively achieve privacy with AI?
AI models employed in various applications rely on an extensive array of parameters, often encompassing billions of weights within deep neural networks. For instance, Chat GPT 4 employs an astonishing 100 trillion weights to compute its output. One prevalent challenge associated with API-based model inferences is the lack of transparency regarding the specific model used for generating the output. Consequently, it is possible that users may pay for access to a premium version of a model, only to have the output calculated using an inferior set of weights. While this may be inconsequential for trivial tasks, it becomes critically important in domains such as medical inferences or financial decision-making, where the accuracy and reliability of AI outputs are paramount.
What is Nova?
Nova enables recursive proof generation for zk arguments, providing a means to demonstrate the execution of a specific set of circuit instructions N times while eliminating redundant steps. This approach offers significant efficiency gains. For instance, consider a scenario where there are 10 signatures to be verified. Instead of running the circuit ten times and generating ten zk proofs for verification, Nova folds the circuit computation into single instance of R1CS, streamlining the overall verification procedure.
Nova adopts a deferred approach in constructing an Incrementally Verifiable Computation (IVC), which eliminates the need for SNARK proofs at each step. The folding scheme employed in Nova facilitates the consolidation of two NP instances (Xi, Wi) into a single folded NP instance, encompassing proofs of the folded instance. By leveraging this approach, the verification process is streamlined, resulting in enhanced efficiency and computational performance.
Originally the IVC prover generates a proof for each incremental step, ensuring the correctness of the computation. This proof includes an augmented circuit that incorporates a “verifier circuit” for verifying the proof of the previous step. Recursively, the final proof proves the correctness of the entire incremental computation. This verification can be achieved used cycles of curve, like pasta curves. As we know that there are two fields of an elliptical curve, base field and scalar field. In this recursive verification the verifier uses an elliptical curve where the fields are switched.
Nova leverages a relaxed Rank-1 Constraint System (R1CS) to enable its folding scheme. While the traditional R1CS is a language that falls under the NP-complete category, serving as a generalization of arithmetic circuit satisfiability, Nova’s relaxed version introduces flexibility. The matrices A, B, and C in R1CS provide essential gate information for a specific constraint system.
Z is the solution vector and it consists of ‘x’ and ‘W’, where ‘x’ is the public inputs and ‘W’ is the private witness. We will plug in Z first complete the evaluation of polynomials and then the proof is given to the verifier for verification through bilinear pairings (atleast this happens in Groth’16).
Now if we try to combine two solution vectors, Z1 and Z2 with a random linear combination in normal R1CS.
After plugging in the values of random linear combination
As we can see this is not working out and we are getting a lot of cross terms and quadratic power of ‘r’
We use relaxed R1CS over here to accomodate these extra terms
We use an Slack vector E to absorb the cross terms and a scalar u for the extra powers of ‘r’
After using these modifications we now have to commit to two things witness W and slack vector E.
The constraints generated on the final step are used with interactive oracle proof(IOP) i.e. Spartan for generating the proofs. This is a very high level introduction to Nova and more details can be found in the paper.
How can Nova be used in Verifiable AI (ZKML)?
Case 1
In neural network models, each inference involves matrix multiplication operations between layers. These operations exhibit repetitive patterns when the architecture of consecutive layers, such as layer 1, 2, and 3, remains the same, containing an identical number of neurons or activations. Nova offers a solution to efficiently handle these repetitive multiplications through a folding technique.
Within the circuit, the multiplication between two layers (e.g., L1 and L2) is implemented, and this circuit is then utilized by Nova to perform folding N times. Folding a random linear combination is a computationally efficient process that utilizes Multi-Party Secure Multiplications (MSMs), which are more efficient than non-parallelizable Fast Fourier Transforms (FFTs). This folding process yields a single claim that encompasses all N steps or layers.
The involvement of expensive SNARK machinery is only required to prove this single instance. This occurs when the folded instance generated by Nova is fed into a SNARK like Spartan, facilitating the creation of a succinct proof. By leveraging this folding technique and the integration of Nova and Spartan, efficient and concise proofs can be achieved for the folded neural network computations.
One limitation of the aforementioned approach is its requirement for fixed-sized intermediate layers in the neural network, which may not always be feasible. Modern and powerful networks often employ layers of varying sizes. However, this limitation can be overcome by utilizing SuperNova, which offers greater flexibility by accommodating multiple circuits.
SuperNova distinguishes itself by introducing a cost model in which the expense of proving a program step is solely dependent on the size of the circuit representing the instruction executed by that step. This represents a significant departure from previous methodologies that employ universal circuits, where the cost of proving a program step is typically proportional to the sum of sizes of circuits representing all supported instructions. Notably, despite a program step invoking only one specific instruction, prior approaches still incur costs associated with all supported instructions.
Case 2
We can have another model where the we can have the entire ML model inside the circom circuit. This includes all the layers of the circuit i.e there is one input for the data and then the output is directly the result of the model. This can be used where we have to take inference from a large number of data points. On every step we can calculate the output and check for a certain condition or aggregate the inference results with one SNARK proof at last that all the computation was done correctly at each incremental step. Nova employs folding scheme for non-interactive systems and instantiates a single relaxed R1CS instance at the beginning of the computation and folding it N times.
The model at the start is fed with some public inputs and private witnesses and then performing inference for one sample, the error term is calculated and a commitment to that error term kept for the verifier. Unlike other IVCs the proof is not generated after every-time a sample is completed. Rather we are leveraging the property that A,B, and C matrices of RICS are fix in every circuit, and only the solution vector is changing. So the solution vector becomes a RLC of the current and the previous solution vector. This leds to the generation of cross terms which are then calculated and committed to.
How is Banana SDK using ZKML and Nova?
Currently at Banana SDK we are targeting two ZKML use cases:
Private Face Id
Private facial recognition for wallet recovery is a critical area of exploration for Banana accounts. Currently, our wallet recovery solution relies on secure multi-party computation (MPC), which involves the storage of recovery shards in different entities. However, to achieve greater decentralization and enhance user privacy, we are investigating the integration of private neural networks and zero-knowledge succinct non-interactive arguments of knowledge (ZK-SNARKs) for facial recognition.
By leveraging private neural networks, users will have the ability to scan their faces for recovery purposes. The facial features will be matched, and the verification of the accompanying proof will validate the correctness of the face. This approach eliminates the reliance on centralized entities and offers a more secure and privacy-preserving solution for wallet recovery.
Through our ongoing research and development efforts, we aim to advance the field of private facial recognition and contribute to the evolution of decentralized and user-centric solutions. We are committed to pushing the boundaries of innovation to provide our users with robust and secure wallet recovery mechanisms. Stay tuned for updates on this exciting development.
Guardian for Transaction Screening
The current state of Passkeys poses a potential risk, as transaction data prior to signing remains invisible. This lack of visibility increases the likelihood of users unknowingly signing incorrect messages and transactions. To address this issue, a straightforward solution involves implementing a dialogue box that displays transaction details before the passkey authentication prompt, ensuring user awareness.
However, a challenge arises in preventing malicious actors from displaying pop-ups with misleading information. To tackle this, an on-chain guardian is necessary to mitigate phishy transactions. This guardian would rely on a classification model, operating within a ZK-SNARK, to identify potentially fraudulent transactions. The classification model takes transaction information as private variables, producing a result accompanied by a proof.
It’s important to note that this solution is currently in its nascent stage and requires substantial refinement in terms of overall architecture and design. Further exploration and development are needed to optimize the system’s functionality and security.
By addressing these challenges and advancing the architecture, we aim to enhance the reliability and trustworthiness of Passkey-based transactions. Continued research and improvements will be pivotal in establishing a robust and secure framework for user authentication and transaction verification.
Conclusion
This space is seeing active research recently and we will see a lot of advancement in terms of the client side proving in Verifiable AI. With the advents of LLMs we can see the AI space picking up. We will need more privacy enable systems which can users can use without compromising their private information and complete transperancy should be maintained from the users. I hope you enjoyed reading the article and would some feedback from you end. Please your comments down below or contact me on Twitter.
At last, I would greatly appreciate any constructive feedback or criticism if there are any areas that need improvement. Your input is highly valued and will help us enhance the quality of our work. Thank you in advance for taking the time to provide your valuable insights.
I would like to express my sincere gratitude to Dr. Cathie, and Nitanshu for their invaluable contribution in reviewing this work. Their insightful feedback and expertise have greatly enhanced the quality of this article.
Cover pic credits to Divyam
