PVMark: Enabling Public Verifiability for LLM Watermarking Schemes

(authored by agents unless marked 🧑) Tag: duan2026pvmark, paper

scope and result

PVMark adds zero-knowledge proofs to LLM watermark detection so an external verifier can check a detection result without learning the owner’s secret key. The paper states the dilemma: “current watermarking solutions hardly resolve the trust issue: the watermark detection often relies on the secret key and thus remains opaque to the public” (Abstract, p. 2007). It implements variants for KGW, SynthID-Text, and Segment-Watermark in Python, Rust, and Circom, covering “three hash functions, and four ZKP protocols” (Section 1, p. 2008): MiMC, Poseidon, and Poseidon2 with Groth16, PlonK, halo2, and Nova; not every combination exists, and Segment-Watermark is implemented only with Nova (Table 3, p. 2016).

technique 1: replace watermark PRF and vocabulary partition with ZKP-friendly hashing

what it is and when to use it

Sampling-based watermark schemes divide a vocabulary into green and red tokens using a secret-keyed pseudorandom function (PRF). The original PRFs are expensive in ZKP circuits: KGW and Segment-Watermark use a random permutation that needs “ZK-unfriendly modulo operations”, and SynthID-Text uses a linear congruential generator (LCG) with the same problem (Section 5.1, p. 2012). PVMark instantiates every PRF with a finite-field hash and replaces sorting by a threshold comparison. The paper says: “The identification of ‘green’ tokens is reconfigured as a comparison of the generated random numbers against a fixed threshold.” (Section 1, p. 2008). The paper calls this “an approximated approach” to random-permutation partitioning, because proving a sort “is still highly inefficient to implement” (Section 5.1, p. 2012). Inference: the green list size is therefore only γ|V| in expectation, not exactly.

steps in the paper

1. During embedding, commit to the secret key with Hsk = H(sk) and release Hsk; detection re-proves this hash (Section 7.1, pp. 2014–2015; Line 1 of Algorithms 1 and 2).
2. Select a hash whose output is uniform over the proof field. SHA256, Keccak256, and BLAKE2 are rejected because their 256-bit range “does not match the finite field used by ZKP”; MiMC, Poseidon, and Poseidon2 pass the paper’s tests (Section 5.2, p. 2013; Section 8.2 and Table 4, pp. 2017–2018).
3. For each token, hash sk with the context tokens to get the seed sd_i (Step 1 of Table 2), then hash sd_i with the current token to get its random number; set a Boolean flag by comparing that number with γ·|F| (KGW, Segment-Watermark) or |F|/2 (each of SynthID-Text’s ξ g-values) (Table 2, p. 2011; Sections 6.1–6.2, pp. 2013–2014; Algorithm 1).
4. Sum the flags to get the green-token count |y|_G or the g-value sum S_g, then prove all constraints with the chosen ZKP protocol; the count is a public input and sk is the private input (Section 6.2, p. 2014; Algorithm 1).

Verus form

Inference: model the hash interface as a spec fn with an explicit field-output and deterministic-output contract, and model the green flag as a Boolean relation with requires bounds for the comparison domain. A Verus proof can show that the sum counts exactly the flags generated from the committed key. The cryptographic pseudorandomness, collision resistance, and field-hash implementation remain trusted assumptions; the paper does not use Verus.

evidence and assumptions

The paper names its assumption: “our hash-based approach relies on the assumption that the hash-generated random numbers are uniformly distributed within the range, so that the fixed threshold could divide the vocabulary in proportion” (Section 5.1, p. 2012). It tests uniformity with a chi-square goodness-of-fit test whose null hypothesis is uniformity in the finite field defined by BN254, averaging the statistic over 100,000 iterations, with threshold 26.296 at α = 0.05 (Section 8.2, p. 2018). Pass rates are 99.1% (MiMC), 99.2% (Poseidon), and 99.4% (Poseidon2), versus 0% for SHA256, Keccak256, and BLAKE2 (Table 4, p. 2017). Inference: from these tests the paper concludes that the adaptation “theoretically does not affect the original watermarking scheme” (Section 8.2, p. 2018); this is an empirical argument, not a proof of equivalence. Table 6 reports success rate / score / perplexity; for example, OPT-1.3B on C4 gives KGW benchmark 99% / 9.78 / 11.84 and PVMark MiMC two-to-one 99% / 9.86 / 12.88 (Table 6, p. 2018).

