Basic Chaum-Pedersen Zero Knowledge Proof implementation

Overview

This repo contains a very basic implementation of a ZK proof auth client and server (prover and verifier) which implements the Chaum–Pedersen Protocol. Both the prover and the solver are coded using Rust and are built into separate binaries whcih communicate between each other using gRPC.

How it works

The implementation of this library uses discreet logarithm computation where the prover and verifier both agree on a discreet group of prime order as well as two generators for it. Therefore as a pre-requisite both parties need to agree on the following well-known values:

• p - a prime number, used for the modulus of the discreet group G. In a real application this needs to be a very large prime number.
• q - q = |G| is the order of the group
• g and h are of prime order and as such g ^ q mod p = 1 and h ^ q mod p = 1

Once the above pre-requisite/steup step is completed there are 3 steps required to stablish a secure ZKP authentication:

1. Registration step - the prover "registers" with the prover. During this step the prover chooses a secret (big) number x and with it calculates two numbers y1, y2. Then these numbers are shared with the verifier (whithout shint x)
2. Commitment -> Challenge step - the prover initiates an authentication attempt by choosing a (very big) random number k which is then used to calculate two values r1 and r1. R1 and r2 are then sent to the verifier (without sharing k). In the response the verifier returns a randomly generated number c.
3. Verification step - the prover uses the challenge c from the previous step and its secret x to calculate a solution s whcih is sent to the verifier. Then the verifier calculates a new number using y1, y2, r1, r2, c and s to verify if the prover indeed knows x without ever revealing it.

Assumptions and comments

Simplifications and shortcuts taken

This code is simplified and is not suitable for production use. Its purpose is only to demonstrate use of the Chaum-Pedersen ZKP protocol. A more production ready solution would require a number of improvements. For example, to name a few:

• The client and server would communicate over TLS
• Proper observability instrumentation needs to be added (metrics, tracing, logs, dashboards/alerts as code etc.)
• Proper documentation
• The ZKP protocol would be exported as a library which can then be used from different client and server implementations and communication protocols (i.e. not just gRPC)
• External storage for the users, challenges needs to be used instead of an in-memmory map which doesn't scale
• Use proper session_id token, e.g. JWT. Returning just random string is not appropriate for production without at least checking if the string is unique or not
• Disallow registering a username more than once for obvious reasons. For simplification reasons in the current implementation, the entry in the users hashmap is overridden if it already exists which is not secure at all.
• The client would accept the username and secret from configuration (e.g. environment variable or a config file) or user input instead of hard-coding them in the code.
• Build the docker images for multiple platforms.

Unit tests

Some unit tests of the main functionality (i.e. the solve and verify methods) have been added, however, production-grade code would require a higher level of coverage.

Functional tests of the ZKP protocol

Some functional tests have been added which test the process of registration, atuh challenge and verification. The set of tests is by no means compelte and doesn't involve all happy and unhappy paths.

Client and Server setup

Assuming that Docker is present on your machine, the client and the server can be started by running using the docker-compose.yaml file:

$ docker compose up
[+] Running 2/0
 ✔ Container zkp-auth-server-1  Created                                                                              0.0s
 ✔ Container zkp-auth-client-1  Created                                                                              0.0s
Attaching to client-1, server-1
server-1  | Listening for connections on 0.0.0.0:50051
client-1  | Registration successful.
client-1  | Received challenge from server.
client-1  | Successfully logged in! Session ID: OooJ8n7FOOU1ZyhxOqfBhsvK5x4mwdP7
client-1 exited with code 0

Alternatively, if Docker is not available, one can always run the binaries using cargo like this:

• Run cargo run --bin zkpauth-server in one terminal; and then
• Run cargo run --bin zkpauth-client in another terminal

By default the server listens on and the client tries to connect to 127.0.0.1:50051.

Performance and optimizations

There is room for improvement in terms of performance optimizations. In a production grade code it would be appropriat to use Profile-guided Optimizations as well as add benchmarks to ensure that the performance of every iteration of the code is not worse than the previous in terms of performance.

Cloud deployment

In the repo there are GitHub workflow actions which create cloud infrastructure on AWS as well as build and deploy containers of the client and server to the cloud.

Using BigUint numbers

In order for the protocol to be more secure really big numbers need to be used. This is the reason why this implementation uses BigUint instead of int64 for example.

TODOs

• Add a prover and a verifier traits so that multiple implementations can be added
• Use elliptic curves - Instead of using discrete logarithms the protocol could be changed to use a well known elliptic curve. Then instead of providing numbers y1, y2 and r1, r2 etc. each number would need to replaced with the x and y coordinate of a point on the elliptic curve. One can use one of the elliptic curves from one of the TLS libraries. Further reading:
  • Zero-Knowledge Proof - Cryptographic Primitives and Sigma Protocol
  • Elliptic curves
• Add observability (e.g. Prometheus metrics, tracing, structured logging and Grafana dashboards).

Resources

• Explanation video
• Basic example explained
• Primitive modulo
• RFC3526 - Groups
• RFC5114 - Groups