Zero-knowledge (commit · trace · circuit)

Commitment, trace-capture and circuit micro-benchmarks for the research-grade ZK estate (commit · canonicalisation · trace · circuit gates). Research-grade only — the v1 verifier is not externally audited, so these are indicative engineering numbers, not an audited cryptographic guarantee.

Latest commit a40cf2a1 · every metric smaller-is-better · each group header shows a competitive summary computed live from real same-box competitor numbers (or an honest placeholder where none exist yet).

Circuit gate & proving-time cost

Per-member cost for the sparq ZK circuit family, sorted by gate count. Gate counts are the deterministic bb gates -s ultra_honk (circuit_size) snapshot (bb 5.0.0-nightly.20260324, nargo 1.0.0-beta.21) — the only figures of record here. Proving times are indicative / non-canonical and are shown only where a measurement exists (“—” = unmeasured, not estimated).

Research-grade, not externally audited. Composition verifier NOT-yet-sound (sq-qhy4/sq-9hrn/sq-1s2). Research-grade, NOT externally audited. MPC layer (separate) is semi-honest. A 'verified' result is not production-trustworthy. A fast or passing proof is not a soundness or privacy guarantee.

Member	Gates (circuit_size)	Prove t1 (indic.)	Prove t8 (indic.)
scan_k2_n64_r8scan · heaviest	34,821	—	—
scan_k2_n64_r4scan	27,054	—	—
scan_k1_n64_r8scan	18,850	—	—
join_eq_na64_nb64join	18,681	—	—
filter_int_d1filter	17,416	—	—
filter_int_d2filter · live in-browser	17,416	1314 ms	469 ms
filter_int_d3filter	17,416	—	—
filter_int_d4filter	17,416	—	—
filter_signed_int_d2filter	17,416	—	—
filter_signed_int_d4filter	17,416	—	—
filter_decimal_i3_f2filter	17,416	—	—
filter_f64_d1filter	17,416	—	—
filter_f64_d2filter	17,416	—	—
filter_f64_d3filter	17,416	—	—
filter_f64_d4filter	17,416	—	—
hidden_issuer_d4issuer	16,946	—	—
scan_k1_n64_r4scan	14,923	—	—
join_eq_na16_nb64join	12,885	—	—
join_eq_na64_nb16join	12,885	—	—
scan_k2_n16_r8scan	11,261	—	—
holder_set_d4holder	10,650	—	—
holder_pokholder	10,334	—	—
scan_k2_n16_r4scan	9,254	—	—
scan_k1_n16_r8scan	7,038	—	—
join_eq_na16_nb16join	7,025	—	—
scan_k1_n16_r4scan	5,991	—	—
filter_f64filter	3,113	—	—
revoke_unset_d10revoke · cheapest	899	—	—

Hotspots

Scan is the heavy end — scan_k2_n64_r8 is heaviest at 34,821 gates (per-graph Poseidon2 commitment recompute + the completeness double-loop).
In-circuit signature verification is expensive — hidden_issuer_d4 at 16,946 gates (two ~251-bit twisted-Edwards scalar muls dominate; the heaviest non-scan / non-filter operator).
Filter is flat in digit-count — every filter_* token-binding member is 17,416 gates (the blake3 token fits one 64-byte block; D only changes what leaks).
Cheapest — revoke_unset_d10 at 899 gates (a depth-10 Merkle bit-unset).

Proof size & verify — constant across the family

UltraHonk succinctness: proof, vk size and verify time do not vary by member.

Proof: 14.3 KB (noir-recursive) / 8.2 KB (evm/keccak, still zero-knowledge)
Verifying key: 3.6 KB
Verify: ~12 ms (aarch64, indicative)

Browser single-thread overhead (~4.2×)

The deployed GitHub Pages demo is forced single-threaded: bb.js worker fan-out needs SharedArrayBuffer, which requires cross-origin isolation that Pages cannot set. A COI service-worker shim is the lever that unlocks multithreaded proving.

On the one live member (filter_int_d2): prove 1314 ms single-thread → 469 ms at 8 threads (indicative). Threads change only speed, never the proof or its zero-knowledge property.

prove_ms_* are INDICATIVE / NON-CANONICAL native bb prove wall-clock on a shared EC2 box (includes process startup + CRS/SRS load); populated only where measured; null = unmeasured (not fabricated). Verify time, proof bytes and vk bytes are constant across the family and are not per-member fields.

SPARQL feature → ZK gate-cost catalog

A coverage map across SPARQL 1.1: for each query shape, which ZK circuit member(s) it compiles to today and that member’s circuit size. The numbers are deterministic bb gates -s ultra_honk circuit-size metrics (bb 5.0.0-nightly.20260324, nargo 1.0.0-beta.21) joined from the regression-gated gate snapshot — not a throughput or wall-clock measurement. Gaps carry no number (never fabricated).

26 queries12 covered5 partial9 no circuit yet

Research-grade, not externally audited. These are gate-count (circuit-size) figures, not a performance benchmark and not an audited cryptographic guarantee. The v1 composition verifier is research-grade and has not been externally audited (bead sq-qhy4); a covered row is not a soundness or privacy guarantee to a relying party.

