Comparing Polynomial Commitments

For a degree-$d$ polynomial:

	FRI	KZG	IPA	DARK
Building Block	Hash Function	Elliptic Curve Pairings	Discrete Log Group	Unknown Order Group
Computational Hardness Assumption	Hash Functions	DLP, t-SDH, t-BSDH (for multi-reveal)	DLP	DLP, q-HSM, Low Order & Strong Root Assumptions
Transparent (no trusted setup)	Yes	No	Yes	No (RSA) / Yes (Ideal Class Groups)
Succinct1 proofs	Yes	Yes	No	Yes
Post-quantum secure	Yes	No	No	No
Proof size	$O({\log }^{2}d)$	$O(1)$	$O(\log d)$	$O(\log d)$
Proving time	$O(d{\log }^{2}d)$	$O(d)$	$O(d)$	$O(d)$
Verification time	$O({\log }^{2}d)$	$O(1)$	$O(\log d)$	$O(\log d)$

In practice, for post-quantum secure polynomial commitment schemes:

• degree ~1: see TCitH-GGM (Seed trees)
• degree ~10: degree-enforcing commitment (TCitH-MT)
• degree: 1,000: Merkle Tree with Ligero-like proximity tests
• degree 10,000: FRI-based commitments

Footnotes

1. Succinct is not really well-defined: can either mean polylog or constant. ↩