arXiv CSopen access

ZK-Value: A Practical Zero-Knowledge System for Verifiable Data Valuation

arXiv:2605.03581v1 [cs.CR] 5 May 2026

ZK-Value: A Practical Zero-Knowledge System for Verifiable Data Valuation Zhaoyu Wang

Pingchuan Ma∗

Zhantong Xue

Yuguang Zhou

HKUST Kowloon, Hong Kong SAR

Zhejiang University of Technology Hangzhou, China

HKUST Kowloon, Hong Kong SAR

HKUST Kowloon, Hong Kong SAR

Qixin Zhang

Xiaoqin Zhang

Shuai Wang

Nanyang Technological University Singapore

Zhejiang University of Technology Hangzhou, China

HKUST Kowloon, Hong Kong SAR

ABSTRACT Data valuation is a foundational task in data marketplaces, where a Shapley-value attribution determines how a buyer’s payment is distributed among data providers. Typically, the marketplace operator runs this attribution alone, requiring participants and external auditors to trust scores they cannot independently recompute on the underlying private data. While zero-knowledge proofs (ZKPs) can theoretically reconcile this conflict between privacy and verifiability, existing ZK valuation systems fail to scale to real-world marketplace demands due to prohibitive proving times or the requirement to disclose validation cohorts. We present ZK-VALUE, a practical, end-to-end ZK data-valuation system. Our solution bridges the scalability gap through a fully codesigned architecture: (1) LSH-Shapley, a locality-based valuation primitive that replaces expensive pairwise distance metrics with perbucket collision counts; (2) ZK-LSH-SHAPLEY, a tailored ZKP protocol that drastically reduces witness size by encoding these counts into bucket-level histograms rather than naive per-pair tensors; and (3) structural proof-system optimizations, specifically superoracle batching and sparsity skipping. Evaluated across 12 standard datasets, ZK-Value delivers valuation quality on par with stateof-the-art baselines (within 0.033 AUROC of exact KNN-Shapley), while generating proofs in seconds to minutes and outperforming specialized ZK baselines by 12.6× to 68.1× in proving time, with verification in under 4.6 s.

1

INTRODUCTION

Training data is now a paid commodity traded through data marketplaces [6, 8, 23, 29]. A typical marketplace [9, 35] brings together data providers, a buyer who pays for aggregated data to train a downstream model, a marketplace operator who runs the transaction, and external auditors who oversee compliance. Every transaction hinges on data valuation [39, 51]: how should payment be divided among providers so that each share reflects the value its data contributes to the buyer’s downstream task? To date, Shapley value [14, 20, 24, 47, 48] has become the de facto standard for answering this question in a principled way. Each provider is credited in proportion to the marginal gain its data brings, averaged over all coalitions and scored on the buyer’s validation cohort. As a well-known limitation of the Shapley value, however, computing it ∗ Corresponding author (email: [email protected]).

directly is often intractable; the community has therefore developed a variety of ML-specific surrogates, e.g., KNN-Shapley [20], that are tractable at modern training-set sizes and feature dimensions. Despite the progress in efficiency, however, the Shapley value and its surrogates remain technically unverifiable in the data valuation setting. The marketplace operator, who runs the valuation and earns a fee on each transaction, has a direct financial motive to skew the payout, and nothing in the setup prevents it from substituting a cheaper approximation, steering payouts toward a preferred counter-party, or delivering data different from what the valuation actually saw. Each non-operator party is thus left with an unauditable concern, and no party can settle that concern without the raw-data access that privacy forbids. The claimed scores are accepted in practice yet remain technically unverifiable, a fundamental conflict between privacy and verifiability at the heart of modern data marketplaces. Example 1.1 (Hospital Consortium Data Marketplace). Consider a consortium of hospitals selling de-identified patient data to a pharmaceutical buyer training a drug-response classifier. The operator splits the buyer’s $1M payment across hospitals according to Shapley values scored on the buyer’s validation cohort. Suppose the operator quietly shifts 5% of the payout from a small rural hospital to a large client hospital by tampering with score entries. As Figure 1 illustrates, no other party can catch the shift: the rural hospital sees only its reduced payment with no way to verify the correct amount, the regulator sees the published scores but is barred from patient records needed to recompute, and the buyer has no standing to audit payout allocations. The only recourse, i.e., recomputing scores on raw patient data, is exactly what privacy policy and regulations forbid. Breaking this deadlock demands privacy-preserving and verifiable data valuation. Zero-knowledge proofs as the bridge. As a cryptographic primitive, zero-knowledge proofs (ZKPs) [2, 16, 44] offer a principled way to reconcile privacy with verifiability. By allowing a prover to demonstrate that a computation was executed correctly on hidden inputs without revealing the inputs themselves, ZKPs have already seen successful deployment in important areas like ML inference [5], SQL query processing [18, 27], and data analytics [49]. However, a cryptographic building block alone does not make a practical marketplace protocol. Adapting this primitive to a multiparty data marketplace dictates four system-level properties that

Zhaoyu Wang, Pingchuan Ma, Zhantong Xue, Yuguang Zhou, Qixin Zhang, Xiaoqin Zhang, and Shuai Wang

Provider A (rural hospital) fair share?

Buyer tr

payout A

(client hospital) fair share?

$1

Marketplace Operator

(pharma) honest score??

𝐷 tr

financial motive to skew the payout

payout B

Provider B

l

𝐷 vaM

𝐷𝐴

sc 𝐵

𝐷 tr

or e

Ext. Auditor (regulator / press) no raw access

Figure 1: The verifiability gap in a data marketplace.

Table 1: Requirements (P-1)–(P-4) coverage by solution families and ZK-Value. ✓ = met, ✗ = not met, ◦ = partial. Solution family

P-1

P-2

P-3

P-4

DP/MPC valuation ZK-DV ZK encoding of existing Shapley ZK-Value (ours)

✗ ✓ ✓ ✓

✓ ◦ ◦ ✓

✗ ✗ ✓ ✓

✗ ✗ ✗ ✓

any deployable verifiable data-valuation protocol must jointly satisfy. (P-1) Public verifiability: the protocol produces a single noninteractive proof that any third party verifies locally. (P-2) Data privacy with commitment binding: third-party verifiers learn nothing about the private inputs beyond what the released scores reveal, and commitments bind each party to the data it contributed. (P-3) Operator-as-prover architecture: the prover role can only be filled by a party that both holds every valuation input and operates infrastructure capable of amortizing ZK proving across transactions, where only the operator satisfies both conditions. (P-4) Practical cost at modern ML scale: proving must remain tractable at modern ML training scale, and verification cheap enough for any third party to check the proof quickly. Limitations of existing solutions. Table 1 shows three representative families each fail at least one requirement (P-1)–(P-4). (1) DP/MPC methods [36, 45, 48] hide raw data but lack non-interactive correctness proofs for third-party verification, failing (P-1). (2) ZKDV [30], a concurrent work and the only other ZK data-valuation system, forces buyers to disclose validation data to sellers (partial P-2 failure) and requires sellers to run individual provers, forfeiting the marketplace cost-sharing of a shared operator (failing P-3) (3) ZK encodings of existing Shapley algorithms [25, 52] inherit prohibitive computational costs (failing P-4); for example, KNN-Shapley [20, 48] requires 𝑁 ·𝑇 ·𝑑 work plus a top-𝑘 sort, while retraining [14, 24, 47] and gradient variants [22] scale even worse. Satisfying all four properties simultaneously requires co-designing the valuation algorithm with its proof system, which is the approach ZK-Value takes. Our Solution. We present ZK-Value, the first practical ZK datavaluation system deployable in a real marketplace. ZK-Value adopts

a multi-party architecture: providers and the buyer publish hidingand-binding commitments to their datasets, while a marketplace operator computes valuation scores and produces a single noninteractive zero-knowledge proof attesting that the scores are consistent with all commitments. To make proving costs practical at modern ML scale, we codesign the valuation algorithm and proof system.We introduce LSH-Shapley (§4), which hashes data into locality-sensitive buckets and computes Shapley values from bucket histograms, avoiding explicit pairwise distance computations. We pair this with ZK-LSHShapley (§4.2), a tailored ZKP protocol commits only to per-bucket histograms and proves scores directly against them. With optimizations such as super-oracle batching and sparsity skipping (§5), this system enforces input integrity, satisfies (P-1)–(P-4), and reduces per-valuation proving time to a practical seconds-to-minutes range. We evaluate ZK-Value on 12 standard valuation datasets at realistic marketplace sizes. On valuation quality, ZK-Value tracks exact KNN-Shapley within 0.033 AUROC across all datasets while outperforming gradient-based and Monte-Carlo Shapley baselines. On end-to-end proving cost, ZK-Value achieves 12.6× to 68.1× speedups over specialized ZK baselines for KNN- and LSH-Shapley, proves a full valuation in seconds on tabular workloads with verification under 4.6 s, and is the only system that scales to highdimensional ViT-embedding workloads. Contributions. In summary, our contributions are: • Conceptually, we identify and formulate privacy-preserving and verifiable data valuation as a first-class problem arising in crossorganizational data marketplaces, and distill a four requirements ((P-1)–(P-4)) for practical solutions. • Technically, we present ZK-Value, a multi-party ZK data valuation system with an operator-as-prover architecture, built on a co-design of the valuation algorithm and underlining proof system: (i) LSH-Shapley, a Shapley-family algorithm that replaces KNN-Shapley’s pairwise-distance cost with per-bucket collision counts, and (ii) ZK-LSH-Shapley, a specialized ZK protocol that certifies LSH-Shapley scores efficiently, together with two proofsystem optimizations (super-oracle batching and sparsity skipping) that further reduce proof size and prover time. • Empirically, our evaluation across 12 datasets demonstrates that ZK-Value preserves strong valuation quality (within 0.033 AUROC of exact KNN-Shapley) while reducing ZK proving time by 12.6× to 68.1× over specialized ZK baselines and verifying in under 4.6 s.

2

BACKGROUND

This section recaps the three ingredients ZK-Value rests on: Shapleyvalue data valuation (§2.1), zero-knowledge SNARKs (§2.2), and locality-sensitive hashing (§2.3).

2.1

Data Valuation via Shapley Values

Shapley value. Given a utility function 𝑢 : 2 [𝑁 ] → R that scores any subset of the 𝑁 training points (e.g., the accuracy the buyer’s model attains on the validation cohort after training on that subset), the Shapley value 𝜙𝑖 of point 𝑖 is its weighted average marginal

ZK-Value : A Practical Zero-Knowledge System for Verifiable Data Valuation

contribution across every coalition of the other points [38]: 𝜙𝑖 =

∑︁ 𝑆 ⊆ [𝑁 ]\{𝑖 }

|𝑆 |! (𝑁 − |𝑆 | − 1)! 𝑢 (𝑆 ∪ {𝑖}) − 𝑢 (𝑆) . 𝑁!

𝜙𝑖 is uniquely characterized by four fairness axioms (efficiency, symmetry, dummy-player, linearity) [43]. Direct evaluation enumerates 2𝑁 −1 coalitions and retrains the utility on each, so it is #P-hard for a general utility and infeasible at realistic marketplace sizes. This has motivated utility-specific closed forms that sidestep the enumeration entirely. KNN-Shapley. KNN-Shapley is the standard tractable proxy in this family [20, 34]. It instantiates the utility as a 𝑘-nearest-neighbor classifier scored on a held-out validation set. This approach elegantly collapses the combinatorial Shapley sum into a structure that depends solely on how training points rank in distance to a validation query. While this provides a closed-form solution computable in 𝑂 (𝑁 log 𝑁 ) time per validation point, the underlying computation is inherently ill-suited for ZKP encoding. We detail and resolve this challenge in §3.4.

2.2

Zero-Knowledge Proofs

Setting and security properties. A ZKP allows a prover P to convince a verifier V that a statement about a private witness is true without revealing anything beyond the statement’s truth [16]. A ZKP protocol must satisfy three standard properties [2]: completeness (an honest prover always produces a verifying proof), soundness (no malicious prover can convince the verifier of a false statement except with negligible probability), and zero-knowledge (the proof leaks nothing about the private witness beyond what is implied by the statement). Primitives we compose. ZK-Value builds on three standard ZK primitives; for each we state what it does, then the formal guarantee we use, deferring cryptographic details to the cited references. Sumcheck and multilinear extensions. The sumcheck protocol [32, 44] enables a verifier to validate the sum of a polynomial 𝑔 over {0, 1}𝑛 by checking a single evaluation of its multilinear extension at a random point. The protocol requires 𝑛 rounds with a soundness error of at most 𝑛 ·deg(𝑔)/|F| via the Schwartz–Zippel lemma. Since prover complexity scales with the degree of 𝑔, sumcheck cost is governed by the summand’s algebraic structure. ZK-Value employs sumcheck to enforce bucket-count consistency checks (§4). Polynomial commitments. A polynomial commitment scheme [46] (PCS) allows a prover to publish a succinct digest cm(𝑓 ) and subsequently prove the correctness of evaluations 𝑓 (𝑧) without revealing the full polynomial. We instantiate our PCS using a Brakedownstyle construction [17] over the Goldilocks field√(𝑝 = 264 − 232 + 1). This construction incurs an opening cost of 𝑂 ( 𝑀oracle ), a squareroot scaling factor that motivates the optimizations discussed in §5. Lookup arguments. Lookup arguments [11] efficiently verify that a set of committed values exists within a witness table (e.g., verifying bucket counts within [0, 𝑀max ]). Following the LogUp approach [44], we utilize log-derivative identities to reduce multiple lookups to a single sumcheck instance. This amortizes 𝑚 checks against a table 𝑇 into 𝑂 (log |𝑇 | + log 𝑚) constraints, providing a significant efficiency gain over naive encodings.

From interactive to non-interactive. The three primitives above are natively interactive. The Fiat–Shamir transform [10] collapses any such interactive protocol into a single succinct non-interactive argument of knowledge (SNARK) by deriving each verifier challenge from a cryptographic hash of the transcript so far, yielding one static proof any third party can verify offline.

2.3

Locality-Sensitive Hashing

Sensitive hash families. Locality-sensitive hashing (LSH) [7, 15, 33] is a family of randomized hash functions under which similar inputs collide with higher probability than dissimilar ones. A hash family H is (𝑟 1, 𝑟 2, 𝑝 1, 𝑝 2 )-sensitive for a distance 𝑑 (·, ·) if   Pr ℎ(𝑥) = ℎ(𝑦) ≥ 𝑝 1 when 𝑑 (𝑥, 𝑦) ≤ 𝑟 1, ℎ∈ H

  Pr ℎ(𝑥) = ℎ(𝑦) ≤ 𝑝 2 when 𝑑 (𝑥, 𝑦) ≥ 𝑟 2,

ℎ∈ H

with 𝑝 1 > 𝑝 2 . For angular similarity on R𝑑 , the SimHash family [4] is { ℎ𝑟 : 𝑥 ↦→ sign(⟨𝑟, 𝑥⟩) | 𝑟 ∼ N (0, 𝐼𝑑 ) }, with single-bit collision probability 1 − 𝜃 (𝑥, 𝑦)/𝜋 where 𝜃 (𝑥, 𝑦) is the angle between 𝑥 and 𝑦. ZK-Value’s LSH-Shapley protocol (§4.1) instantiates its hash family with SimHash. Bucket structure. A single-bit hash is too coarse, so LSH stacks 𝐾 independent SimHash bits per table into a bucket id (ANDamplification drops the collision probability to (1 − 𝜃 /𝜋) 𝐾 ) and runs 𝐿 independent tables in parallel (OR-amplification). Together (𝐿, 𝐾) control bucket granularity and recall: larger 𝐾 grows the bucket count 𝑀 = 2𝐾 and sharpens discrimination, while larger 𝐿 averages out per-table variance.

3

SYSTEM OVERVIEW

This section specifies the parties, commitments, and protocol phases that realize ZK-Value (Fig. 2), and states the threat model, security guarantees, and application scope under which the construction is analyzed.

3.1

System Model

Parties. A ZK-Value deployment involves four parties. Data providers 𝑉1, . . . , 𝑉𝑚 each hold a private training shard 𝐷𝑖 whose rows occupy Ð positions 𝑆𝑖 ⊆ [𝑁 ] in the aggregated training set 𝐷 = 𝑖 𝐷𝑖 of size 𝑁 ; the index sets {𝑆𝑖 }𝑖 ∈ [𝑚] partition [𝑁 ] and later identify each provider’s rows during selective opening. The buyer 𝐵 holds a private validation set 𝐷 val of size 𝑇 , which encodes the downstream task. The marketplace operator M runs the valuation on behalf of providers and the buyer. External verifiers (regulators, non-participating providers, investigative journalists) participate only through the protocol’s public information and hold no private witnesses or per-provider scores. Commitments. Each provider 𝑉𝑖 submits 𝐷𝑖 to M for valuation and publishes C𝑖 = cm(𝐷𝑖 ), where cm(·) is the cryptographic commitment scheme of §2.2: binding so that the prover cannot later open against a different witness, and hiding so that C𝑖 leaks nothing about 𝐷𝑖 . The buyer does the same with 𝐷 val and Cval = cm(𝐷 val ). The commitments are the public references the rest of the protocol operates against: every claim about the released scores is later checked against them, so the prover cannot quietly compute on a different witness.

