From Interaction to Independence: zkSNARKs for Transparent and Non-Interactive Remote Attestation

From Interaction to Independence: zkSNARKs for Transparent and Non-Interactive Remote Attestation

Speakers: Shahriar Ebrahimi

Conference: NDSS Symposium

YouTube: (no public video)

Overview

Remote Attestation (RA) is a cornerstone technology for verifying the integrity of software on remote devices, underpinning critical security protocols from secure boot to IoT security. However, traditional RA protocols are plagued by two significant limitations: a pervasive lack of transparency and an inherent interactive nature. Existing schemes often keep attestation verification details opaque, preventing independent validation by stakeholders, while their interactive demands restrict participation to a select, privileged few with access to confidential device data like pre-shared keys. This reliance on limited trusted entities and continuous interaction severely impedes scalability and broad adoption, particularly in expansive networks like the Internet of Things (IoT).

This talk introduces zRA, a groundbreaking Remote Attestation protocol designed to overcome these fundamental challenges. zRA leverages Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zkSNARKs) to achieve a non-interactive, transparent, and publicly provable attestation process. By eliminating the need for pre-shared keys or access to confidential data during verification, zRA fosters a truly trustless and open ecosystem, free from dependencies on online services or secure verifier-side storage. The protocol generates privacy-preserving attestation proofs of constant size, regardless of network complexity, which can be verified globally in an auditable manner.

The significance of zRA lies in its ability to democratize device integrity verification. It offers unparalleled scalability, particularly excelling in peer-to-peer and Pub/Sub network architectures, by moving away from costly interactive exchanges. The accompanying open-source prototype, implemented using Circom and deployed on Ethereum Sepolia, demonstrates zRA's practical deployability on public permissionless blockchains, showcasing its resilience against Denial-of-Service (DoS) attacks and its potential as an archival platform for attestation data.

Background

[▶ Watch: Introduction: Problems with Remote Attestation and zRA solution (0:00)]()

To appreciate the novelty of zRA, it's essential to understand the foundational cryptographic primitives it employs and the limitations of prior Remote Attestation (RA) work.

At its core, zRA builds upon Zero-Knowledge Proofs (ZKPs), cryptographic tools allowing a prover to convince a verifier that a statement is true without revealing any information beyond the truth of the statement itself. ZKPs are characterized by three properties: Soundness, ensuring only valid proofs are accepted; Completeness, guaranteeing valid statements can always be proven; and Zero-knowledge, preserving the confidentiality of the underlying data.

Expanding on ZKPs are zkSNARKs, which stand for Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge. These are an advanced form of ZKPs that produce proofs that are not only zero-knowledge but also succinct (small in size) and non-interactive (requiring no further communication between prover and verifier after an initial setup). This makes them exceptionally efficient for verifying computations, especially in decentralized and blockchain contexts. The zRA implementation specifically utilizes Groth16, a widely adopted zkSNARKs family member known for its efficiency.

Another crucial component is the Merkle Tree, a binary hash tree structure used for efficient and secure verification of large datasets. By recursively hashing data blocks and combining results, a single root hash is formed. A Merkle path provides a compact proof of inclusion for any specific leaf, allowing verification in logarithmic time complexity, O(log n). zRA employs the Poseidon hash function, optimized for zkSNARKs, for constructing these trees.

Finally, Commitment Schemes are cryptographic tools that enable a party to commit to a value, keeping it hidden initially but guaranteeing its integrity and allowing later public revelation. They provide hiding (value remains secret) and binding (value cannot be changed) properties, essential for zRA's trustless verification.

Previous RA protocols, as highlighted in the talk, suffer from several critical shortcomings that zRA aims to rectify:

