Audit Scope: Review the protocol description in Section 3.2 of The Halo2 Book (as of 9th May 2022). Check the theoretical reasoning behind the zero-knowledge and soundness of the protocol.
I read through the definitions of Cryptographic Groups, Interactive Proofs, Perfect Completeness, Public Coin, State Restoration Soundness, State Restoration Witness Extended Emulation, and Special Honest Verifier Zero-Knowledge. No issues were found but I did not spend lots of time on this section. The notation for the algebraic group model has been changed in the most recent update and I have not checked for typos in this update. I verbally discussed the method for implementing the hash functions for the Fiat-Shamir transformation with the authors and confirmed that the full transcript is being included when hashing for each new challenge.
My main actionable when reviewing the protocol was fixing the relation description. In the original description there were no restrictions on the witness and thus it was unclear what was being proven. This has been fixed but there are outstanding todos for ensuring that the extractor outputs meaningful information about the witness in the security proof. It is possible that the relation may need to be specified in more detail to complete these todos.
I found some minor typos in the protocol description, but none were critical. All have been fixed in current version.
I have reviewed proof of zero-knowledge and agree that each proof element has either been blinded or is uniquely determined by the verifier equations.
I have reviewed and have found no issues with the description of h.
The description of the extractor function has not yet been completed and thus has not yet been reviewed. It is important that the updated extractor function gets reviewed when it is completed.
I reviewed Lemma 1 in lots of detail. I am convinced by this lemma and found no serious errors.
I have read through the remainder of the proof after Lemma 1 but in less detail because this content is newer. I intend to spend more time on this. Mostly I am convinced by it except for the last paragraph, which could do with more information.
Overall, I did not find any critical security problems with the protocol. I am personally convinced of the security of the inner product argument. I await more detail on the description of the a_j(X) polynomials in the original relation, the extractor function, and the last paragraph of the soundness before I complete the audit.
About Mary Maller
Ms. Maller is a cryptography researcher at the Ethereum Foundation. Much of her research has looked into the design of ceremonies for zero-knowledge proofs. More recently, she has been researching distributed key generation.
Her PhD – Practical Zero-Knowledge Arguments from Structured Reference Strings – was gained at University College London. Her thesis was supervised by Sarah Meiklejohn and Jens Groth and was submitted in December 2018. Microsoft Research Cambridge supported her PhD. She was co-supervised by Markulf Kohlweiss, whom she also completed an internship with in 2017.
She is currently a member of the ECC Scientific Advisory Group.