A recent paper by Benedikt Bünz, Jessica Chen, Zachary DeStefano, and Binyi
Chen proposing two new permutation arguments for use in modern SNARK protocols.
This repository aims to implement BiPerm and MulPerm efficiently in Rust.
ProdPerm, the HyperPlonk grand-product permutation check, is included as a
baseline to benchmark against. It's a work in progress which has not gone
through a formal audit and is not recommended for use in production systems.
Use at your own risk.
- Cryptology ePrint Archive
- Linear*-Time Permutation Check
- What we currently reference
- Almost Linear-Time Permutation Check
- Newer version w/ corrections, slight changes
- HyperPlonk, ProdPerm's product check
- §4.3 Sumcheck protocol: basis for both PIOPs.
- §4.4 Multilinear PCS: our PolynomialCommitment trait shape.
- §4.6 Lemma 4: the permutation-to-sumcheck reduction.
- §6 BiPerm + Algorithm 2: first PIOP to implement.
- §7 MulPerm + Algorithms 3-7: second PIOP to implement.
- §7.1 Algorithm 4: MulPerm's partial products as per-group table lookups.
- §7.2 Algorithm 5: MulPerm's first sumcheck, reducing to the claims
$v_j$ . - §7.3 Algorithm 7: the second sumcheck, proving
$v_j$ from$\tilde{\sigma}$ . - §7.3 Bucketing: the trick that gets MulPerm to
$n \cdot O(\sqrt{log(n)})$ . - §7.4 Setting
$\ell$ :$\ell = \sqrt{\mu}$ balances the two sumchecks. - Appendix B Algorithm 11: collapsing the bucketing tables.
This example comes directly from integration tests in BiPerm and shows what the
full protocol looks like using the Hyrax PCS. For an annotated implementation,
see that source. Integration tests also contain the full protocol using a
MockPcs, which are just full polynomials.
// biperm/tests/integration.rs
use ark_bn254::{Fr, G1Projective};
use ark_ff::UniformRand;
use ark_poly::DenseMultilinearExtension;
use ark_std::test_rng;
use biperm::permcore::{
MockPcs, Permutation, PolynomialCommitment, Transcript,
};
use biperm::{index, prove, verify};
use hyrax::Hyrax;
fn instance(
rng: &mut impl ark_std::rand::RngCore,
) -> (
Permutation,
DenseMultilinearExtension<Fr>,
DenseMultilinearExtension<Fr>,
) {
let perm = Permutation::new(vec![
5, 3, 7, 1, 0, 6, 2, 4, 9, 11, 8, 10, 13, 15, 12, 14,
])
.unwrap();
let num_vars = perm.num_vars();
let f_evals: Vec<Fr> =
(0..(1 << num_vars)).map(|_| Fr::rand(rng)).collect();
let mut g_evals = vec![Fr::from(0u64); perm.size()];
for x in 0..perm.size() {
g_evals[perm.apply(x)] = f_evals[x];
}
let f = DenseMultilinearExtension::from_evaluations_vec(num_vars, f_evals);
let g = DenseMultilinearExtension::from_evaluations_vec(num_vars, g_evals);
(perm, f, g)
}
#[test]
fn biperm_round_trip() {
let mut rng = test_rng();
let (perm, f, g) = instance(&mut rng);
let (pk, vk) =
Hyrax::<G1Projective>::setup(perm.num_vars() * 3 / 2, &mut rng)
.unwrap();
let (p_idx, v_idx) = index::<Fr, Hyrax<G1Projective>>(&pk, &perm).unwrap();
let mut prover_t = Transcript::new(b"integration");
let proof = prove(&pk, &p_idx, &f, &g, &mut prover_t).unwrap();
let mut verifier_t = Transcript::new(b"integration");
verify(&vk, &v_idx, &proof, &mut verifier_t).unwrap();
}- Commands should be run at the workspace level
- The same commands can be scoped to individual crates
# Optionally w/ --release
cargo buildstd(default): disable with--no-default-featuresforno_stdparallel: forwards to arkworks'parallelfeatures; not our own yet
cargo build --no-default-featuresUnit, integration, doc tests, and benches:
# All but benches
cargo test
# Test the benches would run
cargo test --bencheslib, bins, tests, examples, and benches:
# Treat all warnings as errors
cargo clippy --all-targets -- -D warningsRuns full measurement loops:
cargo benchxdg-open target/criterion/report/index.htmlThe index and prove benches expose both a shyrax (sparse) and a dhyrax
(dense) variant. Both use the same Hyrax backend --- biperm's index_with
picks the indicator representation (IndicatorRepr), so the dense path needs
no separate PCS. The gap is large for index (the indicator commit) and
isolated to the opens phase for prove. ProdPerm's benches expose mock and
hyrax (dense) only; nothing it commits is sparse, no variant to compare.
Criterion can snapshot a run and diff:
# Snapshot the index bench under a name
cargo bench --bench index -- --save-baseline beforeAfter a change, compare against it:
# Compare current index against baseline
cargo bench --bench index -- --baseline beforeOr run a specific argument:
# w/ index, prove, verify
cargo bench -p biperm --bench verify
cargo bench -p prodperm --bench verify
# eq table building block
cargo bench -p permcore --bench eqverify also prints a verifier footprint table per scheme and $\mu$.
A non-Criterion report (harness = false) for each phase's share of the call
per PCS scheme and target/; scripts derive the percentages.
For index, the two phases are aux_gen (auxiliary generation: BiPerm
builds the sparse indicator polynomials from commit (PCS-committing them),
"assemble" is ignored. They have no mid-call challenges, so the bench
reconstructs them by re-calling the public steps.
prove squeezes challenges mid-call (BiPerm tracing spans
(no-op without a subscriber) that the bench's capturing layer times. The phases
are commit, aux, sumcheck, and opens (the PCS opens summed via a shared
span name: four for BiPerm, eight for ProdPerm). verify squeezes the same
challenges, spanned the same way: sumcheck and pcs (summed like opens).
BiPerm's tables carry shyrax (sparse) and dhyrax (dense) rows, so you can
see which phase the sparse PCS moves: the index commit and the prove
opens. ProdPerm's carry mock and hyrax. Both verify tables carry mock
and hyrax only, since sparse and dense commitments are byte-identical.
cargo bench --bench phases
# Render as tables
scripts/index-phases-table.sh # biperm
scripts/prove-phases-table.sh # biperm
scripts/verify-phases-table.sh prodpermBiPerm against the prodperm grand-product baseline, per phase and per --run regenerates both back-to-back first,
which is the only way to guarantee both protocols saw the same machine state.
real (default) compares shyrax against hyrax, sparse BiPerm against
dense ProdPerm (hyrax against hyrax for verify); mock compares the
PIOP cost with no curve operations. MockPcs verifies by evaluating the whole
polynomial, so the mock verify pcs column isn't a PCS cost. BiPerm's
dhyrax has no ProdPerm counterpart because the arithmetization doesn't matter
due to the fact that sparsity doesn't matter in ProdPerm.
One per call, mirroring the table scripts:
scripts/index-phases-compare.sh
scripts/prove-phases-compare.sh
scripts/verify-phases-compare.sh
# PIOP cost only, no curve operations w/ mock
scripts/prove-phases-compare.sh mock
# Regenerate both breakdowns first
scripts/prove-phases-compare.sh --runWidth is time, vertical is call depth.
The benches double as profiling targets via pprof. Passing --profile-time
skips the timing analysis and samples the timed closure instead, writing an SVG
per benchmark id or filtering to a single id.
# Profile all, each 8s
cargo bench -- --profile-time=8
# Profile one id for 8s; single path example
# target/criterion/<group>/<id>/profile/flamegraph.svg
cargo bench --bench index -- --profile-time=8 'biperm_index/shyrax/12'From /// doc comments. LaTeX in doc comments is rendered by KaTeX, wired in
via katex-header.html and .cargo/config.toml. Use $…$ for inline math and
$$…$$ for display math.
# Build and open the API docs
cargo doc --no-deps --openClean what's generated:
cargo clean --doccargo fmt
# Verify only
cargo fmt --check-
permcore: Shared building blocks, library crate- permutation type, equality polynomial, Fiat-Shamir transcript, PCS trait, sumcheck, zerocheck, and product-check PIOPs
-
biperm: BiPerm implementation, library crate -
mulperm: MulPerm implementation, library crate- index, partial products, sumcheck 1 so far; power-of-two
$\mu$ only
- index, partial products, sumcheck 1 so far; power-of-two
-
prodperm: HyperPlonk-style grand-product, library crate- benchmarked against BiPerm, under Hyrax
-
hyrax: Hyrax PCS backend, library crate- transparent setup, binding-only; dense + sparse
- Use AI to assist in building a first version
- Walk through decisions, understand why's, what's best
- Separate dependency libs (internal/external) from paper code
- Specify learning in SKILL.md format to run through again
- Permutation check
$g(\sigma(x)) = f(x)$ reduces to a sumcheck via Lemma 4:$\Sigma_{x \in B_\mu} f(x) \cdot 1_\sigma(x, \alpha) = g(\alpha)$
- How
$1_\sigma (X, Y)$ is arithmetized (eg. BiPerm, MulPerm)- BiPerm: indicator polys are
$n^{1.5}$ , needs a sparse-friendly PCS (eg. Hyrax, Dory, KZH) to keep commitment cost linear-time - MulPerm: bucketing keeps prover at
$n \cdot O(\sqrt{log(n)})$ , any ML PCS
- BiPerm: indicator polys are
- Both protocols PIOPs (Polynomial Interactive Oracle Proofs)
- Multi-linear polynomial oracles, instantiated w/ PCS and Fiat-Shamir
- Soundness scales like
$polylog(n)/|F|$ - Authors target
$n = 2^{32}$ ,$|F| = 2^{128}$ .
- Authors target
- No other public Rust implementation of BiPerm/MulPerm.
arkworks: multi-linear extensions, fields, curves, serialization- Serialization:
CanonicalSerialize/CanonicalDeserializeturn commitments and proofs into bytes and back (required by our PCS trait)
- Serialization:
- HyperPlonk, Jolt, Plonky3, Spartan2, Binius relationships?
- PCS started w/ a
MockPcsfor Trait (introduced Hyrax) - BN254 field/curve, pairing friendly, Dory and KZG would need that
- Read more about this curve, details of it, why we choose it
- Multiple small crates (split per protocol, vs HyperPlonk's per layer)
- We use Merlin transcripts, do we want any others?
Ethereum precompiles (EIP-196/197).
BLS12-381 is the obvious upgrade if we ever need$\geq$ 128-bit security.
Goldilocks/BabyBear are non-starters without > extension fields.
linperm/
├── permcore/ # Shared building blocks
├── biperm/ # BiPerm prove/verify (indexed)
├── mulperm/ # MulPerm index (in progress)
├── prodperm/ # Grand-product prove/verify (indexed)
├── hyrax/ # Hyrax PCS backend (dense + sparse)
└── scripts/ # Developer tooling- Sumcheck per MulPerm
- Prover/verifier for MulPerm
- Index:
$\tilde{\sigma}$ table,$\tilde{\alpha}$ , groups - Partial products: Algorithm 4 table lookups
- Sumcheck 1:
$f \cdot \prod_j \tilde{p}$ , send$v_j$ - Sumcheck 2: slow oracle, then direct prover
- End to end: prove/verify, tamper tests
- Padding: any
$\mu$ , not just powers of two - Benches: index/prove/verify phases, baseline note
- Bucketing: Algorithms 6 and 11, bit-identical messages
-
$\ell$ benchmarks, three-way comparison with BiPerm/ProdPerm
- Index:
- PCS backend support (eg. Hyrax, Multi-linear KZG)
- Hyrax
- Dense + sparse
- Transparent setup
- Binding-only
- Batched openings, then re-run
- IPA (log-size openings)
- Hiding
- Hyrax
- Reference "Almost Linear-Time" paper
- Benchmarks by themselves, w/ HyperPlonk
- Grand-product baseline (
prodperm) over Hyrax
- Grand-product baseline (
- Prover-provided permutation
- Lookup generalization
- Benchmarks
- Parallelism
- FFT-based speedups
- Generalized BiPerm:
$\ell$ sparse indicators- (Shout-like), could be for benchmarks
/initialize-linperm: Bootstrap project