You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
The larger the state and message tree depths, the more gas that a user (or relayer) has to pay to sign up or publish a message. The larger the vote option tree, state tree, and message tree depths, the longer it will take for the coordinator to generate proofs.
We can assume that the coordinator has more computational power than the average user, so it's okay to set the vote option tree to the maximum feasible size on consumer hardware (5 ^ 5 = 3125 leaves).
The message tree size should be large enough such that each user can cast 1 vote per vote option, plus an additional key-change message on top of that.
Let the depth of the state tree be s, the depth of the message tree be m, the depth of the vote option tree be v, and the number of voice credits as c.
Each user should be able to publish at least c + 1 messages, or 5 ** v + 1 messages, whichever is smaller. This is to let them either spend all their voice credits (1 credit per vote) or vote for up to all available vote options. Let this value be n.
The depth of the message tree should therefore be ceil(log2(2 ** s * n)).
E.g. Assuming that each user has 99 voice credits, the vote option tree depth is 4, and the state tree depth is 4:
n = 2 ** 4 + 1 = 17
ceil(log2(2 ** 4 * 17)) = 9
Predefined tree depths
State tree depth
Message tree depth
Vote option tree depth
Deployment gas
Signup gas
Publish message gas
10
17
5
9136375
551133
1055361
4
4
2
7274945
333357
583713
Ultimately, whoever builds upon MACI has to decide exactly which tree depths works for their use case, and they have to be responsible for its specific trusted setup.
That said, if we use a Quadtree (see #101), we can support larger trees.
CC: we should just use Large because the gas savings are not that large
The text was updated successfully, but these errors were encountered:
The larger the state and message tree depths, the more gas that a user (or relayer) has to pay to sign up or publish a message. The larger the vote option tree, state tree, and message tree depths, the longer it will take for the coordinator to generate proofs.
We can assume that the coordinator has more computational power than the average user, so it's okay to set the vote option tree to the maximum feasible size on consumer hardware (
5 ^ 5 = 3125
leaves).The message tree size should be large enough such that each user can cast 1 vote per vote option, plus an additional key-change message on top of that.
Let the depth of the state tree be
s
, the depth of the message tree bem
, the depth of the vote option tree bev
, and the number of voice credits asc
.Each user should be able to publish at least
c + 1
messages, or5 ** v + 1
messages, whichever is smaller. This is to let them either spend all their voice credits (1 credit per vote) or vote for up to all available vote options. Let this value ben
.The depth of the message tree should therefore be
ceil(log2(2 ** s * n))
.E.g. Assuming that each user has 99 voice credits, the vote option tree depth is 4, and the state tree depth is 4:
Predefined tree depths
Ultimately, whoever builds upon MACI has to decide exactly which tree depths works for their use case, and they have to be responsible for its specific trusted setup.
That said, if we use a Quadtree (see #101), we can support larger trees.
CC: we should just use Large because the gas savings are not that large
The text was updated successfully, but these errors were encountered: