Zero-Knowledge Proofs

# ─── Requirements: pip install py_ecc ──────────────────────────
# py_ecc provides BN128 pairing operations

from py_ecc.bn128 import (
    G1, G2, pairing, multiply, add, neg, field_modulus, curve_order
)
import hashlib, random

# ─── Schnorr protocol simulation ───────────────────────────────
def schnorr_sim(p=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,
                g=2):
    """Simulate Schnorr over a toy multiplicative group."""
    q = p  # prime order group for simplicity
    x = random.randrange(1, q)          # private key
    Y = pow(g, x, q)                    # public key

    # Prove knowledge of x
    r = random.randrange(1, q)
    R = pow(g, r, q)
    c = int(hashlib.sha256(f"{Y}{R}".encode()).hexdigest(), 16) % q
    s = (r + c * x) % q

    # Verify
    lhs = pow(g, s, q)
    rhs = (R * pow(Y, c, q)) % q
    print(f"Valid proof: {lhs == rhs}")
    return lhs == rhs

schnorr_sim()


# ─── R1CS satisfiability check ─────────────────────────────────
def check_r1cs(A, B, C, s):
    for i, (a, b, c) in enumerate(zip(A, B, C)):
        left  = sum(ai * si for ai, si in zip(a, s))
        right = sum(bi * si for bi, si in zip(b, s))
        out   = sum(ci * si for ci, si in zip(c, s))
        if left * right != out:
            raise ValueError(f"Constraint {i} failed: {left}*{right} != {out}")
    print("All R1CS constraints satisfied!")

# x^3 + x + 5 = 35, with x=3
s = [1, 35, 3, 9, 27]  # [1, out, x, v1, v2]
A = [[0,0,1,0,0], [0,0,0,1,0], [5,0,1,0,1]]
B = [[0,0,1,0,0], [0,0,1,0,0], [1,0,0,0,0]]
C = [[0,0,0,1,0], [0,0,0,0,1], [0,1,0,0,0]]
check_r1cs(A, B, C, s)


# ─── BN128 pairing check (Groth16-style) ───────────────────────
def demo_pairing():
    # e(aG1, bG2) == e(G1, G2)^(ab)
    a, b = 5, 7
    aG1 = multiply(G1, a)
    bG2 = multiply(G2, b)
    abG1 = multiply(G1, a * b % curve_order)

    lhs = pairing(bG2, aG1)
    rhs = pairing(G2, abG1)
    print(f"Pairing bilinearity: {lhs == rhs}")

demo_pairing()


# ─── circom witness generation example ─────────────────────────
# Requires: npm install -g circom snarkjs
# Circuit: multiplier2.circom
#   pragma circom 2.0.0;
#   template Multiplier2() {
#       signal input a, b;
#       signal output c;
#       c <== a * b;
#   }
#   component main = Multiplier2();

import subprocess, json, os

def generate_proof(circom_circuit, input_data, output_dir="."):
    """Full circom -> witness -> proof pipeline."""
    # 1. Write input
    with open(f"{output_dir}/input.json", "w") as f:
        json.dump(input_data, f)

    # 2. Generate witness
    subprocess.run(["node", f"{circom_circuit}_js/generate_witness.js",
                    f"{circom_circuit}_js/{os.path.basename(circom_circuit)}.wasm",
                    f"{output_dir}/input.json",
                    f"{output_dir}/witness.wtns"], check=True)

    # 3. Generate proof (requires trusted setup zkey)
    subprocess.run(["snarkjs", "groth16", "prove",
                    f"{circom_circuit}.zkey",
                    f"{output_dir}/witness.wtns",
                    f"{output_dir}/proof.json",
                    f"{output_dir}/public.json"], check=True)

    # 4. Verify
    result = subprocess.run(["snarkjs", "groth16", "verify",
                              f"{circom_circuit}_vk.json",
                              f"{output_dir}/public.json",
                              f"{output_dir}/proof.json"],
                             capture_output=True, text=True)
    return "OK" in result.stdout

# generate_proof("multiplier2", {"a": 3, "b": 7})  # proves 3*7=21

// ─── Requirements: npm install snarkjs circomlibjs ─────────────

const snarkjs = require("snarkjs");
const { buildPoseidon } = require("circomlibjs");

