# Notes and Proofs for Divisor Techniques

- **Authors**: Mathias Hall-Andersen
- **Date**: May 08, 2026
- **Tags**: educative, zk, elliptic-curves, monero

![Elliptic Artwork](https://blog.zksecurity.xyz/posts/divisor-notes/thumbnail.jpg)

On the request of [MAGIC Grants](https://magicgrants.org/)
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](https://eprint.iacr.org/2022/596).
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)**](https://blog.zksecurity.xyz/posts/divisor-notes/divisor-techniques.pdf)

## Application

The intended application is the upcoming Full-Chain Membership Proofs (FCMP++) for Monero,
which composes the ECIP with [Curve Trees](https://eprint.iacr.org/2022/756) 
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](https://eprint.iacr.org/2022/1530.pdf) 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*](https://github.com/kayabaNerve/fcmp-plus-plus-paper/blob/divisor-paper/divisors.pdf).
All this is covered in much more detail in [our writeup](https://blog.zksecurity.xyz/posts/divisor-notes/divisor-techniques.pdf).

## 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.

---

This article was published on the [ZK/SEC Quarterly](https://blog.zksecurity.xyz) blog by [ZK Security](https://www.zksecurity.xyz), a leading security firm specialized in zero-knowledge proofs, MPC, FHE, and advanced cryptography. ZK Security has audited some of the most critical ZK systems in production, discovered vulnerabilities in major protocols including Aleo, Solana, and Halo2, and built open-source tools like [Clean](https://github.com/Verified-zkEVM/clean) for formally verified ZK circuits. For more articles, see the [full list of posts](https://blog.zksecurity.xyz/llms.txt).