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.
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.
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:
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.
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.
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 \ U
S
H
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.
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.
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!
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.
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] in the finite field of integers modulo 337. This domain forms a multiplicative group with 8=23 elements. The elements of this group are powers of ω=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]. 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 0, the order of the group is exactly one less than the number of elements in the field. Fields Fp that satisfy this condition are referred to as p−1 smooth.
An exemplary prime is the BabyBear prime p=231−227+1. The largest multiplicative group in the BabyBear field has p−1=227⋅3⋅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=231−1? Unfortunately, 231−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.
Instead of generating subgroup elements as simply powers of a generator g, we move from a point (xi,yi) on the circle to the point:
(xi+1,yi+1)=(gx⋅xi−gy⋅yi,gx⋅yi+gy⋅xi)
It turns out that the number of points lying on the circle, defined over the Mersenne prime 231−1, is quite large (231). One can generate all 231 group elements by starting with (x0,y0)=(1,0) and applying the generator (gx,gy)=(2,1268011823) using the law above.
For the circle FFT/FRI, we need two more group operations: the group squaring map π and the inversion map J.
Squaring is the quadratic map defined as
π(x,y):=(x,y)⋅(x,y)=(x2−y2,2⋅x⋅y)=(2⋅x2−1,2⋅x⋅y)
This transformation reduces the set size by half.
Inverse is given by the degree-one map
J(x,y):=(x,−y)
This operation maps each point (x,y) to its reflection (x,−y).
Map J is an involution, i.e., J(J(P))=P. Maps J and π commute, i.e., π(J(P))=J(π(P)) for every P∈C(Fp).
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 n-th roots of unity, i.e. {1,ω,ω2,…,ω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 g and square it logn−1 times to create a subgroup Gn−1. Then, we create two twin cosets, which are formed by taking an element Q that is not in Gn and creating two disjoint sets: Q⋅Gn−1 and Q−1⋅Gn−1. The union of these sets forms the circle FFT domain containing 2n 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 f is a linear combination f(x)=feven(x)+x⋅fodd(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 x projection of each point. This is justified by the use of the inverse map when performing a decomposition f(x,y)=f0(x)+y⋅f1(x) such that:
I have modified the notation to demonstrate how in practice we treat polynomials f,f0,f1 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) 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 x coordinate.
In later steps, we continue to halve the domain using the univariate squaring map π(x)=2⋅x2−1. This is analogous to squaring the k-th root of unity such that ω2k=ωk. The even-odd decomposition (in the original notation) fj(x)=fj+1(π(x))+x⋅fj+1(π(x)) — now looks like this:
f0(π(x))=2f(x)+f(−x)f1(π(x))=2⋅xf(x)−f(−x)
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).
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 d over the domain D.
Here, being "close" is defined by the relative Hamming distance δ such that the number of points where the committed vector and the codeword disagree is at most δ⋅∣D∣. The distance δ is such that δ∈(0,1−ρ) where 0<ρ<1 is the rate of the Reed-Solomon code. In turn, the rate ρ is defined by the blow-up factor 2B,B≥1 so that ρ=2−B. Finally, the domain size is ∣D∣=2n+B where 2n 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=4, so the rate is ρ=0.25. The worst possible distance is δ=0.5, so for a vector with 1024 elements, the codeword over a 2B+n=4096 sized domain can disagree on at most half of the points. In practice, δ 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,21−ρ].
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: θ∈[21−ρ,1−ρ]. HAB23
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, 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), so whenever a polynomial has y2, it's replaced by 1−x2.
For a given proximity parameter θ∈(0,1−ρ), the interactive oracle proof of a function f:X→FD (mapping the committed vector) being θ-close to the circle codeword C consists of r rounds of a commit phase and a subsequent query phase, which are as follows.
For each j=1,…,r, P decomposes gj−1 into "even" and "odd" parts; sends a commitment [gj] to V
In the last round, P sends gr+1 in plain.
1. P decomposes f into f=g+λ⋅vn and sends λ to V
We start with the extended domain coset Dn+B. First, we want to find the component of f that is aligned with vn. This can be done using vector projection: given two functions (or vectors) f and vn, the projection of f onto vn is given by:
projvn(f)=⟨vn,vn⟩D⟨f,vn⟩D⋅vn
Note: angle brackets denote the inner product ⟨vn,f⟩D=∑x∈Dvn(x)⋅f(x).
Taking λ as the magnitude of this projection will ensure that λ⋅vn is the part of f that lies along vn
λ=⟨vn,vn⟩D⟨f,vn⟩D
The vanishing polynomial vn has an alternating behavior over the domain D, e.g., if D has size N=2n, then vn alternates as (1,−1,1,−1,…). This significantly simplifies the inner product calculations as vn(x)∈{1,−1}, each term vn(x)2=1 so
⟨vn,vn⟩D=x∈D∑1=∣D∣=N
Knowing λ, we can now find g, which represents the component of f that is orthogonal to vn
g=f−λ⋅vn
This ensures that g lies entirely in the FFT space LN′(F), orthogonal to vn. This is because the inner product ⟨g,vn⟩D=0, making g and vn orthogonal by construction.
3. For each j=1,…,r, P decomposes gj−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) and use the full squaring π(x,y) and inverse J(x,y) maps. The inverse map transformation allows us to identify points (x,y) and their reflection (x,−y) so we can treat them as a single point x on the x-axis in subsequent rounds. The squaring map π transforms the domain Dj−1 into Dj by effectively halving the space of points:
1. V samples s≥1 queries uniformly from the domain D
For each query Q, 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=Q is transformed through several rounds, resulting in a series of points Qj in different domains Dj:
Qj=πj(Qj−1)
2. For each j=1,…,r, V asks for the values of the function gj at a query point Qj and its reflection Tj(Qj)
Given the commitment [gj], as in oracle access, 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))
where at j=1, Tj=J and for j>1, Tj(x)=−x.
3. 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 gj from gj−1 are consistent.
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 z. 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 z. We fix this with another instance of quotienting—DEEP quotienting.
We construct DEEP quotients with a single-point vanishing function vz in the denominator to show that a certain polynomial, say a trace column t, evaluates to the claim yj at z, i.e., vzt−t(z).
In classical STARKs, vz is simply a line function X−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
vzt−t(z)=Re(vzt−t(z))+i⋅Im(vzt−t(z))
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
In the ethSTARK paper, the prover does batching using L random weights γ1,…,γL provided by the verifier (affine batching). Here, the prover uses powers of a single random weight γ1,…,γL (parametric batching).
Computing Q 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
where gˉ=∑k=0L−1γk⋅gk and vˉz=∑k=0L−1γk⋅gk(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.
In circle STARK, work is done over the finite field Fp and its extension E=Fpk where k is the extension degree. For Fp, we choose M31, but any other p+1 smooth prime will suffice. The extension field 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), the field that results from F by extending it with the imaginary unit i. Note that i may trivially be contained in some fields, e.g., if −1≡4mod5 then i in F5 is both 4=2 and 3 (since 23mod5≡4). For those fields where this isn't the case, such as F3, we can devise a quadratic extension, F9={a+bi∣a,b∈F3}, which extends the original field in the same way complex numbers extend rationals.
FYI
A more common notation is F[X]/(X2+1), which means forming a field extension where X2+1=0. This results in a new field with elements of the form a+bi where a,b∈F and i is a root of X2+1, such that i2=−1.
Trace values are over the base field and trace domain are points over the base field C(F).
The evaluation domain consists of points over the base field C(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.
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.
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.
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.
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) 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 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) over the boolean domain {0,1}v (the boolean hypercube), polynomial operations such as addition, multiplication, and evaluation can be performed using only the evaluations of P 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. Every function f and vector a mapping from {0,1}v→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) as an "extension" of a, as MLE(a) "begins" with a 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.
The Sumcheck protocol allows a proverP to convince a verifierV that the sum of a multivariate polynomial over boolean inputs [xi∈{0,1}] is computed correctly.
H:=(x1,⋯,xv)∈{0,1}∑g(x1,x2,⋯,xv)
Sumcheck does not require 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 can choose to either request the polynomial and evaluate it directly or perform an oracle query, i.e., outsource the evaluation to P via a polynomial commitment scheme (PCS).
This is an interactive protocol: If ℓ is the number of variables in g, then ℓ 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.
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 d. Note that many of today's variations of GKR allow for more arbitrary topologies just as well.
The arithmetic circuit C encodes logic with addition and multiplication gates to combine values on the incoming wires. Accordingly, functions addi and muli are gate selectors that together constitute the wiring predicate of layer i.
We encode wire values on a boolean hypercube {0,1}n, creating multi-linear extensions Wi(x) for each layer i. The output is in W0(x), and inputs will be encoded in Wd(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 a at layer i has two unique in-neighbors, namely in1(a) and in2(a).
addi(a,b,c)={10 if (b,c)=(in1(a),in2(a)) otherwise
and muli(a,b,c)=0 for all b,c∈{0,1}ℓi+1 (the case where gate a is a multiplication gate is similar), T23a. Selector MLEs are sparse, with at most 22ℓ non-zero elements out of 0,13ℓ.
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:
A few things to note here: First, notice how gate selectors are indexed—this aligns with the convention that selectors at layer i determine how values from the next layer i+1 are combined. Notice also that the i-layer sumcheck is over boolean inputs of size ℓi+1, i.e., the number of gates in the next layer.
P sends the output vector ω and claims that ω~=W0.
V sends random r0∈E and computes m0:=ω~(r0).
P and V apply sumcheck on the relation between W0 and W1 (using fr0 for the summand)
y,z∈{0,1}ℓ1∑fr0(y,z)=?m0
P and V reduce two claims Wi+1(b) and Wi+1(c) to a single random evaluation/combination mi.
P and V apply sumcheck on the reduced relation mi, alternating steps 4-5 for d−1 more times.
V checks that Wd is consistent with the inputs vector x.
1. P sends the output vector ω and claims that ω~=W0
First, the P has to evaluate the circuit at the given input vector 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 ω as a function D:{0,1}ℓ0→F mapping output gate labels to output values, 2ℓ0 of them in total. The gate labels are the vertices of the boolean hypercube; for example, for ℓ0=2, the 4 output labels are 00, 01, 10, 11.
In practice, though, P and V work with polynomials, not functions, so they have to compute multilinear extension ω~ from the vector ω. Same goes for the inputs x→Wd. However, since computation on MLEs can be performed over evaluations, in practice no additional computation, like interpolation/IFFT, is even required!
2. V sends random r0∈E and computes m0:=ω~(r0)
V picks a random challenge r0∈E. Crucially, the soundness error of the sumcheck protocol is inversely proportional to the size of the field from which challenges ri are drawn (due to the Schwartz-Zippel lemma), T23a. That's why in practice for challenge values, we use an extension field E:=Fpk where k is the extension degree.
For example, say we opt for M31 as a base field Fp whose order is ∣Fp∣=p=231−1 elements. Then, the probability of soundness error in sumcheck for an ℓ-variate summand polynomial is 231−1ℓ, which is too large, certainly for the non-interactive setting. Instead, we choose challenges from QM31—the extension field of M31 with k=4. Now, for any reasonable ℓ, 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 cannot yet trust ω~ 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 and V apply sumcheck on the relation between W0 and W1
For the first layer, P and V run a sumcheck on Equation (1) with i=0, between W0 and W1, with x fixed to r0.
In the first round of sumcheck, P uses r0 to fix the variable x. In the remaining two rounds, V picks b,c∈E randomly to fix the variables y and z, respectively. At the end of the sumcheck, from V's point of view, the relation on the sum (Equation 1) is reduced to a simple check that the summand fr0(b,c) evaluates to m0.
To compute fr0(b,c), V must compute addr0(b,c) and mulr0(b,c) locally. Remember that these depend only on the circuit's wiring pattern, not on the values. Since fr0 is recursive, V also asks P for the W1(b) and W1(c) values and computes fr0(u,v) to complete the sumcheck protocol.
In this way, P and V reduce a claim about the output to two claims about values in layer 1. While P and V could recursively invoke two sumcheck protocols on W1(b) and W1(c) for the layers above, the number of claims and sumcheck protocols would grow exponentially in d. XZZ19
4. P and V reduce two claims Wi+1(b) and Wi+1(c) to a single random evaluation/combination mi
To avoid an exponential blow-up in complexity, P and 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 W1(b) and W1(c), V picks random weights αi,βi∈E and computes the RLC as
mi=αiW1(b)+βiW1(c)
In the next step, V would use mi as the claim for the i-th layer sumcheck.
5. P and V apply sumcheck on the reduced relation mi, alternating steps 4-5 for d−1 more times
For the layers i=1,…,d−1, P and V would execute the sumcheck protocol on Equation (2) instead of Equation (1)
At the end of each layer's sumcheck protocol, V still receives two claims about Wi+1, computes their random linear combination, and proceeds to the next layer above recursively until the input layer. XZZ19
6. V checks that Wd is consistent with the inputs vector x
At the input layer d, V receives two claims Wd(bi=d) and Wd(ci=d) from P. Recall that Wd is claimed to be a multilinear extension of the input vector x.
If V knows all the inputs in clear, they can compute Wd and evaluate it at bi=d and ci=d themselves.
Alternatively, if V doesn't know all inputs and is instead given an input commitment [wd] for succinctness or zero-knowledge reasons, then V queries the oracle for evaluations of Wd at bi=d and ci=d.
Ultimately, V outputs accept if the evaluated values are the same as the two claims; otherwise, they output reject. XZZ19
Let C:F→E be a layered circuit of depth d with n:=∣x∣ input variables, having Si gates in layer i. Naturally, ∣C∣:=∑i=0dSi is the total number of gates in the circuit, i.e., the circuit size.
Rounds:O(d⋅log∣C∣).
P time:O(∣C∣⋅log∣C∣)
V work:O(n+d⋅log∣C∣+t+S0)≈O(n+d⋅log∣C∣) for 1 output.
Communication:O(S0+d⋅log∣C∣) field elements.
Soundness error:O(∣E∣d⋅log∣C∣)
The GKR protocol consists of one execution of the sumcheck protocol per layer. Therefore, the total communication cost (proof size) is O(dlog∣C∣) field elements. The accumulated soundness error is O(∣E∣d⋅log∣C∣) due to the Schwartz-Zippel lemma. T23a
The prover must first evaluate the circuit, which takes time ∣C∣. It must also compute addi and muli at each layer, which, if done trivially, induces logarithmic overhead log∣C∣. The resulting time for the prover is O(∣C∣⋅log∣C∣). XZZ19
The verifier's work is O(n+dlog∣C∣+t+S0), where S0 is the number of outputs of the circuit, t denotes the optimal time to evaluate all addi and muli, and the n term is due to the time needed to evaluate Wd. XZZ19
Part 2 will cover modifications and techniques that result in O(∣C∣) prover.
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 f from Equation (1) and a claim W in zero-knowledge, P generates a random polynomial γ with the same variables and individual degrees as f, commits to γ, and sends V a claim
Γ=∑x1,…,xℓ∈{0,1}ℓγ(x1,…,xℓ)V picks a random number ρ, and together with P executes the sumcheck protocol on
In the last round of this sumcheck, P opens the commitment to γ at γ(r1,…,rℓ), and the verifier computes f(r1,…,rℓ) by subtracting ρ⋅γ(r1,…,rℓ) from the last message, and compares it with P's original claim.
Chiesa et al. showed that as long as the commitment and opening of γ are zero-knowledge, the protocol is zero-knowledge.
Let W be a multilinear polynomial over F with logn variables. The following is the description of a simple one-round subroutine from GKR08 with communication cost O(logn) that reduces the evaluation of W(b) and W(c) to the evaluation of W(r) for a single point r∈E.
P interpolates a unique line ℓ passing through b and c, such that ℓ(0)=b and ℓ(1)=c. The line can be formally defined as ℓ(t)=b+t⋅(c−b) using the point-slope form. The points b and c are tuples with v elements for a v-variate polynomial W.
By substituting b and c−b into ℓ(t), we get the tuple ℓ(t)=(ℓ0(t),⋯,ℓv(t)) defined by v linear polynomials over t. P sends a univariate polynomial q of degree at most ki+1 that is claimed to be Wi+1∘ℓ, the restriction of Wi+1 to the unique line ℓ.
q(t):=(W∘ℓ)(t)=W(ℓ0(t),⋯,ℓlogn(t)))
V interprets q(0) and q(1) as P's claims for the values of W(b) and W(c). V also picks a random point r∗∈F, sets r=ℓ(r∗), and interprets q(r∗) as P's claim for the value of W(r). See the picture and an example from T23a (Section 4.5.2).
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.↩
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.
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.
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.
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.
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.
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?
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.
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.
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.
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.
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.
A transactiont has publicly visible and immutable sizest. The creator of the transaction is responsible for specifying a bidbt per unit size, publicly indicating to pay upto st⋅bt. A block is an ordered sequence of transactions and each block has a cap on the number of included transactions called maximum block size, C (capacity). A Mempool is a list of outstanding transaction waiting to be included in the block. M is miner's current mempool.
Valuationvt is the maximum per size value the transaction inclusion in a block for a creator is (vt is private to the creator) whereas bt 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,...,Bk−1 (History) is the sequence of blocks in the current longest chain. B1 being the genesis block and Bk−1 the most recent block.
Allocation rule is a vector-valued function x from the on-chain history H and mempool M to a 0-1 value xt(H,M) for each pending transaction t∈M.
A value of 1 for xt(H,M) indicates transaction t’s inclusion in the current block Bk; a value of 0 indicates its exclusion.
Bk=x(H,M) is the set of transactions for which xt(H,M)=1.
A feasible allocation rule is a set of transactions T such that:
t∈M∑st⋅xt(H,M)≤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.
Burning rule is a function q, indicating the amount of money burned by the creator of transaction t∈Bk.
qt(H,Bk) 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) where x is a feasible allocation rule, p is payment rule and q is burning rule.
For a TFM (x,p,q), on-chain history H and mempool M, the utility of the originator of the transaction t∈/M with valuation vt and bid bt is:
ut(bt):=(vt−pt(H,Bk)−qt(H,Bk))⋅st
if t is included in Bk=x(H,M(bt)), 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.
For a TFM (x,p,q), on-chain history H, mempool M, fake transactions F, and choice Bk⊆M∪F of included transactions (real and fake), the utility of a myopic miner (a miner concerned only with the current block) is:
where μ 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=∅
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.
In OCA, each creator of transaction t agrees to submit t with on-chain bid bt while transferring τ⋅st to the miner off-chain; the miner in turn agrees to mine a block comprising the agreed upon transactions of T.
A TFM is OCA-proof if, for every on-chain historyH, there exists an individually rational bidding strategyσHsuch that, for every possible setTof outstanding transactions and valuationsv, there is no OCA under which the user's utility of every transaction and the miner's utility is strictly higher than in the outcomeBk=x(H,M(σH(v)))with on-chain bidsσ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.
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].
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)
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:
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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 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 X, Y & Z, if 40% voters liked X best i.e. ranked it first, 35% liked Y best and 25% liked Z best, then X wins, even though it is short of an over-all majority (greater than 50%).
40%
35%
25%
X
Y
Z
In majority rule, the winning option is the option that is preferred by a majority to each other option. E.g. for 3 options X, Y & Z, if 40% voters rank X>Y>Z, 35% rank Y>Z>X and 25% rank Z>Y>X, the winner is Y because majority of voters (35% + 25% = 60%) prefer Y to X and a majority (40% + 35% = 70%) prefer Y to Z.
40%
35%
25%
X
Y
Z
Y
Z
Y
Z
X
X
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:
Given a voting rule and voter's ranking, if X is the winner, then if we remove Y from the ballot as it was not the winning choice (irrelevant), X should still win i.e. independent from an irrelevant choice. To give an example, in the plurality rule example above, if option Z was removed and all those who chose Z as their first choice now chooses Y, making Y the winning choice with 60%. Politically speaking, Z is a spoiler. Even though Z 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 X 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, Y beats Z by a majority (68% to 32%), X beats Y by a majority (67% to 33%) and Z beats X 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%
X
Y
Z
Y
Z
X
Z
X
Y
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>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'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:
There is a dictatorship i.e. one voter's choice determines the outcome OR
There are only two choices (in ballot) and hence only two possible outcome OR
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 n options, assign n−1 points to the top option, n−2 to the second option, ... and 0 to the last option. Option with the most point is the winner.
To demonstrate the theorem, consider 3 voters A, B & C and 4 options W, X, Y & Z and their ranked preference is as follows:
Voter
Choice 1
Choice 2
Choice 3
Choice 4
Alice
W
X
Y
Z
Bob
Y
X
Z
W
Carol
Y
X
Z
W
Based on Borda's count (W: 3, X: 6, Y: 7, Z: 2), Y is the winner. But if Alice changes its ballot as follows:
Voter
Choice 1
Choice 2
Choice 3
Choice 4
Alice
X
W
Z
Y
Bob
Y
X
Z
W
Carol
Y
X
Z
W
From Borda count (W: 2, X: 7, Y: 6, Z: 3), X is the winner and Alice's preference of X over Y is still maintained. We can say that there exists a strategy where Borda count is manipulable.
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!
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.
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.
In ZK systems computation is expressed as arithmetic circuits that in turn perform their operations on a finite field Fr. 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 E′ whose base field matches the scalar field of a curve E 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+dx2⋅y2, 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.
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 and G2 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 point, which acts as a product