Skip to main content

Jagrut Kosti

Token vesting is one of the less talked about topics in Web3. And probably it's for the best! Let's explore, what it is, why it can be useful and if it is actually solving any problem.

What's Vesting?

Token vesting refers to a certain percentage of tokens that you know for sure will be available for use and trade. It's similar to ESOPs (Employee Stock Option Plans) with a major difference that ESOPs, even when vested, cannot be freely traded right away.

There are a lot of nuances on the structure of token allocation and what vesting exactly means. This changes from project to project. For example, a project can make only 20% of the total supply of tokens available for claiming/air drop. The rest can either be allocated later in further rounds of allocation, or they are part of the token emissions via staking rewards, etc.

Why Vesting?

Most Web3 projects deploy vesting strategies to prevent mass dumping of their token after the initial allocation or air drop, and therefore saving the token price from plummeting. The rationale is that since there are more tokens to be vested (unlocked), no one can dump all of their tokens and exit. Which leaves room for speculation whether the future vested tokens will be dumped or not, preventing the token price from completely nose diving.

Broadly speaking, there are generally 2 different types of vesting strategies:

  1. Only a certain percentage of total supply is in circulation and distributed via air drops. The unvested (locked) tokens are then brought into circulation via protocol metrics like validator rewards, emissions, etc. The unvested tokens are NOT air dropped again to the same set or a large subset.
  2. Similar to 1, but unvested tokens are brought into circulation via more air drops and the new vested tokens are distributed to the same set or large subset.

Next section is only applicable to 2nd type.

Is it effective?

I'll try to explain why vesting is actually worse than fully unlocked/vested tokens at the time of launch. Assumptions:

  • This analysis is from a token holder's / air drop recipient's perspective only. Does not include token buying or investors.
  • The token holder knows about all their vested tokens and their schedule.
  • The vesting schedule is fixed for all token holders i.e. the tokens are vested at the same time for all token holders.

From game theoretic perspective, any air drop is a positive-sum game, i.e. there is no monetary loss even if the price of the tokens drops to zero. The utility is to derive the maximum profits. Consider a scenario where a new token launch has a vesting schedule of 20% at the time of launch and every quarter of the year, another 20%. So by the end of the year, all tokens would be vested.

Every user (U) is playing a game with the market (M). Each of them can either Sell (S) or Hold (H). Based on relative utility and the assumption that there will be more tokens available in the future, the following utility matrix resembles the outcome.

M \ USH
S(1,1)(1, -3)
H(0,2)(0,0)

The effect of a user's action on the market is lower than a market's action on the user. Therefore, if both U and M sell at the time of air drop, they both derive the utility of (1,1). But if the U holds and M sells, there will be a much larger impact of that on user, hence their utility is (1, -3). If the U sells and M holds, there is a slightly higher utility for the user since they are selling at current holding price and hence we have (0,2). This can also be (0,1) and it would not make much difference. Important point to note here is that the action of holding gives a utility of 0 to both. People familiar with basics of Game Theory can quickly tell that there exists a pure-strategy Nash Equilibrium i.e. irrespective of what other player's actions are, your best strategy is to play the action with guaranteed maximum payoff. In our case, for both U and M, their best strategy is to Sell and get a payoff of (1,1).

This matrix is only valid when User knows that there are more tokens that will be available in the future. This is because all assets can theoretically gain value over time and it would be ideal to hold some portion with a certain probability of the protocol succeeding. Note that the last vesting schedule is identical to protocols with no vesting schedule as it then leaves it up to the user and their reasoning of the protocol's success. Which implies that all the vesting prior to the final one, simply gives more chance for users to dump their token.

From the protocol's perspective, this is disastrous. If the token price is somehow considered an indicator of the market's belief in protocol's success, then irrespective of how good the protocol is technically, it will get a bad rep. Furthermore, a non-vesting schedule air drop, entirely leaves it up to the market on how they perceive the protocol and let the market decide the optimal price point.

The reality

If we look at most protocol's distribution of the tokens, majority are distributed to investors, core team and early adopters. For them, vesting or no-vesting should not make a difference and they would ideally Hold till the protocol gains some traction.

On the other hand, vesting still gives them disproportional power to start dumping at the most opportunistic moment, especially investors, whose major utility is realising profits over time. Don't get me wrong, I'm not trying to throw negative light on investors, I'm simply talking about their utility from a rational perspective.

Irrespective of how the newly vested tokens are distributed, new circulating supply decreases the FDV (Fully Diluted Valuations)and increases selling pressure. See a relevant report on Low Float, High FDV.

Any solution?

Yes! A trivial sounding but not-so-trivial to implement on chains, is the idea of randomized vesting schedule. For each user, when the tokens will be vested is randomized. This creates a situation where a market cannot act in one way at one time because there is a fluctuating volume of tokens being vested every now and then.

For trading, randomized vesting schedules work to avoid nose dive of the token price. For governance, certain things need to be taken care of. Since all tokens are not vested at same time, a voting process should take into account all tokens, including the un-vested, to determine voting power (If the protocol uses one-token-one-vote mechanism).

So how can randomized vesting schedules be implemented? Through DVRFs! (Distributed Verifiable Random Function) The randomness from VRFs can be used to securely introduce random vesting schedule for each user.

ChainSafe R&D is currently working on implementing a better version of distributed verifiable random functions. More on that coming soon!

Timofey Yaluhin

Recently, there has been a lot of excitement and interest around circle STARKs. This didn't pass me by either, and my interest was piqued. Not only by the loud "breakthrough" announcements and the prospects of unlocking verifiable computation on Bitcoin, but also by the subtle elegance of applied algebraic geometry to address limitations and simplify previous solutions.

At this point, we have several excellent introductory and explainer articles by zkSecurity, Vitalik, and LambdaClass. I have tried my best not to repeat their words and instead focus on the unexplored aspects and elements that I personally found very interesting. I wrote this as I was learning, so I cannot rule out inaccuracies. If you spot any mistakes, please comment away in this mirror on HackMD.

Introduction

Circle STARKs enable the prover to work over the finite field modulo Mersenne 31 prime (M31), which has very efficient arithmetic. Namely, it is 1.3 times faster than BabyBear, the previous most efficient field used in SP1, Valida, and RISC Zero. For more insight on why working over M31 is so desirable, refer to this article.

However, simply plugging M31 into existing univariate STARKs won't work. The reason is that Mersenne primes are not FFT/FRI friendly. Let's unpack why.

The efficiency of the FFT "divide-and-conquer" algorithm relies on the ability to recursively divide the problem size by powers of 2. When working over a finite field, this requirement necessitates an evaluation domain to have the "structure" of a multiplicative group whose order's factorization contains a large power of two. We refer to this as high 2-adicity. The reason we want this is that at each step of the FFT, we reduce the size of the domain by a factor of two by squaring each number in it.

For example, consider the domain [1,85,148,111,336,252,189,226][1, 85, 148, 111, 336, 252, 189, 226] in the finite field of integers modulo 337337. This domain forms a multiplicative group with 8=238 = 2^3 elements. The elements of this group are powers of ω=85\omega = 85, which is a generator of the group. If you square every number in the domain, you reduce the size of the domain by a factor of two: [1,148,111,336][1, 148, 111, 336]. If you take the same domain but with, say, 6 elements, you don't get this property anymore.

Another relevant way of framing the 2-adicity requirement is to search for a group whose order is a product of small primes. We call such numbers smooth numbers. Since the multiplicative group of a field includes every element except 00, the order of the group is exactly one less than the number of elements in the field. Fields Fp\mathbb{F}_p that satisfy this condition are referred to as p1p-1 smooth.

An exemplary prime is the BabyBear prime p=231227+1p = 2^{31} - 2^{27} + 1. The largest multiplicative group in the BabyBear field has p1=22735p-1 = 2^{27} \cdot 3 \cdot 5 elements. You can clearly see that it is both smooth and highly 2-adic. It's perfect.

What about the Mersenne-31 prime p=2311p = 2^{31} - 1? Unfortunately, 23122^{31} - 2 can be divided by 2 only once. Thus, the conventional Cooley-Tukey FFT algorithm would be very inefficient for this field group. The authors solve this by devising a group from a unit circle.

Circle as a group

A circle group is generated from a point (x,y)(x, y) such that x2+y2=1x^2 + y^2 = 1 (i.e., it lies on a unit circle) by applying a different multiplicative law:

(x0,y0)(x1,y1):=(x0x1y0y1,x0y1+y0x1)(x_0, y_0) \cdot (x_1, y_1) := (x_0 \cdot x_1 - y_0 \cdot y_1, x_0 \cdot y_1 + y_0 \cdot x_1)

Instead of generating subgroup elements as simply powers of a generator gg, we move from a point (xi,yi)(x_i, y_i) on the circle to the point:

(xi+1,yi+1)=(gxxigyyi,gxyi+gyxi)(x_{i+1}, y_{i+1}) = (g_x \cdot x_i - g_y \cdot y_i, g_x \cdot y_i + g_y \cdot x_i)

It turns out that the number of points lying on the circle, defined over the Mersenne prime 23112^{31}-1, is quite large (2312^{31}). One can generate all 2312^{31} group elements by starting with (x0,y0)=(1,0)(x_0, y_0) = (1, 0) and applying the generator (gx,gy)=(2,1268011823)(g_x, g_y) = (2, 1268011823) using the law above.

For the circle FFT/FRI, we need two more group operations: the group squaring map π\pi and the inversion map JJ.

Squaring is the quadratic map defined as

π(x,y):=(x,y)(x,y)=(x2y2,2xy)=(2x21,2xy)\pi(x, y) := (x, y) \cdot (x, y) = (x^2 - y^2, 2 \cdot x \cdot y) = (2 \cdot x^2 - 1, 2 \cdot x \cdot y)

This transformation reduces the set size by half.

Inverse is given by the degree-one map

J(x,y):=(x,y)J(x, y) := (x, -y)

This operation maps each point (x,y)(x, y) to its reflection (x,y)(x, -y).

Map JJ is an involution, i.e., J(J(P))=PJ(J(P)) = P. Maps JJ and π\pi commute, i.e., π(J(P))=J(π(P))\pi(J(P)) = J(\pi(P)) for every PC(Fp)P \in C(\mathbb{F}_p).

FFT over the circle domain

Same as in the classical STARK, the circle FFT is used to evaluate some polynomial on a special domain. In regular FFT, the domain consists of nn-th roots of unity, i.e. {1,ω,ω2,,ωn1}\{1, \omega, \omega^2, \ldots, \omega^{n-1}\}. In circle FFT, the domain is a set of points on a circle curve, generated as follows.

First, we take a circle group generator gg and square it logn1\log n - 1 times to create a subgroup Gn1G_{n-1}. Then, we create two twin cosets, which are formed by taking an element QQ that is not in GnG_n and creating two disjoint sets: QGn1Q \cdot G_{n-1} and Q1Gn1Q^{-1} \cdot G_{n-1}. The union of these sets forms the circle FFT domain containing 2n2^n elements. A self-descriptive implementation can be found here in Plonky3.