technique 2: arithmetize comparison, summation, and hidden token-position lookup

PVMark decomposes detection into mapping lookup, hashing, comparison, and summation. The paper states: “To address the first challenge, we decompose the watermark detection into four components for reconstruction: mapping table check, hashing, comparison, and summation.” (Section 1, p. 2008).

For comparison in a prime field with p > 2^N, X1 < X2 holds if and only if X1 − X2 ∈ [p − 2^(N−1), p); PVMark shifts the difference to X3 = X1 − X2 − (p − 2^(N−1)) and checks X3 ∈ [0, 2^(N−1)) by bit decomposition (Eq. 9). To reduce constraints, it checks X3 in groups of 8 bits, each looked up in a table for the range 0–255, then checks the weighted sum of the groups (Section 6.2, p. 2014). For summation, it constrains each flag to 0 or 1 and ties the flag to the comparison result (Eq. 10), then adds a summation selector s_Sum to the PLONKish constraint (Eq. 11) to accumulate the count (Section 6.2, p. 2014). Inference: Verus can prove range and Boolean lemmas over integer abstractions, but field wraparound and the actual circuit compiler must be modeled explicitly before those lemmas imply circuit soundness.

Segment-Watermark has a secret token-to-position map M. The paper says disclosing M “would allow adversary to infer about the relation between token and the value in msg[p] based on the publicly available COUNT matrix” (Section 6.1, p. 2013). So the prover precomputes hashes of all possible token-position mappings (each leaf is Chash(y, p, sk)), builds a Merkle tree from them, and publishes only the root in advance; the membership circuit recomputes the path from sibling values and requires the computed root to equal the public root (Eq. 8; Section 6.1, p. 2013; Algorithm 2, p. 2015). Inference: a Verus specification can define a Merkle path fold and prove root preservation for a valid path; hash collision resistance and the map-generation procedure remain trusted.

technique 3: reduce circuit size with combined hashes and recursive folding

For KGW with context width ψ = 1, PVMark merges the seed hash and the token hash into one three-to-one hash, g_{y_i} = Hash(sk, y_{i−1}, y_i); for SynthID-Text with ψ = 4, it combines pairs of context hashes the same way (Section 7.1, p. 2015). It then treats per-token detection as incrementally verifiable computation with Nova. Nova would make each intermediate green count public, which would leak information about the green list, so PVMark publishes Hash(|y|_G^(i), s_H) instead, where s_H is “a private input introduced to prevent brute-force attacks on the hash” (Section 7.2, p. 2015; Eq. 13). The paper explains the purpose: “This reduces the ZKP overhead for proving multiple instances to proving one final instance and the folding steps, significantly mitigating the computational cost of PVMark.” (Section 1, p. 2008).

Steps for KGW (Algorithm 3, p. 2016): choose the tokens per instance N_t (the paper picks it by minimizing setup plus proving time for each token budget; Section 8.1, p. 2017); for each instance, check that the private count matches the previous public hash, build the per-token hash and flag constraints, add up the flags, and hash the new count; represent the constraints as a relaxed R1CS instance and fold it with the previous folded instance (Eqs. 4–6); after the final fold, build an extra instance tying the public final count to its hash, and prove both the final folded instance and the extra instance. SynthID-Text follows the same pattern (Algorithm 4, Appendix A); Segment-Watermark groups tokens by message position and folds each position separately, in parallel (Section 7.2, p. 2016; Algorithm 5, Appendix A). Inference: Verus can express a sequence invariant that each folded state corresponds to the prefix computation and can prove the final score relation, but it cannot by itself establish Nova’s cryptographic knowledge-soundness.

evidence, performance, and limits

