# MACI v1.0: pairwise coordination subsidy ## Introduction Quadratic funding is a protocol for efficiently allocating funds to public goods. Suppose there are total $m$ projects (i.e. $\{p_1,\cdots,p_m\}$) and $n$ contributors (i.e. $\{u_1,\cdots, u_n\}$). Each contributor $u_i$ can allocate his/her money into different projects. We can record his/her opinion (or votes) into an array $(v_{i1},\cdots,v_{im})$. The actual contribution of $u_i$ is the square of the votes $C_i=(v_{i1}^2,\cdots,v_{im}^2)$. This is why we use the name quadratic funding. Given a project $l\in \{1,\cdots,m\}$, the total allocation to this project is the sum of contributions from contributors with subsidy allocated by the protocol's public funding pool. The basic form of calculating the subsidy is illustrated by the following picture: ![](https://i.imgur.com/2xHRHAN.png) where the green squares are the contributions from different contributors to project $p_l$. Each of the yellow rectangular is the subsidy allocated by the protocol according to the contributions of each contributor pair $(u_i, u_j)$ to this project. Thus total area of the big square is the total funding to this project: $$F_l=(\sum_i^nv_{il})^2$$ The subsidy allocated by the public funding pool (assuming we have enough public fund) is given by $$S_l=(\sum_i^nv_{il})^2-\sum_i^nv_{il}^2=\sum_{i\neq j}v_{il}v_{jl}$$ There is one issue from the basic quadratic funding, if two contributors collude with each other, they can extract most of the public funding pool if they have enough money. In this [post](https://ethresear.ch/t/pairwise-coordination-subsidies-a-new-quadratic-funding-design/5553), Vitalik introduced this kind of collusion and also proposed a protocol to penalize this behavior. In order to penalize the potential collusion from contributors, we generalize the subsidy formula: $$S_l = \sum_{i\neq j} k_{ij}v_{il}v_{jl}$$ Notice that when $k_{ij}=1$, it's the basic clr formula and when $k_{ij}=0$, there is no subsidy allocated to the project. So the general idea is that the more correlation between $(u_i, u_j)$, the smaller $k_{ij}$, hence the smaller subsidy allocated to this project. Vitalik proposed the following $k_{ij}$ coefficient: $$k_{ij}=\frac{M}{M+(\sum_{l=1}^mv_{il}v_{jl})^{\alpha}}$$ Here $M$ and $\alpha$ are protocol related constants. In this case, there is an upper bound that the contributors can extract from the public funding pool. In the general form, the subsidy allocated by public pool: $$S_p=\sum_{i\neq j}k_{ij}v_{ip}v_{jp}=(\sum_{i\neq j}\frac{M}{M+(\sum v_{il}v_{jl})^{\alpha}}(v_{ip}v_{jp})^{\alpha})^{\frac{1}{\alpha}}$$ $\alpha=2$ is defined in [strange kind QF](https://ethresear.ch/t/a-strange-kind-of-pairwise-bounded-quadratic-funding/6808). In our application, we will choose $\alpha=1$ which is defined in the normal [pairwise bound QF](https://ethresear.ch/t/pairwise-coordination-subsidies-a-new-quadratic-funding-design/5553). i.e. $$S_p=\sum_{i\neq j}\frac{M}{M+\sum_{l=1}^m v_{il}v_{jl}}(v_{ip}v_{jp})$$ One might argue what if the contributor chooses different identities in different project? The basic assumption to the quadratic funding (also quadratic voting) is that we need depend on the identity system (e.g. KYC) to identify user's identity. ## Pseudocode ```javascript= // input: V = [u1,u2,...,un]. ui = [vi1,vi2,...,vim] // ui is the votes for contributor i // vij is coordinator i's vote on option j. // Step 1: calculate kij coefficients kij = [] for (let i=0;i<n; i++){ for (let j=i+1;j<n;j++){ let sum = 0; for (let l=0;l<m;l++){ sum += V[i][l]*V[j][l]; } kij.push(M/(M+math.power(sum,alpha))); } } // Step 2: calculate subsidy S = [] for (let l=0;l<m;l++){ let idx = 0; let sum = 0; for (let i=0;i<n;i++){ for (let j=i+1;j<n;j++){ sum += 2*kij[idx]*V[i][l]*V[j][l]; // by symmetry of kij } } idx += 1; S.push(sum); } ``` In Step $1$, number of operations is $O(n^2*m)$, storage is $O(n^2)$. In Step $2$, number of operations is $O(n^2*m)$, storage is $O(m)$. Thus, the total number of operations is $O(n^2*m)$, storage is $O(n^2+m)$. ## Represent float number Notice that $0\leq k_{ij}\leq 1$. The first thing we need to do is to represent float number. In circom, everything is in finite field $\mathbb{F_q}$, where $$q= 21888242871839275222246405745257275088548364400416034343698204186575808495617$$ The field element can be represented by $253$ bits. One solution is to represent last $N$ bits as decimal part and the first $253-N$ bits as integer part. Here are the basic rules: 1. $a \leftrightarrow a\cdot 10^N$: $1500 \leftrightarrow 1.5$ 1. division $a/b \rightarrow a\cdot 2^N/b$: $1/2 \rightarrow 1\cdot 10^3/2=500 \,(\leftrightarrow 0.5)$ 1. multiplication $ab \rightarrow ab\cdot 10^{-N}$: $(0.2\cdot 5\leftrightarrow)\, 200\cdot 5000 \rightarrow 200\cdot 5000\cdot 10^{-3}=1000 \,(\leftrightarrow 1)$ 1. addition and substraction $a+b, a-b$ same as before Here is the sage code sample: ```python= p = 21888242871839275222246405745257275088548364400416034343698204186575808495617 F = GF(p) class FF: N = 4 # how many bits used for float part; N not too large to avoid overflow def __init__(self, x, adjust = False): # assume x is in F if adjust: self.v = x*10**FF.N else: self.v = x def mul(self, y): m = mod(self.v * y.v, 10**FF.N) res = (self.v * y.v - F(m))/10**FF.N #res = (self.v * y.v) >> FF.N return FF(res) def add(self, y): res = self.v + y.v return FF(res) def div(self, y): m = mod(self.v * 10**FF.N,y.v) res = ((self.v * 10**FF.N) - F(m))/y.v return FF(res) def sub(self, y): res = self.v - y.v return FF(res) def __str__(self): return self.v.__str__() def real(self): # print the real number representation pass ``` Test cases: ``` a=FF(F(1),true) b=FF(F(2),true) c=FF(F(3),true) d=FF(F(4),true) e=FF(F(6),true) x=a.div(b) y=a.div(c) z=a.div(d) w=a.div(e) print(x) #1/2 => 5000 print(y) #1/3 => 3333 print(z) #1/4 => 2500 print(w) #/1/6 => 1666 ``` This is the integer division instead of finite field division. Thus, we need write a circuit that can calculate integer division with float representation. ```javascript= pragma circom 2.0.0; include "./node_modules/circomlib/circuits/bitify.circom"; include "./node_modules/circomlib/circuits/comparators.circom"; include "./node_modules/circomlib/circuits/mux1.circom"; template IntegerDivision(n) { // require max(a, b) < 2**n signal input a; signal input b; signal output c; assert (n < 253); assert (a < 2**n); assert (b < 2**n); var r = a; var d = b * 2**n; component b2n = Bits2Num(n); component lt[n]; component mux[n]; component mux1[n]; for (var i = n - 1; i >= 0; i--) { lt[i] = LessThan(2*n); mux[i] = Mux1(); mux1[i] = Mux1(); } for (var i = n-1; i >= 0; i--) { lt[i].in[0] <== 2 * r; lt[i].in[1] <== d; mux[i].s <== lt[i].out; mux[i].c[0] <== 1; mux[i].c[1] <== 0; mux1[i].s <== lt[i].out; mux1[i].c[0] <== 2 * r - d; mux1[i].c[1] <== 2 * r; b2n.in[i] <== mux[i].out; r = mux1[i].out; } c <== b2n.out; } ``` ## Coefficient and Subsidy Calculation From above section, we can see that due to limitation of circom 2.0 compiler restriction. It's difficult to do the coefficient calculation by batch. And if we calculate all together, the circuit will be too big to compile/generate proof. Instead of saving the calculation of coefficients as upper triangle $\{k_{ij}\}_{0\leq i<j<N}$, we can calculate the coefficients redundantly, i.e. $\{k_{ij}\}_{0\leq i<N, 0\leq i<N}$. With this approach, we can divide the matrix evenly, where each batch is of size `B*B, B < N`. In this case, there are total `ceil(N/B)*ceil(N/B)` batches. We can index each batch by its starting index `(rowStartIndex, colStartIndex)`. For each of the batch, we have two inputs ``` rowVotes=(votes[rowStartIndex],...votes[rowStartIndex+B-1]) colVotes=(votes[colStartIndex],...,votes[colStartIndex+B-1]) ``` Choose the batchSize `B=treeArity**subTreeDepth`, then it is easy to prove the votes are part of vote trees. And since the order of the batch index is regular, we don't have to do order check anymore. For each batch, we add its contribution to previous the subsidy result. After we process all the batches, the last subsidy result is the final one. For example, suppose we have $4$ users $\{u_1,u_2,u_3,u_4\}$ in $2$ batches (i.e. $B_1=\{u_1,u_2\}$, $B_2=\{u_3,u_4\}$), we need calculate $6$ correlation coefficients: $$\{u_1,u_2,u_3,u_4\}\rightarrow \{c_{12},c_{13},c_{14},c_{23},c_{24},c_{34}\}$$ We do it by $4$ pair of batches: $$\{(B_1,B_1), (B_1,B_2), (B_2,B_1),(B_2,B_2)\}$$ ## Avoid overflow in subsidy calculation When we use finite field $\mathbb{F}_N$ to emulate real number operations, we need avoid overflow. Especially, we need to make sure that the denominator of $k_{ij}$ and the final sum are not greater than modules number $N$. For simplicity, suppose we have an upper bound for any given voter's total vote: $\sum_{l=1}^m v_{il}\leq V$. The sum in denomiator has maximum value when two voters vote for the same project: $$\sum_{l=1}^mv_{il}v_{jl}\leq V^2$$ However, the last sum is not easy to estimate the bound, as the larger correlation will has smallar coefficient. A rough estimate would be: $$\sum_{i\neq j}k_{ij}v_{ip}v_{jp}\leq \frac{M}{M+V^2/m}V^2\cdot n(n-1)\leq n^2\cdot m \cdot M$$ * $V^2 + M < N$ * $n^2\cdot m\cdot M < N$ We can pick $2^{252}<N$ as a safe bound (because the circomlib LessThan require $n<2^{252}$). In practice, we have $n\leq 5^{10}, m\leq 5^4$. Thus, for example, if $M<2^{196}, V<2^{125}$, above two conditions are met. ## reference [clr paper](https://blogchains.org/wp-content/uploads/sites/4/2019/04/SSRN-id3243656.pdf) [pairwise bound QF](https://ethresear.ch/t/pairwise-coordination-subsidies-a-new-quadratic-funding-design/5553) [strange kind QF](https://ethresear.ch/t/a-strange-kind-of-pairwise-bounded-quadratic-funding/6808) ###### tags: `public` `maci`
Last changed by  
 