• Verifier Prerequisites: Traditional RA often demands that verifiers possess privileged knowledge, such as device keys, initial states, or measurements. This dependency on a limited set of trusted entities creates a centralized trust model. zRA circumvents this by using commitment mechanisms: manufacturers commit to future responses for global challenges, and devices prove knowledge of the correct response without revealing it, enabling anyone to verify the claim without confidential data.
• Availability and Maintenance Costs: Interactive protocols necessitate continuous reliance on manufacturers or trusted servers throughout a device's lifecycle. Maintaining high availability for these centralized services is costly and complex. zRA eliminates this by offering independent, direct, and public verifiability, drastically reducing maintenance overheads and increasing network availability.
• Infrastructural and Device Assumptions: Many prior solutions rely on heavy infrastructures like permissioned blockchains (e.g., Hyperledger) or dedicated servers and databases, incurring substantial provisioning and maintenance overhead. zRA is designed to be lightweight and robust, platform-independent, and deployable even on permissionless blockchains like Bitcoin. Crucially, on the prover side, zRA requires only minimal trust anchors: Read-Only Memory (ROM) and a Memory Protection Unit (MPU), avoiding the need for specialized Trusted Execution Environments (TEEs) for proof generation.
• Distributed Trust Model: Prior RA models often concentrate trust in a few entities. zRA's transparency and public verifiability enable independent validation by any user. Furthermore, its setup phase can be distributed among multiple stakeholders using Multi-Party Computation (MPC), enhancing trust distribution and mitigating single points of failure.
• Scalability: Interactive RA protocols exhibit escalating communication costs as the number of devices and attestations grows. For instance, a broker in the PROVE 10 protocol could handle only about 150 attestations per second, reaching limits quickly. zRA, by contrast, is largely unaffected by the number of devices or attestations. All attestation requests are validated using zkSNARKs and global challenges, enabling direct, publicly verifiable proofs of knowledge without privilege or trust, offering superior scalability.

Key Findings

[▶ Watch: Background: Zero-Knowledge Proofs and zkSNARKs (2:20)]()

zRA introduces a paradigm shift in Remote Attestation, offering a suite of key findings and contributions that collectively address the long-standing limitations of transparency and interactivity. The core contributions highlighted in the talk are:

1. zRA: The First Transparent and Non-Interactive RA Protocol based on zkSNARKs: This is the foundational contribution. zRA fundamentally re-architects RA to be publicly verifiable, removing the need for privileged access or continuous interaction. This delivers:

• Trustless Public Verifiability: Anyone can verify an attestation without needing pre-shared keys, confidential device data, or reliance on a specific trusted server.
• Zero-Trust and Server-Free Operation: Post-setup, the protocol operates without a centralized, continuously online trusted server, improving resilience and reducing operational costs.
• Global Challenges: A system of globally broadcasted challenges ensures freshness and consistency across all devices.
• Platform-Independence: The protocol is designed to be lightweight and compatible with various platforms, including resource-constrained devices (with certain limitations discussed later).
• DoS Resilience: By offloading verification to a blockchain and eliminating interactive server dependencies, zRA inherently gains resilience against Denial-of-Service attacks.
• Distributed Trust: The setup phase can leverage Multi-Party Computation to distribute trust among multiple stakeholders, mitigating single points of failure.
• Privacy-Preserving Proofs: zkSNARKs ensure that sensitive internal device information is not revealed during the attestation process, only the truth of the statement.
• Constant Proof Size: A critical feature for scalability, the generated zero-knowledge attestation proofs maintain a constant size (approximately 805 Bytes), irrespective of network complexity or the number of attestations.

1. A Comprehensive Security Analysis: The paper provides a thorough analysis of zRA against various attack vectors, including Denial of Service, False Attestation, Replay Attacks, Message Manipulation, and attempts to manipulate zkSNARK circuit execution. This analysis demonstrates zRA's robustness under a defined adversary model, assuming the security of underlying cryptographic primitives and the trust anchor components (ROM and MPU).

1. A Practical and Open-Source Proof-of-Concept Implementation: To validate its practicality, the researchers developed and released an open-source prototype of zRA. This implementation, utilizing Circom, JavaScript, and Solidity, successfully demonstrates the protocol's deployability and functionality on public permissionless blockchains like Ethereum Sepolia, proving its real-world applicability and facilitating further research and adoption.

These findings collectively position zRA as a significant advancement in remote attestation, addressing critical shortcomings that have hindered the widespread, secure, and transparent deployment of integrity verification in diverse computing environments.

