Correct. You need a succinct proof (which would then have linear proving) or to move the problem statement to one with sublinear complexity (a merkle tree).
Curve Trees is one approach, and great for a trustless setup discussion.
You can do quite a bit better. My work has been applying Curve Trees to Monero and we’re at 35ms for verifying one proof (using two curves without tailored field implementations yet crypto-bigint’s Residue type) of 219b. With batch verification (n=10), it quickly gets down to 11ms.
This isn’t necessary if you define the linking tags as x coordinates. Then proving for a negative leaf may produce a negative linking tag, except the sign data is lost when you drop the tag’s y coordinate.
You could still trivially produce a collision on the layers by hashing negative words. That’s solved by using an initialization generator as a term with a constant coefficient of 1. Since that term can’t be negated, you’d need to solve the DLP for the initialization generator and other generators.
Technically Generalized Bulletproofs (not Bulletproofs as published several years ago).
The benefit of using Generalized Bulletproofs is the ‘native’ operations re: Pedersen Vector Commitments. Using Spartan would require manually building them on the towering curve (historically hundreds of multiplication constraints per word).
They’d just need to open the re-randomized output key. The existing DLEq proof does so (while additionally providing linkability).