Chao
759

Read more

Barrett Reduction

Barrett reduction allows us to quickly calculate the quotient $q$ and reminder $r$ of $a \pmod n$, i.e. $a = q\cdot n + r, 0\leq r<n$. GLV One of the use case is in GLV decomposition. For simplicity, we consider all the integers below are less than $2^{256}$. We want to decompose $k=k_1+k_2\cdot\lambda$ with both $k_1, k_2$ are small. Here is the correspondence $$k\rightarrow a,k_1\rightarrow r, k_2\rightarrow q, \lambda\rightarrow n$$ When $\lambda$ is $128$ bit, we can use Barrett reduction to derive $k_1, k_2$ with $k_1<2^{128}, k_2<2^{128}$. In the glv paper, it considers more general case where $\lambda$ might not be $128$ bit and hence use lattice based algorithm to derive small $k_1, k_2$ (which might not less than $2^{128}$)

3/24/2023
Lookup argument for folding

Example Assume in lookup arguments, we have two columns $(A,S)$, and try to lookup $A_i\in S$. Firstly, we cannot directly fold two such instances, e.g. with random factor $r=1$: $$A_1=[1,1,2,3], S_1=[1,2,3,4,5]\ A_2=[1,1,1,2], S_2=[1,2,3,4,5]\ A_1+A_2=[2,2,3,5], S_1+S_2=[2,4,6,8,10]$$ Obviously $(A_1+A_2, S_1+S_2)$ will not work. And since the lookup is arbitrary, we probably will not have any explicit formula to make the folding of $(A,S)$ work. Attempt 1 Assume we want to calcualte a function $F: X\rightarrow Y$. Instead of writing circuit for $F$, we do lookup argument that $(x,F(x))\in S$. Here $S={(x,F(x))|x\in X}$.

3/20/2023
Montgomery modular multiplication

Original version Suppose $a,b\in \mathbb{Z}_N$, modular multiplication $[ab]$ requires first multiply them in the range $[0,N^2-2N+1]$, and then use Euclidean division theorem to get $ab=qN+r,q=\lfloor ab/N\rfloor$, such that $[ab]=r$. The division is quite expensive. Montgomery form is to choose a different divisor $R>N$ with $\gcd{(R, N)}=1$. For example, by choose $R=2^n$, the division is just shift by $n$ bits. Thus, we just want to make sure the numerator is divisible by $R$. Montgomery form of $a$ is defined as $\bar{a}=[aR]$, i.e. residual class of $aR$. We have: $$\gcd{(R,N)}=1\implies \exists R^{-1}:RR^{-1}\equiv 1\implies\exists N'<R:RR^{-1}=N'N+1$$ i.e. $N'$ is negative mod inverse of $N$ w.r.t $R$. And we have multiplication by $R$ is ring isomorphism. And: $$T=[aR][bR]\equiv abR\cdot R\equiv [abR]\cdot R$$ Notice $T<N\cdot N< R*N$. For any $0\leq T < RN$, define reduction form of $T$ as: $$t=redc(T):=TR^{-1}\pmod N$$ i.e. $\overline{ab}=redc(\bar{a}\bar{b})$. We use the following algorithm to do the reduction:

2/10/2023
Plonk By Hand

Reference plonk by hand (part1) plonk by hand (part2) plonk by hand (part3) Codes All the codes below are python with SageMath.

2/2/2023
Read more from Chao
Published on HackMD