zk-battleship

zk-battleship is a blockchain project aimed at exploring the fascinating world of zero-knowledge proofs using Circom. It allows for playing the classic game of Battleship on the blockchain without revealing the board state to the public. This README will guide you through the project's goals, features, installation, usage, and contributions.

Table of Contents

• Introduction
• Features
• Installation
• Circuit Overview
• Contract Overview
• License

Introduction

In the world of blockchain and smart contracts, privacy is a fundamental concern. zk-battleship demonstrates the power of zero-knowledge proofs (ZKPs) by enabling users to play the Battleship game on-chain without revealing sensitive information, such as the positions of their ships.

By utilizing Circom and Solidity, this project showcases how ZKPs can be integrated into decentralized applications, ensuring the confidentiality of data while still enabling trustless interactions.

Features

• Zero-Knowledge Proofs: zk-battleship leverages Circom to create zero-knowledge circuits that enable players to prove the validity of their moves without disclosing the actual board state.

• On-Chain Battleship: Play the classic game of Battleship directly on the blockchain, enjoying the benefits of transparency and trustlessness while keeping your board secret.

• Privacy-Preserving: The project's main focus is on preserving user privacy. No one can access your board state except you.

Installation

To get started with zk-battleship, follow these installation steps:

1. Clone this repository:

   git clone https://github.com/AndrewPochapsky/zk-battleship.git
   cd zk-battleship

2. Install the dependencies:

   • For the circom side, I used circomkit
   • For the solidity side, I used foundry
   • Install dependencies using npm

npm install

3. Run circom tests using npm

npm test

4. Run contract tests using forge

forge test

Circuit Overview

There are two main circuits: VerifyBoard and VerifyImpact.

VerifyBoard is used to verify that a given board state is valid (provided by giving the start and end coordinates of all boats) and outputs a hash commitment. The hash commitment also takes into account a secret value only known to the prover to ensure that the hash cannot be simply brute forced to get the board state. See the GenerateBoardCommitment circuit for the implementation (note that a thorough cryptographic analysis has not been conducted to verify if this is indeed safe against brute force attacks).

VerifyImpact is used to prove that a given coordinate results in a hit or miss in order to reveal the result to the opposing player. The board commitment generated by VerifyBoard must be provided and verified to ensure that the prover is using the same board that they started the game with.

Contract Overview

There are three contracts:

• VerifyBoardVerifier: This contract was generated using npx circomkit contract verify_board and contains the logic to verify a groth16 proof for the VerifyBoard circuit.
• VerifyImpactVerifier: This contract was generated using npx circomkit contract verify_impact and contains the logic to verify a groth16 proof for the VerifyImpact circuit.
• BattleshipManager: This contract contains all of the business logic and has functions to create and play games and interacts with the two verifier contracts to verify proofs. On game creation, each player must provide a valid VerifyBoard proof. The commitments will be stored on-chain to ensure that the players cannot change their boards throughout the game. Each turn plays as follows:

  • Turn 1: Player1 starts the game by providing a coordinate they want Player2 to reveal.

  • Turn 2: Player2 provides a proof of the outcome of the reveal and also provides a coordinate they wish for Player1 to reveal.

    ...

  • Turn n: Going player provides an impact proof of the coordinate proposed by the opposing player during Turn n-1 and provides a coordinate for the opposing player to reveal on Turn n+1.

If at any point a player runs out of ships, the game ends.

There are many possible improvements that can be made here, but as this was mostly just a proof of concept the contract is left without many enhancements. For example, there needs to be a way to prevent a player from refusing to reveal a coordinate impact; a turn timer would likely be a good solution there. It would also be better to allow a form of match making by allowing players to put up games and have others accept them. Right now the logic requires a game to be created in a single transaction which was done for simplicity. Wagers would also be fun, but that really would require that the circuit logic is audited before being used in production.

License

This project is licensed under the GPL-3.0 license - see the LICENSE.md file for details.