Anastasia: Cinderella's Stepsister Turning Shabby X.509 Certificates into Elegant Anonymous Device Attestations with the Magic of Noir

Project description

Anastasia is a zero-knowledge system that proves the validity of X.509 certificate chains while revealing only the minimum information required.

Inspired by the prior work Cinderella ¹, which transformed X.509 certificates into anonymous credentials with zk-SNARKs, Anastasia extends the idea to make it practical on mobile devices, specifically Android Key Attestation.

⚠️ Work in progress!
No formal security review or performance tuning has been done.
Please don’t run this in production yet 🙂

Key contributions:

• Replaces Pinocchio (Linear PCP) with UltraHonk (Plonk-style proving system), enabling efficient prover on smartphones.
• Circuits written in Noir DSL, making them maintainable and extensible.
• Adds ECDSA signature verification, supporting Android’s native attestation certificates.
• Adopts a split-proof approach: instead of verifying an entire chain at once, each certificate is proved separately and linked via commitments, reducing memory and CPU load on mobile devices.
• Leverages Cinderella’s insight: parse outside the circuit, re-serialize inside. Thanks to the bijective property of ASN.1 DER encoding, we can prove correctness without costly parsing inside the circuit.

With Anastasia, we demonstrate that a smartphone can produce a zero-knowledge proof that its attested key truly originates from a Secure Element, without leaking identifiers that would enable tracking.

Originally built during ETHTokyo 2025 Hackathon (Presentation / Demo Video)

Technologies used

• Noir (circuit DSL)
  • nargo 1.0.0-beta.8
  • noirc 1.0.0-beta.8+b33131574388d836341cea9b6380f3b1a8493eb8
  • bb 1.0.0-nightly.20250723 (for UltraHonk / Plonk-style proving)
• Rust (ZK library, bindings)
  • rustc 1.87.0 (17067e9ac 2025-05-09)
  • arkworks 0.5.0
  • noir-rs 1.0.0-beta.8-3
• Mopro (bridging Noir/Rust to Kotlin)
  • mopro-cli 0.1.0 (d18eb3004 2025-09-14)
• Kotlin (Android SDK + demo app)
• Solidity (Verifier smart contract)
• ASN.1 DER / X.509 (certificate)

Basic architecture

Prover (Android)

• Generates attestation chain (Secure Element)
• Parses X.509 certs in Rust, re-serializes inside Noir circuit
• Produces ZK proof

Verifier (Smart Contract)

• Solidity contract (generated via Noir standard toolchain)
• Verifies ZK proof of certificate validity

Circuits

If you want to know how our circuits are constructed, check this.

Deployment

Smart Contract

• Solidity verifier contract deployed on testnet

Android

Follow these steps to build and run this Android app locally:

1. Clone the repository:

   git clone <repository_url>
   cd <cloned_directory>/android/v2

2. Open the project in Android Studio:

   • Launch Android Studio.
   • Select "Open an existing Android Studio project" and specify the android/v2 folder within the cloned directory.

3. Configuration for Proof Verification via Smart Contract (Optional):

   • The proofs generated by this app can be verified on a smart contract.

   • To enable this, set your Sepolia testnet API key in a file named secrets.properties located in the project root of your Android app.

   • Create secrets.properties by copying the template file secrets.defaults.properties.

     $ cp secrets.defaults.properties secrets.properties
     

     SEPOLIA_API_KEY=your-api-key
     

   • Note: Manage your API key securely. Be careful not to commit it directly to the repository.

   • Note: The file secrets.defaults.properties also contains an address used to identify the smart contract in addition to the API key entry, but you generally do not need to modify it.

4. Build and Run:

   • Wait for Android Studio to complete the project sync. (After setting the environment variable, a Gradle sync may be required. Press the elephant icon button in the toolbar.)
   • Select a connected physical device or an Android Emulator.
   • From the menu bar, select Run > Run 'app' or click the green play button in the toolbar.

This will build the app and run it on the selected device/emulator.

Footnotes

1. A. Delignat-Lavaud, C. Fournet, M. Kohlweiss and B. Parno, "Cinderella: Turning Shabby X.509 Certificates into Elegant Anonymous Credentials with the Magic of Verifiable Computation," 2016 IEEE Symposium on Security and Privacy (SP), San Jose, CA, USA, 2016, pp. 235-254, doi: 10.1109/SP.2016.22. keywords: {Protocols;Privacy;Authentication;Servers;Public key;PKI;Verifiable computation;TLS;Helios} ↩