Battleship.circom

/* 
Author: Tobe :)

ZKP Circuits for a Game of Battleship

Circom: https://github.com/iden3/circom
3rd-Party circuits gotten from: https://github.com/iden3/circomlib
*/

pragma circom 2.1.5;

include "../node_modules/circomlib/circuits/comparators.circom";
include "../node_modules/circomlib/circuits/mimcsponge.circom";


// A ship has the right number of coordinates
// And those coordinates form a straight line
// Horizontally or vertically
template ShipMatchesShape(shape){
    signal input coords[shape][2];
    signal output out;

    // Ensure that for all the coords, 
    // they must have the same X or Y values (they must be touching)
    component isEqualCompX[shape];
    component isEqualCompY[shape];

    for(var i = 0; i < (shape - 1); i++){
        isEqualCompX[i] = IsEqual();
        isEqualCompX[i].in[0] <== coords[i][0];
        isEqualCompX[i].in[1] <== coords[i + 1][0];

        isEqualCompY[i] = IsEqual();
        isEqualCompY[i].in[0] <== coords[i][1];
        isEqualCompY[i].in[1] <== coords[i + 1][1];
    }

    var isEqualX = 0;
    var isEqualY = 0;

    for(var i = 0; i < (shape - 1); i++){
        isEqualX = isEqualX | isEqualCompX[i].out;
        isEqualY = isEqualY | isEqualCompX[i].out;
    }
    out <== isEqualX | isEqualY;
}

// Verify that Ship pieces are unique
// And ship coordinates are less than board size
template ValidShipCoordinates(boardSize, noShipPieces) {
    signal input shipCoords[noShipPieces][2];
    signal output out;
    
    component lessThanEqComp[noShipPieces][2];
    component isEqualComp[noShipPieces - 1];
    component mimcShipPiecesComp[noShipPieces];
    component mimcOutComp = MiMCSponge(noShipPieces, 220, 1);
    mimcOutComp.k <== 0;

    // Verify coordinates are less than the whole field/squares
    for(var i = 0; i < noShipPieces; i++){
        // Verify x coordinate
        lessThanEqComp[i][0] = LessEqThan(2);
        lessThanEqComp[i][0].in[0] <== shipCoords[i][0];
        lessThanEqComp[i][0].in[1] <== boardSize;
        lessThanEqComp[i][0].out === 1;

        // Verify y coordinate
        lessThanEqComp[i][1] = LessEqThan(2);
        lessThanEqComp[i][1].in[0] <== shipCoords[i][1];
        lessThanEqComp[i][1].in[1] <== boardSize;
        lessThanEqComp[i][1].out === 1;

        // Hash coordinates together
        mimcShipPiecesComp[i] = MiMCSponge(2, 220, 1);
        mimcShipPiecesComp[i].ins[0] <== shipCoords[i][0];
        mimcShipPiecesComp[i].ins[1] <== shipCoords[i][1];
        mimcShipPiecesComp[i].k <== 0;

        mimcOutComp.ins[i] <== mimcShipPiecesComp[i].outs[0];

        if (i > 0){    
            var j = i - 1;
            isEqualComp[j] = IsEqual();
            isEqualComp[j].in[0] <== mimcShipPiecesComp[j].outs[0];
            isEqualComp[j].in[1] <== mimcShipPiecesComp[j + 1].outs[0];
        }
    }

    // Verify coordinate hashes are unique
    for (var i = 0; i < (noShipPieces - 1); i++){
        isEqualComp[i].out === 0;
    }
        
    out <== mimcOutComp.outs[0];
}

// Board Size of 20x20
// Each player gets 10 coordinates to build their ships
component main = ValidShipCoordinates(20, 10);