Grant Proposal - Zero Knowledge Location Proofs

# Grant Proposal - Zero Knowledge Location Proofs ## Project Abstract   In recent years, location-based services have become ubiquitous. However, despite their ubiquity in the current era of digital connectivity, these developments also raise significant privacy concerns, as location data can reveal sensitive information about an individual's habits and preferences.  With this project we aim to initiate research on Zero Knowledge Location Proofs (ZKLP), a mechanism to provide proofs of physical location, whilst protecting personalized location information. With ZKLP, users can efficiently prove that they are within a specific geographical region whilst obfuscating their exact location for utility and privacy. The proof of obfuscated location can be verified by any party, including smart contract applications, with little cost. ## Objectives  With this project, the objectives we are hoping to accomplish are fourfold: 1. **Understanding \& Formalizing Zero-Knowledge Location Proofs:** Whereas several privacy-preserving location services exist, Zero-Knowledge Proofs have thus far not been rigorously investigated for proving physical locations. We aim to provide a comprehensive formalization of Zero-Knowledge Location Proofs by relying on already existing algorithms for mapping two dimensional locations to a three dimensional sphere. By doing so, we will rely on [Discrete Global Grid Systems (DGGS)](https://en.wikipedia.org/wiki/Discrete_global_grid). DGGS divide the Earth into a hierarchy of progressively finer resolution grids. By formalizing Zero-Knowledge Location Proofs, we will enable structured reasoning about the concrete, and configurable, privacy provisions that can be obtained with the ZKLP paradigm.    2. **Optimizing SNARKs for IEEE 754 compliant floating-point (FP) operations:** When relying on DGGS, we need to handle large values (e.g., $\sqrt{7}^{\text{resolution}}$, where *resolution* is the hexagonal resolution) and small values (e.g., the product of $\sin({\theta})$ and $\cos({\theta})$) simultaneously, resulting in either increased data size or reduced accuracy in fixed-point representation. Therefore, we aim to introduce optimized circuits for primitive floating-point operations, compliant with the [IEEE 754](https://en.wikipedia.org/wiki/IEEE_754) floating-point standard. The introduced optimizations are of independent interest, and can be used in arbitrary, orthogonal application that leverage Zero-Knowledge Proofs over fractional numbers (such as trustless Machine Learning inference, i.e., "Zero-Knowledge Machine Learning").  3. **Developing a Proof of Concept of ZKLP for practical applications:** To demonstrate the power of Zero-Knowledge Proofs (and specifically SNARKs) for privacy-preserving location proofs, we aim to implement privacy-preserving peer-to-peer proximity testing, which evaluates the minimal distance to a peer without forfeiting privacy. The goal is to leverage SNARKs, which are non-interactive, to provide a peer-to-peer solution for evaluating the distance to other peers. A prover can broadcast a proof, whereas the verifier can evaluate the minimal distance to a large amount of provers due to the succinct properties of SNARKs.  4. **(Optional) Authenticated Locations, compatible with the ZKLP paradigm:** While the above objectives are useful independently, we will further investigate how to obtain authenticated location information. This is difficult, as currently GPS signals are not authenticated and can trivially be spoofed. Even more so, if satellite signals *would be* authenticated, the problem of authentic location information would not be solved, as a recipient of a location could simply hand the authenticated location information to anyone else. We aim to obtain a system model, which incorporates a combination of trusted hardware, secure computation and facial recognition, to obtain a *proof of personhood*, computable on consumer hardware.    We will measure the success of our project by the following criteria: - **Number of Constraints:** We will minimize the number of constraints per floating-point operation (expected to be $<100$ for all primitive operations) and the number of constraints per ZKLP proof (expected to be $<10^5$) with the Groth16 proof system. We will further evaluate the cost of verifying a ZKLP in an Ethereum smart contract on a Layer1 / Layer2 solution, based on Proof Systems with per-circuit (Groth16), universal (Plonk) and transparent setup (FRI-based).  - **Compatibility:** We aim to construct arithmetic circuits for floating-point operations that are fully compliant with IEEE 754. Our circuits for ZKLP should also be compatible with DGSS.  - **Performance of the Proof of Concept:** We expect the prover runtime for the PoC application to be $<0.5$ seconds on consumer hardware. Further, we will evaluate the number of proximity proofs a verifier can evaluate per second, given our PoC, which should be $>100$. ## Outcomes  This project will contribute to the greater Ethereum ecosystem by providing a solid foundation for privacy-preserving location-based services. Specifically, with its efficient proof generation and on-chain verification capabilities, ZKLP will open up new possibilities for decentralized applications on Ethereum that rely on location data while ensuring user privacy. Our seminal investigation of authenticated locations further enables ZKLP to be used in applications that require strong assurances for exact locations, such as proximity-based token dispersal. As concrete outcomes, we aim to provide the following: * An open-source library for primitive FP arithmetic. * An open-source system for P2P proximity testing. * An academic publication, presenting ZKLP and the concrete optimizations for floating-point arithmetic in a formalized manner. Our implementation of standard-compliant floating-point operations will also be a valuable resource for zkVM and other privacy-preserving systems that require floating-point arithmetic. ## Grant Scope  We approach the Zero-Knowledge Location Privacy from a bottom-up perspective. Hence, we first instantiate low-level primitives, such as floating-point computation, and succesively design a practical high-level system for providing Zero-Knowledge Proofs of locations. In our **first research iteration** we will focus on the following research items: 1. Formalization of Zero Knowledge Location Proofs 2. Optimized Circuits for Floating Point Arithmetic 3. Proof of Concept implementation for Zero-Knowledge Location Proofs The first iteration will include the publication of an academic paper at a top tier computer security venue, like IEEE S&P (Oakland), ACM CCS, or similar. In our **second research iteration**, we will leverage the ZKLP paradigm in a system that provides *authentic* location information. This is necessary, as our first research thrust assumes authentic location information (i.e., latitude and longitude) without accounting for potentially adversarial provers. The research items in our second iteration are the following: 1. Understanding the state of the art in authenticated GNSS signals and mobile compatible Trusted Execution Environments. 2. Deriving a concrete system model, which ensures that an adversarial prover can only prove authentic locations. 3. Evaluating the performance of the proposed system in a Proof of Concept implementation We believe that the second iteration requires much more consideration and thought. The problem of a mobile-capable Proof-of-Personhood has been a long standing problem, and many nuances can decide its actual feasibility. For the purpose of this grant, we consider successfully conducting the first iteration the main criteria to determine the success of this project proposal. ## Project Team   **Principal Researchers** - [Jens Ernstberger](https://ernstberger.xyz/) - [Chengru Zhang](https://github.com/winderica) - The University of Hong Kong - [Philipp Jovanovic](https://scholar.google.com/citations?user=p-KBDi8AAAAJ) - University College London Both Jens Ernstberger and Chengru Zhang will work 20 hours per week on the research project, whereas Philipp Jovanovic will take a supervisory role with 5 hours per week.  ## Background - **Jens Ernstberger** is currently a PhD student at Technical University of Munich. He co-authored multiple research papers in the blockchain domain, including but not limited to the topics of [Zero-Knowledge Proofs](https://eprint.iacr.org/2024/050.pdf), [Benchmarking SNARKs](https://eprint.iacr.org/2023/1503.pdf), [Verifiable Data Provenance](https://eprint.iacr.org/2023/1377.pdf) and [Security in Decentralized Finance](https://discovery.ucl.ac.uk/id/eprint/10182321/1/2022-1773%20%281%29.pdf). Previously, Jens was a Visiting Researcher at [University of California, Berkeley](https://rdi.berkeley.edu/) and at the [Simons Institute for Theory in Computing](https://simons.berkeley.edu/homepage).  - **Chengru Zhang** is currently a PhD student at the University of Hong Kong under the supervision of Prof. Man Ho Allen Au and Prof. Siu Ming Yiu. His research focuses on privacy-preserving protocols for blockchains. Chengru also has extensive experience in developing and optimizing zero-knowledge proofs. His team won ZPrize 2022, the "PLONK-DIZK GPU Acceleration" division, and his contribution included architecture design and [implementation](https://github.com/winderica/jellyfish/tree/zprize_submission). He is also working on [r1cs-float](https://github.com/winderica/r1cs-float), a project for supporting floating-point arithmetic in R1CS circuits.  - **Philipp Jovanovic** is an Associate Professor in Information Security at the Computer Science Department of University College London (UCL) where he's a member of the Information Security Research Group (ISRG). Philipp's research interests broadly include applied cryptography, distributed systems, blockchains, and privacy-enhancing technologies. Lately he has been working on [security](https://arxiv.org/abs/1602.06997), [scalability](https://eprint.iacr.org/2017/406), and [interoperability aspects](https://eprint.iacr.org/2021/1361) of distributed ledger platforms, [public randomness generation](https://eprint.iacr.org/2016/1067), [secure multi-party computation](https://eprint.iacr.org/2022/1759), [consensus mechanisms](https://arxiv.org/abs/2102.09041), and [zero-knowledge proofs](https://eprint.iacr.org/2023/961). For more information on his research see his [Google Scholar Profile](https://scholar.google.com/citations?user=p-KBDi8AAAAJ).   ## Methodology  1. **Formalizing Zero-Knowledge Location Priavcy via Discrete Global Grid Systems:** Discrete Global Grid Systems (DGGS) divide the Earth into a hierarchy of progressively finer resolution grids. A naive solution for dividing the Earth's surface is to apply a simple latitude-longitude grid. The Earth is divided into a grid based on lines of latitude and longitude, creating a series of rectangular cells that cover the entire globe. However, the drawback of such an encoding is that near the poles, the lines of longitude are in closer proximity than they are at the equator. While a latitude-longitude grid is a simple way to partition the Earth's surface, it lacks the uniformity, efficiency, and scalability of a DGGS, particularly for complex spatial analyses and global-scale applications. We will build upon previous work conducted by Uber, a popular ride-sharing service, which relies on their in-house [Hexagonal Spatial Index](https://github.com/uber/h3) for price prediction and route finding. Their hexagonal spatial index relies on hexagons as geometric representation (see image below). This allows for maximal flexibility for ZKLP as a primitive. Successive algorithms can build upon our paradigm, developing streaming properties with Incrementally Verifiable Computation [\[1\]](https://eprint.iacr.org/2021/370.pdf). ![Image](https://www.geographyrealm.com/wp-content/uploads/2020/08/h3-globe-grid-system.png) 2. **Optimizing IEEE-754 compliant Floating Point Arithmetic in SNARKs:** Efficiently emulating floating-point operations in a SNARK is hard. A SNARK commonly operates over a finite field $\mathbb{F}_{p}$, where $p$ is a large prime depending on the underlying elliptic curve (e.g., $|p| = 254$ for BN254). By contrast, $32$- or $64$-bit floating-point arithmetic require integer operations that are circuit-unfriendly, such as comparison and shifts. A naive in-circuit implementation for floating-point representation and operations would lead to a huge number of constraints. To efficiently operate on floating-point values, we convert their integer components to an equivalent but circuit-efficient form, build optimized sub-circuits for integer operations, and minimize the number of costly range checks in key steps, e.g., rounding. The key is to efficiently model non-native arithmetic in-circuit via appropriate techniques. Recent work by Orrù et. al [\[2\]](https://eprint.iacr.org/2024/265.pdf) has shown that lookup arguments can be leveraged to minimze foreign arithemtic in ZK circuits. We will leverage the lookup argumens based on logarithmic derivatives by Haböck et. al [\[3\]](https://eprint.iacr.org/2022/1530.pdf) to derive efficient instantiations of range-checks and other non-native field operations to optimize our implementation. Additionally, for compliance with IEEE 754, we take additional care of edge cases, such as NaN, $\pm \infty$ and subnormal numbers.  3. **Eliminate expensive mathematical operations from the ZKLP circuit:** To efficiently instantiate the Zero-Knowledge Location Privacy paradigm over primitive floating-point operations, we aim to introduce shortcuts, eliminating expensive math operations through trigonometric identities and nondeterministic programming. Nondeterministic inputs (or *hints*[\[4\]](https://docs.gnark.consensys.io/HowTo/write/hints)) are additional inputs which are not trusted to be correct, but whose verification is more efficient in-circuit than the emulation of the plain computation. For example, consider the computation of a square root $\sqrt{x}$ over a variable $x$ given as an input to the arithemtic circuit. Naively, the circuit can emulate Newton's method to approximate the actual value of the square root with sufficient accuracy. However, this algorithm is iterative, which leads to a blowup in constraints in the arithmetic circuit. In contrast, one can leverage a *hint* to pass $\sqrt{x}$ as an additional input. The in-circuit logic checks that $\sqrt{x} \cdot \sqrt{x} == x$, which only requires one multiplication instead of a full-fledged iterative algorithm. We aim to leverage similar techniques to optimize the ZKLP circuit implementation to derive an efficient implementation, without the need to compute any trigonometric functions in-circuit.  ## Timeline   **First Research Iteration (6 months):**  | **Deliverable** | **Time Duration (Total)** | |-----------|-------------| | Formalizing Zero-Knowledge Location Priavcy via Discrete Global Grid Systems | 4 weeks | | Optimizing IEEE-754 compliant Floating Point Arithmetic in SNARKs | 8 weeks | | Eliminating expensive mathematical operations from the ZKLP circuit | 4 weeks | | Evaluation | 4 weeks | | Writing a Research Paper | 4 weeks | | **Total Time For Completing The First Research Iteration** | 24 weeks/6 months | Both Jens Ernstberger and Chengru Zhang will work on the project for 20 hours per week. Philipp Jovanovic will act as an academic supervisor, committing 5 hours per week.    ## Budget  **Total Budget: $66.000** **Breakdown:** * **Primary Principal Researchers** (Jens Ernstberger and Chengru Zhang) * 24 weeks, 20 hours per week, $50 an hour, for two researchers * Sum: $48.000  * **Advising Principal Researcher** (Philipp Jovanovic) * 24 weeks, 5 hours per week, $75 an hour, for one researcher * Sum: $9.000  * **Travel Cost / Other Staff Cost** * Presentation at zkSummit and a top tier academic research conference * Sum: $6.000  * **Cloud Computing Cost** * Experiments at a global scale on AWS * Sum: $3.000