On the request of MAGIC Grants we were asked to review the security of the divisor-based protocol for proving Elliptic Curve Inner Products (ECIPs) introduced by Liam Eagen in his 2022 eprint. The motivation is the upcoming upgrade to Monero, which will employ this technique; then billions are on the line, you want to be sure. Our contributions include a new proof of extraction, more exact definitions of the relations proven, and a formal treatment of the composition of the protocol with a non-interactive proof. Our treatment goes all the way from the algebraic geometry to the concrete constraints that must be checked.

Download The Notes (PDF)

Application

The intended application is the upcoming Full-Chain Membership Proofs (FCMP++) for Monero, which composes the ECIP with Curve Trees to get set-membership proofs much more efficient than a standard Merkle tree verified inside a proof system. This will allow Monero to scale its membership proofs to include every possible transaction. Curve trees requires:

• A single lookup.
• A single scalar multiplication.

Proven using a circuit over a field that is the base field of the elliptic curve. The usual way to prove the scalar multiplication involves emulating the group operation in-circuit, e.g. proving the execution of the standard double-and-add inside the circuit. Eagen's technique instead exploits non-determinism and interaction: instead of computing the group operations, the prover constructs a proof (witness), commits to it, and then the verifier samples a random challenge to verify the validity of the proof. A small teaser follows.

The Trick

We think the original paper is underappreciated; the core observation is very neat. The key insight is that there is a 1-to-1 correspondence (up to nonzero scalar) between rational functions on an elliptic curve $E$ and principal divisors: formal sums of points with integer multiplicities, of degree zero, that sum to the identity on $E$. Concretely, $P_1, \ldots, P_n \in E$ satisfy $\sum_i P_i = \mathcal{O}$ (counted with multiplicity) if there exists a rational function $f \in \mathbb{F}(E)$ with divisor:

The useful direction: a witness for the sum is a rational function with the prescribed zeros at the $P_i$ and a matching pole of order $n$ at infinity. Hence, rather than emulating the group law inside the circuit, the prover commits to the coefficients of $f$ and the verifier checks that $f$ has exactly that divisor. Taking the logarithmic derivative reduces this further: the check becomes an inner product between the prover's secret coefficients and a public vector derived from a random challenge point, instead of evaluating $f$ at every $P_i$.

Done naively, this saves nothing over the simple group law emulation approach, however, by applying Haböck's logarithmic derivative trick to the expression, everything becomes a linear combination between public challenge values and the divisor polynomial $f(X, Y) \in \mathbb{F}[E]$. The end result is that an MSM of arbitrary length can be verified in 7 multiplicative constraints. All this is covered in much more detail in our writeup.

We Can Help

With broad practical/academic expertise zkSecurity helps its clients review/develop/employ the most advanced cryptography with confidence. Including providing additional formalism beyond the original paper, helping you go from paper to practice without fear of security/proof gaps. Whether you need extra eyes on your own work, or work you plan to incorporate into your solution, we are happy to discuss how we may help.