Benchmark
non-incremental/QF_ANIA/20211213-GrandProduct-Ozdemir/sound/same/9.smt2
# The special soundness of PLONK's grand product argument
Let F be a prime-order field and n a natural less than F's size. Let n = {1,
2, .., n} be a subset of F. The PLONK[1] grand product argument relies on the
fact that given a permutation pi: [n] -> [n] and functions A, B: [n] -> [n],
prod_i (A(i) + beta * i + gamma) = prod_i (B(i) + beta * pi(i) + gamma)
holds for random beta, gamma in F with good probability only when A composed
with pi is B.
Does this implication hold in a deterministic setting, where the above is
checked for distinct---but non-random---beta and gamma?
If it is checked for n+1 distinct values of beta, and for each value of beta,
n+1 distinct values of gamma, then yes. One can prove this.
If it is checked for 2 distinct values of beta, and for each value of beta, n+1
distinct values of gamma, then no.
This series of benchmarks checks the implication holds
* for varying n
* for a fixed permutation pi = (2 3 ... n 1)
* for all A and B
* that must be equal ("same") or may differ ("diff")
* for all distinct 2 ("unsound") or n+1 ("sound") beta values
rather than instantiating gamma explicitly, we just check that the multisets
{{A[i] + beta * i}}_i == {{B[i] + beta * pi(i)}}_i
are equal.
[1]: https://eprint.iacr.org/2019/953
| Benchmark |
|---|
| Size | 24258 |
| Compressed Size | 5659 |
| License |
Creative Commons Attribution 4.0 International
(CC-BY-4.0)
|
| Category | crafted |
| First Occurrence | 2022-08-10 |
| Generated By | Alex Ozdemir |
| Generated On | 2021-12-13 00:00:00 |
| Generator | Z3Py API |
| Dolmen OK | 1 |
| strict Dolmen OK | 1 |
| check-sat calls | 1 |
| Status | unsat |
| Inferred Status | None |
| Size | 24250 |
| Compressed Size | 5679 |
| Max. Term Depth | 50 |
| Asserts | 57 |
| Declared Functions | 0 |
| Declared Constants | 29 |
| Declared Sorts | 0 |
| Defined Functions | 0 |
| Defined Recursive Functions | 0 |
| Defined Sorts | 0 |
| Constants | 0 |
| Declared Datatypes | 0 |
Symbols
true | 1 |
not | 1 |
and | 2 |
= | 28 |
distinct | 1 |
let | 451 |
+ | 360 |
* | 90 |
<= | 18 |
>= | 18 |
select | 180 |
store | 180 |
Evaluations
| Evaluation |
Rating |
Solver |
Variant |
Result |
Wallclock |
CPU Time |
|
SMT-COMP 2022
|
1.00 (0/4) |
CVC4 |
CVC4-sq-final_default |
unknown ❌
|
1200.04000
|
1199.73000
|
| |
cvc5 |
cvc5-default-2022-07-02-b15e116-wrapped_sq |
unknown ❌
|
1200.04000
|
1199.66000
|
| |
MathSAT |
MathSAT-5.6.8_default |
unknown ❌
|
1200.02000
|
1199.86000
|
| |
Z3 |
z3-4.8.17_default |
unknown ❌
|
1200.02000
|
1199.72000
|
|
SMT-COMP 2023
|
1.00 (0/4) |
CVC4 |
CVC4-sq-final_default |
unknown ❌
|
1200.02000
|
1199.00000
|
| |
cvc5 |
cvc5-default-2023-05-16-ea045f305_sq |
unknown ❌
|
1200.12000
|
1199.95000
|
| |
SMTInterpol |
smtinterpol-2.5-1272-g2d6d356c_default |
unknown ❌
|
1200.08000
|
1233.70000
|
| |
Yices2 |
Yices 2 for SMTCOMP 2023_default |
unknown ❌
|
1200.10000
|
1199.84000
|
|
SMT-COMP 2024
|
1.00 (0/3) |
cvc5 |
cvc5 |
unknown ❌
|
1201.72495
|
1201.09618
|
| |
SMTInterpol |
SMTInterpol |
unknown ❌
|
1201.71860
|
1249.63106
|
| |
Yices2 |
Yices2 |
unknown ❌
|
1201.25511
|
1200.57508
|
|
SMT-COMP 2025
|
1.00 (0/3) |
cvc5 |
cvc5 |
unknown ❌
|
1201.77178
|
1200.97549
|
| |
SMTInterpol |
SMTInterpol |
unknown ❌
|
1201.42777
|
1255.27343
|
| |
Yices2 |
Yices2 |
unknown ❌
|
1201.88669
|
1201.54472
|