# MACI v1.0: top-up voice credits ## Introduction In previous design, when an user signup, she will get an initial voice credit balance. This info is stored in corresponding stateLeaf. For multiple polls, an user can spend credits upto this initial balance. e.g. If an user has initial 100 credits. Then she can spend a total of 100 credits for each poll. If she wants to spend more than initial balance, she has to signup again. The purpose of top-up feature is to allow users to add more credits without signup again. ## Design One approach is to modify the voiceCreditBalance on the stateLeaf each time when user deposit new credits. This is the current approach we are going to take. ### Proposal Notice that an user cannot just arbitrarily send a topup command to add credits. Instead, we add an ERC20 contract to store voting credits. Then the user can use the topup function in poll.sol to deposit tokens into the contract address. In the current design, we don't allow users to withdraw their tokens. The reason is that withdraw feature can allow malicious one to bribe others offline to transfer their keys. Without withdraw function, the malicious cannot distinguish whether key transferred is valid or not. Since now the poll.sol contract address will hold all the funds deposit from users for the current pollID. At the end of poll, the coordinator (or anyone) can transfer funds in poll.sol into hardcoded address which is used for public goods. When an user deposit tokens by calling topup, she will also need to specify the stateTree index. The topup function will insert a topup message into the message queue for her. When the voting period is end, any call of topup function will be rejected. Both voting and topup messages have the same ending time, which ensures we have a well-defined ending state for each poll. Notice in this approach, the initialCredit is still shared across multiple polls, and the actual credit an user can spend in a given poll is the following: `totalCredit=initialCredit+topupCredit` where the topupCredit is the voice credit deposit by the user during the voting period of the given pollID. ### domainobjs We have two types of messages: voting and topup. In previous design, the voting message is encrypted and stored in smart contracts. For topup message, which is created by topup function, we don't need to encrypt. However, when we process messages, we need distinguish these two type of messages. The idea is to add a new field to identify type of messages. ``` struct MessageLeaf { uint256 type; // 0x00 voting, 0x01 topup uint256[N] message; } ``` The message field will be interpret differently for different types. ### core core/ts/MaciState.ts: Now there are two types of messages: voting and topup. Add logic to process topup type message. ### circuits Add circuit logic to process topup message, update balance in stateTree leaf for topup message. Add necessary conditions check, for example: `totalCredit=initialCredit+topupCredit >= spentCredit` ### contracts contracts/contracts/ERC20.sol: standard ERC20 tokens contracts/contracts/Poll.sol: `function topup(amount uint256, stateIndex uint256)`. This function will do the following: transfer ERC20 tokens from an user into this contract address (poll.sol), insert "topup" type message into messageAq. We don't allow people to withdraw the funds from the Poll.sol, because the attacker can ask people to withdraw funds to make sure their keys are registered and valid before bribing them. This will make the bribe attack possible. contracts/ts/genMaciState.ts: Add action of topup. `action['type'] === "topup"`. This can be done by filtering the event logs from poll.sol, and construct the state from there. ### cli Add topup command which will send transaction to poll.sol. ### Remarks With above design, the order of vote type and topup type message matters. MACI process the message queue in reverse order. Suppose the initial credit balance for any user is $100$. Consider the following two scenarios in message queue: ``` # case 1 [topup(balance=350), vote(weight=20,nonce=2), vote(weight=9,nonce=1)] # case 2 [vote(weight=20,nonce=2), topup(balance=350), vote(weight=9,nonce=1)] ``` The first case, the topup message is processed at last, so the `vote(weight=20,nonce=2)` will fail because $20*20 > 100$. `vote(weight=9,nonce=1)` is the final result. In the second case, the topup message is processed before the second vote, so `vote(weight=20,nonce=2)` will invalidate the first vote and become the final result. ## reference https://hackmd.io/@ef-zkp/rk6uaQBrI ###### tags: `public` `maci`
Last changed by  
 
Chao
370

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