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. There are two versions:
The Anybody Problem NFT is a simulation of the bodies moving in space over time. Proofs are generated over s
steps with n
bodies and verified on-chain. This version is represented in the top level nft.circom
circuit here.
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. A very rough draft of the game can be played at https://okwme.github.io/anybody-problem.
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.5
would be represented as150000000
.
NOTICE: Negative Values Due to the nature of finite field arithmetic, negative values are represented as
p-n
wherep
is the prime number used in the finite field andn
is the absolute value of the negative number.For example,
-1
would 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 is0
when the difference is outside the margin of error and1
when 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_y
andradius/mass
. These are all scaled up by a factor of 10**8.output out_forces
- An array of length 2 for each force,force_x
andforce_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 lengthtotalBodies
for each body. Each body has 5 inputs:position_x
,position_y
,vector_x
,vector_y
andradius/mass
input missile[5]
- An array of length 5 for the missile. Each missile has 5 inputs:position_x
,position_y
,vector_x
,vector_y
andradius/mass
. These are all scaled up by a factor of 10**8.output out_bodies[totalBodies][5]
- An array of lengthtotalBodies
for each body. Each body has 5 outputs:position_x
,position_y
,vector_x
,vector_y
andradius/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_y
andradius/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 lengthtotalBodies
for each body. Each body has 5 inputs:position_x
,position_y
,vector_x
,vector_y
andradius/mass
. These are all scaled up by a factor of 10**8.output out_bodies[totalBodies][5]
- An array of lengthtotalBodies
for each body. Each body has 5 outputs:position_x
,position_y
,vector_x
,vector_y
andradius/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 circuit is the top level circuit for the NFT version of Anybody Problem. It takes in the initial state of the bodies and the number of steps to simulate and outputs the resulting bodies.
totalBodies
- The total number of bodies in the simulationsteps
- The total number of steps to simulateinput bodies[totalBodies][5]
- An array of lengthtotalBodies
for each body. Each body has 5 inputs:position_x
,position_y
,vector_x
,vector_y
andradius/mass
. These are all scaled up by a factor of 10**8.output out_bodies[totalBodies][5]
- An array of lengthtotalBodies
for each body. Each body has 5 outputs:position_x
,position_y
,vector_x
,vector_y
andradius/mass
. These are all scaled up by a factor of 10**8.
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 lengthtotalBodies
for each body. Each body has 5 inputs:position_x
,position_y
,vector_x
,vector_y
andradius/mass
. These are all scaled up by a factor of 10**8.input missiles[steps + 1][5]
- An array of lengthsteps + 1
for each missile. Each missile has 5 inputs:position_x
,position_y
,vector_x
,vector_y
andradius/mass
. These are all scaled up by a factor of 10**8.output out_bodies[totalBodies][5]
- An array of lengthtotalBodies
for each body. Each body has 5 outputs:position_x
,position_y
,vector_x
,vector_y
andradius/mass
. These are all scaled up by a factor of 10**8.
To run rudimentary tests on the various circuits use the following command:
yarn test
You should see something like:
absoluteValueSubtraction circuit
✔ produces a witness with valid constraints
✔ has the correct output
acceptableMarginOfError circuit
✔ produces a witness with valid constraints
✔ has the correct output
Bodies Tests
✔ has the correct bodies, dust addresses
✔ onlyOwner functions are really only Owner
✔ updates dust price correctly
✔ has all the correct interfaces
✔ fallback and receive functions revert
✔ onlyProblem functions can only be called by Problems address
✔ matches seeds between Bodies and Problems contracts
✔ mints a new body after receiving Dust
✔ fails when you try to mint a body for a problem you do not own
✔ validate second mint event
✔ succeeds adding a body into a problem
✔ removes a body that was added into a problem
✔ mints a body, adds it to a problem, then mints another body
- combines two bodies correctly
✔ fails to mint an 11th body
calculateForceMain circuit
✔ produces a witness with valid constraints
✔ has the correct output
detectCollisionMain circuit
✔ produces a witness with valid constraints
✔ has the correct output
forceAccumulatorMain circuit
✔ produces a witness with valid constraints
✔ 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
ProblemMetadata Tests
✔ has the correct problems address
✔ onlyOwner functions are really only Owner
✔ creates an SVG
BoodyMetadata Tests
✔ has the correct problems address
✔ onlyOwner functions are really only Owner
✔ creates an SVG
nft circuit
✔ produces a witness with valid constraints
✔ has the correct output
✔ NftVerifier.sol works
Problem Tests
✔ has the correct verifiers problemMetadata, bodies, dust, solver addresses
✔ onlyOwner functions are really only Owner
✔ onlySolver functions are really only Solver
✔ has all the correct interfaces
✔ emits 'EthMoved' events when eth is moved
✔ fails when unitialized
✔ fails to adminMint when uninitialized
✔ fails to adminMint when not owner
- sends money to splitter correctly
✔ must be unpaused
✔ succeeds to mint
✔ succeeds to mint with fallback method
✔ succeeds to mint with explicit recipient
✔ token ID is correctly correlated
✔ validate second mint event
✔ checks whether mint fails with wrong price and succeeds even when price = 0
✔ adminMint from owner address
✔ stores the verifiers in the correct order of the mapping
✔ mints bodies that contain valid values
✔ mints a body via mintBodyToProblem
Solver Tests
✔ has the correct problems, dust addresses
✔ onlyOwner functions are really only Owner
✔ fallback and receive functions revert
✔ creates a proof for 3 bodies
✔ creates multiple proofs in a row
✔ creates proofs for multiple bodies
✔ has the correct body boost amount
✔ adds a body, removes a body, creates a proof
- adds two bodies, removes first body, creates a proof
stepStateTest circuit
✔ produces a witness with valid constraints
✔ has the correct output
Utilities work as expected
✔ should only allow valid seeds
66 passing (1m)
3 pending
✨ Done in 64.01s.
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 |
nft(3, 10) | 15_184 | 26.34 |
stepState(3, 10) | 19_121 | 20.92 |
nft_3_20 | 33_060 | |
nft_4_20 | 55_480 |
Generated proof in 0m 3s 121ms for 20 ticks with 3 bodies
Tick rate: 6.41 ticks/s
Tick rate per body: 2.14 ticks/s
Dust rate: 6.41 dust/s
Dust rate per body: 2.14 dust/s
Generated proof in 0m 3s 894ms for 20 ticks with 4 bodies
Tick rate: 5.14 ticks/s
Tick rate per body: 1.28 ticks/s
Dust rate: 10.27 dust/s
Dust rate per body: 2.57 dust/s
Generated proof in 0m 6s 701ms for 20 ticks with 5 bodies
Tick rate: 2.98 ticks/s
Tick rate per body: 0.60 ticks/s
Dust rate: 11.94 dust/s
Dust rate per body: 2.39 dust/s
Generated proof in 0m 7s 910ms for 20 ticks with 6 bodies
Tick rate: 2.53 ticks/s
Tick rate per body: 0.42 ticks/s
Dust rate: 20.23 dust/s
Dust rate per body: 3.37 dust/s
Generated proof in 0m 12s 961ms for 20 ticks with 7 bodies
Tick rate: 1.54 ticks/s
Tick rate per body: 0.22 ticks/s
Dust rate: 24.69 dust/s
Dust rate per body: 3.53 dust/s
Generated proof in 0m 14s 497ms for 20 ticks with 8 bodies
Tick rate: 1.38 ticks/s
Tick rate per body: 0.17 ticks/s
Dust rate: 44.15 dust/s
Dust rate per body: 5.52 dust/s
Generated proof in 0m 16s 339ms for 20 ticks with 9 bodies
Tick rate: 1.22 ticks/s
Tick rate per body: 0.14 ticks/s
Dust rate: 78.34 dust/s
Dust rate per body: 8.70 dust/s
Generated proof in 0m 25s 522ms for 20 ticks with 10 bodies
Tick rate: 0.78 ticks/s
Tick rate per body: 0.08 ticks/s
Dust rate: 100.31 dust/s
Dust rate per body: 10.03 dust/s
A basic circom project using Hardhat and hardhat-circom. This combines the multiple steps of the Circom and SnarkJS workflow into your Hardhat workflow.
By providing configuration containing your Phase 1 Powers of Tau and circuits, this plugin will:
- Compile the circuits
- Apply the final beacon
- Output your
wasm
andzkey
files - Generate and output a
Verifier.sol
See the source projects for full documentation and configuration
yarn
to install dependencies
yarn circom:dev
to build deterministic development circuits.
Further, for debugging purposes, you may wish to inspect the intermediate files. This is possible with the --debug
flag which the circom:dev
task enables by default. You'll find them (by default) in artifacts/circom/
To build a single circuit during development, you can use the --circuit
CLI parameter. For example, if you make a change to hash.circom
and you want to only rebuild that, you can run yarn circom:dev --circuit hash
.
yarn circom:prod
for production builds (using Date.now()
as entropy)
yarn install
yarn serve
yarn build
yarn lint