Block stuffing is a type of attack in blockchains where an attacker submits
transactions that deliberately fill up the block’s gas limit and stall other
transactions. To ensure inclusion of their transactions by miners, the
attacker can choose to pay higher transaction fees. By controlling the
amount of gas spent by their transactions, the attacker can influence the number
of transactions that get to be included in the block.
To control
the amount of gas spent by the transaction, the attacker utilizes a special
contract. There is a function in the contract which takes as input the amount of
gas that the attacker wants to burn. The function runs meaningless
instructions in a loop, and either returns or throws an error when the desired
amount is burned.
For example let’s say that the average gas price has been 5 Gwei in the last
10 blocks. In order to exert influence over the next block, the attacker needs to
submit transactions with gas prices higher than that, say 100 Gwei. The higher
the gas price, the higher the chance of inclusion by miners.
The attacker can choose to divide the task of using 8,000,000 gas—current
gas limit for blocks—into as
many transactions as they want. This could be 80 transactions with
100,000 gas expenditure, or 4 transactions with 2,000,000 gas expenditure.
Deciding on how to divide the task is a matter of maximizing the chance of
inclusion, and depends on the factors outline below.
Miners’ strategy for selecting transactions
Miners want to maximize their
profit by including transactions with highest fees. In the current PoW
implementation of Ethereum, mining the block takes significantly more time
than executing the transactions. So let’s assume
all transactions in the pool are trivially executed as soon as they arrive
and miners know the amount of gas each one uses.
For miners, maximizing profit is an
optimum packing problem.
Miners want to choose a subset of the transaction pool that gives them
maximum profit per block. Since there are at least tens of thousands of
transactions in the pool at any given time, the problem can’t be solved by
brute-forcing every combination. Miners use algorithms that test a
feasible number of combinations and select the one giving the highest reward.
A block stuffer’s main goal is to target the selection process by
crafting a set of transactions that has the highest chance of being picked
up by miners in a way that will deplete blocks’ gas limits.
They can’t devise a 100% guaranteed strategy since each miner
can use a different algorithm, but they can find a sweet spot by testing out the
whole network.
(In a PoS system, our assumptions would be wrong since executing
transactions is not trivial compared to validating blocks. Validators would
need to develop more complex strategies depending on the PoS implementation.)
The transactions the attacker wants to stall:
It could be so that the
attacker wants to stall transactions with a specific contract. If the
function calls to that contract use a distinctively high amount of gas, say
between 300,000 and 500,000, then the attacker has to stuff the block in a
way that targets that range.
For example, the attacker can periodically submit $n$ transactions
$\{T_1, T_2,\dots, T_{n-1}, T_n\}$ with very high prices where
If the attacker is targeting transactions within a range of
$(R_\text{lower}, R_\text{upper})$, they can choose
the first $n-1$ transactions to deplete $8,000,000 - R_\text{upper}$ gas
in short steps, and submit $T_n$ to deplete the remaining $R_\text{upper}$
gas with a relatively higher price. Note that the revenue from including a
single transaction is
As gas usage decreases, the
probability of being picked up by miners decreases, so prices should increase
to compensate.
Example: Fomo3D
Fomo3D
is a gambling game where players buy keys from a contract and their money
goes into a pot. At the beginning of each round, a time counter is initiated
which starts counting back from 24 hours. Each bought key adds 30 seconds to the
counter. When the counter hits 0, the last player to have bought a key wins the
majority of the pot and the rest is distributed to others. The
way the pot is distributed depends on the team that the winner belongs to.
Key price increases with increasing key supply, which makes it harder and harder
to buy a key and ensures the round will end after some point. In time, the stakes
increase and the counter reduces to a minimum, like 2 minutes. At this
point, the players pay both high gas and key prices to be “it” and win the game.
Players program bots to buy keys for them, and winning becomes a matter of coding the
right strategy. As you can understand from the subject, the
first round was won through a block stuffing attack.
On August 22 2018, the address
0xa16…f85
won
10,469 ETH from the first round by following the strategy I outlined above. The
winner managed to be the last buyer in
block 6191896
and managed to stall
transactions with Fomo3D until block 6191909
for 175 seconds,
ending the round. Some details:
The user addresses above were scraped from the Ethereum transaction graph as being
linked to a primary account which supplied them with funds. The contract
addresses were scraped from 0-valued transactions sent from user addresses.
These have a distance
of 1, there may be other addresses involved with greater distances.
Below are details of the last 4 blocks preceding the end of the round. The rows
highlighted with yellow are transactions submitted by the attacker. The crossed
out rows are failed transactions. All transactions by the attacker were
submitted with a 501 Gwei gas price, and stuffing a single block costed around 4
ETH. The calls to buy keys generally spend around 300,000~500,000 gas, depending
on which function was called.
Below, you see the successfully stuffed
block 6191906.
Block 6191907 was a close call for the winner, because their transactions picked
up for the block did not amount up to 8,000,000 and the other transaction was a
call to Fomo3D by an opponent to buy keys. Note that it has a gas price of 5559
Gwei, which means either the bot or person who submitted the transaction was
presumably aware of the attack.
The transaction failed due to low gas limit, presumably due to a miscalculation
by the bot or the person.
Transactions in block 6191908 belonged to the attacker except for one irrelevant
transfer. This block is also considered successfully stuffed, since the
7,970,000 gas usage by the attacker leaves no space for a call to buy keys.
By block 6191909, the counter has struck zero—more like current UTC time
surpassed the round end variable stored in the contract—and any call to Fomo3D
would be the one to end the round and distribute the pot. And the first transaction
in the block is—wait for it—a call to Fomo3D to buy keys by the opponent
whose transaction failed a few blocks earlier, submitted with 5562 Gwei. So the
guy basically paid 1.7 ETH to declare the attacker the winner!
Another thing to note is that the attacker probably crafted the spender contract
to stop the attack when the round has ended, presumably to cut costs. So the 37,633
gas used by the contract are probably to call the Fomo3D contract to check
round status. All these point out to the fact that the attacker is an
experienced programmer who knows their way around Ethereum.
Here, you can see the details of the 100
blocks preceding the end of the round, with the additional information of ABI
calls and events fired in transactions.
Since the end of the first round, 2 more rounds ended with attacks similar to
this one. I didn’t analyze all of them because it’s too much for this post, but
here are some details if you want to do it yourselves.
A thing to note in the following rounds is that participation in the game
and amount of pot gradually decreased, presumably owing to the fact that
the way of beating the game has been systematized. Although anyone can attempt
such an attack, knowing how it will be won takes the “fun” factor out of it.
Credit: Although I’ve found previous instances of the term “block stuffing”
online, Nic Carter is the first
one to use it in
this context.
A bonding curve is a financial instrument proposed by Simon de la Rouviere
in his Mediumarticles. ETH is bonded in a smart contract to mint tokens, and unbonded to burn them. Every bonding and unbonding changes the price of the token according to a predefined formula. The “curves” represent the relationship between the price of a single token and the token supply. The result is an ETH-backed token that rewards early adopters.
An example supply versus price graph. The area below the curve is equal to the amount of ETH $E$ that must be spent to increase the supply from $S_0$ to $S_1$, or that is going to be received when $S_1-S_0$ tokens are unbonded.
Inside a transaction, the price paid/received per token is not constant and depends on the amount that is bonded or unbonded. This complicates the calculations.
Let’s say for an initial supply of $S_0$, we want to bond $T$ tokens which are added to the new supply $S_1=S_0+T$. The ETH $E$ that must be spent for this bonding is defined as
\[E = \int_{S_0}^{S_1} P\, dS\]
which is illustrated in the figure above. If one wanted to unbond $T$ tokens, the upper limit for the integral would be $S_0$ and the lower $S_0-T$, with E corresponding to the amount of ETH received for the unbonding.
Linear Curves
A linear relationship for the bonding curves are defined as
\[P(S) = P_0 + S I_p\]
where $P_0$ is the initial price of the token and $I_p$ is the price increment per token.
Bonding Tokens
Let us have $E$ ETH which we want to bond tokens with. Substituting $P$ into the integral above with the limits $S_0\to S_0+T$, we obtain $E$ in terms of the tokens $T$ that we want to bond:
\[E(S, T) = T P_0 + T I_p S + \frac{1}{2} T^2 I_p\]
where $S$ is the supply before the bonding. Solving this for $T$, we obtain the tokens received in a bonding as a function of the supply and ETH spent:
\[\boxed{T(S, E) = \frac{\sqrt{S^2I_p^2 + 2E I_p + 2 S P_0 I_p + P_0^2}-P_0}{I_p} - S.}\]
Unbonding Tokens
Let us have T tokens which we want to unbond for ETH. Unbonding $T$ tokens decreases the supply from $S_0$ to $S_0-T$, which we apply as limits for the above integral and obtain:
\[\boxed{E(S, T) = T P_0 + T I_p S - \frac{1}{2} T^2 I_p.}\]
Breaking Even in PoWH3D
PoWH3D is one of the applications of bonding curves with a twist: 1/10th of every transaction is distributed among token holders as dividends. When you bond tokens with $E$ ETH, you receive $9/10 E$ worth of tokens and $1/10 E$ is distributed to everybody else in proportion to the amount they hold.
This means you are at a loss when you bond P3D (the token used by PoWH3D). If you were to unbond immediately, you would only receive 81% of your money. Given the situation, one wonders when exactly one can break even with their investment. The activity in PoWH3D isn’t deterministic; nonetheless we can deduce sufficient but not necessary conditions for breaking even in PoWH3D.
Sufficient Bonding
Let us spend $E_1$ ETH to bond tokens at supply $S_0$. The following calculations are
done with the assumption that the tokens received
\[T_1 = T(S_0, 9E_1/10)\]
are small enough to be
neglected, that is $T_1 \ll S_0$ and $S_1 \approx S_0$. In other words, this only
holds for non-whale bondings.
Then let others spend $E_2$ ETH to bond tokens and raise the supply to $S_2$.
The objective is to find an $E_2$ large enough to earn us dividends and make us
break even when we unbond our tokens at $S_2$.
We have
\[S_2 = S_0 + T(S_0, E_2).\]
Our new share of the P3D pool is $T_1/S_2$ and the dividends we earn from
the bonding is equal to
$E^{\text{suff}}_2$ can be obtained from the source of this page in JavaScript from
the function sufficient_bonding. The function involves many power
and square operations and may yield inexact results for too high values of
$S_0$ or too small values off $E_1$, due to insufficient precision of the
underlying math functions. For this reason, the calculator is disabled
for sensitive input.
$S_0$ versus $E^{\text{suff}}_2$ for $E_1 = 100$.
The relationship between the initial supply and sufficient bonding is roughly
quadratic, as seen from the graph above. This means that the difficulty of
breaking even increases quadratically as more people bond into P3D. As interest in
PoWH3D saturates, dividends received from the supply increase decreases
quadratically.
Logarithmic plot of $S_0$ versus $E^{\text{suff}}_2$ for changing values of $E_1$.
The relationship is not exactly quadratic, as seen from the graph above. The
function is sensitive to $E_1$ for small values of $S_0$.
Sufficient Unbonding
Let us spend $E_1$ ETH to bond tokens at supply $S_0$ and receive $T_1$ tokens.
Then let others unbond $T_2$ P3D to lower the supply to $S_2$. The objective is to find a $T_2$ large enough to earn us dividends and make us break even when we unbond our tokens at $S_2$. We have
\[S_2 = S_0 - T_2.\]
Our new share of the P3D pool is $T_1/S_2$ and the dividends we earn from the bonding is equal to
$T^{\text{suff}}_2$ can be obtained from the function sufficient_unbonding.
$S_0$ versus $T^{\text{suff}}_2$ for $E_1 = 100$.
The relationship between $S_0$ and $T^{\text{suff}}_2$ is linear and insensitive to $E_1$. Regardless of the ETH you invest, the amount of tokens that need to be unbonded to guarantee your break-even is roughly the same, depending on your entry point.
Calculator
Below is a calculator you can input $S_0$ and $E_1$ to calculate $E^{\text{suff}}_2$ and $T^{\text{suff}}_2$.
$S_0$
$E_1$
$E^{\text{suff}}_2 $
$T^{\text{suff}}_2 $
For the default values above, we read this as:
For 100 ETH worth of P3D bonded
at 3,500,000 supply, either a bonding of ~31715 ETH
or an unbonding of ~3336785 P3D
made by other people is sufficient to
break even.
In order to follow these statistics, you can follow
this site.
Conclusion
Bonding curve calculations can get complicated because the price paid per token depends on the amount of intended bonding/unbonding. With this work, I aimed to clarify the logic behind PoWH3D. Use the formulation and calculator at your own risk.
The above conditions are only sufficient and not necessary to break even. As PoWH3D becomes more popular, it gets quadratically more difficult to break even from a supply increase. PoWH3D itself doesn’t generate any value or promise long-term returns for its holders. However every bond, unbond and transfer deliver dividends. According to its creators, P3D is intended to become the base token for a number of games that will be built upon PoWH3D, like FOMO3D.
When utilizing Galerkin-type solutions for
IBVPs, we often
have to compute integrals using numerical methods such as
Gauss quadrature. In
such a solution, we solve for the values of a function at mesh nodes, whereas
the integration takes place at the quadrature points. Depending on the case,
we may need to compute the values of a function at mesh nodes, given their
values at quadrature points, e.g. stress recovery for mechanical problems.
There are many ways of achieving this, such as
superconvergent patch recovery.
In this post, I wanted to document a widely used solution which is easy to
implement, and which is used in research oriented codebases such as
FEAP.
L2 Projection
Given a function $u \in L^2(\Omega)$, its projection into a finite element space
$V_h\subset L^2(\Omega)$ is defined through the following optimization
problem:
There is a unique solution to the problem since $\Pi(\cdot)$ is convex. Taking
its variation, we have
\(\begin{equation}
D \Pi(u_h) \cdot v_h = \langle u_h-u, v_h \rangle = 0
\end{equation}\)
for all $v_h\in V_h$. Thus we have the following variational formulation
Find $u_h\in V_h$ such that
\[\begin{equation}
\langle u_h,v_h\rangle = \langle u, v_h\rangle
\end{equation}\]
are our bilinear and linear forms respectively. Substituting FE
discretizations $u_h = \sum_{J=1}^{\nnode} u^JN^J$ and
$v_h = \sum_{I=1}^{\nnode} v^IN^I$, we have
Thus L2 projection requires the solution of a linear system
\[\boldsymbol{M}\boldsymbol{u}=\boldsymbol{b}\]
which depending on the algorithm used, can have a complexity of at least
$O(n^2)$ and at most $O(n^3)$.
Lumped L2 Projection
The L2 projection requires the solution of a system which can be
computationally expensive. It is possible to convert the
matrix—called the mass matrix in literature—to a diagonal
form through a procedure called lumping.
since $\sum_{J=1}^{\nnode} N^J = 1$.
Substituting the lumped mass matrix allows us to decouple the linear system of
equations in \eqref{eq:projectionsystem1} and instead write
\[\begin{equation}
m^I u^I = b^I
\end{equation}\]
for $I=1,\dots,\nnode$. The lumped L2 projection is then as simple as
This results in a very efficient algorithm with $O(n)$ complexity.
Conclusion
Lumped L2 projection is a faster working approximation to L2 projection that is
easy to implement for quick results. You can use it when developing a solution
for an IBVP, and don’t want to wait too long when debugging, while not
forgetting that it introduces some error.
where $\boldsymbol{B}^I = \nabla N^I$ are the gradients of the shape
functions $N^I$ and $\mathbb{C}$ is the linear elasticity tensor (you see the
contraction of their components in the equation).
Despite being of the most explicit form, these types of indicial expressions are
avoided in most texts on finite elements. There are two reasons for this:
Engineers are not taught the Einstein summation convention.
The presence of indices result in a seemingly cluttered expression.
They avoid the indicial expression by reshaping it into matrix multiplications.
In engineering notation, the left- and right-hand sides are reshaped as
The matrices $\tilde{\boldsymbol{B}}$ and $\tilde{\boldsymbol{C}}$ are set on with tildes in order to
differentiate them from the boldface symbols used in the previous sections.
Here,
$\tilde{\boldsymbol{C}}$ is a matrix containing the unique components of the elasticity
tensor $\mathbb{C}$, according to the Voigt notation.
In this reshaping, only the minor symmetries are taken into account.
If the dimension of the vectorial problem is $d$, then $\tilde{\boldsymbol{C}}$ is of the size
$d(d+1)/2 \times d(d+1)/2$. For example, if the problem is 3 dimensional, $\tilde{\boldsymbol{C}}$
is of the size $6\times 6$:
$\tilde{\boldsymbol{B}}$ is a $nd\times d(d+1)/2$ matrix whose components are
adjusted so that \eqref{eq:engnot2} is equivalent to \eqref{eq:engnot1}. It
has the components of $\boldsymbol{B}^I$ for $I=1,\dots,n$ where $n$ is the number of
basis functions. Since $\tilde{\boldsymbol{B}}$ is adjusted to account for the reshaping
of $\mathbb{C}$, it has many zero components. A 3d example:
Although \eqref{eq:engnot3} looks nice on paper, it is much less optimal for
implementation. Implementing it requires the implementation of
\eqref{eq:engnotB}, which adds another layer of complexity to the algorithm.
The same cannot be said for \eqref{eq:engnotC}, because using Voigt
notation might be more efficient in inelastic problems. In the most complex
problems, the most efficient method is to implement \eqref{eq:engnot1} in
conjunction with Voigt notation.
To prove the inefficiency of \eqref{eq:engnot3} we can readily compare it with
\eqref{eq:engnot1} in terms of required number of iterations. Indices in
\eqref{eq:engnot1} have the following ranges:
iterations are required. So engineering notation requires $(d+1)^2/4$ times more
equations than index notation. For $d=2$, engineering notation is $2.25$
times slower and for $d=3$ it is $4$ times slower. For example, calculation of a
stiffness matrix for $n=8$ and $d=3$ requires $20736$ iterations for
engineering notation, whereas it only requires $5184$ iterations for index notation.
Although \eqref{eq:engnot3} seems less cluttered, what actually happens is
that one
trades off complexity in one expression for a much increased complexity in
another one, in this case \eqref{eq:engnotB}.
And to make it worse, it results in a slower algorithm.
The only obstacle to the widespread adoption of
index notation seems to be its lack in undergraduate engineering curricula.
If engineers were taught the index notation and summation convention as well
as the formal notation, such expressions would not be as confusing at first
sight. A good place would be in elementary calculus and physics courses, where
one heavily uses vector calculus.
There are many books that give an outline of hyperelasticity, but there are few
that try to help the reader implement solutions, and even fewer that
manage to do it in a concise manner. Peter Wriggers’
Nonlinear Finite Element Methods
is a great reference for those who like to
roll up their sleeves and get lost in theory. It helped me understand a lot
about how solutions to hyperelastic and inelastic problems are implemented.
One thing did not quite fit my taste though—it was very formal in the way that
it didn’t give out indicial expressions. And if it wasn’t clear up until this
point, I love indicial expressions, because they pack enough information to
implement a solution in a single line. Almost all books skip these
because they seem cluttered and the professors who wrote them think they’re
trivial to derive. In fact, they are not.
So below, I’ll try to derive indicial expressions for the update equations of
hyperelasticity.
In the case of a hyperelastic material, there exists a strain energy function
which describes the elastic energy stored in the solid, i.e. energy
density per unit mass of the reference configuration.
The total energy stored in $\CB$ is described by the the stored energy
functional
where $\bar{\BGamma}$ and $\bar{\BT}$ are the prescribed body forces per unit mass and surface tractions
respectively, where $\BT=\BP\BN$ with Cauchy’s stress theorem.
The potential energy of $\CB$ for deformation $\Bvarphi$ is defined as
We can write a Eulerian version of this form by pushing-forward the stresses and
strains.
The Almansi strain $\Be$ is the pull-back of the Green-Lagrange strain $\BE$ and
vice versa:
Commutative diagram of the linearized solution procedure. Each
iteration brings the current iterate $\bar{\Bvarphi}$ closer to the optimum
value $\Bvarphi^\ast$.
Mappings between line elements belonging to the tangent spaces of
the linearization.
If we introduce the Cauchy stress tensor $\Bsigma$ and corresponding elasticity tensor
$\BFc^\sigma = \BFc/J$,
our variational formulation can be expressed completely in terms of Eulerian quantities:
Here, $\bar{\BB}^\gamma = \nabla_{\bar{x}} N^\gamma$ denote the spatial
gradients of the shape functions. One way of calculating is
$\bar{\BB}^\gamma = \bar{\BF}\invtra\BB^\gamma$, similar to
\eqref{eq:defgradidentity1}.
The update equation
\eqref{eq:lagrangianupdate1} holds for the Eulerian version.
Conclusion
The equations above in boxes contain all the information needed to implement the
nonlinear solution scheme of hyperelasticity.
In lecturenotes
related to the
Discontinuous Galerkin method,
there is
mention of a magic formula which AFAIK first appeared on a paper1 by
Douglas Arnold (at least in this context).
It has been proven and all, but it’s still called magic because its reasoning is
not apparent at first glance. The magic formula is actually a superset of
the divergence theorem, generalized to discontinuous fields. But to make that
generalization, we need to abandon the standard formulation which starts by
creating a triangular mesh, and consider arbitrary partitionings of a domain.
A domain $\Omega$ is partitioned into parts $P^i$, $i=1,\dots,n$ as follows:
We call the set of parts $\mathcal{P}$ a partition of $\Omega$.
Broken Hilbert Spaces
We allow the vector field $\boldsymbol{u}$ to be discontinuous at
boundaries $\partial P^i$ and continuous in $P^i$, $i=1,\dots,n$.
To this end, we define the broken Hilbert
space over partition $\mathcal{P}$
It can be seen that $H^m(\mathcal{P})\subseteq H^m(\Omega)$.
Part Boundaries
Topologically, a part may share boundary with $\Omega$, like $P^4$.
In that case, the boundary of the part is divided into an
interior boundary and exterior boundary:
If a part has an exterior boundary, it is said to be an external part
($P^3$, $P^4$, $P^5$, $P^6$). If it
does not have any exterior boundary, it is said to be an internal
part.($P^1$, $P^2$).
Divergence theorem over parts
For a vector field $\boldsymbol{v}\in H^1(\mathcal{P})$,
$i=1,\dots,n$, we can write the following integral as a sum and apply the
divergence theorem afterward
If $P^i$ and $P^j$ are not neighbors, we simply have $\Gamma^{ij}=\emptyset$.
Integrals over interior boundaries
For opposing parts $P^i$ and $P^j$,
we have different values of the function $\boldsymbol{v}^{ij} = \boldsymbol{v}|_{\Gamma^{ij}}$
and conjugate normal vectors at the
interface $\Gamma^{ij}$:
With the results obtained, we put forward a generalized version of the divergence
theorem: Let $\boldsymbol{v}\in H^1(\mathcal{P})$ be a vector field. Then we have
Verbally,
the integral of the divergence of a vector field over a domain $\Omega$
equals
its integral over the domain boundary $\partial\Omega$,
plus
the integral of its jump over part interfaces $\mathcal{I}$.
In the case of a continuous field, the jumps vanish and this
reduces to the regular divergence theorem.
The Magic Formula
There are different versions of the magic formula for scalar, vector and tensor
fields, and for different IBVPs. I won’t try to derive them all, but give an
example: If we were substitute a linear mapping
$\boldsymbol{A}\boldsymbol{v}$
instead of $\boldsymbol{v}$, we would have the jump
$\llbracket \boldsymbol{A}\boldsymbol{v} \rrbracket$ on the right-hand side.
We introduce the vector and tensor average operator \(\{\cdot\}\)
The different versions of the magic formula are obtained by
substituting the identities above—or their analogs—in the discontinuous
divergence theorem.
Douglas N. Arnold. An interior penalty finite element method with discontinuous elements. SIAM J. Numer. Anal., 19(4):742–760, 1982. ↩
An example supply versus price graph. The area below the curve is equal to the amount of ETH $E$ that must be spent to increase the supply from $S_0$ to $S_1$, or that is going to be received when $S_1-S_0$ tokens are unbonded.
$S_0$ versus $E^{\text{suff}}_2$ for $E_1 = 100$.
Logarithmic plot of $S_0$ versus $E^{\text{suff}}_2$ for changing values of $E_1$.
$S_0$ versus $T^{\text{suff}}_2$ for $E_1 = 100$.
Commutative diagram for the pull-back and push-forward relationships of the Green-Lagrange and
Almansi strain tensors.
Commutative diagram of the linearized solution procedure. Each
iteration brings the current iterate $\bar{\Bvarphi}$ closer to the optimum
value $\Bvarphi^\ast$.
Mappings between line elements belonging to the tangent spaces of
the linearization.
