Abstract
In Zero Knowledge Proofs of Elliptic Curve Inner Products from Principal Divisors and Weil Reciprocity, Eagen proposes a method for checking whether a sum of points in an elliptic curve group have been computed correctly. Eagen’s method verifiably checks elliptic curve group operations only with linear combinations in the base field, allowing very general proofs to be encoded in inner product argument systems and rank-1 constraint systems (R1CS). We call this method “straight-line verification,” due to how it utilizes straight lines in the verification procedure. In FCMP++ by Parker, the author uses Eagen’s method in a R1CS to verify scalar multiplication of group elements, proposing a protocol based on Eagen’s arguments. Although the iterative witness construction algorithm proposed by Eagen is correct, the arguments are rather informal, lacking precise protocol descriptions, claims, proofs, or efficiency analyses. We present a method based on Eagen’s technique for straight-line verification of cryptographic protocols, offloading the bulk of the computational costs faced by verifiers onto the prover, which is useful for light-weight devices or when verification must be performed repeatedly. Computational improvements are largely due to replacing expensive division operations with lower-cost arithmetic by applying logarithmic derivatives.
Our work, while not fully novel, is a healthy expansion of previous work. In Soundness Proof for an Interactive Protocol for the Discrete Logarithm Relation, Bassa contributed towards formalizing Eagen’s method, explicitly describing Parker’s proof of scalar multiplication and sketching arguments towards proofs of soundness. However, the soundness arguments in Bassa’s work are not without obstacles. Per Eagen, rational solutions to certain systems of polynomial equations are assumed to exist. We point out that these equations do not, in fact, admit rational solutions in general. Bassa lifts to the surface of pairs of elliptic curve group points to avoid this problem, but the verification equations proposed by Eagen and studied by Bassa are not sufficiently justified in those documents.
The verification equations described by Bassa reduce to our verification equations, and therefore they are equivalent. In particular, given a variable choice of a line in the affine plane with three distinct, non-identity, and collinear points on an elliptic curve , say with interpolating slope and -coordinates , , and , these points are necessarily dependent: . Thus, given any derivation on the function field over , we have , allowing computations to reduce further than presented in Bassa’s work.
Nonetheless, Bassa’s amended approach results in formal arguments, if not proofs, of security. We fully justify the verification equations presented by Bassa, show they reduce further, and reconsider the security of Eagen’s approach under the reduced verification equations. We encourage the reader to keep in mind that our verification equations are equivalent reduced versions of those presented by Bassa. Along the way, we exploit the techniques utilized by Eagen to further reduce the total number of field divisions required by prover to just a single one. Our framework is easily applied to generically speed up verification in discrete-logarithm-based protocols.
We present our protocol, and explicitly compute the completeness and soundness errors. We remark on how to complete the scheme, and our soundness error supersedes the previous estimates in the literature. We also show how the corrected scheme can be used to verify scalar multiplication as in Parker’s proposed protocol. We then apply this approach to zero-knowledge proof systems such as the Schnorr identification scheme and Bulletproofs to illustrate the generic computational advantage offered by divisors. Because these protocols are simple, secure, and popular, we demonstrate that this work is readily applicable to improve verifier computation in cryptocurrencies such as Monero or Salvium.