Class Group-based ZK SNARKs

[kayabaNerve]

Class groups of unknown order have trustless setups, offer an elliptic-curve-esque API, yet are a couple orders of magnitude larger/slower (~2 KB elements for 128-bit security). They do not offer multiplicative inverses over the scalar field, and have a few interesting properties.

Dew is a constant-sized logarithmic-time-to-verify ZK-SNARK based on class groups of unknown order.

CL15 additionally describes a way to create elements in a subgroup of an arbitrary prime, letting class groups be used for operations over existing fields used in elliptic curves, albeit with the discrete log problem being easy.

If we have a class group-based SNARK offering native arithmetic for Monero's elliptic curve, we'd have the option to feasibly use it. In practice, this will hammering a square peg into a round hole using class groups due to how much more expensive they are to compute over. If they fundamentally offer better complexity though, that may be a worthwhile trade off.

I'm personally more interested in ECC with a cycle. While there are no logarithmic-time-to-verify proofs for isolate programs, IVC proofs do exist which offer such performance when running the same program multiple times. That, combined with the overhead of class groups, likely makes ECC options the sane path forward.

[narodnik]

Class groups based off binary quadratic forms are secure. See the Chia project for an implementation. However they are close to RSA in performance.

Genus 3 hyperelliptic curves are much faster. Indeed genus 2 curves actually outperform normal EC. However there's debate on their security. https://asz.ink/2020/03/08/jacobians-of-hyperelliptic-curves/