Zhaoyu Wang, Pingchuan Ma, Zhantong Xue, Yuguang Zhou, Qixin Zhang, Xiaoqin Zhang, and Shuai Wang

𝑉1

𝑉2

𝑉3

pp

𝑉1

𝑉2

𝑉3

𝐶𝑡𝑟2 𝐶𝑡𝑟3 𝐶𝑡𝑟1 𝐶𝑣𝑎𝑙

{𝐶𝑡𝑟𝑖 }, 𝐶𝑣𝑎𝑙

Buyer Marketplace Buyer Marketplace Operator Operator Auditor

Phase 1 - Setup

Phase 2 - Commit

3.3

Marketplace Operator

𝑉1

𝑉2

𝑉3

LSHShapley Proof System

𝑓𝑖𝑛𝑎𝑙

𝜙h

Buyer , 𝜋𝑣𝑎𝑙𝑢𝑎𝑡𝑒

Auditor

Phase 3 - Valuate

Phase 4 - Open

Figure 2: End-to-end architecture of ZK-Value.

3.4 Four protocol phases. ZK-Value’s valuation pipeline runs in four sequential phases (Figure 2). (1) Setup. Setup(1𝜆 ) → (pp, vk) produces the public parameters and verification key for the polynomial commitment scheme and the Fiat–Shamir-transformed sumcheck backend, once per deployment. (2) Commit. Providers and the buyer submit their datasets to M and publish the corresponding commitments {C𝑖 }𝑖 ∈ [𝑚] and Cval . (3) Valuate. M ingests the private witnesses (the providers’ datasets and the buyer’s validation set), computes the per-training-point Shapley scores {𝜙ℎfinal }ℎ∈ [𝑁 ] , and produces a single non-interactive proof 𝜋valuate certifying that these scores are consistent with every published commitment. (4) Open. Each provider 𝑉𝑖 receives only 𝜙ℎfinal : ℎ ∈ 𝑆𝑖 together with a selective opening bound to C𝑖 , while all other providers’ scores remain hidden. The opening is accompanied by 𝜋valuate , which certifies the correctness of the released scores.

3.2

Threat Model and Security Goals

Threat model. A valuation transaction touches three assets that need protection: the provider shards {𝐷𝑖 }𝑖 ∈ [𝑚] , the buyer’s validation set 𝐷 val , and the integrity of the valutaion scores on those committed inputs. We assume each role of §3.1 may deviate adversarially against these assets. A dishonest provider 𝑉𝑖 may craft shards to inflate their score or attempt to recover peers’ data from the transcript. A curious buyer may use score signals for inference attacks against shards or "free-ride" by abandoning settlement once the value is revealed. A malicious operator M observes the submitted datasets, executes the prover, and collects a transaction fee, giving it a direct stake in the outcome it computes; it may therefore substitute inputs inconsistent with the commitment, bias the valuation function, or leak per-provider scores to unauthorized parties. Security guarantees. ZK-Value addresses these threats by leveraging ZKP primitives and their underlying commitment schemes (§2.2). During the commit phase, input integrity is established via binding (the prover cannot later prove against a dataset different from the one each party committed) and hiding (verifiers learn nothing about the committed datasets from the commitments alone). Subsequently, the proof 𝜋 valuate enforces correctness, guaranteeing that released scores derive strictly from the committed inputs and the agreed valuation function. ZK-Value formally inherits completeness, knowledge soundness, and zero-knowledge from its underlying ZKP primtives (§2.2), with specific realizations detailed in §4.2.

Application Scope

ZK-Value provides an integrity layer for Shapley-based data valuation for classification tasks in cross-organizational marketplaces. It offers providers, buyers, and auditors public, non-interactive verifiability of released scores against committed inputs, scaling to modern ML workloads. Privacy-focused alternatives address orthogonal goals: DP-TKNN-Shapley [48] mitigates membership-inference leakage, while MPC distributes computation to hide private inputs. Neither generates a publicly verifiable certificate of correct execution, so they complement ZK-Value rather than substitute for it (detailed in §7).

The Algorithmic Challenge

The natural baseline. The protocol of §3.1 fixes the parties, commitments, and four phases, but leaves one slot open: which valuation function does M certify in 𝜋 valuate ? A natural choice is KNNShapley [20]. Among the estimators in §2.1, KNN-Shapley is the only one with an 𝑂 (𝑁 log 𝑁 ) closed form per validation point, making it the standard tractable proxy in data-valuation literature [47, 48]. Instantiating ZK-Value with KNN-Shapley is thus the most conservative approach: it ensures that the ZK layer carries the verifiability burden without introducing unstudied valuation trade-offs. Why the baseline fails ZK encoding. Encoding valuation inside 𝜋 valuate requires certifying every operation against committed inputs. For KNN-Shapley, this imposes two structural costs scaling as 𝑁 · 𝑇 : (1) computing the full distance matrix, which requires an inner-product commitment per training-validation pair, and (2) ranking these distances, which demands costly non-arithmetic constraints for each validation point. While this 𝑁 · 𝑇 complexity is workable in plaintext, ZK certification overhead makes it the dominant proof bottleneck. Tractable ZK valuation therefore requires an algorithm and proof system that decouple from this 𝑁 · 𝑇 scaling (Requirement P-4, §1). We develop both pieces in §4, with further optimizations in §5.

4

METHOD

This section introduces the valuation function that ZK-Value certifies, LSH-Shapley (§4.1), together with ZK-LSH-Shapley (§4.2), the specialized ZK protocol that produces this certificate.

4.1

LSH-Shapley

LSH-Shapley replaces KNN-Shapley’s pairwise-distance signal with bucket co-membership under a locality-sensitive hash. We state the utility in §4.1.1 and derive its closed-form Shapley value in §4.1.2 (Theorem 4.1). 4.1.1 Bucket-Based Nearest Neighbor Utility. Before stating the utility, we fix the hash family and the bucket-count primitives that its closed form (§4.1.2) is built on. Hash family. We instantiate the LSH primitive of §2.3 with SimHash. Each hash bit is the sign of a Gaussian inner product sign⟨𝑟, 𝑥⟩ with 𝑟 ∼ N (0, 𝐼𝑑 ), so its underlying metric is angular similarity, the appropriate notion for ℓ2 -normalized neural embeddings. Stacking 𝐾 such bits gives a per-table bucket id 𝐵 ℓ (𝑥) =

ZK-Value : A Practical Zero-Knowledge System for Verifiable Data Valuation

𝜅 ℓ (𝑥) ∈ {0, 1}𝐾 with expected occupancy 𝑁 /2𝐾 , and we run 𝐿 independent tables to drive estimator variance down. Among LSH families, SimHash also has the lowest circuit degree under our ZK back-end: the inner product ⟨𝑟, 𝑥⟩ is linear in 𝑥, and sign extraction reduces to a single lookup. Alternatives such as 𝑝-stable hashes [7] (floor gates) and MinHash [3] (set-encoding gates) raise the per-bit circuit degree substantially. Bucket and counts. The bucket of validation point 𝑥𝑡te in table ℓ is the set of training points sharing its bucket id, Bℓ𝑡 := { 𝑗 ∈ [𝑁 ] : 𝐵 ℓ (𝑥 tr𝑗 ) = 𝐵 ℓ (𝑥𝑡te ) }. We summarize each (ℓ, 𝑡) pair by two counting queries on the committed data: 𝑀 (ℓ, 𝑡) := |Bℓ𝑡 | (bucket size) and 𝑀 + (ℓ, 𝑡) := |{ 𝑗 ∈ Bℓ𝑡 : 𝑦 𝑗 = 𝑦𝑡 }| (same-label count). Both are simple histograms over bucket ids, which is what eventually makes the closed form of §4.1.2 ZK-friendly. Utility function. For a coalition 𝑆 ⊆ [𝑁 ], validation point 𝑡, and table ℓ, we define the LSH-Shapley utility as the fraction of 𝑆’s bucket-mates whose label agrees with 𝑦𝑡 :  0     𝑡 𝑢 ℓ (𝑆) := { 𝑗 ∈ 𝑆 ∩ Bℓ𝑡 : 𝑦 𝑗 = 𝑦𝑡 }    𝑆 ∩ Bℓ𝑡 

|𝑆 ∩ Bℓ𝑡 | = 0, |𝑆 ∩ Bℓ𝑡 | > 0.

(1)

This form is motivated by three observations. (i) Non-colliders (𝑗 ∉ Bℓ𝑡 ) are Shapley dummies, so the 𝑁 -player game restricts to an 𝑀-player subgame on the bucket. (ii) If Bℓ𝑡 equals a 𝐾-nearestneighbor set, 𝑢 ℓ𝑡 (𝑆) reduces to the fraction-of-correct-votes utility of [20], preserving KNN-Shapley semantics. (iii) For any coalition 𝑆, the utility 𝑢 ℓ𝑡 (𝑆) depends on the data only through two integers, |𝑆 ∩ Bℓ𝑡 | and |{ 𝑗 ∈ 𝑆 ∩ Bℓ𝑡 : 𝑦 𝑗 = 𝑦𝑡 }|. This dependence on aggregate bucket counts yields the closed-form Shapley value of Theorem 4.1, expressed solely through 𝑀 (ℓ, 𝑡) and 𝑀 + (ℓ, 𝑡), letting LSH-Shapley avoid the sorting and pairwise-distance proofs that KNN-Shapley would otherwise require in ZKP. 4.1.2 Closed-Form Shapley Values. With the utility 𝑢 ℓ𝑡 fixed by (1), we now derive its closed-form Shapley value. This closed form is the structural enabler of ZK-Value: it reduces the exponential coalition sum to a constant-time expression in two histogram counts, and it determines the algebraic shape of the ZKP protocol of §4.2 (the protocol design is the paper’s main contribution). For brevity, let Í 𝐻𝑀 := 𝑀 𝑗=1 1/𝑗 denote the 𝑀-th harmonic number, and let 𝑀 and 𝑀 + stand for the bucket counts 𝑀 (ℓ, 𝑡) and 𝑀 + (ℓ, 𝑡) when no ambiguity arises. With this notation in place, the Shapley value of 𝑢 ℓ𝑡 admits the following closed form. Theorem 4.1 (LSH-Shapley closed form). Let 𝜙 ± (ℓ, 𝑖, 𝑡) denote the Shapley value of training point 𝑖 under 𝑢 ℓ𝑡 , where the + branch applies when the labels match (𝑦𝑖 = 𝑦𝑡 ) and the − branch applies when they disagree. The value depends on the data only through (𝑀, 𝑀 +, 𝐻𝑀 ). For non-colliders (𝑖 ∉ Bℓ𝑡 ), 𝜙 ± = 0; for singleton buckets (𝑀 = 1), 𝜙 ± = 1[𝑦𝑖 = 𝑦𝑡 ]; for 𝑖 ∈ Bℓ𝑡 with 𝑀 ≥ 2,  𝐻𝑀 (𝑀 + − 1)(𝐻𝑀 − 1)   −    𝑀 𝑀 (𝑀 − 1) 𝜙± =  𝑀 + (𝐻𝑀 − 1)    − 𝑀 (𝑀 − 1) 

𝑦𝑖 = 𝑦𝑡 , (2) 𝑦𝑖 ≠ 𝑦𝑡 .

The proof, the verification of all four Shapley axioms, and the sign / monotonicity properties are deferred to Appendix B.3.

Algorithm 1 LSH-Shapley Require: Training set {(𝑥 tr𝑗 , 𝑦 𝑗 )}𝑁𝑗=1 , validation set {(𝑥𝑡te, 𝑦𝑡 )}𝑇𝑡=1 , hash tables 𝐿, hash depth 𝐾, public Gaussian projection vectors 𝑟 ℓ(𝑘 ) ∼ N (0, 𝐼𝑑 ) for ℓ ∈ [𝐿], 𝑘 ∈ [𝐾]. 𝑁 . Ensure: Per-sample scores {sv_avg𝑖 }𝑖=1 1: Phase 1 (Hash). For each ℓ ∈ [𝐿] and each input 𝑥 ∈ {𝑥 tr 𝑗 }𝑗 ∪
(𝑘 ) te {𝑥𝑡 }𝑡 , compute the bucket id 𝐵 ℓ (𝑥) ← sign⟨𝑟 ℓ , 𝑥⟩ 𝑘<𝐾 . 2: Phase 2 (Bucket statistics). For each (ℓ, 𝑡), form Bℓ𝑡 = { 𝑗 : 𝐵 ℓ (𝑥 tr𝑗 ) = 𝐵 ℓ (𝑥𝑡te )} and record the counts 𝑀 (ℓ, 𝑡) and 𝑀 + (ℓ, 𝑡). 3: Phase 3 (Per-bucket weight). For each (ℓ, 𝑡, 𝑖), evaluate 𝑁 . 𝜙 ± (ℓ, 𝑖, 𝑡) via (2) using a precomputed harmonic table {𝐻𝑚 }𝑚=1 4: Phase 4 (Aggregate). For each 𝑖 ∈ [𝑁 ], set sv_avg𝑖 ← (𝐿 · Í 𝑇 ) −1 ℓ,𝑡 𝜙 ± (ℓ, 𝑖, 𝑡). 𝑁 . 5: return {sv_avg𝑖 }𝑖=1

Released score per training point. Combining Theorem 4.1 with the linearity of the Shapley value in the utility, the score ZKValue releases for training point 𝑖 is the average of the per-table, per-validation contributions, 1 ∑︁ ± sv_avg𝑖 := 𝜙 (ℓ, 𝑖, 𝑡), 𝐿 · 𝑇 ℓ,𝑡 and we also work with the unnormalized form sv_sum𝑖 := 𝐿 · 𝑇 · sv_avg𝑖 , which is what the table-aggregation sumcheck of §4.2 certifies in the verified circuit. Why averaging, not OR-amplification. ZK-Value aggregates the 𝐿 tables by mean rather than the OR-amplification rule of standard LSH nearest-neighbor search (§2.3). Statistically, the per-table games are i.i.d. random partitions, so the table-mean is unbiased for its expectation over the random hash projections (concentration rate below). Algorithmically, Shapley linearity in the utility decomposes the table-mean utility’s Shapley value into 𝐿 independent per-table evaluations of Theorem 4.1, with the released score their arithmetic mean. OR-amplification breaks this: it combines per-table memberships by a non-linear Boolean OR rather than a sum, so Shapley linearity no longer factors across tables and the per-table closed form does not transfer. This Boolean OR is also more expensive to certify in the ZK backend than an arithmetic mean. Algorithm. Algorithm 1 presents LSH-Shapley as four phases that map one-for-one onto the verification obligations of §4.2.2: Phase 1 hashes every training and validation point, Phase 2 queries the bucket counts (𝑀, 𝑀 + ) off those hashes, Phase 3 evaluates 𝜙 ± via (2) against a precomputed harmonic table, and Phase 4 aggregates per-sample scores across the 𝐿 · 𝑇 table-validation pairs. Complexity. A single evaluation of (2) on the inputs (𝑀, 𝑀 +, 𝐻𝑀 ) runs in 𝑂 (1) time. There are 𝐿 ·𝑇 · 𝑁 triples (ℓ, 𝑖, 𝑡) in total, so computing all of {𝜙 ± (ℓ, 𝑖, 𝑡)}, together with the bucket histograms they depend on, costs 𝑂 (𝐿 ·𝑇 · 𝑁 ) overall. The feature dimension 𝑑 enters only once, through the hashing step (Phase 1 of Algorithm 1). Convergence. Theorem 4.1 is exact for each per-table game 𝑢 ℓ𝑡 , so the only randomness in sv_avg𝑖 is over the hash projections 𝑟 ℓ(𝑘 ) . We therefore view sv_avg𝑖 as a Monte Carlo estimator of its expectation E𝑟 [sv_avg𝑖 ] over the random hash family. Since the 𝐿 tables are i.i.d. random partitions, this estimator is unbiased and

Zhaoyu Wang, Pingchuan Ma, Zhantong Xue, Yuguang Zhou, Qixin Zhang, Xiaoqin Zhang, and Shuai Wang

√ concentrates at rate 𝑂 (1/ 𝐿) around its expectation; the formal statement and the rank-stability bound that drives our parameter selection are in Theorem 1 of Appendix B.4.

Table 2: Committed-oracle inventory for ZK-LSH-Shapley, in dataflow order. Each plaintext object of §4.1 is mapped to the committed oracle and the protocol step that consumes it.

4.2

Plaintext object

Committed oracle

Verified by

Features (train / test) Hash bits Per-bucket histogram Per-class histograms Label indicators Per-sample lookups Shapley weight Aggregates Harmonic value

