It’s a rainy Sunday afternoon, and my friend, Alice, and I are playing “Where’s Waldo.”* This page is a particularly challenging one, and we’ve been looking for nearly twenty minutes.  I’m about ready to give up, when- finally- I spot Waldo, and I yell out, “I got him!”

“Oh really? Prove it then,” Alice says, hand on her hip.

I raise my finger, and I’m about to point to Waldo’s location, but she stops me, exclaiming, “Wait, wait, wait! Wait just one second! I’ve put so much work into finding Waldo, and I don’t want you to ruin it for me.”

“Hmm…” I say. “If only there was a way for me to prove to you that I know where Waldo is without revealing his location.”

“Here, I have an idea,” Alice says. “I’ll make a photocopy of this page in the book, and you can cut Waldo out of the photocopy and show him to me. That way, I know for sure that you know where Waldo is, AND I still won’t know where he is.”

As you might have guessed by the title of this blog, the scenario I’ve described is a classic example of a real-life zero knowledge proof. In this story (which **definitely** happened in real life), I am proving that I possess a piece of information (Waldo’s location), while at the same time not revealing that information.

There are many types and potential applications of zero-knowledge proofs, including nuclear disarmament (yes, really) and verified anonymous voting. In this example project, I’ve focused on how using Fluree in conjunction with zero-knowledge proofs can begin to tackle the challenge of traceable fishing. 

Before we begin, I need to make the disclaimer that I am, by no means, an expert in zero-knowledge proofs. I welcome and encourage comments, suggestions, corrections, and more in the comments. This project is an exploration of the possibility of using zero-knowledge proofs with Fluree.

With three billion people relying on fish as their main source of protein, oceans are a critical food source. Given the importance of marine life to human nourishment, efforts have been made to regulate fishing locations, methods, and quantity. These regulation attempts are sometimes at odds with the desires of fishers who, among other concerns, are not too keen to reveal their fishing locations. This is where zero-knowledge proofs can come in.  Zero-knowledge proofs can allow a fisher to prove that they are, for example, fishing within an allowed area, without exposing the exact location.

To follow along with this example, you can download the fluree/legal-fishing repository. If video is more your speed, you can also check out this project’s accompanying video above or on youtube.

Iden3’s Circom and SnarkJS

In this project, I use two Javascript libraries, both published by Iden3, to handle my zero-knowledge proofs. I use circom to write and compile an arithmetic circuit (more on this in a second). I then use this circuit in conjunction with the snarkjs library to implement a zero-knowledge proof. (For those who are interested, the specific type of zero-knowledge proof we use here is called a zkSNARK, or zero-knowledge succinct non-interactive argument of knowledge, using the 8points protocol). 

The intuition behind this type of zero-knowledge proof is not as simple as the “Where’s Waldo” example, but it operates in a similar way. We first build a very specific type of electrical circuit that is only satisfied by inputs that match certain restrictions.

Using circom, we’ll create a representation of a circuit, but let’s imagine for a second that it’s a real-world circuit. You and I sit down, and we build an electrical circuit with 5 switches on one side. The circuit has a light bulb that will always light up if exactly 3 of the switches are on- it doesn’t matter which three.

I leave the room, and you flip any three of the switches that you want. You then cover up the switches with a cardboard box so that no one can see them. I walk into the room, see the light bulb is shining, and I know that the circuit is complete. I know that your input (which switches you turned on) fit our criteria (exactly 3 switches turned on), but I won’t know exactly what your input was.

This type of zero-knowledge proof is analogous to what we are mathematically accomplishing using circom and snarkjs. We won’t delve into the math here, but hopefully this has given you some intuition.

InRange.circom

The specific type of circuit we are creating is an arithmetic circuit, which is a circuit that can perform some arithmetic operations. If you are following along with the GitHub repository, the circuit is `src/circuits/InRange.circom`. Our circuit will take two public inputs:

1. latitudeRange – an array of two numbers representing the min and max latitudes of the legal fishing range (must be positive numbers). 
   
2. longitudeRange  – an array of two numbers representing the min and max longitudes of the legal fishing range (must be positive numbers). 

These two inputs will be visible to the public. This circuit will also take a private input:

• fishingLocation – an array of two numbers within the legal range.
  

The circuit will output a 0 (if the circuit is not satisfied) or a 1 (if it is). To compile the circuit, you’ll need to have circom installed:

npm install -g circom

Then you’ll need compile the circuit:

circom InRange.circom -o InRange.json

This will take InRange.circom as an input an output InRange.json in the same directory.

Setup

Now, we need to setup the circuit. In order to do this, we’ll need to have snarkjs installed.

npm install -g snarkjs

And then we can issue:

snarkjs setup -c InRange.json

This will create two files, proving_key.json and verification_key.json. As the names suggest, the proving key is the key you’ll need to prove that your input (your location) is valid. The verification key is the key you’ll need to verify anyone else’s proofs. When we set up our Fluree ledger, we’ll be putting both the proving and verification key (as well as the circuit) on the ledger.