An interactive plotter to demonstrate the distribution of domain points, which uses a simple TS implementation of the circle group over Mersenne-17 field. Even though it's modulo prime p, you can still see a regular circular patterns with symmetry about the line p/2. This phenomena is also exists in elliptic curves (genus 1), but is much more apparent on circle curves (genus 0) and complex roots of unity.

The FFT works by recursively splitting the larger problem into two smaller ones. In the context of polynomial evaluation, this means decomposing the polynomial into "even" and "odd" parts. In regular FFT, these sub-polynomials are simply formed from even and odd coefficients of the original polynomial. In circle FFT, this is a bit more involved, as we'll see, but the underlying mechanics is the same — the original polynomial ff is a linear combination f(x)=feven(x)+xfodd(x)f(x) = f_{\operatorname{even}}(x) + x\cdot f_{\operatorname{odd}}(x). At each split, we also reduce the domain by a factor of two.

In the first step, we "halve" the domain by simply taking an xx projection of each point. This is justified by the use of the inverse map when performing a decomposition f(x,y)=f0(x)+yf1(x)f(x, y)=f_0(x)+y \cdot f_1(x) such that:

f0[indexD1(x)]=f[indexD0(x,y)]+f[indexD0(J(x,y))]2f1[indexD1(x)]=f[indexD0(x,y)]f[indexD0(J(x,y))]2y\begin{aligned} & \vec{f_0}[\operatorname{index}_{D_1}(x)]=\frac{\vec{f}[\operatorname{index}_{D_0}(x, y)]+\vec{f}[\operatorname{index}_{D_0}(J(x,y))]}{2} \\ & \vec{f_1}[\operatorname{index}_{D_1}(x)]=\frac{\vec{f}[\operatorname{index}_{D_0}(x, y)]-\vec{f}[\operatorname{index}_{D_0}(J(x,y))]}{2 \cdot y} \end{aligned}

I have modified the notation to demonstrate how in practice we treat polynomials f,f0,f1f, f_0, f_1 as vectors of their coefficients. Compare the original notation here with Vitalik's implementation here.

You can think of the inverse map J(x,y)=(x,y)J(x, y) = (x, -y) as a way to identify vertically mirrored pairs of points so that they can be treated as a single entity. This allows us to proceed with only the xx coordinate.

In later steps, we continue to halve the domain using the univariate squaring map π(x)=2x21\pi(x)=2 \cdot x^2-1. This is analogous to squaring the kk-th root of unity such that ω2k=ωk\omega^{2k} = \omega_k. The even-odd decomposition (in the original notation) fj(x)=fj+1(π(x))+xfj+1(π(x))f_j(x) = f_{j+1}(\pi(x))+x \cdot f_{j+1}(\pi(x)) — now looks like this:

f0(π(x))=f(x)+f(x)2f1(π(x))=f(x)f(x)2x\begin{aligned} & f_0(\pi(x))=\frac{f(x)+f(-x)}{2} \\ & f_1(\pi(x))=\frac{f(x)-f(-x)}{2 \cdot x} \end{aligned}

Although speeding up the FFT is not the main point of the paper, as author points out here, it serves as an effective demonstration of the core principles of working over the circle group. When studying the paper, I made the mistake of skipping it and rushing to circle FRI only to hit a wall of confusion. So, I encourage you to take some time to appreciate this mechanic. If you want to play around with it, I made this Python notebook (trigger warning: shitty code).

Regular FRI

Structure of the FRI algorithm is a lot like FFT. But instead of recursively dividing the polynomial into many smaller ones, in FRI, the prover iteratively reduces the degree of a polynomial until it gets to some small constant-size one. It does so via random linear combination, i.e., by combining "even" and "odd" sub-polynomials against a random weight.

In STARK, we use FRI for something called "low-degree testing"—by knowing the final degree and the number of reduction steps, the verifier can work backwards and check that the degree bound of the original polynomial is as claimed. More formally, FRI enables an untrusted prover to convince a verifier that a committed vector is close to a Reed-Solomon codeword of degree dd over the domain DD.

Here, being "close" is defined by the relative Hamming distance δ\delta such that the number of points where the committed vector and the codeword disagree is at most δD\delta \cdot |D|. The distance δ\delta is such that δ(0,1ρ)\delta \in (0,1-\sqrt{\rho}) where 0<ρ<10 < \rho < 1 is the rate of the Reed-Solomon code. In turn, the rate ρ\rho is defined by the blow-up factor 2B,B12^B, B \geq 1 so that ρ=2B\rho=2^{-B}. Finally, the domain size is D=2n+B|D| = 2^{n+B} where 2n2^n is the size of the original vector.

To make this definition more senseful, let's assign standard values: A commonly used blow-up factor is 2B=42^B=4, so the rate is ρ=0.25\rho = 0.25. The worst possible distance is δ=0.5\delta=0.5, so for a vector with 1024 elements, the codeword over a 2B+n=40962^{B+n}=4096 sized domain can disagree on at most half of the points. In practice, δ\delta is much smaller to give better soundness guarantees.

Another interesting property is the decoding regime. In the unique decoding regime, the goal is to identify a single low-degree polynomial that is close to the committed vector. The unique decoding radius is typically defined as: θ[0,1ρ2]\theta \in [0, \frac{1-\rho}{2}].

STARKs are shown to be sound outside this regime as the goal is to demonstrate the existence of such polynomials, even if multiple polynomials fit the given points. We refer to this simplified requirement as the list decoding regime. The list decoding radius is typically defined as: θ[1ρ2,1ρ]\theta \in [\frac{1-\rho}{2}, 1-\sqrt{\rho}]. HAB23

Circle FRI

The general mechanics behind low-degree testing over the circle domain remain unchanged from the regular FRI. As a reminder, see this blog post for an in-depth theoretical discussion or this one if you only care about the implementation.

Circle FRI operates on codewords in the circle code C\mathcal{C}, which is a generalization of the Reed-Solomon code defined over elements of the circle group and special polynomials in Riemann-Roch space. Oversimplified, they are bivariate polynomials modulo the unit circle equation (x2+y2=1)(x^2 + y^2 = 1), so whenever a polynomial has y2y^2, it's replaced by 1x21 - x^2.

For a given proximity parameter θ(0,1ρ)\theta \in (0,1-\sqrt{\rho}), the interactive oracle proof of a function f:XFDf: X \rightarrow \mathbb{F}^D (mapping the committed vector) being θ\theta-close to the circle codeword C\mathcal{C} consists of rr rounds of a commit phase and a subsequent query phase, which are as follows.

Commit phase

  1. P\mathbf{P} decomposes ff into f=g+λvnf=g+\lambda \cdot v_n and sends λ\lambda to V\mathbf{V}
  2. V\mathbf{V} picks random weight λj\lambda_j for layer jj
  3. For each j=1,,rj=1, \ldots, r, P\mathbf{P} decomposes gj1g_{j-1} into "even" and "odd" parts; sends a commitment [gj][g_j] to V\mathbf{V}
  4. In the last round, P\mathbf{P} sends gr+1g_{r+1} in plain.

1. P\mathbf{P} decomposes ff into f=g+λvnf=g+\lambda \cdot v_n and sends λ\lambda to V\mathbf{V}

We start with the extended domain coset Dn+BD_{n+B}. First, we want to find the component of ff that is aligned with vnv_n. This can be done using vector projection: given two functions (or vectors) ff and vnv_n, the projection of ff onto vnv_n is given by:

projvn(f)=f,vnDvn,vnDvn\operatorname{proj}_{v_n}(f)=\frac{\langle f, v_n\rangle_D}{\langle v_n, v_n\rangle_ D} \cdot v_n

Note: angle brackets denote the inner product vn,fD=xDvn(x)f(x)\langle v_n, f\rangle_D=\sum_{x \in D} v_n(x) \cdot f(x).

Taking λ\lambda as the magnitude of this projection will ensure that λvn\lambda \cdot v_n is the part of ff that lies along vnv_n

λ=f,vnDvn,vnD\lambda=\frac{\langle f, v_n\rangle_D}{\langle v_n, v_n\rangle_D}

The vanishing polynomial vnv_n has an alternating behavior over the domain DD, e.g., if DD has size N=2nN=2^n, then vnv_n alternates as (1,1,1,1,)(1,-1,1,-1, \ldots). This significantly simplifies the inner product calculations as vn(x){1,1}v_n(x) \in \{1,-1\}, each term vn(x)2=1v_n(x)^2=1 so

vn,vnD=xD1=D=N\langle v_n, v_n\rangle_D=\sum_{x \in D} 1=|D|=N

Knowing λ\lambda, we can now find gg, which represents the component of ff that is orthogonal to vnv_n

g=fλvng=f-\lambda \cdot v_n

This ensures that gg lies entirely in the FFT space LN(F)\mathcal{L}_N^{\prime}(F), orthogonal to vnv_n. This is because the inner product g,vnD=0\langle g, v_n\rangle_D=0, making gg and vnv_n orthogonal by construction.

2. V\mathbf{V} picks random weight λj\lambda_j for layer jj

In practice, though, P\mathbf{P} can compute λj\lambda_j as a random linear accumulator starting with λ\lambda and using a single random weight αE\alpha \in \mathbb{E} picked by V\mathbf{V}

λj=λj1α+λ\lambda_j = \lambda_{j-1} \cdot \alpha + \lambda

See this done in Stwo.

3. For each j=1,,rj=1, \ldots, r, P\mathbf{P} decomposes gj1g_{j-1} into "even" and "odd" parts

The "even-odd" decomposition follows the same progression as in FFT. In the first round, we work with 2D points (x,y)(x, y) and use the full squaring π(x,y)\pi(x, y) and inverse J(x,y)J(x, y) maps. The inverse map transformation allows us to identify points (x,y)(x, y) and their reflection (x,y)(x, -y) so we can treat them as a single point xx on the xx-axis in subsequent rounds. The squaring map π\pi transforms the domain Dj1D_{j-1} into DjD_j by effectively halving the space of points:

gj1,0(πj(x))=gj1+gj1(J(x))2,gj1,1(πj(x))=gj1gj1(J(x))2tj,\begin{aligned} g_{j-1,0}(\pi_j(x)) & =\frac{g_{j-1}+g_{j-1}(J(x))}{2}, \\ g_{j-1,1}(\pi_j(x)) & =\frac{g_{j-1}-g_{j-1}(J(x))}{2 \cdot t_j}, \end{aligned}

where π(x)=2x21\pi(x)=2 \cdot x^2-1 and tjt_j is a twiddle factor. Then, fold into a random linear combination against λj\lambda_j:

gj=gj1,0+λjgj1,1g_j=g_{j-1,0}+\lambda_j \cdot g_{j-1,1}

Commitment [gj][g_j] is a simple Merkle root. Under the Fiat-Shamir transformation, P\mathbf{P} also sends openings, i.e., Merkle branches for FRI queries.

Query phase

1. V\mathbf{V} samples s1s \geq 1 queries uniformly from the domain DD

For each query QQ, V\mathbf{V} considers its "trace" as the sequence of points obtained by repeatedly applying the squaring map and the transformations defined by the protocol. The initial query point Q0=QQ_0=Q is transformed through several rounds, resulting in a series of points QjQ_j in different domains DjD_j:

