In general, I think of zk-SNARK circuits representing a language in NP, meaning it is "computationally easy" to verify. However I was reading about a recent zk-SNARK (Sonic) which has as goal "to provide zero-knowledge arguments for the satisfiability of constraint systems representing NP-hard languages".

Can someone explain how a zk-SNARK circuit can prove satisfiability of an NP-hard language?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.