𝑥f f tr , 𝑥 te sign, abs_dp, dp cnt cnt_c_tr, cnt_c_te 𝑦ind , 𝑦test_ind 𝑚, b𝑚 b𝑐 , b 𝑡𝑐 𝑊 , 𝑒, 𝐷 inv , wt_num sv_sum, sv_avg 𝐻𝑀 (not committed)

Hash-binding Hash-binding Histogram Histogram Histogram Lookup Weight Weight Reconstruction

ZKP Protocol for LSH-Shapley

We now describe ZK-LSH-Shapley, the ZKP protocol that certifies Theorem 4.1’s closed-form score on committed training and validation inputs. 4.2.1 Witness Design: Why Bucket Histograms. A key design choice in ZK-LSH-Shapley is the witness granularity. By Theorem 4.1, 𝜙 ± depends on an (ℓ, 𝑖, 𝑡) triple solely through the bucket counts (𝑀 (ℓ, 𝑡), 𝑀 + (ℓ, 𝑡)) and the harmonic value 𝐻𝑀 . The witness must deliver these efficiently. We compare a natural per-pair baseline against ZK-LSH-Shapley’s bucket-level encoding. Naive encoding (naive-ZK-LSH-Shapley). A direct per-pair approach commits a binary tensor member(ℓ, 𝑡, 𝑖) = 1[𝐵 ℓ (𝑥𝑖tr ) = 𝐵 ℓ (𝑥𝑡te )] indicating bucket co-membership. This requires full-tensor consistency sumchecks to recover 𝑀 and 𝑀 + . This incurs two avoidable costs. First, witness size scales with the validation-set size 𝑇 , unnecessarily tracking per-pair interactions when only bucket-level counts are needed. Second, verifying each bit forces sumchecks to re-derive bucket IDs from 𝐾 sign bits, pushing the per-round polynomial degree to 𝐾 + 𝑂 (1). Consequently, both prover work and proof size scale poorly as O (𝑇 · 𝐿 · 𝑁 ). Bucket histograms. To avoid overcommitting, ZK-LSH-Shapley directly commits bucket statistics. The base histogram cnt[ℓ, 𝑏] and its per-class refinements cnt_c_tr[ℓ, 𝑏, 𝑐] and cnt_c_te[ℓ, 𝑏, 𝑐] count points hashing to each bucket. Spanning O (𝐿 · 𝑀 · 𝐶) entries, this bucket-side witness drops the 𝑇 axis entirely. To recover per-sample statistics, we define three materialized lookup oracles indexing the pre-resolved count at training point 𝑖’s bucket:   𝑚[ℓ, b 𝑖] := cnt ℓ, 𝐵 ℓ (𝑥𝑖tr ) ,   𝑚 b𝑐 [ℓ, 𝑖] := cnt_c_tr ℓ, 𝐵 ℓ (𝑥𝑖tr ), 𝑦𝑖 ,   b 𝑡𝑐 [ℓ, 𝑖] := cnt_c_te ℓ, 𝐵 ℓ (𝑥𝑖tr ), 𝑦𝑖 . The reason for committing 𝑚, b𝑚 b𝑐 , b 𝑡𝑐 separately rather than letting the weight sumcheck look up cnt[ℓ, 𝐵 ℓ (𝑥𝑖tr )] on the fly is to keep the per-round polynomial degree low. An on-the-fly lookup would entangle the histogram data with the bucket-routing bits, drastically increasing the computational overhead of the proof. Pre-computing these arrays allows the main proof to query them at minimal cost, requiring only a small, one-time auxiliary check to ensure they correctly match the base histograms. The harmonic value 𝐻𝑀 also enters the closed form, but it is a deterministic public function of 𝑀; once the histograms establish 𝑀, 𝐻𝑀 is implicitly verified without requiring an extra step. Commitment size. The full protocol commits five families of oracles. The bucket-side family (cnt, cnt_c_tr, cnt_c_te and the persample lookups 𝑚, b𝑚 b𝑐 , b 𝑡𝑐 , all introduced above) takes 𝑂 (𝐿 · 𝑁 + 𝐿 · 𝑀 · 𝐶), independent of 𝑇 . The hashing-side family (the feature MLEs 𝑥f f tr , 𝑥 te together with the sign and dot-product oracles that bind the LSH evaluation to those features) adds 𝑇 · 𝑑 for the validation features (where 𝑑 denotes the feature dimension). The per-class label indicators 𝑦ind, 𝑦test_ind that resolve the same-label test inside the closed form add 𝐶 · 𝑇 . The weight-identity advice

(𝑊 , 𝑒, 𝐷 inv, wt_num) that turns the closed-form division and edgecase split into low-degree polynomial identities, together with the aggregate oracles sv_sum, sv_avg, contribute 𝑂 (𝐿 · 𝑁 ). Table 2 lists every committed oracle in dataflow order, paired with the protocol step that consumes it. 4.2.2 Protocol Construction. Given the witnesses of §4.2.1, the verifier discharges four obligations Algorithm 1 imposes (honest hashing, histogram faithfulness, closed-form weight, aggregation) plus the marketplace requirement (commit-binding to providers and disclosure to buyer). These factor into a hashing module upstream and four chained verification layers downstream, each binding the next adjacent commitment level via a small group of sumcheck modules, summarized at a glance in Algorithm 2. Hashing module. The hashing module sits upstream of the four layers and discharges the honest-hashing obligation by tying the sign and dot-product oracles to the committed feature MLEs. We utilize existing sumcheck protocols for sign, Boolean, and absolute dot-product operations [53], which verify that sign⟨𝑟 ℓ(𝑘 ) , 𝑥⟩ is Boolean and that the absolute dot products are correctly computed. This architecture successfully isolates the feature dimension to the input layer; downstream sumchecks process only verified bucket assignments, never raw features. Layer 1: histogram consistency. With the bucket assignments verified upstream, Layer 1 binds the committed histograms to those assignments, discharging the histogram-faithfulness obligation (Phase 2 of Algorithm 1). The training-histogram consistency sumcheck binds cnt via the identity ∑︁
eq𝐾 𝐵 ℓ (𝑥𝑖tr ), 𝑏 = cnt[ℓ, 𝑏]. (ℓ,𝑖 ) ∈ {0,1} log 𝐿+log 𝑁

Two analogous sumchecks bind cnt_c_tr and cnt_c_te on the perclass refinements (the per-class training-histogram consistency sumcheck and the per-class validation-histogram consistency sumcheck); per-module target sums and round-degrees are tabulated in Appendix B.2. Round-degrees are constant in 𝐾 (𝐾 + 1 to 𝐾 + 2); this layer dominates prover time. Layer 2: lookup consistency. With the histograms now bound to the bucket assignments, Layer 2 binds the per-sample materialized lookups to those histograms, completing the second half of Phase 2’s faithfulness obligation. The bucket-size lookup sumcheck

ZK-Value : A Practical Zero-Knowledge System for Verifiable Data Valuation

Algorithm 2 ZK-LSH-Shapley (high-level). The full per-module protocol is Algorithm 4 in Appendix B.1.

binds 𝑚 b via 𝑚[ℓ, b 𝑖]

= cnt ℓ, 𝐵 ℓ (𝑥𝑖tr ) , 



Public input: public parameters pp, projection vectors {𝑟 ℓ(𝑘 ) }, per-provider data commitments {cm(𝐷𝑖 )}, validation-set commitment cm(𝐷 val ), hash parameters (𝐿, 𝐾). Witness: per-provider data shards {𝐷𝑖 }, validation set 𝐷 val ; bucket/weight/label oracles (see Table 2). Output: proof 𝜋 certifying sv_avg = LSH-Shapley(𝐷, 𝐷 val ).

verified through an eq𝐾 -based identity sumcheck on (𝐿, 𝑁 ) paired with a degree-3 squared-count auxiliary on (𝐿, 𝑀). Two analogous lookup sumchecks (the same-class lookup and the validation-class lookup, each main and squared-count auxiliary) bind 𝑚 b𝑐 and b 𝑡𝑐 to their respective histograms; full identities in Appendix B.2. Layer 3: weight identity and aggregation. With per-sample lookups now bound to the histograms, Layer 3 plugs them into the closed form: it verifies that the committed weight 𝑊 satisfies (2) on every training point and that the published sv_avg is the correct aggregate (Phases 3 and 4 of Algorithm 1). The edge-case weight identity binds 𝑊 on the 𝑀 ∈ {0, 1} region: ∑︁  𝑊 = 𝑚[ℓ, b 𝑖] · 𝑦ind,𝑐 [𝑖] · b 𝑡𝑐 [ℓ, 𝑖] on 𝑒 = 1.

1: Commit witnesses. Prover commits to feature MLEs, hash-

ing/weight oracles, bucket histograms, label indicators, and aggregates (plus PCA witnesses if 𝑑 > PCS budget). 2: Hash binding. Run the hash-binding sumchecks that tie sign and dot-product oracles to the committed feature MLEs; if PCA is enabled, additionally run the ZK-PCA sumchecks. 3: Histogram and lookup consistency. Run sumchecks binding bucket counts (cnt, cnt_c_tr, cnt_c_te) to the bucketassignments and lookups (𝑚, b𝑚 b𝑐 , b 𝑡𝑐 ) to those histograms. 4: Weight and aggregation. Run the weight-identity sumchecks binding 𝑊 to the closed form (2) on both the edge and interior cases, then the table-aggregation and normalization sumchecks producing sv_sum and sv_avg. 5: Reconstruction and opening. Run the input-side and outputside reconstruction sumchecks binding 𝑥f tr and sv_avg to perprovider commitments, then send PCS openings at every sumcheck challenge point.

𝑐

The interior weight identity (𝑀 ≥ 2) clears the denominator 𝑀 (𝑀 − 1) via a committed inverse 𝐷 inv and a numerator witness wt_num; auxiliary checks discharge the boolean of the edge flag 𝑒 and the denominator-inverse structural identities. The table-aggregation sumcheck collapses 𝑊 across 𝐿 tables into sv_sum, and a normalization sumcheck [53] divides by 𝐿 · 𝑇 to obtain sv_avg. Layer 4: input/output reconstruction. Layers 1–3 produce a single committed sv_avg from honest LSH-Shapley evaluation, but in the marketplace setting that is not enough: the protocol must additionally bind sv_avg to the providers who actually contributed and let each buyer privately verify only their own scores. Layer 4 closes the binding chain on both sides, tying sv_avg back, on the input side, to per-provider data commitments cm(𝐷𝑖 ), and forward, on the output side, to per-provider score-slice commitments cm(Φ𝑖 ). Two structurally identical reconstruction sumchecks discharge the two halves. For each provider 𝑖 over the disjoint contiguous slice 𝑆𝑖 with ℎ = (ℎ low, ℎ high ), the output-side reconstruction proves ž sv_avg(ℎ) =

𝑚 ∑︁

eq(ℎ high, bin(𝑖)) · Φ𝑖 (ℎ low ),

𝑖=1

reducing to one PCS opening of sv_avg at 𝜏 plus 𝑚 openings of Φ𝑖 at 𝜏low ; the input-side reconstruction is symmetric, binding 𝑥f tr to {cm(𝐷𝑖 )}. Together the two reconstructions yield the binding chain 𝐷𝑖 → cm(𝐷𝑖 ) → cm(f 𝑥 tr ) → · · · → cm(sv_avg) → cm(Φ𝑖 ) → sv_avg |𝑆 . 𝑖

Each provider then runs three local checks (input binding, output binding, transcript correctness) on the per-provider slice they verify, deferred to Appendix B.7. Optional layer for high-dimensional inputs. When the raw feature dimension is too large to commit directly under the polynomialcommitment scheme, we adopt a verifiable dimensionality-reduction (PCA) sumcheck from prior work [53] as a preprocessing step that projects the features into a lower-dimensional space before hashing. The construction commits the necessary auxiliary witnesses and discharges the projection identity through additional sumchecks; we use it as a black box and defer details to Appendix B.1.

4.2.3 Security and Complexity. This subsection states the security guarantees and prover-cost profile of ZK-LSH-Shapley, with formal proofs and per-module breakdowns deferred to Appendix B.8. Security. ZK-LSH-Shapley is a non-interactive zero-knowledge argument of knowledge for the closed-form score relation: it satisfies completeness (an honest prover always convinces the verifier), knowledge soundness (the verifier accepts only when the prover knows a witness consistent with the closed-form score formula (2)), and zero-knowledge (the proof reveals nothing beyond the published sv_avg). Complexity. The hashing module incurs a one-shot input-binding cost of 𝑂 (𝐿 · 𝐾 · (𝑁 + 𝑇 ) · 𝑑) and is compute-dominant due to signcheck overhead, with 𝑑 and 𝑇 entering only here and dropping out of all downstream layers. Subsequent Shapley layers are led by histogram-consistency sumchecks at 𝑂 (𝐿 · 𝑁 · poly(𝐾)), with lookup, weight, and aggregation costs lower order; Layers 2 and 3 instantiate one sumcheck instance per class, contributing a multiplicative 𝐶 factor on those layers’ transcript. Proof size therefore splits into a transcript component linear in 𝐶 on Layers 2 and 3, plus a PCS-opening component governed by the total length of the 𝐶-indexed tensor and batched across classes (§5.1).

5

PROOF-SYSTEM OPTIMIZATIONS

The ZK-LSH-Shapley protocol of §4 is correct but unoptimized along two axes: proof size and prover time. This section presents two optimizations that target them: super-oracle batching (§5.1) and sparsity-aware sumchecks (§5.2).

Zhaoyu Wang, Pingchuan Ma, Zhantong Xue, Yuguang Zhou, Qixin Zhang, Xiaoqin Zhang, and Shuai Wang

5.1

Super-Oracle Batching for Proof Size

The opening-count bottleneck. Under our PCS (§2.2), if 𝑄 denotes the number of PCS openings and 𝑐 fix the per-opening fixedoverhead bytes (commitment header, authentication path, transcript material), proof size scales as √
|𝜋 PCS | = 𝑄 · 𝑐 fix + 𝑀 , so the opening count 𝑄 is the dominant lever, and each opening also costs the prover one PCS open phase. The witnesses committed in §4.2.1 are indexed tensors, each queried by the sumcheck that consumes it (its parent sumcheck) at one or more evaluation points. Most parents query a single point and contribute a single opening; the cost-bearing exceptions are tensors whose parent issues multiple queries at one shared upstream point, differing only along a single index axis. We call such an indexed slice group a family, and three of them dominate 𝑄 in ZK-LSH-Shapley: • the sign-bit family sign[ℓ, 𝑘, ·], driven by the dot-product sign sumchecks of §4.2.2, which probe 𝐾 points differing only in the hash-function index 𝑘 on each of the training-side and test-side preambles; • the histogram family cnt_c_tr[ℓ, 𝑏, 𝑐], driven by the per-class training-histogram sumcheck together with the bucket-size lookup, which together probe 2𝐶 + 2 points differing only in the class coordinate 𝑐; • the lookup family {𝑚 b𝑐 [ℓ, 𝑖, 𝑐], b 𝑡𝑐 [ℓ, 𝑖, 𝑐]}, driven by the sameclass and validation-class lookup sumchecks, which each probe 𝐶 points differing only in 𝑐. In every case the queries share a common upstream point 𝑥 ∗ ∈ F𝑛EF (the random suffix of verifier challenges already fixed by the parent sumcheck) and differ only in the index variable that one prepends to 𝑥 ∗ . This is exactly the structure batching exploits. Construction. Let 𝑓0, 𝑓1, . . . , 𝑓𝑄 −1 : {0, 1}𝑛 → F be 𝑄 multilinear sub-oracles, each obtained by fixing one index axis of a parent tensor (e.g., 𝑓𝑐 (ℓ, 𝑏) := cnt_c_tr[ℓ, 𝑏, 𝑐] for 𝑐 ∈ {0, . . . , 𝐶 − 1}). Suppose the upstream sumcheck has fixed a common evaluation point 𝑥 ★ ∈ F𝑛EF and the verifier needs the 𝑄 values 𝑓0 (𝑥 ★), . . . , 𝑓𝑄 −1 (𝑥 ★) to close its claim; without batching, each 𝑓 𝑗 carries its own PCS commitment √ and opening at 𝑥 ★, costing 𝑄 · (𝑐 fix + 𝑀 ′ ) proof bytes and 𝑄 separate open-phase invocations on the prover. We collapse the 𝑄 commitments to one by padding 𝑄 to a power of two and reshaping the family {𝑓 𝑗 } into a single multilinear extension on {0, 1}log 𝑄+𝑛 that treats the index 𝑗 as an extra variable: 𝐹 ( 𝑗, 𝑥) := 𝑓 𝑗 (𝑥),

log 𝑄+𝑛

extended multilinearly to ( 𝑗, 𝑥) ∈ FEF

.

We call 𝐹 the super-oracle of the family {𝑓 𝑗 }. The prover commits 𝐹 once. To recover the 𝑄 values {𝑓 𝑗 (𝑥 ★)}, the verifier samples one log 𝑄 Fiat–Shamir challenge 𝑟 ∈ FEF , asks for the single PCS opening 𝐹 (𝑟, 𝑥 ★), and accepts the prover-supplied values 𝑣 0, . . . , 𝑣𝑄 −1 iff ∑︁ 𝐹 (𝑟, 𝑥 ★) = eq(𝑟, 𝑗) · 𝑣 𝑗 . (3) 𝑗 ∈ {0,1} log 𝑄