// ─── Generate and verify a Groth16 proof with snarkjs ──────────
async function proveAndVerify() {
    // Input to the circuit (must match the circuit's public/private inputs)
    const input = { a: 3, b: 11 };  // proving a*b = 33

    // Generate proof
    const { proof, publicSignals } = await snarkjs.groth16.fullProve(
        input,
        "multiplier.wasm",   // compiled circuit (circom -> wasm)
        "multiplier.zkey"    // proving key (from trusted setup)
    );

    console.log("Proof:", JSON.stringify(proof, null, 2));
    console.log("Public signals:", publicSignals);

    // Verify proof using verification key
    const vkey = JSON.parse(require("fs").readFileSync("verification_key.json"));
    const isValid = await snarkjs.groth16.verify(vkey, publicSignals, proof);
    console.log("Proof valid:", isValid);

    return { proof, publicSignals, isValid };
}

// ─── Export Solidity verifier contract ─────────────────────────
async function exportSolidityVerifier() {
    const templates = { groth16: snarkjs.groth16 };
    const solidityCode = await snarkjs.zKey.exportSolidityVerifier(
        "multiplier.zkey",
        templates
    );
    require("fs").writeFileSync("Verifier.sol", solidityCode);
    console.log("Verifier.sol written — deploy this to Ethereum!");
}


// ─── Circom compilation workflow ───────────────────────────────
// Install: npm install -g circom
// 1. Write circuit in multiplier.circom:
//    pragma circom 2.0.0;
//    template Multiplier() {
//        signal input a, b;
//        signal output c;
//        c <== a * b;
//    }
//    component main { public [c] } = Multiplier();
//
// 2. Compile: circom multiplier.circom --r1cs --wasm --sym
// 3. Trusted setup:
//    snarkjs powersoftau new bn128 12 pot12_0000.ptau
//    snarkjs powersoftau contribute pot12_0000.ptau pot12_0001.ptau
//    snarkjs powersoftau prepare phase2 pot12_0001.ptau pot12_final.ptau
//    snarkjs groth16 setup multiplier.r1cs pot12_final.ptau multiplier.zkey
//    snarkjs zkey export verificationkey multiplier.zkey verification_key.json


// ─── Poseidon hash (ZK-friendly hash function) ─────────────────
async function poseidonDemo() {
    const poseidon = await buildPoseidon();
    // Poseidon is a ZK-friendly hash — many times cheaper in circuits
    // than SHA256 (SHA256 needs ~20k R1CS constraints; Poseidon needs ~200)
    const input = [BigInt(1), BigInt(2), BigInt(3)];
    const hash = poseidon(input);
    const hashHex = poseidon.F.toString(hash, 16);
    console.log("Poseidon hash:", hashHex);

    // Proving knowledge of a Poseidon preimage (for Semaphore/Merkle trees)
    // Circuit: poseidon(secret, nullifier) == commitment (public)
    // Proves: I know the secret behind a public commitment
}

proveAndVerify().catch(console.error);

/* ── Requirements: libff (https://github.com/scipr-lab/libff) ──
   Compile: g++ -O2 -o zkp_demo zkp_demo.c -lff -lgmp -lssl -lcrypto
   libff provides elliptic curve arithmetic and pairing operations.    */

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>

/* ── Conceptual BN128 group element (opaque in real libff) ──── */
typedef struct { uint64_t x[4], y[4], z[4]; } G1;
typedef struct { uint64_t x[8], y[8], z[8]; } G2;
typedef struct { uint64_t c[12]; }             GT;

/* ── Stub declarations — real libff uses C++ ────────────────── */
extern G1  g1_generator(void);
extern G2  g2_generator(void);
extern G1  g1_scalar_mul(G1 P, uint64_t s[4]);
extern G1  g1_add(G1 P, G1 Q);
extern GT  bn128_pairing(G2 Q, G1 P);   /* e: G2 x G1 -> GT */
extern int gt_equal(GT a, GT b);
extern void g1_print(const char *name, G1 P);

/* ── Check bilinearity: e(aG1, bG2) == e(G1, G2)^(ab) ─────── */
int check_pairing_bilinearity(uint64_t a, uint64_t b) {
    G1 G1gen = g1_generator();
    G2 G2gen = g2_generator();

    /* a*G1, b*G2, (a*b)*G1 */
    uint64_t a4[4] = {a, 0, 0, 0};
    uint64_t b4[4] = {b, 0, 0, 0};
    uint64_t ab4[4] = {a * b, 0, 0, 0};  /* simplified, ignores overflow */

    G1 aG1   = g1_scalar_mul(G1gen, a4);
    G2 bG2   = g2_scalar_mul(G2gen, b4);
    G1 abG1  = g1_scalar_mul(G1gen, ab4);

    /* e(aG1, bG2) should equal e(abG1, G2) by bilinearity */
    GT lhs = bn128_pairing(bG2, aG1);
    GT rhs = bn128_pairing(G2gen, abG1);

    return gt_equal(lhs, rhs);
}

