Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
In the zero-knowledge cryptography nomenclature, we have multiple representations of arbitrary computation suitable for submission to various proof backends (e.g. Groth16). Two specific examples spring to mind: rank-1 constraint systems (R1CS) and Algebraic Intermediate Representations (AIR).
What are these called?
I'd say, R1CS, PLONK and AIR are 3 different arithmetic circuit / constraints systems ("backends").
All of these characterize NP and work using arithmetic over finite prime fields.
Other languages that characterize NP are for example 3-SAT. So it should be possible to define ZK with a 3-SAT backend:
https://cs.stackexchange.com/questions/135457/is-there-a-zero-knowledge-proof-for-sat
An interesting side question would be: why are arithmetic circuits seemingly preferred to SAT based ones? One possible answer: using arithmetic circuits allows to use advanced math available, eg compressing polynomials
Also compare to the verifier-based definition of NP:
"Given any instance I of problem Π \Pi and witness W, if there exists a verifier V so that given the ordered pair (I, W) as input, V returns "yes" in polynomial time if the witness proves that the answer is "yes" or "no" in polynomial time otherwise, then Π \Pi is in NP." (wikipedia)
