- Each player has a board of 10x10 slots.
- Each player has to place 5 ships, sizes of 1, 2, 3, 4 and 5 slots.
- Ships can be oriented vertically or horizontally.
- Ships cannot overlap.
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.
- Each of 100 slots is represented as a tuple
(x, y, ship_number).
- 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.)
- 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):
- Each slot is constrained to have a specific coordinate.
- Each slot is checked to contain
ship_numberfrom 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:
- First 5 slots are constrained to have
ship_number=5and to have successive coordinates along X or Y axis, with coordinate values belonging to a valid range 0-9.
- Next 4, 3, 2 and 1 slot are similarly checked for respective ship shapes.
- All the remaining slots are constrained to have
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:
- 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.
- If the ship is hit, the slots for that ship are randomized to not reveal which part of the ship is hit.
- 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.