python-plonk-permutation-grand-product-fiat-shamir
Done. The verified solution is at ~/SOLUTION.md (self-contained: embeds the full source + tests), with the implementation in ~/plonk_permutation.py and tests in ~/test_plonk_permutation.py.
A naive PLONK grand-product implementation breaks in four independent ways:
% P on Python int, pow(x, P-2, P) for inverses, and an AST test asserting no float literals / no true division.beta, gamma without absorbing the whole commitment vector makes proofs malleable. Fixed with a domain-separated SHA-256 Transcript that length-prefixes every (wire, sigma) commitment before challenge derivation.Z[0], the Z(ω^n)=Z(ω^0) constraint is never checked. Fixed: grand_product defines only rows 1..n-1; check_grand_product enforces the row n-1 closure as a constraint. This is exactly what catches the tampered witness.NonBijectiveSigmaError vs WitnessVerificationError (plus TranscriptError).P = 28948022309329048855892746252171976963317496166410141009864396231776212615169 (255 bits, P−1 = 2^40 · odd) so power-of-two domains up to 2^40 exist.1, k2, k3) verified via x ∈ H ⟺ x^n = 1.14 passed in 0.03s
Z[0] = 1.NonBijectiveSigmaError (prover and verifier).WitnessVerificationError (grand-product relation fails at row 3).beta/gamma; different transcript labels give different challenges.(P−1)² mod P = 1 exactly, while the float path yields 52807088726587076576200884225.The embedded code blocks in the markdown were programmatically confirmed to byte-match the files that passed the tests.
# Evidence - Problem class: python-plonk-permutation-grand-product-fiat-shamir - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-23T10:04:36.034Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a minimal PLONK-style permutation argument over a 255-bit prime field: from a circuit's three wire polynomials, s1..s3 identity-permutation polynomials and beta/gamma challenges, build the grand-product polynomial Z(X) and verify the copy constraints. Provide prover and verifier halves with a domain-separated Fiat-Shamir transcript (challenge derivation must bind the commitment vector), plus tests proving a non-bijective sigma mapping and a tampered witness are both rejected with distinct errors. All arithmetic must be exact modular integer math with no floating point anywhere.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-plonk-permutation-grand-product-fiat-shamir", "provider": "openrouter", "solved_at": "2026-09-23T10:04:36.035Z", "version": "3.12"}Done. The verified solution is at ~/SOLUTION.md (self-contained: embeds the full source + tests), with the implementation in ~/plonk_permutation.py and tests in ~/test_plonk_permutation.py.
A naive PLONK grand-product implementation breaks in four independent ways:
% P on Python int, pow(x, P-2, P) for inverses, and an AST test asserting no float literals / no true division.beta, gamma without absorbing the whole commitment vector makes proofs malleable. Fixed with a domain-separated SHA-256 Transcript that length-prefixes every (wire, sigma) commitment before challenge derivation.Z[0], the Z(ω^n)=Z(ω^0) constraint is never checked. Fixed: grand_product defines only rows 1..n-1; check_grand_product enforces the row n-1 closure as a constraint. This is exactly what catches the tampered witness.NonBijectiveSigmaError vs WitnessVerificationError (plus TranscriptError).P = 28948022309329048855892746252171976963317496166410141009864396231776212615169 (255 bits, P−1 = 2^40 · odd) so power-of-two domains up to 2^40 exist.1, k2, k3) verified via x ∈ H ⟺ x^n = 1.14 passed in 0.03s
Z[0] = 1.NonBijectiveSigmaError (prover and verifier).WitnessVerificationError (grand-product relation fails at row 3).beta/gamma; different transcript labels give different challenges.(P−1)² mod P = 1 exactly, while the float path yields 52807088726587076576200884225.The embedded code blocks in the markdown were programmatically confirmed to byte-match the files that passed the tests.
# Evidence - Problem class: python-plonk-permutation-grand-product-fiat-shamir - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-23T10:04:36.034Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a minimal PLONK-style permutation argument over a 255-bit prime field: from a circuit's three wire polynomials, s1..s3 identity-permutation polynomials and beta/gamma challenges, build the grand-product polynomial Z(X) and verify the copy constraints. Provide prover and verifier halves with a domain-separated Fiat-Shamir transcript (challenge derivation must bind the commitment vector), plus tests proving a non-bijective sigma mapping and a tampered witness are both rejected with distinct errors. All arithmetic must be exact modular integer math with no floating point anywhere.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-plonk-permutation-grand-product-fiat-shamir", "provider": "openrouter", "solved_at": "2026-09-23T10:04:36.035Z", "version": "3.12"}