Proving that a transaction is part of a block (or state) is crucial for security, scalability, and efficiency in blockchain systems. Traditionally, this is done using Merkle proofs, where a prover provides a path of hash siblings leading to the Merkle root. This method, however, has a fundamental flaw—it leaks information about the structure of the Merkle tree, which can compromise privacy and security.
What if we could prove membership without revealing the proof path or even the Merkle root itself?
This is where Sigma-based Merkle proofs come in.
Mathematically, we want to prove the following statement:
Given a transaction, prove that it exists in a Merkle tree without revealing the proof path or the root.
To define this formally, we introduce a membership relation between a transaction and a proof. If the given proof is valid for the transaction, then the relation holds true.
A Sigma protocol allows a prover to convince a verifier that a valid proof exists without revealing the proof itself.
To achieve this, we transform the proof into an elliptic curve cryptographic proof, using:
Elliptic Curve Discrete Logarithm (ECDLP): This ensures that the proof remains hidden while still being verifiable.
Non-interactive Fiat-Shamir transformation: Converts the proof into a form that does not require back-and-forth communication.
Cryptographic hash functions: Used to generate challenges for the proof verification process.
Merkle Tree Construction & Proof Encoding
A critical part of this process is being able to interpret the problem properly, in this context, it means encoding the merkle proofs into elliptic curve elements. Encoding the merkle proofs essentially enable our model to execute Sigma protocol with the merkle proof as a compatible secret key.
Constructing the Merkle Tree
A Merkle tree is a binary tree where each node is computed as the hash of its two child nodes. If we represent the left and right child hashes as
Hleft and Hright, the parent node’s hash is computed as:
This process is repeated until we compute the Merkle root, which serves as a cryptographic fingerprint of all transactions in the tree.
Extracting a Proof Path
To prove that a transaction is in the Merkle tree, we need a proof path, which consists of all sibling hashes needed to reconstruct the Merkle root. If a transaction is at a leaf node, its proof path consists of the hashes of its sibling nodes moving up the tree.
Mapping Proofs to Elliptic Curve Scalars
Instead of sending the proof path directly, we encode it as an elliptic curve secret. This is done in two steps:
Convert the proof path into a scalar value:
Each hash in the proof path is treated as a number.
These numbers are combined using a weighted sum, where each hash is multiplied by a power of two.
Finally, the sum is taken modulo a large prime number (the curve order).
Map this scalar value onto an elliptic curve point:
We take the computed scalar and multiply it by a generator point on the elliptic curve.
This results in an elliptic curve point that encapsulates the proof without revealing it.
This transformation ensures that the proof remains hidden (encapsulated) while still being verifiable using elliptic curve cryptographic techniques.
Sigma Protocol Implementation
A Sigma protocol consists of three steps:
Commitment: The prover generates a random commitment.
Challenge: The verifier issues a challenge based on the commitment.
Response: The prover responds with a proof, which is then verified.
The verifier checks that the prover's response satisfies a specific cryptographic equation, ensuring that the proof is valid without exposing any details about it.
A Practical Implementation
FUNCTION Sigma_Proof(merkle_proof, generator, curve_order):
#Step 1: Encode Merkle Proof as an Elliptic Curve (ECC) Scalar
s ← 0
FOR i FROM 0 TO LENGTH(merkle_proof) - 1:
s ← (s + merkle_proof[i] * 2^i) MOD curve_order
END FOR
X ← s * generator # Map scalar to elliptic curve point
# Step 2: Prover generates a random commitment
r ← Random_Scalar(curve_order)
t ← r * generator # Commitment point
# Step 3: Verifier generates a cryptographic challenge
e ← Hash_To_Scalar(t, X) # Non-interactive challenge
# Step 4: Prover computes the response
z ← (r + e * s) MOD curve_order
# Step 5: Verification check
IF generator z = t + X e:
RETURN TRUE # Proof is valid
ELSE:
RETURN FALSE # Proof is invalid
END IF
END FUNCTION
An Additional Tweak To Our Design.
To further enhance privacy, we introduce an experimental concept of a Merkle Product, which combines both the Merkle root and the Merkle proof into a single elliptic curve scalar. Instead of separately encoding the proof path as a scalar, we compute the product of the Merkle proof elements and the Merkle root, then map this product to an elliptic curve point. This transformation ensures that neither the Merkle proof nor the Merkle root is revealed during verification, achieving more zero-knowledge membership proofs. The verifier can still confirm membership without learning any information about the Merkle tree’s structure, individual proof elements, or the root itself.
Security and Efficiency Considerations
Security Analysis
Sigma proofs ensure both zero-knowledge privacy and strong security guarantees. The zero-knowledge property ensures that the verifier learns nothing about the Merkle proof or the tree structure, as the proof’s validity depends solely on the verifier’s challenge. This prevents any leakage of information beyond the fact that the statement is true. Meanwhile, soundness and unforgeability are maintained through elliptic curve cryptography; without knowledge of a valid proof path, a prover cannot construct a valid response. The hardness of the elliptic curve discrete logarithm problem (ECDLP) ensures that no adversary can forge a proof, making the system both secure and computationally infeasible to attack.
Efficiency Considerations
Sigma proofs offer significant efficiency advantages over traditional Merkle proofs. While Merkle proofs grow in size with the depth of the tree and require multiple hash operations for verification, Sigma proofs remain constant in size—just 32 bytes—and require only two elliptic curve operations for validation. This makes them far more efficient, particularly in blockchain applications such as light clients and rollups, where minimizing proof size and computational overhead is crucial. Additionally, Sigma proofs provide stronger privacy guarantees, as they do not reveal the proof path, unlike standard Merkle proofs, which expose tree structure information.
Limitations and Future Research
Our current design is greatly limited as it explores a very basic implementation of zero-knowledge proof-of-inclusion in a merkle tree.
Non-Interactive Proofs (Fiat-Shamir Transformation)
The protocol currently requires interaction between prover and verifier.
Applying the Fiat-Shamir transformation removes this need, making it fully non-interactive.
Post-Quantum Resistance
Since Sigma proofs rely on elliptic curve cryptography, they are vulnerable to quantum attacks.
Future implementations could explore lattice-based Sigma protocols for quantum security.
Aggregated Proofs for Scalability
Verifying multiple Sigma proofs efficiently is still an open challenge.
Batch verification techniques could help scale this protocol to large datasets.
Final Thoughts
Sigma-based Merkle (Or ZK-Merkle Proofs) proofs provide a scalable, privacy-enhancing alternative to traditional Merkle proofs. They:
✅ Reduce proof size to a constant
✅ Prevent inference attacks on Merkle trees
✅ Lower computational costs for verification
This method explores an experimental procedure that combines cryptographic commitments with zero-knowledge techniques, making it a potential tool for the next generation of scalable, trust-minimized blockchain systems.