Polynomial Commitment Protocol for MPC Encryption

Abstract

This document formally specifies Umbra's Polynomial Commitment Protocol, a hybrid cryptographic system that bridges Solana (Ed25519), Zero-Knowledge Proofs (BN254), and Multi-Party Computation (Curve25519). The protocol enables users to prove valid encryption to the MPC network with significantly fewer communication rounds while maintaining lightweight ZKPs with minimal non-linear constraints, resulting in dramatically faster proof generation and verification.

The key innovation is the use of polynomial commitments combined with Strong Fiat-Shamir transformation and 85-bit limb-based Non-Native Arithmetic to efficiently bridge field mismatches. This eliminates interactive challenge-response rounds and reduces circuit complexity by orders of magnitude compared to naive approaches.

---

1. System Overview and Actors

The protocol coordinates four distinct parties:

1.1 User A (The Prover)

Identity:

The user holds two keypairs:

• Ownership Keypair: Ed25519 keypair $(a, A)$ for Solana transaction signing and ownership control
• Decryption Keypair: Curve25519 keypair $(a', A')$ for encryption and decryption operations

Goal: Deposit funds and claim them into a Private Token Account without revealing the amount or source note, while proving correct encryption to MPC.

1.2 User B (The Adversary)

Role: Passive observer monitoring the blockchain

Goal: Compromise anonymity (link nullifier to leaf) or confidentiality (decrypt amount)

1.3 Smart Contract C (The Verifier)

Role: Solana program that maintains the Incremental Merkle Tree, verifies Zero-Knowledge Proofs on-chain, and orchestrates data passing to MPC

Constraint: Transparent execution; everything is stored on-chain; cannot hold private keys

1.4 MPC Network D (The Authority)

Role: Can be thought of as a virtual user that holds a Curve25519 keypair $(D, d)$

Constraints:

• Operates over $\mathbb{F}_p$ where $p = 2^{255} - 19$
• Cannot perform BN254 pairings or Poseidon hashes
• Output capability limited to values $< 2^{128} - 1$

---

2. Cryptographic Foundations

2.1 Mathematical Fields and the Mismatch Problem

The protocol navigates two distinct prime fields, each serving a specific purpose:

Encryption/MPC Field: $\mathbb{F}_p$ - The prime field of Curve25519

$$p = 2^{255} - 19$$

Used for Rescue Cipher encryption, MPC secret sharing, and polynomial arithmetic.

Zero-Knowledge Field: $\mathbb{F}_r$ - The scalar field of BN254

$$r = 21888242871839275222246405745257275088548364400416034343698204186575808495617$$

Used for Merkle Trees (Poseidon) and Groth16 circuit logic.

The Arithmetic Mismatch: Since $p > r$, an element $x \in \mathbb{F}_p$ cannot be naively represented as a signal in an $\mathbb{F}_r$ circuit because it may overflow the modulus $r$. This necessitates Non-Native Arithmetic.

2.2 Non-Native Arithmetic: 85-bit Limb Basis

To verify operations in the field $\mathbb{F}_p$ inside an $\mathbb{F}_r$ circuit, we employ a limb-based representation. Every element is decomposed into 3 limbs of 85 bits each:

$$x = x_{0} + x_{1} \cdot 2^{85} + x_{2} \cdot 2^{170}$$

where each limb satisfies $0 \leq x_{i} < 2^{85}$ for $i \in \{0, 1, 2\}$

Why 85 bits?

Coverage:

• $3 \times 85 = 255$ bits, which strictly covers the 255-bit prime $p$

Overflow Safety:

• Native capacity of $\mathbb{F}_r$ is $\approx 254$ bits
• Addition of two limbs: max value $\approx 2^{86} \ll r$
• Multiplication of two limbs: max value $\approx 2^{170} \ll r$

This ensures intermediate calculations never overflow the native modulus $r$.

Constraint Logic

To enforce $A + B \equiv C \pmod{p}$ inside the circuit:

1. Decomposition: Prover supplies limbs for $A$, $B$, $C$ and a quotient $k$
2. Range Check: Circuit asserts $x_{i} < 2^{85}$ for all limbs via binary decomposition constraints
3. Polynomial Equality: Circuit enforces the relation over the integers:

$$A(2^{85}) + B(2^{85}) = C(2^{85}) + k \cdot p$$

Efficiency Gain: This limb-based approach requires significantly fewer constraints compared to bit-by-bit verification, directly translating to faster proof generation.

---

3. Data Structures

3.1 The Incremental Merkle Tree

The mixer pool uses a Merkle Tree of depth $D = 32$. Leaves are constructed to hide both usage constraints and secret values using the Poseidon hash function over public context (AssetID, PoolID) and secret context (random blinding factor, nullifier, amount).

Components:

• Random blinding factor: 250-bit value
• Private nullifier: 250-bit value
• Amount: 64-bit value

---

4. The Interactive Protocol (Σ-Protocol)

We first define the theoretical Interactive Protocol to establish Completeness, Soundness, and Zero-Knowledge properties.

4.1 Phase 1: Commitment (P → V)

User A (Prover) locks secret values into a commitment:

Step 1 - Shared Secret:

$S = ECDH(a', D)$

Step 2 - Keystream:

Generate nonce $n_{1}$ and compute keystream using Rescue cipher: $\vec{k} = Rescue(S, n_{1})$

Step 3 - Encryption (One-Time Pad):

Encrypt the amount using one-time pad over the field:

$$C_1 = a + k_1 \bmod p$$

Encrypt the polynomial blinder:

$$C_2 = r_1 + k_2 \bmod p$$

where $a$ is the amount, $r_1$ is a random blinder, and $k_1, k_2$ are keystream elements.

Step 4 - Commitment:

Select random blinder $r_2$ and compute commitment hash $h$ using Poseidon hash function $H$:

$$h = H(n_1, C_1, C_2, a, r_1, k_1, k_2, r_2)$$

Step 5 - Send to Verifier:

Send commitment $h$ to the Verifier (Smart Contract)

4.2 Phase 2: Challenge (V → P)

1. Verifier generates uniform random challenge $f \in \mathbb{F}_p$
2. Verifier sends $f$ to Prover

4.3 Phase 3: Response (P → V)

1. Polynomial Evaluation:

$$V = a_{val} \cdot f + r_{1} \cdot f^2 \pmod{p}$$

2. ZKP Generation: Prover generates proof $\pi$ for the relation:

   • Membership: Leaf is in Merkle Tree
   • Encryption: $C_{amount} \equiv a_{val} + k_{1} \pmod{p}$ (Non-Native)
   • Polynomial: $V \equiv a_{val} \cdot f + r_{1} \cdot f^2 \pmod{p}$ (Non-Native)
   • Nullifier: Correctly formed

3. Send $(\pi, V, C_{amount}, C_{poly}, n_{1}, h_{nullifier})$ to Verifier

4.4 Phase 4: Verification

1. Verifier checks $\pi$ using public inputs
2. Verifier checks nullifier set for duplicates
3. MPC nodes decrypt amount and blinder, then verify polynomial evaluation matches $V$

4.5 Security Analysis

The protocol's security relies on standard cryptographic assumptions (ROM, CDH, DLP, Groth16 security, PRF security of Rescue). We focus here on the novel security properties introduced by our polynomial commitment mechanism with non-native arithmetic.

---

Polynomial Commitment Soundness

Key Property: The polynomial commitment binds the prover to a specific amount value through the Schwartz-Zippel Lemma. An adversary who commits to amount $a_{val}$ via polynomial $Q(x) = a_{val} \cdot x + r_{1} \cdot x^2$ cannot later claim a different amount $a'_{val}$ (via polynomial $Q'(x)$) without the MPC detecting the mismatch.