/* ── Simplified Groth16 verification (structure only) ────────
   In practice: use libsnark or arkworks-rs for production code. */
typedef struct {
    G1 alpha_g1;
    G2 beta_g2, gamma_g2, delta_g2;
    G1 *IC;           /* size: n_public + 1 */
    int n_public;
} VerificationKey;

typedef struct { G1 A; G2 B; G1 C; } Proof;

int groth16_verify(const VerificationKey *vk, const Proof *pi,
                   const uint64_t *pub_inputs, int n_pub)
{
    /* Compute vk_x = IC[0] + sum_i( pub_inputs[i] * IC[i+1] ) */
    G1 vk_x = vk->IC[0];
    for (int i = 0; i < n_pub; i++) {
        uint64_t s4[4] = {pub_inputs[i], 0, 0, 0};
        G1 term = g1_scalar_mul(vk->IC[i + 1], s4);
        vk_x = g1_add(vk_x, term);
    }

    /* Check: e(A, B) == e(alpha, beta) * e(vk_x, gamma) * e(C, delta) */
    GT lhs = bn128_pairing(pi->B, pi->A);

    GT r1 = bn128_pairing(vk->beta_g2, vk->alpha_g1);
    GT r2 = bn128_pairing(vk->gamma_g2, vk_x);
    GT r3 = bn128_pairing(vk->delta_g2, pi->C);

    /* GT multiplication */
    GT rhs = gt_mul(gt_mul(r1, r2), r3);

    return gt_equal(lhs, rhs);
}

int main(void) {
    printf("BN128 pairing bilinearity (3, 7): %s\n",
           check_pairing_bilinearity(3, 7) ? "PASS" : "FAIL");
    /* For full ZKP: use libsnark C++ interface or arkworks-rs */
    return 0;
}

// ─── Requirements: libsnark ──────────────────────────────────
// git clone https://github.com/scipr-lab/libsnark && cd libsnark
// mkdir build && cd build && cmake .. && make
// g++ -O2 -o zkp_demo zkp_demo.cpp -lsnark -lff -lgmp -lprocps

#include <libsnark/gadgetlib1/gadgets/basic_gadgets.hpp>
#include <libsnark/gadgetlib1/gadget.hpp>
#include <libsnark/gadgetlib1/pb_variable.hpp>
#include <libsnark/zk_proof_systems/ppzksnark/r1cs_gg_ppzksnark/r1cs_gg_ppzksnark.hpp>
#include <libff/algebra/curves/public_params.hpp>

using namespace libsnark;
typedef libff::default_ec_pp ppT;
typedef libff::Fr<ppT>       FieldT;

// ─── Circuit: prove knowledge of x s.t. x^3 + x + 5 == 35 ───
class CubicCircuit : public gadget<FieldT> {
public:
    pb_variable<FieldT> x;    // private input
    pb_variable<FieldT> v1;   // x*x
    pb_variable<FieldT> v2;   // x*x*x
    pb_variable<FieldT> out;  // public output

    CubicCircuit(protoboard<FieldT> &pb, const std::string &name)
        : gadget<FieldT>(pb, name)
    {
        out.allocate(pb, "out");   // public first
        x.allocate(pb,   "x");
        v1.allocate(pb,  "v1");
        v2.allocate(pb,  "v2");
        pb.set_input_sizes(1);     // out is the single public input
    }

    void generate_r1cs_constraints() {
        // x * x = v1
        pb.add_r1cs_constraint(
            r1cs_constraint<FieldT>(x, x, v1), "x*x=v1");
        // v1 * x = v2
        pb.add_r1cs_constraint(
            r1cs_constraint<FieldT>(v1, x, v2), "v1*x=v2");
        // (v2 + x + 5) * 1 = out
        pb.add_r1cs_constraint(
            r1cs_constraint<FieldT>(v2 + x + FieldT(5), FieldT::one(), out),
            "v2+x+5=out");
    }

    void generate_r1cs_witness(const FieldT &x_val) {
        pb.val(x)   = x_val;
        pb.val(v1)  = x_val * x_val;
        pb.val(v2)  = pb.val(v1) * x_val;
        pb.val(out) = pb.val(v2) + x_val + FieldT(5);
    }
};