Qj=πj(Qj1)Q_j=\pi_j(Q_{j-1})

2. For each j=1,,rj=1, \ldots, r, V\mathbf{V} asks for the values of the function gjg_j at a query point QjQ_j and its reflection Tj(Qj)T_j(Q_j)

Given the commitment [gj][g_j], as in oracle access, V\mathbf{V} can ask the oracle for the values (openings) at query points. In other words, verify Merkle proofs at the points:

gj(Qj) and gj(Tj(Qj))g_j(Q_j) \text{ and } g_j(T_j(Q_j))

where at j=1j=1, Tj=JT_j=J and for j>1j>1, Tj(x)=xT_j(x)=-x.

3. V\mathbf{V} checks that the returned values match the expected values according to the folding rules

This involves checking that the even and odd decompositions are correct and that the random linear combinations used to form gjg_j from gj1g_{j-1} are consistent.

DEEP quotients

Quotienting is the fundamental polynomial identity check used in STARK and PLONKish systems. Leveraging the polynomial remainder theorem, it allows one to prove the value of a polynomial at a given point. Vitalik's overview of quotienting is well on point, so I will focus on the DEEP-FRI over the circle group.

DEEP (Domain Extension for Eliminating Pretenders) is a method for checking consistency between two polynomials by sampling a random point from a large domain. In layman's terms, it lets FRI be secure with fewer Merkle branches.

In STARK, we use the DEEP method on a relation between the constraint composition polynomial (one that combines all the constraints) and the trace column polynomials, all evaluated on a random point zz. For more context, see this post and the ethSTARK paper.

The first part is DEEP algebraic linking: It allows us to reduce the STARK circuit satisfiability checks (for many columns and many constraints) to a low-degree test (FRI) on single-point quotients. By itself, DEEP-ALI is insecure because the prover can cheat and send inconsistent evaluations on zz. We fix this with another instance of quotienting—DEEP quotienting.

We construct DEEP quotients with a single-point vanishing function vzv_z in the denominator to show that a certain polynomial, say a trace column tt, evaluates to the claim yjy_j at zz, i.e., tt(z)vz\frac{t - t(z)}{v_z}.

In classical STARKs, vzv_z is simply a line function XzX - z. In circle STARKs, in addition to not having line functions, we also run into the problem that single-point (or any odd degree) vanishing polynomials don't exist. To get around this, we move to the complex extension, i.e., decomposing into real and imaginary parts

tt(z)vz=Re(tt(z)vz)+iIm(tt(z)vz)\frac{t-t(z)}{v_z}=\operatorname{Re}\left(\dfrac{t-t(z)}{v_z}\right)+i \cdot \operatorname{Im}\left(\dfrac{t-t(z)}{v_z}\right)

Using with this quirk, we follow the standard procedure constructing a composite DEEP quotient polynomial as a random linear combination. We use different random weights for the real and imaginary parts

Q=i=0L1γiRez(ti)+i=0L1γL+iImz(ti)=Rez(i=0L1γiti)+γLImz(i=0L1γiti)Q=\sum_{i=0}^{L-1} \gamma^i \cdot \operatorname{Re}_z(t_i)+\sum_{i=0}^{L-1} \gamma^{L+i} \cdot \operatorname{Im}_z(t_i)=\operatorname{Re}_z\left(\sum_{i=0}^{L-1} \gamma^i \cdot t_i\right)+\gamma^L \cdot \operatorname{Im}_z\left(\sum_{i=0}^{L-1} \gamma^i \cdot t_i\right)
FYI

In the ethSTARK paper, the prover does batching using LL random weights γ1,,γL\gamma_1, \ldots, \gamma_L provided by the verifier (affine batching). Here, the prover uses powers of a single random weight γ1,,γL\gamma^1, \ldots, \gamma^L (parametric batching).

Computing QQ naïvely will suffer overhead due to the complex extension, essentially doubling the work due to real and imaginary decompositions. The authors solve this by exploiting the linearity in the above equation. The prover now computes

Q=(Re(1vz)+γLIm(1vz))(gˉvˉz)=Re(vz)zLIm(vz)Re(vz)2+Im(vz)2(gˉvˉz)Q=\left(\operatorname{Re}\left(\frac{1}{v_z}\right)+\gamma^L \cdot \operatorname{Im}\left(\frac{1}{v_z}\right)\right) \cdot(\bar{g}-\bar{v}_z)=\frac{\operatorname{Re}(v_z)-z^L \cdot \operatorname{Im}(v_z)}{\operatorname{Re}(v_z)^2+\operatorname{Im}(v_z)^2} \cdot(\bar{g}-\bar{v}_z)

where gˉ=k=0L1γkgk\bar{g}=\sum_{k=0}^{L-1} \gamma^k \cdot g_k and vˉz=k=0L1γkgk(z)\bar{v}_z=\sum_{k=0}^{L-1} \gamma^k \cdot g_k(z).

Interestingly, Stwo and Plonky3 actually use different quotienting approaches: Plonky3 implements the method described in the paper and here, but Stwo chooses instead to use a 2-point vanishing polynomial, as described in Vitalik's note.

Field work

In circle STARK, work is done over the finite field Fp\mathbb{F}_p and its extension E=Fpk\mathbb{E} = \mathbb{F}_{p^k} where kk is the extension degree. For Fp\mathbb{F}_p, we choose M31, but any other p+1p+1 smooth prime will suffice. The extension field E\mathbb{E} used in Stwo and Plonky3 is QM31, a degree-4 extension of M31, aka. the secure field.

In rare cases, it will be useful to work with the complex extension F(i)\mathbb{F}(i), the field that results from F\mathbb{F} by extending it with the imaginary unit ii. Note that ii may trivially be contained in some fields, e.g., if 14mod5-1 \equiv 4 \mod 5 then ii in F5\mathbb{F}_5 is both 4=2\sqrt{4} = 2 and 33 (since 23mod542^3 \mod 5 \equiv 4). For those fields where this isn't the case, such as F3\mathbb{F}_3, we can devise a quadratic extension, F9={a+bia,bF3}\mathbb{F}_9 = \{ a + bi \mid a, b \in \mathbb{F}_3 \}, which extends the original field in the same way complex numbers extend rationals.

FYI

A more common notation is F[X]/(X2+1)\mathbb{F}[X] / \left(X^2+1\right), which means forming a field extension where X2+1=0X^2+1=0. This results in a new field with elements of the form a+bia+b i where a,bFa, b \in \mathbb{F} and ii is a root of X2+1X^2+1, such that i2=1i^2=-1.

  • Trace values are over the base field and trace domain are points over the base field C(F)\mathbb{C}(\mathbb{F}).
  • The evaluation domain consists of points over the base field C(F)\mathbb{C}(\mathbb{F}).
  • All random challenges and weights for linear combinations are drawn from the secure field.
  • When computing DEEP quotients, we move from the base field to secure fields, while briefly using complex extensions for vanishing denominators.
  • Circle FRI works mainly on the secure field. However, query values are base field elements since we Merkle commit to values in the base field.

The results

That's cool and all, but let's see how all this translates into actual performance differences. Below I have profiling charts comparing Plonky3 with regular STARK over BabyBear and circle STARK over M31.

Image 0
Image 1

The first thing to note is that the difference in prover time is indeed about 1.3x. You can see that circle STARK spends less time committing to the trace, as it does so over a more efficient base field. Consequently, since computing quotients and FRI involves extension field work, these are now account for a larger percentage of the total work.

Thanks to Shahar Papini for feedback and discussion.

References

  • [HLP24] Haböck et al. (2024) "Circle STARKs"
  • [HAB23] Ulrich Haböck (2023) "A summary on the FRI low degree test"
  • [ethSTARK] StarkWare Team (2023) "ethSTARK Documentation — Version 1.2"

Timofey Yaluhin

Cryptographic work, such as commitments, is often the primary performance bottleneck in SNARKs. This cost is particularly pronounced when committed values are random and necessarily large, as is the case with PLONKish systems.

In recent years, a lot of innovation have been aimed at making commitments as cheap as possible. Circle STARKs and Binius, in particular, are hash-based and sound1 over small fields, M31 and GF[2] respectively. This means lower prover overhead and better hardware compatibility.

However, it should be noted that FRI, the scheme behind these improvements, involves superlinear-time procedures like FFTs, which become a new bottleneck when applied directly to large computations without recursion.

In this note, I will explore GKR, an interactive proof (IP) scheme that addresses cryptographic overhead differently—by nearly avoiding commitments in the first place. My primary aim is to accurately summarize available materials and research. I am very open to changes and improvements, so if anything is unclear or incorrect, please leave comments here.

Background

GKR08 is a relatively old scheme that is based on multivariate polynomials and the sum-check protocol. A technology that was largely ignored in favor of simpler designs featuring univariate polynomials and divisibility check. Lately, however, it has seen renewed interest as projects like Jolt, Expander, and Modulus have demonstrated not only its viability but also impressive performance results.

Notably, modern GKR-based systems demonstrate O(n)O(n) prover complexity, which is linear in the size of the computation and with a constant factor overhead. For some applications, like matrix multiplication, the prover is less than 10x slower than a C++ program that simply evaluates the circuit, Tha13.

Furthermore, the aforementioned Binius is multivariate and it too involves sumcheck. Even StarkWare's Circle-Stark-based proof system called Stwo used GKR for LogUp lookups. I think it is safe to say that there is currently a broad consensus on the relevance of GKR.

Multilinear functions & MLEs

Multilinear polynomial is a multivariate polynomial that is linear in each variable, meaning it has degree at most one in each variable. When multilinear polynomials defined over the boolean domain, they have a much lower degree compared to the univariate case for the same domain size, T23a.

For any multilinear polynomial P(x1,x2,,xv)P\left(x_1, x_2, \ldots, x_v\right) over the boolean domain {0,1}v\{0,1\}^v (the boolean hypercube), polynomial operations such as addition, multiplication, and evaluation can be performed using only the evaluations of PP on the boolean hypercube. This eliminates the need to explicitly reconstruct the polynomial from its evaluations, so there's no FFTs.

Multilinear extension (MLE) is used to translate functions into polynomials over the boolean domain {0,1}v\{0,1\}^v. Every function ff and vector a\vec{a} mapping from {0,1}vF\{0,1\}^v \rightarrow \mathbb{F} has exactly one extension polynomial that is multilinear.

The multilinear extension is a multivariate analog of the low-degree extensions (LDE) commonly present in STARKs. One thinks of MLE(f)\operatorname{MLE}(f) as an "extension" of aa, as MLE(a)\operatorname{MLE}(a) "begins" with aa itself but includes a large number of additional entries. This distance-amplifying nature of MLE, combined with the Schwartz-Zippel lemma, forms the first basic building block of multivariate interactive proofs and GKR in particular.

Sumcheck

The Sumcheck protocol allows a prover P\mathbf{P} to convince a verifier V\mathbf{V} that the sum of a multivariate polynomial over boolean inputs [xi{0,1}][x_i \in \{0, 1\}] is computed correctly.