Soundness Guarantee: Since $Q - Q' = (a_{val} - a'_{val}) x + (r_{1} - r'_{1}) x^2$ is a non-zero polynomial of degree $\leq 2$, the probability that a random challenge $f$ is a root is at most $2 / p < 2^{-254}$ by the Schwartz-Zippel Lemma.

This polynomial commitment mechanism provides cryptographic binding between the encrypted amount and the ZK proof, preventing amount manipulation attacks.

---

5. The Non-Interactive Protocol (Strong Fiat-Shamir)

To eliminate interaction and prevent front-running attacks on the challenge, we apply the Strong Fiat-Shamir Transformation.

5.1 The Transformation Logic

Instead of receiving $f$ from the Verifier, the Prover derives $f$ from the transcript of the commitment. This binds the challenge to the specific secrets committed:

$$f = H_{RO}(Transcript)$$

Key Advantage: This transformation eliminates the need for multiple communication rounds. The prover can generate the entire proof in a single pass, reducing latency from multiple round-trips to a single on-chain transaction.

5.2 Protocol Execution Flow

Step 1: Setup & Encryption (Off-Chain)

Identical to Interactive Phase 1. User derives keys, encrypts $C_{amount}$, $C_{poly}$, and computes $H_{com}$.

Step 2: Challenge Derivation

1. Transcript Assembly:

$$T = H_{com} \, || \, root \, || \, h_{nullifier} \, || \, n_{1} \, || \, C_{amount} \, || \, C_{poly}$$

2. Random Oracle Evaluation:

$$f = H_{RO}(T) \pmod{p}$$

Security Note: Because $f$ depends on $H_{com}$ (which contains $a_{val}$), the Prover cannot manipulate $a_{val}$ to satisfy a polynomial relation $V_{fake}$ without changing $f$. This circular dependency makes spoofing computationally infeasible.

Step 3: ZKP Generation (85-bit Limb Circuit)

The circuit takes $f$ as a public input:

Inputs: Witnesses $a_{val}$, $k_{1}$, $r_{1}$, $f$, $V$ provided as 3-limb arrays

Constraints:

1. Non-Native Check 1: $BigIntAdd(a_{val}, k_{1}) \equiv C_{amount} \pmod{p}$

2. Non-Native Check 2: $BigIntMul(a_{val}, f) + BigIntMul(r_{1}, f \cdot f) \equiv V \pmod{p}$

3. Commitment Check: $H_{com} = H_{Pos}(n_{1}, \cdots)$

Step 4: On-Chain Settlement

The Smart Contract:

1. Reconstructs $T$ from transaction data
2. Computes $f_{onchain} = H_{RO}(T)$
3. Verifies $Groth16.Verify(\pi, f_{onchain})$
4. Emits event for MPC network

---

6. Adversarial Analysis

We now provide comprehensive game-based security proofs against active and passive adversaries.

6.1 Scenario A: User A (The Drainer)

Goal: Claim more funds than deposited ($a_{fake} > a_{real}$)

We analyze three sophisticated attack strategies and provide rigorous game-based security proofs.

---

Attack 1: Modulus Mismatch Exploitation

Attack Strategy: Adversary attempts to exploit the field mismatch $p > r$ by finding ciphertext that decrypts to different values modulo $r$ vs. modulo $p$.

Formal Game: Modulus Mismatch Game

1. Setup: Challenger generates system parameters
2. Adversary Goal: Find $(C_{amount}, a_{real}, a_{fake}, k_{1})$ such that:
   • $C_{amount} \equiv a_{real} + k_{1} \pmod{r}$ (passes circuit check)
   • $C_{amount} \equiv a_{fake} + k_{1} \pmod{p}$ (MPC decrypts to fake amount)
   • $a_{fake} > a_{real}$

Theorem 8 (Modulus Mismatch Resistance):

For any PPT adversary, the probability of successfully exploiting modulus mismatch is negligible.

Proof:

Non-Native Arithmetic Enforcement: The circuit verifies addition via 85-bit limb decomposition.

The circuit enforces integer equality of the limb representations:

$$C = A + K + q \cdot p$$

where $C$, $A$, $K$ are the integer values represented by their respective limbs, and $q$ is an integer quotient.

Key Observation: This is an integer equality, not modular arithmetic. Therefore the ciphertext equals the plaintext plus keystream plus some multiple of the modulus, all as integers.

Contradiction: Suppose $\mathcal{A}_{1}$ succeeds with $(a_{real}, a_{fake})$ where $a_{real} \not\equiv a_{fake} \pmod{p}$.

From circuit verification:

$$C_{amount} = a_{real} + k_{1} + q_{1} \cdot p$$

From MPC decryption (modulo $p$):

$$C_{amount} \equiv a_{fake} + k_{1} \pmod{p}$$

Subtracting: $a_{real} + q_{1} \cdot p \equiv a_{fake} \pmod{p}$

This implies: $a_{real} \equiv a_{fake} \pmod{p}$

But we assumed $a_{real} \not\equiv a_{fake} \pmod{p}$. Contradiction!

Conclusion: The 85-bit limb arithmetic enforces integer equality, making modulus mismatch attacks impossible. $\square$

---

Attack 2: Challenge Prediction and Adaptive Polynomial Construction

Attack Strategy: Adversary attempts to predict challenge before committing, then construct polynomial with fake amount that evaluates correctly at predicted challenge.

Formal Game: Challenge Prediction Game

1. Adversary chooses: $(a_{fake}, r_{fake})$ with $a_{fake} \neq a_{real}$
2. Adversary predicts: Challenge $f^*$
3. Adversary computes: $V^* = a_{fake} \cdot f^* + r_{fake} \cdot (f^*)^2$
4. Adversary creates: Commitment $H_{com}^*$
5. Challenger derives: Actual challenge $f = H_{RO}(H_{com}^* || \cdots)$
6. Adversary wins if: $f = f^*$ and verification passes

Theorem 9 (Challenge Unpredictability):

For any PPT adversary making at most $q_H$ random oracle queries, the success probability is negligible: at most $q_H / p + 2^{-128}$.

Proof:

Challenge Binding: The challenge depends on commitment:

$$f = H_{RO}(H_{com}(a_{val}, r_{1}, \cdots) || root || \cdots)$$

Case 1: Adversary queries $H_{RO}$ on correct transcript before outputting proof

$\mathcal{A}_{2}$ makes queries $T_{1}, \cdots, T_{q_H}$ to $H_{RO}$ and receives responses $f_{1}, \cdots, f_{q_H}$.

For $\mathcal{A}_{2}$ to predict correctly, one query must equal the actual transcript:

$$\Pr[\exists i : T_i = H_{com}^* || \cdots] \leq \frac{q_H}{p}$$

since each $f_{i}$ is uniformly random in $\mathbb{F}_p$.

Case 2: Adversary does not query on correct transcript

$\mathcal{A}_{2}$ must guess $f = H_{RO}(T^*)$ without querying. In ROM, $f$ is information-theoretically hidden:

$$\Pr[f^* = f] = \frac{1}{p}$$

Case 3: Adversary creates collision

$\mathcal{A}_{2}$ finds $H_{com}' \neq H_{com}$ such that:

$$H_{RO}(H_{com}' || \cdots) = H_{RO}(H_{com} || \cdots)$$

Collision probability: $\leq 2^{-128}$ (Poseidon collision resistance)

Total probability: The adversary's success probability is bounded by the sum of these cases, which is negligible. Therefore, challenge prediction is infeasible. $\square$

---

Attack 3: Keystream Divergence Attack

Attack Strategy: Adversary uses different keystreams in ZKP vs. MPC decryption to claim incorrect amount.

Formal Game: Keystream Divergence Game

1. Adversary computes: Keystream for ZKP
2. MPC decrypts with: Real keystream derived from shared secret
3. Adversary Goal: Successful attack with divergent keystreams

Theorem 10 (Keystream Binding):

For any PPT adversary, the success probability is negligible: at most $1 / p + 2^{-128}$.

Proof:

Keystream Determination: Both ZKP and MPC use same keystream derivation:

$$\vec{k} = Rescue(S, n_{1}) \quad \text{where} \quad S = ECDH(a', D)$$

The nonce $n_{1}$ is public (included in transcript). The shared secret $S$ is uniquely determined by $a'$ and $D$.

Case 1: Adversary uses correct shared secret $S$

Then $\vec{k}_{zk} = \vec{k}_{real}$ by determinism of Rescue cipher. Attack fails.

Case 2: Adversary uses different shared secret $S'$ in ZKP

The commitment $H_{com}$ includes keystream components:

$$H_{com} = H_{Pos}(\cdots, k_{1}, k_{2}, \cdots)$$

For MPC to decrypt differently, the keystream used in the ZKP must differ from the keystream derived from the shared secret.

Constraint from polynomial check: Both the ZKP verification and MPC verification must agree on the polynomial evaluation $V$. However, if different keystreams are used, the MPC will decrypt to different values than what the ZKP claims. This creates a constraint that the adversary must satisfy, which requires predicting the challenge.

Equation: Setting both polynomial evaluations equal:

$$a_{fake} \cdot f + r_{fake} \cdot f^2 = (a_{fake} + \Delta k_{1}) \cdot f + (r_{fake} + \Delta k_{2}) \cdot f^2$$

Simplifying:

$$0 = \Delta k_{1} \cdot f + \Delta k_{2} \cdot f^2$$

If $\Delta k_{1} \neq 0$ or $\Delta k_{2} \neq 0$, then:

$$f \cdot (\Delta k_{1} + \Delta k_{2} \cdot f) = 0$$

Since $f$ is the output of a random oracle, the challenge takes a specific required value with probability only $1/p$.

Challenge Unpredictability: The challenge is derived from the random oracle applied to the commitment. For the adversary to satisfy the constraint, they must predict the random oracle output to match a specific value, which happens with probability $1/p$.

Case 3: Adversary breaks PRF security of Rescue

To use different keystreams without detection, the adversary must break the PRF security of Rescue cipher, which has security level $2^{128}$.

Conclusion:

$$\Pr[\mathcal{A}_{3} \text{ succeeds}] \leq \frac{1}{p} + 2^{-128} \approx 2^{-255} + 2^{-128} = \mathsf{negl}(\lambda)$$

Keystream divergence attacks are infeasible. $\square$

---

6.2 Scenario B: Passive Observer with Complete Plaintext Knowledge

Adversary Model: We consider a strong passive adversary $\mathcal{B}$ with the following capabilities:

1. Complete blockchain visibility: Monitors all on-chain data (Merkle root, nullifier hash, nonce, ciphertexts, polynomial evaluation, challenge, ZKP)
2. Plaintext space knowledge: Knows all possible amount values (the complete set of 64-bit unsigned integers)
3. Computational bounds: Cannot break underlying cryptographic primitives (DLP, CDH, PRF, ROM)

Adversary Goal: Determine which specific amount was encrypted in a given transaction.

This is a stronger model than typical IND-CPA security, as the adversary has perfect knowledge of the plaintext distribution and all possible values.

---

Novel Security Property: Polynomial Blinding Against Plaintext-Aware Adversaries

Theorem (Information-Theoretic Polynomial Blinding):

Even when the adversary knows all possible plaintext amounts $\mathcal{A} = \{0, 1, \ldots, 2^{64}-1\}$, the polynomial evaluation $V = a_{val} \cdot f + r_{1} \cdot f^2$ provides perfect information-theoretic hiding of $a_{val}$.

Formal Security Game:

1. Setup: Adversary receives complete plaintext space $\mathcal{A}$ and all on-chain data: $(C_{amount}, C_{poly}, V, f, \pi)$
2. Challenge: Challenger encrypts actual amount $a^* \in \mathcal{A}$
3. Adversary Task: Determine $a^*$ from observation of $V$
4. Adversary Wins: If correct identification

Theorem: For any adversary (even computationally unbounded), the probability of correctly identifying the actual amount is exactly $1 / 2^{64}$, which is no better than random guessing despite knowing all possible amounts.

Proof:

Key Observation: For any candidate amount $a_i \in \mathcal{A}$, we can write:

$$V = a_i \cdot f + r_i \cdot f^2$$

where $r_i$ is uniquely determined by the equation and lies in $\mathbb{F}_p$ (assuming $f \neq 0$, which holds except with negligible probability).

Consistency Analysis: The adversary observes polynomial evaluation $V$ and knows:

• Challenge $f$ (public)
• All possible amounts $\mathcal{A}$
• Ciphertexts $C_{amount}$, $C_{poly}$ (but without keystream, these are information-theoretically hidden)

For each candidate $a_i \in \mathcal{A}$, there exists a unique blinding factor $r_i$ that would produce the observed $V$. This can be solved directly from the polynomial equation.

Distribution Analysis: Since the actual blinding factor $r_1$ is chosen uniformly at random from $\mathbb{F}_p$, and $|\mathbb{F}_p| \gg |\mathcal{A}|$ (specifically, $p \approx 2^{255}$ while $|\mathcal{A}| = 2^{64}$), every candidate amount $a_i$ is equally consistent with the observed transcript.

Information-Theoretic Argument:

From the adversary's perspective:

• $V$ is a single field element
• $f$ is known
• For each $a_i \in \mathcal{A}$, there exists a valid $(a_i, r_i)$ pair

Since $r_1$ is uniformly distributed in $\mathbb{F}_p$ and provides perfect one-time pad blinding for the $r_1 \cdot f^2$ term, the observed $V$ is information-theoretically independent of which specific $a_{val} \in \mathcal{A}$ was chosen.

Conclusion: Even with complete knowledge of the plaintext space, the polynomial blinding mechanism provides perfect secrecy - the adversary gains zero information about the actual amount from observing $V$. $\square$

Practical Implication: This property is novel and critical for our protocol. Traditional IND-CPA security assumes the adversary doesn't know the plaintext distribution. Our polynomial commitment provides security even when the adversary:

1. Knows all possible amounts (full plaintext space)
2. Has unlimited computational power (information-theoretic security)
3. Can observe the polynomial evaluation $V$ (which is publicly visible on-chain)

---

7. Protocol Advantages

7.1 Communication Efficiency

Traditional Interactive Approach:

• Round 1: Prover → Verifier (commitment)
• Round 2: Verifier → Prover (challenge)
• Round 3: Prover → Verifier (response)

Non-Interactive Approach:

• Single transaction: Prover → Blockchain

The Non-Interactive transformation eliminates two-thirds of the communication rounds, significantly reducing latency and enabling seamless integration with blockchain transactions.

7.2 Circuit Efficiency

The 85-bit limb-based approach provides substantial efficiency improvements over naive bit-by-bit verification:

Key Advantages:

• Dramatically reduced constraint count for field operations
• More efficient Merkle path verification
• Significantly faster proof generation
• Lower memory requirements during proving

The limb-based Non-Native Arithmetic enables practical ZK proofs for cross-field operations that would otherwise be computationally prohibitive.

7.3 Security Properties

✅ Computational Soundness: $2^{-128}$ security under DLP and PRF assumptions

✅ Perfect Zero-Knowledge: Information-theoretic hiding of witness data

✅ Information-Theoretic Confidentiality: One-Time Pad encryption

✅ Anonymity Set: $2^{32}$ possible sources per claim

✅ Front-Running Resistance: Challenge derived from commitment

---

8. Integration with Umbra Architecture

8.1 Relationship to Individual Transaction Keys

The polynomial commitment protocol is used in conjunction with the Transaction Viewing Key (TVK) derivation system:

1. ITK Derivation: User derives ITK from MVK and timestamp
2. Linker Encryption: User encrypts metadata using Poseidon Cipher with ITK
3. MPC Encryption: User encrypts amount using Rescue Cipher with ECDH shared secret
4. Polynomial Commitment: User proves correctness of MPC encryption via this protocol

8.2 Relationship to MPC Network

The protocol enables the MPC Network to:

1. Verify Encryption: Confirm that ciphertext was correctly formed
2. Decrypt Amount: Use threshold decryption to reveal amount
3. Validate Polynomial: Check polynomial evaluation without learning blinding factor
4. Prevent Draining: Reject claims where amount exceeds deposited amount

---

9. Formal Security Parameters

---

10. References

1. Schwartz-Zippel Lemma: J. Schwartz (1980), R. Zippel (1979) - Polynomial identity testing
2. Fiat-Shamir Transform: A. Fiat, A. Shamir (1986) - How to prove yourself
3. Strong Fiat-Shamir: D. Bernhard et al. (2012) - Non-malleable Fiat-Shamir
4. Groth16: J. Groth (2016) - On the size of pairing-based non-interactive arguments
5. Rescue Cipher: Grassi et al. (2020) - Rescue: A family of efficient permutations
6. Poseidon Hash: Grassi et al. (2019) - Poseidon: A new hash function for zero-knowledge proof systems

For implementation details of specific components:

• Poseidon PRF Security
• Poseidon Cipher
• Rescue Cipher
• MPC Threat Model