blake3-binding — the numeric-FILTER family. High because of the blake3 token-binding; the value-hook reduction target.

scan/join lattice corner — big for a different reason (the (k,n,r)/(na,nb) lattice), not a value-hook target.

no circuit yet — greyed; the feature is not yet ZK-provable. No gate number.

SPARQL feature / query shape	ZK circuit member(s) (per-member gates)	Gates (circuit_size)	Status
Basic graph patterns
BGP (1 triple pattern)`SELECT ?s ?o WHERE { ?s :p ?o }`	scan_k1_n16_r45,991 scan_k1_n16_r87,038 scan_k1_n64_r414,923 scan_k1_n64_r818,850	18,850range 5,991–18,850	coveredscan/join lattice corner
BGP (multi-pattern, single graph)`SELECT ?s ?v WHERE { ?s :p ?o . ?s :q ?v }`	scan_k2_n16_r49,254 scan_k2_n16_r811,261 scan_k2_n64_r427,054 scan_k2_n64_r834,821	34,821range 9,254–34,821	coveredscan/join lattice corner
Numeric & typed FILTER
FILTER xsd:integer (>=, <, =, !=)`SELECT ?p WHERE { ?p :age ?age FILTER(?age >= 18) }`	filter_int_d117,416 filter_int_d217,416 filter_int_d317,416 filter_int_d417,416	17,416	coveredblake3-binding · reduction target
FILTER signed xsd:integer (negative operands)`SELECT ?a WHERE { ?a :balance ?bal FILTER(?bal >= -100) }`	filter_signed_int_d217,416 filter_signed_int_d417,416	17,416	coveredblake3-binding · reduction target
FILTER xsd:decimal`SELECT ?o WHERE { ?o :amount ?amt FILTER(?amt <= 199.99) }`	filter_decimal_i3_f217,416	17,416	coveredblake3-binding · reduction target
FILTER xsd:double (IEEE-754 compare)`SELECT ?x WHERE { ?x :reading ?d FILTER(?d > 42.0) }`	filter_f64_d117,416 filter_f64_d217,416 filter_f64_d317,416 filter_f64_d417,416	17,416	coveredblake3-binding · reduction target
FILTER boolean / term = literal`SELECT ?x WHERE { ?x :active ?flag FILTER(?flag = true) }`not yet ZK-provable	—	—	no circuit yet
FILTER string ops (STR, REGEX, CONTAINS, STRLEN)`SELECT ?x WHERE { ?x :name ?n FILTER(CONTAINS(STR(?n), "a")) }`not yet ZK-provable	—	—	no circuit yet
FILTER xsd:dateTime compare`SELECT ?e WHERE { ?e :when ?d FILTER(?d >= "2020-01-01T00:00:00Z"^^xsd:dateTime) }`not yet ZK-provable	—	—	no circuit yet
Join & property paths
JOIN on a shared variable (hidden equi-join)`SELECT ?p ?s WHERE { ?p :worksFor :ACME . ?p :hasSalary ?s }`	join_eq_na16_nb167,025 join_eq_na16_nb6412,885 join_eq_na64_nb1612,885 join_eq_na64_nb6418,681	18,681range 7,025–18,681	coveredscan/join lattice corner
Property path / (sequence)`SELECT ?o WHERE { ?s :p/:q ?o }`	scan_k2_n16_r49,254 scan_k2_n16_r811,261 scan_k2_n64_r427,054 scan_k2_n64_r834,821	34,821range 9,254–34,821	coveredscan/join lattice corner
Property path ^ (inverse)`SELECT ?s WHERE { ?o ^:p ?s }`	scan_k1_n16_r45,991 scan_k1_n16_r87,038 scan_k1_n64_r414,923 scan_k1_n64_r818,850	18,850range 5,991–18,850	coveredscan/join lattice corner
Property path \| (alternative)`SELECT ?o WHERE { ?s (:p\|:q) ?o }`	verifier-side / desugars to a covered primitive	—	partial
Property path ? (zero-or-one)`SELECT ?o WHERE { ?s :p? ?o }`not yet ZK-provable	—	—	no circuit yet
Property path + (one-or-more, transitive closure)`SELECT ?o WHERE { :s :p+ ?o }`not yet ZK-provable	—	—	no circuit yet
Property path * (zero-or-more, reflexive transitive closure)`SELECT ?o WHERE { :s :p* ?o }`not yet ZK-provable	—	—	no circuit yet
Composition (OPTIONAL / UNION / subquery / …)
OPTIONAL (left join)`SELECT ?s ?v WHERE { ?s :p ?o OPTIONAL { ?s :q ?v } }`	verifier-side / desugars to a covered primitive	—	partial
UNION`SELECT ?s WHERE { { ?s :p ?o } UNION { ?s :q ?o } }`	verifier-side / desugars to a covered primitive	—	partial
Subquery (nested SELECT)`SELECT ?p WHERE { ?p :a ?x { SELECT ?p WHERE { ?p :b ?y } } }`	verifier-side / desugars to a covered primitive	—	partial
VALUES (inline data)`SELECT ?x WHERE { VALUES ?x { :a :b } ?x :p ?o }`	verifier-side / desugars to a covered primitive	—	partial
Aggregation, BIND & negation
Aggregate / GROUP BY (COUNT, SUM, AVG, MIN, MAX)`SELECT ?g (COUNT(?x) AS ?n) WHERE { ?x :inGroup ?g } GROUP BY ?g`not yet ZK-provable	—	—	no circuit yet
BIND (expression evaluation)`SELECT ?c WHERE { ?s :a ?a . ?s :b ?b BIND(?a + ?b AS ?c) }`not yet ZK-provable	—	—	no circuit yet
Negation (FILTER NOT EXISTS / MINUS)`SELECT ?s WHERE { ?s :p ?o FILTER NOT EXISTS { ?s :q ?v } }`not yet ZK-provable	—	—	no circuit yet
Hidden-credential primitives
Revocation / status (hidden status-list index)`ASK { ?cred :revocationStatus ?bit FILTER(?bit = 0) }`	revoke_unset_d10899	899	covered
Issuer attestation (hidden tier, Schnorr)`ASK { ?cred :issuer ?iss FILTER(?iss IN (:tierA, :tierB)) }`	hidden_issuer_d416,946	16,946	covered
Holder possession (hidden binding)`ASK { ?cred :holder ?h FILTER(?h = :me) }`	holder_pok10,334 holder_set_d410,650	10,650range 10,334–10,650	covered

