This is an implementation of Groth-Sahai proof system, designed in particular to illustrate the language of "Knowledge of Elgamal Ciphertext that encrypts zero or one", as presented in the blog post https://crypto.ethereum.org/blog/groth-sahai-blogpost.
Notation-wise the implementation follows the description of the Groth-Sahai proof system presented in "Malleable Proof Systems and Applications" by Chase et al., Appendix A.1. [1]
This only affects the notation, as the proving system is essentially the same as in the original paper, "Efficient Non-interactive Proof Systems for Bilinear Groups" [2].
Another useful resource for understanding GS proofs is "Groth-Sahai Proofs Revisited" [3].
For nix users, preparing the setup is easy, just run nix-shell shell.nix.
Otherwise, the only non-standard library it uses is py_ecc which can be installed from your package manager or from pip.
Then, simply run groth_sahai.py, which contains both the library and some examples / tests.
>>> python groth_sahai.py
- Preparing the setup
- Committing
- Creating the proof
- Verifying the proof
* Checking commitment consistency
* Equation 1/4
** Verification, pairings 1/4
** Verification, pairings 2/4
** Verification, pairings 3/4
** Verification, pairings 4/4
* Equation 2/4
** Verification, pairings 1/4
** Verification, pairings 2/4
** Verification, pairings 3/4
** Verification, pairings 4/4
* Equation 3/4
** Verification, pairings 1/4
** Verification, pairings 2/4
** Verification, pairings 3/4
** Verification, pairings 4/4
* Equation 4/4
** Verification, pairings 1/4
** Verification, pairings 2/4
** Verification, pairings 3/4
** Verification, pairings 4/4
Proof verifies: True