By Schwartz–Zippel over FEF , agreement at random 𝑟 binds 𝑣 𝑗 = 𝑓 𝑗 (𝑥 ★) for every 𝑗 except with probability at most log 𝑄/|FEF |. The verifier then plugs the recovered {𝑣 𝑗 } into the parent sumcheck identity exactly as in the unbatched protocol; nothing downstream changes.

Application to the three families. The sign-bit, histogram, and lookup families introduced above all satisfy the setup of (3): each is a slice of its parent tensor along a single integer-encoded axis (𝑘 for sign; 𝑐 for 𝑚 b𝑐 , b 𝑡𝑐 , and cnt_c_tr), and within each family the 𝑄 queries share a common upstream 𝑥 ★ already fixed by the parent sumcheck. The same construction therefore applies verbatim to all three. We pack them into three separate super-oracles rather than one: although the template is shared, the parent tensors have different shapes and queries in different families land at different 𝑥 ★, so merging the commitments would leave the post-batching opening count unchanged. Savings. For one super-oracle of 𝑄 sub-oracles, the 𝑄 separate openings of the unbatched template collapse to one in the PCSopening component of the proof: √
before: 𝑄 · 𝑐 fix + 𝑀 ′

−→

√︁ after: 𝑐 fix + 𝑄 · 𝑀 ′,

and the prover runs one open phase instead of 𝑄, cutting prover time in proportion. The savings apply to PCS-opening bytes only; the parent sumchecks that consume the sub-oracles are unaffected, so any sumcheck transcript whose instance count scales with the batched index (e.g., per-class lookup and weight-identity sumchecks over the class axis 𝑐) retains its linear-in-𝑄 transcript contribution. Batching is profitable only when 𝑄 is large enough to amortize √ 𝑐 fix and when 𝑀 ′ exceeds the per-opening authentication-path bytes (see §2.2); families that fall short of either threshold are left unbatched. We report the per-family breakdown in §6.4. Soundness. Replacing 𝑄 separate openings with a single packed opening preserves soundness: the random index challenge 𝑟 binds the prover to consistent sub-oracle values via (3), and the verifier’s downstream check is unchanged. Appendix B.6 gives the full proof.

5.2

Sparsity-Aware Sumchecks for Prover Time

The dense-grid bottleneck. The complexity analysis of §4.2.3 identifies the three histogram sumchecks of Layer 1 (traininghistogram, per-class training-histogram, per-class validation-histogram) as the prover-time bottleneck. Each runs 𝐾 rounds, and in every round the prover walks the entire bucket grid of size 𝑀 = 2𝐾 to assemble its univariate round message: roughly 𝐿·𝑀 field multiplications per round per sumcheck, repeated across all three sumchecks. The optimization below brings this cost down to a function of the data size rather than of the bucket-grid size. Why most of that work is wasted. Every multilinear extension committed in a sumcheck lives on a power-of-two cube of size 2𝑛 , and the 𝐾-round histogram sumchecks of §4.2.2 are no exception. What is special here is how little of that cube the data actually occupies: LSH places the 𝑁 training points into at most 𝑁 distinct cells of cnt[ℓ, 𝑏] out of 𝑀 = 2𝐾 , and class-stratified factors (cnt_c_tr[ℓ, 𝑏, 𝑐], cnt_c_te[ℓ, 𝑏], and the per-class label and lookup slices) inherit the same bucket sparsity plus a further partition across 𝐶 classes. The remaining cells are zero by construction and contribute nothing to any round message, yet the dense walk multiplies and accumulates them anyway. The same observation underpins prior sparsity-aware sumcheck designs for ZK machine learning [26, 37], where the zeros come from rounding arbitrary matrix dimensions up to powers of two; in our setting the zeros

ZK-Value : A Practical Zero-Knowledge System for Verifiable Data Valuation

come from hashing and class slicing instead, but the prover-side mechanism is the same. Sparse-aware sumcheck path. We expose the skip in the prover by attaching a support mask supp(𝑓 ) ⊆ {0, 1}log 𝑀 to each sparse factor 𝑓 ∈ {cnt_c_tr, cnt_c_te, per-class label and lookup slices}: the index set of cells the prover knows are nonzero. To assemble round 𝑖’s message, the prover (i) intersects the masks of the factors that appear in each product term, (ii) iterates the round message’s outer loop only over that intersection, and (iii) folds each mask in place once the round advances, keeping it one variable ahead of the partially-folded table. By construction, the round message emitted on the sparse path equals the dense-path message bit for bit, so verifier-side soundness transfers verbatim. A factor whose postfold density exceeds a fixed crossover threshold (set so that mask bookkeeping no longer pays for the zeros it skips) drops back to the dense path for its remaining rounds; on workloads with high bucket occupancy 𝜆 = 𝑁 /𝑀, cnt_c_tr itself crosses early and the savings come only from the sparser per-class factors. Full pseudocode and the support-superset invariant are in Appendix C. Savings. Unlike super-oracle batching, whose savings depend only on 𝑄, the sparsity-aware path has no fixed complexity: every multiplication it skips corresponds to a zero cell of the underlying tensor, and the fraction of zero cells is set by the workload (bucket occupancy 𝜆 = 𝑁 /𝑀, class count 𝐶, and how unevenly LSH distributes points across buckets and classes), not by the protocol. On workloads where the histogram itself stays dense, the gain comes only from the sparser per-class slices; on workloads with low bucket occupancy, the histogram contributes too. We report the per-dataset breakdown in §6.4. Soundness. The cells the prover skips are exactly the zero cells of the underlying tensor, and each such cell contributes 0 to the roundmessage sum; the message the prover emits on the sparse path is therefore identical to the dense-path message by direct equality. Soundness inherits from the unmodified ZK-LSH-Shapley protocol. Appendix C gives the full argument.

by nearest-cosine to 𝐶 random unit anchors, so we can vary one axis at a time. Pre-processing and synthetic-data generation details are given in Appendix A. Baselines. We compare ZK-Value against six baselines, organized in two groups. Valuation-quality baselines: (1) KNN-Shapley [20], a closed-form KNN-based Shapley estimator with O (𝑁 log 𝑁 ) pervalidation cost; (2) G-Shapley [14], the gradient-based Shapley estimator that ZK-DV adopts as its valuation primitive; (3) Data Shapley [14], a truncated Monte-Carlo Shapley estimator over a fixed predictor; and (4) Data Banzhaf [47], the Banzhaf-value variant. ZK baselines: (5) KNN-Shapley-ZK, a direct SNARK compilation of KNN-Shapley through the same sumcheck/PCS pipeline as ZKValue; and (6) naive-ZK-LSH-Shapley, the per-pair tensor encoding from §4.2. We also attempted to include SP1 [25], a state-of-the-art general-purpose zkVM, but it failed to complete a single proof on the smallest dataset in the benchmark; we report the run alongside the ZK-DV comparison in §6.2. Tasks and Metrics. Following prior work [14, 48], we evaluate two standard data-valuation tasks: mislabeled data detection and noisy data detection. Of each dataset, we hold out 10% as the validation cohort and train on the remaining 90%, of which a further 10% is corrupted (label flip for mislabel, feature perturbation for noisy); a faithful estimator should rank these corrupted points lowest. We report two data-valuation metrics: AUROC for valuation quality, and valuation runtime for throughput. For ZK-Value and the two ZK baselines, we additionally report proving time, verification time, and proof size measured on the same hardware; OOM marks runs that exceeded the host memory budget. Every reported number is the median of three frozen-seed runs. Implementation. ZK-Value is implemented in Rust (36K LOC) over the Goldilocks base field (𝑝 = 264 − 232 + 1) with a Brakedown polynomial commitment scheme [17]. All experiments run on a single 64-core Intel-class server with 256 GB RAM and Ubuntu Linux.

6

6.2

EVALUATION

We aim to answer three research questions (RQs) about ZK-Value. • RQ1: Capability. Does ZK-Value deliver verifiable Shapley attributions on real marketplace data while preserving the underlying valuation quality? • RQ2: Scalability. How does each cost dimension scale as the workload is pushed to modern ML scale along 𝑁 , 𝑑, 𝐶, and 𝑇 ? • RQ3: Ablation. How much does each component of the construction contribute to the end-to-end cost?

6.1

Experimental Setup

Datasets. We conduct our experiments on the 12-dataset benchmark established in prior data-valuation work [30, 48], which covers the two data regimes a production marketplace typically trades in: 10 OpenML tabular benchmarks covering raw feature dimensions 𝑑 ∈ [5, 170], and 2 ViT embeddings on mnist and cifar10 at 𝑑 = 768, standing in for marketplaces that trade pre-processed representations of rich media. The scalability experiments in §6.3 and the ablation in §6.4 switch to synthetic Gaussian workloads with features drawn i.i.d. from N (0, 𝐼𝑑 ) and class labels assigned

RQ1: End-to-End Capability on Real-World Data

We assess ZK-Value on two facets in turn: first, valuation quality on the 12-dataset benchmark; second, end-to-end proving cost against the two ZK baselines on the same datasets. Valuation Quality and Throughput. Tables 3 and 4 jointly report per-method AUROC and valuation runtime on the 12-dataset benchmark. ZK-Value consistently outperforms baselines such as G-Shapley, Data Shapley, and Data Banzhaf across most settings, particularly in noisy detection at high feature dimensions. It remains comparable to KNN-Shapley within |ΔAUROC| ≤ 0.033 on every dataset and on both tasks, confirming that the bucketcounting reformulation preserves the underlying valuation primitive. On throughput, ZK-Value runs in 0.11–5.93 s per validation cohort across all twelve datasets, whereas KNN-Shapley itself takes 4.4–427 s. The gap widens at high feature dimension because KNNShapley scales with 𝑁 · 𝑇 · 𝑑, whereas ZK-Value’s per-class bucket histograms decouple the complexity to (𝑁 + 𝑇 ) · 𝑑. Data Shapley and Data Banzhaf time out on the larger rows of Table 4: their cost is dominated by an O (𝑀 · 𝑁 ) retraining loop (𝑀 Monte-Carlo permutations or coalition samples, each requiring a fresh model fit),

Zhaoyu Wang, Pingchuan Ma, Zhantong Xue, Yuguang Zhou, Qixin Zhang, Xiaoqin Zhang, and Shuai Wang

Table 3: Valuation quality on the 12-dataset benchmark. AUROC reported for both mislabel and noisy detection. Mislabel AUROC Dataset phoneme 2dplanes click wind cpu creditcard fraud pol vehicle apsfail mnist cifar10

Noisy AUROC

𝑁

𝑑

G-Shapley

DS

DB

KNN

LSH-Shapley

G-Shapley

DS

DB

KNN

LSH-Shapley

5,404 10,000 10,000 6,574 8,192 10,000 10,000 10,000 10,000 10,000 60,000 50,000

5 10 11 14 21 23 30 48 100 170 768 768

0.658 0.668 0.515 0.726 0.756 0.540 0.766 0.636 0.569 0.783 0.747 0.810

0.564 0.515 0.499 0.583 0.569 0.531 0.585 0.547 0.551 0.539 – –

0.508 0.491 0.491 0.480 0.511 0.491 0.491 0.491 0.491 0.491 – –

0.872 0.943 0.594 0.905 0.959 0.713 0.952 0.970 0.853 0.971 0.982 0.995

0.883 0.938 0.620 0.889 0.952 0.724 0.941 0.957 0.820 0.964 0.979 0.998

0.507 0.517 0.495 0.517 0.499 0.496 0.508 0.499 0.498 0.517 0.519 0.504

0.530 0.514 0.508 0.528 0.541 0.521 0.551 0.520 0.517 0.541 – –

0.508 0.492 0.491 0.480 0.513 0.492 0.494 0.491 0.492 0.494 – –

0.712 0.780 0.567 0.802 0.844 0.686 0.826 0.778 0.779 0.916 0.855 0.950

0.741 0.726 0.723 0.818 0.860 0.773 0.795 0.880 0.771 0.840 0.843 0.899

consistent with prior work [14, 47, 48] that reports these estimators only at thousand-scale 𝑁 . ZK-Value is therefore the only estimator in Table 3 that simultaneously reaches the KNN-Shapley quality frontier and the G-Shapley-class throughput band. End-to-End Proving Cost. Table 5 reports proving time 𝑃, verification time 𝑉 , and proof size |𝜋 | for ZK-Value, KNN-Shapley-ZK, and naive-ZK-LSH-Shapley across the 12-dataset benchmark. Against KNN-Shapley-ZK, ZK-Value delivers a uniform proving-time speedup on every reached dataset, peaking at 20.3× on cpu. Against naiveZK-LSH-Shapley, ZK-Value delivers 12.6×–68.1× proving-time speedups, with the verifier under 4.6 s on every dataset and the proof size shrinking in lockstep with the prover-side reduction. Where the workload crosses out of the small regime, the comparison stops being a speed question and becomes a feasibility question: KNN-Shapley-ZK runs out of host memory on 5 of 12 datasets, and naive-ZK-LSH-Shapley runs out on 3 datasets (vehicle, mnist, cifar10), all of which are the high-𝑑 OpenML and ViT-embedding rows that a production marketplace would actually ship. ZK-Value is the only system in Table 5 that verifies every one of these largescale datasets, in 6.2–135.0 s on the ten OpenML rows and 1445– 2274 s on the two ViT rows, with verification under 4.6 s holding flat throughout. The end-to-end picture is therefore that ZK-Value is strictly better than every baseline wherever a head-to-head comparison is possible, and is the only system that reaches the MLembedding-scale workloads at all. Comparison against ZK-DV and SP1. Direct benchmarking is currently unfeasible for two alternative ZK frameworks: ZK-DV, whose source code is not yet open-sourced, and SP1, a generalpurpose zkVM. ZK-DV [30] reports a maximum configuration of 𝑁 = 256 on MNIST under a LeNet-5 G-Shapley substrate, on which their optimal prover takes ≈ 2992 s per seller. In contrast, on mnist with a ViT at 𝑁 = 60,000 (234× larger), ZK-Value generates a proof in 1445 s, achieving a two-to-three order-of-magnitude speedup despite the larger workload. For SP1, we compiled LSH-Shapley as standard Rust inside within its execution environment; on the smallest dataset (𝑁 = 5404, 𝑑 = 5) it consumed more than 87 GB of resident memory and failed to complete a single proof in over one hour. This is consistent with the structural mismatch between general-purpose zkVMs, whose cycle counts scale with program execution, and the structured workload LSH-Shapley targets.

Table 4: Valuation runtime on the 12-dataset benchmark. Valuation Runtime (s) Dataset phoneme 2dplanes click wind cpu creditcard fraud pol vehicle apsfail mnist cifar10

G-Shapley

DS

DB

KNN

LSH-Shapley

0.86 0.88 0.74 0.43 0.57 1.16 0.69 0.77 0.86 0.76 9.08 7.22

10.48 47.27 58.91 9.20 30.43 73.07 79.65 27.40 398.04 18.20 >1h >1h

3.54 8.46 9.34 6.54 9.74 12.51 21.76 17.55 14.25 20.42 >1h >1h

8.74 28.59 24.70 10.91 17.50 25.89 24.97 27.10 28.99 28.29 729.99 721.97

0.16 0.86 0.31 0.31 0.19 0.54 0.20 0.23 0.78 0.47 3.25 4.21

Takeaway for RQ1. ZK-Value is the only evaluated system to successfully complete the full benchmark suite, maintaining high fidelity with an AUROC within 0.033 of the baseline. By achieving seconds-range proving times for both OpenML and ViT embeddings, ZK-Value demonstrates the practical feasibility of providing scalable, high-accuracy guarantees for real-world data marketplaces.

6.3

RQ2: Scalability

We evaluate ZK-Value along the four workload axes the §4.2.3 cost statement covers: the training-set size 𝑁 , the feature dimension 𝑑, the number of classes 𝐶, and the validation-set size 𝑇 . We anchor the experiments at a reference configuration of 𝑁 = 16,384, 𝑑 = 8, 𝐶 = 10, 𝑇 = 64, and vary one axis at a time around it. Figure 3 plots proving time, verification time, and proof size against each axis. Effect of 𝑁 . The 𝑁 panel of Figure 3 sweeps 𝑁 ∈ {24, 26, . . . , 216 } at the reference 𝑑 = 8, 𝐶 = 10. Prove time scales linearly with the dataset size for larger 𝑁 , reaching 79.8,s at 𝑁 = 65, 536. At smaller values of 𝑁 , the fixed cost of the per-oracle PCS commit/open dominates, but this amortizes once the witness population crosses the per-oracle threshold. The overall linear scaling matches the histogram-consistency cost O (𝐿 · 𝑁 · poly(𝐾)) of §4.2.3. Effect of 𝑑. The 𝑑 panel of Fig. 3 sweeps 𝑑 ∈ {4, 16, 64, 256, 1024, 4096} at the reference 𝑁 = 16,384, 𝐶 = 10. Prove time stays in the 20.0 s

