Pedersen Commitments and Nilpotent Group Extensions
Zero-knowledge cash systems require a mechanism for parties to commit to transaction values without revealing those values to external observers. The commitment scheme must satisfy two fundamental properties:hiding (commitments reveal no information about the committed value) andbinding (the committer cannot change the committed value after creating the commitment).
The commitment layer serves as the cryptographic foundation that enables homomorphic operations on encrypted transaction amounts while maintaining perfect privacy. Unlike hash-based commitments that require revealing both the message and randomness during opening, Pedersen commitments support homomorphic operations that allow combining commitments without revealing underlying values.
Definition 1 (Cyclic Group): A group G is cyclic if there exists an element g ∈ G such that every element of G can be written as gk for some integer k. The element g is called a generator of G.
Definition 2 (Discrete Logarithm Problem): Given a cyclic group G of prime order q, a generator g, and an element h ∈ G, the discrete logarithm problem is to find the unique integer x ∈ {0, 1, ..., q-1} such that gx = h.
Definition 3 (Perfect Hiding): A commitment scheme is perfectly hiding if the commitment reveals no information about the committed message, even to a computationally unbounded adversary.
Definition 4 (Computational Binding): A commitment scheme is computationally binding if no polynomial-time adversary can find two different messages that produce the same commitment, except with negligible probability.
Setup: Let G be a cyclic group of prime order q where the discrete logarithm problem is hard. Choose two generators g, h ∈ G such that the discrete logarithm logg(h) is unknown to all parties.
To commit to a message m ∈ ℤq, choose a random r ∈ ℤq and compute C(m,r) = gmhr.
Theorem 1 (Perfect Hiding): The Pedersen commitment scheme is perfectly hiding.
Proof Sketch: For any two distinct messages m₀, m₁ ∈ ℤq, the distributions of commitments C(m₀, r) and C(m₁, r) are identical when r is chosen uniformly at random. Since h is a generator of G, the mapping r ↦ hr is a bijection from ℤq to G, making both distributions uniform over G.
Theorem 2 (Computational Binding): Under the discrete logarithm assumption, the Pedersen commitment scheme is computationally binding.
Proof Sketch: If an adversary can find (m₀, r₀) and (m₁, r₁) with m₀ ≠ m₁ such that gm₀hr₀ = gm₁hr₁, then rearranging gives gm₀-m₁ = hr₁-r₀. This allows computing logg(h), contradicting the discrete logarithm assumption.
Theorem 3 (Additive Homomorphism): Pedersen commitments are additively homomorphic:
This homomorphic property enables combining commitments to compute commitments to sums without revealing individual values.
The commitment C(m,r) reveals no information about the message m due to the uniform randomness r, providing unconditional privacy even against computationally unbounded adversaries.
Commitments can be combined algebraically, enabling privacy-preserving arithmetic operations on committed values without revealing the underlying amounts.
Modern implementations typically use elliptic curve groups for efficiency. The curve must be chosen carefully to ensure the discrete logarithm problem remains hard.
The generators g and h must be chosen such that no party knows logg(h). Common approaches include hash-to-curve and nothing-up-my-sleeve constructions.
The randomness r must be cryptographically secure. Poor randomness can completely break the hiding property.
Definition 5 (Nilpotent Group): A group G is nilpotent of class n if its lower central series terminates at step n: G = G₁ ⊃ G₂ ⊃ ... ⊃ Gn+1 = {1}, where Gi+1 = [Gi, G] and [Gi, G] denotes the subgroup generated by all commutators [g, h] = ghg-1h-1 with g ∈ Gi, h ∈ G.
Theorem 4 (Kahrobaei-Tortora-Tota Identity): In a nilpotent group N of class n > 1, for any elements g₁, ..., gn ∈ N and integers a₁, ..., an:
Definition 6 (Multilinear Map): A function e: Gn → GT is n-linear if for any a₁, ..., an ∈ ℤ and g₁, ..., gn ∈ G:
This construction enables multilinear cryptographic protocols without bilinear pairings, offering potential advantages in efficiency and security.
| Operation | Time Complexity | Space Complexity | Security Level |
|---|---|---|---|
| Commitment creation | O(log q) | O(1) | 128-bit |
| Commitment opening | O(log q) | O(1) | 128-bit |
| Homomorphic addition | O(1) | O(1) | 128-bit |
| Nilpotent commutation | O(n log q) | O(1) | Variable |
Special thanks to the community members and selfless volunteers who contributed reviews, feedback, and technical insights to make this documentation possible.