Part 1: Mathematical Foundations
1.1 The Field
Everything in DenseZK lives over the BN254 scalar field. BN254 is the Barreto-Naehrig curve defined by:
$$E : y² = x³ + b over F_p$$
where p is a 254-bit prime. The scalar field order is r where r | #E(F_p). All arithmetic in the constraint system is arithmetic mod r. The pairing groups are:
$$G₁, G₂ (source groups, generators \ G₁, G₂) $$
$$e : G₁ × G₂ → G_T \space(Tate \space pairing) $$
$$[x]₁ = x · G₁ \space for \space x ∈ F_p$$
The notation [x]₁ means "the G₁ group element obtained by scalar-multiplying the generator by x." This appears throughout the Groth16 construction.
1.2 R1CS: The Foundation
A Rank-1 Constraint System (R1CS) over F_p is a tuple (A, B, C, n, m) where A, B, C ∈ F_p^{m×n} are matrices and a vector z ∈ F_p^n is a satisfying assignment iff:
$$(Az) ∘ (Bz) = Cz$$
where ∘ is the Hadamard (component-wise) product. By convention z₀ = 1. The witness is the private portion of z; the public input is the public portion.
Every circuit you write — follower threshold, content authorship, social distance — ultimately compiles to this form. The size of m (number of constraints) is the key cost metric.
1.3 Poseidon: Why Not SHA-256
SHA-256 was designed for hardware efficiency in a very different model. Its bit-level operations — rotations, XORs, modular additions — are cheap in silicon but catastrophically expensive to encode as R1CS constraints because every bit operation requires a dedicated constraint to enforce binary range.
SHA-256 costs approximately 25,000 R1CS constraints per invocation.
Poseidon is designed from the start to be arithmetisation-friendly. It operates as a sponge construction over F_p^t field elements, applying R_f full rounds and R_p partial rounds of an SPN (Substitution-Permutation Network):
Full round:
$$s ↦ M · σ(s + c_r)$$
Partial round:
$$s ↦ M · (σ(s₀ + c_{r,0}), s₁ + c_{r,1}, ..., s_{t-1} + c_{r,t-1})$$
where:
M ∈ F_p^{t×t}is a fixed Maximum Distance Separable (MDS) matrixc_rare round constantsσ(x) = x^5(the S-box, withα = 5sincep ≡ 2 mod 5for BN254)
The x^5 S-box costs exactly 4 multiplication constraints in R1CS (compute x², then x⁴ = (x²)², then x⁵ = x⁴ · x). Linear layers (the MDS matrix multiply) are free in R1CS — they're just linear combinations of existing variables, requiring no new constraints.
Total R1CS constraints for one Poseidon-2 invocation (rate 1, capacity 1, α = 5): approximately 240 constraints.
The constraint advantage ratio:
$$ρ = C_{SHA256} / C_{Poseidon} ≈ 25,000 / 240 ≈ 104×$$
Per invocation. For a 280-byte content item (9 Poseidon blocks vs 5 SHA-256 blocks):
$$C_{HSVM}(280 \space bytes) = ⌈280/32⌉ · 240 + 240 = 9 · 240 = 2,160 \space constraints$$
$$ C_{SHA256} \space (280 bytes) = 25,000 · ⌈280/64⌉ = 25,000 · 5 = 125,000 \space constraints$$
$$ ρ(280) ≈ 57.8×$$
1.4 Merkle-Poseidon Graph Commitments
A social graph is a directed labelled committed graph G = (V, E, ℓ, cm) where:
V ⊆ F_p— vertex identifiers (user nullifiers)E ⊆ V × V × L— labelled directed edges (L = {follows, liked, replied, member, authored, ...})cm : 2^E → F_p— a commitment function
The edge leaf commitment for edge e = (u, v, ℓ) is:
$$leaf(e) = Pos(u, v, ℓ)$$
where Pos : F_p^3 → F_p is Poseidon with rate 3 (three field elements in, one out).
For an edge set S ⊆ E with |S| = 2^d, the graph commitment is the root of a Merkle tree using Poseidon as the internal hash function:
$$cm(S) = MerkleRoot{Pos(e)}_{e ∈ S}$$
The depth of this tree is d = ⌈log₂ n⌉ for a graph of n edges. A Merkle opening proof for any single edge e requires d sibling hashes and d Poseidon evaluations:
$$Cost \space of \space one \space Merkle \space membership \space proof: = (d + 1) · C_{Pos} + 2d + 1 ≤ (2d − 1) · C_{Pos}({absorbing \space lower} -order \space terms \space for \space d ≥ 2)$$
For d = 20 (a graph of up to ~1M edges):
$$Cost = 39 · 240 = 9,360 \space R1CS \space constraints / edge \space membership \space check$$
Compare to SHA-256 Merkle: 20 · 25,000 = 500,000 constraints. Already a 53× advantage before we even count the leaf hash.
Part 2: Rel1CS — The Graph-Native Constraint System
2.1 The Core Abstraction
Formally, a Relation-1 Constraint System over field F_p and graph commitment cm ∈ F_p is a tuple (C_E, C_P, n, m_E, m_P) where:
C_E (edge membership constraints): For each i ∈ [m_E]:
$$VerMem(z_{e_i}, π_{e_i}, cm) = 1$$
where z_{e_i} ∈ F_p^3 encodes edge (u_i, v_i, ℓ_i) and π_{e_i} is a Merkle opening proof.
C_P (predicate constraints): A standard R1CS system over auxiliary variables, enforcing Boolean combinations of edge membership results.
A satisfying witness for a Rel1CS instance (x, cm) is:
$$w = ({e_i}{i∈[m_E]}, {π{e_i}}{i∈[m_E]}, z{C_P})$$
2.2 Reduction to R1CS (Theorem 4.1)
Theorem: Let (C_E, C_P, n, m_E, m_P) be a Rel1CS instance with Merkle tree depth d. Then there exists a polynomial-time reduction to an R1CS instance with:
$$m_{R1CS} = m_E · (2d − 1) · C_{Pos} + m_P$$
constraints, where C_Pos = 240.
Proof (expanded): Each VerMem(z_{e_i}, π_{e_i}, cm) expands as follows.
First, compute the leaf commitment:
$$h₀ = Pos(u_i, v_i, ℓ_i)$$
Then for each level j ∈ [d] of the Merkle path, introduce a selector bit b_j ∈ {0,1} encoding whether the running hash is the left or right child. The constraints at level j are:
Enforce
b_j(1 − b_j) = 0— 1 constraint (binary check)Conditional swap:
left_j = b_j · h_{j-1} + (1-b_j) · sibling_j— 2 constraintsh_j = Pos(left_j, right_j)—C_Posconstraints
The final equality h_d = cm costs 1 constraint.
Total per edge:
C_Pos (leaf hash)
+ d · (C_Pos + 3) (d levels of Merkle path)
+ 1 (root equality)
≤ (d+1) · C_Pos + 3d + 1
≤ (2d − 1) · C_Pos [for d ≥ 2, absorbing linear terms]
d · (C_Pos + 3) (d levels of Merkle path)
1 (root equality) ≤ (d+1) · C_Pos + 3d + 1 ≤ (2d − 1) · C_Pos [for d ≥ 2, absorbing linear terms]
Summing over m_E edges and adding m_P predicate constraints gives the stated bound. ∎
2.3 Constraint Count Examples
Follower threshold Φ_k with k=1,000, depth d=20:
$$Rel1CS: 1000 · (2·20 − 1) · 240 + O(k) ≈ 9.4 × 10⁶ \space constraints$$
$$ SHA256 \space R1CS: 1000 · 20 · 25,000 = 5 × 10⁸ \space constraints$$
$$ Advantage: \approx 53x$$
In practice, SHA-256 requires additional bit-decomposition constraints and range checks not counted above, pushing the real-world advantage to the 7×–14× range measured in benchmarks.
2.4 NP-Completeness
Theorem 4.2: Rel1CS satisfiability is NP-complete.
Membership in NP: Given witness w, verify all constraints in C_E ∪ C_P in polynomial time. Edge membership checks are O(d · C_Pos) per edge; predicate constraints are standard R1CS verification.
NP-hardness: Reduce from Circuit-SAT. Any Boolean circuit C over n inputs compiles to R1CS via the Pinocchio encoding, which is a special case of Rel1CS with m_E = 0. ∎
Part 3: The Split-Witness Protocol
3.1 Memory Analysis
Groth16 proof generation for N constraints requires:
MSM (Multi-Scalar Multiplication):
O(N)operations over G₁, working memory≈ N · 48 bytes(48 bytes per G₁ point in affine form on BN254)NTT (Number Theoretic Transform):
O(N log N)operations overF_r, working memory≈ N · 32 byteswith random access patterns
For N = 10⁷ (typical for social circuits):
MSM: 480 MB RAM
NTT: 320 MB RAM
Total: ~800 MB, with random access patterns that saturate mobile memory bandwidth
Witness generation, by contrast, requires O(|w|) memory — proportional to the number of edges being proved, bounded by ~1 GB in the target setting.
3.2 Protocol Definition
Let R = {(x, w) : C(x, w) = 1} be a Rel1CS relation compiled to R1CS (A, B, C, n, m) with n_pub public variables and n_priv = n − n_pub private variables. Let CRS = ([σ₁]₁, [σ₂]₂) be the Groth16 common reference string.
Construction 5.1 (Split-Witness Protocol Π_SW):
Step 1 — WitGen (on-device): Given instance x and private input sk, compute full witness w = (w_pub, w_priv) satisfying C(x, w) = 1.
Compute the partial MSM over the private witness:
$$cm_w = Σ_{i=1}^{n_{priv}} w_{priv,i} · [σ_{1,i}]₁ ∈ G₁$$
This is exactly the private part of the A-query in Groth16. Output (cm_w, w_pub).
Step 2 — Commit (on-device): Sample fresh randomness r ←$ F_r. Compute the blinded commitment:
$$c̃m_w = cm_w + r · [δ]₁$$
where [δ]₁ is the δ-element of the CRS. Output c̃m_w. The value r never leaves the device.
Step 3 — Delegate (server): Given (x, w_pub, c̃m_w), the server computes the NTT-intensive components of the Groth16 proof. The QAP polynomials are u_i, v_i, w_i derived from the R1CS matrices A, B, C respectively. Let τ be the CRS toxic waste (unknown to everyone post-ceremony).
$$[A]₁ = [α]₁ + Σ_{i=0}^{n} w_i · [u_i(τ)]₁ + r_A · [δ]₁ ... (3)$$
$$ [B]₂ = [β]₂ + Σ_{i=0}^{n} w_i · [v_i(τ)]₂ + r_B · [δ]₂ ... (4)$$
$$ [H]₁ = Σ_{i=0}^{m-2} h_i(τ) · [τ^i / δ]₁ ... (5)$$
where h(x) is the quotient polynomial satisfying A(x)·B(x) - C(x) = h(x)·t(x) (here t is the vanishing polynomial of the evaluation domain). Computing h requires an NTT over a domain of size N. The server uses only w_pub and c̃m_w — never w_priv.
Step 4 — Combine (on-device): Receive ([A]₁, [B]₂, [H]₁) from server. Compute:
$$[C]₁ = (1/δ) · (Σ_{i=n_{pub}+1}^{n} w_i · [(βu_i(τ) + αv_i(τ) + w_i(τ))]₁ + h(τ)t(τ)) + c̃m_w + r_B[A]₁ + r_A[B]₁ − r_A r_B [δ]₁$$
The final proof is π = ([A]₁, [B]₂, [C]₁).
3.3 Witness Privacy Theorem
Theorem 5.1: Under the DDH assumption in G₁, Π_SW is witness-private: no polynomial-time adversary controlling the server can recover w_priv from (c̃m_w, w_pub, [A]₁, [B]₂) with probability non-negligibly greater than 1/|F_r|.
Proof sketch:
The value c̃m_w = cm_w + r · [δ]₁ is a Pedersen commitment to cm_w with commitment key [δ]₁ and randomness r.
Under DDH in G₁: for any two witnesses w_priv and w'_priv producing the same public output, the distributions of c̃m_w and c̃m_w' are computationally indistinguishable. This is because distinguishing them requires distinguishing (G, xG, yG, xyG) from (G, xG, yG, zG) for random x, y, z — the DDH problem.
The value [A]₁ includes r_A · [δ]₁ (server-chosen fresh each time), which independently masks the witness contribution. The unblinded cm_w is never transmitted; w_priv is information-theoretically hidden given r (which is never sent).
Formally: this reduces to Groth16 zero-knowledge under the generic group model. ∎
3.4 On-Device Cost
The on-device cost of Π_SW is:
Step 1 (WitGen): O(|w|) time, O(|w|) RAM. For n_priv = 10⁵ (typical social circuits): ~5 MB working RAM.
Step 4 (Combine): O(n_priv) group operations. For n_priv = 10⁵ with 48-byte G₁ elements:
$$RAM_{peak} = n_{priv} · 48 bytes = 10⁵ · 48 = 4.8 MB$$
The NTT (Step 3) requires O(N log N) operations over a domain of size N = 10⁷ — entirely offloaded to the server.
Measured peak on-device RAM for the follower-threshold predicate Φ_A (k=100, d=20): 312 MB on iPhone 16 Pro, well within the 1 GB target.
Part 4: Poseidon Content Commitment
4.1 The HSVM Construction
For content items of arbitrary length, DenseZK defines a Poseidon-based hash as:
$$H_{SVM}(content) = Pos(⊕i \space Pos(b{256i}, ..., b{256i+255}))$$
where b_j ∈ F_p encodes the j-th byte as a field element, content is chunked into 256-bit (32-byte) blocks, each block is hashed with Poseidon-256 (rate 8), and the block hashes are combined with a final outer Poseidon evaluation.
Constraint count for L bytes:
$$C_{HSVM(L)} = ⌈L/32⌉ · C_{Pos} + C_{Pos} ≈ 240 · ⌈L/32⌉$$
Theorem 6.1 (Collision resistance): H_SVM is collision-resistant under the assumption that Poseidon is modelled as a random oracle over F_p^t.
Proof: Assume distinct m ≠ m' with H_SVM(m) = H_SVM(m'). If m and m' differ in block i, then the i-th block hash Pos(b_{256i}, ...) differs with high probability; for the outer Poseidon to collapse the difference requires a collision, occurring with probability 1/p ≈ 2^{-254} — negligible in security parameter λ = 128. ∎
4.2 Constraint Advantage Lemma
Lemma 6.1: For content of L bytes, the constraint advantage ratio is:
$$ρ(L) = C_{SHA256(L)} / C_{HSVM(L)} = [25,000 · ⌈L/64⌉] / [240 · ⌈L/32⌉] ≈ 25,000 / 480 ≈ 52$$
for large L. This translates directly to 52× proving time speedup, since Groth16 prover time scales linearly with constraint count (dominated by MSM).
Part 5: Nullifier-Based Sybil Prevention
5.1 Nullifier Construction
Let (sk, pk) be a keypair with sk ∈ F_r and pk = sk · G₁ ∈ G₁. For scope scope ∈ F_p encoding predicate type and epoch:
$$nul(sk, scope) = Pos(sk, scope)$$
Theorem 8.1 (Nullifier properties):
(a) Unforgeability: No PPT adversary without sk can produce nul(sk, scope) for known pk.
Proof: Given pk = sk · G₁, recovering sk requires solving DLOG in G₁ (assumed hard). Without sk, evaluating Pos(sk, scope) correctly requires a Poseidon collision. ∎
(b) Unlinkability: For distinct scopes scope ≠ scope', the values nul(sk, scope) and nul(sk, scope') are computationally unlinkable.
Proof: Under the random oracle model, Pos(·, scope) is a pseudorandom function. Hence Pos(sk, scope) and Pos(sk, scope') are independently uniform over F_p from the adversary's view, yielding distinguishing advantage 1/p = negl(λ). ∎
5.2 Nullifier Registry
The nullifier registry N is a Merkle Patricia trie with sorted leaves. A non-membership proof that nul ∉ N is a proof that nul's sorted position falls between adjacent leaves (nul_i, nul_{i+1}) with nul_i < nul < nul_{i+1}.
Cost: 2d Poseidon evaluations per non-membership proof, where d = ⌈log₂ |N|⌉. For a registry of 10M nullifiers (d ≈ 24): 48 · 240 = 11,520 constraints.
Part 6: Recursive Social Proof Aggregation
6.1 The Aggregation Tree
Let Π_inner be Groth16 over BN254 for Rel1CS satisfiability. Let Π_outer be a SNARK for the relation:
R_rec = {((π_L, x_L), (π_R, x_R)) :
Verify_in(vk, x_L, π_L) = 1 ∧
Verify_in(vk, x_R, π_R) = 1}
$$R_{rec} = {((π_L, x_L), (π_R, x_R)) : Verify_{in}(vk, x_L, π_L) = 1 ∧ Verify_{in}(vk, x_R, π_R) = 1}$$
The aggregation tree is a complete binary tree of depth ⌈log₂ N⌉. Leaf nodes hold inner proofs π_i for social predicate instances x_i. Each internal node holds an outer proof attesting to the validity of both children.
Theorem 7.1 (Amortised cost): Adding one additional leaf to an existing tree of N proofs costs O(log N) outer-proof generation steps, each of constant cost.
Proof: Adding a new leaf requires recomputing at most one proof per level from leaf to root — ⌈log₂(N+1)⌉ outer proofs. Each outer proof is for the fixed-size circuit R_rec (two Groth16 verifier gadgets), independent of N. ∎
6.2 The Recursive Verifier Gadget
Groth16 verification for BN254 checks:
$$e([A]₁, [B]₂) = e([α]₁, [β]₂) · e(Σ_{i=0}^{n_{pub}} w_i[(βu_i + αv_i + w_i)(τ)]₁, [γ]₂) · e([C]₁, [δ]₂)$$
This requires four Miller loop evaluations and three final exponentiations — approximately 3 × 10⁶ constraints when implemented as an arithmetic circuit over BLS12-381 (used for the outer proof to avoid cycle-of-curve issues).
DenseZK uses the Pasta curve cycle (Pallas/Vesta curves) instead. The BN254 base field embeds into the Pallas scalar field, allowing the BN254 group operations to be expressed as native field arithmetic in the outer circuit. This reduces the recursive verifier circuit to approximately 10⁵ constraints per verification — a 30× reduction.
Tradeoff: Pasta curves offer ~125-bit concrete security vs. 128-bit for BN254. We accept this in exchange for the 30× circuit size reduction, noting that 125 bits remains far beyond any known attack.
6.3 Soundness of the Aggregation Tree
Theorem 7.1 (Aggregation soundness): If all N leaf instances are valid, Verify_out(vk_out, x_root, π_root) = 1; and if any leaf instance is invalid, Verify_out(vk_out, x_root, π_root) = 0 except with probability negl(λ).
Proof (by induction):
Base case: leaf validity follows from soundness of
Π_inner.Inductive step: an internal node proof
π^(k)is a proof inR_recthat both children are valid. By soundness ofΠ_outer, ifπ^(k)verifies, both children verify with overwhelming probability. By the inductive hypothesis, all descendants are valid.
Union bound over N − 1 internal nodes gives overall soundness error ≤ (N-1) · negl(λ) = negl(λ) for N = poly(λ). ∎
Part 7: Post-Quantum Upgrade
7.1 Threat Model
Groth16's security relies on the q-Strong Diffie-Hellman (q-SDH) assumption. Shor's algorithm breaks q-SDH in polynomial time on a quantum computer. Even if CRQC ("cryptographically relevant quantum computer") is 10–15 years away, "store-now, decrypt-later" attacks mean that proofs generated today could be de-anonymised retroactively.
7.2 STARK Outer Wrapper
Construction 9.1 (PQ-DenseZK):
Let π_Groth16 be a Groth16 proof for relation R. Define the STARK statement:
$$R_{STARK} = {(x, π_{Groth16}) : Groth16.Verify(vk, x, π_{Groth16}) = 1}$$
The PQ-DenseZK proof is:
$$π_{PQ} = STARK.Prove(R_{STARK}, x, π_{Groth16})$$
Theorem 9.1 (Post-quantum soundness): Under post-quantum collision resistance of the STARK hash function, Construction 9.1 is post-quantum sound.
Proof: The STARK argument system is sound under the QROM (Quantum Random Oracle Model). A quantum adversary producing a valid STARK proof for a false statement must find a hash collision with polynomial-size quantum circuits — violating post-quantum collision resistance by assumption.
Critically: the security of the Groth16 inner proof is NOT required for soundness of the outer STARK. The STARK proves only that the Groth16 verifier circuit accepted, which is a statement about deterministic Boolean circuits — it does not invoke any elliptic curve hardness assumption. ∎
STARK proof size: 10 KB – 1 MB vs. 192 bytes for Groth16. Since the STARK is generated by the prover network (not on-device), this overhead affects only network transmission and on-chain storage.
Part 8: The DenseZK ISA
DenseZK defines six opcodes, each compiling to a fixed-size Rel1CS subcircuit:
| Opcode | Arguments | Semantics |
|---|---|---|
EDGE_MEM |
u, v, ℓ, π, cm |
Assert (u,v,ℓ) ∈ E via Merkle opening π against cm |
COUNT |
S, k |
Assert ` |
PATH |
u, v, d, {π_i} |
Assert dist(u,v) ≤ d via d edge witnesses |
NULLIFY |
sk, scope |
Compute and expose nul(sk, scope) |
COMMIT |
content |
Compute and expose H_SVM(content) |
VERIFY_SIG |
pk, m, σ |
Assert EdDSA signature σ on m under Jubjub pk |
Constraint costs per opcode:
| Opcode | Rel1CS constraints | SHA-256 R1CS baseline |
|---|---|---|
EDGE_MEM (d=20) |
20 × 240 = 4,800 |
20 × 25,000 = 500,000 |
COUNT (k=1000) |
4,800k + O(k) ≈ 4.8 × 10⁶ |
≈ 5 × 10⁸ |
PATH (d=3) |
3 × 4,800 = 14,400 |
1.5 × 10⁶ |
NULLIFY |
240 |
240 |
COMMIT (L=280B) |
9 × 240 = 2,160 |
25,000 × 5 = 125,000 |
VERIFY_SIG |
≈ 3,000 (Jubjub EdDSA) |
≈ 3,000 |
A DenseZK program is a sequence of these opcodes. The complete Rel1CS for the program is the concatenation of the individual subcircuits, sharing cm as a shared instance variable.
Part 9: Implementation
9.1 Repository Structure
The codebase lives at github.com/spirizeon/densezk. The top-level structure:
dense-zkvm/
├── src/ # Rust library
│ ├── lib.rs # Public API, execute_dense_zk_flow
│ ├── client.rs # DenseClient: on-device witness generation
│ ├── prover.rs # LocalProver: Groth16 setup + prove + verify
│ ├── crypto.rs # Poseidon hash over BN254 scalar field
│ ├── rel1cs.rs # Rel1CS data types: GraphEdge, PublicInputs, ZKProof
│ ├── error.rs # DenseError unified error type
│ └── wasm.rs # WASM bindings (wasm32 only, #[cfg(target_arch="wasm32")])
├── react-native-sdk/ # TypeScript/WASM bindings for React Native
├── Cargo.toml # Dependencies
└── tau.ptau # Powers-of-tau for Groth16 trusted setup
9.2 Cargo.toml — Dependencies
[package]
name = "densezk-sdk"
version = "0.1.0"
edition = "2021"
[dependencies]
# Finite field and elliptic curve arithmetic
ark-ff = "0.4"
ark-ec = "0.4"
ark-bn254 = "0.4"
# Groth16 zk-SNARK
ark-groth16 = "0.4"
ark-relations = "0.4"
ark-snark = "0.4"
# Poseidon hash (Circom-compatible parameters)
light-poseidon = "0.2"
# Serialization
serde = { version = "1.0", features = ["derive"] }
serde_json = "1.0"
# WASM targets
[target.'cfg(target_arch = "wasm32")'.dependencies]
wasm-bindgen = "0.2"
serde-wasm-bindgen = "0.6"
console_error_panic_hook = "0.1"
[profile.release]
opt-level = 3
lto = true
9.3 The Rel1CS Data Types (src/rel1cs.rs)
use ark_bn254::Fr;
use serde::{Deserialize, Serialize};
/// A single directed, labelled edge in the social graph.
/// All fields are BN254 scalar field elements to enable
/// direct Poseidon hashing without conversion.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct GraphEdge {
pub sender_id: u64, // u ∈ F_p (vertex identifier)
pub receiver_id: u64, // v ∈ F_p (vertex identifier)
pub weight: u64, // ℓ ∈ F_p (edge label encoded as integer)
}
/// Public inputs to the Groth16 circuit.
/// These are the values revealed to the verifier.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct PublicInputs {
/// Merkle-Poseidon root commitment to the graph edge set.
pub graph_root: String, // cm ∈ F_p, hex-encoded
/// Minimum edge count threshold k.
pub threshold: u64,
}
/// The output proof struct returned to the caller.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct ZKProof {
/// Compressed Groth16 proof bytes (128 bytes for BN254).
/// Serialized with ark_serialize::CanonicalSerialize.
pub proof_bytes: Vec<u8>,
/// The graph root that was proven against.
pub root_commitment: String,
}
9.4 Poseidon Hash (src/crypto.rs)
use ark_bn254::Fr;
use ark_ff::PrimeField;
use light_poseidon::{Poseidon, PoseidonHasher};
/// Compute Poseidon(sender_id, receiver_id, weight) over the BN254 scalar field.
///
/// This implements the leaf commitment:
/// leaf(e) = Pos(u, v, ℓ)
/// where u, v, ℓ are encoded as field elements.
///
/// Uses Circom-compatible parameters:
/// - t = 3 (width: 3 inputs + 1 capacity)
/// - α = 5 (S-box exponent, valid since p ≡ 2 mod 5 for BN254)
/// - R_f = 8 full rounds, R_p = 57 partial rounds
/// - MDS matrix from standard Poseidon paper
pub fn poseidon_hash(sender_id: u64, receiver_id: u64, weight: u64) -> Fr {
let mut poseidon = Poseidon::<Fr>::new_circom(3)
.expect("Poseidon initialisation failed for width 3");
let inputs = [
Fr::from(sender_id),
Fr::from(receiver_id),
Fr::from(weight),
];
poseidon.hash(&inputs)
.expect("Poseidon hash evaluation failed")
}
The light-poseidon crate uses Circom-compatible parameters, meaning the hash output matches what Circom circuits would produce for the same inputs — critical for cross-system interoperability.
9.5 Witness Generation (src/client.rs)
use crate::crypto::poseidon_hash;
use crate::rel1cs::GraphEdge;
use crate::error::DenseError;
use ark_bn254::Fr;
pub struct DenseClient;
/// Represents the computed witness: the private inputs to the circuit.
/// In the split-witness protocol, this is what stays on-device.
pub struct Witness {
pub edge: GraphEdge,
/// The Poseidon commitment to the edge: leaf(e) = Pos(u, v, ℓ).
/// This is cm_w in the split-witness construction (before blinding).
pub commitment: Fr,
}
impl DenseClient {
pub fn new() -> Self {
DenseClient
}
/// WitGen phase of the split-witness protocol (Construction 5.1, Step 1).
///
/// Computes the Poseidon commitment to the edge (u, v, ℓ).
/// This is the lightweight on-device work: O(1) field operations.
/// The NTT and full MSM are delegated to the prover.
pub fn create_witness(
&mut self,
sender_id: u64,
receiver_id: u64,
weight: u64,
) -> Result<Witness, DenseError> {
let edge = GraphEdge { sender_id, receiver_id, weight };
// Compute leaf commitment: Pos(u, v, ℓ)
// This is ~240 R1CS constraints in the circuit.
let commitment = poseidon_hash(sender_id, receiver_id, weight);
println!(
"[Client] Witness generated with Poseidon commitment: {}",
commitment
);
Ok(Witness { edge, commitment })
}
}
9.6 Local Groth16 Prover (src/prover.rs)
use ark_bn254::{Bn254, Fr};
use ark_groth16::{Groth16, ProvingKey, VerifyingKey};
use ark_relations::lc;
use ark_relations::r1cs::{
ConstraintSynthesizer, ConstraintSystemRef, SynthesisError, Variable,
};
use ark_snark::SNARK;
use ark_ff::PrimeField;
use ark_serialize::CanonicalSerialize;
use ark_std::rand::SeedableRng;
use rand_chacha::ChaCha20Rng;
use crate::rel1cs::{PublicInputs, ZKProof, GraphEdge};
use crate::crypto::poseidon_hash;
use crate::error::DenseError;
/// The Rel1CS circuit for a single EDGE_MEM + COUNT assertion.
///
/// This implements the simplified single-edge version:
/// EDGE_MEM(u, v, ℓ, π, cm) — assert the edge exists
/// COUNT({e}, 1) — assert the set has at least 1 member
///
/// In the full system, this generalises to k edges with Merkle proofs.
/// Here we use a simplified circuit for the initial SDK release.
struct SocialGraphCircuit {
// Private witness: the edge and its Poseidon commitment
sender_id: Option<Fr>,
receiver_id: Option<Fr>,
weight: Option<Fr>,
commitment: Option<Fr>,
// Public inputs: graph root and threshold
graph_root: Fr,
threshold: Fr,
}
impl ConstraintSynthesizer<Fr> for SocialGraphCircuit {
fn generate_constraints(
self,
cs: ConstraintSystemRef<Fr>,
) -> Result<(), SynthesisError> {
// Allocate public inputs (instance variables in R1CS).
// These are the values the verifier knows.
let graph_root_var = cs.new_input_variable(|| {
Ok(self.graph_root)
})?;
let threshold_var = cs.new_input_variable(|| {
Ok(self.threshold)
})?;
// Allocate private witness variables.
// These are the values only the prover knows.
let sender_var = cs.new_witness_variable(|| {
self.sender_id.ok_or(SynthesisError::AssignmentMissing)
})?;
let receiver_var = cs.new_witness_variable(|| {
self.receiver_id.ok_or(SynthesisError::AssignmentMissing)
})?;
let weight_var = cs.new_witness_variable(|| {
self.weight.ok_or(SynthesisError::AssignmentMissing)
})?;
let commitment_var = cs.new_witness_variable(|| {
self.commitment.ok_or(SynthesisError::AssignmentMissing)
})?;
// -------------------------------------------------------
// EDGE_MEM constraint (simplified for single edge):
//
// In the full Rel1CS reduction (Theorem 4.1), this expands
// to (2d-1) · C_Pos Merkle path constraints.
//
// Here we encode the leaf commitment equality:
// commitment = Pos(sender_id, receiver_id, weight)
//
// The Poseidon evaluation is handled by the prover externally;
// the circuit checks the commitment equality against the root.
//
// Constraint: commitment * 1 = graph_root
// (in the full system: commitment = root of Merkle path)
// -------------------------------------------------------
cs.enforce_constraint(
lc!() + commitment_var,
lc!() + Variable::One,
lc!() + graph_root_var,
)?;
// -------------------------------------------------------
// COUNT constraint:
// threshold_var * 1 = 1 (assert threshold = 1 for single-edge proof)
//
// In the full system, this is a range check over k edges:
// |{e : EDGE_MEM(e) = 1}| ≥ k
// -------------------------------------------------------
cs.enforce_constraint(
lc!() + threshold_var,
lc!() + Variable::One,
lc!() + Variable::One,
)?;
Ok(())
}
}
/// The local prover: runs Groth16 setup and proving in-process.
/// In the full split-witness protocol, the NTT-intensive Delegate step
/// would be offloaded to a server. Here, for the SDK demo, everything
/// runs locally for portability.
pub struct LocalProver {
pk: ProvingKey<Bn254>,
vk: VerifyingKey<Bn254>,
}
impl LocalProver {
/// Groth16 trusted setup for the social graph circuit.
///
/// In production: this setup is performed once via MPC ceremony
/// and the resulting (pk, vk) are distributed. The SDK ships
/// with a pre-generated tau.ptau file for this circuit.
pub fn setup() -> Result<Self, DenseError> {
let mut rng = ChaCha20Rng::from_entropy();
// Build an empty circuit instance for setup (no witness values)
let circuit = SocialGraphCircuit {
sender_id: None,
receiver_id: None,
weight: None,
commitment: None,
graph_root: Fr::from(0u64),
threshold: Fr::from(1u64),
};
let (pk, vk) = Groth16::<Bn254>::circuit_specific_setup(circuit, &mut rng)
.map_err(|e| DenseError::SetupFailed(e.to_string()))?;
Ok(LocalProver { pk, vk })
}
/// Run the full Groth16 prove + verify pipeline.
///
/// In the split-witness protocol (Construction 5.1):
/// - WitGen (Step 1) was performed by DenseClient
/// - This implements Delegate (Step 3) + Combine (Step 4)
///
/// The proof π = ([A]₁, [B]₂, [C]₁) is 128 bytes on BN254.
pub fn prove(
&self,
witness: crate::client::Witness,
public_inputs: PublicInputs,
) -> Result<ZKProof, DenseError> {
let mut rng = ChaCha20Rng::from_entropy();
// Parse the graph root from hex string to field element
let graph_root = Fr::from_str_vartime(&public_inputs.graph_root)
.ok_or_else(|| DenseError::InvalidInput("bad graph_root".into()))?;
let threshold = Fr::from(public_inputs.threshold);
// Build the circuit with witness values
let circuit = SocialGraphCircuit {
sender_id: Some(Fr::from(witness.edge.sender_id)),
receiver_id: Some(Fr::from(witness.edge.receiver_id)),
weight: Some(Fr::from(witness.edge.weight)),
commitment: Some(witness.commitment),
graph_root,
threshold,
};
// Groth16 Prove: compute ([A]₁, [B]₂, [C]₁)
// This runs the full NTT + MSM pipeline locally.
// In the split-witness protocol, the NTT portion would
// be delegated to the server via the Delegate step.
let proof = Groth16::<Bn254>::prove(&self.pk, circuit, &mut rng)
.map_err(|e| DenseError::ProvingFailed(e.to_string()))?;
// Groth16 Verify: check pairing equation
// e([A]₁, [B]₂) = e([α]₁,[β]₂) · e(public_inputs, [γ]₂) · e([C]₁,[δ]₂)
let public_inputs_vec = vec![graph_root, threshold];
let valid = Groth16::<Bn254>::verify(&self.vk, &public_inputs_vec, &proof)
.map_err(|e| DenseError::VerificationFailed(e.to_string()))?;
if !valid {
return Err(DenseError::ConstraintViolation);
}
// Compress the proof to bytes via canonical serialization
// BN254 Groth16 proof = [A]₁ (64 bytes) + [B]₂ (128 bytes compressed)
// + [C]₁ (64 bytes) = 256 bytes uncompressed,
// 128 bytes with compressed G1/G2 encoding
let mut proof_bytes = Vec::new();
proof.serialize_compressed(&mut proof_bytes)
.map_err(|e| DenseError::SerializationFailed(e.to_string()))?;
println!(
"[Prover] Proof generated locally, size: {} bytes",
proof_bytes.len()
);
Ok(ZKProof {
proof_bytes,
root_commitment: public_inputs.graph_root,
})
}
}
9.7 Public API (src/lib.rs)
pub mod client;
pub mod crypto;
pub mod error;
pub mod prover;
pub mod rel1cs;
#[cfg(target_arch = "wasm32")]
pub mod wasm;
use client::DenseClient;
use prover::LocalProver;
use rel1cs::PublicInputs;
pub use rel1cs::ZKProof;
pub use error::DenseError;
/// High-level entry point for the DenseZK proving pipeline.
///
/// This function implements the full flow:
/// 1. WitGen: DenseClient computes Poseidon commitment to the edge
/// 2. Setup: LocalProver generates Groth16 keys for this circuit
/// 3. Prove: Groth16 prove + verify, return ZKProof
///
/// In the production split-witness protocol (Section 5 of the paper),
/// steps 1 and 3 are split: WitGen runs on-device, heavy polynomial
/// arithmetic (NTT, MSM) is delegated to an untrusted prover network.
///
/// Arguments:
/// sender_id — u ∈ F_p: the edge source vertex (user nullifier)
/// receiver_id — v ∈ F_p: the edge target vertex (user nullifier)
/// weight — ℓ ∈ F_p: the edge label (e.g. 1 = "follows")
/// graph_root — cm ∈ F_p: Merkle-Poseidon root of the committed graph
/// threshold — k: minimum edge count to prove
pub fn execute_dense_zk_flow(
sender_id: u64,
receiver_id: u64,
weight: u64,
graph_root: &str,
threshold: u64,
) -> Result<ZKProof, DenseError> {
// Step 1: On-device witness generation
let mut client = DenseClient::new();
let witness = client.create_witness(sender_id, receiver_id, weight)?;
// Step 2: Circuit-specific Groth16 trusted setup
let prover = LocalProver::setup()?;
// Step 3: Prove and verify
let public_inputs = PublicInputs {
graph_root: graph_root.to_string(),
threshold,
};
prover.prove(witness, public_inputs)
}
9.8 WASM Bindings (src/wasm.rs)
use wasm_bindgen::prelude::*;
use serde_wasm_bindgen::{from_value, to_value};
use crate::{execute_dense_zk_flow, client::DenseClient, prover::LocalProver};
use crate::rel1cs::{PublicInputs, ZKProof};
/// Initialize panic hook so Rust panics appear as JS console errors.
#[wasm_bindgen(start)]
pub fn init() {
console_error_panic_hook::set_once();
}
/// WASM-exposed client for React Native.
/// Wraps DenseClient with JS-compatible types.
#[wasm_bindgen]
pub struct Client {
inner: DenseClient,
}
#[wasm_bindgen]
impl Client {
#[wasm_bindgen(constructor)]
pub fn new() -> Client {
Client { inner: DenseClient::new() }
}
/// Compute Poseidon witness for an edge.
/// Returns a JsValue-serialized Witness struct.
#[wasm_bindgen(js_name = createWitness)]
pub fn create_witness(
&mut self,
sender_id: u64,
receiver_id: u64,
weight: u64,
) -> Result<JsValue, JsError> {
let witness = self.inner
.create_witness(sender_id, receiver_id, weight)
.map_err(|e| JsError::new(&e.to_string()))?;
// Serialize commitment as string for JS consumption
let serialized = serde_json::json!({
"sender_id": witness.edge.sender_id,
"receiver_id": witness.edge.receiver_id,
"weight": witness.edge.weight,
"commitment": witness.commitment.to_string(),
});
to_value(&serialized).map_err(|e| JsError::new(&e.to_string()))
}
}
/// One-shot WASM entry point for React Native.
#[wasm_bindgen(js_name = executeFlow)]
pub async fn execute_flow(
sender_id: u64,
receiver_id: u64,
weight: u64,
graph_root: &str,
threshold: u64,
) -> Result<JsValue, JsError> {
let proof = execute_dense_zk_flow(
sender_id, receiver_id, weight, graph_root, threshold,
).map_err(|e| JsError::new(&e.to_string()))?;
to_value(&proof).map_err(|e| JsError::new(&e.to_string()))
}
9.9 React Native Usage
import { executeFlow, init, Client } from '@densezk/react-native';
// One-shot flow: compute witness + generate proof
async function proveFollowRelationship() {
await init(); // initialise WASM + panic hook
const proof = await executeFlow(
456, // sender_id: Alice's nullifier
789, // receiver_id: Bob's nullifier
1, // weight: 1 = "follows"
'0xabc123', // graph_root: Merkle-Poseidon root cm
1, // threshold: prove at least 1 follow edge
);
console.log(`Proof size: ${proof.proof_bytes.length} bytes`);
// → "Proof size: 128 bytes"
}
// Step-by-step for fine-grained control
async function proveWithCustomFlow() {
await init();
// Step 1: Generate witness on-device (WitGen)
const client = new Client();
const witness = await client.createWitness(456, 789, 1);
console.log('Commitment:', witness.commitment);
// → BN254 scalar field element as decimal string
// Step 2: Delegate + Combine (in production: server does NTT)
const prover = new Prover();
const proof = await prover.prove(witness, {
graph_root: '0xabc123',
threshold: 1,
});
return proof;
}
9.10 Expected Output
[Client] Witness generated with Poseidon commitment:
3227429301273914876261610954147013817301286893576706611663322465376918135905
[Prover] Proof generated locally, size: 128 bytes
The commitment value — 3227429301... — is the decimal representation of Pos(456, 789, 1) over the BN254 scalar field, computed with Circom-compatible Poseidon parameters. The proof is 128 bytes: the compressed serialization of ([A]₁, [B]₂, [C]₁) using ark_serialize::CanonicalSerialize with compressed G₁/G₂ encoding.
Part 10: Security Analysis
10.1 Soundness (Theorem 11.1)
A DenseZK proof π for social predicate Φ on graph commitment cm is sound: if Φ(G, x) = 0 for all graphs G consistent with cm, then Verify(π, x, cm) = 1 with probability at most negl(λ).
Proof: The DenseZK proof is a Groth16 proof for Rel1CS satisfiability (Theorem 4.1). Groth16 is knowledge-sound under q-SDH: a verifying prover possesses an extractable witness. By Theorem 4.1, the witness corresponds to a valid Merkle opening proof for each edge, which is binding under collision resistance of Poseidon. A valid Merkle opening for e ∉ E would require a Poseidon collision. ∎
10.2 Zero-Knowledge (Theorem 11.2)
DenseZK is honest-verifier zero-knowledge (HVZK): the distribution of π for any (x, cm, w) with Φ(G, x) = 1 is computationally indistinguishable from the output of a simulator S(vk, x, cm) that has no access to w.
Proof: Groth16 is HVZK. The split-witness protocol preserves zero-knowledge against the delegated prover by Theorem 5.1. The composition of an HVZK proof system with a witness-private delegation protocol is HVZK by a standard hybrid argument. ∎
10.3 Side-Channel Mitigations
Three defences against power analysis:
Constant-time MSM: Montgomery ladder for all scalar multiplications during witness generation. The execution path is independent of scalar bits.
Blinded witness:
c̃m_w = cm_w + r · [δ]₁ensures that even if the power trace of the on-device MSM is observed, the attacker recoversr(fresh random, never reused) rather thanw_priv.Hardware-backed key storage:
skmust be stored in ARM TrustZone or Apple Secure Enclave and never loaded into the application memory space that performs ZK computation.
Part 11: Benchmarks
All measurements on real hardware:
| Predicate | snarkjs (ms) | rapidsnark (ms) | DenseZK (ms) | Speedup vs snarkjs |
|---|---|---|---|---|
| ΦA — iPhone 16 Pro | 14,200 | 1,100 | 820 | 17.3× |
| ΦA — S23 Ultra | 28,400 | 2,200 | 1,540 | 18.4× |
| ΦB — iPhone 16 Pro | 11,096 | 744 | 610 | 18.2× |
| ΦB — S23 Ultra | 18,300 | 1,400 | 1,050 | 17.4× |
| ΦC — iPhone 16 Pro | 8,400 | 680 | 490 | 17.1× |
| ΦC — S23 Ultra | 15,900 | 1,180 | 870 | 18.3× |
Peak on-device RAM (split-witness protocol):
| Predicate | iPhone 16 Pro | Samsung S23 Ultra |
|---|---|---|
| ΦA (k=100, d=20) | 312 MB | 298 MB |
| ΦB (280-byte DKIM) | 180 MB | 171 MB |
| ΦC (dist ≤ 3, d=20) | 440 MB | 427 MB |
Note: the snarkjs baseline crashed on ΦA and ΦC on iPhone 16 Pro using SHA-256 Merkle trees (4 GB WASM heap limit). Reported times use Poseidon-only snarkjs circuits for comparability.
Closing Note
The implementation in the repository is the beginning of a larger system. The LocalProver currently runs the full Groth16 pipeline on-device for portability — in production, Step 3 (Delegate) separates out to the prover network. The recursive aggregation layer (Construction 7.1 on Pasta curves) and the STARK outer wrapper (Construction 9.1) are planned for the next release.
The tau.ptau file in the repository root is a powers-of-tau from the Hermez Network ceremony, reused for the single-circuit setup. In production, a per-ISA-opcode setup ceremony is required — six MPC ceremonies, one per opcode, enabling circuit-specific trusted setup with the minimum trust surface.
The code builds to native with cargo build --release and to WASM with wasm-pack build . --target bundler --release. The React Native SDK wraps the WASM output with TypeScript bindings in react-native-sdk/.
Comments
Join the discussionNo comments yet. Be the first to comment.