H:=(x1,,xv){0,1}g(x1,x2,,xv)H := \sum_{(x_1,\cdots,x_v) \in \{0,1\}} g(x_1, x_2, \cdots, x_v)

Sumcheck does not require V\mathbf{V} to know anything about the polynomial to which it is being applied. It is only until the final check in the protocol that, depending on the performance/succinctness tradeoff, V\mathbf{V} can choose to either request the polynomial and evaluate it directly or perform an oracle query, i.e., outsource the evaluation to P\mathbf{P} via a polynomial commitment scheme (PCS).

This is an interactive protocol: If \ell is the number of variables in gg, then \ell rounds are required to complete the protocol. By applying the Fiat-Shamir transform, we can render the sumcheck non-interactive.

This post doesn't aim to explain the general workings of sumcheck. For that, I recommend T23a (section 4.1) or this blog post.

GKR

In GKR, we work with layered circuits. A circuit is layered if it can be partitioned into layers such that every wire in the circuit is between adjacent layers, L23. The number of layers is the depth of the circuit, denoted as dd. Note that many of today's variations of GKR allow for more arbitrary topologies just as well.

The arithmetic circuit C\mathcal{C} encodes logic with addition and multiplication gates to combine values on the incoming wires. Accordingly, functions addi\operatorname{add}_i and muli\operatorname{mul}_i are gate selectors that together constitute the wiring predicate of layer ii.

We encode wire values on a boolean hypercube {0,1}n\{0,1\}^n, creating multi-linear extensions W~i(x)\widetilde{W}_i(x) for each layer ii. The output is in W~0(x)\widetilde{W}_0(x), and inputs will be encoded in W~d(x)\widetilde{W}_d(x).

Gate selectors depend only on the wiring pattern of the circuit, not on the values, so they can be evaluated by the verifier locally, XZZ19. Each gate aa at layer ii has two unique in-neighbors, namely in1(a)\operatorname{in}_1(a) and in2(a)\operatorname{in}_2(a).

