\(\textsf{Spectra}\) : Interval-Agnostic Vector Range Argument for Unstructured Range Assertions
摘要
A structured vector range argument proves that a committed vector \(\boldsymbol{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 \(\textsf{R}_i \overset{\text {def}}{=} \bigcup _{j=0}^{k-1}\left[ l_{i,j},r_{i,j}\right] \) . In this work, we present novel techniques to prove that \(\boldsymbol{v} \in \mathbb {Z}^n_p\) lies within \(\textsf{R}_0 \times \textsf{R}_1 \times \cdots \times \textsf{R}_{n-1}\) . We first introduce \(\textsf{RangeLift}\) , a generic compiler that lifts a structured vector range argument to support such unstructured range assertions. Then we present \(\textsf{Spectra}\) , a realization of \(\textsf{RangeLift}\) over the \(\textsf{KZG}\) -based vector commitment scheme. \(\textsf{Spectra}\) achieves succinct communication and verifier time; its prover complexity is \(O\left( n\,\tfrac{\log N}{\log \log N}\cdot \log (n\tfrac{\log N}{\log \log N}) \right) \) , where N upper bounds the maximum interval size across all \(\textsf{R}_i\) . Notably, \(\textsf{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 \(\textsf{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 \(\textsf{Cq}^{+}\) lookup argument (PKC’24), which are also of independent interest. Experiments show that \(\textsf{Spectra}\) outperforms well-known curve-based vector range arguments on standard metrics while supporting strictly more expressive range assertions.