I've always been fascinated by cryptography and privacy in computing. My journey began with an understanding of Pretty Good Privacy (PGP), where I delved into data signing and verification processes. With the rise of blockchain technologies and secure communications, my interest in understanding how Zero Knowledge Proof (ZKP) algorithms work was piqued. As I began to dive into online resources, it became clear that implementing such an algorithm would be an exciting and educational project..
I wanted my implementation to be as close to reality as possible, mirroring real-world scenarios where two separate participants, the Prover and the Verifier, interact across different servers. Additionally, the separation of participants provided me with an opportunity to develop the solution with two different programming languages, providing a more complex and realistic setup.
For the messaging system between the Prover and Verifier, I chose RabbitMQ. This decision is based on its ease of use and quick implementation. It enabled seamless communication between two distinct servers, aligning perfectly with my goal of simulating a real-world application.
However, it's important to note that, when the entire application stack is first initiated, the Prover and Verifier might not immediately have access to RabbitMQ due to the time it takes for the RabbitMQ server to become fully operational. To manage this, I have implemented a mechanism in both the Prover and Verifier scripts which attempts to establish a connection to RabbitMQ multiple times over a set duration. This ensures that the Prover and Verifier will start processing only once the connection to RabbitMQ is successfully established.
The use of two different programming languages for the Prover and Verifier components added an extra layer of realism and provided a challenging and rewarding coding experience.
- The Prover component is implemented in Python.
- The Verifier component is written in PHP.
In implementing the Fiat-Shamir Zero Knowledge Proof algorithm, I adhered closely to the original specification, with a few necessary adaptations to accommodate the messaging system. Specifically, values that need to be communicated between the Prover and the Verifier, such as 'n' and 'v', are sent as messages through RabbitMQ queues. This adaptation improves the overall simulation, providing a more accurate representation of how such a system would operate in real-world scenarios.
To keep the simulation more manageable and the outputs easier to interpret, I've chosen a specific range for the generation of prime numbers 'p' and 'q', which are used to compute 'n'. In a real-world application, these numbers would be significantly larger to ensure robust security. As explained in the Wikipedia article on the Feige-Fiat-Shamir identification scheme, 'n' should be the product of two large prime numbers, 's' and 'r' should be less than 'n', and 's' should be coprime to 'n'. These conditions contribute to the security of the Fiat-Shamir protocol.
The system performs a number of iterations defined by the TOTAL_TESTS environment variable in the .env file, with a default of 20 if not specified. This setup allows for flexibility in the number of iterations, which can be adjusted to meet specific security requirements. In practice, this number can be changed as needed. Based on my research, a minimum of 20 iterations should be sufficient to verify whether the Prover truly knows the secret.
I have taken care to heavily comment the code to aid understanding for the reader (and for myself! 😃). This approach will facilitate a more in-depth comprehension of the algorithm's functioning and the design choices made.
The Fiat-Shamir algorithm is a method for implementing a Zero-Knowledge Proof (ZKP) protocol. A ZKP is a method by which one party (the prover) can prove to another party (the verifier) that they know a value of a certain parameter, without conveying any information apart from the fact that they know the value.
Here's a simplified explanation of the algorithm:
Setup Phase: This is the initial stage before the message exchange begins. In this phase:
- The Prover possesses a secret 's' that they aim to prove knowledge of to the Verifier, without revealing the secret itself.
- 'n' is a composite number which is the product of two prime numbers. Both the Prover and Verifier are aware of 'n'.
- 'v' is a value calculated by the Prover as v = (s * s) mod n, which is then shared with the Verifier.
Commitment Phase: The prover begins by choosing a secret value 's' and computes v = (s * s) mod n, where 'n' is a composite number (preferably a product of two large primes 'p' and 'q'). The value 'v' is sent to the verifier. The prover also chooses a random number 'r' and computes x = (r * r) mod n. This value 'x' is the commitment and is sent to the verifier.
Challenge Phase: The verifier then sends a random challenge bit 'b' to the prover. This bit is either 0 or 1.
Response Phase: If the bit 'b' is 0, the prover sends 'r' back (since anything raised to the power of 0 is 1, and 'r' is less than 'n', the product of 'r' and 1 remains 'r' itself). If 'b' is 1, the prover sends y = (r * s^b) mod n back.
Verification Phase: The verifier checks if y * y mod n is equal to 'x' (if 'b' was 0) or to x * v^b mod n (if 'b' was 1). If the check passes, the verifier can be assured that the prover knows the secret s.
This algorithm is iterated several times to reduce the probability of a malicious prover successfully passing the verification without knowing the secret.
This project is containerized using Docker, making it easy to build and run regardless of your development environment.
To install and run the Prover and Verifier:
- Clone this repository:
git clone https://github.com/oscarpascualbakker/fiat-shamir-zero-knowledge-proof .
- Setup Configuration:
Before running the application, you need to set up configuration files for both the Prover and the Verifier. Create .env files for both the Prover and the Verifier in their directories, or copy the existing .env_example to .env in both directories.
Adjust the values in the .env files as per your needs. Ensure that the configuration matches between the Prover and Verifier so they can interact correctly.
- Build and run
From the root directory of the project, build and run the Docker images using docker-compose:
docker-compose up -d
The Prover and Verifier services will start interacting once RabbitMQ is up and running.
To review the results, you can check the logs of both the Prover and Verifier containers. This can be done with Docker's log command:
docker logs <container_id>
Where <container_id> is the ID of the container for which you want to view the logs.
When you run the application, you should see outputs similar to the following:
Prover Output:
Verifier Output:
Please note that your actual output may vary due to the random nature of the Fiat-Shamir algorithm.
-
Fiat-Shamir Heuristic: The Wikipedia page offering a detailed explanation of the heuristic algorithm.
-
Feige-Fiat-Shamir Identification Scheme: The Wikipedia page offering a detailed explanation of the scheme.
-
Zero-Knowledge Proofs: A comprehensive guide to Zero-Knowledge Proofs (ZKP).
This project provided me with an invaluable opportunity to deepen my understanding of Zero Knowledge Proofs and cryptography in general. By attempting to align the implementation closely with real-world conditions, including the use of distinct servers (Docker containers in practice) and programming languages, as well as a robust messaging system, I feel that I have achieved a realistic and functional simulation of the Fiat-Shamir algorithm.
Please don't hesitate to share your thoughts or suggestions.