Spectra: Interval-Agnostic Vector Range Argument for Unstructured Range Assertions

A structured vector range argument proves that a committed vector v lies in a well-structured range of the form [0,2^d-1]. This structure makes the protocol extremely efficient, although it cannot handle more sophisticated range assertions, such as those arising from non-membership attestations. To address this gap, we study a more general setting not captured by prior constructions. In this setting, for each i, the admissible integer set for v_i is a union of k intervals R_i=def⋃_j=0^k-1l_i,j,r_i,j. In this work, we present novel techniques to prove that v∈Z_pⁿ lies within R₀×R₁×⋯×R_n-1. We first introduce RangeLift, a generic compiler that lifts a structured vector range argument to support such unstructured range assertions. Then we present Spectra, a realization of RangeLift over the KZG-based vector commitment scheme. Spectra achieves succinct communication and verifier time; its prover complexity is OnlogNloglogN·log(nlogNloglogN), where N upper bounds the maximum interval size across all R_i. Notably, Spectra is interval-agnostic, meaning its prover complexity is independent of the number of intervals k; therefore, its prover cost matches the single-interval case even when each R_i is composed of hundreds of thousands of intervals. We also obtain two new structured vector range arguments and a batching-friendly variant of the Cq⁺ lookup argument (PKC’24), which are also of independent interest. Experiments show that Spectra outperforms well-known curve-based vector range arguments on standard metrics while supporting strictly more expressive range assertions.