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:

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^n{v}_{il}{)}^2$$
The subsidy allocated by the public funding pool (assuming we have enough public fund) is given by

$$S_l=(\sum _i^n{v}_{il}{)}^2-\sum _i^n{v}_{il}^2=\sum _{i\ne 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, 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\ne 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}^m{v}_{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\ne j}{k}_{ij}{v}_{ip}{v}_{jp}=(\sum _{i\ne 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. In our application, we will choose

$\alpha =1$ which is defined in the normal pairwise bound QF. i.e.

$$S_p=\sum _{i\ne 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

// 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\ast m)$, storage is

$O(n^2)$. In Step

$2$, number of operations is

$O(n^2\ast m)$, storage is

$O(m)$. Thus, the total number of operations is

$O(n^2\ast m)$, storage is

$O(n^2+m)$.

Represent float number

Notice that

$0\le k_{ij}\le 1$. The first thing we need to do is to represent float number. In circom, everything is in finite field

${\mathbb{F}}_{\mathbb{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$
2. division
   $a/b\to a\cdot 2^N/b$:
   $1/2\to 1\cdot {10}^3/2=500(\leftrightarrow 0.5)$
3. multiplication
   $ab\to ab\cdot {10}^{-N}$:
   $(0.2\cdot 5\leftrightarrow )200\cdot 5000\to 200\cdot 5000\cdot {10}^{-3}=1000(\leftrightarrow 1)$
4. addition and substraction
   $a+b,a-b$ same as before

Here is the sage code sample:

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.

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\le i<j<N}$, we can calculate the coefficients redundantly, i.e.

$\{k_{ij}{\}}_{0\le i<N,0\le 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\}\to \{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}\le V$. The sum in denomiator has maximum value when two voters vote for the same project:

$$\sum _{l=1}^m{v}_{il}{v}_{jl}\le 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\ne j}{k}_{ij}{v}_{ip}{v}_{jp}\le \frac{M}{M+V^2/m}{V}^2\cdot n(n-1)\le 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\le 5^{10},m\le 5^4$. Thus, for example, if

$M<2^{196},V<2^{125}$, above two conditions are met.

reference

clr paper
pairwise bound QF
strange kind QF

tags: public maci