I was confused how this related to graph theory until I realized "snark" is overloaded in mathematics,

1. Succinct Non-interactive ARgument of Knowledge https://en.wikipedia.org/wiki/Non-interactive_zero-knowledge...

2. Simple, connected, bridgeless cubic graph with chromatic index equal to 4 https://en.wikipedia.org/wiki/Snark_(graph_theory)

3. SRI's New Automated Reasoning Kit https://en.wikipedia.org/wiki/SNARK_(theorem_prover)

4. 90° stable glider reflector http://conwaylife.com/wiki/Snark

Indeed! zkSNARK is a more exact term for one of the technologies we utilize, but we didn't want to miss a chance to reference https://en.wikipedia.org/wiki/The_Hunting_of_the_Snark.

For those, like me, who needed a good primer on SNARKs, this reference they linked is great https://blog.cryptographyengineering.com/2014/11/27/zero-kno...

How can I compile my scheme? What are the tools available? (doc for libsnark is not very good I need to say)

You might also try https://github.com/akosba/jsnark which is a frontend for libsnark.

An entire reimplemented alternative is Pequin (and related projects by Michael Walfish's group) https://github.com/pepper-project/pequin

As part of the QED-it team - I hope you enjoy and we'd love any feedback :)

The solution to 1.1 is incomplete - Alice can set p=1 and q=n

Ah! It's one thing to be able to answer the question and another to show that the proposed solution is not good enough :-)

Thanks for the heads up - we should have specified this constraint about p and q.