Value-hook reduction target (projection — not yet measured)

The numeric-FILTER family currently measures 17,416 gates (driven by the blake3 token-binding, gate-identical across digit count). The field-native value-hook encoding is a projected reduction to ~3,200 gates — an estimate that must be re-measured with bb gates; it is not an achieved result, and lands only after the external audit (CR-G8 / sq-qhy4). For context, the raw-compare floor member filter_f64 (no token-binding) measures 3,113 gates — a measured lower bound on the achievable size.

Projection string from the canonical catalog: “ESTIMATE ~3200 — MUST be re-measured with bb gates (NOT a measurement)”

Source: bench/zk-compose/sparql_feature_catalog.json (regenerated by scripts/sparql_catalog.py; every covered circuit_size is joined from gate_count_snapshot.json and regression-gated, so it cannot drift).

No same-box competitor baseline has been gathered for this suite yet — sparq's absolute numbers are shown below.

Benchmark	sparq	Unit
zk compose filter decimal i3 f2 gates`zk_compose_filter_decimal_i3_f2_gates`	17,416	gates
zk compose filter f64 d1 gates`zk_compose_filter_f64_d1_gates`	17,416	gates
zk compose filter f64 d2 gates`zk_compose_filter_f64_d2_gates`	17,416	gates
zk compose filter f64 d3 gates`zk_compose_filter_f64_d3_gates`	17,416	gates
zk compose filter f64 d4 gates`zk_compose_filter_f64_d4_gates`	17,416	gates
zk compose filter int d3 gates`zk_compose_filter_int_d3_gates`	17,416	gates
zk compose filter signed int d2 gates`zk_compose_filter_signed_int_d2_gates`	17,416	gates
zk compose filter signed int d4 gates`zk_compose_filter_signed_int_d4_gates`	17,416	gates
zk compose filter value dl decimal gates`zk_compose_filter_value_dl_decimal_gates`	3,070	gates
zk compose filter value dl f64 gates`zk_compose_filter_value_dl_f64_gates`	4,157	gates
zk compose filter value dl int gates`zk_compose_filter_value_dl_int_gates`	3,033	gates
zk compose hidden issuer d4 gates`zk_compose_hidden_issuer_d4_gates`	16,946	gates
zk compose holder pok gates`zk_compose_holder_pok_gates`	10,334	gates
zk compose holder set d4 gates`zk_compose_holder_set_d4_gates`	10,650	gates
zk compose join eq na16 nb64 gates`zk_compose_join_eq_na16_nb64_gates`	12,885	gates
zk compose join eq na64 nb16 gates`zk_compose_join_eq_na64_nb16_gates`	12,885	gates
zk compose join eq na64 nb64 gates`zk_compose_join_eq_na64_nb64_gates`	18,681	gates
zk compose revoke unset d10 gates`zk_compose_revoke_unset_d10_gates`	899	gates
zk compose scan k1 n16 r8 gates`zk_compose_scan_k1_n16_r8_gates`	7,038	gates
zk compose scan k1 n64 r4 gates`zk_compose_scan_k1_n64_r4_gates`	14,923	gates
zk compose scan k1 n64 r8 gates`zk_compose_scan_k1_n64_r8_gates`	18,850	gates
zk compose scan k2 n16 r4 gates`zk_compose_scan_k2_n16_r4_gates`	9,254	gates
zk compose scan k2 n64 r4 gates`zk_compose_scan_k2_n64_r4_gates`	27,054	gates