Paper 2025/2326

Efficiently Provable Approximations for Non-Polynomial Functions

Abstract

Zero-Knowledge Proofs (ZKPs) are now widely used to verify the correctness of various types of computations. However, despite phenomenal advancements, current ZKPs are inefficient for applications that need accurate evaluation of non-polynomial functions over floating-point numbers, such as machine learning, decentralized finance, scientific computing, and geolocation. Current state-of-the-art approaches typically emulate floating-point numbers using fixed-point representations (via quantization), and handle non-polynomial functions using lookup tables, piece-wise or low-degree polynomial approximations, which lead to sub-optimal performance and/or loss in accuracy or generality, limiting their potential for adoption in practice. In this work, we present a general framework for approximating a large class of non-polynomial functions using Gauss-Legendre quadrature, which supports efficient ZKPs of correct computation. We show that our approach decreases the adversarial error (the maximum number of lower-order bits a cheating prover can manipulate undetected) up to the limits imposed by quantization, without increasing the multiplicative circuit depth beyond a small constant ($\leq 4$). This is a strong deviation from prior approximation techniques, where decreasing the adversarial error leads to increased multiplicative depth—the main factor determining the adversarial error growth of an approximation. We implement and evaluate our approach in Noir/Barretenberg, and we obtain absolute adversarial errors $2-256\times$ lower than comparable baselines for most non-polynomial functions with low prover overhead. We also demonstrate an efficient prover and low adversarial errors for high-accuracy applications in DeFi and astronomy that require non-polynomial functions, again obtaining adversarial errors $4-64\times$ lower than the baseline approximations.