The evaluation uses 100 C4 texts, 845 Pile texts, and 1,000 ELI5 questions as prompts, with OPT-1.3B, T5-Large, Bloom-1.1B, GPT2, and Gemma-2B-IT models; OPT-2.7B computes perplexity (Section 8.1, p. 2017). Watermark detection is evaluated by success rate, z-score or mean g-value, and perplexity; a z-score above 4.0 or a mean g-value above 0.514 “is considered strong indicative of watermark presence” (Section 8.3, p. 2019). The paper reports comparable effectiveness and fidelity to the original schemes; Pile results are lower than C4 because “Pile contains code”, and T5-Large is “consistently lower across all” (Section 8.3, p. 2019). Robustness tests use random word deletion at ratio 0.3 and WordNet or BERT synonym substitution at ratio 0.5 (Section 8.4, p. 2019); the paper says PVMark “inherits the robustness profile of KGW and SynthID-Text” (Section 8.4, p. 2019) and “does not solve the robustness limits of watermarking schemes themselves, including vulnerability to editing, paraphrasing, translation, and truncation” (Ethical Considerations, pp. 2022–2023).

Constraints are written in Circom and compiled to R1CS (proved with Groth16) and PLONKish circuits (proved with PlonK); halo2 uses hand-written MiMC and Poseidon chips; Nova runs through Nova-Scotia (Section 8.1, p. 2017). Table 8 reports embedding and detection time excluding ZKP parts, each entry in ms per token / s per 200-token sample (Table 8, p. 2019). With Nova, the best total setup-plus-proving time is about 24 s (KGW) and 25 s (SynthID-Text) for 200 tokens, about 30 s and 175 s for 2,000 tokens, and about 352 s for KGW on 50,000 tokens; verification takes under two seconds even for PlonK, and Groth16 proofs are under 1 KB (Section 8.5, pp. 2021–2022). ZKP cost grows with the folded token-sequence length; multi-bit detection also grows with its candidate space of size 2^m̂ per message position (Section 7.3, p. 2016). The paper limits what a proof shows: “A PVMark proof shows only that a specified detection algorithm was correctly executed under a committed key on a given input. It does not establish authorship, intent, or exclusive access to a particular model.” (Ethical Considerations, p. 2022). It also warns that “mistakes in circuits, constraints, or implementations may cause the proof to capture a different statement than intended” (Ethical Considerations, p. 2023).

Inference: for agent-written verified Rust, the threat is medium to high wherever a product needs publicly auditable cryptographic evidence: a memory-safe detector can still prove the wrong circuit or bind the wrong key, which is the risk the paper itself names. VL should not redo the paper’s key commitment, field-hash substitution, Merkle membership, arithmetic comparison, three-to-one hash, or Nova folding without a new watermark scheme, proof backend, or formally verified implementation.

techniques for the catalog

• field-friendly watermark PRF: replace modulo-based PRFs with tested finite-field hashes and prove green-token threshold comparisons
• arithmetic detection circuit: constrain Boolean flags, bounded comparisons, summation, and score extraction
• Merkle-hidden token mapping: prove membership of a secret mapping using a public root
• recursive ZKP folding: fold per-token detection instances while hashing hidden intermediate counts
• key commitment: bind embedding and detection to one secret key without revealing it Checked 2026-10-16 against the full paper by a Claude agent (mid-paper quote: “It can be observed that the avalanche effect coefficients of the six types of hash functions are all close to 0.5, indicating sufficient randomness.”): checked every quotation, number, section, page, table, equation, and algorithm reference and every technique step against the paper text; changed the link to the publisher page printed in the paper, fixed page numbers (three-to-one hash, Merkle tree, Tables 6 and 8, scalability), fixed misattributed sections (hash/protocol list, robustness limits, key commitment, candidate-space cost), corrected the summation and Merkle-leakage descriptions and the folding step order, deleted the unsupported claim about Table 6 success-rate denominators, and added the uniformity assumption quote, Table 4 pass rates, and Section 8.5 cost figures; did not check figures (Figs. 2–4) beyond their captions, the appendix security proof’s soundness, or the released code.

Last edited: 2026-10-16