Review of Monero Divisors Technique

# Review of Monero Divisors Technique The following is a SoW for proofs/documents/protocols related to the use of the "Elliptic Curve Divisor" technique in the context of the Monero blockchain. ## Context & Background Monero will shortly implement full-chain memberships. This requires proving a number of discrete-log relations inside an arithmetic circuit. To optimize this in-circuit relation, Monero aims to employ [techniques devised by Liam Eagen](https://moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=229&list=1&highlight=1), which exploits the one-to-one correspondence between sets of elliptic curve points summing to the identity and divisors interpolating (vanishing) at the exact set of points. The security arguments in the original paper by Eagen were informal, therefore Magic Grants asked Veridise to produce a set of documents formally proving the security of the various components of the construction: - [Soundness Proof for Eagen's Proof of Sums of Points](https://moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=229&list=1&highlight=1) \ By Alp Bassa, Veridise. - [On the Use of Logarithmic Derivatives in Eagen's Proof of Sums of Points](https://moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=241&list=1&highlight=1) \ By Alp Bassa, Veridise. - [Soundness Proof for an Interactive Protocol for the Discrete Logarithm Relation]( https://moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=259&list=1&highlight=1) \ By Alp Bassa, Veridise. Magic Grants subsequently commissioned [Cypher Stack](https://cypherstack.com/) to review the claims in these documents. The conclusion from Cypher Stack was that they did not find the documents sufficiently convincing. As a consequence, Magic Grants is now looking for a third opinion and a definitive conclusion on the soundness of the protocol. To be able to provide this assurance, ZKSecurity has put together a team and this document outlines the efforts/cost/timeline for this team to provide a thorough review of the Veridise documents, a definite answer on the question of soundness and descriptions of any potential protocol modifications required. ## Goal of This Engagement The goal of this engagement is to conclusively confirm the soundness of the protocol described in [figure 1 of "Soundness Proof for an Interactive Protocol for the Discrete Logarithm Relation"](https://moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=259&list=1&highlight=1) by Veridise. If soundness for the protocol *as stated* cannot be proved, then the goal is to augment the protocol and then rigorously prove soundness of the augmented version. ## The Team The team which will undertake this effort consists of two experts, one with a focus on zero-knowledge/interactive proofs and one in algebraic geometry/elliptic curves: 1) [Mathias Hall-Andersen](https://rot256.dev/post/whoami/) has a PhD in theoretical cryptography from Aarhus University with a specialization in Zero-Knowledge Proofs and Multi-Party Computation (MPC). He has published multiple works at top IACR conferences and will provide the primary expertise in zero-knowledge proofs for this project. 2) [Diego Aranha](https://dfaranha.github.io) is a professor in the cryptography group at Aarhus University. He has an [extensive publication record](https://scholar.google.com/citations?user=FF26-mIAAAAJ&hl=en) on pairing based cryptography, isogeny based cryptography and elliptic curve based cryptography in general. Additionally he is the author and maintainer of the [RELIC](https://github.com/relic-toolkit/relic) crypto library. He will provide his deep knowledge about the relevant algebraic geometry and elliptic curves for this project. ## Estimated Effort We estimate that: - Reviewing the original paper. - Reviewing the Veridise documents. - Proving any/all potential holes/inaccuracies left by Bassa. - Providing a report with our findings and proofs. Will take this team one week working full time. Should the effort take longer, due to unforeseen complexities, we commit to providing these additional hours pro-bono until the goal of the engagement is met. The fee for this effort is: *$50,000* ## Timeline The team will primarily carry out the work during the week of the 23rd of June till 27th of June. We commit to providing the report by the 18th of July; with the additional time allowed to account for protocol / proof updates as necessary and to compile the final report. ## Relevant Resources - [Zero Knowledge Proofs of Elliptic Curve Inner Products from Principal Divisors and Weil Reciprocity](https://eprint.iacr.org/2022/596) \ By Liam Eagen. - [Soundness Proof for Eagen's Proof of Sums of Points](https://moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=229&list=1&highlight=1) \ By Alp Bassa, Veridise. - [On the Use of Logarithmic Derivatives in Eagen's Proof of Sums of Points](https://moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=241&list=1&highlight=1) \ By Alp Bassa, Veridise. - [Soundness Proof for an Interactive Protocol for the Discrete Logarithm Relation]( https://moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=259&list=1&highlight=1) \ By Alp Bassa, Veridise.