Bulletproofs Battleships

bulletproofs_battleships.md

Bulletproofs battleships

Rules

1. Each player has a board of 10x10 slots.
2. Each player has to place 5 ships, sizes of 1, 2, 3, 4 and 5 slots.
3. Ships can be oriented vertically or horizontally.
4. Ships cannot overlap.

Goal

Construct a proof system where each player can commit to a placement of their ships and prove its correctness, and then provide proofs of hitting or missing shots aimed at their ships.

Solution

Preliminaries:

1. Each of 100 slots is represented as a tuple (x, y, ship_number).
2. Each ship has a number from 1 to 5 identifying the size of the ship. (If multiple ships of the same size are allowed, separate unique numbers are used for each ship.)
3. Empty slots are identified by ship_number = 0.

Proof of initial layout

The core of the protocol is verifiable shuffle gadget that proves that two sets of slots are equal up to an order.

The input slots are ordered by coordinates (left to right, top to bottom):

1. Each slot is constrained to have a specific coordinate.
2. Each slot is checked to contain ship_number from 0 to 5 to enforce that it cannot be occupied by two or mote ships.

Constraints on input slots enforce that all coordinates are correct and assigned valid values without overlapping. But they do not check that all or correct ships are assigned.

The output slots are ordered by ships:

1. First 5 slots are constrained to have ship_number=5 and to have successive coordinates along X or Y axis, with coordinate values belonging to a valid range 0-9.
2. Next 4, 3, 2 and 1 slot are similarly checked for respective ship shapes.
3. All the remaining slots are constrained to have ship_number=0.

Constraints on output slots enforce that all ships are correctly oriented and assigned, and no excess ships are added.

The proof requires an order of 500-2000 multipliers and the resulting proof size is expected to be somewhere around 1-3Kb in size.

TBD: specify exact circuit and commitments.

Proof of shot

To prove that at a given (x,y) coordinate, a ship is missed, scratched or destroyed, we run a modified Proof-of-Layout protocol, as described above, with the following modifications:

1. A constraint is added that one of the slots on the right side of the shuffle has coordinate explicitly assigned to the specified (x,y) value. The type of the ship (or whether it's a miss) is inferred from the slot's position.
2. If the ship is hit, the slots for that ship are randomized to not reveal which part of the ship is hit.
3. To maintain integrity of the layout for the hit ship, additional N-item shuffle is added for this ship only, which proves on the right side that coordinates are laid out correctly and match the ship commitment.

The proof is only slightly larger and dependent on the size of the affected ship. If no ship is hurt, the proof size is the same as for the layout.