ZK-Value : A Practical Zero-Knowledge System for Verifiable Data Valuation

Table 5: End-to-end ZK cost on the 12-dataset benchmark. 𝑃, 𝑉 , |𝜋 | are proving time, verification time, and proof size. KNN-Shapley-ZK Dataset phoneme 2dplanes click wind cpu creditcard fraud pol vehicle apsfail mnist cifar10

naive-ZK-LSH-Shapley

ZK-Value

𝑁

𝑑

𝑃 (s)

𝑉 (s)

|𝜋 | (MB)

𝑃 (s)

𝑉 (s)

|𝜋 | (MB)

𝑃 (s)

𝑉 (s)

|𝜋 | (MB)

5,404 10,000 10,000 6,574 8,192 10,000 10,000 10,000 10,000 10,000 60,000 50,000

5 10 11 14 21 23 30 48 100 170 768 768

32.1 158 177 43.3 266 280 277 OOM OOM OOM OOM OOM

2.23 3.70 4.45 2.06 7.03 5.19 5.67 OOM OOM OOM OOM OOM

963 1389 1389 988 1512 1512 1515 OOM OOM OOM OOM OOM

80.2 639 302 158 296 627 332 325 OOM 735 OOM OOM

1.42 8.85 2.54 2.72 2.54 9.63 4.35 3.62 OOM 9.59 OOM OOM

498 942 742 633 751 950 751 843 OOM 958 OOM OOM

6.16 21.7 11.3 11.8 13.1 23.2 13.9 25.7 135 10.8 1445 2274

0.75 0.79 0.68 0.66 0.84 0.92 0.76 0.89 1.43 0.75 3.71 4.55

356 469 423 413 440 487 452 544 680 499 1164 1332

Table 6: Ablation study to 72.9 s band across four orders of magnitude in 𝑑, with a discrete step at 𝑑 = 64 where the optional PCA projection activates and adds a fixed verifiable dimensionality-reduction stage. At 𝑑 = 4096, Variant Proof (MB) Prove (s) Verify (s) ZK-Value generates a proof in 72.9 s. The pattern matches §4.2.3: Full system (ZK-Value) 579 11.9 0.73 the Shapley layers are 𝑑-independent, and 𝑑 enters only through w/o super-oracle batching 1247 14.7 1.06 the hashing input and the optional PCA projection. w/o sparsity skipping 579 13.4 0.86 Effect of𝑇 . The𝑇 panel of Figure 3 sweeps𝑇 ∈ {32, 128, 512, 2048, 4096} w/o bucket reformulation 635 129.5 6.91 at the reference 𝑁 = 16,384, 𝑑 = 8, 𝐶 = 10. Prove time is flat within 6.6% across the range. This follows §4.2.3: the histogram and weight stages are 𝑇 -independent, so an operator can extend the validation set at no prover-side cost. A residual log𝑇 slope appears only in encoding commits the 𝐿 · 𝑇 · 𝑁 membership tensor in full, whereas the verify-time row. the bucket refactor commits only the 𝐶 ·𝑀 per-class histograms that Effect of 𝐶. The 𝐶 panel of Figure 3 sweeps 𝐶 ∈ {2, 5, 10, 50, 100} the LSH-Shapley computation actually consumes, which is what at the reference 𝑁 = 16,384, 𝑑 = 8. At 𝐶 = 100, the proof is 1757 MB makes the bucket-counting reformulation the primary structural and proving time is 32.2 s. The observed scaling matches the twolever for proving time. component cost model of §4.2.3: a linear cost from the interactive Super-oracle batching. On the proof-size column, Table 6 shows sumcheck messages (handling per-class lookups √ and weight identithat removing super-oracle PCS batching inflates the proof from ties), and a PCS-opening cost reduced to 𝑂 ( 𝐶) via super-oracle 579 MB to 1247 MB (2.2×); the corresponding proving-time inflation √ batching. At small 𝐶 the proof is floored by 𝐶-independent costs is 11.9 → 14.7 s. The pattern reproduces the 𝐶 scaling rule of (the hashing module and the fixed-overhead PCS commitments), so §4.2.3: opening the per-class oracles individually pushes PCS-open growth is shallow; as 𝐶 rises, the linear transcript term takes over work to scale linearly with 𝐶 instead of with its square root. and scaling approaches linear from below. Prove time follows the Sparsity skipping. Sparsity skipping cuts end-to-end proving time same regime transition. from 13.4 s to 11.9 s (12.6%) Mechanically, a support mask exposes Takeaway for RQ2. ZK-Value demonstrates robust scalability, only the nonzero cells of the three Layer-1 histogram sumchecks maintaining prover latency within a consistent seconds-to-tens(training-histogram, per-class training-histogram, and per-class of-seconds range across modern ML configurations. This stability validation-histogram), eliminating the dense-grid sweep over empty ensures that ZK-Value’s performance remains predictable and pracbuckets. tical as system complexity grows. Per-module breakdown. Fig. 4 partitions ZK-Value’s proving time across the five components detailed in §4.2. At the §6.4 refer6.4 RQ3: Optimization Effectiveness and ence configuration, the hashing module dominates the total cost, Module Breakdown driven by the high ZKP overhead of sign-bit and range-proof opTo isolate the contribution of each optimization ZK-Value stacks erations. The four downstream layers collectively account for the on top of naive-ZK-LSH-Shapley, we run a one-at-a-time knockout remaining 14.5%. on a synthetic Gaussian workload at 𝑁 = 10,000, 𝑑 = 16, 𝐶 = 10. Takeaway for RQ3. The ablation study confirms that ZK-Value’s Bucket-counting reformulation. Table 6 reports the largest optimizations are orthogonal and collectively essential for achievsingle shift on the proving-time column: replacing the bucketing practical performance. The absence of these techniques leads to histogram refactor with the naive-ZK-LSH-Shapley tensor encoding multi-fold degradation across these independent metrics, demoninflates proving time by 11× (11.9 → 129.5 s) at the same workload. strating that ZK-Value’s efficiency stems from a comprehensive The shift is consistent with the cost analysis of §4.2.3: the tensor architectural approach to verifiable valuation.

Zhaoyu Wang, Pingchuan Ma, Zhantong Xue, Yuguang Zhou, Qixin Zhang, Xiaoqin Zhang, and Shuai Wang

1043 102 101 100 10 10 12 10

Proving time (s)

24 26 28 210212214216

102 101 100 10 1 10 2 10 3

Verification time (s)

24 26 28 210212214216

104 103 102 101

Proof size (MB)

24 26 28 210212214216

103 102 101 100

Proving time (s)

22 24 26 28 210 212

(a) Effect of 𝑁 at 𝑑 = 8, 𝐶 = 10. 103 102 101 100

Proving time (s)

25 27 29 211212

102 101 100 10 1 10 2

Verification time (s)

25 27 29 211212

104 103 102 101

102 101 100 10 1 10 2

Verification time (s)

22 24 26 28 210 212

104 103 102 101

Proof size (MB)

22 24 26 28 210 212

(b) Effect of 𝑑 at 𝑁 = 16,384, 𝐶 = 10.

Proof size (MB)

25 27 29 211212

104 103 102 101 100

(c) Effect of 𝑇 at 𝑁 = 16,384, 𝑑 = 8, 𝐶 = 10.

Proving time (s)

21 2223 2526

29

103 102 101 100 10 1 10 2

Verification time (s)

21 2223 2526

29

106 105 104 103 102 101

Proof size (MB)

21 2223 2526

29

(d) Effect of 𝐶 at 𝑁 = 16,384, 𝑑 = 8.

Figure 3: ZK-Value scalability along the four workload axes (𝑑, 𝑁 ,𝑇 , 𝐶).

Hashing module (85.4%) Layer 1 (histogram consistency) (5.5%) Layer 2 (lookup consistency) (8.8%) Layer 3 (weight + aggregation) (0.2%) Layer 4 (input/output reconstruction) (0.1%) Figure 4: ZK-Value proving-time decomposition.

7

RELATED WORK

Privacy-preserving and verifiable data valuation. The Shapley formulation of data valuation has produced a rich algorithmic line [13, 14, 20, 21, 24, 47, 51], all of which assume a trusted valuator with plaintext access to seller data. A second line addresses the resulting privacy tension via differentially private estimators [48] or secure-MPC prototypes [36, 45]. While these approaches ensure privacy, they lack verifiability, i.e., the ability for external parties to verify results without accessing raw data. Data marketplaces and pricing. The database community has built a layered stack for data and model markets, from query-based pricing [8, 23] and model-based pricing for ML [6, 29] to marketplatform abstractions and unifying surveys [9, 35], and, more recently, Shapley-driven pricing exposed to users [54], auction- and competition-based pricing under federated learning [28, 42], and explicit treatments of marketplace privacy and security [1]. All assume a trusted broker who sees raw seller data in the clear. ZKValue removes the trust assumption by promoting the operator to a prover whose valuation, pricing, and selective disclosure are each attested by a succinct proof. Zero-knowledge proof systems for ML and analytics. ZK proofs are now practical for non-trivial computations, spanning CNN/Transformer training and inference [5, 12, 19, 31, 40, 50], billion-parameter LLMs [37, 41], model fairness [53], ad-hoc SQL [18, 27], and causal analytics [49], with general-purpose zkVMs [25, 52] as substrate. Rather than encoding a generic ML or SQL workload, ZK-Value co-designs a valuation primitive (LSH-Shapley) with a specialized ZK protocol whose super-oracle batching and sparsity skipping make Shapley-style data valuation provable end-to-end at marketplace scale.

8

DISCUSSION AND FUTURE WORK

Privacy-enhancing composition. ZK-Value is designed to compose orthogonally with the privacy-preserving mechanisms discussed in §7. For instance, the noise calibration techniques from DP-TKNN-Shapley [48] can be combined with ZK-Value to provide a verifiable defense against membership inference attacks. This allows auditors to verify that release-time noise was applied honestly without revealing the underlying scores. Beyond LSH-Shapley. LSH-Shapley is a Shapley-family proxy that inherits the faithfulness assumption of the KNN-Shapley line. Tighter proxies — gradient-Shapley, influence-function approximations, or coalition-sketch estimators with sharper concentration — remain an open structural target, provided their final-result correctness can be verified without replaying data-dependent search; the same requirements extend to regression and generative utilities beyond the classification scope of §3.

9

CONCLUSION

We presented ZK-Value, a practical zero-knowledge system that resolves the fundamental conflict between privacy and verifiability in data marketplaces. By co-designing the LSH-Shapley valuation primitive with a specialized, highly optimized ZKP protocol, we bridged the scalability gap that previously made verifiable valuation infeasible at modern machine learning scales. Our evaluation confirms that ZK-Value maintains baseline valuation fidelity while reducing proving times to seconds or minutes, producing megabyte-sized proofs verifiable in seconds. Ultimately, ZK-Value provides a deployable, auditable foundation for transparent crossorganizational data trading.

REFERENCES [1] Daniel Alabi, Sainyam Galhotra, Shagufta Mehnaz, Zeyu Song, and Eugene Wu. 2025. Privacy and security in distributed data markets. In Companion of the 2025 International Conference on Management of Data. 775–787. [2] Nir Bitansky, Ran Canetti, Alessandro Chiesa, Shafi Goldwasser, Huijia Lin, Aviad Rubinstein, and Eran Tromer. 2017. The hunting of the SNARK. Journal of Cryptology 30, 4 (2017), 989–1066. [3] Andrei Z Broder, Moses Charikar, Alan M Frieze, and Michael Mitzenmacher. 1998. Min-wise independent permutations. In Proceedings of the thirtieth annual ACM symposium on Theory of computing. 327–336. [4] Moses S Charikar. 2002. Similarity estimation techniques from rounding algorithms. In Proceedings of the thiry-fourth annual ACM symposium on Theory of

ZK-Value : A Practical Zero-Knowledge System for Verifiable Data Valuation

computing. 380–388. [5] Bing-Jyue Chen, Suppakit Waiwitlikhit, Ion Stoica, and Daniel Kang. 2024. Zkml: An optimizing system for ml inference in zero-knowledge proofs. In Proceedings of the Nineteenth European Conference on Computer Systems. 560–574. [6] Lingjiao Chen, Paraschos Koutris, and Arun Kumar. 2019. Towards model-based pricing for machine learning in a data marketplace. In Proceedings of the 2019 international conference on management of data. 1535–1552. [7] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. 2004. Localitysensitive hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry. 253–262. [8] Shaleen Deep and Paraschos Koutris. 2017. QIRANA: A framework for scalable query pricing. In Proceedings of the 2017 ACM International Conference on Management of Data. 699–713. [9] Raul Castro Fernandez, Pranav Subramaniam, and Michael J Franklin. 2020. Data market platforms: Trading data assets to solve data problems. arXiv preprint arXiv:2002.01047 (2020). [10] Amos Fiat and Adi Shamir. 1986. How to prove yourself: Practical solutions to identification and signature problems. In Conference on the theory and application of cryptographic techniques. Springer, 186–194. [11] Ariel Gabizon and Zachary J Williamson. 2020. plookup: A simplified polynomial protocol for lookup tables. Cryptology ePrint Archive (2020). [12] Sanjam Garg, Aarushi Goel, Somesh Jha, Saeed Mahloujifar, Mohammad Mahmoody, Guru-Vamsi Policharla, and Mingyuan Wang. 2023. Experimenting with zero-knowledge proofs of training. In Proceedings of the 2023 ACM SIGSAC conference on computer and communications security. 1880–1894. [13] Amirata Ghorbani, Michael Kim, and James Zou. 2020. A distributional framework for data valuation. In International Conference on Machine Learning. PMLR, 3535–3544. [14] Amirata Ghorbani and James Zou. 2019. Data shapley: Equitable valuation of data for machine learning. In International conference on machine learning. PMLR, 2242–2251. [15] Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al. 1999. Similarity search in high dimensions via hashing. In Vldb, Vol. 99. 518–529. [16] S GOLDWASSER, S MICALI, and C RACKOFF. 1989. The knowledge complexity of interactive proof systems. SIAM journal on computing (Print) 18, 1 (1989), 186–208. [17] Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, and Riad S Wahby. 2023. Brakedown: Linear-time and field-agnostic SNARKs for R1CS. In Annual International Cryptology Conference. Springer, 193–226. [18] Binbin Gu, Juncheng Fang, and Faisal Nawab. 2025. PoneglyphDB: Efficient non-interactive zero-knowledge proofs for arbitrary sql-query verification. Proceedings of the ACM on Management of Data 3, 1 (2025), 1–27. [19] Meng Hao, Hanxiao Chen, Hongwei Li, Chenkai Weng, Yuan Zhang, Haomiao Yang, and Tianwei Zhang. 2024. Scalable zero-knowledge proofs for non-linear functions in machine learning. In 33rd USENIX Security Symposium (USENIX Security 24). 3819–3836. [20] Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nezihe Merve Gurel, Bo Li, Ce Zhang, Costas Spanos, and Dawn Song. 2019. Efficient task-specific data valuation for nearest neighbor algorithms. Proc. VLDB Endow. 12, 11 (July 2019), 1610–1623. https://doi.org/10.14778/3342263.3342637 [21] Kevin Jiang, Weixin Liang, James Y Zou, and Yongchan Kwon. 2023. Opendataval: a unified benchmark for data valuation. Advances in Neural Information Processing Systems 36 (2023), 28624–28647. [22] Pang Wei Koh and Percy Liang. 2017. Understanding black-box predictions via influence functions. In International conference on machine learning. PMLR, 1885–1894. [23] Paraschos Koutris, Prasang Upadhyaya, Magdalena Balazinska, Bill Howe, and Dan Suciu. 2015. Query-based data pricing. Journal of the ACM (JACM) 62, 5 (2015), 1–44. [24] Yongchan Kwon and James Zou. 2022. Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning. In International Conference on Artificial Intelligence and Statistics. PMLR, 8780–8802. [25] Succinct Labs. 2026. SP1. https://github.com/succinctlabs/sp1. [26] Alan Li, Qingkai Liang, and Mo Dong. 2024. Sparsity-aware protocol for zkfriendly ml models: Shedding lights on practical zkml. Cryptology ePrint Archive (2024). [27] Xiling Li, Chenkai Weng, Yongxin Xu, Xiao Wang, and Jennie Rogers. 2023. Zksql: Verifiable and efficient query evaluation with zero-knowledge proofs. Proceedings of the VLDB Endowment 16, 8 (2023). [28] Zitao Li, Bolin Ding, Liuyi Yao, Yaliang Li, Xiaokui Xiao, and Jingren Zhou. 2024. Performance-based pricing for federated learning via auction. Proceedings of the VLDB Endowment 17, 6 (2024), 1269–1282. [29] Jinfei Liu, Jian Lou, Junxu Liu, Li Xiong, Jian Pei, and Jimeng Sun. 2021. Dealer: An end-to-end model marketplace with differential privacy. Proceedings of the VLDB Endowment 14, 6 (2021). [30] Ruibang Liu, Minyu Chen, Dengji Ma, and Guoqiang Li. 2026. Bridging Privacy and Utility: A Verifiable Framework for Data Valuation via Zero-Knowledge Proofs. Cryptology ePrint Archive (2026).

