zkbattleship-circuit

zkbattleship-circuit consists of the zkSNARKs arithmetic circuit implementation for zkbattleship, a prototype Battleship game built on zkSNARKs proof and verification.

Currently it has the circuit implementations in ZoKrates (which can generate verifier in form of Ethereum smart contract), as well as circom (which can then be used with snarkjs).

Prerequisite

For ZoKrates, install ZoKrates CLI locally per the instruction at here. This allows the use of zokrates in command prompt.

For circom, install circomlib via npm:

npm install circomlib@0.0.16

The above will also install snarkjs as a dependency. Alternatively, install snarkjs via npm:

npm install snarkjs@0.1.18

Notice that the current implementation is not yet compatible with circom v0.5, which was released in March 2020.

Structure

zokrates and circom subfolders hold the implementation for ZoKrates and circom respectively.

Build

You may find the basics of the lifecycle of zkSNARKs proof and verification here.

Both Pedersen (see more at ethresear.ch and Zcash) and SHA256 hash implementations are available, you may choose the ones that you need to compile.

Pedersen hash implementation is recommended for zkSNARKs efficiency - see more in Notes on Hashing.

For ZoKrates:

cd zokrates

# Pedersen:
# compile circuit code and generate out, proving.key and verifier.sol
./zkcompile code/battleship_pedersen.code
# calculate sample witness and generate proof (proof.json)
./zkprove_pedersen

# SHA256 (not recommended):
# compile circuit code and generate out, proving.key and verifier.sol
./zkcompile code/battleship_sha256.code
# calculate sample witness and generate proof.json
./zkprove_sha256

For circom:

cd circom

# Pedersen:
# compile circuit code and generate circuit.json, proving_key.json, verification_key.json and verifier.sol
./zkcompile battleship_pedersen.circom
# calculate sample witness (input.json) and generate proof (proof.json and public.json)
./zkprove

# SHA256 (not recommended):
# compile circuit code and generate circuit.json, proving_key.json, verification_key.json and verifier.sol
./zkcompile code/battleship_sha256.code
# calculate sample witness (input.json) and generate proof.json and public.json
./zkprove

The keys generated from above can be used to prove and verify respectively (e.g. to be used in snarkjs for circom). verifier.sol, which is the generated smart contract in Solidity, can be deployed on Ethereum blockchain for decentralized verification (see section below).

In particular, zkbattleship uses circom implementation to perform on-demand proof generation (using circuit.json and proving_key.json), local verification (verification_key.json) as well as Web3 verification (verifier.sol).

Contract Deployment

Assume that a Ganache local development blockchain is up and running:

# start Ganache as local Ethereum blockchain at the background
ganache-cli

Verifier contract (verifier.sol) can be deployed to the network using truffle:

cd contracts

# softlink to verifier.sol generated either by ZoKrates or circom
# circom's one is required for zkbattleship
ln -s ../zokrates/verifier.sol
ln -s ../circom/verifier.sol

# compile contract and deploy
truffle compile
truffle migrate

See more details around ganache-cli and truffle.

truffle-config.js is in its basic configuration for local development. Additional networks (e.g. Kovan testnet) can be manually configured there.

Notes on Hashing

There have been different discussions on whether/how hashing can be made more efficient in arithmetic circuits for zkSNARKs use; see Zcash forum and ethresear.ch.

For this battleship use case, taking circom's hash as an example, Pedersen Hash is proved to be more efficent in terms of the resulting number of wires (>88% reduction) and constraints (>97% reduction), compared with the SHA-256 counterpart:

> ./zkcompile battleship_pedersen.circom 
# Wires: 3540
# Constraints: 708
# Private Inputs: 15
# Public Inputs: 4
# Outputs: 1
> ./zkcompile battleship_sha256.circom 
# Wires: 31366
# Constraints: 29785
# Private Inputs: 15
# Public Inputs: 4
# Outputs: 1

motailab/zkbattleship-circuit