Technical Deep Dive

[▶ Watch: Background: Merkle Trees and Commitment Schemes (3:10)]()

The zRA protocol introduces a novel architecture for transparent and non-interactive Remote Attestation, structured around four distinct phases: Setup, Update Global Challenge, Attestation, and Verification.

1. Setup Phase

This foundational phase is performed offline by the manufacturer once. Its primary goal is to pre-compute and commit to all future attestation responses.

• Response Generation: For each device k, the manufacturer generates a set of m future responses R_k = {r_1, r_2, ..., r_m} corresponding to a sequence of pseudo-random challenges C = {C_1, C_2, ..., C_m}. These responses r_i are specific to a device's public key P_k and a challenge C_i, derived from a calcResp(P_k, dev_k, C_i) function which embodies the attestation logic.
• Commitment Calculation: For each device k and each challenge C_i, the manufacturer computes a commitment L_k,i = H_pos3(P_k || r_i || C_i). Here, H_pos3 denotes the Poseidon hash function optimized for zkSNARKs, taking the device's public key, the calculated response, and the challenge as inputs.
• Merkle Tree Construction:
• First, for each device k, a device-specific Merkle tree T_k is built, where the leaves are the m commitment values L_k,1, ..., L_k,m. This T_k has a height of log m.
• Second, an overarching Merkle tree T is constructed. The leaves of this final tree T are the roots (RT_k) of all the previously generated device-specific Merkle trees T_k. If there are n devices, this tree T has n leaves and a height of log n.
• Final Structure: The resulting structure is a nested Merkle tree with a total height of log m + log n. This ensures a unique path for every attestation of every device. Crucially, the leaves of this final tree T are commitments to P_k || r_i || C_i, but the Merkle tree itself does not reveal the confidential challenges C or responses R. Therefore, the final Merkle tree T contains no confidential data and its root (RT) can be publicly disclosed. The sequence of challenges C, however, is kept confidential and revealed periodically.

2. Update Global Challenge Phase

To ensure freshness and introduce timed randomness, the challenges C_i are not revealed all at once. Instead, individual challenges c_i are periodically published, one at a time. A blockchain is utilized for this purpose, where the manufacturer publishes the latest challenge, making it universally and unconditionally accessible to all devices, along with all previously published challenges.

3. Attestation Phase

This phase is executed by the prover (the device) when it needs to attest its integrity.

• Challenge Retrieval: The device queries the blockchain to retrieve the latest global challenge c_i.
• Evidence Computation: Using c_i and its internal state, the device computes its attestation evidence r_i via the devCalcResp() function. This function is designed to be flexible and independent of the specific attestation method.
• zkSNARK Proof Generation: The device then constructs a zkSNARK proof (π). This proof asserts the device's knowledge of r_i such that its commitment l = H_pos3(P_k || r_i || C_i) belongs to the manufacturer's publicly committed Merkle tree T with root RT.
• The core of this process takes place within a verifiable circuit. This circuit calculates leaf = H_pos3(P_k || r_i || C_i). It then iteratively hashes this leaf up the provided Merkle path O(T, i) to reconstruct a root value. It asserts that this reconstructed root value matches the publicly known RT.
• The genVCProof() function then generates the zkSNARK proof π. It's vital that the entire ZK circuit (computing leaf and verifying the Merkle path) can be executed in untrusted environments, as its inputs (public key, challenge, response, Merkle path) are not confidential.
• Signing: After generating π, the prover signs the tuple (π, C_i, P_k, RT) with its private key sk. The private key sk is the only confidential variable used by the device, and its role is exclusively for signing, not for proof generation. This sk is assumed to be securely stored within the device's trust anchor (ROM/MPU).
• Submission: Finally, the prover submits the proof π, the public inputs (C_i, P_k, RT), and the digital signature sign to a chosen network, such as a blockchain. This submission is non-interactive and publicly verifiable.

4. Verification Phase

This phase is designed to be straightforward, autonomous, and publicly accessible, typically implemented as a smart contract on a blockchain.

The verifier performs four critical checks:

1. zkSNARK Proof Validity: Verifies the integrity and correctness of π using verifyZkSnarks(dv, π, RT, C_i, P_k). This ensures the device correctly computed r_i and that its commitment is indeed part of the manufacturer's Merkle tree.
2. Prover Authenticity: Checks if the public key P_k used in the proof matches the public address of the prover (e.g., msg.sender on a blockchain), verified via recoverPubKey(sign).
3. Merkle Root Integrity: Confirms that RT is a valid Merkle root previously published by the manufacturer, ensuring the proof originates from a legitimate source.
4. Challenge Freshness: Ensures that c_i in the proof corresponds to the latestChallenge published by the manufacturer, preventing replay attacks with outdated challenges.

If all four checks pass, the attestation is considered valid.

Trust Distribution

While the setup phase generates challenges offline, relying on a single manufacturer to periodically publish them could still be a single point of failure. To enhance robustness, zRA proposes a trusted setup ceremony for generating challenges. This involves multiple stakeholders participating in a (t,n)-threshold random sequence generation. To reconstruct any challenge C_ti, at least t out of n participants must publish their share. This significantly boosts availability (up to n-t participants can be unavailable) and strengthens freshness (requiring t participants to collude to reveal future challenges). This distributed model offers flexibility for different groups of devices to have their own designated stakeholders.

Implementation Details

The zRA prototype is open-source, available on GitHub and Zenodo, and built with:

• Circom 16: For creating the verifiable zkSNARK circuits.
• JavaScript: For client and manufacturer scripts.
• Solidity 17: For autonomous verifier smart contracts.
• Full compatibility with Ethereum blockchain, demonstrated on Ethereum Sepolia Testnet 18.

Two main Circom Circuits are implemented:

1. MerkleTreeChecker (Listing 1): Adapted from the audited Tornado-Cash 31 code, this circuit verifies the membership of a leaf in a Merkle tree given the root, path elements, and path indices. It iteratively hashes up the path to reconstruct the root and asserts its match.
2. Attest (Listing 2): This is the top-level attestation circuit. It computes hashValue = H_pos3(pubAddr || challenge || response), which serves as the commitment. This hashValue is then passed as the leaf input to the MerkleTreeChecker circuit. Instantiated as main(20) for a Merkle tree height of 20, it ensures the commitment is part of the manufacturer's tree.

The Solidity Smart Contract, PublicAttestor (Listing 3), acts as an autonomous and trustless verifier, directly implementing Algorithm 3. Its attest function takes zkSNARK proof components and public inputs, then executes the four verification checks described above. Any failed check causes the transaction to revert. The Groth16Verifier class is generated using the snarkjs tool. Additional functions, publishChallenge and addRoot, allow the manufacturer to update the latestChallenge and validRoots respectively.

Demo / Proof of Concept