[31] Tianyi Liu, Xiang Xie, and Yupeng Zhang. 2021. Zkcnn: Zero knowledge proofs for convolutional neural network predictions and accuracy. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2968–2985. [32] Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. 1992. Algebraic methods for interactive proof systems. Journal of the ACM (JACM) 39, 4 (1992), 859–868. [33] Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. 2007. Multiprobe LSH: efficient indexing for high-dimensional similarity search. In Proceedings of the 33rd international conference on Very large data bases. 950–961. [34] Konstantin D Pandl, Fabian Feiland, Scott Thiebes, and Ali Sunyaev. 2021. Trustworthy machine learning for health care: scalable data valuation with the shapley value. In Proceedings of the Conference on Health, Inference, and Learning. 47–57. [35] Jian Pei, Raul Castro Fernandez, and Xiaohui Yu. 2023. Data and AI model markets: Opportunities for data and model sharing, discovery, and integration. Proceedings of the VLDB Endowment 16, 12 (2023), 3872–3873. [36] Li Peng, Jiayao Zhang, Yihang Wu, Weiran Liu, Jinfei Liu, Zheng Yan, Kui Ren, Lei Zhang, and Lin Qu. 2025. Reliable and Private Utility Signaling for Data Markets. Proceedings of the ACM on Management of Data 3, 6 (2025), 1–27. [37] Wenjie Qu, Yijun Sun, Xuanming Liu, Tao Lu, Yanpei Guo, Kai Chen, and Jiaheng Zhang. 2025. { zkGPT } : An Efficient Non-interactive Zero-knowledge Proof Framework for { LLM } Inference. In 34th USENIX Security Symposium (USENIX Security 25). 2045–2063. [38] Lloyd S Shapley et al. 1953. A value for n-person games. (1953). [39] Rachael Hwee Ling Sim, Xinyi Xu, and Bryan Kian Hsiang Low. 2022. Data Valuation in Machine Learning:" Ingredients", Strategies, and Open Challenges.. In IJCAI. 5607–5614. [40] Haochen Sun, Tonghe Bai, Jason Li, and Hongyang Zhang. 2024. Zkdl: Efficient zero-knowledge proofs of deep learning training. IEEE Transactions on Information Forensics and Security 20 (2024), 914–927. [41] Haochen Sun, Jason Li, and Hongyang Zhang. 2024. zkllm: Zero knowledge proofs for large language models. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security. 4405–4419. [42] Peng Sun, Liantao Wu, Zhibo Wang, Jinfei Liu, Juan Luo, and Wenqiang Jin. 2024. A profit-maximizing data marketplace with differentially private federated learning under price competition. Proceedings of the ACM on Management of Data 2, 4 (2024), 1–27. [43] Mukund Sundararajan and Amir Najmi. 2020. The many Shapley values for model explanation. In International conference on machine learning. PMLR, 9269–9278. [44] Justin Thaler. 2022. Proofs, arguments, and zero-knowledge. Foundations and Trends® in Privacy and Security 4, 2-4 (2022), 117–660. [45] Zhihua Tian, Jian Liu, Jingyu Li, Xinle Cao, Ruoxi Jia, Jun Kong, Mengdi Liu, and Kui Ren. 2022. Private data valuation and fair payment in data marketplaces. arXiv preprint arXiv:2210.08723 (2022). [46] Riad S Wahby, Ioanna Tzialla, Abhi Shelat, Justin Thaler, and Michael Walfish. 2018. Doubly-efficient zkSNARKs without trusted setup. In 2018 IEEE Symposium on Security and Privacy (SP). IEEE, 926–943. [47] Jiachen T Wang and Ruoxi Jia. 2023. Data banzhaf: A robust data valuation framework for machine learning. In International conference on artificial intelligence and statistics. PMLR, 6388–6421. [48] Jiachen Tianhao Wang, Yuqing Zhu, Yu-Xiang Wang, Ruoxi Jia, and Prateek Mittal. 2023. A privacy-friendly approach to data valuation. Advances in Neural Information Processing Systems 36 (2023), 60429–60467. [49] Zhaoyu Wang, Pingchuan Ma, Zhantong Xue, Yanbo Dai, Zhenlan Ji, and Shuai Wang. 2025. Privacy-preserving and Verifiable Causal Prescriptive Analytics. Proceedings of the ACM on Management of Data 3, 6 (2025), 1–27. [50] Chenkai Weng, Kang Yang, Xiang Xie, Jonathan Katz, and Xiao Wang. 2021. Mystique: Efficient conversions for { Zero-Knowledge } proofs with applications to machine learning. In 30th USENIX Security Symposium (USENIX Security 21). 501–518. [51] Jinsung Yoon, Sercan Arik, and Tomas Pfister. 2020. Data valuation using reinforcement learning. In International Conference on Machine Learning. PMLR, 10842–10851. [52] RISC Zero. 2026. RISC Zero. https://github.com/risc0/risc0. [53] Tianyu Zhang, Shen Dong, O Deniz Kose, Yanning Shen, and Yupeng Zhang. 2025. Fairzk: A scalable system to prove machine learning fairness in zero-knowledge. In 2025 IEEE Symposium on Security and Privacy (SP). IEEE, 3460–3478. [54] Yiding Zhu, Hongwei Zhang, Jiayao Zhang, Jinfei Liu, and Kui Ren. 2024. Dataprice: An interactive system for pricing datasets in data marketplaces. Proceedings of the VLDB Endowment 17, 12 (2024), 4433–4436.

Zhaoyu Wang, Pingchuan Ma, Zhantong Xue, Yuguang Zhou, Qixin Zhang, Xiaoqin Zhang, and Shuai Wang

Table 7: Committed oracles of ZK-LSH-Shapley (𝐶 = 2). “Family” column: H = histogram, L = lookup, W = weight, Real-world panel. The 12-dataset panel comprises ten OpenML A = advice, Y = label indicator, P = preamble, PCA = conditabular benchmarks (phoneme, 2dplanes, click, wind, cpu, creditcard, tional. fraud, pol, vehicle, apsfail; raw feature dimensions 𝑑 raw ∈ [5, 170]) and two ViT embedding datasets on mnist and cifar10 Oracle Domain Family (𝑑 raw = 768). Every row passes through the same pre-processing pipeline: (i) class- balanced sub-sampling down to the largest powercnt[ℓ, 𝑏 ] 𝐿·𝑀 H of-two cardinality not exceeding the configured budget for 𝑁 and cnt_c_tr[ℓ, 𝑏, 𝑐 ] 𝐿 ·𝑀 ·𝐶 H 𝑇 , (ii) 𝑧-score normalization, (iii) ℓ2 normalization. The power-ofcnt_c_te[ℓ, 𝑏, 𝑐 ] 𝐿 ·𝑀 ·𝐶 H 𝑚[ℓ, b 𝑖] 𝐿·𝑁 L two constraint is required so that the multilinear extensions used 𝑚 b𝑐 [ℓ, 𝑖 ] 𝐿·𝑁 L inside the proof system live on Boolean hypercubes of matched b 𝑡𝑐 [ℓ, 𝑖 ] 𝐿·𝑁 L size. Datasets whose raw dimension exceeds the hashing budget 𝐻𝑀 [ · ] 𝐿·𝑁 L (self-verified) enter the verifiable PCA preamble described in §4.2. 𝑊 [ℓ, 𝑖 ], 𝐷, 𝐷 −1 , 𝑒 𝐿 · 𝑁 W Synthetic Gaussian workloads. The scalability sweeps in §6.3 and wt_num, 𝑡 match 𝐿·𝑁 A the ablation in §6.4 use a synthetic Gaussian generator that gives 𝑦ind,𝑐 𝑁 Y (𝐶 oracles) full control over 𝑁 , 𝑑 raw , 𝐶, and 𝑇 . Concretely: features 𝑥𝑖 ∈ R𝑑raw 𝑦test_ind,𝑐 𝑇 Y (𝐶 oracles) are drawn i.i.d. from N (0, 𝐼𝑑raw ); we sample 𝐶 random unit anchors sign[ℓ, 𝑘, · ] 𝐿 · 𝐾 · (𝑁 +𝑇 ) P 𝑎𝑐 ∈ R𝑑raw and assign each point the label arg max𝑐 ⟨𝑥𝑖 /∥𝑥𝑖 ∥, 𝑎𝑐 ⟩ abs_dp[ℓ, 𝑘, · ] 𝐿 · 𝐾 · (𝑁 +𝑇 ) P 𝑥 raw (conditional) 𝑁 · 𝑑 raw PCA (nearest-cosine assignment); the resulting features and labels are 𝑉pca (conditional) 𝑑 raw · 𝑑 pca PCA split into (𝑥 train, 𝑦train ) and (𝑥 test, 𝑦test ) at the configured sizes, each row ℓ2 -normalized to match the LSH preprocessing pipeline. The non-power-of-two cases used in the ablation reference are zeropadded up to the next power of two, which is the natural input format for the per-class label-indicator sparsity that the M2 fallback path of §5.2 exploits.

A

DATASETS AND PRE-PROCESSING

B.2

B

ALGORITHM PSEUDOCODE AND EXTENDED DERIVATIONS B.1 ZK-LSH-Shapley Prove/Verify Pseudocode Committed oracles. Table 7 catalogs every multilinear oracle the prover commits in Phase 1 of Algorithm 3: 13 + 2𝐶 bucket-specific oracles (17 at 𝐶 = 2), the two hashing-preamble oracles (sign and abs_dp), and, conditionally, two PCA oracles when 𝑑 raw exceeds the hashing budget. Each is committed as a multilinear extension in the sense of §2.2, so the verifier interacts with it only through PCS openings at Fiat–Shamir-sampled points. The non-obvious commitment choices follow. The Shapley-weight family 𝑊 , 𝐷 = 𝑀 (𝑀 − 1), 𝐷 −1, 𝑒 records the per-table contribution, denominator, denominator inverse, and edge-case flag (𝑒 = 1 ⇔ 𝑚 b ≤ 1); committing the advice oracles wt_num, 𝑡 match (derivable from the rest) lets the weight-identity sumcheck stay low-degree. The label indicators 𝑦ind,𝑐 , 𝑦test_ind,𝑐 one-hot-encode class membership into 2𝐶 oracles, the factor that drives the super-oracle batching of §5. The hashing preamble commits sign and abs_dp = |⟨𝑟 ℓ , 𝑥⟩| so the verifier can reconstruct each signed dot product at the final challenge, and the conditional PCA oracles 𝑥 raw, 𝑉pca are committed only when 𝑑 raw exceeds the hashing budget.

Full per-module protocol. Algorithm 4 below is the detailed counterpart of the high-level Algorithm 2 in §4.2.2. Each step in the main-body algorithm expands into the per-module commitments and sumchecks listed here.

ZK-LSH-Shapley Per-Module Specification Table

Table 8 catalogs the logical sumcheck modules of ZK-LSH-Shapley (§4.2.2). For each module we list its verification layer, target-sum identity (canonical forms drawn from §4.2.1 and the closed-form derivation of Appendix B.3), sum domain, maximal round-message degree, and the RLC batch the module is folded into in the deployed implementation (§5). The deployed implementation collapses logical modules sharing a sum domain into five RLC-batched sumcheck instances: a batched-LN sumcheck over (𝐿, 𝑁 ) folding ten samedomain identities under coefficients 𝛽 [0..9], a batched-LB sumcheck over (𝐿, 𝑀) folding three squared-count auxiliaries under 𝛾 [0..2], plus three standalone sumchecks (V3, S-agg, S1).

B.3

LSH-Shapley Closed Form: Derivation, Axioms, and Bounds

This subsection derives the four-case closed form (2), verifies the four Shapley fairness axioms, and records the sign and monotonicity properties cited in §4.1.2. Setup recap. Fix a validation point (𝑥𝑡te, 𝑦𝑡 ) and a hash table ℓ. Write the bucket as Bℓ𝑡 = { 𝑗 ∈ [𝑁 ] : 𝐵 ℓ (𝑥 tr𝑗 ) = 𝐵 ℓ (𝑥𝑡te )} of size 𝑀, the agreeing subset Bℓ𝑡,+ of size 𝑀 + , and the disagreeing subset of size 𝑀 − = 𝑀 − 𝑀 + . The per-table bucket-vote utility (defined in §4.1.1) is 𝑢 ℓ𝑡 (𝑆) = |𝑆 ∩ Bℓ𝑡,+ |/|𝑆 ∩ Bℓ𝑡 |, with 𝑢 ℓ𝑡 (𝑆) := 0 when Í 𝑆 ∩ Bℓ𝑡 = ∅. Throughout we write 𝐻𝑚 = 𝑚 𝑛=1 1/𝑛 (𝐻 0 = 0). Dummy collapse (Lemma B.1). For any 𝑗 ∉ Bℓ𝑡 and any 𝑆, (𝑆 ∪ { 𝑗 }) ∩ Bℓ𝑡 = 𝑆 ∩ Bℓ𝑡 , so 𝑢 ℓ𝑡 (𝑆 ∪ { 𝑗 }) = 𝑢 ℓ𝑡 (𝑆). Non-colliders are therefore Shapley dummies and 𝜙 𝑗 = 0, and the Shapley value of any 𝑖 ∈ Bℓ𝑡 in the 𝑁 -player game equals its value in the 𝑀-player sub-game over Bℓ𝑡 .

ZK-Value : A Practical Zero-Knowledge System for Verifiable Data Valuation

Table 8: Per-module specification for ZK-LSH-Shapley. “RLC batch” is the batch each module is folded into in the deployed implementation: LN = batched-(𝐿, 𝑁 ) under 𝛽 [0..9], LB = batched-(𝐿, 𝑀) under 𝛾 [0..2], Std = standalone. Identities use the canonical forms of §4.2.1; 𝑤¯ denotes the denominator-cleared weight numerator (Appendix B.3). Module (descriptive name)

Layer

Target-sum identity

Sum domain

Round-deg.

V1 (training-histogram consistency) V2 (per-class training-histogram consistency) V3 (per-class validation-histogram consistency)

1 1 1

(𝐿, 𝑁 ) (𝐿, 𝑁 ) (𝐿,𝑇 )

𝐾 +1 𝐾 +2 𝐾 +2

LN LN Std

V4-main (bucket-size lookup, main) V4-aux (bucket-size lookup, squared-count auxiliary) V5-main (same-class lookup, main) V5-aux (same-class lookup, squared-count auxiliary) V6-main (validation-class lookup, main) V6-aux (validation-class lookup, squared-count auxiliary)

2 2

Í Î cnt[ℓ, 𝑏 ] = ℎ 𝑘Í𝑏𝑘 𝑠𝑘 (ℓ, ℎ) + (1−𝑏𝑘 ) (1−𝑠𝑘 (ℓ, ℎ) ) cnt_c_tr[ℓ, 𝑏, 𝑐 ] = Íℎ 1[𝑦ℎ = 𝑐 ] · eq𝐾 (𝑏, 𝜅 ℓ (𝑥ℎ ) ) cnt_c_te[ℓ, 𝑏, 𝑐 ] = 𝑡 1[𝑦𝑡te = 𝑐 ] · eq𝐾 (𝑏, 𝜅 ℓ (𝑥𝑡te ) ) Í Î b = ⟨eq, cnt⟩ (eq𝐾 identity) (ℓ,ℎ)Íeqℓ · 𝑘 𝑔𝑘 · 𝑚 𝐶 4 = (ℓ,𝑏) cnt 2 · eq (squared-count)

(𝐿, 𝑁 ) (𝐿, 𝑀 )

𝐾 +2 3

LN LB

2 2

eq𝐾 identity binding 𝑚 b𝑐 ↔ cnt_c_tr Squared-count claim on cnt_c_tr · cc_weighted

(𝐿, 𝑁 ) (𝐿, 𝑀 )

𝐾 +2 3

LN LB

2 2

eq𝐾 identity binding b 𝑡𝑐 ↔ cnt_c_te Squared-count claim on cnt_c_te · cc_weighted

(𝐿, 𝑁 ) (𝐿, 𝑀 )

𝐾 +2 3

LN LB

S-new-2-edge (edge-case weight identity) S-new-2-nonedge (interior weight identity) E-bool (edge-flag boolean check) S-weight-1 (denominator-inverse structural check, non-edge) S-weight-2 (denominator-inverse structural check, edge) S-agg (table-aggregation sumcheck) S1 (normalization sumcheck)

3 3 3 3