Note – This type of zero-knowledge proof requires a trusted setup. The process of generating these keys will also create some toxic data that must be deleted. Participants need to trust that the toxic data was deleted. It is important to note that this toxic data would allow an untrustworthy participant to create a fake proof using inputs that don’t match the constraints. The toxic data would NOT allow a user to discover someone else’s secret location. 

But this toxic data is only created once, and there are methods to minimize the risk. For example, a multi-party trusted setup creates a situation where a number of participants come together to generate the proving and verification keys, and each of them possess a piece of toxic data. In a setup like this, the only way to create a fake proof would be if every single party was untrustworthy, and they all kept their toxic data and then colluded by bringing their toxic data together (hopefully an unlikely occurrence!).

Calculating a Witness

Before we can create a proof, we need to calculate all the signals in the circuit (including all the intermediate inputs) that match the circuit’s constraints. In order to do this, we’ll need to create an input.json, which has all of our inputs (including the private inputs). Neither the inputs.json, nor the witness.json files will be shared with anyone, but we do need to calculate them first.

Our input file needs to be a map, where the keys are the names of all of the circuit’s inputs, and the values are our specific inputs. For example:

{
    "latitudeRange": [ 20, 21],
    "longitudeRange": [ 176, 190],
    "fishingLocation": [ 20, 180]
}

We can then calculate the witness, which will generate the witness.json file. 

snarkjs calculatewitness -c InRange.json

Create the Proof

Now, we have all of the pieces to create the proof:

snarkjs proof

This command uses the proving key and the signals in witness.json to generate a proof.json (the actual proof) and public.json, which is a subset of your witness.json containing only your public inputs and the outputs.

Verify the Proof

You can now give any other party your verification_key.json, proof.json, and public.json, and they can verify that you put in an input that matched the constraints (a location within the legal range).

Connecting this with Fluree

In the fluree/legal-fishing repo, we not only have an example circuit with example keys and inputs, but we also have a small demo React app that makes it easy to connect this zero-knowledge proof to a Fluree instance.

To get this running, you’ll need to:

1. Download a fresh instance of Fluree. I used version 0.11.5.
2. Run Fluree (./fluree_start.sh). Fluree needs to be running on port 8080. This is the default port, so if you didn’t change any of the settings for version 0.11.5, everything will be all set for you. 
3. Create a database called legal/fishing.
4. Issue a transaction to create the schema. You can find this transaction in seed/schema.json.
5. Issue a transaction to upload the circuit, verification key, and proving key to Fluree. You can generate and upload your own, or you can use the example in ‘seed/seed/json’. If uploading your own, be very careful to copy the keys and circuits exactly, otherwise, the proof and verification won’t work.

Now, you can run `npm install` and `npm start` to start up the lightweight React app, which integrates Fluree with the zero-knowledge proofs.

You can use the app to generate a proof and submit the proof and public signals to the Fluree ledger.

You can also click on the Verify Proofs pages to see all the proofs that have been submitted to this ledger. You can click on “Verify Proof” to verify any given proof. Note that verifying a proof takes a little while, so expect to wait 10 – 20 seconds before a green “Verified!” alert comes up. For a full tour of the application, as well as a visual walk-through of getting the circuit and app setup, check out this project’s accompanying video.

Additional Considerations

This small project is only a tiny part of the puzzle needed to ensure seafood traceability. For starters, this example only deals with a single rectangular-shaped area. A real-life project would, of course, be much more complicated than this. In the case of zero-knowledge proofs, verifying and creating proofs can be time-intensive, so implementing a real-world project would require careful consideration of timing. There are zero-knowledge proofs that specifically are optimized for range-proofs, which might be a better fit for this example. This could be an area of future exploration for us.  

Additionally, even if the proof itself took the full scope of real-world restrictions into account, a fisher’s location at the time of catch would have to be reported by a source that is reliable. For example, we might want a piece of hardware that is sufficiently tamper-proof reporting a fisher’s location, rather than, say, the fisher’s word. We would also need a reliable way to correlate a GPS location to a particular catch. For hardware, considerations of cost, hassle to the fishers, and tamper-proofness would all have to be weighed. 

A final area to consider is public knowledge and trust of zero-knowledge proofs. Even if mathematically, we can show that a zero-knowledge proof does not reveal a fisher’s location, the fisher would have to trust the organization implementing this system. The fisher would first have to trust that their location is not hidden somewhere in the proof they are uploading to the database. The proof is a large, JSON object that could conceivably hide information. The fisher would also have to trust that the hardware they are using to report their location is not sending it out through some backdoor. 

These are assuredly not insurmountable concerns, but they should be considered as food-for-thought. Research, implementation, and public understanding of zero-knowledge proofs have really grown in the past few years due to projects like ZCash, so this is definitely an area to look out for!

Thanks everyone for reading, and I’m interested in any and all feedback. If this piqued your interest, you might be interested in checking out other projects that tackle the challenge of proof of location, as well as this curated list of zero-knowledge proof content. You can also get started with Fluree here, and make sure to check out our documentation as well! 

* For those unfamiliar with the “Where’s Waldo” books (or “Where’s Wally” outside of North America), Waldo is a cartoon man in a red-and-white striped shirt. “Where’s Waldo” books have page after page of hectic scenes, filled with people and colors. The object of the game is to try and spot Waldo. 

k