💻 computer science

Efficient Zero-Knowledge Proofs for Set Membership in Blockchain-Based Sensor Networks: A Novel OR-Aggregation Approach

This paper proposes a novel OR-aggregation approach for efficient zero-knowledge set membership proofs tailored to resource-constrained blockchain-based sensor networks, demonstrating significant improvements in proof size, generation time, and verification efficiency compared to existing methods.

Original authors: Oleksandr Kuznetsov, Emanuele Frontoni, Marco Arnesano, Kateryna Kuznetsova

Published 2026-04-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Oleksandr Kuznetsov, Emanuele Frontoni, Marco Arnesano, Kateryna Kuznetsova

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are part of a massive, exclusive club. The club is so big that it has millions of members, and it's run on a public ledger (like a blockchain) that everyone can see. Now, imagine you are a tiny, battery-powered sensor device (like a smart thermostat or a temperature gauge) that needs to prove to the club, "Yes, I am a real member," without revealing your name, your address, or any other secret about you.

This is the problem the paper solves.

The Problem: The "Heavy Backpack"

In the past, to prove you belong to a club of 1 million people, you had to carry a "backpack" of proof.

The Old Way (Merkle Trees): Imagine the club gives you a receipt for your membership. But to prove it's valid, you also have to carry receipts for every single step up the ladder to the top of the club. If the club has 1 million members, your backpack gets heavy. It grows bigger as the club gets bigger.
The Sensor Problem: Your sensor device is tiny. It has a small battery and a weak processor. Carrying a heavy, growing backpack drains its battery and slows it down. It's like asking a bicycle to carry a cargo ship.

The Solution: The "Magic OR-Aggregation"

The authors of this paper invented a new trick called OR-Aggregation. Think of it as a magic spell that turns that heavy backpack into a single, tiny postcard, no matter how big the club is.

Here is how it works, using a simple analogy:

1. The "Club Roster" vs. The "Magic List"

Imagine the club has a list of all members.

Old Method: To prove you are on the list, you have to show the path from your name to the top of the list. The longer the list, the longer the path.
New Method (OR-Aggregation): The club creates a single, giant "Magic Hash" (a digital fingerprint) that represents the entire list combined into one number.

2. The "OR" Trick

Now, you need to prove you are on that list without saying which number on the list is yours.