Í b · t_match ] = 0 on 𝑒 = 1 Í (ℓ,ℎ) 𝑒 · [ 𝑊 − 𝑚 (ℓ,ℎ) (1 − 𝑒 ) · [ 𝑊 · 𝐷 − wt_num ] = 0 on 𝑀 ≥ 2 𝑒 · (1 − 𝑒 ) = 0 (Boolean flag) (1 − 𝑒 ) · 𝐷 · 𝐷 inv = (1 − 𝑒 ) (denominator inverse on non-edge)

(𝐿, 𝑁 ) (𝐿, 𝑁 ) (𝐿, 𝑁 ) (𝐿, 𝑁 )

4 4 2 3

LN LN LN LN

3

𝑒 · 𝐷 = 0 (structural; 𝐷 = 0 on edge) Í sv_sum[ℎ] = ℓ 𝑊 [ℓ, ℎ] sv_avg · (𝐿 · 𝑇 ) = sv_sum (normalization, inherited)

(𝐿, 𝑁 )

2

LN

𝐿 𝑁

1 1

Std Std

3 3

Marginal contributions (Lemma B.2). For 𝑇 ⊆ Bℓ𝑡 \ {𝑖} with |𝑇 | = 𝑘 and |𝑇 ∩ Bℓ𝑡,+ | = 𝑚 + , direct algebra gives, for 𝑘 ≥ 1, Δ𝑖+ (𝑇 ) := 𝑢 ℓ𝑡 (𝑇 ∪{𝑖})−𝑢 ℓ𝑡 (𝑇 ) =

𝑘 − 𝑚+ , 𝑘 (𝑘 + 1)

Δ𝑖− (𝑇 ) = −

𝑚+ , 𝑘 (𝑘 + 1)

where + / − denote 𝑦𝑖 = 𝑦𝑡 / 𝑦𝑖 ≠ 𝑦𝑡 . For 𝑘 = 0: Δ𝑖+ (𝑇 ) = 1 and Δ𝑖− (𝑇 ) = 0. Closed form (Theorem B.1). For 𝑖 ∈ Bℓ𝑡 and 𝑀 ≥ 2, 𝜙+ =

𝐻𝑀 (𝑀 + − 1)(𝐻𝑀 − 1) − , 𝑀 𝑀 (𝑀 − 1)

𝜙− = −

𝑀 + (𝐻𝑀 − 1) . 𝑀 (𝑀 − 1)

For 𝑀 = 1, 𝜙𝑖 = 1[𝑦𝑖 = 𝑦𝑡 ]. For 𝑖 ∉ Bℓ𝑡 , 𝜙𝑖 = 0. Proof (correct-label case, 𝑀 ≥ 2, 𝑦𝑖 = 𝑦𝑡 ). By Lemma B.1 we work in the 𝑀-player sub-game. Decomposing the Shapley sum over 𝑘 = |𝑇 | and 𝑚 + = |𝑇 ∩ Bℓ𝑡,+ |,    𝑀 −1 ∑︁ 𝑘! (𝑀−𝑘−1)! ∑︁ 𝑀 + −1 𝑀 − 𝑘 − 𝑚 + 1 + , 𝜙+ = 𝑀 𝑀! 𝑚+ 𝑘−𝑚 + 𝑘 (𝑘 + 1) + 𝑘=1

𝑚

where the leading 1/𝑀 collects the 𝑘 = 0 term and 𝑚 + ranges over 0, . . . , min(𝑘, 𝑀 + − 1). The Vandermonde identity and its weighted variant give ∑︁ 𝑀 + −1 𝑀 −  𝑀−1 = , 𝑚 + 𝑘−𝑚 + 𝑘 𝑚+   ∑︁ 𝑀 + −1 𝑀 −  𝑀−2 + 𝑚+ = (𝑀 −1) , 𝑚 + 𝑘−𝑚 + 𝑘−1 𝑚+
−2
which collapse the inner sum to 𝑘 𝑀𝑘−1 − (𝑀 + − 1) 𝑀 𝑘 −1 . SubstiÍ𝑀 −1 tuting and using 𝑘=1 1/(𝑘 + 1) = 𝐻𝑀 − 1, 1 𝐻𝑀 − 1 (𝑀 + − 1)(𝐻𝑀 − 1) 𝐻𝑀 (𝑀 + − 1)(𝐻𝑀 − 1) 𝜙+ = + − = − . 𝑀 𝑀 𝑀 (𝑀 − 1) 𝑀 𝑀 (𝑀 − 1) Í 𝑀 +
𝑀 − −1
The incorrect-label case is analogous, using 𝑚+ 𝑚 + 𝑚 + 𝑘 −𝑚 + =
𝑀 −2 + − 𝑀 𝑘 −1 , and yields 𝜙 . The 𝑀 = 1 case follows since the only coalition is empty (𝑘 = 0), giving 𝜙𝑖 = Δ𝑖 (𝑇 = ∅)/1. □

RLC batch

Shapley axioms (Theorem B.2). The closed form satisfies all four fairness axioms against 𝑢 ℓ𝑡 . Í • Efficiency. 𝑖 ∈ [𝑁 ] 𝜙𝑖 = 𝑀 + /𝑀 = 𝑢 ℓ𝑡 ([𝑁 ]). For 𝑀 ≥ 2, expanding 𝑀 + · 𝜙 + + 𝑀 − · 𝜙 − and using 𝑀 + + 𝑀 − = 𝑀 telescopes the harmonic terms to 𝑀 + /𝑀; non-colliders contribute zero by Lemma B.1. • Symmetry. 𝜙 + and 𝜙 − depend on 𝑖 only through (𝑀, 𝑀 +, 1[𝑦𝑖 = 𝑦𝑡 ]), so any two bucket-mates sharing a label receive equal value. • Dummy player. Established by Lemma B.1. • Linearity. Inherited from the linearity of Shapley values in the utility function. This is what licenses the multi-table mean of Í §4.1.1: the Shapley value of 𝑢¯ = (𝐿𝑇 ) −1 ℓ,𝑡 𝑢 ℓ𝑡 equals the corresponding mean of the per-table per-validation Shapley values. Sign and monotonicity (Theorem B.3). For 𝑀 ≥ 2, the algebraic rewrite 𝜙 + = 1/𝑀 + (𝑀 − 𝑀 + )(𝐻𝑀 − 1)/(𝑀 (𝑀 − 1)) gives: • 𝜙 + ≥ 1/𝑀 > 0 always; equality iff 𝑀 + = 𝑀. • 𝜙 − ≤ 0 always; equality iff 𝑀 + = 0. • 𝜙 + − 𝜙 − = 1/𝑀 + (𝐻𝑀 − 1)/(𝑀 − 1) > 0, so the closed form discriminates correct-label from incorrect-label colliders. • Both weights are non-increasing in 𝑀 + : 𝜕𝜙 + /𝜕𝑀 + = 𝜕𝜙 − /𝜕𝑀 + = −(𝐻𝑀 − 1)/(𝑀 (𝑀 − 1)) ≤ 0. • Asymptotically, fixing 𝑝 = 𝑀 + /𝑀, both weights are 𝑂 (𝐻𝑀 /𝑀) = 𝑂 (log 𝑀/𝑀) as 𝑀 → ∞, capturing the dilution of per-point value in large buckets.

B.4

Theorem 1: Rank Concentration (Proof Sketch)

Theorem 1 (rank-concentration). Fix a validation point 𝑥 te and a training point 𝑥𝑖tr . Let 𝜌 (𝑥𝑖tr ) denote the true KNN-Shapley rank of 𝑥𝑖tr against 𝑥 te , and 𝜌ˆ (𝑥𝑖tr ; 𝐿) the LSH-Shapley rank estimated from 𝐿 independent tables. For any 𝜀, 𝛿 > 0 there exists 𝐿 ∗ = 𝐿 ∗ (𝜀, 𝛿, 𝐾, 𝑑) such that for 𝐿 ≥ 𝐿 ∗ ,   Pr | 𝜌ˆ (𝑥𝑖tr ; 𝐿) − 𝜌 (𝑥𝑖tr )| > 𝜀 · 𝑁 ≤ 𝛿.

Zhaoyu Wang, Pingchuan Ma, Zhantong Xue, Yuguang Zhou, Qixin Zhang, Xiaoqin Zhang, and Shuai Wang

Algorithm 3 ZK-LSH-Shapley Prove / Verify (sketch) 1: Input (Prover): {𝑥𝑖tr , 𝑦𝑖tr }𝑖 ∈ [𝑁 ] , {𝑥𝑡te , 𝑦𝑡te }𝑡 ∈ [𝑇 ] , hash tables {𝜅 ℓ }ℓ ∈ [𝐿] . 2: Input (Verifier): public parameters pp, commitments {C𝑖 }𝑖 ∈ [𝑚] , Cval . 3: Phase 1 — Commit. 4: Prover hashes data and builds the bucket-, lookup-, weight-, advice-,

label-, and preamble-family oracles of Table 7 (with conditional PCA oracles when 𝑑 raw > budget). 5: Prover publishes cm(·) for each oracle above and broadcasts sv_sum, sv_avg. 6: Phase 2 — Sumcheck. 7: Fiat–Shamir-derive (𝛽 [0..9], 𝛾 [0..2], 𝑟𝑐 , 𝜌, 𝜌 1 ) from the transcript. Run RLC-batched sumcheck over (𝐿, 𝑁 ) folding the ten Layer-1/2/3 8:

modules of Table 8 (LN batch). The per-class validation-histogram sumcheck is folded in via 𝑟𝑐 , with the same 𝑟𝑐 reused for both the perclass training- and validation-histogram class-folding and the batched run. 9: Run RLC-batched sumcheck over (𝐿, 𝑀 ): bucket-size lookup auxiliary. 10: If high-𝑑 raw : run training-side and test-side PCA-projection sumchecks plus the orthonormality sumcheck. Always-on: dot-product sign sumchecks (training and test) over log 𝑑. 11: Run Op1 input-side reconstruction sumcheck (§4.2.2, Layer 4). 12: Run Op7 output-side reconstruction sumcheck (§4.2.2, Layer 4). 13: Phase 3 — Opening. 14: At each final challenge point the verifier requests, in the pre-

optimization baseline: (a) 2𝐾 + 2 sign-bit openings (22 at 𝐾 = 10; §5 reduces this to 𝑂 (1)); (b) (2𝐶 + 2) per-class histogram openings; (c) 𝐶 per-class lookup openings. Each opening invokes one PCS opening proof. 15: For each provider 𝑖: PCS openings of 𝑥f tr at 𝜏1 and cm(𝐷𝑖 ) at 𝜏1,low (Op1); sv_avg at 𝜏 and cm(Φ𝑖 ) at 𝜏low (Op7). 16: Verify checks all per-round polynomial identities, PCS opening proofs, Op1/Op7 final-point equalities, and accepts iff all checks pass.

Proof sketch. The proof is a Hoeffding-style concentration argument over the 𝐿 independent per-table estimators. Each per-table bucket-collision count contributes a bounded-variance, independent random variable under the hash-family randomness; averaging over 𝐿 tables yields sub-Gaussian tails with rate 𝐿 −1 . A union bound across training points and a standard rank-stability argument (the rank function is 1-Lipschitz in sample-wise Shapley-value perturbations up to ties) converts the per-point concentration into the stated rank-difference bound. The explicit constant tracks 𝐾 and 𝑑 through the hash-family bias; see below for the variance-saturation refinement that replaces the Hoeffding bound with an 𝑂 (1)-in-𝑁 estimate.

B.5

Parameter Selection: Variance-Saturation Derivation

Hoeffding baseline for 𝐿. A direct Hoeffding bound on the pertable estimator yields 𝐿 = 𝑂 (log(𝑁 /𝛿)/𝜀 2 ) tables to achieve 𝜀accurate Shapley values with probability at least 1 − 𝛿. This is the bound underlying Theorem 1. Variance-saturation refinement. The Hoeffding bound is loose because the per-table estimator variance saturates once 𝐿 exceeds

Algorithm 4 Full ZK-LSH-Shapley protocol with per-module sumchecks (detailed version of Algorithm 2). (𝑘 )

Public input: public parameters pp, projection vectors {𝑟 ℓ }, perprovider data commitments {cm(𝐷𝑖 ) }, validation-set commitment cm(𝐷 val ), hash parameters (𝐿, 𝐾 ). Witness: per-provider data shards {𝐷𝑖 }, validation set 𝐷 val . Auxiliary input: bucket histograms cnt, cnt_c_tr, cnt_c_te; persample lookups 𝑚, b𝑚 b𝑐 , b 𝑡𝑐 ; weight oracles 𝑊 , 𝑒, 𝐷 inv , wt_num; label indicators 𝑦ind , 𝑦test_ind ; aggregates sv_sum, sv_avg; conditional PCA witnesses 𝑥 raw , 𝑉pca and remainders. Output: proof 𝜋 certifying sv_avg = LSH-Shapley(𝐷, 𝐷 val ). 1: Prover commits the feature MLEs 𝑥f f tr , 𝑥 te (and 𝑥 raw , 𝑉pca , remainders if

PCA enabled).

2: Prover commits hashing-module oracles sign, abs_dp, dp (and ZK-PCA

remainder oracles if PCA enabled). 3: Prover and verifier run the hashing-module sumchecks (sign-boolean,

sign-range lookup, dot-product binding for both training and validation), and the ZK-PCA sumchecks if PCA is enabled. 4: Prover commits the bucket-histogram oracles cnt, cnt_c_tr, cnt_c_te, the per-sample lookups 𝑚, b𝑚 b𝑐 , b 𝑡𝑐 , and the per-class label indicators 𝑦ind , 𝑦test_ind . 5: Prover and verifier run the histogram-consistency sumchecks. 6: Prover and verifier run the lookup-consistency sumchecks. 7: Prover commits the weight oracles 𝑊 , 𝑒, 𝐷 inv , wt_num and the aggregates sv_sum, sv_avg. 8: Prover and verifier run the weight-identity sumchecks (edge case, interior case, edge-flag boolean, denominator-inverse structural), the table-aggregation sumcheck, and the normalization sumcheck. 9: Prover and verifier run the input-side reconstruction sumcheck binding 𝑥f tr to {cm(𝐷𝑖 ) }, and the output-side reconstruction sumcheck binding cm(sv_avg) to {cm(Φ𝑖 ) }. 10: Prover sends PCS openings at all sumcheck challenge points; verifier replays the round-by-round identities and the closing equality at each challenge. 11: Each provider runs three local checks (input binding, output binding, transcript correctness) on the per-provider slice they verify. 12: In the deployed implementation, the modules sharing a sum domain col-

lapse into five batched sumcheck instances via random linear combination; see §5.1 and Appendix B.2.

the effective support of the bucket-collision distribution. Tracking the variance of 𝜙 ± directly — using the bounded-variance structure of the closed-form weights — yields a refined design rule 𝐿 ∗ = 𝑂 (1) under fixed (𝜀, 𝛿, 𝐾); empirically 𝐿 = 16 suffices across all benchmark datasets. The constant-in-𝑁 scaling is what makes LSHShapley ZK-feasible at marketplace scale: the prover’s Layer-1 work scales linearly in 𝐿, so a log 𝑁 factor in 𝐿 would reintroduce a 𝑁 log 𝑁 term that the histogram reformulation was designed to remove. Choice of 𝐾. 𝐾 controls bucket granularity: larger 𝐾 sharpens label discrimination (fewer spurious collisions between label classes), but the number of buckets 𝑀 = 2𝐾 drives Layer-2 lookup work (§4.2.3) and drives the sign-bit opening count in Phase 3. We pick the largest 𝐾 the ZK budget tolerates subject to a quality lower bound (rankcorrelation against exact KNN-Shapley on a held-out validation slice); our reference (𝐿, 𝐾) = (16, 10) configuration balances these constraints across the 12-dataset benchmark suite.

ZK-Value : A Practical Zero-Knowledge System for Verifiable Data Valuation

B.6

Super-Oracle Batching: Soundness Proof

This subsection gives the full proof of the super-oracle batching soundness claim deferred from §5.1. 𝑄 −1 Setup recap. Let {𝑓 𝑗 } 𝑗=0 be a family of multilinear sub-oracles on 𝑛 {0, 1} obtained by fixing one index axis of a parent tensor, with 𝑄 padded to a power of two. The prover commits the super-oracle 𝐹 : {0, 1}log 𝑄+𝑛 → FEF defined by 𝐹 ( 𝑗, 𝑥) := 𝑓 𝑗 (𝑥) and extended multilinearly. At a common upstream evaluation point 𝑥 ★ ∈ F𝑛EF already fixed by the parent sumcheck, the verifier samples a fresh log 𝑄 challenge 𝑟 ∈ FEF , requests the single PCS opening 𝐹 (𝑟, 𝑥 ★), and accepts the prover-supplied values 𝑣 0, . . . , 𝑣𝑄 −1 iff (3) holds. Claim. For any prover P ★ and any choice of values {𝑣 𝑗 }, the probability over 𝑟 that P ★ passes the equality check 𝐹 (𝑟, 𝑥 ★) = Í ★ 𝑗 eq(𝑟, 𝑗)·𝑣 𝑗 while having some 𝑣 𝑗 ★ ≠ 𝑓 𝑗 ★ (𝑥 ) is at most log 𝑄/|FEF |. Proof. Define the residual polynomial ∑︁ 𝑔(𝑟 ) := 𝐹 (𝑟, 𝑥 ★) − eq(𝑟, 𝑗) · 𝑣 𝑗 . 𝑗 ∈ {0,1} log 𝑄

Both terms are multilinear in 𝑟 of total degree at most log 𝑄. By Í multilinear interpolation, 𝐹 (𝑟, 𝑥 ★) = 𝑗 eq(𝑟, 𝑗) · 𝑓 𝑗 (𝑥 ★) for every Í 𝑟 , so 𝑔(𝑟 ) = 𝑗 eq(𝑟, 𝑗) · (𝑓 𝑗 (𝑥 ★) − 𝑣 𝑗 ). If 𝑣 𝑗 ★ ≠ 𝑓 𝑗 ★ (𝑥 ★) for some 𝑗 ★, then evaluating at 𝑟 = 𝑗 ★ gives 𝑔( 𝑗 ★) = 𝑓 𝑗 ★ (𝑥 ★) − 𝑣 𝑗 ★ ≠ 0, so 𝑔 . 0. By the Schwartz–Zippel lemma over FEF , Pr𝑟 ←Flog 𝑄 [𝑔(𝑟 ) = EF

0] ≤ log 𝑄/|FEF |. Composition with the parent sumcheck. The verifier plugs the recovered {𝑣 𝑗 } into the parent sumcheck’s closing identity exactly as in the unbatched protocol; under the super-oracle binding above, the parent sumcheck inherits its pre-existing soundness error. Each of the three families (sign, cnt_c_tr, {𝑚 b𝑐 , b 𝑡𝑐 }) is packed into a separate super-oracle, and their soundness errors add by a union bound. With log 𝑄 ≤ log(2𝐶 + 2) + 1 ≤ 5 and |FEF | = 264 − 232 + 1 ≈ 264 , the per-family contribution is below 2−59 , dominated by the parent sumcheck and PCS-binding terms. Endpoint correctness. The single PCS opening 𝐹 (𝑟, 𝑥 ★) binds the prover to the unique multilinear extension 𝐹 that agrees with the committed sub-oracle slices on {0, 1}log 𝑄+𝑛 . Schwartz–Zippel binding therefore reaches all the way to the underlying {𝑓 𝑗 } rather than only to a prover-chosen extension, completing the chain from the PCS-binding assumption to per-slice equality 𝑣 𝑗 = 𝑓 𝑗 (𝑥 ★). □

B.7

Op7 Selective-Disclosure: Full Reconstruction Sumcheck

Op1 input-side mirror. Op1 is structurally identical to Op7 but anchors the input end of the binding chain via the training-data oracle 𝑥f tr over the augmented (log 𝑁 + log 𝑑) cube, using per-provider oracle 𝐷𝑖 . The identity proved is 𝑥f tr (ℎ tr , ℎ𝑑 ) =

𝑚 ∑︁

eq(ℎ tr,high, bin(𝑖)) · 𝐷𝑖 (ℎ tr,low, ℎ𝑑 ),

𝑖=1

reduced by a Fiat–Shamir sumcheck to one PCS opening of 𝑥f tr at 𝜏1 plus 𝑚 openings of 𝐷𝑖 at 𝜏1,low . Together Op1 + middle sumchecks (§4.2.2) + Op7 form the end-to-end binding chain 𝐷𝑖 → cm(𝐷𝑖 ) → cm(f 𝑥 tr ) → · · · → cm(sv_avg) → cm(Φ𝑖 ) → sv_avg |𝑆 ; falsifying 𝑖 any link forces a PCS forgery, infeasible under PCS binding.

Three-check provider verification. Provider 𝑉𝑖 executes three local checks that together close the five-attack surface (data substitution, misplacement, intermediate-computation corruption, fabricated values, cross-provider attribution). • Check A — input binding. Recompute cm(𝐷𝑖 ) locally from the raw provider data (one Brakedown encoding + Merkle hashing over 𝑁 /𝑚 ·𝑑 elements) and match the value published in the proof transcript. • Check B — output binding. From the 𝑁 /𝑚 received Shapley values, reconstruct the MLE Φ𝑖 over log(𝑁 /𝑚) variables, recompute cm(Φ𝑖 ), and match the proof. • Check C — computation correctness. Verify the full transcript: Op1, all sumchecks of §4.2.2, Op7. Binding-chain detail. A malicious prover who substitutes provider 𝑖’s data fails Check A (the committed cm(𝐷𝑖 ) does not match); a prover who tampers with intermediate computation fails Check C (a middle-sumcheck identity rejects); a prover who fabricates scores fails Check B (the reconstructed cm(Φ𝑖 ) does not match the Op7 output-endpoint commitment). Cross-provider attribution attacks — swapping scores across providers — fail Check B at the defrauded provider and fail Check A at any provider whose slice was moved. The soundness argument composes: under the PCS-binding assumption, the probability that all three checks accept on a forged witness is bounded by the union of the per-module soundness errors plus the PCS-binding error, which is ≤ 2 log 𝑁 /|FEF | plus a negligible PCS term. Per-provider opening cost. Op1 + Op7 together add 2𝑚 commits (one cm(𝐷𝑖 ) and one cm(Φ𝑖 ) per provider), two degree-2 sumchecks of length log 𝑁 , and 2(𝑚 +1) PCS openings: two endpoint openings cm(f 𝑥 tr ) at 𝜏1 and cm(sv_avg) at 𝜏 (amortized across all providers), plus 𝑚 provider-side openings each of cm(𝐷𝑖 ) at 𝜏1,low and cm(Φ𝑖 ) at 𝜏low . The PCS openings are the dominant per-provider cost; §6 measures the end-to-end wall-clock overhead. Soundness and privacy. Soundness. A malicious prover committing incorrect sub-polynomials is caught with probability ≥ 1 − 2 log 𝑁 /|FEF | since both endpoints are bound to PCS openings. Privacy. Each provider’s PCS opening reveals a single random linear combination of the provider’s 𝑁 /𝑚 values (negligible for 𝑁 /𝑚 ≫ 1). The sumcheck is not formally zero-knowledge; masking extensions achieve formal ZK at one extra commitment (Future Work, §8).

B.8

ZK-LSH-Shapley Soundness Chain and Per-Sumcheck Cost Table

This appendix expands the soundness sketch and complexity summary of §4.2.3 with a per-link reduction and a per-sumcheck cost table. Per-link reduction. If the training-histogram sumcheck accepts, cnt agrees with the committed per-sample bucket assignments under 𝐵 ℓ ; the per-class training-histogram and validation-histogram sumchecks anchor cnt_c_tr and cnt_c_te respectively, folding the class dimension via a single random 𝑟𝑐 challenge. The bucketsize lookup sumcheck then forces 𝑚 b to match cnt at every sample’s bucket, the same-class lookup sumcheck does the same for 𝑚 b𝑐 ↔ cnt_c_tr, and the validation-class lookup sumcheck for b 𝑡𝑐 ↔ cnt_c_te. The match-count advice sumcheck binds 𝑡 match to b 𝑡𝑐 . With (𝑚, b𝑚 b𝑐 , b 𝑡𝑐 , 𝑡 match, 𝐻𝑀 ) thus anchored, the edge-case and

Zhaoyu Wang, Pingchuan Ma, Zhantong Xue, Yuguang Zhou, Qixin Zhang, Xiaoqin Zhang, and Shuai Wang

Table 9: Per-sumcheck cost table for ZK-LSH-Shapley. Domain shows the sumcheck variables; degree is the maximal round polynomial degree; prover work is the asymptotic permodule cost. Sumcheck

Domain

Degree

Prover work

Training-histogram Per-class training-histogram Per-class validation-histogram Bucket-size lookup Same-class lookup Validation-class lookup Squared-count auxiliary Match-count advice Edge-case weight Interior weight Table-aggregation

log 𝐿 + log 𝑁 log 𝐿 + log 𝑁 log 𝐿 + log𝑇 log 𝐿 + log 𝑁 log 𝐿 + log 𝑁 log 𝐿 + log 𝑁 log 𝐿 + log 𝑀 log 𝐿 + log 𝑁 log 𝐿 + log 𝑁 log 𝐿 + log 𝑁 log 𝐿 + log 𝑁

𝐾 +1 𝐾 +2 𝐾 +2 𝐾 +2 𝐾 +2 𝐾 +2 3 𝐾 +1 3 3 2

𝑂 (𝐿 · 𝑁 · 𝐾 2 ) 𝑂 (𝐿 · 𝑁 · 𝐾 2 ) 𝑂 (𝐿 · 𝑇 · 𝐾 2 ) 𝑂 (𝐿 · 𝑁 ) 𝑂 (𝐿 · 𝑁 ) 𝑂 (𝐿 · 𝑁 ) 𝑂 (𝐿 · 𝑀 ) 𝑂 (𝐿 · 𝑁 ) 𝑂 (𝐿 · 𝑁 ) 𝑂 (𝐿 · 𝑁 ) 𝑂 (𝐿 · 𝑁 )

Dot-product sign (ancillary) PCA-projection (conditional)

log 𝑑 log 𝑑 raw + log 𝑑 pca

2 2

𝑂 (𝐿 · 𝐾 · (𝑁 + 𝑇 ) · 𝑑 ) 𝑂 (𝑁 · 𝑑 raw · 𝑑 pca )

interior weight sumchecks together force 𝑊 to equal the closedform weight identity 𝑊 = 𝜙 ± (𝑚, b𝑚 b𝑐 , 𝐻𝑚b ) on the 𝑀 ∈ {0, 1} and 𝑀 ≥ 2 regions respectively; the table-aggregation sumcheck aggregates 𝑊 across the 𝐿 tables into sv_sum, and normalization by 𝐿 ·𝑇 yields sv_avg. The harmonic oracle 𝐻𝑀 is checked compositionally: a forged 𝐻𝑀 produces a wrong 𝑊 via the weight sumchecks, hence a wrong sv_avg via the table-aggregation sumcheck, which fails Op7’s reconstruction Check B (each provider’s Check B locally recomputes cm(Φ𝑖 ) from the values they receive, so a mismatch is detected without a dedicated module for 𝐻𝑀 ). Per-sumcheck cost table. Table 9 lists each of the eleven bucketspecific sumchecks and the ancillary sumchecks together with their domain, degree, and asymptotic prover work. The total soundness Í error sits below 2−50 at typical parameters because modules deg · log(domain)/|𝐹𝑖𝑔.| remains negligible against the Goldilocks field size |𝐹𝑖𝑔.| = 264 − 232 + 1 ≈ 264 , with PCS binding contributing a similarly negligible additive term. The Layer-1 row dominates prover work; Layer-2 and Layer-3 rows are sub-dominant by a factor of 𝐾 in the typical regime, and the ancillary rows confine 𝑑 and 𝑑 raw to the preamble as claimed in the body.

C

SPARSITY-AWARE SUMCHECK: PSEUDOCODE AND SOUNDNESS

This appendix expands the sparsity-aware sumcheck path of §5.2: the per-round prover pseudocode, the support-superset invariant that controls correctness, and the soundness argument that the sparse path produces round messages identical to the dense path. Notation. For a multilinear factor 𝑓 : {0, 1}𝑛 → F, let supp(𝑓 ) = {𝑥 ∈ {0, 1}𝑛 : 𝑓 (𝑥) ≠ 0} be its true support and let sš upp(𝑓 ) ⊇ supp(𝑓 ) denote the prover-tracked support mask — a superset that the prover maintains explicitly. After fixing the first 𝑟 variables to challenges (𝜌 1, . . . , 𝜌𝑟 ) ∈ F𝑟EF , write 𝑓 (𝑟 ) : {0, 1}𝑛−𝑟 → FEF for the partially-folded factor; the corresponding mask sš upp(𝑓 (𝑟 ) ) ⊆ {0, 1}𝑛−𝑟 is obtained by projecting away the 𝑟 folded coordinates (a fold step preserves the superset property because folding cannot create new nonzero cells beyond the projection of the previous mask).

Algorithm 5 Sparsity-aware histogram-sumcheck round (one factor; multi-factor case intersects masks). 1: Input. Round index 𝑟 ; partially folded factor 𝑓 (𝑟 −1) ; tracked mask (𝑟 −1)

sš upp( 𝑓 (𝑟 −1) ) ⊆ {0, 1}𝑛−𝑟 +1 ; product factors {𝑔𝑡 }𝑡 that multiply 𝑓 in the round message; degree bound 𝐷. 2: Output. Univariate round-𝑟 message ℎ𝑟 ∈ FEF [𝑋 ] of degree ≤ 𝐷. 3: ℎ𝑟 ← 0 4: for each 𝑧 ∈ sš upp( 𝑓 (𝑟 −1) ) with 𝑧 1 = 0 do 5: ⊲ The first coordinate is the round-𝑟 variable. 6: Let 𝑧 ′ = (𝑧 2 , . . . , 𝑧𝑛−𝑟 +1 ); for each 𝑏 ∈ {0, 1} and each evaluation

point 𝑋 ∈ {0, 1, . . . , 𝐷 }: Î (𝑟 −1) ℎ𝑟 (𝑋 ) += 𝑓 (𝑟 −1) (𝑋 , 𝑧 ′ ) · 𝑡 𝑔𝑡 (𝑋 , 𝑧 ′ ) if (𝑋 , 𝑧 ′ ) ∈ sš upp( 𝑓 (𝑟 −1) ) or 𝑋 ∈ FEF \ {0, 1}. 8: end for 9: Send ℎ𝑟 . Receive challenge 𝜌𝑟 ∈ FEF from the verifier. 10: 𝑓 (𝑟 ) (·) ← (1 − 𝜌𝑟 ) · 𝑓 (𝑟 −1) (0, ·) + 𝜌𝑟 · 𝑓 (𝑟 −1) (1, ·) upp( 𝑓 (𝑟 −1) ) or (1, 𝑧 ′ ) ∈ 11: sš upp( 𝑓 (𝑟 ) ) ← {𝑧 ′ : (0, 𝑧 ′ ) ∈ sš sš upp( 𝑓 (𝑟 −1) ) } 12: ⊲ Fold mask one variable ahead of the table. 13: if |š supp( 𝑓 (𝑟 ) ) | > 𝜃 · 2𝑛−𝑟 then 14: Switch 𝑓 back to the dense path for remaining rounds. ⊲ Crossover threshold 𝜃 chosen so mask bookkeeping no longer pays for the zeros it skips. 15: end if 16: return ℎ𝑟 , updated 𝑓 (𝑟 ) , sš upp( 𝑓 (𝑟 ) ). 7:

Support-superset invariant. The pseudocode of Algorithm 5 maintains the following invariant after every round 𝑟 :

supp 𝑓 (𝑟 ) ⊆ sš upp 𝑓 (𝑟 ) for every sparse factor 𝑓 . This is the only structural property required for soundness: cells outside sš upp are guaranteed to evaluate to zero, so skipping them cannot remove any nonzero contribution to the round message. Multi-factor masks. When the round message contains a product Î 𝑡 𝑔𝑡 · 𝑓 in which several factors are sparse, the prover iterates Ñ upp(𝑔𝑡(𝑟 −1) ) ∩ sš upp(𝑓 (𝑟 −1) ). The intersection inherits the over 𝑡 sš superset property factor-by-factor: any 𝑧 outside the intersection lies outside at least one sš upp, hence outside the corresponding supp, and the product is zero at 𝑧. Soundness. The dense-path round-𝑟 message is ∑︁ Ö ℎ𝑟dense (𝑋 ) = 𝑓 (𝑟 −1) (𝑋, 𝑧) 𝑔𝑡(𝑟 −1) (𝑋, 𝑧), 𝑧 ∈ {0,1}𝑛−𝑟

𝑡

and the sparse-path message restricts the outer sum to sš upp(𝑓 (𝑟 −1) )∩ Ñ (𝑟 −1) upp(𝑔𝑡 ). By the support-superset invariant, every 𝑧 ex𝑡 sš cluded from the intersection has at least one factor evaluating to zero at (𝑋, 𝑧) on 𝑋 ∈ {0, 1}; for 𝑋 ∉ {0, 1} the verifier treats the round message as a degree-𝐷 polynomial that is fully determined by its values at 𝐷 + 1 Boolean / small-integer points, so the sparse and dense polynomials agree at every evaluation point and therefore as sparse polynomials. Hence ℎ𝑟 ≡ ℎ𝑟dense as univariate polynomials over FEF , and the sparse path emits the same transcript as the dense path. The verifier’s sumcheck soundness is therefore inherited verbatim from the unmodified ZK-LSH-Shapley protocol of §4.2, with no additional error term. □

ZK-Value : A Practical Zero-Knowledge System for Verifiable Data Valuation

Crossover safety. The threshold 𝜃 that triggers a fall-back to the dense path is a prover-side bookkeeping decision: the verifier observes only the round message ℎ𝑟 , which is identical on both

paths, so any choice of 𝜃 preserves soundness. The threshold is tuned for prover-side performance only.