[▶ Watch: zRA's impact on availability and maintenance costs (4:30)]()

The practical viability of zRA was demonstrated through an open-source prototype, publicly available on GitHub and Zenodo. This implementation showcases the full functionality of the zRA protocol, leveraging a combination of cutting-edge technologies to interact with public blockchain networks.

The prototype is built using Circom 16 for defining the zero-knowledge circuits, JavaScript for client-side and manufacturer-side scripting, and Solidity 17 for the autonomous verifier smart contracts. Its full compatibility with the Ethereum blockchain ecosystem was validated through successful deployments and experimental transactions on the Ethereum Sepolia Testnet 18.

To rigorously evaluate the prototype's performance and practicality, benchmarks were conducted across a range of platforms, including a high-end Dell Latitude 5531 laptop (Intel CPU), a resource-constrained Raspberry Pi Zero 2W (ARM Cortex-A processor), and an ASUS Tinkerboard. These diverse platforms highlight zRA's adaptability while also revealing performance trade-offs.

Prover Storage Requirements

One of zRA's most compelling features is its remarkably small memory footprint on the prover (device) side. For an extreme scenario involving a Merkle tree height of 40 (which can support 1 million devices each attested 1 million times), the Circom circuit required less than 10K constraints. This translates to:

• A proving key size of only 6.0 MB.
• A witness size of 321 KB.
• Crucially, the final proof size (π) remains constant at approximately 805 Bytes, irrespective of the Merkle tree height or the total number of attestations. This constant, compact proof size is a significant advantage for network efficiency and scalability.

Witness and Proof Generation Time

The time taken by a device to generate a new witness and the corresponding zkSNARK proof for each attestation varies significantly by hardware:

• On the Dell Latitude 5531 laptop (Intel CPU), proof generation for a height 40 tree took less than 4 milliseconds. This demonstrates near real-time attestation on general-purpose computing platforms.
• On the Raspberry Pi Zero 2W (ARM Cortex-A processor), the same process took around 25 seconds.
• On the ASUS Tinkerboard, it was approximately 12 seconds.

The substantial difference between Intel and ARM platforms is attributed to the availability of optimized witness generators for Intel CPUs. While 25 seconds for a single attestation on a constrained device might appear high, it is a one-time, independent computation per attestation and does not impede the overall system's scalability or parallel processing capacity.

Communication and Storage Costs

Comparative analysis with prior interactive RA protocols like SCRAPS 2 and PROVE 10 vividly illustrates zRA's superior efficiency:

• Communication Cost and Scalability: Figures 6 and 7 in the original paper underscore zRA's advantages. For 10,000 devices, the manufacturer only needs to publish m global challenges (m messages) for each attestation interval, a cost independent of the number of devices. In sharp contrast, previous interactive protocols show communication costs that escalate dramatically with the number of attestations and devices. For example, to handle 10,000 attestations from 1 million devices, previous protocols would necessitate entities like brokers or proxy verifiers transmitting over 200 billion messages. zRA completely avoids such communication bottlenecks, maintaining a constant communication overhead from the manufacturer irrespective of device count.
• Storage Cost: Traditional RA demands privileged access to secure databases and costly storage infrastructure. zRA, due to its transparency, has minimal private storage needs. The manufacturer only stores the sequence of challenges C, determined solely by the number of attestations (m), not devices. For a scenario of 1 million devices attested 1 million times, this amounts to roughly 3 MB (1,000,000 challenges * 32 Bytes/challenge). Each device needs about 6 MB to access its relevant Merkle tree for path proofs. Public data, like valid Merkle roots, is efficiently managed by the blockchain.

Computational Cost

While zRA introduces a higher computational load on the prover side compared to interactive approaches (e.g., a Cortex M-3 in SCRAPS 2 takes 1.07 seconds, while a Cortex-A53 in zRA takes 21.8 seconds), this cost is borne independently by each device and does not hinder overall system scalability. On general-purpose CPUs, proof generation is exceptionally fast (hundreds of milliseconds). For resource-constrained ARM Cortex series, optimizing ZK circuits remains a challenge, with the Tinkerboard (A17) showing 2x better performance than Raspberry Pi Zero (A53) but consuming 3x more energy. Despite higher prover-side computation, zRA's reduced communication interactions often lead to lower overall energy consumption.

Defensive Implications

[▶ Watch: zRA's reduced infrastructure and device assumptions (4:55)]()

The introduction of zRA carries significant implications for defenders seeking to bolster the security and integrity of remote devices, particularly in distributed and resource-constrained environments.

1. Embrace Non-Interactive Integrity Verification: Defenders should recognize the value of zRA's non-interactive nature. By eliminating the need for continuous communication with a centralized verifier, organizations can deploy more resilient and scalable attestation systems. This is especially pertinent for large-scale IoT deployments where interactive protocols quickly become unmanageable due to communication overhead and server load.
2. Reduce Reliance on Centralized Trust: zRA fundamentally shifts the trust model away from single, privileged servers. Defenders can leverage this to create more robust systems less susceptible to single points of failure and Denial-of-Service (DoS) attacks. By utilizing public blockchains as a trust anchor for challenge publication and proof verification, the inherent DoS countermeasures of these decentralized networks can be exploited.
3. Implement Distributed Trust for Critical Operations: For the generation of attestation challenges, defenders should explore implementing the proposed (t,n)-threshold trusted setup ceremony. This distributes trust among multiple stakeholders, enhancing the availability of challenges and making it significantly harder for adversaries to compromise the freshness of attestations or manipulate future challenges.
4. Leverage Public Blockchains as a Secure, Transparent Ledger: The use of blockchain for publishing global challenges and verifying attestation proofs provides a publicly auditable and immutable record. Defenders can use this transparency to allow any stakeholder to independently validate device integrity, fostering greater trust and accountability within their ecosystems. This also provides an archival platform for attestation data.
5. Strategize for Software Updates and Rollback Protection: zRA's mechanism for invalidating old Merkle roots with new challenges provides a robust defense against rollback attacks. Manufacturers can publish new binaries, update smart contracts, and issue fresh challenges, effectively rendering proofs generated against outdated software versions invalid. Defenders should integrate this capability into their software update and patch management strategies.
6. Understand and Mitigate Prover-Side Computational Costs: While zRA offers substantial system-level benefits, defenders must be aware of the increased computational load on individual devices for zkSNARK proof generation. For extremely constrained devices (e.g., 8-bit/16-bit AVR or some ARM Cortex-M series), zRA might be infeasible without significant hardware acceleration or the adoption of secure outsourcing of proof generation. When designing systems, it's crucial to select devices with sufficient processing power for the required attestation frequency or explore future optimizations like STARKs or dedicated hardware solutions.
7. Ensure Trust Anchor Integrity: The security of zRA, like many RA protocols, fundamentally relies on the integrity of the device's trust anchor (ROM and MPU). Defenders must ensure these components are tamper-evident and protected against physical attacks, as the private key sk used for signing the final attestation message resides within this trusted boundary.
8. Adapt Attestation Intervals to Blockchain Block-times: While zRA is resilient, the time window between blockchain blocks presents a potential vulnerability where a device could be compromised before its attestation is recorded. Defenders should adjust their minimum attestation intervals based on the target blockchain's block-time (e.g., Ethereum's ~10 seconds) to align with application security requirements.

By thoughtfully integrating zRA's principles and architectural components, defenders can build a more secure, transparent, and scalable remote attestation framework, particularly well-suited for the evolving landscape of IoT and peer-to-peer networks.

Key Takeaways

• Solving Core RA Limitations: zRA addresses the critical issues of transparency and interactivity in traditional Remote Attestation (RA) protocols by leveraging zkSNARKs.
• Non-Interactive & Publicly Verifiable: The protocol enables devices to generate constant-size (approx. 805 Bytes), privacy-preserving, non-interactive attestation proofs that can be verified by anyone, anywhere, without requiring pre-shared keys or confidential data.
• Enhanced Scalability and DoS Resilience: zRA significantly reduces communication and storage costs compared to interactive RA, offering superior scalability, especially in Pub/Sub and peer-to-peer networks, and inherent resilience against Denial-of-Service attacks by utilizing blockchain for verification.
• Minimal Trust Anchors: On the prover side, zRA requires only fundamental trust anchors like Read-Only Memory (ROM) and a Memory Protection Unit (MPU), without needing specialized Trusted Execution Environments (TEEs) for proof generation.
• Practical Implementation & Blockchain Integration: An open-source prototype using Circom and Solidity has been successfully deployed and verified on the Ethereum Sepolia Testnet, demonstrating its practical applicability and compatibility with public permissionless blockchains.
• Challenges for Extremely Constrained Devices: While highly efficient on general-purpose CPUs (sub-4ms proof generation), zkSNARK proof generation can still be computationally intensive for extremely resource-constrained microcontrollers, highlighting an area for future optimization through hardware solutions or alternative proving mechanisms like STARKs.

About the Speaker(s)

Shahriar Ebrahimi is a researcher in the field of cybersecurity, as evidenced by his presentation on zRA at the NDSS Symposium. His work focuses on applying advanced cryptographic techniques, specifically Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zkSNARKs), to solve critical security challenges such as remote attestation. He demonstrates expertise in designing and implementing secure protocols for decentralized systems and blockchain technology, aiming to enhance transparency, scalability, and trust distribution in device integrity verification.