Imagine the club has 1 million lockers. You have the key to one specific locker (Locker #45,201).
Instead of showing the key to Locker #45,201, you use a clever math trick (the "OR" logic). You prove to the guard: "I have the key to Locker #1 OR I have the key to Locker #2 OR ... OR I have the key to Locker #45,201."
Because of the magic of Zero-Knowledge Proofs, the guard can verify that you do have a key to one of the lockers, but they cannot tell which one. They just know you are telling the truth.

3. The Result: Constant Size

The most amazing part? Whether the club has 10 members or 100 million members, your "postcard" proof is always the exact same size.

Old Way: 10 members = small note. 100 million members = a giant scroll.
New Way: 10 members = small note. 100 million members = still the same small note.

Why This Matters for Sensors and IoT

The paper tested this on real computers and simulated tiny sensor devices. Here is what they found:

Saving Bandwidth (The Data Pipe): In a city with millions of sensors, sending data is like trying to pour water through a tiny straw. The old methods tried to pour a firehose of data. The new method pours just a single drop. This saves massive amounts of internet data.
Saving Battery (The Energy): Because the sensors don't have to do heavy math or send huge files, they use less energy. This means a sensor battery could last for years instead of months.
Speed: Verifying the proof is instant. It doesn't matter if the club has 10 people or 1 billion; the check takes the same split second.

The Comparison: A Race

The authors compared their new method against the current "champions" of the crypto world (like Merkle Trees, Verkle Trees, and STARKs).

For small groups: The old methods are slightly faster to create the proof.
For huge groups (like a whole city): The new method wins by a landslide. It creates a proof that is 18,000 times smaller than the old methods when checking 1,000 items at once.

The Bottom Line

This paper introduces a new way for tiny, weak devices to prove they belong to a huge, secure group without getting tired, running out of battery, or clogging up the internet.

It's like upgrading from a horse-drawn carriage (the old methods) to a high-speed bullet train (the new OR-Aggregation) for the specific job of checking IDs in a massive crowd. It makes the future of the "Internet of Things" (where everything from fridges to traffic lights talks to each other) much more practical, private, and efficient.

1. Problem Statement

The integration of blockchain technology with Internet of Things (IoT) sensor networks promises secure, transparent, and decentralized data management. However, a critical bottleneck exists in efficient set membership proofs within resource-constrained environments.

Current Limitations: Existing methods like Merkle Trees, cryptographic accumulators, and standard Zero-Knowledge Proofs (e.g., zk-SNARKs) suffer from scalability issues.
- Merkle Trees: Proof size grows logarithmically ( $O(\log n)$ ) with the set size, consuming excessive bandwidth and storage.
- Accumulators: Often require trusted setups or computationally intensive witness updates, which are unsuitable for low-power sensor nodes.
- General ZKPs: High computational overhead and complex setup procedures make them difficult to deploy on edge devices.
The Gap: There is a lack of a solution that offers constant-size proofs, low computational overhead, and strong privacy guarantees specifically tailored for large-scale, resource-constrained blockchain-based sensor networks.

2. Methodology: The OR-Aggregation Approach

The authors propose a novel OR-aggregation technique for zero-knowledge set membership proofs. This method allows a prover to demonstrate that an element $x$ belongs to a set $S = \{x_1, x_2, ..., x_n\}$ without revealing which specific element it is or any other information about the set.

Core Technical Mechanism

The approach leverages Sigma protocols and OR-composition combined with cryptographic aggregation:

Aggregation:
- RSA-based: Individual set elements are aggregated into a single commitment using modular exponentiation ( $y = \prod g^{x_i} \mod N$ ).
- Elliptic Curve (EC)-based: Elements are aggregated via scalar multiplication ( $Y = \sum x_i G$ ).
OR-Composition: The prover uses an OR-proof to demonstrate knowledge of the discrete logarithm (for EC) or an $e$ -th root (for RSA) for one of the individual components within the aggregated commitment.
Zero-Knowledge Property: The protocol proves membership without revealing the specific index or value of the element, ensuring privacy.

Protocol Specification

The system follows a standard three-move Sigma protocol structure:

Setup: Generates public parameters (modulus $N$ or curve parameters) and the aggregated commitment for the set.
Proof Generation: The prover selects a random challenge, computes a commitment, receives a verifier challenge, and calculates a response based on the specific element they know.
Verification: The verifier checks the consistency of the response against the aggregated commitment and the challenge.

3. Key Contributions

Novel Protocol: Introduction of an OR-aggregation protocol applicable to both RSA and Elliptic Curve cryptography (specifically tested on Ed25519, secp256r1, BLS12-381, etc.).
Constant Complexity: Theoretical proof that proof size and verification time are constant ( $O(1)$ ), independent of the set size $n$ . This is a significant departure from the logarithmic scaling of Merkle trees.
Formal Security Analysis: Rigorous proofs demonstrating Completeness, Soundness (relying on the RSA problem or ECDLP), and Zero-Knowledge properties.
Optimized Implementation: Development of specific optimization techniques for resource-constrained devices, including:
- Precomputed tables for scalar multiplication.
- Sliding window exponentiation.
- Memory-efficient data structures (bit-packing).
- Batch verification strategies.
Comprehensive Evaluation: Extensive experimental comparison against Patricia-Merkle trees, Verkle trees, and STARKs.

4. Experimental Results

The authors evaluated the approach on a standard desktop environment (AMD Ryzen 7) using Python and pycryptodome, comparing it against Patricia-Merkle trees, Verkle trees, and STARKs.

Key Performance Metrics

Proof Size:
- OR-Aggregation: Constant size regardless of set size (e.g., 160 bytes for Ed25519, 224 bytes for BLS12-381).
- Patricia-Merkle: Grows logarithmically. For a set of 300 million elements, Merkle proofs are ~2.9 KB, whereas OR-aggregation remains 160 bytes.
- STARKs: Significantly larger (e.g., ~174 KB for 1M elements).
Verification Time:
- OR-Aggregation: Constant time (~0.012s for Ed25519).
- Batch Verification: In a scenario verifying 100,000 elements, Patricia-Merkle requires transferring 292 MB of data and takes ~17.6s. OR-aggregation requires only 160 bytes and takes 0.012s (constant).
Generation Time:
- While OR-aggregation generation is slightly slower than Merkle trees for very small sets due to the complexity of the OR-proof, it remains constant. For large sets, the trade-off is favorable due to the massive reduction in transmission overhead.

Comparative Advantage

Scalability: The method outperforms all competitors in large-scale scenarios (millions of elements).
Bandwidth Efficiency: Reduces data transfer by factors of 18,000x in batch verification scenarios compared to Merkle trees.
Resource Suitability: Ideal for IoT devices where bandwidth and battery life are critical constraints.

5. Significance and Implications

This research provides a scalable, privacy-preserving solution for blockchain-based sensor networks, addressing the "trilemma" of scalability, security, and decentralization in IoT contexts.

IoT & Edge Computing: The constant proof size and verification time make it feasible for battery-powered sensors to interact with blockchains without draining resources or clogging network bandwidth.
Light Clients: Enables the creation of "ultra-light" blockchain clients that can verify state changes without storing the entire ledger.
Applications:
- Access Control: Verifying device authorization without revealing identity.
- Supply Chain: Proving product batch legitimacy.
- Federated Learning: Verifying participation in training rounds.
- Smart Cities: Real-time verification of traffic or utility data.
Future Outlook: While the current method is specialized for set membership (unlike STARKs which handle arbitrary computations), it fills a critical niche for high-volume, low-latency IoT applications. Future work may focus on hardware acceleration for proof generation and post-quantum security considerations.

In conclusion, the proposed OR-aggregation approach represents a paradigm shift in handling set membership proofs for large-scale distributed systems, offering a practical path toward the widespread adoption of blockchain in the IoT ecosystem.