---
# System prepended metadata

title: Grant Proposal - Zero Knowledge Location Proofs

---

# Grant Proposal - Zero Knowledge Location Proofs

## Project Abstract

<!-- In 3-5 sentences what problem are you trying to solve? (The project abstract may be used for for the winners announcement.) -->

<!-- While location-based services are ubiquitous 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. -->


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.

<!-- Existing privacy-preserving solutions, known as Location Privacy Preserving Mechanisms (LPPM) protocols, either have limitations for location information that is correlated between users, or require a third party for data anonymization. -->

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

<!-- What are you hoping to accomplish with this grant? How do you define and measure success for this project? -->

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.
<!--  -->
<!--     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.  -->
<!--  -->
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.
<!--    To do so, we will investigate how to combine ZKLP -->

<!-- * Construct arithmetic circuits for IEEE 754 compliant floating-point (FP) operations
* Construct arithmetic circuits for ZKLP
* Optimize the circuits to minimize the number of constraints
* Develop a protocol for privacy-preserving peer-to-peer proximity testing as the demonstration of ZKLP
* Evaluate the performance of the circuits and the P2P proximity testing protocol -->

<!-- The success of this project will be measured by the following criteria: -->


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

<!-- How does this project benefit the greater Ethereum ecosystem? -->

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

<!-- What are you going to research? What is the expected output? -->

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

<!-- How many people are working on this project? -->
<!-- Please list their names and roles for the project as well as how many hours per month will each person work on this project? -->

**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.

<!-- | **Name** | **Role** | **Hours per Month** |
|-------------|-------------|-------------|
| Jens Ernstberger | Principal Researcher |  |
| Chengru Zhang | Principal Researcher |  |
| Philipp Jovanovic | Principal Researcher |  | -->


## 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).


<!-- Give us a bit of info and include relevant links, if available! Please provide other projects or research papers (ideally public and/or open source), engagements or other types of proof that your team has the necessary experience to undertake the project you are applying for. -->
<!-- Any links for us to review? E.g. research papers, blog posts, etc. -->



## Methodology

<!-- How do you plan to achieve your research objectives? -->


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.


<!-- <p style="color: red">**!Link / Image of the actual thing!**</p> -->

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.

<!-- To achieve our research objectives, we will:

* Rely on Discrete Global Grid Systems (DGGS) with hexagons as geometric representation, which divide the Earth into a hierarchy of progressively finer resolution grids
* Utilize lookup arguments to reduce the number of constraints for FP arithmetic
* Eliminate expensive mathematical operations like trigonometric functions from the ZKLP circuit
* <p style="color: red">**!TODO!**</p> -->

## Timeline

<!-- Please include a brief explanation on the milestones/roadmap, along with expected deliverables. Also outline how the funds will be used for the research project and or members of the team. -->

<!-- Please include a brief explanation on the milestones/roadmap, along with expected
deliverables. Also outline how the funds will be used for the research project and or
members of the team.
Qualitative Systematization - 2 weeks
Framework Specification - 4 weeks
Framework Building & Benchmark Execution - 12 weeks
Front End Development - 4 weeks
Writing a Research Paper - 8 weeks
Comprehensive Documentation - 2 weeks
Total Time for project completion - 32 weeks / 8 months -->

**First Research Iteration (6 months):**

<!-- Two people, 80 hours per week -->

|     **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.

<!-- 
|     **Deliverable**      | **Person Weeks** (40 hours per week) |  **Time Duration (Total)** |
|-----------|-------------|-------------|
| Formalizing Location Transformation via Discrete Global Grid Systems | 2 weeks | 1 weeks |
| Specification of Floating-Point Circuit Optimizations | 8 weeks | 3 weeks |
| Implementation of Circuits for Circuit Optimizations | 8 weeks | 2 weeks |
|-----------|-------------|-------------|
| Formalization of ZKLP | 2 weeks | 1 weeks |
| Implementation of Circuits for ZKLP | 2 weeks | 2 weeks |
| Implementation of Proof of Concept | 1 weeks | 1 week |
|-----------|-------------|-------------|
| Writing a Research Paper | 8 weeks | 3 weeks |
|-----------|-------------|-------------|
| **Total (Sum)** | 8 weeks | 12 weeks | -->

<!-- **Second Research Iteration (3 months):**

|     **Deliverable**      | **Person Weeks** (40 hours per week) |  **Time Duration (Total)** |
|-----------|-------------|-------------|
|-----------|-------------|-------------| -->

<!-- |           | **Phase 1** | **Phase 2** | **Phase 3** |
|-----------|-------------|-------------|-------------|
| **Duration** |  |  |  |  |
| **Activities** |  |  |  |  |
| **Deliverables** | <ul><li>A library for primitive FP operations</li></ul> |  | -->



## Budget

<!-- 
Cost per Chengru / Jens:
12 weeks
40 hours per week
50 $ and hour
-> 24.000$ per Person

Cost for Philipp:
12 weeks
10 hours per week
80 $ and hour
-> 9.600$ per Person

Cost for Travel:


-->

**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
<!--  -->

    


<!-- Requested grant amount and how this will be used -->
<!-- Please provide an requested amount and outline of how the grant will be used. A detailed budget proposal would be helpful and some item you could include are: -->
<!-- * Principle Researchers Costs -->
<!-- * Other Staff Costs -->
<!-- * Hardware Costs -->
<!-- * Software Costs -->
<!-- * Data Collection Costs -->
<!-- * Indirect Costs -->