Constraint-Efficient Comparators via Weighted Accumulation
Marc Guzmán-Albiol, Marta Bellés-Muñoz, Rafael Genés-Durán, José L. Muñoz · Mathematics · 2025
This article presents an optimized method for verifying the comparison of two binary numbers using the rank-1 constraint system (R1CS) representation, a standard framework for verifiable computation systems. In particular, we analyze different strategies for implementing strict comparisons of the form t>K, where K is a known constant and t is an integer input to the comparison. We first analyze a lexicographic approach that, although conceptually straightforward, results in a large number of constraints due to its branching logic. To address this inefficiency, we introduce a weighted-accumulation method that computes an accumulator whose sign determines the comparison outcome. By assigning position-dependent weights to bit pairs and formulating the computation through degree-2 constraints, this method eliminates branching and significantly reduces the total number of constraints. In order to validate our designs, we implemented the described comparison algorithms in an R1CS compiler called circom, allowing us to generate and analyze the corresponding R1CS constraint systems in practice. Overall, the presented design not only ensures correctness but also demonstrates how careful exploitation of the R1CS structure can lead to efficient constraint settings.