int main() {
    libff::default_ec_pp::init_public_params();
    protoboard<FieldT> pb;

    CubicCircuit circuit(pb, "cubic");
    circuit.generate_r1cs_constraints();

    // ── Trusted setup ────────────────────────────────────────
    const r1cs_constraint_system<FieldT> cs = pb.get_constraint_system();
    auto keypair = r1cs_gg_ppzksnark_generator<ppT>(cs);

    // ── Prove: x = 3 ────────────────────────────────────────
    circuit.generate_r1cs_witness(FieldT(3));
    assert(pb.is_satisfied());

    const r1cs_gg_ppzksnark_proof<ppT> proof =
        r1cs_gg_ppzksnark_prover<ppT>(
            keypair.pk,
            pb.primary_input(),    // public: out=35
            pb.auxiliary_input()); // private: x=3, v1=9, v2=27

    // ── Verify ──────────────────────────────────────────────
    bool verified = r1cs_gg_ppzksnark_verifier_strong_IC<ppT>(
        keypair.vk,
        pb.primary_input(),
        proof);

    std::cout << "Proof verified: " << verified << "\n";
    // Proof size: 3 group elements (~192 bytes for BN254)
    return 0;
}

import java.math.BigInteger;
import java.security.SecureRandom;
import java.security.MessageDigest;
import org.web3j.protocol.Web3j;
import org.web3j.tx.gas.DefaultGasProvider;

/**
 * Zero-Knowledge Proof demonstration in Java.
 * Part 1: Schnorr protocol simulation (educational, over toy group)
 * Part 2: web3j interaction with an on-chain Groth16 verifier
 */
public class ZKPDemo {