addi(a,b,c)={1 if (b,c)=(in1(a),in2(a))0 otherwise \operatorname{add}_i(a, b, c)= \begin{cases}1 & \text { if }(b, c)=\left(\operatorname{in}_1(a), \operatorname{in}_2(a)\right) \\ 0 & \text { otherwise }\end{cases}

and muli(a,b,c)=0\operatorname{mul}_i(a, b, c)=0 for all b,c{0,1}i+1b, c \in\{0,1\}^{\ell_{i+1}} (the case where gate aa is a multiplication gate is similar), T23a. Selector MLEs are sparse, with at most 222^{2\ell} non-zero elements out of 0,13{0,1}^{3\ell}.

addi(x,y,z)={1W~i(x)=W~i+1(y)+W~i+1(z)0 otherwise muli(x,y,z)={1W~i(x)=W~i+1(y)W~i+1(z)0 otherwise \begin{aligned} \operatorname{add}_i(x, y, z) & = \begin{cases}1 & \widetilde{W}_i(x)=\widetilde{W}_{i+1}(y)+\widetilde{W}_{i+1}(z) \\ 0 & \text { otherwise }\end{cases} \\ \operatorname{mul}_i(x, y, z) & = \begin{cases}1 & \widetilde{W}_i(x)=\widetilde{W}_{i+1}(y) \cdot \widetilde{W}_{i+1}(z) \\ 0 & \text { otherwise }\end{cases} \end{aligned}

Note, the above definition does not reflect how selector MLEs are computed in practice, it is an effective method for illustrating the relationship between selectors and wire values.

The GKR prover starts with the output claim and iteratively applies the sumcheck protocol to reduce it from one layer to the next until it arrives at the input. The values on the layers are related thusly:

W~i(x)=y,z{0,1}i+1addi(x,y,z)(W~i+1(y)+W~i+1(z))+muli(x,y,z)(W~i+1(y)W~i+1(z))(1)\widetilde{W}_i(x)=\sum_{y, z \in\{0,1\}^{\ell_{i+1}}}\operatorname{add}_i(x, y, z) \cdot(\widetilde{W}_{i+1}(y)+\widetilde{W}_{i+1}(z))+\operatorname{mul}_i(x, y, z) \cdot(\widetilde{W}_{i+1}(y) \cdot \widetilde{W}_{i+1}(z)) \tag{1}

A few things to note here: First, notice how gate selectors are indexed—this aligns with the convention that selectors at layer ii determine how values from the next layer i+1i+1 are combined. Notice also that the ii-layer sumcheck is over boolean inputs of size i+1\ell_{i+1}, i.e., the number of gates in the next layer.

Protocol

  1. P\mathbf{P} sends the output vector ω\vec{\omega} and claims that ω~=W~0\tilde{\omega} = \widetilde{W}_0.
  2. V\mathbf{V} sends random r0Er_0 \in \mathbb{E} and computes m0:=ω~(r0)m_0 := \tilde{\omega}(r_0).
  3. P\mathbf{P} and V\mathbf{V} apply sumcheck on the relation between W0W_0 and W1W_1 (using fr0f_{r_0} for the summand)
    y,z{0,1}1fr0(y,z)=?m0\sum_{y, z \in\{0,1\}^{\ell_1}} f_{r_0}(y, z) \stackrel{?}{=} m_0
  4. P\mathbf{P} and V\mathbf{V} reduce two claims Wi+1(b)W_{i+1}(b) and Wi+1(c)W_{i+1}(c) to a single random evaluation/combination mim_i.
  5. P\mathbf{P} and V\mathbf{V} apply sumcheck on the reduced relation mim_i, alternating steps 4-5 for d1d-1 more times.
  6. V\mathbf{V} checks that W~d\widetilde{W}_d is consistent with the inputs vector x\vec{x}.

1. P\mathbf{P} sends the output vector ω\vec{\omega} and claims that ω~=W~0\tilde{\omega} = \widetilde{W}_0

First, the P\mathbf{P} has to evaluate the circuit at the given input vector x\vec{x}. This is why the prover is always at least linear to the size of the computation (circuit).

A common notation would be to write the output vector ω\vec{\omega} as a function D:{0,1}0FD: \{0,1\}^{\ell_0} \rightarrow \mathbb{F} mapping output gate labels to output values, 202^{\ell_0} of them in total. The gate labels are the vertices of the boolean hypercube; for example, for 0=2\ell_0=2, the 4 output labels are 0000, 0101, 1010, 1111.

In practice, though, P\mathbf{P} and V\mathbf{V} work with polynomials, not functions, so they have to compute multilinear extension ω~\tilde{\omega} from the vector ω\vec{\omega}. Same goes for the inputs xW~d\vec{x} \rightarrow \widetilde{W}_d. However, since computation on MLEs can be performed over evaluations, in practice no additional computation, like interpolation/IFFT, is even required!

2. V\mathbf{V} sends random r0Er_0 \in \mathbb{E} and computes m0:=ω~(r0)m_0 := \tilde{\omega}(r_0)

V\mathbf{V} picks a random challenge r0Er_0 \in \mathbb{E}. Crucially, the soundness error of the sumcheck protocol is inversely proportional to the size of the field from which challenges rir_i are drawn (due to the Schwartz-Zippel lemma), T23a. That's why in practice for challenge values, we use an extension field E:=Fpk\mathbb{E} := \mathbb{F}_{p^k} where kk is the extension degree.

For example, say we opt for M31 as a base field Fp\mathbb{F}_p whose order is Fp=p=2311|\mathbb{F}_p| = p=2^{31}-1 elements. Then, the probability of soundness error in sumcheck for an \ell-variate summand polynomial is 2311\frac{\ell}{2^{31}-1}, which is too large, certainly for the non-interactive setting. Instead, we choose challenges from QM31—the extension field of M31 with k=4k=4. Now, for any reasonable \ell, the soundness error can be considered negligible.

This soundness characteristic is a notable drawback of sumcheck-based systems, as it requires the GKR prover to work over extension fields after the second round, thus making field work the main contributor to the proving overhead. In Part 2, I'll cover the recent work from Bagad et al describing an algorithm that reduces the number of extension field operations by multiple orders of magnitude.

Also note that V\mathbf{V} cannot yet trust ω~\tilde{\omega} correctly to encode the outputs. The remainder of the protocol is devoted to confirming that the output claim is consistent with the rest of the circuit and its inputs.

3. P\mathbf{P} and V\mathbf{V} apply sumcheck on the relation between W0W_0 and W1W_1

For the first layer, P\mathbf{P} and V\mathbf{V} run a sumcheck on Equation (1)(1) with i=0i=0, between W0W_0 and W1W_1, with xx fixed to r0r_0.

y,z{0,1}1addr0(y,z)(W~1(y)+W~1(z))+mulr0(y,z)(W~1(y)W~1(z))=?m0\sum_{y, z \in\{0,1\}^{\ell_1}} \operatorname{add}_{r_0}(y, z) \cdot\left(\widetilde{W}_1(y)+\widetilde{W}_1(z)\right)+\operatorname{mul}_{r_0}(y, z) \cdot\left(\widetilde{W}_1(y) \cdot \widetilde{W}_1(z)\right) \stackrel{?}{=} m_0

In the first round of sumcheck, P\mathbf{P} uses r0r_0 to fix the variable xx. In the remaining two rounds, V\mathbf{V} picks b,cEb, c \in \mathbb{E} randomly to fix the variables yy and zz, respectively. At the end of the sumcheck, from V\mathbf{V}'s point of view, the relation on the sum (Equation 11) is reduced to a simple check that the summand fr0(b,c)f_{r_0}(b, c) evaluates to m0m_0.

To compute fr0(b,c)f_{r_0}(b, c), V\mathbf{V} must compute addr0(b,c)\operatorname{add}_{r_0}(b, c) and mulr0(b,c)\operatorname{mul}_{r_0}(b, c) locally. Remember that these depend only on the circuit's wiring pattern, not on the values. Since fr0f_{r_0} is recursive, V\mathbf{V} also asks P\mathbf{P} for the W~1(b)\widetilde{W}_1(b) and W~1(c)\widetilde{W}_1(c) values and computes fr0(u,v)f_{r_0}(u, v) to complete the sumcheck protocol.

In this way, P\mathbf{P} and V\mathbf{V} reduce a claim about the output to two claims about values in layer 1. While P\mathbf{P} and V\mathbf{V} could recursively invoke two sumcheck protocols on W~1(b)\widetilde{W}_1(b) and W~1(c)\widetilde{W}_1(c) for the layers above, the number of claims and sumcheck protocols would grow exponentially in dd. XZZ19

4. P\mathbf{P} and V\mathbf{V} reduce two claims Wi+1(b)W_{i+1}(b) and Wi+1(c)W_{i+1}(c) to a single random evaluation/combination mim_i

To avoid an exponential blow-up in complexity, P\mathbf{P} and V\mathbf{V} apply a "rand-eval" reduction subroutine.

Here I will describe a method from CFS17 based on random linear combination (RLC), as it is more commonly found in modern implementations. Later, for completeness, I will also include the method based on line restriction, as described in the original paper GKR08.

Given two claims W~1(b)\widetilde{W}_1(b) and W~1(c)\widetilde{W}_1(c), V\mathbf{V} picks random weights αi,βiE\alpha_i, \beta_i \in \mathbb{E} and computes the RLC as

mi=αiW~1(b)+βiW~1(c)m_i = \alpha_i \widetilde{W}_1(b)+\beta_i \widetilde{W}_1(c)

In the next step, V\mathbf{V} would use mim_i as the claim for the ii-th layer sumcheck.

5. P\mathbf{P} and V\mathbf{V} apply sumcheck on the reduced relation mim_i, alternating steps 4-5 for d1d-1 more times

For the layers i=1,,d1i=1, \ldots, d-1, P\mathbf{P} and V\mathbf{V} would execute the sumcheck protocol on Equation (2)(2) instead of Equation (1)(1)

αiW~i(b)+βiW~i(c)=y,z{0,1}n((αiaddi(b,y,z)+βiaddi(c,y,z))(W~i+1(y)+W~i+1(z))+(αimuli(b,y,z)+βimuli(c,y,z))(W~i+1(y)W~i+1(z)))(2)\begin{align} &\alpha_i \widetilde{W}_i(b)+\beta_i \widetilde{W}_i(c) = \\ &\sum_{y, z \in\{0,1\}^n}\binom{(\alpha_i\cdot\operatorname{add}_i(b, y, z)+\beta_i\cdot\operatorname{add}_i(c, y, z)) \cdot(\widetilde{W}_{i+1}(y)+\widetilde{W}_{i+1}(z))}{+(\alpha_i\cdot\operatorname{mul}_i(b, y, z) +\beta_i\cdot\operatorname{mul}_i(c, y, z)) \cdot(\widetilde{W}_{i+1}(y) \cdot \widetilde{W}_{i+1}(z))} \end{align}\tag{2}

At the end of each layer's sumcheck protocol, V\mathbf{V} still receives two claims about W~i+1\widetilde{W}_{i+1}, computes their random linear combination, and proceeds to the next layer above recursively until the input layer. XZZ19

6. V\mathbf{V} checks that W~d\widetilde{W}_d is consistent with the inputs vector x\vec{x}

At the input layer dd, V\mathbf{V} receives two claims W~d(bi=d)\widetilde{W}_d(b_{i=d}) and W~d(ci=d)\widetilde{W}_d(c_{i=d}) from P\mathbf{P}. Recall that W~d\widetilde{W}_d is claimed to be a multilinear extension of the input vector x\vec{x}.

If V\mathbf{V} knows all the inputs in clear, they can compute W~d\widetilde{W}_d and evaluate it at bi=db_{i=d} and ci=dc_{i=d} themselves.

Alternatively, if V\mathbf{V} doesn't know all inputs and is instead given an input commitment [wd][w_d] for succinctness or zero-knowledge reasons, then V\mathbf{V} queries the oracle for evaluations of W~d\widetilde{W}_d at bi=db_{i=d} and ci=dc_{i=d}.

Ultimately, V\mathbf{V} outputs accept\mathbf{accept} if the evaluated values are the same as the two claims; otherwise, they output reject\mathbf{reject}. XZZ19

Analysis

Let C:FE\mathcal{C}: \mathbb{F} \rightarrow \mathbb{E} be a layered circuit of depth dd with n:=xn := |\vec{x}| input variables, having SiS_i gates in layer ii. Naturally, C:=i=0dSi|\mathcal{C}| := \sum^d_{i=0} S_i is the total number of gates in the circuit, i.e., the circuit size.

  • Rounds: O(dlogC)O(d\cdot \log |\mathcal{C}|).
  • P\mathbf{P} time: O(ClogC)O(|\mathcal{C}|\cdot\log |\mathcal{C}|)
  • V\mathbf{V} work: O(n+dlogC+t+S0)O(n+dlogC)O(n+d\cdot\log |\mathcal{C}|+t+S_0) \approx O(n+d\cdot\log |\mathcal{C}|) for 1 output.
  • Communication: O(S0+dlogC)O(S_0+d\cdot\log |\mathcal{C}|) field elements.
  • Soundness error: O(dlogCE)O(\frac{d\cdot\log |\mathcal{C}|}{|\mathbb{E}|})

The GKR protocol consists of one execution of the sumcheck protocol per layer. Therefore, the total communication cost (proof size) is O(dlogC)O(d \log |\mathcal{C}|) field elements. The accumulated soundness error is O(dlogCE)O\left(\frac{d \cdot \log |\mathcal{C}|}{|\mathbb{E}|}\right) due to the Schwartz-Zippel lemma. T23a

The prover must first evaluate the circuit, which takes time C|\mathcal{C}|. It must also compute addi\operatorname{add}_i and muli\operatorname{mul}_i at each layer, which, if done trivially, induces logarithmic overhead logC\log |\mathcal{C}|. The resulting time for the prover is O(ClogC)O(|\mathcal{C}| \cdot \log |\mathcal{C}|). XZZ19

The verifier's work is O(n+dlogC+t+S0)O(n + d \log |\mathcal{C}| + t + S_0), where S0S_0 is the number of outputs of the circuit, tt denotes the optimal time to evaluate all addi\operatorname{add}_i and muli\operatorname{mul}_i, and the nn term is due to the time needed to evaluate W~d\widetilde{W}_d. XZZ19

Part 2 will cover modifications and techniques that result in O(C)O(|\mathcal{C}|) prover.

Zero Knowledge

To make the sumcheck protocol zero-knowledge, the polynomial in the sumcheck protocol is masked by a random polynomial.

To prove the sumcheck for the summand polynomial ff from Equation (1)(1) and a claim WW in zero-knowledge, P\mathbf{P} generates a random polynomial γ\gamma with the same variables and individual degrees as ff, commits to γ\gamma, and sends V\mathbf{V} a claim Γ=x1,,x{0,1}γ(x1,,x)\Gamma = \sum_{x_1, \ldots, x_{\ell} \in \{0,1\}^{\ell}} \gamma(x_1, \ldots, x_{\ell}) V\mathbf{V} picks a random number ρ\rho, and together with P\mathbf{P} executes the sumcheck protocol on

W+ρΓ=x1,,xn{0,1}f(x1,,xn)+ργ(x1,,xn)W+\rho\cdot\Gamma=\sum_{x_1, \ldots, x_{n} \in\{0,1\}^{\ell}} f\left(x_1, \ldots, x_{n}\right)+\rho\cdot\gamma\left(x_1, \ldots, x_{n}\right)

In the last round of this sumcheck, P\mathbf{P} opens the commitment to γ\gamma at γ(r1,,r)\gamma(r_1, \ldots, r_{\ell}), and the verifier computes f(r1,,r)f(r_1, \ldots, r_{\ell}) by subtracting ργ(r1,,r)\rho \cdot \gamma(r_1, \ldots, r_{\ell}) from the last message, and compares it with P\mathbf{P}'s original claim.

Chiesa et al. showed that as long as the commitment and opening of γ\gamma are zero-knowledge, the protocol is zero-knowledge.

Original method to reduce two claims to one

Let W~\widetilde{W} be a multilinear polynomial over F\mathbb{F} with logn\log n variables. The following is the description of a simple one-round subroutine from GKR08 with communication cost O(logn)O(\log n) that reduces the evaluation of W~(b)\widetilde{W}(b) and W~(c)\widetilde{W}(c) to the evaluation of W~(r)\widetilde{W}(r) for a single point rEr \in \mathbb{E}.

P\mathbf{P} interpolates a unique line \ell passing through bb and cc, such that (0)=b\ell(0)=b and (1)=c\ell(1)=c. The line can be formally defined as (t)=b+t(cb)\ell(t) = b + t \cdot (c - b) using the point-slope form. The points bb and cc are tuples with vv elements for a vv-variate polynomial W~\widetilde{W}.

By substituting bb and cbc - b into (t)\ell(t), we get the tuple (t)=(0(t),,v(t))\ell(t) = (\ell_0(t), \cdots, \ell_{v}(t)) defined by vv linear polynomials over tt. P\mathbf{P} sends a univariate polynomial qq of degree at most ki+1k_{i+1} that is claimed to be W~i+1\widetilde{W}_{i+1} \circ \ell, the restriction of W~i+1\widetilde{W}_{i+1} to the unique line \ell.

q(t):=(W~)(t)=W~(0(t),,logn(t)))q(t) := (\widetilde{W} \circ \ell)(t)=\widetilde{W}(\ell_0(t),\cdots,\ell_{\log n}(t)))

V\mathbf{V} interprets q(0)q(0) and q(1)q(1) as P\mathbf{P}'s claims for the values of W~(b)\widetilde{W}(b) and W~(c)\widetilde{W}(c). V\mathbf{V} also picks a random point rFr^* \in \mathbb{F}, sets r=(r)r=\ell(r^*), and interprets q(r)q(r^*) as P\mathbf{P}'s claim for the value of W~(r)\widetilde{W}(r). See the picture and an example from T23a (Section 4.5.2).

References

  • [Tha13] Justin Thaler (2013). "Time-Optimal Interactive Proofs for Circuit Evaluation"
  • [T23a] Justin Thaler (2023). "Proofs, Arguments, and Zero-Knowledge". See also lecture notes.
  • [L23] Jieyi Long (2023). "Efficient Arguments and Proofs for Batch Arithmetic Circuit Satisfiability"
  • [XZZ+19]: Tiancheng Xie et al. (2019). "Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation"
  • [G24] Ariel Gabizon (2024). zkWarsaw talk "The GKR method".

  1. statistically sound, as in likelihood of error is small, based on statistical measures according to field size and other factors. Also note that Circle STARKs and Binius must use extension fields in certain parts of computation, e.g. M31^4 for Circle-FFT.

Daniel Choi

Introduction

In software development (and more commonly in the blockchain ecosystem), many often interact with Open Source Software (OSS) to either draw inspiration from or simply copy-paste. The latter case described is a very common scenario for smart contract development and many developers fork another project's code and piggy back off of another person's/team's work.

IRL

During the token craze of 2021, new tokens were being minted every hour and there have been many of these tokens that have been copied - sometimes with very minor modifications. Using another person's/team's code is always risky and could potentially introduce a "zero-day" vulnerability. An example of this would be the case of Grim Finance's exploit. Grim Finance had forked Beefy Finance's smart contracts and have made changes according to their protocol's needs. Beefy Finance had uncovered a vulnerability with their smart contracts, which allowed for a reentrancy attack. The same attack vector was what caused Grim Finance to become hacked.

Another project that had introduced a "zero-day" vulnerability was Compound Finance. In the Compound Finance code, there was a rounding error which could be used by an attacker to manipulate empty markets. The same way Compound Finance was attacked, other similar protocols that forked their code were also attacked. Some of these protocols include Onyx, Hundred Finance, Midas Captial, and Lodestar Finance (NOT to be confused with the Lodestar Ethereum 2 client!!!).

A similar case is with Meter, an unaffiliated fork of Chainbridge . Meter had introduced a vulnerability that was not present in the base Chainbridge smart contracts. Improper modifications to the code had opened the smart contract to different attack vectors. More information regarding this can be found here.

Transparency, Collaboration, Pacing and Audits

As part of an on-going effort to make the blockchain ecosystem into a safer environment for users to interact with and participate in, developers must take ownership and responsibility for their shortcomings. In many cases, projects do not make known to the developers/owners of the code base that they will be using and forking their code. This may be due to a project's desire to stay stealth, or they wish to hide the fact they explicitly copied another project's code. Whichever the case, the argument could be made that if the "forkers" had made known to the "forkee", there could have been a collaborative effort to mitigate known vulnerabilities or work together to uncover new ones. Transparency (as well as humility) is an important part in building a stronger community of developers so we can help shoulder these type of burdens.

Timing is very important when it comes to go-to-market strategies. The same execution in different times could produce significantly opposing results. During bull markets, there is a pressure to release a token (or blockchain project) as fast as humanly possible. During the rush and chaos, blunders could be made and sleep-deprived developers could make a simple but critical mistake. It is imperative to note that smart contracts (as long as not upgradeable) cannot be modified. Once a smart contract is deployed, the source code remains forever, unable to change. Thus, a smart contract should be - ideally - without possibilities for a present attack nor future ones. To get closer to this goal, getting one's smart contracts audited is paramount, especially when it will deal with money and valuable assets. Especially when re-using code and introducing new logic, these things should be audited, even if the base contracts that were forked were already audited.

Here Comes ChainSafe

ChainSafe is a blockchain development company that loves to work with the community and wants to support a conducive environment for growth and collaboration. As part of that, ChainSafe offers services such as Smart Contract Auditing, Engineering Services, and R&D Consultancy, which people can utilize for their project. ChainSafe also offers OSS dev tooling that could be used and we encourage you to engage with us in our Community. Let's work together to stay [Chain]safe.

Willem Olding

One way to think of a blockchain is as a system for verifying provable statements to alter a global state. Examples of provable statements include:

  • Proving you hold a private key corresponding to a public key by signing some data. This is how transactions are authorized to mutate the ledger.
  • A proof-of-work (PoW)
  • Proving you know the pre-image of a hash
  • Proving result of executing a known, deterministic program on known data. The blockchain executes the program itself to check the result
  • A SNARK proof of the result of executing a known program on (possibly unknown) data

To verify a proof, the blockchain performs the verification computation inside its execution and this can result in changes to global state. Other on-chain applications can treat the result as if it is truth.

Some statements have a lovely property in that they are succinct. This means it is easier to verify them than it is to prove them (PoW, SNARK). Others take the same amount of work either way (deterministic arbitrary computation).

What you might have spotted from above is that some of these are in theory provable statements but they are impractical to prove on a blockchain. For example hashing an extremely large piece of data, or checking the result of a long and complex computation.

Dispute games are multi-party protocols that, under certain economic conditions, can allow a blockchain to be convinced of a statement while only having to execute a small part of a computation when disputes arise.

One-step Fraud Proving

For statements that could be proven on-chain there is an elegant solution that can avoid expensive verification costs. In a one-step fraud proof Ashley submits a statement on-chain (e.g. the result of this computation is X) along with a bond. The bond should be greater than the expected gas cost of having the chain verify the proof.

The statement is considered pending by the chain for a length of time known as the challenge period. During this time anyone (Bellamy) can pay the gas and force the chain to perform the check in full. This will then determine if Ashley was indeed correct and update the state accordingly. If Ashley is proven to be wrong their bond is slashed and given to Bellamy.

Importantly, if no one challenges Ashley during the challenge period it is safe to assume the statement is true under the assumption that there is at least one observer who would have proven Ashely false if they could.

This approach is great for on-going protocols like rollups where it is important to keep the running cost low. It is relatively simple in its implementation and can be permissionless.

This design was used by the early versions of Optimism such that the rollup state transition was only computed on L1 in the case of a dispute. Another clever application is in the Eth-NEAR Rainbow Bridge where one-step fraud proofs are used to avoid performing expensive Ed25519 signature checks on Ethereum under regular operation. In recent months some projects such as Fuel have proposed using on-step fraud proofs to avoid performing expensive SNARK verification unless there is a dispute.

The downside to one-step proofs is they are not applicable in every case. It must be possible to fall back to executing the verification on-chain. Some types of computation are simply too large or require too much data for this to be feasible. What can be done in this case?

2-party bisection dispute games

The Arbitrum paper first popularized bisection dispute games in the blockchain space. To understand a bisection game you first need to understand emulators and the computation trace.

A program can be expressed as a sequence of instructions to be executed on a processor. This processor also has registers and/or memory to store state.

Executing the program and recording the registers+memory at after each instruction is called an execution trace. This trace may be much longer than the original program as instructions may branch or loop. For a program that terminates this execution trace can be considered a very verbose proof of the final state. A program that knows how to execute all the possible instructions and update the state accordingly (an emulator) can verify this proof.

A program trace for any non-trivial program is absurdly huge, but it can be compressed using two clever tricks.

The first is that the full CPU+memory state need not be included at each step. Instead a commitment of the state (e.g. Merkle root) can be recorded instead.

The second applies when there are two conflicting parties in dispute about the result of executing a program. A two-party protocol can be used to reduce the trace down to the first instruction that the parties disagree upon the result of. A third trusted arbitrator (usually a blockchain runtime) can then execute only a single instruction in the trace resolve a dispute over an entire program.

This last trick of framing the dispute as being between two parties allows proving faults in programs in a number of steps that is logarithmic in the length of the trace, followed by the execution of a single instruction. This is incredibly powerful and has been developed by Arbitrum and the Optimism Bedrock prototype for proving rollup state transitions, along with Cartesi for proving arbitrary computations on-chain.

Problems

The problem with this approach as described is that once two players are engaged in a dispute they must both remain live in order to resolve it. There is also no way to ensure that both participants are honest so it must be possible for multiple disputes to be open on a single claim at once for the honest minority assumption to hold.

A malicious challenger may open many dispute games on a single assertion and although they will lose their bond if they have more available funds than the defender they can eventually prevent them from being able to participate. I have written about this issue in another article.

The usual solution to this is to limit who can participate in dispute games. This is the approach used by Arbitrum and the Optimism Bedrock prototype. This compromise places these dispute game systems in an in-between trusted federation and fully permissionless dispute games.

Permissionless Bisection Dispute Games

So can bisection style dispute games be made fully permissionless? A recent paper by Nehab and Teixeira proposes a modification to the dispute games where the participants must submit a vector commitment to the entire execution trace before the game begins. Once this has been done the game becomes permissionless as anyone can submit a step along with its inclusion proof.

This is an excellent solution however it has a major drawback. Execution traces are incredibly large, commonly several trillion instructions. Producing a merkle tree and associated proofs for such a long vector is prohibitive in most cases. The authors solution to this is to split the trace into stages and run

More recently Optimism has proposed another design which structures dispute game is structured as an n-degree tree rather than a binary tree. This allows other participants to fork off an existing dispute game when they believe participants to be fraudulent.

Bond is added incrementally at each step of the tree allowing permissionless participation. Once a game has concluded the player who asserted correctly against any branch that has been proven false can collect the bond on each of those nodes in the tree.

This design gives the best of both worlds allowing permissionless participation without needing to compute trace commitments. This is at the cost of increased complexity in implementation.

Conclusion

Dispute games are conceptually simple but designing them to be permissionless is much more challenging. Despite dispute games being proposed for use in blockchain systems more than 5 years ago, and claiming to be permissionless, there has not been a single permissionless dispute game used in production.

Optimism has made excellent progress in the last year design dispute games that can be safe and permissionless and these will hopefully be deployed in production in the near future.

Jagrut Kosti

Given a blockchain protocol, where the transactions are included in a block by a miner or validators, there are a few incentive compatibility requirements that do not get much attention. These are:

  • Dominant Strategy Incentive Compatible (DSIC)
  • Incentive Compatibility for Myopic Miner (MMIC)
  • Off-Chain Agreements (OCA)

For a sustainable decentralized ecosystem, it is important to align the incentives so that system isn't biased towards a particular actor at scale. While this article discusses base layer incentives, the requirements can be extended in application layer as well. In most protocols, there are primarily 2 different actors: the ones that maintain the protocol and the ones that use it. They can be further divided based on the architecture, but the collective flow of revenue is between these actors. Not much research efforts have gone into formalizing the requirements for a susitainable incentive structure.

We first formalize transaction fee mechanism (TFM), then define the incentive compatibility requirements and conclude by stating what does a good TFM should consist of. The description and the conclusion are based on 2 papers mentioned in the reference section.

Transaction Fee Mechanism

A transaction tt has publicly visible and immutable size sts_t. The creator of the transaction is responsible for specifying a bid btb_t per unit size, publicly indicating to pay upto stbts_t \cdot b_t. A block is an ordered sequence of transactions and each block has a cap on the number of included transactions called maximum block size, CC (capacity). A Mempool is a list of outstanding transaction waiting to be included in the block. MM is miner's current mempool.

Valuation vtv_t is the maximum per size value the transaction inclusion in a block for a creator is (vtv_t is private to the creator) whereas btb_t is what they actually pay. Valuation can also be thought of as maximum price for the utility of a transaction to be included in the block.

H=B1,B2,...,Bk1H = B_1, B_2, ..., B_{k-1} (History) is the sequence of blocks in the current longest chain. B1B_1 being the genesis block and Bk1B_{k-1} the most recent block.

Allocation Rule

Allocation rule is a vector-valued function xx from the on-chain history HH and mempool MM to a 0-1 value xt(H,M)x_t(H,M) for each pending transaction tMt \in M.

A value of 1 for xt(H,M)x_t(H,M) indicates transaction tt’s inclusion in the current block BkB_k; a value of 0 indicates its exclusion.

Bk=x(H,M)B_k = x(H,M) is the set of transactions for which xt(H,M)=1x_t(H,M) = 1.

A feasible allocation rule is a set of transactions TT such that:

tMstxt(H,M)C\sum_{t \in M} s_t \cdot x_t(H, M) \le C

While a allocation rule is defined with some criteria in mind, it is important to note that the miner (block proposer) has the ultimate say over the block it creates.

Payment Rule

Payment rule is a function pp from the creator of the included transactions to the miner for each included transaction tBkt \in B_k.

pt(H,Bk)p_t(H, B_k) is a non-negative number for each unit size.

Burning Rule

Burning rule is a function qq, indicating the amount of money burned by the creator of transaction tBkt \in B_k.

qt(H,Bk)q_t(H, B_k) is a non-negative number for each unit size.

Burning rule can also be thought of as a refund to the holders of the currency via deflation. An alternative is to redirect a block's revenue to entities other than block's miner e.g. foundation, future miners, etc.

A TFM is a triple (x,p,q)(x, p, q) where x is a feasible allocation rule, p is payment rule and q is burning rule.

Incentive Compatibility

Dominant Strategy Incentive Compatible

User's Utility Function

For a TFM (x,p,q)(x, p, q), on-chain history HH and mempool MM, the utility of the originator of the transaction tMt \notin M with valuation vtv_t and bid btb_t is:

ut(bt):=(vtpt(H,Bk)qt(H,Bk))stu_t(b_t) := ( v_t - p_t(H, B_k) - q_t(H, B_k)) \cdot s_t

if tt is included in Bk=x(H,M(bt))B_k = x(H, M(b_t)), 0 otherwise.

We assume that a transaction creator bids to maximize the utility function above. A TFM is then DSIC if, assuming that the miner carries out the intended allocation rule, every user (no matter what their value) has a dominant strategy — a bid that always maximizes the user’s utility, no matter what the bids of the other users.

E.g. First Price Auctions (FPA) are not DSIC. An FPA allocation rule (historically Bitcoin, Ethereum) is to include a feasible subset of outstanding transactions that maximizes the sum of the size-weighted bids. A winner then pays the bid if the transaction is included and nothing is burned and all revenue goes to the miner.

Incentive Compatibility for Myopic Miner

Myopic Miner Utility Function

For a TFM (x,p,q)(x, p, q), on-chain history HH, mempool MM, fake transactions FF, and choice BkMFB_k \subseteq M \cup F of included transactions (real and fake), the utility of a myopic miner (a miner concerned only with the current block) is:

u(F,Bk):=tBkMpt(H,Bk)sttBkFqt(H,Bk)stμtBkstu(F, B_k) := \sum_{t \in B_k \cap M} p_t(H, B_k) \cdot s_t - \sum_{t \in B_k \cap F} q_t(H, B_k) \cdot s_t - \mu \sum_{t \in B_k} s_t

where μ\mu is the marginal cost per unit size for a miner. Its the same for all miners and a common knowledge.

  • The first term is the miner's revenue
  • The second term is the fee burn for miner's fake transactions. It does not include real transactions as that is paid by transaction's creators.
  • The third term is the total marginal cost

A TFM is then MMIC, if a myopic miner maximizes its utility by creating no fake transactions i.e. settingF=F = \emptyset

E.g. FPAs are MMIC as the miner's best choice is to include all max bid transactions and including fake transactions does not increase any utility. Second-price type auctions, on the other hand, are not MMIC since a miner can include fake transactions to boost the max bid.

Off-chain Agreements

In OCA, each creator of transaction tt agrees to submit tt with on-chain bid btb_t while transferring τst\tau \cdot s_t to the miner off-chain; the miner in turn agrees to mine a block comprising the agreed upon transactions of TT.

A TFM is OCA-proof if, for every on-chain history HH, there exists an individually rational bidding strategy σH\sigma_H such that, for every possible set TT of outstanding transactions and valuations vv, there is no OCA under which the user's utility of every transaction and the miner's utility is strictly higher than in the outcome Bk=x(H,M(σH(v)))B_k = x(H,M(\sigma_H(v))) with on-chain bids σH(v)\sigma_H(v) and no off-chain transfers.

E.g. FPAs are OCA-proof whereas the TFMs where any amount of revenue is burned are not.

Conclusion

The article gives a brief overview of the formalization in TFM design. For a sustainable protocol, it is important that the TFM is DSIC, MMIC and OCA-proof. Based on this, the obvious question is: Is there any TFM that satisfies all 3 properties?

[1] conjectures that no non-trivial TFM can satisfy all 3 properties and [2] proves this conjecture. For designing a TFM, we can generally say that it would be interesting to characterize a mechanism that satisfy various subsets and relaxations of these 3 properties. The goal should be to minimize the effects of a property that is not satisfied or partially satisfied.

I highly recommend interested users to read [1] & [2].

References

  1. Roughgarden, Tim. "Transaction fee mechanism design." ACM SIGecom Exchanges 19.1 (2021): 52-55. (Paper)
  2. Chung, Hao, and Elaine Shi. "Foundations of transaction fee mechanism design." Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2023. (Paper)

Daniel Choi

In an evolving blockchain ecosystem, the number of bad actors and exploiters grow, one could experience some fear or paranoia around interacting with strangers in the terrifying internet.

In this short article, we will explore a few ways to equip yourself with the necessary tools to fend off any potential attacks and keep your keys/system secure. This handbook will encompass a few protective measures, including:

Our exploration will dive into the Ethereum blockchain system and associated tools and technologies.

Key Storage

One's key(s) is an essential component to interacting with the blockchain and an incredibly valuable piece of data that should be well guarded. Safeguarding these keys should be prioritized and those keys should always be used with caution.

A simple way to start is choosing how one's private keys are generated. Opt for offline generation to ensure that the process remains concealed from prying eyes and potential data breaches. An offline private key generator, such as this one, guarantees the confidentiality of your private key. Additionally, consider exploring the SLIP39 protocol — a mnemonic (private key) generator leveraging Shamir Secret Sharing to divide the seed phrase into multiple shares.

These private keys, or mnemonic - a list of 12 or 24 words, must be safeguarded and should never be lost or stolen. You may wish to physically write down your private key/mnemonic on a piece of paper, which is called a "paper wallet". It is imperative to never lose this piece of paper and take precautionary measures, such as buying a safe to store it in. The best way to protect your keys is to generate them offline on a dedicated computer/device. This computer/device will never connect to the internet and be "air gapped", which will further shield your keys.

Alternatively, entrusting a reputable wallet application with your key management is another option. Beware that certain wallets are "custodial," implying that they possess ownership of your keys, while merely providing access to it via their platform. Opting for a "non-custodial" wallet provides greater autonomy, granting you full control over your assets by exporting one's private key. As the saying goes, "not your private key, not your coins".

Among various "non-custodial" wallets, ZenGo, Torus, Argent and AlphaWallet stand out. Particulary, the most technologically inclined for protection is ZenGo. This is due to the its MPC (multi-party computation) as well as the "social recovery" feature.

There are also different types of wallets such as hot wallets and cold wallets. Any keys used to continually connect to the internet and make frequent transactions would be a "hot wallet". "Cold wallets" would refer to stored keys that are not connected to the internet and are rarely used, such a Ledger and Trezor. For highest security, both should be used. The cold wallet should hold longer term assets that do not need to be transferred frequently and the hot wallet should have minimum funds (perhaps, up to the amount one would be willing to lose).

To note, there is actually a vulnerability for the Terzor T. Additional information can be found here. Due to this, it is recommended to use another model offered by Trezor, or taking extra precautions in physically securing the device.

Wallet Security

So now that you have a wallet, does that mean it's secure forever? Most likely not... However, there are a few ways to make sure your wallets are protected. Let us explore some important strategies for proper and ongoing maintenance.

  1. Asset Monitoring: Employ monitoring tools like such as tenderly and OZ Defender to track wallet addresses and associated assets. These will will help in checking wallet address(es) and you may optionally configure notifications for any activity on those address(es). Alternatively, a blockchain explorer can be used to view your address.
  2. Approval Management: When interacting with tokens, there is a process by which you allow "approval" for another address to transfer the corresponding token. This is a necessary step when minting/burning/transferring tokens. However, there are plenty of times a contract will request "indefinite approval" for any amount of tokens. These are especially dangerous if the contract has malicious intent. Utilize tools such as revoke, unrekt, orzapper to manage "approvals" for all of your addresses.
  3. Key Rotations: Regularly rotate your keys to enhance security. While there is no particularly fixed schedule for key rotations, the more frequently you do it, the more likely your keys will be secure - granted they are generated in a secure manner. Key rotation involves generating a new key and then transferring your previous assets to the new key. Though execution costs may be a deterring factor in the frequency of key rotations, it is still an important practice to exercise.
  4. Adding Canary Tokens/Accounts: For the ultra-cautious, there is a great tool to provide insight into potential breaches. Canary Tokens generates a dummy file and it can be given an obvious name, like "privatekeys.txt". The file will then keep track of who accessed the file, when it has been accessed, and from where. This is a great way to ascertain if your computer has been compromised and if there is anyone lurking that could potentially cause you harm. To get started, you can follow this quick guide.

Ephemeral Execution Environment

A great way to ensure that all web3 interactions are safe would be to setup a brand new environment. This will account for any potential malware or undetected bad-actors that could be present in your current system.

One way this could be done is by creating a VM (virtual machine) - ideally a dedicated machine. This will be used solely for any blockchain activity. This will guarantee a clean working environment and can foster some peace of mind. Another benefit to this type of setup is that if anything anomalous occurs, you can always tear down the VM and build a new one again!

A very useful article for getting quickly set up and get started is available here. Bear in mind, this article does not go through security in detail (e.g. networking security) and should be considered when following the article.

Making Smart Decisions

People are prone to making mistakes, but rarely do they make a royal one. When it comes to protecting your assets, however much, there is nothing more important. Minimizing errors is crucial, as actions within the blockchain are immutable.

A very common problem for blockchain users are phishing scams. Some are relatively easy to catch, and here are a couple tips on how to avoid them. Firstly, never click any links (especially if they're phish-y) in emails or strange websites - supplemental information can be found here. Secondly, do not send tokens to any address(es) that are unkown or unverified. Along these lines, be aware of who you are interacting with online (whether username, email, etc.). If an email or DM was sent by a a funny looking email/username, one could deduce that it is most likely a scam.

Another tip is to go deeper into the code. If able, one should try to examine the protocol's codebase and make sure that it is public and verified. This will help with making informed decisions when interacting with a smart contract. Although this may be a far more difficult security practice, there are other simpler ways such as ensuring a protocol has received an audit.

Conclusion

While this article offers a succinct overview, I hope it goes through some useful tips to be more security-centric. As a now-informed reader, delve into further research and tread cautiously in the dark forest.

If this article was helpful, please let us know and make a request! There is a number of things that could be added or further expounded on and could possibly be in another article. Thanks for the read and stay (Chain)Safe.

Jagrut Kosti

Ever had to go out with your colleagues for lunch and experienced how hard it can be to come to a conclusion on where to eat? Individual decision making is hard. Collective decision making is much harder (an understatement)! But it is extremely important, especially in decentralized autonomous organizations (DAOs). To be able to come to a conclusion using code as mediator is challenging. But before we dive into the complexities of governance whether on-chain or off-chain, let's understand some of the fundamentals from social choice theory and the decades of work that has been put into understanding decision making in a democratic structure.

Most of the DAOs that have implemented governance mechanism, essentially boils down their voting method into single choice "yes", "no" or "abstain" option. While this seems intuitively simple and completely eliminates the complex intricacies involves in ranked choice voting, it's not the best system for all scenarios. And most of the projects do not seem to highlight this:

Let's say for platform X (sarcasm intended), a decision has to be made about which logo, out of logoA, logoB and logoC, should be adopted. One can argue that instead of creating one proposal and tallying using ranked choice preference, we can split the proposal into 3 and carry-on with the usual voting methods adopted by DAOs:

  • Should we go with logoA? Options: "yes", "no", "abstain"
  • Should we go with logoB? Options: "yes", "no", "abstain"
  • Should we go with logoC? Options: "yes", "no", "abstain"

This opens up a can of worms! What happens if logoA and logoB both have "yes" as the winner? Should we then create another proposal to resolve the tie? Are the same voters going to vote on that? What if some significant portion of the old voters does not show up? What if new voters show up? Would this not increase voter fatigue?....

While most DAOs try to avoid such proposals, it can still happen depending on the topic of discussion. There is a reason why ranked choice preference tallying is avoided but that does not mean it cannot be made practical. In this article, we will look into a few of the well-known theorems in social choice theory and to keep in mind when designing any governance mechanism.

May's Theorem

The reason that most DAOs use single choice simple majority voting method is because of the May's theorem:

For two alternative voting, May's theorem states that simple majority is the only anonymous, neutral and positively responsive social choice function.

Anonymous: There is no distinction between the votes and each voter is identical.

Neutral: Reversing the choice of each voter, reverses the group outcome.

Positively Responsive: If some voters change their preference in favor of one option, while others remain the same, the proposals outcome does not change in opposite direction. If the previous outcome was a tie, the tie is broken in the direction of the change.

The theorem only applies if there are two options. In most DAO's ballot (set of options in proposals), "abstain" vote is not counted and hence the theorem applies.

Arrow's Impossibility Theorem

Arrow's impossibility theorem applies only for ranked choice voting. A voting rule is a method of choosing winner from a set of options (ballot) on the basis of voter's ranking of those options. Before jumping into the theorem, lets examine a couple of different voting rules.

In plurality rule, the winning option is the option which was ranked first the most than any other option. E.g. for 3 options XX, YY & ZZ, if 40% voters liked XX best i.e. ranked it first, 35% liked YY best and 25% liked ZZ best, then XX wins, even though it is short of an over-all majority (greater than 50%).

40%35%25%
XYZ

In majority rule, the winning option is the option that is preferred by a majority to each other option. E.g. for 3 options XX, YY & ZZ, if 40% voters rank X>Y>ZX>Y>Z, 35% rank Y>Z>XY>Z>X and 25% rank Z>Y>XZ>Y>X, the winner is YY because majority of voters (35% + 25% = 60%) prefer YY to XX and a majority (40% + 35% = 70%) prefer YY to ZZ.

40%35%25%
XYZ
YZY
ZXX

Note that plurality and majority rule leads to different outcome. This prompts the question: Which outcome is "right"? Or, which one is better to use? We can then ask a general question: Among all possible voting rules, which is the best?

Arrow proposed that we should first identify what we want out of the voting rule i.e. what properties should be satisfied. The best voting rule will then be the one that satisfy all of them. Those properties are:

1. Decisive/Unrestricted domain

All preferences of all voters should be accounted for and there should always be a winner and there shouldn't be more than one winner.

2. Pareto Principle

If all voters rank XX above YY and XX is on the ballot, YY should not be the outcome.

3. Non-dictatorship

No single voter's choice should decide the outcome.

4. Independence of irrelevant alternatives

Given a voting rule and voter's ranking, if XX is the winner, then if we remove YY from the ballot as it was not the winning choice (irrelevant), XX should still win i.e. independent from an irrelevant choice. To give an example, in the plurality rule example above, if option ZZ was removed and all those who chose ZZ as their first choice now chooses YY, making YY the winning choice with 60%. Politically speaking, ZZ is a spoiler. Even though ZZ was not going to win in either cases, it ended up determining the outcome. This happens in democratic elections several times. This property serves to rule out spoilers.

Plurality rule is vulnerable to spoilers and hence violates the independence property. Majority rule, satisfies the independence property i.e. if XX beats each of the other choices, it continues to do so if one of the choices is dropped. But majority rule does not satisfy the decisiveness property i.e it doesn't always produce a winner. E.g. in the following table of ranked choices, YY beats ZZ by a majority (68% to 32%), XX beats YY by a majority (67% to 33%) and ZZ beats XX by a majority (65% to 35%) - so there is no option which beats the other two. This is called Condorcet's Paradox.

35%33%32%
XYZ
YZX
ZXY

Arrow tried to find a voting rule that satisfies all the properties but eventually led to the conclusion that there is no voting rule that satisfies all 4 properties!

The name of the theorem is itself a source of pessimism: if something is "impossible", its pretty hard to accomplish. This theorem prompts the question: Given that no voting rule satisfies all properties, which rule satisfies them most often? One plausible answer is that in majority voting, if one particular class of ranking (e.g. Z>Y>XZ>Y>X) is removed with high probability of it not occurring, then majority rule will always have an outcome. In this case, majority rule does not violate the decisive property.

There is another theorem called the domination theorem. It states that for any voting rule that differs from majority rule, if it works well for a particular class of rankings, then majority rule must also work well for that class. Furthermore, there must be some other class of rankings for which majority rule works well and the voting method we started with does not. Whenever another voting rule works well, majority rule must work well too, and there will be cases where majority rule works well and the other voting rule does not.

This applies only if there is a possibility of identifying a class of ranking that is highly unlikely to occur. In case of DAOs, the question arises who is responsible for identifying and eliminating such a class of ranking for each proposal. Simply eliminating the least voted class of ranking results into utter neglect of minority.

Gibbard–Satterthwaite Theorem

Gibbard-Satterthwaite's theorem is applicable on ranked choice voting that chooses a single winner. It follows from Arrow's impossibility theorem. For every voting rule, one of the 3 things must hold:

  1. There is a dictatorship i.e. one voter's choice determines the outcome OR
  2. There are only two choices (in ballot) and hence only two possible outcome OR
  3. Tactical voting is possible i.e. there exist some strategy where a voter's ranked choice does not show their sincere opinion but gives the outcome they want.

Borda count: For the ranked choice ballot of each voter with nn options, assign n1n-1 points to the top option, n2n-2 to the second option, ... and 00 to the last option. Option with the most point is the winner.

To demonstrate the theorem, consider 3 voters AA, BB & CC and 4 options WW, XX, YY & ZZ and their ranked preference is as follows:

VoterChoice 1Choice 2Choice 3Choice 4
AliceWXYZ
BobYXZW
CarolYXZW

Based on Borda's count (WW: 3, XX: 6, YY: 7, ZZ: 2), YY is the winner. But if Alice changes its ballot as follows:

VoterChoice 1Choice 2Choice 3Choice 4
AliceXWZY
BobYXZW
CarolYXZW

From Borda count (WW: 2, XX: 7, YY: 6, ZZ: 3), XX is the winner and Alice's preference of XX over YY is still maintained. We can say that there exists a strategy where Borda count is manipulable.

Conclusion

Before designing any governance mechanism for DAOs, it is extremely important to understand that on-chain voting is a great tool but it does not solve the inherent problems in social choice theory. We also want to experiment with new systems but first, base our work on decades of research that have already been proven to work or not work. This article gives an overview of why ranked choice voting is complex to implement and even though most DAOs are currently opting for single choice voting, it is also prone to manipulation.

Most DAOs allow the voters to weigh the preference by either using more tokens or time-locking tokens (conviction voting). This is limited to putting the weight towards one option in single choice voting. Ranked choice voting is complex to begin with and introducing weights can potentially add more complexities and result in unforeseen outcomes. As shown in Gibbard-Satterthwaite theorem, Borda count is manipulable. And adding weights will open up more possibilites to game the system. But nonetheless, a great domain to research and experiment!

Timofey Yaluhin

Elliptic curves form a basic building block for all kinds of complex cryptographic machinery: digital signature schemes, key exchange mechanisms, zero knowledge proofs, multi-party computation, etc.

While all curves have a similar mathematical structure they can have wildly different properties in terms of security, performance, and supported arithmetic. With the increasing adoption of zero-knowledge cryptography, finding and exploiting such differences becomes increasingly prominent. Thus, the search for new elliptic curves is an active area of research in cryptography. The goal is to find curves that offer higher security, more efficient arithmetic operations, and are widening the scope of cryptographic applications.

This post goes over different methods for constructing elliptic curves, some potential applications, and some practical consideration for application-specific curve development. The reader is assumed to have a basic understanding of elliptic curve cryptography. If not consider checking elliptic curves cheat-sheet first.

Why search for new curves?

As with many things in modern cryptography, it is the rise of blockchains that sparked so many innovations related to elliptic curves as well as zero-knowledge cryptography, which subsequently pushed even more researchers to actively search for new elliptic curves. The applications described here would therefore be closely related to Web3 and ZK domains.

Platform-constraint arithmetic circuits

In ZK systems computation is expressed as arithmetic circuits that in turn perform their operations on a finite field Fr\mathbb{F}_r. This field corresponds to a scalar field of an elliptic curve whose base field is then used by the verifier in the proof verification algorithm. A verifier can be a person whom you need to prove some statement, but more commonly the verifier would be a smart contract. Blockchains that host these contracts usually support a fairly limited number of elliptic curves. Ethereum for example only has a precompiled contract for BN256. This can become a significant limitation when an in-circuit computation itself contains elliptic curve operations. Think of signature verification; checking that encrypted message has some properties, or even verifying another SNARK aka recursive proofs composition, which we discuss later.

An example to note is related to the StarkNet platform and Cairo language. The core technology powering these two is STARKs (no surprise). What's interesting is that, unlike other proof systems, STARKs only require a small prime field to operate, so researchers at Starkware invented a special STARK curve that has a very small prime field - 64 bytes. As a result, implementing cryptographic schemes over the standard curves (e.g. ECDSA over Secp256k1) would be wasteful. Unsatisfied with the status quo Mikerah from HashCloak resolved to find a new Cairo-friendly curve named Starkjub.

The solution to this kind of problem is quite simple, in fact, it's the oldest trick in the book. One can pick another curve EE' whose base field matches the scalar field of a curve EE used by the verifier. This offers a great alternative to simulating foreign fields with available (unfriendly) one, referred to as non-native arithmetic. Commonly, curves found with such intent have a twisted Edwards form. They are defined over a particular form of equation, ax2+y2=1+dx2y2ax^2 + y^2 = 1 + dx^2\cdot y^2, and are known for their efficient point addition. Many such curves were found in recent years. Some of them are given cute names like JubJub (Ed-on-BLS12-381) and funny pictures to be more memorable.

JubJub (left) and Bandersnatch (right)

Application-constraint arithmetic circuits

For some applications the aforementioned curve substitution is impossible. Think of a cross-chain bridge where a smart contract on the destination chain needs to verify signatures of the source blockchain. Another example is identity-based encryption (IBE) like the one used in the tlock scheme to achieve practical time-lock encryption facilitated by Drand threshold network. Recently I've set to make such encryption verifiable and quickly realized that performing arithmetic on BLS12-381, which Drand operates on, is very inefficient with existing tools. Search for a better alternative brought me into this rabbit hole.

The discovered solution is the opposite of the one we've just discussed. Here a curve must be picked, whose scalar field matches the projective curve's base field. Depending on the proving system, there can be another important requirement: systems that rely on KZG commitment scheme, such as Groth'16, PLONK require pairing-friendly curves to operate. The reason is that KZG proof verification algorithm requires elliptic curve point multiplication which is not allowed in traditional ECC. However, when both points are from pairing-friendly curve G1\mathbb{G}_1 and G2\mathbb{G}_2 and there exists a bilinear map between their respective groups of points, then it's possible to map these points into a target group GT\mathbb{G}_T point, which acts as a product G1<