Anybody Problem is a circom project that models the movement of any number of n bodies using classic newtonian-like physics over any number of s steps.
The Anybody Problem Game adds an additional missiles input that allows a user to fire missiles at the bodies in order to destroy them. This version is represented in the top level stepState.circom circuit here. The game is live at anybody.gg
There are a number of circuits involved in Anybody Problem. They're listed below with links and short descriptions.
NOTICE: Scaling Factor
Due to the lack of float values in circom, the values are scaled up by a factor of 10**8. This means that the values are integers and the decimal point is implied. For example, the value1.5would be represented as150000000.
NOTICE: Negative Values Due to the nature of finite field arithmetic, negative values are represented as
p-nwherepis the prime number used in the finite field andnis the absolute value of the negative number.For example,
-1would be represented as:21888242871839275222246405745257275088548364400416034343698204186575808495617 - 1
or
21888242871839275222246405745257275088548364400416034343698204186575808495616.
This circuit finds the absolute value difference between two numbers.
n- The maximum number of bits for each input valueinput in[2]- An array of length 2 for each input valueoutput out- The difference between the two values
This circuit is used in tandem with approxDiv and approxSqrt which are both defined in approxMath.circom. When finding the approximate solution to division or the approximate square root of a value, there is an acceptable margin of error to be expected. This circuit ensures the value is within that range.
n- The maximum number of bits for each input valueinput expected- The expected valueinput actual- The actual valueinput marginOfError- The margin of erroroutput out- The output value is0when the difference is outside the margin of error and1when within the margin of error.
This circuit calculates the gravitational force between two bodies based on their mass and position in space.
input in_bodies[2][5]- An array of length 2 for each body. Each body has 5 inputs:position_x,position_y,vector_x,vector_yandradius/mass. These are all scaled up by a factor of 10**8.output out_forces- An array of length 2 for each force,force_xandforce_y
This circuit detects if a body and a missile are colliding. It does this by calculating the distance between the two and comparing it to the sum of their radii. If a collision is detected, the radius/mass of the body and the missile are returned as 0.
totalBodies- The total number of bodies in the simulationinput bodies[totalBodies][5]- An array of lengthtotalBodiesfor each body. Each body has 5 inputs:position_x,position_y,vector_x,vector_yandradius/massinput missile[5]- An array of length 5 for the missile. Each missile has 5 inputs:position_x,position_y,vector_x,vector_yandradius/mass. These are all scaled up by a factor of 10**8.output out_bodies[totalBodies][5]- An array of lengthtotalBodiesfor each body. Each body has 5 outputs:position_x,position_y,vector_x,vector_yandradius/mass. These are all scaled up by a factor of 10**8.output out_missile[5]- An array of length 5 for the missile. Each missile has 5 outputs:position_x,position_y,vector_x,vector_yandradius/mass. These are all scaled up by a factor of 10**8.
This circuit calculates the total force on each body based on the gravitational force between each pair of bodies. It limits the vector by a maximum value and updates the position of each body based on its accumulated force. If the new position is outside the boundary of the simulation, it is updated to be on the opposite side as if the area was a torus.
totalBodies- The total number of bodies in the simulationinput in_bodies[totalBodies][5]- An array of lengthtotalBodiesfor each body. Each body has 5 inputs:position_x,position_y,vector_x,vector_yandradius/mass. These are all scaled up by a factor of 10**8.output out_bodies[totalBodies][5]- An array of lengthtotalBodiesfor each body. Each body has 5 outputs:position_x,position_y,vector_x,vector_yandradius/mass. These are all scaled up by a factor of 10**8.
This circuit calculates the distance between two coordinate points using approxSqrt() and checking the result is within an acceptable margin of error using AcceptableMarginOfError().
n- The maximum number of bits for each input value and expected output value.input x1- The x coordinate of the first pointinput y1- The y coordinate of the first pointinput x2- The x coordinate of the second pointinput y2- The y coordinate of the second pointoutput distance- The distance between the two points
This circuit limits the value of an input to a maximum value. It also accepts an alternative value that is returned if the input value is greater than the maximum.
n- The maximum number of bits for each input value and expected output value.input in- The input valueinput limit- The maximum valueinput rather- The alternative valueoutput out- The output value
This circuit limits the value of an input to a minimum value. It also accepts an alternative value that is returned if the input value is less than the minimum.
n- The maximum number of bits for each input value and expected output value.input in- The input valueinput limit- The minimum valueinput rather- The alternative valueoutput out- The output value
This is the top level circuit for the game version of Anybody Problem. It takes in the initial state of the bodies, the number of steps to simulate and the missiles to fire and outputs the resulting bodies.
totalBodies- The total number of bodies in the simulation.steps- The total number of steps to simulate.input bodies[totalBodies][5]- An array of lengthtotalBodiesfor each body. Each body has 5 inputs:position_x,position_y,vector_x,vector_yandradius/mass. These are all scaled up by a factor of 10**8.input missiles[steps + 1][5]- An array of lengthsteps + 1for each missile. Each missile has 5 inputs:position_x,position_y,vector_x,vector_yandradius/mass. These are all scaled up by a factor of 10**8.output out_bodies[totalBodies][5]- An array of lengthtotalBodiesfor each body. Each body has 5 outputs:position_x,position_y,vector_x,vector_yandradius/mass. These are all scaled up by a factor of 10**8.
In order to run tests you need to have compiled circuits generated. You can do this by running:
yarn circom:game-testThis will generate smaller versions of the circuits, each only covering 20 frames of gameplay at a time. These should allow you to run most tests, the exception being stepstate.test.js where there is a test used to check proofs generated from real games called "passes one off check input".
To prepare for production, run the following command:
yarn circom:game-prodThis might take a while to generate but it will only produce proofs for 4 bodies at 250 frames of gameplay and 6 bodies at 125 frames of gameplay. All levels can be proven with these two circuits because the missing bodies are added with radius of 0 so they don't impact the simulation.
While games can be proven in browser, the variation of hardware prevents accurate prognosis of which machines are capabale of doing so in a reasonable time. As such we are using the service Sindri to generate proofs reliably fast. To ensure Sindri is unable to generate valid but incorrect proofs, we generate the prover files locally and then upload them to Sindri. To do this ensure the zkey file is named the same as the circuit file and is referenced with the same name as that used in circuitPath in the sindri.json file. For example, when uploading the zkey for game_4_250.circom that contains the StepState circuit, the sindri.json looks like this:
{
"$schema": "https://forge.sindri.app/api/v1/sindri-manifest-schema.json",
"name": "game_4_250_v7",
"circuitType": "circom",
"circuitPath": "./game_4_250.circom",
"curve": "bn254",
"provingScheme": "groth16",
"witnessCompiler": "c++"
}and the zkey is saved at ./circuits/game_4_250.zkey.
To run rudimentary tests on the various circuits use the following command:
yarn testYou should see something like:
> yarn test
yarn run v1.22.22
$ hardhat test
·------------------------|--------------------------------|--------------------------------·
| Solc version: 0.6.11 · Optimizer enabled: false · Runs: 200 │
·························|································|·································
| Contract Name · Deployed size (KiB) (change) · Initcode size (KiB) (change) │
·························|································|·································
| AnybodyProblem · 19.820 (0.000) · 21.935 (0.000) │
·························|································|·································
| AnybodyProblemMock · 20.123 (0.000) · 22.237 (0.000) │
·························|································|·································
| AnybodyProblemV0 · 18.953 (0.000) · 21.295 (0.000) │
·························|································|·································
| AnybodyProblemV0Mock · 19.200 (0.000) · 21.542 (0.000) │
·························|································|·································
| Assets1 · 19.754 (0.000) · 19.781 (0.000) │
·························|································|·································
| Assets2 · 23.139 (0.000) · 23.167 (0.000) │
·························|································|·································
| Assets3 · 20.617 (0.000) · 20.645 (0.000) │
·························|································|·································
| Assets4 · 16.870 (0.000) · 16.897 (0.000) │
·························|································|·································
| Assets5 · 16.719 (0.000) · 16.746 (0.000) │
·························|································|·································
| ExternalMetadata · 18.384 (0.000) · 18.580 (0.000) │
·························|································|·································
| Speedruns · 7.716 (0.000) · 8.009 (0.000) │
·------------------------|--------------------------------|--------------------------------·
absoluteValueSubtraction circuit
✔ produces a witness with valid constraints
✔ has the correct output
acceptableMarginOfError circuit
✔ produces a witness with valid constraints
✔ has the correct output
calculateForceMain circuit
✔ produces a witness with valid constraints
- can check the differnce in speed calculating with witness vs anybody.js
✔ has the correct output
detectCollisionMain circuit
✔ produces a witness with valid constraints
✔ has the correct output
forceAccumulatorMain circuit
✔ produces a witness with valid constraints (41ms)
✔ has the correct output
getDistanceMain circuit
✔ produces a witness with valid constraints
✔ has the correct output
limiterMain circuit
✔ produces a witness with valid constraints
✔ has the correct output
lowerLimiterMain circuit
✔ produces a witness with valid constraints
✔ has the correct output
nft circuit
- produces a witness with valid constraints
- has the correct output
- NftVerifier.sol works
stepStateTest circuit
✔ produces a witness with valid constraints (277ms)
✔ passes one off check input (24710ms)
✔ has the correct output when one body and missile positioned to hit and it returns correct number of steps (70ms)
AnybodyProblem Tests
✔ has the correct verifiers, externalMetadata, speedruns addresses (397ms)
✔ stores the verifiers in the correct order of the mapping (300ms)
- starts week correctly
✔ has the correct Speedruns addresses (303ms)
✔ onlyOwner functions are really only Owner (397ms)
✔ fallback and receive functions revert (312ms)
✔ creates a proof for level 1 (2680ms)
✔ solves the first level using mock (4518ms)
✔ must be unpaused (334ms)
✔ solves all levels async using mock (26775ms)
✔ solves all levels in a single tx (14845ms)
✔ has the same results for generateLevelData as anybody.js (392ms)
✔ has correct getLevelFromInputs with no dummy (312ms)
✔ has correct getLevelFromInputs with dummy (309ms)
✔ returns correct currentLevel (4577ms)
✔ performs an upgrade and the records are correct (29157ms)
- emits arbitrary events within Speedruns
- tests an arbitrary tx
ExternalMetadata Tests
✔ has the correct anybodyProblem and speedruns addresses (355ms)
✔ onlyOwner functions are really only Owner (339ms)
✔ has valid json (17636ms)
Speedruns Tests
✔ onlyAnybodyProblem functions can only be called by AnybodyProblem address (387ms)
✔ has all the correct interfaces (354ms)
39 passing (2m)
7 pending
······························································································································································································
| Solidity and Network Configuration │
·········································································································|·················|···············|·················|································
| Solidity: 0.6.11 · Optim: false · Runs: 200 · viaIR: false · Block: 20,000,000 gas │
·········································································································|·················|···············|·················|································
| Network: ETHEREUM · L1: 0.10000 gwei · · 2521.10 usd/eth │
·········································································································|·················|···············|·················|················|···············
| Contracts / Methods · Min · Max · Avg · # calls · usd (avg) │
·········································································································|·················|···············|·················|················|···············
| AnybodyProblem · │
·········································································································|·················|···············|·················|················|···············
| batchSolve(uint256,bool,uint256,uint256[],uint256[2][],uint256[2][2][],uint256[2][],uint256[][]) · - · - · 1,263,522 · 2 · 0.32 │
·········································································································|·················|···············|·················|················|···············
| recoverUnsuccessfulPayment(address) · - · - · 30,247 · 2 · 0.01 │
·········································································································|·················|···············|·················|················|···············
| updateDiscount(uint256) · - · - · 24,462 · 2 · 0.01 │
·········································································································|·················|···············|·················|················|···············
| updatePaused(bool) · - · - · 45,769 · 2 · 0.01 │
·········································································································|·················|···············|·················|················|···············
| updatePriceToMint(uint256) · - · - · 24,924 · 2 · 0.01 │
·········································································································|·················|···············|·················|················|···············
| updatePriceToSave(uint256) · - · - · 27,232 · 2 · 0.01 │
·········································································································|·················|···············|·················|················|···············
| updateProceedRecipient(address) · - · - · 30,194 · 2 · 0.01 │
·········································································································|·················|···············|·················|················|···············
| updateSpeedrunsAddress(address) · - · - · 29,490 · 2 · 0.01 │
·········································································································|·················|···············|·················|················|···············
| updateVerifier(address,uint256,uint256) · - · - · 46,664 · 2 · 0.01 │
·········································································································|·················|···············|·················|················|···············
| AnybodyProblemMock · │
·········································································································|·················|···············|·················|················|···············
| batchSolve(uint256,bool,uint256,uint256[],uint256[2][],uint256[2][2][],uint256[2][],uint256[][]) · 1,902,008 · 9,547,209 · 4,452,577 · 37 · 1.12 │
·········································································································|·················|···············|·················|················|···············
| setMockedBodyDataByLevel(uint256,(uint256,uint256,uint256,uint256,uint256,uint256,bytes32)[6]) · 124,905 · 942,401 · 556,054 · 28 · 0.14 │
·········································································································|·················|···············|·················|················|···············
| updatePaused(bool) · - · - · 45,763 · 1 · 0.01 │
·········································································································|·················|···············|·················|················|···············
| updateProceedRecipient(address) · - · - · 30,232 · 1 · 0.01 │
·········································································································|·················|···············|·················|················|···············
| AnybodyProblemV0Mock · │
·········································································································|·················|···············|·················|················|···············
| batchSolve(uint256,bool,uint256,uint256[],uint256[2][],uint256[2][2][],uint256[2][],uint256[][]) · - · - · 8,031,319 · 3 · 2.02 │
·········································································································|·················|···············|·················|················|···············
| setMockedBodyDataByLevel(uint256,(uint256,uint256,uint256,uint256,uint256,uint256,bytes32)[6]) · 383,080 · 942,416 · 662,753 · 5 · 0.17 │
·········································································································|·················|···············|·················|················|···············
| ExternalMetadata · │
·········································································································|·················|···············|·················|················|···············
| setAssets(address[5]) · 137,001 · 137,013 · 137,011 · 20 · 0.03 │
·········································································································|·················|···············|·················|················|···············
| setupSVGPaths() · - · - · 1,806,648 · 40 · 0.46 │
·········································································································|·················|···············|·················|················|···············
| updateAnybodyProblemAddress(address) · 29,326 · 46,438 · 37,479 · 42 · 0.01 │
·········································································································|·················|···············|·················|················|···············
| updateSpeedrunsAddress(address) · 29,008 · 46,108 · 44,553 · 22 · 0.01 │
·········································································································|·················|···············|·················|················|···············
| __burn(address,uint256,uint256) · - · - · 28,073 · 2 · 0.01 │
·········································································································|·················|···············|·················|················|···············
| __mint(address,uint256,uint256,bytes) · - · - · 52,830 · 4 · 0.01 │
·········································································································|·················|···············|·················|················|···············
| __safeTransferFrom(address,address,uint256,uint256,bytes) · - · - · 53,906 · 2 · 0.01 │
·········································································································|·················|···············|·················|················|···············
| __setApprovalForAll(address,address,bool) · - · - · 48,789 · 2 · 0.01 │
·········································································································|·················|···············|·················|················|···············
| Speedruns · │
·········································································································|·················|···············|·················|················|···············
| emitGenericEvent(bytes32[],bytes) · - · - · 25,003 · 2 · 0.01 │
·········································································································|·················|···············|·················|················|···············
| updateAnybodyProblemAddress(address) · 29,172 · 46,284 · 37,524 · 41 · 0.01 │
·········································································································|·················|···············|·················|················|···············
| Deployments · · % of limit · │
·········································································································|·················|···············|·················|················|···············
| AnybodyProblem · 4,863,675 · 4,863,699 · 4,863,698 · 24.3 % · 1.23 │
·········································································································|·················|···············|·················|················|···············
| AnybodyProblemMock · 4,931,197 · 4,990,909 · 4,943,147 · 24.7 % · 1.25 │
·········································································································|·················|···············|·················|················|···············
| AnybodyProblemV0 · 4,688,531 · 4,688,543 · 4,688,539 · 23.4 % · 1.18 │
·········································································································|·················|···············|·················|················|···············
| AnybodyProblemV0Mock · 4,743,168 · 4,743,192 · 4,743,183 · 23.7 % · 1.20 │
·········································································································|·················|···············|·················|················|···············
| Assets1 · - · - · 4,427,169 · 22.1 % · 1.12 │
·········································································································|·················|···············|·················|················|···············
| Assets2 · - · - · 5,177,023 · 25.9 % · 1.31 │
·········································································································|·················|···············|·················|················|···············
| Assets3 · - · - · 4,618,748 · 23.1 % · 1.16 │
·········································································································|·················|···············|·················|················|···············
| Assets4 · - · - · 3,788,953 · 18.9 % · 0.96 │
·········································································································|·················|···············|·················|················|···············
| Assets5 · - · - · 3,755,434 · 18.8 % · 0.95 │
·········································································································|·················|···············|·················|················|···············
| ExternalMetadata · 4,170,569 · 4,170,581 · 4,170,580 · 20.9 % · 1.05 │
·········································································································|·················|···············|·················|················|···············
| Game_2_20Verifier.sol:Groth16Verifier · - · - · 1,389,269 · 6.9 % · 0.35 │
·········································································································|·················|···············|·················|················|···············
| Game_3_20Verifier.sol:Groth16Verifier · - · - · 1,739,395 · 8.7 % · 0.44 │
·········································································································|·················|···············|·················|················|···············
| Game_4_20Verifier.sol:Groth16Verifier · - · - · 2,089,585 · 10.4 % · 0.53 │
·········································································································|·················|···············|·················|················|···············
| Game_5_20Verifier.sol:Groth16Verifier · - · - · 2,440,280 · 12.2 % · 0.62 │
·········································································································|·················|···············|·················|················|···············
| Game_6_20Verifier.sol:Groth16Verifier · - · - · 2,790,971 · 14 % · 0.70 │
·········································································································|·················|···············|·················|················|···············
| Speedruns · - · - · 1,790,475 · 9 % · 0.45 │
·········································································································|·················|···············|·················|················|···············
| ThemeGroupBlues.sol:ThemeGroup · - · - · 1,002,009 · 5 % · 0.25 │
·········································································································|·················|···············|·················|················|···············
| Key │
······························································································································································································
| ◯ Execution gas for this method does not include intrinsic gas overhead │
······························································································································································································
| △ Cost was non-zero but below the precision setting for the currency display (see options) │
······························································································································································································
| Toolchain: hardhat │
······························································································································································································
✨ Done in 133.89s.Currently the project is targeting powersOfTau28_hez_final_20.ptau which has a limit of 1MM constraints. Below is a table of the number of constraints used by each circuit.
| Circuit | Non-Linear Constraints | seconds at 25fps under 1MM constraints |
|---|---|---|
| absoluteValueSubtraction(252) | 257 | 155.64 |
| acceptableMarginOfError(60) | 125 | 320 |
| calculateForce() | 279 | 143.37 |
| detectCollision(3) | 348 | 114.94 |
| forceAccumulator(3) | 1_522 | 26.28 |
| getDistance(20) | 88 | 454.55 |
| limiter(252) | 254 | 157.48 |
| lowerLimiter(252) | 254 | 157.48 |
| stepState(3, 10) | 19_121 | 20.92 |