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.
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:
$$ \mathrm{div}(f) = \sum_i (P_i) - n(\mathcal{O}) $$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.