    // ── Schnorr simulation (educational - uses BigInteger, not EC) ──
    static final BigInteger P = new BigInteger(
        "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16);
    static final BigInteger Q = P.subtract(BigInteger.ONE).divide(BigInteger.TWO);
    static final BigInteger G = BigInteger.valueOf(2);

    public static BigInteger[] schnorrProve(BigInteger x) throws Exception {
        SecureRandom rng = new SecureRandom();
        BigInteger r = new BigInteger(Q.bitLength(), rng).mod(Q);
        BigInteger Y = G.modPow(x, P);
        BigInteger R = G.modPow(r, P);

        // Fiat-Shamir challenge: c = H(Y || R)
        MessageDigest md = MessageDigest.getInstance("SHA-256");
        md.update(Y.toByteArray());
        md.update(R.toByteArray());
        BigInteger c = new BigInteger(1, md.digest()).mod(Q);

        BigInteger s = r.add(c.multiply(x)).mod(Q);
        return new BigInteger[]{ R, c, s };
    }

    public static boolean schnorrVerify(BigInteger Y, BigInteger[] proof) throws Exception {
        BigInteger R = proof[0], c = proof[1], s = proof[2];

        // Recompute challenge
        MessageDigest md = MessageDigest.getInstance("SHA-256");
        md.update(Y.toByteArray());
        md.update(R.toByteArray());
        BigInteger cCheck = new BigInteger(1, md.digest()).mod(Q);
        if (!cCheck.equals(c)) return false;

        // Check g^s == R * Y^c mod P
        BigInteger lhs = G.modPow(s, P);
        BigInteger rhs = R.multiply(Y.modPow(c, P)).mod(P);
        return lhs.equals(rhs);
    }

    // ── web3j: call deployed Groth16 verifier contract ──────────────
    // After running `snarkjs groth16 exportsolidityverifier circuit.zkey`
    // you get a Verifier.sol. Deploy it, then call verifyProof().
    public static boolean verifyOnChain(Web3j web3, String verifierAddress,
                                         BigInteger[] a,       // [2]    G1 point
                                         BigInteger[][] b,     // [2][2] G2 point
                                         BigInteger[] c2,      // [2]    G1 point
                                         BigInteger[] inputs)  // public signals
            throws Exception
    {
        // Load the auto-generated Java wrapper (web3j generate ...)
        Verifier verifier = Verifier.load(
            verifierAddress, web3,
            /* credentials */ null,
            new DefaultGasProvider()
        );

        // The snarkjs-generated Solidity verifier exposes:
        // function verifyProof(uint[2] a, uint[2][2] b, uint[2] c, uint[] input)
        //     external view returns (bool)
        return verifier.verifyProof(
            new org.web3j.abi.datatypes.generated.Uint256[]{
                new org.web3j.abi.datatypes.generated.Uint256(a[0]),
                new org.web3j.abi.datatypes.generated.Uint256(a[1])
            },
            new org.web3j.abi.datatypes.generated.Uint256[][]{
                { new org.web3j.abi.datatypes.generated.Uint256(b[0][0]),
                  new org.web3j.abi.datatypes.generated.Uint256(b[0][1]) },
                { new org.web3j.abi.datatypes.generated.Uint256(b[1][0]),
                  new org.web3j.abi.datatypes.generated.Uint256(b[1][1]) }
            },
            // ... c, inputs
        ).send();
    }

    public static void main(String[] args) throws Exception {
        // Simulate Schnorr proof
        BigInteger x = new BigInteger("12345678901234567890");
        BigInteger Y = G.modPow(x, P);
        BigInteger[] proof = schnorrProve(x);

        boolean valid = schnorrVerify(Y, proof);
        System.out.println("Schnorr proof valid: " + valid);

        // x = 3, Y = 2^3 mod P
        BigInteger x2 = BigInteger.valueOf(3);
        BigInteger Y2 = G.modPow(x2, P);
        BigInteger[] proof2 = schnorrProve(x2);
        System.out.println("Schnorr proof for x=3 valid: " + schnorrVerify(Y2, proof2));
    }
}

// ─── Requirements: go get github.com/consensys/gnark@latest ────
//     go get github.com/consensys/gnark-crypto@latest

package main

import (
	"fmt"
	"log"

	"github.com/consensys/gnark-crypto/ecc"
	"github.com/consensys/gnark/backend/groth16"
	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gnark/frontend/cs/r1cs"
	"github.com/consensys/gnark-crypto/ecc/bn254/fr/poseidon"
)

// ─── Circuit: prove x^3 + x + 5 == out ─────────────────────────
type CubicCircuit struct {
	X   frontend.Variable `gnark:",secret"`  // private witness
	Out frontend.Variable `gnark:",public"`  // public output
}

// Define adds R1CS constraints. Called once during setup.
func (c *CubicCircuit) Define(api frontend.API) error {
	// v1 = x * x
	v1 := api.Mul(c.X, c.X)
	// v2 = v1 * x  (= x^3)
	v2 := api.Mul(v1, c.X)
	// out == v2 + x + 5
	api.AssertIsEqual(c.Out, api.Add(v2, c.X, 5))
	return nil
}

func groth16Demo() {
	var circuit CubicCircuit

	// ── Compile to R1CS ────────────────────────────────────────
	ccs, err := frontend.Compile(ecc.BN254.ScalarField(), r1cs.NewBuilder, &circuit)
	if err != nil {
		log.Fatal("compile:", err)
	}
	fmt.Printf("Constraints: %d\n", ccs.GetNbConstraints()) // should be 3

	// ── Trusted setup (Groth16) ────────────────────────────────
	pk, vk, err := groth16.Setup(ccs)
	if err != nil {
		log.Fatal("setup:", err)
	}
	fmt.Println("Setup complete. pk size:", pk.NbG1(), "G1 elements")

	// ── Prove: x = 3, out = 35 ────────────────────────────────
	witness, err := frontend.NewWitness(&CubicCircuit{X: 3, Out: 35}, ecc.BN254.ScalarField())
	if err != nil {
		log.Fatal("witness:", err)
	}

	proof, err := groth16.Prove(ccs, pk, witness)
	if err != nil {
		log.Fatal("prove:", err)
	}
	fmt.Println("Proof generated:", proof)

	// ── Verify ────────────────────────────────────────────────
	publicWitness, _ := witness.Public()
	err = groth16.Verify(proof, vk, publicWitness)
	if err != nil {
		fmt.Println("Verification FAILED:", err)
	} else {
		fmt.Println("Proof VERIFIED ✓")
	}
}

// ─── Poseidon hash (gnark-crypto) ──────────────────────────────
func poseidonDemo() {
	// Poseidon is ZK-friendly: ~200 constraints vs ~20k for SHA256
	h, err := poseidon.New()
	if err != nil {
		log.Fatal(err)
	}
	h.Write([]byte("secret preimage"))
	digest := h.Sum(nil)
	fmt.Printf("Poseidon hash: %x\n", digest)

	// In a circuit you'd use: mimc.NewMiMC() or poseidon.NewPoseidon()
	// and call api.Commit(inputs...) to get a ZK-native commitment
}

// ─── zkVM-style: prove a general Go program ────────────────────
// SP1 (Succinct) and Risc0 support proving arbitrary Go programs
// compiled to RISC-V. The pattern:
//
//   sp1-sdk: https://github.com/succinctlabs/sp1
//   1. Write your Go/Rust program as normal
//   2. Compile to RISC-V ELF
//   3. sp1_prover.prove(elf_bytes, stdin_bytes) -> proof
//   4. Deploy SP1Verifier.sol, call verify(proof, public_values)
//
// Cost: ~1M gas onchain verification for any program up to 10^8 cycles

func main() {
	groth16Demo()
	poseidonDemo()
}