SNARKs On A Card

This research explores methods for efficiently verifying zero-knowledge (ZK) proofs on resource-constrained devices, such as secure elements. Our focus is on the Groth16 proof system over the BN254 curve, a widely adopted standard in ZK systems like SNARKs and STARKs, largely due to its near-optimality and support from Ethereum's EIP-197 precompiles. We target a scenario where a powerful but potentially malicious host device delivers proofs to a secure element for verification.

• We took an NXP J3R180 JCOP4 smart card and, using the JCMathLib library to abuse the card's RSA crypto-accelerator for general-purpose modular arithmetic, implemented the final exponentiation step of a BN254 pairing. A pair of FP12 multiplications took 34 seconds, and we calculated that a full verification would take nearly two days.
• We tested the feasibility of a delegated pairing computation algorithm called DCKKS20 using a faster platform, the Ledger Flex. We used the Ledger SDK's crypto APIs and simulated the performance of the client side of the delegation protocol. It brought the verification time down from days to just 72 seconds -- a 5500x speedup, but still too slow for a good user experience.
• We identified a new pairing delegation algorithm, AmorE, which promised another 3x speedup. We tried to integrate the authors' own implementation from the RELIC cryptographic toolkit, but ran into a wall with cross-compilation issues for the embedded target and couldn't get real-world data by the deadline.
• We document promising avenues for future research, including the intriguing possibility of delegating the verification of the verified pairing delegation using extremely tiny STARKs.