${\sf Hyb}_1$. This experiment is almost identical to the experiment in ${\sf Hyb}_0$, except the following modifications:

* Instead of calling $\NIZK.{\sf K}$ to generate the CRS, the simulator $\S'$ calls the simulated CRS generation algorithm $\widetilde{\sf K}_0$, such that for each honest miner $h\in\mcal{H}_{\rm miner}$, the simulator gets $(\widetilde{\crs}_h, \tau_h, \ek_h)$.
The simulator uses $\widetilde{\crs}_h$ as miner $h$'s NIZK CRS, and keeps the trapdoor $\tau_h$ and extraction key $\ek_h$ to itself.

* Whenever the simulator $\S'$ needs to compute a proof on behalf of an honest user identity $i$, it calls the simulated prover algorithm $\widetilde{\sf P}$ supplying the trapdoor $\overrightarrow{\tau}:=\{\tau_h\}_{h\in\mcal{H}_{\rm miner}}$ to compute a simulated proof without using the witness.

We use ${\sf Hyb}_1$ to denote the joint distribution of honest players' outputs and the adversary's view in this experiment.

Assuming that $\NIZK$ satisfies zero-knowledge, then ${\sf Hyb}_0\equiv_c{\sf Hyb}_1$.

The proof can be done via a sequence of hybrid experiments. First,
one by one for each honest miner, we
replace the real generation algorithm ${\sf K}$
with the simulated generation algorithm $\widetilde{\sf K}$.
Next, one by one for each NIZK proof of an honest user identity,
we replace the proof
with a simulated proof computed using
$\widetilde{P}$ without using the witness.

Since the number of corrupted miners is less than half, the adversary is minority-constrained (as defined in <ref>), the adjacent hybrids in each step are indistinguishable by a straightforward reduction to the zero-knowledge property of $\NIZK$.

${\sf Hyb}_2$. This experiment is almost identical to the experiment in ${\sf Hyb}_1$, except that whenever $\A$ supplies a correct   proof $\pi_{\ell}$ on behalf of a corrupted user identity $\ell$ for statement $\stmt_{\ell}$, the simulator $\S'$ calls the 's extraction algorithm $\mcal{E}(\CRS, \overrightarrow{\ek}, \stmt_{\ell}, \pi_{\ell})$ to extract the witness $w_{\ell}$.
If $w_{\ell}$ is not a valid witness yet $\NIZK.{\sf V}(\CRS, \stmt_{\ell}, \pi_{\ell}) = 1$, the simulator $\S'$ aborts.
We use ${\sf Hyb}_2$ to denote the joint distribution of honest players' outputs and the adversary's view in this experiment.

Assuming that $\NIZK$ satisfies simulation sound extractability, then ${\sf Hyb}_1\equiv_c{\sf Hyb}_2$.

Given that the simulator $\S'$ does not abort, the two experiments are identical.
Since the adversary controls less than half corrupted miners, by the simulation sound extractability property of , the probability of $\S'$ aborting in ${\sf Hyb}_2$ is negligible.
Specifically, for applying the simulation sound extractability, all NIZK statements in the protocol are tagged with the user identity (identity of the prover), thus no statement can be reused.
Therefore, ${\sf Hyb}_1\equiv_c{\sf Hyb}_2$.

${\sf Hyb}_3$. This experiment is almost identical to the experiment of ${\sf Hyb}_2$, except for the following difference:

* In the sharing phase, for each honest user identity $i$, instead of committing to the $m$ shares $\{X_{i,j}\}_{j\in[m]}$ of the $t$-out-of-$m$ secret sharing scheme, the simulator $\S'$ commits to $X_{i,k}$ for corrupted miner $k\in\mcal{K}_{\rm miner}$, and commits to $0$ for honest miner $h\in\mcal{H}_{\rm miner}$.

* $\S'$ uses the simulated prover algorithm $\widetilde{\sf P}$ of   to vouch for honest user identities.

* Upon receiving the openings, it sends $({\sf ok}, h, i)$ for all honest user identities $i\in{\sf ID}$ and all honest miners $h\in\mcal{H}_{\rm miner}$, without actually checking the openings of the commitments.

We use ${\sf Hyb}_3$ to denote the joint distribution of honest players' outputs and the adversary's view in this experiment.

Assuming that the commitment scheme ${\sf comm}$ is computationally hiding, then ${\sf Hyb}_2\equiv_c{\sf Hyb}_3$.

The proof can be done via a sequence of hybrid experiments, where one by one for each honest user identity $i$, we replace the commitments $\{\widehat{X}_{i,h}\}_{h\in\mcal{H}_{\rm miner}}$ of the shares $X_{i,h}$ with commitments of $0$.
The adjacent hybrids in each step are indistinguishable by a direct reduction to the computational hiding property of ${\sf comm}$.

Recall that ${\sf Exp}_{\mcal{S}}^{\sf Ideal}$ denotes the honest players' outputs computed by $\fmec$ and the view simulated by $\mcal{S}$ which interacts with $\fmec$.

If the commitment scheme ${\sf comm}$ is perfect binding and that the $t$-out-of-$m$ secret sharing scheme is secure, then ${\sf Hyb}_3 \equiv {\sf Exp}_{\mcal{S}}^{\sf Ideal}$.

The only differences in ${\sf Hyb}_3$ and
${\sf Exp}_{\mcal{S}}^{\sf Ideal}$

* In ${\sf Exp}_{\mcal{S}}^{\sf Ideal}$, the simulator is generating
honest-to-corrupt shares at random; whereas
in ${\sf Hyb}_3$, the honest-to-corrupt shares are generated honestly.
By the security of Shamir secret sharing, the two approaches
result in the same distribution since the adversary controls fewer
than $m/2$ miners.

* In ${\sf Hyb}_3$, if the experiment did not abort,
then the simulator sends
the shares actually opened by corrupt user identities to $\mcal{F}_{\rm TFM}$.
By contrast, in ${\sf Exp}_{\mcal{S}}^{\sf Ideal}$,
the simulator uses the shares output by the NIZK's extractor
$\mcal{E}$ instead.
Since the commitment is perfectly binding, the two approaches
result in the same outcome as long as the simulator did not abort.

Therefore, the two hybrids are identically distributed.

We first show that, if the simulators do not abort in both experiments, the joint distribution of honest players' outputs and the adversary's views in both experiments are computationally indistinguishable.
First, note that in ${\sf Hyb}_3$, for each honest user identity $i\in{\sf ID}$, the shares $\{X_{i,k}\}_{k\in\mcal{H}_{\rm miner}}$ for corrupted miners are generated from the secret $b_i$ by a $t$-out-of-$m$ secret sharing scheme, whereas in ${\sf Exp}_{\mcal{S}}^{\sf Ideal}$, they are generated uniformly at random.
Since the number of the corrupted miners is strictly smaller than $\frac{m}{2}\leq t$, by the security of secret sharing, the views of the adversary in the two worlds must be identical.

Now, for any fixed view of the adversary $\mcal{A}$, the distribution of the output of honest players in the two experiments must be identical.
At the end of the sharing phase, the set $\mcal{C}$ are the same in both ${\sf Hyb}_3$ and ${\sf Exp}_{\mcal{S}}^{\sf Ideal}$.
Moreover, by the perfect binding property of the commitment ${\sf comm}$, at the end of the sharing phase in ${\sf Hyb}_3$, every miner holds a valid share for secret $b_i$ of each user identity $i\in{\sf ID}\setminus\mcal{C}$.
Since the number of honest miners is more than the reconstruction threshold $t$, it is guaranteed that any bid $b_i$ for $i\in{\sf ID}\setminus\mcal{C}$ will be successfully reconstructed in ${\sf Hyb}_3$.
Hence, in both worlds, as long as the simulators do not abort, the inputs $\bids$ to the mechanism are identically distributed.

Since the probability that the simulator aborts is negligible, we have that ${\sf Hyb}_3 \equiv_c {\sf Exp}_{\mcal{S}}^{\sf Ideal}$.

By the hybrid lemma, we have that ${\sf Exp}_{\mcal{A}}^{\sf Real} \equiv_c {\sf Exp}_{\mcal{S}}^{\sf Ideal}$.
Therefore, the protocol $\pmec$ securely realizes $\fmec$ in the $\mcal{F}_{\rm TFM}$-hybrid model as long as the adversary controls only a minority number of miners.

§.§ MPC Protocol in the Presence of Majority-Miner Coalitions

So far, we have focused on instantiating the MPC protocol
when the coalition controls only
minority of the miners.
As we explained in <Ref>, our game-theoretic
analyses also naturally extend to the case
when the coalition may control
majority of the miners.

In this case, we can modify our MPC protocol as follows to achieve
with abort under corrupt majority.
First, instead of threshold secret sharing, the user identities
may use additive secret sharing to share their bids among the miners.
As before, each user identity will broadcast commitments of all shares of its bid,
and then it gives the corresponding opening to every miner.
There is no more need to prove that the committed values are internally consistent
secret shares.
If a miner did not receive the correct opening from a user identity,
it can broadcast a complaint in which case the corresponding user identity
must reveal the correct opening or it will get kicked out.
During the reconstruction phase, if any miner fails to open, then the protocol
just aborts and no output is produced, i.e., no block will be mined.
Finally, $\mcal{F}_{\rm TFM}$
should also be instantiated with a corrupt majority MPC protocol.

§ CHARACTERIZATION OF FINITE BLOCK SIZE IN THE PLAIN MODEL

In real-world blockchains, we do not have an infinite block size.
Chung and Shi <cit.> showed that no non-trivial plain-model TFM
can achieve strict UIC and
strict SCP (even when $c = 1$)
for finite block size.
In this section, we show that although
approximate incentive compatibility
can help us overcome this impossibility,
nonetheless we cannot get useful mechanisms
whose social welfare scales with
the bid distribution (ignoring logarithmic terms).

§.§ Impossibility for Approximate Incentive Compatibility: Unbounded Bids

relaxing to approximate incentive compatibility
does not help us overcome the finite-block size
impossibility if bids can be unbounded.

Formally, we have the following theorem.

Suppose the block size is finite.
For any $\eps>0$,
no (possibly randomized) non-trivial TFM
in the plain model
can simultaneously satisfy $\eps$-UIC and $\eps$-SCP,
even if the miner colludes with only one user.

The rest of <ref> is dedicated to proving <ref>.
Before proving <ref>, we prove two useful lemmas.
The following lemma stating that for any non-trivial TFM and for any $\Delta > 0$, there always exists a user whose utility is at least $\Delta$ as long as the miner is honest.

Suppose a plain-model TFM $\mecha$ satisfies $\eps$-UIC for some $\eps \geq 0$.
For any $\Delta > 0$, if there exists a bid vector $\bfb = (b_1,\ldots,b_n)$ such that $x_i(\bfb) > 0$ for some $i \in [n]$, then there exists a true value $v_i$ of user $i$ such that $v_i \cdot x_i(\bfb_{-i}, v_i) - p_i(\bfb_{-i}, v_i) > \Delta + 2\cdot \max\left(\eps,\sqrt{v_i \cdot \eps}\right)$.

If user $i$'s bid is unconfirmed, the payment must be zero.
If user $i$'s bid is unconfirmed, the payment never exceeds the bid.
Thus, if user $i$ bids truthfully, its utility must be non-negative, so we have $r \cdot x_i(\bfb_{-i}, r) - p_i(\bfb_{-i}, r) \geq 0$ for all $r$ and $\bfb$.

By <ref> does it implies ex post case?, for all $\bfb$ and for all $z > y$, we have
\[
z[x_i(\bfb_{-i}, z)-x_i(\bfb_{-i}, y)] \geq p_i(\bfb_{-i}, z) - p_i(\bfb_{-i},y) - \eps.
\]

Moreover, we have
\[
z \cdot x_i(\bfb_{-i}, z) - y \cdot x_i(\bfb_{-i}, y) = z[x_i(\bfb_{-i}, z)-x_i(\bfb_{-i}, y)] + (z-y)\cdot x_i(\bfb_{-i}, y).
\]

Combine two equations above, we have
\[
z \cdot x_i(\bfb_{-i}, z) - y \cdot x_i(\bfb_{-i}, y) \geq p_i(\bfb_{-i}, z) - p_i(\bfb_{-i},y) + (z-y)\cdot x_i(\bfb_{-i},y) - \eps.
\]

Re-arrange the equation, we have
\[
z \cdot x_i(\bfb_{-i}, z) - p_i(\bfb_{-i}, z) \geq y \cdot x_i(\bfb_{-i}, y) - p_i(\bfb_{-i},y) + (z-y)\cdot x_i(\bfb_{-i},y) - \eps.
\]

As we have shown, $y \cdot x_i(\bfb_{-i}, y) - p_i(\bfb_{-i},y) \geq 0$.
Because $x_i(\bfb_{-i},y) > 0$,

there must exist an real number $z$ such that

\begin{equation}\label{eq:bigutil}
(z-y) \cdot x_i(\bfb_{-i}, y) - \eps > 2\cdot \max\left(\eps,\sqrt{z\eps}\right) + \Delta.
\end{equation}

Note that in the above step, we are using the fact
that there is no a-prori upper bound on the bids.
If Eq.(<ref>) holds, we have
\[
z \cdot x_i(\bfb_{-i}, z) - p_i(\bfb_{-i}, z) \geq 2\cdot \max\left(\eps,\sqrt{z\eps}\right) + \Delta.
\]

Thus, if user $i$'s true value is $z$, its utility is at least $2\cdot \max\left(\eps,\sqrt{z\eps}\right) + \Delta$.

The following lemma states that any user's utility is bounded by the miner's revenue.

Suppose the block size is upper bounded by $k$.
Fix any $\eps>0$, suppose a (possibly randomized) plain-model TFM
satisfies $\eps$-UIC and $\eps$-SCP (even when the miner colludes with only one user).
Then, for any possible bid vector, if the miner revenue is upper bounded by $\tau$,
every user's expected utility must be upper bounded by $\tau + \eps$.

For the sake of contradiction, suppose there exists a bid $\bids$ and a user $i$ with value $v$ such that ${\sf util}_i(\bfb,v) > \tau + \eps$.
In other words, when the world is $(\bids, v)$ and the miner is honest,
user $i$'s expected utility is $\tau + \eps + \delta$ for some $\delta > 0$.

Let $N = \lceil\frac{vk}{\delta}\rceil + 1$.
Imagine that the world is $\widetilde{\bids}$ of length $N+|\bids|$ where

\[\widetilde{\bids} = (\bids, \underbrace{v,v,\dots,v}_{N}).\]

Because the block size is upper bounded by $k$, there must exist a user $j$ whose bid is $v$ while its confirmation is $x \leq \frac{k}{N}$.
Therefore, if user $j$ bids truthfully, its true value is $v$.
Thus, user $j$'s utility is at most $v\frac{k}{N}< \delta$.

By assumption, the miner revenue is at most $\tau$.
Thus, when the miner is honest, the joint utility of the miner and user $j$ is strictly less than $\tau + \delta$.
However, the miner can collude with user $j$.
The coalition pretends that the world is $(\bids, v)$, and user $j$ plays the role of user $i$.

By assumption, if the world is $(\bids, v)$, user $i$'s utility is $\tau + \eps + \delta$.
Because the coalition does not inject any fake bid, the miner's utility is at least zero.
Thus, by deviating from the mechanism, the joint utility of the coalition becomes at least $\tau + \eps + \delta$, which increases strictly more than $\eps$.
It contradicts to $\eps$-SCP.

Now we are ready to prove <ref>.

Proof of <ref>.
For the sake of reaching a contradiction, suppose there exists a non-trivial TFM $\mecha$ that satisfies $\eps$-UIC and $\eps$-SCP for some $\eps$.
Because $\mecha$ is non-trivial, there must exist a bid vector $\bfb = (b_1,\ldots,b_n)$ such that $x_i(\bfb) > 0$ for some $i \in [n]$.

By <ref>, there exists a value $v_i$ such that
\[
v_i \cdot x_i(\bfb_{-i}, v_i) - p_i(\bfb_{-i}, v_i) > \mu(\bfb_{-i},0) + \eps + 2\cdot \max\left(\eps,\sqrt{v_i \cdot \eps}\right).
\]

Imagine that user $i$'s true value is $v_i$.
When user $i$ bids truthfully, the miner revenue is $\mu(\bfb_{-i},v_i)$.
However, by <ref>, we have
\[
\mu(\bfb_{-i},v_i) - \mu(\bfb_{-i},0) \leq 2 \cdot \max\left(\eps,\sqrt{v_i \cdot \eps}\right).
\]

Consequently, user $i$'s utility is larger than the miner's utility by more than $\eps$.
By <ref>, $\mecha$ cannot satisfy $\eps$-UIC and $\eps$-SCP.

The impossibility in <Ref>
relies on the bid distribution being unbounded.
One potential way to get round this impossibility is to assume
that there is an a-priori known bound on the maximum bid.
Indeed, this could allow us to get around the impossibility
of <Ref>
in the plain model,
as shown in <Ref>.  add ref
However, even for bounded bid distribution, we show that
relaxing to approximate incentive compatibility
cannot help us in designing a class of useful
whose social welfare (i.e., the sum of everyone's utilities)
scales up w.r.t. the bid distribution (barring
polylogarithmic factors).

Suppose the block size is upper bounded by $k$.

Fix any $\eps>0$. Given any TFM in the plain model
that satisfies $\eps$-UIC, $\eps$-MIC and $\eps$-SCP when the miner can collude with at most $c=1$ user,
and given any bid vector ${\bf b}$, let $M = \max({\bf b})$ be the maximum
bid of any user,

it must be that

* the miner's expected revenue is upper bounded by $12 k^2 \eps\log\left(\frac{M}{\epsilon}+1\right) + 2k\eps$;

* every user's expected utility is upper bounded by $12 k^2 \eps\log\left(\frac{M}{\epsilon}+1\right) + (2k+1)\eps$
conditioned on the bid being included in the block, and
the bid reflects its true value;

* the expected social welfare
is upper bounded by $O\left(k^3 \eps \log \left(\frac{M}{\epsilon}+1\right) + k^2\eps\right)$.

A direct corollary of <ref> is that there is no non-trivial mechanism that satisfies approximate incentive compatibility if the user's true value is unbounded.
This implies that there is no universal mechanism that works for all bid distributions.

Suppose the block size is upper bounded by $k$.
Fix any $\eps>0$.
If users' true values are unbounded,
then no (possibly randomized) non-trivial TFM in the plain model can simultaneously satisfy $\eps$-UIC and $\eps$-SCP, even if the miner colludes with only one user.

For the sake of contradiction, assume that there exists an $\eps > 0$, such that there exists a non-trivial TFM satisfying $\eps$-UIC and $\eps$-SCP.
Recall that $x_i(\bids)$ denotes the probability of user $i$'s bid being confirmed given that the world consists of the bid vector $\bids$ (assuming the mechanism is honestly implemented).
We define $\widetilde{x}_i(\bids')$ to be the probability of user $i$'s bid being confirmed conditioned on its bid being included in the block configuration $\bids'$.
According to the assumption that the mechanism is non-trivial, there must exist an $i\in[k]$ and a block configuration $\bids' = (b^*,\bids_{-i})$ such that $b^*$ has a positive probability $\widetilde{x}_i(\bids')$ of being confirmed.

Now imagine the world consists of the bid vector $\bids$ where

\[{\bids} = (b_1,b_2,\dots,b_{k-1}, \underbrace{M,M,\dots,M}_{T}),\]

where $T\geq \frac{2k}{\widetilde{x}_i(\bids')}$ and $M$ is some large number (larger than $\max\{b_1,\dots,b_k\}$) that we will specify later.

Since the block size is bounded by $k$, there must exist a user $j$ whose true value is $M$ yet its probability of being confirmed is no more than $\frac{k}{T} \leq \frac{1}{2}\widetilde{x}_i(\bids')$ by our choice of $T$.
Therefore, user $j$'s utility (assuming the mechanism is honestly implemented) is at most $M\cdot \frac{1}{2}\widetilde{x}_i(\bids')$.
Now consider the coalition of the miner and user $j$.
By <ref>, their joint utility when behaving honestly is at most

\[M\cdot \frac{1}{2}\widetilde{x}_i(\bids') + 12 k^2 \eps\log\left(\frac{M}{\epsilon}+1\right) + 2k\eps.\]

However, the miner can ask user $j$ to bid $b^*$ instead of its true value $M$ and include $(b_1,\dots,b_{k-1},b^*)$ into the block, where the bid $b^*$ comes from user $j$.
Since the payment cannot exceed the bid, now the utility of user $j$ is at least

\[M\cdot\widetilde{x}_i(\bids') - b^*.\]

As long as $M$ is large enough such that

\[M\cdot\widetilde{x}_i(\bids') - b^* \geq M\cdot \frac{1}{2}\widetilde{x}_i(\bids') + 12 k^2 \eps\log\left(\frac{M}{\epsilon}+1\right) + 2k\eps + \eps,\]

the coalition gains $\eps$ more joint utility comparing to honest strategy.
This contradicts $\eps$-SCP.
Note that since user's true value can be unbounded, such $M$ must exist.
Therefore, there does not exist a non-trivial mechanism that satisfies $\eps$-UIC and $\eps$-SCP simultaneously.
one bug in this proof: when the $b^*$ in the block is replaces with user $j$'s bid, user $j$ may not get the same confirmation probability.

The rest of <ref> is dedicated to proving <ref>.

§.§ Proof Roadmap

We first explain the blueprint.
To prove that the total social welfare
is small, we first show that the miner revenue
must be $\widetilde{O}(k^2 \epsilon)$ for any bid configuration.
If we can show this, then given that
the block size is finite, we can show that every user $i$'s utility
conditioned on being included is small, which then
allows us to bound the total social welfare. Suppose
this is not the case, i.e., suppose
that under some bid configuration ${\bf b} := (b_1, \ldots, b_N)$,
there is a user $i$ with expected utility (conditioned on being
included) significantly larger
than the maximum possible expected miner revenue
(which is upper bounded by $\widetilde{O}(k^2 \epsilon)$).
Then, imagine a world consisting of ${\bf b}$ and additionally
many users whose true value is the same as $b_i$.
In this case, there must be one such user $j$ whose expected utility is almost $0$.
Thus, if $j$ is the miner's colluding friend,
the miner would be willing to sacrifice all of its
revenue, pretend that the world consists of ${\bf b}$
where the $i$-th coordinate is replaced with $j$'s bid, and
run the honest mechanism subject
to $j$ being included.
In this case, the coalition can increase its expected joint utility
since user $j$ would be doing much better than the honest case.

The crux of our proof, therefore, is to show
that the
expected miner revenue must be bounded
for any bid vector.
To show this, we take two main steps.
First, we show that if the world consists of only
bids of value $M$, the expected miner revenue must be small
(see <ref>).
Using the above as base case, we then go through
an inductive argument to show that
in fact, for any bid vector
where users do not necessarily bid $M$,
the miner revenue must be small too (see <ref>).
Note that showing the first step itself
relies on another inductive argument that inducts
on the length of the bid vector.

§.§ Detailed Proof

§.§.§ Individual User's Influence on Miner Revenue is Bounded

Before proving <ref>,
we introduce some useful lemmas. The miner revenue bound is below
The following lemma states that
if, given some bid configuration, a user's expected utility
is not too large, then,
the miner's expected revenue should not drop
too much when we lower that user's bid to $0$.

any (possibly randomized) TFM in the plain model
that satisfies $\eps$-UIC, $\eps$-MIC and $\eps$-SCP against $1$-sized coalition,
for any $\bids_{-i}$ and $v$, we have the following
${\sf util}^i(\bids)$
denotes user $i$'s expected utility
and $\mu(\bids)$
is the expected miner revenue
when the bid vector is $\bids$:

\begin{equation*}
\mu(\bids_{-i}, v) - \mu(\bids_{-i}, 0) \leq
\begin{cases}
4\epsilon, & v\leq 2\epsilon\\
%    \alpha
{\sf util}^i(\bids_{-i},v)
+3\eps\log\frac{v}{\epsilon}+4\epsilon, & v>2\epsilon.
\end{cases}
\end{equation*}

Henceforth, we use ${\bf x}({\bf b})$ to denote the
vector of probabilities that each bid in ${\bf b}$
is included and confirmed, and let
${\bf p}({\bf b})$ denote the vector of expected payments
for every user when
the bid vector is ${\bf b}$.

First, observe that <Ref>
and <Ref> still hold in the plain model where the
terms $\overline{x}_i(\cdot)$, $\overline{p}_i(\cdot)$, and $\overline{\mu}(\cdot)$
are now replaced with $x_i({\bf b}_{-i}, \cdot)$
$p_i({\bf b}_{-i}, \cdot)$, and $\mu({\bf b}_i, \cdot)$
respectively, i.e., we now fix an arbitrary fixed ${\bf b}_{-i}$

rather than taking expectation
over the random choice ${\bf b}_{-i}$.

Specifically, <Ref> implies that
for any ${\bf b}_{-i}$,
for any $b \leq b'$,

\begin{equation}
b'\cdot [x_i({\bf b}_{-i}, b')-x_i({\bf b}_{-i}, b)]+\eps\geq p_i({\bf b}_{-i}, b') - p_i({\bf b}_{-i}, b) \geq b\cdot [x_i({\bf b}_{-i}, b')-x_i({\bf b}_{-i}, b)]-\epsilon.
\label{eqn:payment-sandwich-plain}
\end{equation}

<Ref> implies that
for any ${\bf b}_{-i}$,
for any $b \leq b'$,

\begin{equation}
\mu(\bids_{-i}, b') - \mu(\bids_{-i}, b) \leq 2\epsilon + (b' - b)\cdot [x_i({\bf b}_{-i}, b') - x_i({\bf b}_{-i}, b)].
\label{eqn:miner-rev-step-plain}
\end{equation}

Henceforth in this proof, we always fix an arbitrary $\bids_{-i}$.
For simplicity, in this proof, we omit $\bids_{-i}$
and use the short-hand notations
$x_i(v) := x_i(\bids_{-i}, v)$, $p_i(v) := p_i(\bids_{-i}, v)$,
and $\mu(v) := \mu(\bids_{-i}, v)$.

For $v\leq 2\epsilon$, the lemma directly follows
from (<ref>).
In the rest of the proof, we focus on the case where $v > 2\epsilon$.
Define a function $u_i(b)$ such that $\int_{0}^b u_i(t)dt = b\cdot x_i(b) - p_i(b)$.
For any $b\leq b'$, the payment when bidding $b$ is

\[p_i(b) = b\cdot x_i(b) - \int_{0}^b u_i(t)dt.\]

Since we do not have the guarantee that the utility increases with the bids, it can be that $u_i(b) \leq 0$ for some $b$.
However, we have that guarantee that at any point, $\int_{0}^b u_i(t)dt$ is non-negative.

By <Ref>, we know that for any $b\leq b'$, we have $p_i(b') - p_i(b)\leq b'[x_i(b')-x_i(b)]+\eps$, i.e.,

\begin{equation*}
\left[b'\cdot x_i(b') - \int_{0}^{b'} u_i(t)dt\right] - \left[b\cdot x_i(b) - \int_{0}^b u_i(t)dt\right]\leq b'\cdot[x_i(b')-x_i(b)]+\eps,
\end{equation*}

which is equivalent to

\begin{equation}
\xi(b,b'):=(b'-b)\cdot x_i(b) - \int_{b}^{b'} u_i(t) dt \leq \eps.
\label{eqn:util-area}
\end{equation}

Intuitively, the meaning
of $\xi(b, b')$ is
how much we are over-estimating if we use a rectangle
of width $b'-b$ and height $x_i(b)$
to approximate the area-under-curve[We may assume that any area under $0$ contributes
negatively to the area-under-curve.] for $u_i$, between $b$ and $b'$.
For example, the blue area in <ref>
represents $\xi(b,b')$, whereas the red area
the gray area is $\xi(b'',v)$.

Now consider the following sequence: $b_l = v - \frac{v}{2^l}$ for $l=0,\dots,L$ where $L = \lceil\log\frac{v}{2\epsilon}\rceil$.
By (<ref>), the miner revenue

\[\mu(b_l) - \mu(b_{l-1})\leq 2\epsilon + S(b_{l-1}, b_l),\]

where $S(b_{l-1}, b_l) := (b_{l} - b_{l-1})\cdot [x_i(b_{l}) - x_i(b_{l-1})]$.
Summing up the miner revenue difference together, we have

\begin{align*}
&\mu(v) - \mu(0) = \mu(v) - \mu(b_L) + \sum_{l=1}^L \mu(b_l) - \mu(b_{l-1})\\
\leq &2\epsilon + (v - b_{L})\cdot [x_i(v) - x_i(b_{L})] + \sum_{l=1}^L \left(S(b_{l-1}, b_l)+2\eps\right) &\text{By~\eqref{eqn:miner-rev-step-plain}}\\
\leq & 4\epsilon+2L\epsilon+\sum_{l=1}^L S(b_{l-1}, b_l). &\text{By }v-b_L\leq 2\epsilon
\label{eqn:miner-rev-sum}
\end{align*}

Now we proceed to bound the sum $\sum_{l=1}^L S(b_{l-1}, b_l)$.
For each $l = 1,\dots, L$, by the choice of the sequence,
we have

\[b_{l} - b_{l-1} = \frac{v}{2^l} = v - b_l, \quad \text{and} \quad
S(b_{l-1}, b_l) = (v-b_l)\cdot [x_i(b_{l}) - x_i(b_{l-1})]
\]

For simplicity, let $b_{L+1} := v$. We have the following:

\begin{align*}
&\sum_{l=1}^L S(b_{l-1}, b_l)
=\sum_{l=1}^L (v-b_l)\cdot [x_i(b_{l}) - x_i(b_{l-1})]\\
=& (v-b_L)\cdot x_i(b_L) + \sum_{l=1}^{L-1} (b_{l+1} - b_l)\cdot x_i(b_{l})\\
=&\sum_{l=1}^L (b_{l+1} - b_l)\cdot x_i(b_{l}). &\text{By } v = b_{L+1}
\end{align*}

In other words, the sum $\sum_{l=1}^L S(b_{l-1}, b_l)$ is equal
to the total area of the dashed rectangles TODO: changed to dashed in
We want to show that the sum $\sum_{l=1}^L S(b_{l-1}, b_l)$
is not significantly greater than
${\sf util}^i(v)$, i.e., the area under the $u_i$-curve.
The follow calculation says that this difference is upper bounded by

$\sum_{l = 1}^L \xi(b_l, b_{l+1})$.

\begin{align*}
&\sum_{l=1}^L S(b_{l-1}, b_l) - \int_{0}^v u_i(t)dt  = \sum_{l=1}^L (b_{l+1} - b_l) x_i(b_{l}) - \int_{0}^v u_i(t)dt\\
\leq & \sum_{l=1}^L \left\{(b_{l+1} - b_l) \cdot x_i(b_{l})-\int_{b_l}^{b_{l+1}} u_i(t)dt\right\} & \text{By } \int_{0}^{b_1} u_i(t)\geq 0\\
=  & \sum_{l=1}^L \xi(b_l, b_l+1) \leq \sum_{l=1}^{L} \epsilon = L\eps. &\text{By~\eqref{eqn:util-area}}
\end{align*}

Add a label in figure

Putting it together, the change in miner revenue $\mu(v) - \mu(0)$ is upper bounded by

\begin{align*}
&\mu(v) - \mu(0) \leq 4\epsilon+2L\epsilon+\sum_{l=1}^L S(b_{l-1}, b_l)\\
\leq &4\epsilon + 2L\epsilon + L\epsilon+\int_{0}^v u_i(t)dt \leq {\sf util}^i(\bids_{-i},v) +3\eps\log\frac{v}{\epsilon}+4\epsilon,
\end{align*}

where the last step comes from the fact that $L\leq \log\frac{v}{\eps}$ by our choice of $L$.

In <ref>, we give an illustrative example of the proof.
The sum of the area of rectangles represents the sum $\sum_{l=1}^L S(b_{l-1}, b_l)$.
While the red area is at most ${\sf util}^i(\bids_{-i},v)$ by the definition of the utility curve, the blue area (or blue area minus gray area when the utility curve goes above the rectangle) in each rectangle is at most $\eps$, according to (<ref>).

[trim axis left]
[grid=major, xmin=0, xmax=2, ymin=-0.1, ymax=1.1,
xtick = 1,1.5,1.7,2, xticklabels=$b$, $b'$, $b''$, $v$,
ytick = 0,1, yticklabels=$0$, $1$, legend pos=north west]
[black, thick, samples=300, smooth,domain=0:2, name path = A] 0.25*x^2;$x_i(\cdot)$;
[blue, thick, samples=300, smooth,domain=0:2, name path = A1] x*(x-1)*(x-1.5);$u_i(\cdot)$;
[draw=none,name path=B] 0.25;
[draw=none,name path=C] 0.25*1.7*1.7;

[blue!30] fill between[of=A1 and B,soft clip=domain=1:1.5];

[red!30] fill between[of=A1 and C,soft clip=domain=1.7:1.92];
[black!30] fill between[of=A1 and C,soft clip=domain=1.92:2];

(3,2) node $\xi(b,b')$;
[->] (3.5,1.8) – (4.3,1.3);
(5.5,4.5) node $\xi(b'',v)$;
[->] (5.5,4.2) – (6.3,3.6);

The blue area denotes $\xi(b,b')$, and the red area minus the gray area
denotes $\xi(b'', v)$.

[trim axis left]
[grid=major, xmin=0, xmax=2, ymin=-0.1, ymax=1.1,
xtick = 0,1,1.5,1.75,2, xticklabels=$b_0$, $b_1$, $b_2$, $b_3$, $v$,
ytick = 0,1, yticklabels=$0$, $1$, legend pos=north west]
[black, thick, samples=300, smooth,domain=0:2, name path = A1] 0.25*x^2;$x_i(\cdot)$;
[blue, thick, samples=300, smooth,domain=0:2, name path = A] x*(x-1)*(x-1.5);$u_i(\cdot)$;
[draw=none,name path=B1] 0.25;
[draw=none,name path=B2] 0.25*1.5*1.5;
[draw=none,name path=B0] 0;
[draw=none,name path=B3] 0.25*1.75*1.75;
[blue!30] fill between[of=B1 and A,soft clip=domain=1:1.5];
[blue!30] fill between[of=B2 and A,soft clip=domain=1.5:1.75];
[blue!30] fill between[of=B3 and A,soft clip=domain=1.75:1.93];
[black!30] fill between[of=A and B3,soft clip=domain=1.92:2];
[thick,dashed] (1,0) rectangle (1.5,0.25);
[thick,dashed] (1.5,0) rectangle (1.75,0.25*1.5*1.5);
[thick,dashed] (1.75,0) rectangle (2,0.25*1.75*1.75);

(4.3,3.6) node $\xi(b_2,b_3)$;
[->] (4.3,3.4) – (5.5,2.7);
(5.5,4.5) node $\xi(b_3,v)$;
[->] (5.5,4.3) – (6.4,3.8);
(2.5,2.3) node $\xi(b_1,b_2)$;
[->] (2.5,2.1) – (4.3,1);

The sum of the dashed rectangles is equal to $\sum_{l = 1}^L S(b_l, b_{l+1})$.
The difference between $\sum_{l = 1}^L S(b_l, b_{l+1})$
and the area under the $u_i(\cdot)$ curve is upper bounded by
$\sum_{l = 1}^L \xi(b_l, b_{l+1})$, represented
by the sum of the blue
areas minus the gray area.

Graphical explanation of the proof to <ref>

Because the miner can inject a bid $0$ for free,
<ref> implies the following corollary,
which says that if we remove a bid, the miner revenue should not be affected by too much.

Let $\mecha$ denote any (possibly randomized) TFM
in the plain model that satisfies $\eps$-UIC, $\eps$-MIC and $\eps$-SCP against $1$-sized coalition.
For any $\bids_{-i}$ and $v$,

\begin{equation*}
\mu(\bids_{-i}, v) - \mu(\bids_{-i}) =
\begin{cases}
5\epsilon, & v\leq 2\epsilon\\
{\sf util}^i(\bids_{-i},v)
+3\eps\log\frac{v}{\epsilon}+5\epsilon, & v>2\epsilon.
\end{cases}
\end{equation*}

Because the miner can inject a bid $0$ for free, by $\eps$-MIC, it must be

\begin{equation}
\mu(\bids_{-i}, 0) - \mu(\bids_{-i}) \leq \eps.
\label{eqn:inject0}
\end{equation}

The corollary is now directly implied by
and <ref>.

§.§.§ Bounds on Miner Revenue

We now prove bounds for the miner's revenue.
To do this, we first
prove a bound on miner revenue when everyone bids the same value $M$
(see <Ref>).
Then, we generalize to the case when everyone's bids
need not be the same (see <Ref>).

for $t \in \N \cup \{0\}$, we define $\bfm_t := (M,\ldots,M)$ where $|\bfm_t| = t$;
that is, $\bfm_t$
consists of $t$ copies of $M$.
Recall that $\mu(\bfb)$ denote the expected miner revenue given that
the world consists of the bid vector $\bfb$ (assuming the mechanism is honestly implemented).

We define $\tildemu(\bfb')$ to be the expected miner revenue
given that the block configuration is $\bfb'$.

I changed the lemma statement

Suppose that the block size is upper bounded by $k$. Fix an arbitrary
any $\eps>0$ and
$M > 2\epsilon$ and let $\bfm_t := (M, M, \ldots, M)$
be a vector containing $t$ repetitions of $M$.  Then,
for any (possibly randomized) TFM in the plain model
that satisfies $\eps$-UIC, $\eps$-MIC and $\eps$-SCP even when
the miner colludes with at most $c = 1$ user, it holds that
$\tildemu(\bfm_t) \leq 12 k^2 \eps\log\frac{M}{\epsilon}$
for all $t \leq k$.
block size is $k$ or block size is upper bounded by $k$?

the world consists of the bid vector $\bfm_K$ where $K > \frac{Mk}{\eps}$
is sufficiently large.

Let $\bfm_{t^*}$ be the block configuration that gives the miner optimal revenue; that is $t^* = \myargmax_{t\leq k} \tildemu(\bfm_t)$.
Clearly, it must be $\tildemu(\bfm_{t^*}) \geq \mu(\bfm_K)$.

Because of $\eps$-MIC, we have $\mu(\bfm_{t^*}) \geq \tildemu(\bfm_{t^*}) - \eps$.
Otherwise, if $\mu(\bfm_{t^*}) < \tildemu(\bfm_{t^*}) - \eps$, when the world is $\bfm_{t^*}$, the miner could simply choose $\bfm_{t^*}$ as the block configuration so that the revenue becomes $\tildemu(\bfm_{t^*})$, which is more than $\epsilon$ higher
than its honest utility

Combining the two inequalities, we have $\mu(\bfm_{t^*}) \geq \mu(\bfm_K) - \eps$.

Recall that ${\sf util}^i (\bids)$ denotes user $i$'s expected utility when the bid vector is ${\bids}$.
Next, we will show that for any $t \leq K$ and any user $i \in [t]$, it must be

\begin{equation}
\mu(\bfm_t) + {\sf util}^i (\bfm_t) \leq \mu(\bfm_K) + 2\eps.
\label{eq:base-case}
\end{equation}

For the sake of reaching a contradiction, suppose there is an integer $t$ and user $i$ such that $\mu(\bfm_t) + {\sf util}^i (\bfm_t) > \mu(\bfm_K) + 2\eps$.

Imagine that the world is $\bfm_K$, where $K > \frac{Mk}{\eps}$.
There must exist a user $j$ whose confirmation probability is at most $x_j(\bfm_K) \leq \frac{k}{K} < \frac{\eps}{M}$, as at most $k$ bids can be included in a block.
Therefore, user $j$'s utility is at most ${\sf util}^j(\bfm_K) \leq x_j(\bfm_K) \cdot M < \eps$.

Imagine that the miner now colludes with user $j$.
The miner implements the inclusion rule as if the world consists of
the bid vector $\bfm_t$
where the $i$-th position is occupied by user $j$'s bid.
Since the TFM is symmetric, and both users bid $M$,
user $j$'s expected utility
is now ${\sf util}^i(\bfm_t)$.

The joint utility of the coalition now is $\mu(\bfm_t) + {\sf util}^i (\bfm_t) > \mu(\bfm_K) + 2\eps > \mu(\bfm_K) + {\sf util}^j(\bfm_K) + \eps$, which contradicts $\eps$-SCP.

<Ref> must hold for any $t \leq K$ and any user $i \in [t]$.

According to <Ref>, we have $\mu(\bfm_{t^*}) + {\sf util}^i (\bfm_{t^*}) \leq \mu(\bfm_K) + 2\eps$ for any user $i$.
As we have shown, it must be $\mu(\bfm_{t^*}) \geq \mu(\bfm_K) - \eps$.
Combining these two inequalities, we have

\[{\sf util}^i (\bfm_{t^*}) \leq \mu(\bfm_K) + 2\eps -\mu(\bfm_{t^*})\leq \mu(\bfm_K) + 2\eps - \mu(\bfm_K) + \eps = 3\eps.\]

Since the utility of user $i$ is bounded, by applying <ref>, it must be

\begin{equation}\label{eq:base-case2}
\mu(\bfm_{t^*}) - \mu(\bfm_{t^* - 1}) \leq {\sf util}^i (\bfm_{t^*}) + 3\eps\log\frac{M}{\epsilon} + 5\eps \leq 8\eps + 3\eps\log\frac{M}{\epsilon}.
\end{equation}

Consequently, we have

\begin{align*}
&{\sf util}^i (\bfm_{t^*-1}) \leq \mu(\bfm_K) + 2\eps - \mu(\bfm_{t^*-1}) & \text{By~\eqref{eq:base-case}}\\
\leq &\mu(\bfm_K) + 2\eps - \mu(\bfm_{t^*})  + 8\eps + 3\eps\log\frac{M}{\epsilon}& \text{By~\eqref{eq:base-case2}}\\
\leq &\mu(\bfm_K) + 2\eps - \mu(\bfm_{K}) +\eps  + 8\eps + 3\eps\log\frac{M}{\epsilon} &\text{By }\mu(\bfm_{t^*}) \geq \mu(\bfm_K) - \eps\\
= &11\eps + 3\eps\log\frac{M}{\epsilon}.
\end{align*}

Then, we can apply <ref> again, and we have
\[
\mu(\bfm_{t^* - 1}) - \mu(\bfm_{t^* - 2})\leq  {\sf util}_i (\bfm_{t^*-1}) + 3\eps\log\frac{M}{\epsilon} + 5\eps
\leq 16\eps + 6\eps\log\frac{M}{\epsilon}.
\]

By the same reason, for any $r \leq t^*$, we have

\begin{equation}\label{eq:base-case3}
\mu(\bfm_{t^* - r}) - \mu(\bfm_{t^* - r - 1}) \leq (8r + 8) \eps + (3r+3) \cdot \eps\log\frac{M}{\epsilon}.
\end{equation}

Since $M \geq 2\eps$, we have $ \eps\log\frac{M}{\epsilon}\geq \eps$.
By Eq.(<ref>), we have

\begin{align*}
&\mu(\bfm_{t^*}) - \mu(\bfm_0) =
\sum_{r=0}^{t^*-1} \mu(\bfm_{t^* - r}) - \mu(\bfm_{t^* - r - 1}) \\
\leq &\left(8t^* + 4(t^* -1)t^* \right)\eps + \left(3t^* + \frac{3(t^*-1)t^*}{2}\right)\cdot\eps\log\frac{M}{\epsilon}\\
\leq &11(t^*)^2 \eps\log\frac{M}{\epsilon}. &\text{By } \eps\log\frac{M}{\epsilon}\geq \eps \text{ and } t^*\geq 1
\end{align*}

Notice that $\mu(\bfm_0) = 0$, so we have
\[
\mu(\bfm_{t^*}) \leq  11(t^*)^2 \eps\log\frac{M}{\epsilon}.
\]

Recall that we define $t^* = \myargmax_{t\leq k} \tildemu(\bfm_t)$.
By definition, $\tildemu(\bfm_t) \leq \tildemu(\bfm_{t^*})$ for all $t \leq k$.
As we have shown at the beginning, it must be $\mu(\bfm_{t^*}) \geq \tildemu(\bfm_{t^*}) - \eps$.
Thus, we have $\tildemu(\bfm_t) \leq \tildemu(\bfm_{t^*}) \leq \mu(\bfm_{t^*}) + \eps$ for all $t \leq k$.
Combine the arguments above, we have $\tildemu(\bfm_t) \leq 11k^2 \eps\log\frac{M}{\epsilon}+\eps\leq 12k^2 \eps\log\frac{M}{\epsilon}$ for all $t \leq k$.

Suppose the block size is upper bounded by $k$.

Fix any $\eps>0$.
For any (possibly randomized) TFM in the plain model
that satisfies $\eps$-UIC, $\eps$-MIC and $\eps$-SCP (even when the miner only colludes with one user),
for any block configuration $\bfb$,

the following must hold where $M$ is the maximum bid amount in the bid vector $\bfb$:

\[
\tildemu(\bfb) \leq
\begin{cases}
2k \eps, &\text{if } M < 2\eps,\\
12 k^2 \eps\log\frac{M}{\epsilon} + 2k\eps, &\text{if } M \geq 2\eps.
\end{cases}
\]

Given any block configuration $\bfb$,
the miner revenue must be upper bounded by the sum of the bids in $\bfb$.
Thus, if $M < 2\eps$, the miner revenue is upper bounded by $2k\eps$.

Henceforth, we focus on the case $M \geq 2\eps$.
Throughout the proof, we say that a bid $b$ is a low bid if $b < M$.
Then, any block configuration, up to reordering, can be
represented by $(\bfm_t, \bfL)$ for some $t \geq 1$, where
$\bfm_t$ consists of $t$ repetitions of $M$,
$\bfL$ which is possibly of length $0$, contains only low bids.
We prove the following claim by induction on the length of $\bfL$:

For any $\bfL$ consisting of only low bids,
for any $t$ such that $t + |\bfL| \leq k$,
the miner revenue $\widetilde{\mu}(\bfm_t, \bfL) \leq \tau+2|\bfL|\eps$, where  we set $\tau:= 12 k^2 \eps\log\frac{M}{\epsilon}$.

For the base case where $|\bfL| = 0$, i.e. the block does not contain any low bid, it is proven by <ref>.

Now, suppose we have proven that for any $\bfL'$ of length $R$, for any $t$, the miner revenue $\widetilde{\mu}(\bfm_t, \bfL')\leq \tau+2R\eps$.

We are going to show that for any $\bfL$ of length $R+1$, for any $t$, the miner revenue $\widetilde{\mu}(\bfm_t, \bfL)\leq \tau+2(R+1)\eps$.

For the sake of contradiction, suppose there exists a bid $\bfL$ of length $R+1$ and there exists a $t$, such that for the block configuration $(\bfm_t, {\bf L}) = (\bfm_t, d_1,\ldots,d_R,d_{R+1})$, the miner's revenue is $\tau + 2(R+1)\eps + \delta$ for some $\delta > 0$.

Now, imagine that the world consists of $(\bfm_K, d_1,\ldots,d_R)$, where $K > \frac{kM}{\eps}$.
In this case, the block configuration output by the honest
inclusion rule must be of the form $(\bfm_{t^*}, \bfd)$ for some $t^* \leq k - |\bfd|$
and $\bfd \subseteq \{d_1,\ldots,d_R\}$ consists
of only low bids.
Since $(\bfm_{t^*}, \bfd)$ only contains at most $R$ low bids,
the miner revenue $\tildemu(\bfm_{t^*}, \bfd) \leq \tau + 2R\eps$ by induction hypothesis.

By our choice of $K$, there must exist a user $i$ with true value $M$, whose confirmation probability $x_i(\bfm_K, d_1,\ldots,d_R) \leq \frac{k}{K} < \frac{\eps}{M}$ when the miner is honest.
We choose $K$ like this.
Thus, user $i$'s utility is at most $M \cdot x_i(\bfm_K, d_1,\ldots,d_R) < \eps$.
Now the miner can collude with user $i$, ask user $i$ to bid $d_{R+1}$ instead of its true value $M$ and include $(\bfm_t, d_1,\ldots,d_R,d_{R+1})$ in the block.
Since $d_{R+1} < M$ and the payment never exceeds the bid, user $i$'s utility is at least zero.
This implies that the decrease of the utility of user $i$ is strictly less than $\eps$.
Now the miner revenue is $\tau + 2(R+1)\eps + \delta$ by our assumption,
whereas the miner revenue in the honest case is at most $\tau + 2R\eps$.
Thus, the miner revenue increases by more than $2\eps$ compared to the honest case.

Thus, the joint utility of the coalition increases by more than $\eps$, which contradicts $\eps$-SCP.
Therefore, by induction, we have that $\mu(\bfm_t, \bfL) \leq \tau+2|\bfL|\eps$ for any $\bfL$ and any $t$ where $|\bfL| + t \leq k$.

since $|\bfL| \leq k$,
we conclude that $\tildemu(\bfb) \leq 12 k^2 \eps\log\frac{M}{\epsilon} + 2k\eps$.

§.§.§ Completing the Proof of <ref>

We now complete the proof of <Ref>.
To do so, we prove that each user's utility conditioned on being included
must be bounded
given that the miner revenue is bounded (see <Ref>),
which then leads
to our conclusion that the total social welfare must be small.

Suppose that the block size is upper bounded by $k$.

Fix any $\eps>0$.
For any (possibly randomized) TFM in the plain model satisfies $\eps$-UIC and $\eps$-SCP (even when the miner colludes with only one user),

for any bid vector $\bfb$ where $M := \max(\bfb)$, for and any user $i$,
conditioned on user $i$ being included in the block, user $i$'s utility
must be upper bounded by $U + \eps$
where $U = \underset{|\bfb'| \leq k, \max(\bfb') \leq M}{\max}\tildemu(\bfb')$,
i.e., $U$ is the maximum possible revenue
the miner can
get among all possible block configurations where
all bids are at most $M$.

For the sake of contradiction,
that under some bid vector $\bids'$ where all bids are at most $M$, some user $j$'s
expected utility conditioned on being included in the block
strictly more than $U + \epsilon$.
This implies that there must exist a block configuration
$\bids = (b_1,\ldots,b_{|\bfb|})$ where all bids are at most $M$,
and some $i \leq |\bfb|$, such that
under conditioned on the block configuration being $\bids$,
the $i$-th bid $b_i$ in the block
has expected utility
at least $U + \epsilon + \delta$ for some positive $\delta$.

Let $T = \lceil\frac{b_i k}{\delta}\rceil + 1$.
Imagine that the world consists of the bid vector
${\bids'}$ of length $T+|\bids|$ where

\[{\bids'} = (\bids, \underbrace{b_i,b_i,\dots,b_i}_{T}).\]

Because the block size is upper bounded by $k$, there must exist a user $j$ whose bid is $b_i$ while its confirmation probability is at most $\frac{k}{T}$.
Therefore, if user $j$ bids truthfully,
its utility is at most $b_i\cdot \frac{k}{T}< \delta$.
By our assumption, the miner revenue is at most $U$ under any
block configuration where bids are upper bounded by $M$.
Thus, when behaving honestly, the miner and user $j$ have joint utility strictly less than $U + \delta$.
However, the miner can collude with user $j$ and prepare the block where the block configuration is $\bfb$ and the $i$-th position is replaced with user $j$'s bid instead.
In this case, user $j$'s utility is $U + \eps + \delta$.
Because the coalition does not inject any fake bid, the miner's utility is at least zero.
Thus, by deviating from the mechanism, the joint utility of the coalition becomes at least $U + \eps + \delta$, which exceeds the honest case by more than $\eps$.
This contradicts $\eps$-SCP.

Proof of <ref>.
Suppose the world consists of an arbitrary
bid vector $\bfb$.
Let $M = \max(\bfb)$.

If $M < 2\eps$, the miner can have at most $2k\eps$-miner revenue by <ref>.
For any user $i$ who is bidding truthfully, its true value must be upper bounded by $M$ since $M = \max(\bfb)$.
Moreover, each confirmed user's utility is at most its true value, which is upper bounded by $M < 2\eps$.
Since there are at most $k$ number of confirmed user,
the expected social welfare is
$\sum_i {\sf util}^i({\bf b})$
plus the miner's expected utility,
which is upper bounded by $4k\eps$.

In the rest of the proof, we assume $M \geq 2\eps$ and we define
$\tildeutil^i({\bf b})$ to be the utility of user $i$
conditioned on being confirmed when the world
consists of the bid vector ${\bf b}$.
By <ref>, the miner can have at most $\left(12 k^2 \eps\log\frac{M}{\epsilon} + 2k\eps\right)$-miner revenue.

By <ref>,
for any $i$,
$\tildeutil^i({\bf b}) \leq 12 k^2 \eps\log\frac{M}{\epsilon} + (2k+1)\eps$.
Let $\gamma_i$ be the probability that user $i$ is included in the block given the bid vector $\bids$.
Observe that $\sum_i \gamma_i \leq k$ for any $\bids$.
Therefore, the expected total utility of all users is upper bounded by

\[
\sum_i {\sf util}^i({\bf b})
\sum_i \tildeutil^i({\bf b})  \cdot \gamma_i
\leq
\left(12 k^2 \eps\log\frac{M}{\epsilon} + (2k+1)\eps\right) \cdot \sum_{i} \gamma_i
= O\left(k^3 \eps \log \frac{M}{\eps}\right).
\]

The expected social welfare is
$\sum_i {\sf util}^i({\bf b})$
plus the miner's expected utility. Clearly, it is also upper bounded by
$O\left(k^3 \eps \log \frac{M}{\eps}\right)$.

Combine the argument above, because $\log\left(\frac{M}{\epsilon} + 1 \right)$ is always non-negative, the theorem follows.

§ CHARACTERIZATION FOR FINITE BLOCK SIZE IN THE MPC-ASSISTED MODEL

§.§ Characterization for Strict Incentive Compatibility

In this section, we give a characterization of strict incentive compatibility in the MPC-assisted model for finite block size.
We show that cryptography helps
us overcome the finite-block impossibility <cit.>
for $c = 1$, but
for $c\geq 2$, the impossibility still holds.

§.§.§ Feasibility for $c=1$

In the MPC-assisted model, we indeed can have a mechanism that achieves UIC, MIC, and $(\rho,1)$-SCP against a coalition controlling
$\rho \in (0, 1]$ fraction of the miners and $c = 1$ user.

MPC-assisted, posted price auction with random selection

Parameters: the reserved price $r$, and a block size $k$.

Input: a bid vector $\bfb = (b_1,\dots, b_{N})$.

* Allocation rule.
Any bid that is at least $r$ is considered as a candidate. Randomly select $k$ bids from the candidates to confirm.

* Payment rule.
Each confirmed bid pays $r$.

* Miner revenue rule.
Miner gets $0$ revenue.

In the above mechanism, the miner gains zero revenue.
This is inevitable as shown in <ref> of <Ref>.
Even in the MPC-assisted model, the miner must have zero revenue if we insist on strict incentive compatibility (even under Bayesian notions of equilibrium).

Assuming a finite block size $k$.
The above MPC-assisted, posted price auction with random selection in the MPC-assisted model satisfies
UIC, MIC, and $(\rho,1)$-SCP (in the ex post setting)
for arbitrary $\rho\in(0,1]$.

We will prove the three incentive compatibility properties separately.

Let $v_i$ denote the true value of user $i$.
First, refusing to bid cannot increase its utility.
Moreover, injecting bids does not help either.
To see this, assume that user $i$ bids its true value $v_i$ and injects a bid $b'$.
If $b'<r$, then it does not influence user $i$'s utility.
If $b'\geq r$, it either decreases the probability of user $i$ being confirmed if $v_i\geq r$, or it brings user $i$ negative expected utility if $v_i < r$.

Thus, we only need to argue that overbidding or underbidding does not increase the user's utility.
If user $i$'s true value $v_i<r$, then its utility when overbidding $b\geq r$ is $q\cdot (v_i - r)<0$, where $q$ is the probability of $b$ being confirmed.
If user $i$'s true value $v_i\geq r$, then underbidding $b<r$ brings it $0$-utility, whereas the honest utility $q(v_i - r)$ is positive.
Therefore, no matter how user $i$ deviates from the protocol, its utility does not increase.

MIC. Since the total miner revenue is always $0$, injecting fake bids does not increase the colluding miner's utility.
The miner cannot increase its utility by deviating from the protocol.

SCP. No matter how the coalition deviates, the colluding miner's revenue is always $0$. Therefore, the joint utility of the coalition is at most the utility of the colluding user.
By strict UIC, the joint utility does not increase.

Note that the above mechanism does not work for $c=2$.
Imagine that the miner colludes with two users $i$ and $j$, where user $i$ has true value exactly $r$ and user $j$ has a sufficiently large true value.
User $i$ may choose not to bid to increase the probability of user $j$ being confirmed.
This brings the coalition strictly more utility than behaving honestly.

§.§.§ Impossibility for $c \geq 2$

Unfortunately, even in the MPC-assisted model, no mechanism
with non-trivial utility
can achieve UIC, MIC, and $(\rho,2)$-SCP, even for Bayesian
notions of incentive compatibility.
To see this, observe that under the strict incentive compatible notion, $(\rho,c)$-SCP implies that any coalition of $\leq c$ users cannot benefit
from any deviation[We credit Bahrani, Garimidi, Roughgarden, Shi, and
Weinberg for making this observation.],
since the miner revenue has to be $0$
by <ref> of <Ref>.
Similar to the proof in Goldberg and Hartline <cit.>,
we show that any mechanism that is Bayesian UIC and Bayesian SCP against a $(\rho,2)$-sized coalition (for an arbitrary $\rho \in (0, 1]$
must satisfy the following condition: no matter how
a user $j$ changes its bid, user $i$'s utility should not change.

Given any (possibly random) mechanism in the MPC-assisted model that is Bayesian UIC and Bayesian SCP against $(\rho,2)$-sized coalition for some $\rho\in(0,1]$, and
suppose each user's true value is drawn i.i.d. from a distribution $\mathcal{D}$.
Then, for any user $i$ and user $j$, for any bid $b_j$ and $b'_j$, it must be that for any $\ell\geq 1$,

\[\underset{(v,\bids_{-i,j})\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v,b_j,\bids_{-i,j})] = \underset{(v,\bids_{-i,j})\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v,b'_j,\bids_{-i,j})],\]

where $\bids_{-i,j}$ represents all except user $i$ and user $j$'s bids.

The proof of this lemma is deferred to <ref>.
This lemma implies that no matter how user $j$ changes its bid, the expected utility of user $i$ should not change if user $i$'s true value is sampled randomly from $\mcal{D}$.
Consequently, we have the following result stating that user $i$'s utility should remain the same when bidding its true value, regardless of how many users are there.

Given any (possibly randomized) mechanism in the MPC-assisted model that achieves Bayesian UIC and Bayesian SCP against $(\rho,2)$-sized coalition for some $\rho\in(0,1]$, it holds that
for any user $i$ and $j$, for any bid $b_j$, for any $\ell\geq 1$,

\[\underset{(v_i,\bids_{-i,j})\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,b_j,\bids_{-i,j})]\leq \underset{(v_i,\bids_{-i,j})\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,\bids_{-i,j})],\]

where $v_{\textsf{id}}$ ($b_{\textsf{id}}$) denotes a bid $v$ ($b$) coming from identity $\textsf{id}$.

Proof roadmap for <Ref>.
By <Ref>,
$\underset{v_i,\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,b_j,\bids_{-i,j})] = \underset{v_i,\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,0_j,\bids_{-i,j})]$.
Therefore, to prove <Ref>, it suffices
to prove that

\[\underset{\bids_{-i,j}\sim\mathcal{D}^{\ell-1}}{\E}[{\sf util}^i(v_i,0_j,\bids_{-i,j})] \leq \underset{\bids_{-i,j}\sim\mathcal{D}^{\ell-1}}{\E}[{\sf util}^i(v_i,\bids_{-i,j})].
\]

This claim is relatively easy to prove if we
are willing to assume a strong symmetry assumption explained below.
With a technically more involved proof, we
can eventually get rid of this strong symmetry assumption
and prove it under our
current (much weaker) symmetry assumption defined in <ref>.

Strong symmetry assumption.
On top of our
current symmetric assumption defined in <ref>,
we additionally assume that for any
bid vector ${\bf b} := (b_1, \ldots, b_N)$,
if for $i \neq j$, $b_i = b_j$, then
the random variables $(x_i, p_i)$
and $(x_j, p_j)$
are identically distributed,
where $(x_i, p_i)$ are random variables denoting $i$'s confirmation probability
and $i$'s payment, respectively, and $(x_j, p_j)$ are similarly defined.

In other words, the strong symmetry assumption additionally assumes
that two bids of the same amount receive the same treatment, on top of
our existing symmetry assumption — note that this is a very strong assumption,
and this is why we want to get rid of it eventually.
If the above strong symmetry assumption holds, then we have that
for any identity $i'$ that injects a $0$ bid,

\[\underset{\bids_{-i,j}\sim\mathcal{D}^{\ell-1}}{\E}[{\sf util}^i(v_i,0_j,\bids_{-i,j})] = \underset{\bids_{-i,j}\sim\mathcal{D}^{\ell-1}}{\E}[{\sf util}^i(v_i,0_{i'},\bids_{-i,j})],
\]

This is because under the strong symmetry assumption, anyone who bids
the same amount as $i$ has the same expected utility,
and moreover, this utility
is not affected by whether the $0$ bid is posted by $j$ or $i'$.
Finally, we have for any $v_i$,

\[\underset{\bids_{-i,j}\sim\mathcal{D}^{\ell-1}}{\E}[{\sf util}^i(v_i,0_{i'},\bids_{-i,j})]\leq \underset{\bids_{-i,j}\sim\mathcal{D}^{\ell-1}}{\E}[{\sf util}^i(v_i,\bids_{-i,j})].\]

Otherwise, user $i$ can inject a $0$-bid using an arbitrary identity $i'$,
which strictly increases its utility. This contradicts Bayesian UIC.
We refer the reader to <ref> for a full proof of
without relying on the strong symmetry assumption.

The full prove of this lemma is deferred to TODO.
To convey the main idea, in the main body, we only prove this lemma assuming identity agnostic, which in addition to our current symmetric assumption, assumes that the mechanism does not use identity to do tie-breaking.
Equivalently, for any bid vector $(\bids, v)$, the bid $v$ receives the same treatment no matter which user bids $v$.

Note that by Lemma <ref>, we have

\begin{align*}
\underset{\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,b_j,\bids_{-i,j})] = \underset{\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,0_j,\bids_{-i,j})].
\end{align*}

It suffices to prove that

\[\underset{\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,0_j,\bids_{-i,j})] \leq \underset{\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,\bids_{-i,j})].
\]

By the identity agnostic assumption, we know that the utility of user $i$ should not change no matter the $0$-bid comes from which identity.

\[\underset{\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,0_j,\bids_{-i,j})] = \underset{\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,0_{i},\bids_{-i,j})],
\]

where now the $0$ bid comes from any fake identity registered by user $i$.

Therefore, by Bayesian UIC, we have that

\[\underset{\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,0_{i},\bids_{-i,j})]\leq \underset{\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,\bids_{-i,j})].\]

Otherwise, user $i$ can inject a $0$-bid using its fake identity, which strictly increases its utility.
It contradicts Bayesian UIC.
The lemma thus follows.

Given any (possibly randomized) mechanism in the MPC-assisted model that achieves Bayesian UIC, MIC and Bayesian SCP against $(\rho,2)$-sized coalitions for some $\rho\in(0,1]$, it holds that
for any user $i$, any value $v_i$, for any $\ell\geq 1$,

\[\underset{v_i,\bids_{-i}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,\bids_{-i})] = \underset{v_i\sim\mathcal{D}}{\E}{\sf util}^i(v_i).\]

We first show that for any $j$, user $i$'s expected utility should not change if user $j$ refuses to bid. Formally, for any $b_j$,

\begin{equation}
\underset{v_i,\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,b_j,\bids_{-i,j})] = \underset{v_i,\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,\bids_{-i,j})].
\label{eqn:util-equiv-if-quit}
\end{equation}

To see this, by <ref>, we have

\begin{align*}
\underset{v_i,\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,b_j,\bids_{-i,j})] \leq
% \underset{\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v,0,\bids_{-i,j})]\leq
\underset{v_i,\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,\bids_{-i,j})].
\end{align*}

Next, we are going to show that

\[\underset{v_i,\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,b_j,\bids_{-i,j})] = \underset{v_i,\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,0_j,\bids_{-i,j})]\geq \underset{v_i,\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,\bids_{-i,j})].\]

To see why this holds, note that the first equality follows from <ref>.
The inequality comes from 2-SCP:
Since by MIC, it must be that $\underset{\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[\mu(v_i,0_j,\bids_{-i,j})]\leq \underset{\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[\mu(v_i,\bids_{-i,j})]$,
therefore, it must be that $ \underset{v_i,\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,0_j,\bids_{-i,j})]\geq \underset{v_i,\bids_{-i,j}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,\bids_{-i,j})]$.
Otherwise, if there exists a $v_i$ such that this does not hold, the miner can collude with user $i$ and user $j$ with true value $0$, and ask user $j$ not to bid.
This strategy strictly increases the coalition's joint utility and thus contradicts Bayesian SCP against $(\rho,2)$-sized coalition.
Equation (<ref>) thus follows.

Let $f(\cdot)$ denote the p.d.f. of $\mathcal{D}$.
By definition of expectation,

\begin{align*}
&\underset{v_i,\bids_{-i}\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v_i,\bids_{-i})] = \int_{0}^{\infty} \underset{v_i,\bids_{-i,1}\sim\mathcal{D}^{\ell-1}}{\E}[{\sf util}^i(v_i,z_1,\bids_{-i,1})]f(z_1) dz_1\\
=& \int_{0}^{\infty} \underset{v_i,\bids_{-i,1}\sim\mathcal{D}^{\ell-1}}{\E}[{\sf util}^i(v_i,\bids_{-i,1})]f(z_1) dz_1 &\text{By Equation~\eqref{eqn:util-equiv-if-quit}}\\
=& \underset{v_i,\bids_{-i,1}\sim\mathcal{D}^{\ell-1}}{\E}[{\sf util}^i(v_i,\bids_{-i,1})].
\end{align*}

The lemma follows by repeating the above argument.

Now we are ready to prove the theorem stating that there is no mechanism that gives non-zero utility to either users or miners
and yet satisfies Bayesian UIC and SCP against $(\rho,2)$-sized coalitions.

Suppose the block size is $k$.
No MPC-assisted mechanism with non-trivial utility
achieves Bayesian UIC, MIC and Bayesian SCP against $(\rho,2)$-sized coalitions.

By <ref>, the miner-revenue has to be $0$.
Therefore, it suffices to prove that every user must have $0$-utility.

Consider a crowded world with $K$ number of users
and all of their bids are sampled independently at
random from $\mcal{D}$.
There must exist a user $j^*$ whose
probability of being confirmed is at most $k/K$, and thus its expected utility
is at most $\max(\mcal{D}) \cdot k/K$ where $k$ is the block size.
Thus, $\underset{\bids\sim\mathcal{D}^{K}}{\E}[{\sf util}^{j^*}(\bids)] = 0$ by taking $K$ to be arbitrarily large.

By <Ref>, it must be that $\underset{v_{j^*}\sim\mcal{D}}{\E}{\sf util}^i(v_{j^*}) = 0.$
Since $\underset{v_i\sim\mcal{D}}{\E}{\sf util}^i(v_i) = \underset{v_j\sim\mcal{D}}{\E}{\sf util}^j(v_j)$ for all user $i$ and $j$, every user's expected
utility must be the $0$ where the expectation is taken over the randomness of bids as well as the randomness of the mechanism, i.e.,
for any user $i$, any $\ell\geq 1$, we have $\underset{\bids\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^{i}(\bids)] = 0$.
Since user's utility is non-negative, this implies that
$\underset{\bids_{-i}\sim\mathcal{D}^{\ell-1}}{\E}[{\sf util}^{i}(v,\bids_{-i})] = 0$.

§.§ Feasibility of Approximate Incentive Compatibility

Although strict (even Bayesian)
incentive compatibility is impossible to achieve for $c \geq 2$ in the
MPC-assisted model, we have meaningful feasibility results
if we allow $\eps$ additive slack.
Still, we use $k$ to denote the finite block size and $M$ to denote the upper bound of the true values.
Specifically, we can achieve $\Theta(kM)$ social welfare as long
as many people place high enough bids,
which is asymptotically the best possible social welfare one can hope for.

MPC-assisted, Diluted Posted Price Auction

Parameters: the block size $k$, an upper bound $c$ of the number of users
colluding with the miner, an upper bound $M$ of users' true values,
a slack $\eps \geq 0$, and a posted-price $r$ such that $r\geq \frac{\eps}{2c}$.

Input: a bid vector $\bfb = (b_1,\dots,b_{N})$.

* Allocation rule.

* Given a bid vector $\bfb = (b_1,\dots,b_{N})$, remove all bids which are smaller than $r$.
Let $\widetilde{\bids} = (\widetilde{b}_1,\dots, \widetilde{b}_{\ell})$ denote the resulting vector.

* Let $T = \max \left(2c \sqrt{\frac{kM}{\eps}}, k\right)$.
If $\ell \geq T$, let $\bfd = \widetilde{\bids}$.
Else, let $\bfd = (\widetilde{b}_1,\dots, \widetilde{b}_{\ell}, 0, \ldots, 0)$ such that $|\bfd| = T$.
In other words, $\bfd$ is $\widetilde{\bids}$ appended with $T - \ell$ zeros.

* Randomly choose a set $S$ of size $k$ from $\bfd$, and every non-zero bid in $S$ is confirmed.

* Payment rule.
For each confirmed bid $b$, it pays $r$.

* Miner revenue rule.
For each confirmed bid $b$, the miner is paid $\frac{\eps}{2c}$.

Suppose there exists an upper bound $M$ on users' true values.
The above MPC-assisted, diluted posted price auction satisfies UIC, MIC, and $\eps$-SCP (in the ex post setting)
against $(\rho,c)$-sized coalitions for arbitrary $\rho\in(0,1]$ and $c \geq 1$.

We will prove the three incentive compatibility properties separately.
Note that in this mechanism, refusing to bid is equivalent to underbidding some value less than $r$.
So we mainly focus on the strategy space of bidding untruthfully and injecting bids.
When we say the expected utility of a user, the randomness is taken over the randomness in the mechanism.

Fix any user $i$, and let $v$ denote the true value of user $i$.
In the  mechanism, any confirmed bid pays $r$ and any bid less than $r$ must be unconfirmed.
Thus, if $v \leq r$, bidding untruthfully cannot give a postive utility,
so bidding truthfully and getting 0-utility is optimal.

Below we focus on the case when $v > r$.
In this case, the bid has a non-negative probability of being confirmed and it pays $r$.
So following the honest strategy leads to positive utility.
Bidding less than $r$ will cause the bid  to be unconfirmed and will not help the user.
Therefore, we may assume that the user
bids at least $r$ and may inject some fake bids.
Observe that any bid that is at least $r$ is treated the same by the mechanism.
Moreover, injecting fake bids

Bidding any number $b \geq r$ does not change the confirmation probability and the expected payment compared to bidding $v$, and bidding any number $b < r$ will cause it to be unconfirmed.
Thus, bidding truthfully is still optimal.
Consequently, we conclude that bidding truthfully is always optimal no matter what the world is (even if the world consists of some fake bids).
Next, if user $i$ injects some fake bids, either the injecting bids

make no difference (when $\ell \leq T$ after injecting), or it reduces the probability of bid $v$ being elected into the set $S$ (when $\ell > T$ after injecting).
Therefore, bidding untruthfully
and/or injecting fake bids
does not help the user.

By injecting fake bids, the strategic miner cannot increase the expected number of
real bids in the vector ${\bf d}$. Thus, injecting fake bids
cannot increase other bids' contribution towards the miner's revenue.
Therefore, the expected gain in miner revenue
must be upper bounded by
the fake bids' contribution towards miner revenue
minus the expected payments of the fake bids.
For each confirmed bid, the miner revenue is fixed to $\frac{\eps}{2c}$,
which is no more than
the payment of the bid.
Thus, the expected miner revenue
cannot increase through injecting fake bids, i.e., the mechanism is MIC.

First, we argue that
injecting bids does not help the coalition.
Specifically, using a similar proof as UIC, injecting bids does not help improve
the utility of any user in the coalition.
Using a similar argument as MIC, injecting bids
does not improve the miner's revenue minus the payment of the injected bids.

Therefore, injecting bids will not increase the coalition's joint utility.

Now it suffices to argue that underbidding or overbidding does not increase the coalition's joint utility by more than $\eps$.
Suppose when bidding honestly, the number of bids in $\widetilde{\bids}$ is $\ell$.
Each bid in $\widetilde{\bids}$ is confirmed with probability $\frac{k}{\max\{T,\ell\}}$.
Assume that by bidding untruthfully, the coalition changes the length of $\widetilde{\bids}$ to $\ell'$.
Now each bid in $\widetilde{\bids}$ is confirmed with probability $\frac{k}{\max\{T,\ell'\}}$.

We partition the players in the coalition into the following groups:

* Those whose true values are less than $r$ and bid less than $r$. Their expected utility does not change.

* Those whose true values are less than $r$ and bid higher than or equal to $r$. Their expected utility does not increase.

* Those whose true values are at least $r$ and bid less than $r$. Their expected utility does not increase.

* Those whose true values are at least $r$ and bid at least $r$.
For each of these users, its expected utility increases by at most

\begin{equation}
(v-r)\frac{k}{\max\{T,\ell'\}} - (v-r)\frac{k}{\max\{T,\ell\}}.
\label{eqn:dilut-util-change}
\end{equation}

Note that for $\ell'\geq\ell$, then $\eqref{eqn:dilut-util-change}\leq 0$.
Therefore, we only need to consider the case where $\ell'<\ell$.
If $\ell \leq T$, then (<ref>) is $0$.
If $\ell > T$, then (<ref>) is upper bounded by

\begin{align*}
\eqref{eqn:dilut-util-change}&\leq (v-r)\left[\frac{k}{\ell'} - \frac{k}{\ell}\right]\\
&\leq (v-r)\left[\frac{k}{\ell-c} - \frac{k}{\ell}\right]\leq (v-r)\frac{ck}{\ell(\ell-c)}\\
&\leq M\cdot \frac{ck}{T(T-c)}.
\end{align*}

By the choice of $T$, we have that $T(T-c)\geq \frac{1}{2}T^2$.

\[\eqref{eqn:dilut-util-change}\leq M\cdot \frac{ck}{T(T-c)}\leq \frac{2Mck}{T^2}\leq \frac{\epsilon}{2c}.\]

This implies that each user's utility can increase by at most $\frac{\eps}{2c}$.
Meanwhile, for each user in the coalition, it can increase the miner's revenue by no more than $\frac{\eps}{2c}$ via bidding untruthfully.
Since there are at most $c$ users in the coalition, the coalition can gain at most $\eps$ more utility in total, no matter how they deviate.

§ ACKNOWLEDGMENTS

This work is in part supported by NSF awards 2212746, 2044679, 1704788, a Packard Fellowship, a generous gift from the late Nikolai Mushegian, a gift from Google, and an ACE center grant from Algorand Foundation.
The authors would like to thank the anonymous reviewers for their helpful comments.
We also thank Matt Weinberg
for helpful technical discussions regarding how to
efficiently instantiate our MPC-assisted mechanisms.

§ FULL PROOF OF <REF>

We now prove <ref>
of <ref>, i.e., the propotional auction
in the plain model
UIC, MIC, and $\frac54 c\eps$-SCP against
any miner-user coalition
with an arbitrary $c \geq $ number of users.

Proof of <ref>.
We prove the three properties individually.

Because the confirmation and the payment of each bid are independent of other bids, injecting fake bids does not help to increase any user's utility.

Next, suppose user $i$'s true value is $v_i$.
If user $i$ bids $b_i$, its expected utility is
\[
\begin{cases}
\left(v_i - \frac{b_i}{2}\right)\frac{b_i}{r}, & \text{ if } b_i < r,\\
v_i - \frac{r}{2}, & \text{ if } b_i \geq r.
\end{cases}
\]

By direct calculation, the expected utility is maximized when $b_i = v_i$.
Thus, proportional auction is strict UIC.

Since the block size is infinite, the miner's best strategy is to include all bids to maximize its revenue.
Notice that the confirmation of each bid and the miner revenue of each bid are independent of other bids.
Thus, injecting fake bids does not change the miner revenue from “other bids.”
Moreover, for each confirmed bid, the miner revenue is upper bounded by the payment of that bid.
Thus, the increment of the miner revenue never exceeds the cost of the injected fake bids.
Thus, the miner revenue cannot increase by injecting fake bids, so the mechanism is strict MIC.

As we have shown in the argument for strict UIC and strict MIC, injecting fake bids does not change the colluding miner's revenue.
Because the confirmation and the payment of each bid are independent of other bids, injecting fake bids does not help to increase any user's utility.
Thus, in the rest of the proof, we assume the only deviation of the coalition is to change the bids from colluding users' true values to other values.

Let user $i$ be a colluding user.
We will show that the joint utility increases at most by $\frac{5}{4}\eps$ if user $i$ changes its bid from its true value to other values, no matter what other bids are.
Because there are at most $c$ colluding users, the mechanism is $\frac{5}{4}c\eps$-SCP for all $c$.

Let user $i$ be a colluding user with true value $v_i$, and let $b_i$ be user $i$'s bid.
We now proceed to analyze the utility of coalition based on how users in the coalition bid untruthfully.

1. Underbidding. Suppose $b_i < v_i$.
Notice that the miner can get the payment from $b_i$ only when $b_i$ is confirmed, and the miner is paid $ \frac{\sqrt{2r\eps}}{2}$ if $b_i\geq \sqrt{2r\epsilon}$.
When user $i$ underbids, the miner's revenue can not increase.
Because the mechanism is strict UIC, underbidding does not increase user $i$'s utility either.
Thus, the joint utility does not increase if $b_i < v_i$.

2. Overbidding. Suppose $b_i > v_i$.
We first consider the following cases based on whether the true value $v_i$ is less than $r$.

* If $v_i \geq \sqrt{2r\epsilon}$.
If $v_i \geq r$, bidding truthfully already guarantees user $i$'s bid to be confirmed, and the miner is paid $\sqrt{\frac{r\eps}{2}}$.
Thus, when $v_i \geq r$, overbidding does not increase the joint utility.
In the following, we assume $v_i < r$.
Let $\Delta = \min(b_i - v_i, r - v_i) > 0$.
If user $i$ bids truthfully, its bid is confirmed with the probability $\frac{v_i}{r}$, so its expected utility is
\[
\left(v_i - \frac{v_i}{2}\right)\frac{v_i}{r}.
\]

Next, suppose user $i$ bids $b_i > v_i$.
Then, $b_i$ is confirmed with the probability $\frac{v_i + \Delta}{r}$, and the payment is $\frac{v_i + \Delta}{2}$ if $b_i$ is confirmed.
Thus, user $i$'s expected utility is
\[
\left(v_i - \frac{v_i + \Delta}{2}\right) \frac{v_i + \Delta}{r}.
\]

Hence, compared to bidding truthfully, user $i$'s expected utility decreases by
\[
\left(v_i - \frac{v_i}{2}\right)\frac{v_i}{r} -  \left(v_i - \frac{v_i + \Delta}{2}\right) \frac{v_i + \Delta}{r} = \frac{\Delta^2}{2r} > 0.
\]

On the other hand,
if user $i$ bids truthfully, the miner's expected revenue is $\frac{v_i}{r}\sqrt{\frac{r\eps}{2}}$.
If user $i$ bids $b_i > v_i$, the miner's expected revenue is $\frac{v_i + \Delta}{r}\sqrt{\frac{r\eps}{2}}$.
Thus, compared to bidding truthfully, the miner's expected utility increases by
\[
\frac{v_i + \Delta}{r}\sqrt{\frac{r\eps}{2}} - \frac{v_i}{r}\sqrt{\frac{r\eps}{2}} = \frac{\Delta}{r}\sqrt{\frac{r\eps}{2}}.
\]

Combine the argument above, the joint utility increases by

\begin{equation}\label{eq:proportional}
\frac{\Delta}{r}\sqrt{\frac{r\eps}{2}} - \frac{\Delta^2}{2r}.
\end{equation}

The maximum of Eq.(<ref>) is $\frac{\eps}{4}$, so overbidding $b_i$ can only increase the joint utility by $\frac{\eps}{4}$.

* If $v_i < \sqrt{2r\epsilon}$.
Because the mechanism is strict-UIC, overbidding does not increase user $i$'s utility.
If $b_i < \sqrt{2r\eps}$, the miner revenue is still zero.
Thus, we assume $b_i \geq \sqrt{2r\eps}$.
From the argument in the previous case, we know that compared to bidding truthfully, user $i$'s expected utility decreases by $\frac{\Delta^2}{2r}$.
However, if user $i$ bids truthfully, the miner's revenue is zero.
If user $i$ bids $b_i > v_i$, the miner's expected revenue is $\frac{v_i + \Delta}{r}\sqrt{\frac{r\eps}{2}}$.
Thus, compared to bidding truthfully, the miner's expected revenue increases by $\frac{v_i + \Delta}{r}\sqrt{\frac{r\eps}{2}}$.
Consequently, the joint utility increases by

\begin{equation}\label{eq:proportional2}
\frac{v_i}{r}\sqrt{\frac{r\eps}{2}} + \frac{\Delta}{r}\sqrt{\frac{r\eps}{2}} - \frac{\Delta^2}{2r}.
\end{equation}

Because the maximum of Eq.(<ref>) is $\frac{\eps}{4}$, the maximum of Eq.(<ref>) when $v_i < \sqrt{2r\eps}$ is at most $\frac{5\eps}{4}$.
Thus, overbidding $b_i$ can only increase the joint utility by $\frac{5\eps}{4}$.

To sum up, among all cases, overbidding $b_i$ can only increase the joint utility by at most $\frac{5}{4}\eps$.
The theorem thus follows.

Proportional auction for the MPC-assisted model.
In the MPC-assisted model, we want to ensure
incentive compatibility for any miner-user
coalition controlling at most $\rho$ fraction
of the miners and at most $c$ users — recall
that the total miner revenue is split among the miners.

By contrast, in the plain model, effectively $\rho$ is always equal to
$1$ since we always focus on the miner of the present block.
Therefore, to make the proportional auction work
in the MPC-assisted
model, we make a small modification
to the scheme and proof.
For the scheme, the only modification is that
we now allow the miner revenue to scale up
w.r.t. $\frac{1}{\rho}$  (up to the total user payment),
such that the miner revenue
can be larger if we only want to be resilient
against coalitions controlling small fraction of the miners — see the formal
description below.

Proportional Auction for the MPC-assisted Model

Parameters: the approximate factor $\eps$, upper bound $\rho$ on the fraction of the colluding miners and the reserved price $r$ such that $r \geq 2\eps$.

Input: a bid vector $\bfb = (b_1,\dots, b_N)$.

* Allocation rule.
For each bid $b$, if $b < r$, it is confirmed with the probability $b/r$; otherwise, if $b \geq r$, it is confirmed with probability $1$.

* Payment rule.
For each confirmed bid $b$, if $b < r$, it pays $b/2$; otherwise, if $b \geq r$, it pays $r/2$.

* Miner revenue rule.
For each confirmed bid $b$, let $p$ be the payment of $b$, and the miner is paid $\min\left(p, \frac{\sqrt{2r\eps}}{2\rho}\right)$.[The minimum guarantees that the miner revenue never exceed the payment.]

It is not hard to see that
our proof of <ref> can be easily modified to work
for the MPC-assisted model.
The only difference is that when the colluding user's true value $v_i$ is smaller than the threshold $\frac{\sqrt{2r\epsilon}}{\rho}$, overbidding to $v_i+\Delta < \frac{\sqrt{2r\epsilon}}{\rho}$ also increases the joint utility.
There are two cases:

* When a user with true value $v_i$ overbids to $v_i +\Delta < \frac{\sqrt{2r\epsilon}}{\rho}$, the coalition of the miner and this colluding user can gain at most $\eps$ more utility if $\Delta = \sqrt{2r\epsilon}$.

* When a user with true value $v_i$ overbids to $v_i +\Delta \geq  \frac{\sqrt{2r\epsilon}}{\rho}$, the coalition of the miner and this colluding user can gain at most $\frac{9}{4}\eps$ more utility when $\Delta = \sqrt{2r\epsilon}$ and $v_i$ is arbitrarily close to  $\frac{\sqrt{2r\epsilon}}{\rho}$.

explain why

§ FEASIBILITY:
APPROXIMATE INCENTIVE COMPATIBILITY FOR FINITE BLOCKS

In this section, we give a mechanism, called staircase mechanism,
that is $\eps$-UIC, MIC, and $\eps$-SCP for $c = 1$ in the plain model.
The staircase mechanism can in the best case achieve $\Theta(k^2 \epsilon)$ social

Recall that in <ref>, we showed that any
plain-model mechanism that works for finite block size
suffers from poor scaling of the social welfare w.r.t. the bid distribution.
In particular, we showed that the
social welfare is upper bounded by
$O(k^3 \epsilon \log(M/\epsilon))$
where $M$ is an upper bound on the social welfare.
Our staircase mechanism can achieve $\Theta(k^2 \epsilon)$
social welfare in the best case. Thus, we still have a gap
between the upper and lower bounds. Bridging this gap
is an interesting open problem.

Staircase Mechanism

Parameters: the block size $k$, the upper bound $c$ of the colluding users, the upper bound $M$ of the true value, the approximate factor $\epsilon$.

Notations: We define
\[
F_0 =
\begin{cases}
M - k\eps, &\text{ if } \lfloor\frac{M}{\eps} \rfloor \geq k,\\
M - \lfloor\frac{M}{\eps} \rfloor \eps, &\text{ if otherwise}.
\end{cases}
\]

For all $i = 1,\dots, k$, we define
\[
F_i = F_0 + i \cdot \eps.
\]

Input: a bid vector $\bfb = (b_1,\dots,b_N)$.

* Inclusion rule.
Given the bid vector $\bfb = (b_1,\dots,b_N)$, choose the top $k$ bids.

* Confirmation rule.
How do we break tie?

* Let $\bfc = (c_1,\dots, c_{N'})$ denote the bid vector in the block, where $c_1 \geq c_2 \geq \cdots \geq c_{N'}$ and $N' \leq k$.

* If $c_1 < F_1$, set $t = 0$.
Otherwise, set $t = \max_i \{i: c_i \geq F_i\}$.

* If $t = 0$, no one is confirmed.
Otherwise, $c_1, \ldots, c_t$ are confirmed.

* Payment rule.

For each confirmed bid, it pays $F_t$.

* Miner revenue rule.
Miner is paid $t \cdot \eps$.

In the staircase mechanism, the more bids confirmed, the higher the price.
For example, let $M = 10$ be the maximum possible bid, let $\epsilon = 1$,
and let the block size be $k = 5$.
if only one user is confirmed, then the price would be set to $6$;
if two users are confirmed, the price would be $7$; and so on.
Now, if the bid vector is $10, 9, 5, 3, 1$,
the mechanism would confirm the top two bids and they each pay $7$.
One can see that the mechanism achieves at least $\Theta(k^2 \epsilon)$ social welfare
in the best case:
suppose $\lfloor\frac{M}{\eps} \rfloor \geq k$ and $k/2$ users have true value $M$
while the remaining users have a value of $0$.
all the $k/2$ bids at $M$ will be confirmed and each bid
pays $F_{k/2} = M - (k\eps/ 2)$.
In this case, the mechanism achieves $\Theta(k^2 \epsilon)$ social welfare.

For example, suppose there are exactly $k/2$ users with true value $M$.
In this case, an honest miner will include all of them, and all users are confirmed.
Each user pays $F_{k/2} = M - (k\eps/ 2)$, so each user's utility is $k\eps / 2$.
The miner's revenue is also $k\eps / 2$.
Thus, the social welfare is $(k\eps / 2) \cdot k / 2 + k\eps / 2 = \Theta(k^2 \epsilon)$.

Notice that the miner's revenue grows linearly in $t$, the number of the confirmed bids in the block.
On the other hand, any confirmed user's payment also grows linearly in $t$, so each confirmed user's utility actually decreases linearly in $t$.
The miner's revenue and any user's utility as the functions of $t$ can be visualized by <ref>, which explains why the mechanism is called “staircase”.

,xlabel=$\text{the number of confirmed bids}$
,axis x line = bottom,axis y line = left
+[const plot, no marks, thick] coordinates (1,1) (2,0.9) (3,0.8) (4,0.7) (5,0.6) (5.49, 0.6) node[above=1cm,pos=.76,black] $\text{user's utility}$;
+[const plot, no marks, thick] coordinates (0,0) (1,0.1) (2,0.2) (3,0.3) (4,0.4) (5,0.5) (5.49, 0.5) node[below=1cm,pos=.76,black] miner's revenue;

The miner's revenue and any user's utility as the functions of the number of the confirmed bids in the block.

Intuitively, for any coalition consisting of the miner and a user, they do not have incentive to manipulate the number of confirmed bids, as the increase in miner revenue cancels out the decrease in the colluding user's utility.
The following example shows that a user or a miner-user coalition may have $\eps$ extra utility by deviation.
Suppose $M = k = 10$, and $\eps = 1$.
In this case, $F_0 = 0$.
Imagine that there are five users with the true values $8,7,6, 4.95, 4.9$, respectively.
If everyone bids truthfully, then $8,7,6, 4.95$ will be confirmed, since $F_4 = 4$ and $F_5 = 5$.
Notice that the fifth user (with the true value $4.9$) is unconfirmed, so its utility is zero.
However, if the fifth user bids $4.96$ instead, its bid will be confirmed, and $4.95$ will be unconfirmed.
The fifth user pays $F_4 = 4$, and gets the utility $4.9 - 4 = 0.9$.
Notice that the number of the confirmed bids does not change, so the miner is always paid $4\eps$.
Thus, if the miner colludes with the fifth user, their utility increases by $0.9$.
One can easily modify the true values so that the strategic gain is arbitrarily close to $\eps$.

The following theorem shows that
a strategic user or miner-user coalition cannot
gain more than $\epsilon$.

The staircase mechanism above satisfies $\eps$-UIC, strict-MIC, and $\eps$-SCP when the miner colludes with at most $1$ user.

We prove the three incentive compatibility properties separately.

Let $v_i$ be user $i$'s true value.
Without loss of generality, we assume a strategic user $i$ always first injects some fake bids, and then changes its true bid (not the fake bids) from the true value to some other value.
We will show that user $i$'s utility does not increase in either step.
Consequently, user $i$'s utility can never increase even if it plays strategically.

First, we show that

regardless of the current bid vector.
If user $i$ injects one more fake bid, its utility does not increase.
Suppose $\bfb = (b_1,\dots,b_N)$ is the current bid vector, where some bids might be fake bids injected by user $i$, and $b_i = v_i$ is user $i$'s true bid.
If $b_i$ is already confirmed, i.e. $x_i(\bfb_{-i}, v_i) = 1$, injecting another fake bid can never lower $t$.
Thus, user $i$'s payment can never be lower after injecting another fake bid.
On the other hand, if $b_i$ is unconfirmed, i.e. $x_i(\bfb_{-i}, v_i) = 0$, $b_i$ must still be unconfirmed after injecting another fake bid.
Explain more here?
Thus, injecting fake bids does not increase user $i$'s utility.

Second, we show that no matter what the current bid vector is, if user $i$ changes its true bid from the true value to some other value, its utility does not increase.
Suppose $\bfb = (b_1,\dots,b_N)$ is the current bid vector, where some of the bids might be the fake bids injected by user $i$, and $b_i = v_i$ is user $i$'s true bid.
Let $t^* = \max_i \{i: b_i \geq F_i\}$.
There are two cases.

* Case 1: $b_i$ is confirmed under the bid vector $\bfb$.
Notice that the payment never exceeds the bid, so user $i$'s utility is always non-negative when user $i$ bids truthfully.
Thus, if user $i$'s bid becomes unconfirmed after changing the bid, user $i$'s utility does not increase.
On the other hand, if user $i$'s bid is still confirmed after changing the bid, the number of confirmed bids in the block is still $t^*$ because changing the bid only permutes the order of the top $t^*$ bids.
Thus, user $i$'s payment is still $F_{t^*}$, so user $i$'s utility does not change.

* Case 2: $b_i$ is unconfirmed when the bid vector is $\bfb$.

If user $i$ underbids, its bid must still be unconfirmed.
If user $i$ overbids, the number of the confirmed bids must be at least $t^*$, so the payment for each confirmed bid is at least $F_{t^*}$.
Because $x_i(\bfb_{-i}, v_i) = 0$, it must be $v_i \leq F_{t^*+1} = F_{t^*} + \eps$.
Thus, if user $i$'s bid becomes confirmed because of overbidding, user $i$'s utility is at most $v_i - F_{t^*} \leq \eps$.

Without loss of generality, we assume the strategic miner prepares the block in the following order:
the miner chooses a subset of the bids $\bfc' = (c'_1,\ldots,c'_{\ell'})$ from the bid vector
(not necessarily the top $k$) where $c'_1 \geq \cdots \geq c'_{\ell'}$;
then, the miner injects some fake bids into $\bfc'$.
We will show that the miner's utility does not increase in either step.

First, let $\bfc = (c_1,\ldots,c_k)$ denote the top $k$ bids in the current bid vector
(if the number of bids is less than $k$, append zeros),
where $c_1 \geq c_2 \geq \cdots \geq c_k$.
Because $c_i \geq c'_i$ for all $i$, the number of the confirmed bids in $\bfc'$ cannot be more than the number of the confirmed bids in $\bfc$.
Thus, not choosing the top $k$ bids into the block never increases miner's revenue.

Second, let $\bfd = (d_1,\ldots,d_r)$ denote the bid vector that the miner prepares, where $d_1 \geq d_2 \geq \cdots \geq d_r$ for some $r$.
Here, $\bfd$ may or may not contain fake bids injected by the miner.
We will show that if the miner injects one more fake bid $f$, its utility does not increase.
Let $t^* = \max_i \{i: d_i \geq F_i\}$.
In this case, it must be $d_{t^*+1} < F_{t^*+1}$.
To increase the miner's utility, the number of the confirmed bids after injecting $f$ must increase, so we assume it is the case.
Because $d_{t^*+1} < F_{t^*+1}$, if the number of the confirmed bids increases, it must be that $f$ is confirmed and $f \geq F_{t^*+1}$.
Moreover, because the miner only injects one more fake bid to $\bfd$, the number of the confirmed bids after injecting the fake bid is at most $t^* + 1$.
Thus, the revenue that the miner gets increases by at most $\eps$.

The extra cost for injecting $f$ is $F_{t^*+1} \geq \eps$ for any $t \geq 0$.

Therefore, the overall utility does not increase.

Let user $j$ be the colluding user.
Let $\bfd = (d_1,\ldots,d_k)$ denote the top $k$ bids that the miner includes if both the miner and user $j$ are honest, where $d_1\geq \cdots \geq d_k$.
Let $t = \max_i \{i: d_i \geq F_i\}$;
that is, if the miner is honest, $t$ bids will be confirmed.
Next, suppose the coalition strategically includes
the bids $\bfd' = (d'_1,\ldots,d'_r)$ for some $r$,
where $d'_1 \geq d'_2 \geq \ldots \geq d'_r$.
Let $t' = \max_i \{i: d'_i \geq F_i\}$.

First, to increase the joint utility of the coalition, user $j$'s bid must be confirmed
when the block is $\bfd'$ — if user $j$'s bid is not included
under $\bfd'$, then by strict-MIC,
the miner's utility cannot increase when it chooses $\bfd'$ to be the block, and
obviously user $j$'s utility
cannot increase either if it is not confirmed under $\bfd'$.

Henceforth, we assume user $j$'s bid is confirmed when the block is $\bfd'$.
There are two possible cases.

* Case 1: User $j$'s bid is confirmed if the block is $\bfd$.
In this case, user $j$'s bid is confirmed under both $\bfd$ and $\bfd'$, so the change of user $j$'s utility only depends on its payment.
The payment changes from $F_t$ to $F_{t'}$, so user $j$'s utility increases by $F_t - F_{t'} = (t - t')\eps$ —

if $t-t'$ is negative, user $j$'s utility actually decreases.
On the other hand, the miner's revenue decreases by $(t - t')\eps$.
Therefore, the increase in user $j$'s utility
cancels out the decrease in the miner's revenue, and their joint utility does not change.

* Case 2: User $j$'s bid is unconfirmed if the block is $\bfd$.
In this case, user $j$'s true value $v_j$ must be smaller than $F_{t+1}$.
Since user $j$'s bid is unconfirmed when the block is $\bfd$, its utility is zero.
Since user $j$'s bid is confirmed when the block is $\bfd'$, its utility now becomes $v_j - F_{t'} < F_{t+1} - F_{t'}$.
Thus, user $j$'s utility increases by $v_j - F_{t'} < F_{t+1} - F_{t'} = (t + 1 - t')\eps$.
On the other hand, the miner's revenue decreases by $(t - t')\eps$.
Therefore, the joint utility increases by at most $\eps$.

§ DEFERRED PROOFS OF <REF>

§.§ Strict Incentive Compatibility in MPC-Assisted Model: Necessity of Zero Miner Revenue

Chung and Shi <cit.> showed that the posted-price auction with burning gives strict incentive compatibility in the plain model, assuming infinite block size.
One may hope that with the Bayesian notion of incentive compatibility, we can achieve larger miner revenue.
Unfortunately, in this section we show that zero-miner revenue is the best we can hope for strict incentive compatibility, even in the Bayesian setting.

Prelimary: Myerson's lemma for the Bayesian setting.
We first review the Bayesian version of Myerson's lemma.
Recall that $\bids_{-i}$ denotes all but user $i$'s bid, and $(\bids_{-i}, b_i) = \bids$.
We also let $\mcal{D}_{-i}$ to denote $\mcal{D}_1\times\dots\times\mcal{D}_{i-1}\times\mcal{D}_{i+1}\times\dots\times\mcal{D}_n$, which denotes the distribution of other users' true values.

Let $\mcal{D} = \mcal{D}_1\times\dots\times\mcal{D}_n$ be the joint distribution of users' true values.
Let $({\bf x}, {\bf p}, \mu)$ be a single-parameter TFM that is Bayesian UIC.
Then, it must be that

* The allocation rule ${\bf x}$ is monotonically non-decreasing.

Formally, for any user $i$, and any $b'_i > b_i$,
it must be that $\EXPT_{\bfb_{-i}\sim \otherdist} \left[x_i({\bf b}_{-i}, b'_i)\right]  \geq \EXPT_{\bfb_{-i}\sim \otherdist} \left[x_i({\bf b}_{-i}, b_i)\right] $.

* The payment rule ${\bf p}$ is defined as follows.
For any user $i$, and bid $b_i$ from user $i$,
it must be

\begin{equation}\label{eq:payment}
\EXPT_{\bfb_{-i}\sim \otherdist} \left[p_i(\bfb_{-i}, b_i)\right]
= \EXPT_{\bfb_{-i}\sim \otherdist} \left[b_i \cdot x_i(\bfb_{-i}, b_i) - \int_0^{b_i} x_i(\bfb_{-i}, t) dt\right].
\end{equation}

Let $f(z)$ be a non-decreasing function.
Suppose that $ z \cdot (f(z')-f(z)) \leq g(z') - g(z) \leq z' \cdot (f(z')-f(z))  $
for any $z' \geq z \geq 0$, and moreover, $g(0) = 0$.
Then, it must be that

\[
g(z) = z \cdot f(z) - \int_0^{z} f(t) dt.
\]

Necessity of zero miner revenue.
Henceforth we use the following simplified notation.

\[\overline{x_i}(\cdot) = \underset{\bids_{-i}\sim\otherdist}{\E} [{\bf x}(\bids_{-i}, \cdot)], \quad
\overline{p_i}(\cdot) = \underset{\bids_{-i}\sim\otherdist}{\E} [{\bf p}(\bids_{-i}, \cdot)], \quad
\overline{\mu_i}(\cdot) =\underset{\bids_{-i\sim\otherdist}}{\E}[\mu(\bids_{-i}, \cdot)].\]

The following technical lemma was given in <cit.>.

Let $({\bf x}, {\bf p}, \mu)$ be any (possibly randomized) TFM in the Bayesian setting.
If $({\bf x}, {\bf p}, \mu)$ is Bayesian SCP against a $(\rho,1)$-sized coalition, then for any bid vector $\bfb$, user $i$, and $r, r'$ such that $r < r'$, it must be
\[
r \cdot \left(\overline{x_i}(r') - \overline{x_i}(r)\right)
\leq \pi(r') - \pi(r)
\leq r' \cdot \left(\overline{x_i}(r') - \overline{x_i}(r)\right),
\]

where $\pi(r):= \overline{p_i}(r) - \rho\overline{\mu_i}(r)$.

The following result shows that if we allow the strategic players to inject fake bids, then the miner's revenue can only be $0$ if the mechanism is UIC, MIC, and $1$-SCP.
Actually, in the proof of the lower bound, we only need the deviation where the miners in the coalition injecting fake bids, and colluding users only bid untruthfully.

We first show that if a TFM is Bayesian UIC and Bayesian SCP against $(\rho,1)$-sized coalition, then the miner revenue must be independent from each user's bid. Without loss of generality, we assume that $0$ is the minimum value in the support of $\mcal{D}_i$ for $i\in[n]$.

Let $\mcal{D} = \mcal{D}_1\times\dots\times\mcal{D}_n$ be the joint distribution of users' true values.
Let $({\bf x}, {\bf p}, \mu)$ be any (possibly randomized) TFM in the MPC model.
If $({\bf x}, {\bf p}, \mu)$ is Bayesian UIC and Bayesian SCP against a $(\rho,1)$-sized miner-user coalition, then
for any user $i$, any bid $b$, it must be

\begin{equation}
\label{eqn:constant-revenue}
\overline{\mu_i}(b) = \overline{\mu_i}(0).
\end{equation}

In other words, the miner's revenue is a constant that is independent of user $i$'s bid $b$ when other bids $\bfb_{-i}$ are drawn from the distribution $\otherdist$.

Define $\widetilde{\pi}(r)$ as
\[
\widetilde{\pi}(r) = \overline{p_i}(r) - \rho\overline{\mu_i}(r) -
(\overline{p_i}(0) - \rho\overline{\mu_i}(0)).
\]

By Lemma <ref>,
and the fact that definition of $\widetilde{\pi}(r)$
and ${\pi}(r)$ differs by only a fixed constant,
it must be that

\begin{equation}
r \cdot \left(\overline{x_i}(r') - \overline{x_i}(r)\right)
\leq \widetilde{\pi}(r') - \widetilde{\pi}(r)
\leq r' \cdot \left(\overline{x_i}(r') - \overline{x_i}(r)\right).
\label{eqn:sandwich}
\end{equation}

Therefore, we have the following two inequalities:

\begin{align*}
r\cdot [\overline{x_i}(r') - \overline{x_i}(r)]&\leq \widetilde{\pi}(r') - \widetilde{\pi}(r)\\
r\cdot [\overline{x_i}(r') - \overline{x_i}(r)]&\geq \widetilde{\pi}(r') - \widetilde{\pi}(r)
\end{align*}

Now, observe that the above expression strictly
agrees with the “payment sandwich” in
the proof of Myerson's Lemma <cit.>.
Furthermore, we have that
$\widetilde{\pi}(0)= 0$
by definition; and
${\bf x}$ must be monotone because the TFM is UIC and satisfies
Myerson's Lemma.

Due to Lemma <ref>,
it must be that
$\widetilde{\pi}(\cdot)$ obeys the unique payment rule
specified by Myerson's Lemma; that is,

\[
\widetilde{\pi}(r) =
\left[b_i \cdot \overline{x_i}(b_i) - \int_0^{b_i} \overline{x_i}(t) dt \right].
\]

On the other hand, since the TFM is UIC, its payment rule
itself must also satisfy the same expression (Eq.(<ref>)), that is,

\[
\overline{p_i}(b_i)
= b_i \cdot \overline{x_i}(b_i) - \int_0^{b_i} \overline{x_i}(t) dt.
\]

We therefore have that

\[
\widetilde{\pi}(r)
= \overline{p_i}(b_i).
\]

In other words, $\rho\overline{\mu_i}(r) =  \rho\overline{\mu_i}(0) - \overline{p_i}(0)$.
Because $\overline{p_i}(0) = 0$, we conclude $\overline{\mu_i}(r) =  \overline{\mu_i}(0)$.

Note that the result in Lemma <ref> holds even if users do not inject any fake bids. This provides a stronger impossibility result.

Now we show that, if in addition the mechanism $\mecha$ is Bayesian MIC, then the total miner revenue can only be $0$.

Let $\{\mcal{D}^{(n)}\}_n$ be a sequence of distributions where  $\mcal{D}^{(n)} = \mcal{D}_1\times\dots\times\mcal{D}_{n}$ is the joint distribution of $n$ users' true values, where user $i$'s true value is drawn from $\mcal{D}_i$ independently.
Let $\mecha$ be any (possibly randomized) TFM in the MPC model.
If $\mecha$ is Bayesian UIC, Bayesian MIC against $\rho$-sized miner coalition and Bayesian SCP against $(\rho,1)$-sized miner-user coalition, then

\[\underset{\bids\sim\mcal{D}^{(n)}}{\E} [\mu(\bids)]=0.\]

For any $n\geq 2$, we have the following claim:

If $\mecha$ is Bayesian MIC against $(\rho,1)$-sized miner-user coalition, then $\underset{\bids\sim\mcal{D}^{(n)}}{\E} [\mu(\bids)] \leq \underset{\bids'\sim\mcal{D}^{(n-1)}}{\E} [\mu(\bids')]$.

For now assume Lemma <ref> holds and we explain why Theorem <ref> follows from it. The proof of Lemma <ref> appears right afterwards.
By induction on $n$, we have that

\[\underset{\bids\sim\mcal{D}^{(n)}}{\E} [\mu(\bids)] \leq \underset{b\sim\mcal{D}_{1}}{\E} [\mu(b)].\]

By Lemma <ref>, for any $b\in\supp{\mcal{D}_1}$, it should be that $\mu(b) = \mu(0)$. Therefore,

\[\underset{b\sim\mcal{D}_{1}}{\E} [\mu(b)]\leq \mu(0) = 0,\]

where the last equality comes from the requirement that the miner's revenue cannot exceeds the payment of the single identity, who will pay at most what it bids.

Theorem <ref> thus follows.

Proof of Lemma <ref>
Since $\mecha$ is Bayesian-SCP against $(\rho,1)$-sized coalition, it must be that for any user $i$,

\begin{equation}
\underset{\bids\sim\mcal{D}^{(n-1)}}{\E} [\rho \mu(\bids, 0)]\leq \underset{\bids\sim\mcal{D}^{(n-1)}}{\E} [\rho \mu(\bids)].\label{eqn:inject-induction}
\end{equation}

Otherwise, the miners can collude with user $i$, ask user $i$ to bid, and inject $0$ and increase the coalition's miner revenue while it does not need to pay anything for injecting the $0$-bid. This violates the MIC condition.

By the law of total expectation, we have that

\begin{align*}
\underset{\bids\sim\mcal{D}^{(n)}}{\E} [\mu(\bids)] &= \int_{0}^{+\infty} \underset{\bids'\sim\mcal{D}^{(n-1)}}{\E} [\mu(\bids', r)] f(r) dr & \\
&=\int_{0}^{+\infty} \underset{\bids'\sim\mcal{D}^{(n-1)}}{\E} [\mu(\bids', 0)] f(r) dr &\text{By Lemma~\ref{lemma:constantRevenue}}\\
&=\underset{\bids'\sim\mcal{D}^{(n-1)}}{\E} [\mu(\bids', 0)] \leq \underset{\bids'\sim\mcal{D}^{(n-1)}}{\E} [\mu(\bids')] &\text{By \eqref{eqn:inject-induction}}
\end{align*}

Lemma <ref> thus follows.

§.§ Proof of  <ref>

Let $\mecha$ be any (possibly random) mechanism that is Bayesian UIC and Bayesian SCP against $(\rho^*,2)$-sized coalition for some $\rho^*\in(0,1]$.
Suppose each user's true value is drawn i.i.d. from a distribution $\mathcal{D}$.
Then for any user $i$ and $j$, for any bid $b_j$ and $b'_j$, it must be that for any $\ell\geq 1$,

\[\underset{v,\bids\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v,b_j,\bids)] = \underset{v,\bids\sim\mathcal{D}^{\ell}}{\E}[{\sf util}^i(v,b'_j,\bids)].\]

In this proof, we use the following notations for simplicity.
For any fixed $\ell\geq 1$, for any user $i$ and $j$, we define the following notations:

\[\overline{x_i}(\cdot,\cdot) = \underset{\bids_{-i,j}\sim\mathcal{D}^{\ell-1}}{\E} [x_i(\cdot,\cdot,\bids)], \quad
\overline{p_i}(\cdot,\cdot) = \underset{\bids_{-i,j}\sim\mathcal{D}^{\ell-1}}{\E} [p_i(\cdot,\cdot,\bids)], \quad
\overline{\mu}(\cdot,\cdot) = \underset{\bids_{-i,j}\sim\mathcal{D}^{\ell-1}}{\E} [\mu(\cdot,\cdot,\bids)].\]

Imagine that user $i$ has true value $v$ and user $j$ has true value $y$.
Then for any feasible $\rho\leq \rho^*$, it must be that

\begin{align*}
& \text{Honest utility} = [v\cdot \overline{x_i}(v,y) - \overline{p_i}(v,y)]
+[y\cdot \overline{x_j}(v,y) - \overline{p_j}(v,y)]
\geq & \text{Overbid utility} = [v\cdot \overline{x_i}(v,z) - \overline{p_i}(v,z)]
+[y\cdot \overline{x_j}(v,z) - \overline{p_j}(v,z)]
\end{align*}

Otherwise, the miner can collude with user $i$ with true value $v$ and user $j$ with true value $y$ and ask user $j$ to overbid to some $z\geq y$.
This will increase the joint utility of the coalition, which contradicts $(\rho^*,2)$-SCP.
For the same reason, if user $j$'s true value is $z$, then

\begin{align*}
& \text{Honest utility} =[v\cdot \overline{x_i}(v,z) - \overline{p_i}(v,z)]
+[z\cdot \overline{x_j}(v,z) - \overline{p_j}(v,z)]
\geq & \text{Underbid utility} =[v\cdot \overline{x_i}(v,y) - \overline{p_i}(v,y)]
+[z\cdot \overline{x_j}(v,y) - \overline{p_j}(v,y)]
\end{align*}

Combining these two inequalities together, we get the following payment difference sandwich.
For any $z\geq y$, we have

\begin{align*}
&v[\overline{x_i}(v,z) -  \overline{x_i}(v,y)] +
z[\overline{x_j}(v,z) -  \overline{x_j}(v,y)]
\geq
\geq & v[\overline{x_i}(v,z) -  \overline{x_i}(v,y)] +
y[\overline{x_j}(v,z) -  \overline{x_j}(v,y)]
\end{align*}

Divide the inequality with $z-y$ and take limit $y \rightarrow z$, we get

\begin{equation}
\label{eqn:scp-diff}
v\cdot \frac{\partial}{\partial z} \overline{x_i}(v,z) + z\cdot \frac{\partial }{\partial z} \overline{x_j}(v,z) + \rho\frac{\partial }{\partial z} \overline{\mu}(v,z) = \frac{\partial}{\partial z} \overline{p_i}(v,z) + \frac{\partial}{\partial z} \overline{p_j}(v,z).
\end{equation}

Note that <ref> should hold for at least two different values of $\rho \leq \rho^*$.
Hence, it must be that $\frac{\partial }{\partial z} \overline{\mu}(v,z) = 0$.
<ref> thus becomes

\begin{align}
\label{eqn:2-uic}
&v[\overline{x_i}(v,z) -  \overline{x_i}(v,y)] +
z[\overline{x_j}(v,z) -  \overline{x_j}(v,y)]\nonumber\\
\geq
\geq & v[\overline{x_i}(v,z) -  \overline{x_i}(v,y)] +
y[\overline{x_j}(v,z) -  \overline{x_j}(v,y)].
\end{align}

This is equivalent to say: when user $j$ changes its bid, the joint utility of user $i$ and user $j$ should not increase.
That means, for any $v$, if a user $j$ with true value $y$ changes its bid from $y$ to $z$, it must be that

\begin{align*}
\text{i-gain}(v,y\rightarrow z)&:=\underset{\bids_{-i,j}\sim\mathcal{D}^{\ell-1}}{\E}{{\sf util}^i}(v,z,\bids_{-i,j}) - \underset{\bids_{-i,j}\sim\mathcal{D}^{\ell-1}}{\E}{{\sf util}^i}(v,y,\bids_{-i,j})\\ &\leq \underset{\bids_{-i,j}\sim\mathcal{D}^{\ell-1}}{\E}{{\sf util}^j}(v,y,\bids_{-i,j}) - \underset{\bids_{-i,j}\sim\mathcal{D}^{\ell-1}}{\E}{{\sf util}^j}(v,z,\bids_{-i,j}) := \text{j-loss}(v,y\rightarrow z)
\end{align*}

Since the mechanism is UIC, by the same proof as of <cit.>, we get:

\begin{align*}
\underset{v\sim\mathcal{D}}{\E}[\text{i-gain}(v, y\rightarrow z)] \leq & \underset{v\sim\mathcal{D}}{\E}[\text{j-loss}(v, y\rightarrow z)]\\
\leq & \underset{v\sim\mathcal{D}}{\E}[(z-y)(\overline{x_j}(v,z) - \overline{x_j}(v,y))].
\end{align*}

Now consider the situation where user $j$ changes its bid from $b_j$ to $b_j'$.
Without loss of generality, we assume that $b'_j\geq b_j$.
If we divide the interval between $[b_j, b_j']$ into $L$ equally sized segments $b_j^{(0)},\dots,b_j^{(L)}$, then the total gain for user $i$ can be bounded by

\begin{align*}
\underset{v\sim\mathcal{D}}{\E}[\text{i-gain}(v, b_j\rightarrow b_j')] &= \sum_{l=0}^{L-1} \underset{v\sim\mathcal{D}}{\E}[\text{i-gain}(v, b_j^{(l)}\rightarrow b_j^{(l+1)})]\\
&\leq \sum_{l=0}^{L-1}(b_j^{(l+1)} - b_j^{(l)}) \underset{v\sim\mathcal{D}}{\E}\left[\overline{x_j}(v,b_j^{(l+1)}) - \overline{x_j}(v,b_j^{(l)})\right]\\
&=\frac{b'_j-b_j}{L} \underset{v\sim\mathcal{D}}{\E}\left[\overline{x_j}(v,b_j') - \overline{x_j}(v,b_j)\right].
\end{align*}

This holds for any $L$.
Taking limit for $L \rightarrow \infty$, we have that

\[\underset{v\sim\mathcal{D}}{\E}[\text{i-gain}(v, b_j\rightarrow b_j')]\leq 0.\]

Since $\underset{v\sim\mathcal{D}}{\E}[\text{i-gain}(v, b_j\rightarrow b_j')] = - \underset{v\sim\mathcal{D}}{\E}[\text{i-gain}(v, b_j'\rightarrow b_j)]$, we have that $\underset{v\sim\mathcal{D}}{\E}[\text{i-gain}(v, b_j\rightarrow b_j')] = 0$, for arbitrary $b_j$ and $b'_j$.
The lemma thus follows.

§ MULTI-PARTY COMPUTATION PROTOCOL REALIZING $\FMEC$

So far in the paper, we have assumed that the transaction fee mechanism
is implemented by a trusted ideal functionality $\fmec$.
In this section, we show how to instantiate $\fmec$ in the real
world with cryptography.
The protocol described in this section uses generic MPC.
However, as mentioned
in <Ref>, the MPC-assisted mechanisms described
in this paper actually need not employ generic MPC to be instantiated in practice —
we describe efficient instantiations for our specific
protocols in <Ref>.

Terminology and model.
Imagine that there are $m$ miners
and  a set of user identities.

Since each user can assume multiple identities,
henceforth, we often use the term identities to refer to
the set of purported user identities.
We assume that the miners can communicate with each other through
a pairwise private channel.
Further, every user identity can communicate with
every miner through a pairwise private channel.
Morever, there is a broadcast channel
among the miners and the user identities.
We assume that all channels are authenticated, i.e., every message
is marked with the true sender.
Further, we assume a synchronous model of communication, i.e.,
the protocol proceeds in rounds and messages sent by honest parties
will be received by
honest recipients at the beginning of the next round.

We assume that at the beginning of the protocol, the miners have reached consensus on
the set of user identities that will participate in the auction.
For example, the consensus can be achieved in the
following manner: every user identity announces itself to all miners.
Then, each of the $m$ miners broadcasts to all miners a candidate set
consisting of the identities it has heard.
Any identity that appears in the majority
of the miners' candidate sets will be permitted into the auction.
As long as the majority of the miners are honest,
then any honest user identity will be included in the final permitted list.

The parties
now execute an interactive protocol at the end of which
all parties, including the miners and user identities,
learn the outcome of the auction, including which identities' bids
are confirmed and how much each confirmed bid pays.
In our actual protocol, the user identities need not communicate
with each other. Each user identity communicates only with the miners —
either it sends a direct message
to a miner over the pairwise private channel,
or it broadcasts a message which can be seen by all miners.

During the protocol, if  a subset of parties (miners or
user identities) form a coalition, we assume
that the coalition
has the advantage of performing a so-called “rushing attack”.
Specifically, in any round $r$, parties in the coalition can observe
honest parties' messages sent to coalition members
or posted on the broadcast channel, before deciding what messages
coalition members want to send in the same round $r$.

The miners will first reach a consensus on the set of identities that are going to participate.
We assume that each identity has access to the broadcast channel, and a private channel with each of the miners.
In the honest protocol, each identity only need to communicate with miners, no interaction between the identities is needed.
All communication channels are authenticated, i.e., messages carry the sender’s
Moreover, the network is synchronous and the protocol proceeds in rounds.
The protocol execution is parametrized with a security parameter $\secu$.
We assume that the coalition may perform a rushing attack:
In the $r$-th round, it waits for all honest players (those not in the coalition) to send messages in round $r$ and decides what messages the identities or miners in the coalition send in round $r$.
At the end, the protocol outputs the outcome of the mechanism.

§.§ Building Blocks

We first introduce some building blocks used in the protocol.

§.§.§ Commitment Scheme

A commitment scheme, parametrized by a security parameter $\lambda$,
and a message space $\{0, 1\}^{\ell(\lambda)}$ where $\ell(\cdot)$ is a polynomial in $\lambda$,
has two phases:

* Commitment phase:
the committer who has a message $X \in \{0, 1\}^{\ell(\lambda)}$
samples some random
coins $r \getr \{0, 1\}^\lambda$, and computes
the commitment
$\widehat{X} \leftarrow {\sf comm}(X, r)$.
It sends
the commitment $\widehat{X}$ to the receiver.

* Open phase: The committer sends the pair $(X,r)$ to the receiver.
The receiver outputs “accept” if ${\sf comm}(X, r) = \widehat{X}$;
otherwise, it outputs “reject”.

In our protocol, we require that the commitment scheme must satisfy the following two properties.

* Perfect binding: for any $X\neq X'$, and for any $r, r'$, it must be that

\[{\sf comm}(X,r)\neq {\sf comm}(X', r').\]

* Computationally hiding: for any $X$ and $X'$, it must be that

\[\{{\sf comm}(X,r), r\getr \{0, 1\}^\lambda \}
\equiv_c \{{\sf comm}(X',r), r\getr \{0, 1\}^\lambda\},\]

$\equiv_c$ denotes computational indistinguishability.

§.§.§ Shamir Secret Sharing

In our final protocol, each user identity will split its bid
into $m$ shares, one for each miner, using
a $t$-out-of-$m$ Shamir secret sharing scheme.
Henceforth let $\mathbb{F}$ denote some finite field.
A $t$-out-of-$m$ Shamir secret sharing
consists of two algorithms, ${\sf share}$ and ${\sf reconstruct}$.

* share takes as an input a secret $s \in \mathbb{F}$,
and outputs $m$ shares $(s_1,\dots,s_m) \in \mathbb{F}^m$ of the secret.

* reconstruct takes as input a set $I \subseteq [m]$,
and the corresponding shares $\{s_i\}_{i\in I}$, and outputs the corresponding secret if and only if $|I|\geq t$. Otherwise, the algorithm returns $\bot$.

A $t$-out-of-$m$ secret sharing satisfies the following two properties:

* Correctness: For any secret $s$ and any set $I\subseteq[m]$ such that $|I|\geq t$, it must be that

\[\Pr[
(s_1,\dots,s_m)\leftarrow {\sf share}(s): {\sf reconstruct}(I,\{s_i\}_{i\in I}) = s

* Security: For any two secret $s$ and $s'$, and for all set $I\subseteq[m]$ such that $|I|\leq t-1$, it must be that

\[\{\{s_i\}_{i\in I}:(s_1,\dots,s_m)\leftarrow {\sf share}(s)\}\equiv \{\{s_i\}_{i\in I}:(s_1,\dots,s_m)\leftarrow {\sf share}(s')\}.\]

where $\equiv$ denotes identically distributed. In addition, Shamir secret sharing also satisfies the following properties.
For any set $I$ such that $|I| < t$,

\[\{\{s_i\}_{i\in I}:(s_1,\dots,s_m)\leftarrow {\sf share}(s)\} \equiv \{\{u_i\}_{i \in I}: u_i\text{ uniformly randomly chosen from } \F\}.\]

§.§.§ Honest-Majority Multi-CRS NIZK

In our protocol, user identities will need to rely on zero-knowledge proofs to prove that they have correctly shared their bids.
We will use a non-interactive zero-knowledge proof (NIZK).
Since we assume the majority of the miners are honest,
NIZK can be instantiated without a common reference string (CRS),
using an honest-majority multi-CRS NIZK scheme <cit.>.

Specifically, every miner $j \in [m]$ acts as a CRS contributor, and
posts a CRS denoted $\crs_j$ to the broadcast channel.
For any miner $j'$ who did not post a CRS, we treat
its $\crs_{j'}$ as $0$.
Given the collection of all CRSes $\{\crs_j\}_{j \in [m]}$,
a prover can prove an NP statement
given a valid witness.

As long as a majority of the miners (i.e., CRS contributors) are honest,
the NIZK scheme satisfies completeness, zero-knowledge, and simulation sound extractability, as defined below.

For an NP language $L$, let $\mcal{R}_L(\stmt,w)$ denote the NP relation corresponding to the language $L$, i.e., $\stmt\in L$ if and only if there exists a $w$ such that $\mcal{R}_L(\stmt,w)=1$.
An honest-majority multi-CRS NIZK with $m$ CRS contributors for an NP language $L$, parameterized with a security parameter $\secu$, consists of the following algorithms, where part of the definition is taken verbatim from Guo, Pass, and Shi <cit.>.

* $\crs \leftarrow {\sf K} (1^{\secu})$: each CRS contributor $j\in[m]$ runs ${\sf K}(1^{\secu})$ to generate a CRS $\crs_j$. now the user identities also has to be the observer of the broadcast channel

* $\tau \leftarrow {\sf P}(\{\crs_j\}_{j\in[m]}, \stmt, w)$: given a statement $\stmt$ and a witness $w$ such that $\mcal{R}_L(\stmt,w) = 1$, and the set of all CRSes denoted $\{\crs_j\}_{j\in[m]}$, compute a proof denoted $\pi$.

* $\{0,1\}\leftarrow {\sf V} (\{\crs_j\}_{j\in[m]}, \stmt, \pi)$: given a statement $\stmt$, the set of all CRSes $\{\crs_j\}_{j\in[m]}$, and a proof $\pi$,
the verifier algorithm ${\sf V}$ outputs either $0$ or $1$ denoting either reject or accept.

* $(\widetilde{\crs}, \tau) \leftarrow\widetilde{\sf K}(1^{\secu})$: a simulated CRS generation algorithm that generates a simulated $\widetilde{\crs}$ and a trapdoor $\tau$.

* $\pi \leftarrow \widetilde{\sf P}(\stmt, \{\widetilde{\crs}_j\}_{j\in[m]}, \{\tau_j\}_{j\in H})$ where $H\subseteq [m]$ and $|H| \geq \lfloor \frac{m}{2}\rfloor + 1$: a simulated prover algorithm produces a proof for the statement $\stmt$ without any witness, and the simulated prover has to have access to at least $\lfloor \frac{m}{2}\rfloor + 1$ number of trapdoors.

Henceforth, we use $\mcal{A}^{\mcal{O}(\cdot)}(x)$ to
mean that $\algA$ is given oracle access to
the oracle $\mcal{O}(\cdot)$.

denote the output of $\A$ on input $x$ with the oracle access to ${\sf O}(\cdot)$.
We say that an adversary $\mcal{A}$ with the oracle access to the honest key generation oracle ${\sf K}$ is minority-constrained if and only if it outputs a set  $\{\crs_j\}_{j\in[m]}$ such that at least $\lfloor\frac{m}{2}\rfloor + 1$ out of $m$ entries are generated by ${\sf K}$ during its interaction with $\mcal{A}$.

Next, we give the security properties we want from the NIZK.

Completeness says that an honest prover can always produce a proof
that verifies, if it knows a valid witness to the statement.
completeness requires that for every $\secu$,
for any set of CRSes $\{\crs_j\}_{j \in [m]}$
where every $\crs_j$ is in the support of ${\sf K}(1^{\secu})$,
for every
statement ${\sf stmt}$ and witness $w$
such that $\mcal{R}_L({\sf stmt}, w) = 1$,
with probability $1$, the following holds:
$\pi \leftarrow {\sf P}(\{\crs_j\}_{j \in [m]},  \stmt, w)$,
it must be that
${\sf V}(\{\crs_j\}_{j \in [m]}, \stmt, \pi) = 1$.

Completeness requires that with all but negligible probability, the proof generated with a correct witness $w$ will be accepted by the verifier algorithm.
Formally, for any non-uniform probabilistic polynomial time () minority-constrained adversary $\A$, there exists a negligible function $\negl(\cdot)$, such that

\begin{align*}
\begin{array}{ll}
(\{\crs_j\}_{j \in [m]}, \stmt, w) \leftarrow \A^{\sf K}(1^\secu),  \
\pi \leftarrow {\sf P}(\{\crs_j\}_{j \in [m]},  \stmt, w):
\begin{array}{ll}
\mcal{R}_L(\stmt,w) = 1
\text{ but } \\[2pt]
{\sf V}(\{\crs_j\}_{j \in [m]}, \stmt, \pi) = 0
\end{array}
\end{array}
\right]\\
\leq &\negl(\secu).
\end{align*}

An honest-majority multi-CRS NIZK system satisfies zero knowledge iff the following properties hold.
First, we require that simulated reference strings are indistinguishable from real ones,
for every non-uniform $\A$, there exists a negligible function $\negl(\cdot)$, such that

\[
\left|\Pr\left[\crs \leftarrow {\sf K}(1^\secu): \A(1^\secu, \crs) = 1\right]
\Pr\left[(\widetilde{\crs}, \tau) \leftarrow
\widetilde{\sf K}(1^\secu): \A(1^\secu, \widetilde{\crs}) = 1\right]\right| \leq \negl(\secu).
\]

Moreover, we require that
as long as the majority of the CRSes are honestly generated, then
any efficient adversary cannot distinguish

an interaction with a real prover
using real witnesses to prove statements
and an interaction with a simulated prover who proves statements without using witnesses —
even if $\A$ obtains the trapdoors of the simulated CRSes.

More formally, let $\A^{\widetilde{\sf K}}$ denote
and adversary $\A$ who is allowed to call the simulated key generation
algorithm $\widetilde{\sf K}(1^{\secu})$ multiple times.
We say that $\A$ is minority-constrained,
if among the set of CRSes $\{\crs_j\}_{j \in [m]}$
output by $\A$, the majority of them are CRSes
returned to from ${\sf K}$.
We want that
for any non-uniform minority-constrained adversary $\A$,
there exists a negligible function $\negl(\cdot)$ such that

\begin{align*}
&\Big| \Pr\left[
(\{\crs_j\}_{j \in [m]}, \stmt, w) \leftarrow \A^{\widetilde{\sf K}}(1^\secu),
\pi \leftarrow {\sf P}(\{{\crs}_j\}_{j \in [m]}, \stmt, w):
\A(\pi) = 1
\text{ and } \mcal{R}_L(\stmt,w) = 1
\right]\\
\Pr\left[
(\{{\crs}_j\}_{j \in [m]}, \stmt, w)
\leftarrow \A^{\widetilde{\sf K}}(1^\secu),
\pi \leftarrow \widetilde{\sf P}(\{{\crs}_j\}_{j \in [m]},
\overrightarrow{\tau}, \stmt):
\A(\pi) = 1 \text{ and } \mcal{R}_L(\stmt,w) = 1
\right]\Big| \\
\leq &\negl(\secu)
\end{align*}

where $\overrightarrow{\tau}$
is the following vector:
for every CRS in the set  $\{{\crs}_j\}_{j \in [m]}$
that is output by the simulated key generation algorithm $\widetilde{{\sf K}}$, the vector $\overrightarrow{\tau}$
includes its corresponding trapdoor.
Note that there are at least $\lfloor\frac{m}{2}\rfloor + 1$ entries in $\overrightarrow{\tau}$
since $\A$ is minority-constrained.

Simulation soundness.
Intuitively, simulation soundness requires that even though an $\A$
may adaptively interacts with a simulated prover
and obtain simulated proofs of false statements, if $\A$ ever produces
a fresh proof for some purposed statement $\stmt$,
then $\stmt$ must be true except with negligible probability.
Actually we are not using simulation soundness in the proof?

More formally, an honest-majority multi-CRS NIZK system satisfies simulation soundness
iff for any non-uniform minority-constrained adversary $\A$,
there exists a negligible function $\negl(\cdot)$,
such that the following holds:

\[
\Pr\left[
\begin{array}{ll}
\left(\{\crs_j\}_{j \in [m]}, \stmt, \pi\right)
\leftarrow \A^{\mcal{O}(1^\secu, \cdot)}(1^\secu):
\begin{array}{ll}
(\stmt, \pi)
\text{ not output from $\mcal{O}(1^\secu, \cdot)$, and} \\[2pt]
\text{ $\stmt \notin
L$ but ${\sf V}(\{\crs_j\}_{j \in [m]}, \stmt, \pi) = 1$}
\end{array}
\end{array}
\right] \leq \negl(\secu)
\]

where $\mcal{O}(1^\secu, \cdot)$ denotes the following oracle:

* Upon receiving crs ${\tt gen}$ query from $\A$, it runs $(\crs, \tau) \leftarrow \widetilde{{\sf K}}(1^\secu)$;
it records the trapdoor $\tau$ and returns $\crs$ to $\A$.
Note that $\A$ can make such ${\tt gen}$
queries multiple times to generate
CRSes for multiple nodes; and it can choose a subset of these
to include in the output $\{\crs_j\}_{j \in [m]}$.

* Then, at some point, $\A$ outputs $\{\crs_j\}_{j \in [m]}$ — this has to be part of $\A$'s final output.
Since $\A$ is minority-constrained, at least $\lfloor\frac{m}{2}\rfloor + 1$ number of entries in $\{\crs_j\}_{j \in [m]}$ must be generated by $\widetilde{\sf K}$.

* At this moment, $\A$ can send $({\tt prove}, \stmt)$
to the oracle $\mcal{O}$ multiple times.
For each such invocation, the oracle
call $\widetilde{\pi} \leftarrow \widetilde{{\sf P}}(\{\crs_j\}_{j \in [m]}, \overrightarrow{\tau}, \stmt)$
and return the resulting $\widetilde{\pi}$ to $\A$,
where $\overrightarrow{\tau}$
is the following vector: for every CRS in the set  $\{{\crs}_j\}_{j \in [m]}$
that is output by $\widetilde{{\sf K}}$, the vector $\overrightarrow{\tau}$
includes its corresponding trapdoor.
Note that $\overrightarrow{\tau}$ must contain at least $\lfloor\frac{m}{2}\rfloor + 1$ such trapdoors
since $\A$ is minority-constrained.

Simulation sound extractability.

Intuitively, simulation sound extractability requires that even though an $\A$
may adaptively interact with a simulated prover
and obtain simulated proofs of false statements, if $\A$ ever produces
a fresh proof for some purposed statement $\stmt$,
then except with negligible probability, some extractor must be able to extract a valid witness from the proof, using an extraction key
that is produced during a simulated setup procedure.

More formally,
an honest-majority multi-CRS NIZK system satisfies simulation sound extractability
iff there exist
algorithms $\widetilde{{\sf K}}_0$ and $\mcal{E}$
such that the following is satisfied:

* $\widetilde{{\sf K}}_0(1^{\secu})$ outputs a triple denoted $(\widetilde{\crs}, \tau, \ek)$
where the first two terms have an output distribution
identical to that of $\widetilde{{\sf K}}(1^{\secu})$; and

* for any non-uniform minority-constrained adversary $\A$,
there exists a negligible function $\negl(\cdot)$,
such that the following holds:

\begin{align*}
\begin{array}{ll}
\begin{array}{l}
\left(\{\crs_j\}_{j \in [m]}, \stmt, \pi\right)
\leftarrow \A^{\mcal{O}(1^\secu, \cdot)}: \\
w \leftarrow \mcal{E}(\{\crs_j\}_{j \in [m]}, \overrightarrow{\ek}, \stmt, \pi)
\end{array}
\begin{array}{ll}
(\stmt, \pi)
\text{ not output from $\mcal{O}(1^\secu, \cdot)$, and} \\[2pt]
\text{ $\mcal{R}_L(\stmt, w) = 0$ but ${\sf V}(\{\crs_j\}_{j \in [m]}, \stmt, \pi) = 1$}
\end{array}
\end{array}
\right]\\
\leq &\negl(\secu),
\end{align*}

where $\mcal{O}(1^\secu, \cdot)$ is the following oracle:

* Upon receiving crs generation query ${\tt gen}$ from $\A$, it runs $(\crs, \tau, \ek) \leftarrow \widetilde{{\sf K}}_0(1^\secu)$;
it then records $\tau$ and returns $\crs$ and $\ek$ to $\A$.

* Then, at some point, $\A$ outputs $\{\crs_j\}_{j \in [m]}$ — this set
of CRSes must be consistent with the CRSes in $\A$'s final output.
$\A$ is required to be minority-constrained,
meaning that at least $\lfloor\frac{m}{2}\rfloor + 1$ number of entries in $\{\crs_j\}_{j \in [m]}$ must be output from $\widetilde{\sf K}_0$.

At this moment, define the following notation:

* $\overrightarrow{\tau}$
is the following vector: for every CRS in the set  $\{{\crs}_j\}_{j \in [m]}$
that is output by $\widetilde{{\sf K}}_0$, the vector $\overrightarrow{\tau}$
includes its corresponding trapdoor.
Note that ${\overrightarrow{\tau}}$ must contain at least $\lfloor\frac{m}{2}\rfloor + 1$ such trapdoors
since $\A$ is minority-constrained.

* Similarly, the notation $\overrightarrow{\ek}$
the following vector:
for every CRS in the set  $\{{\crs}_j\}_{j \in [m]}$
that is output by $\widetilde{{\sf K}}_0$, the vector $\overrightarrow{\ek}$
includes its corresponding extraction key $\ek$ included in the triple.

* At this moment, $\A$ is allowed to send $({\tt prove}, \stmt)$
to the oracle multiple times; and for each such invocation, the oracle would
call $\widetilde{\pi} \leftarrow \widetilde{{\sf P}}(\{\crs_j\}_{j \in [m]}, \overrightarrow{\tau}, \stmt)$
and return the resulting $\widetilde{\pi}$ to $\A$.

Groth and Ostrovsky <cit.> showed how to construct a multi-CRS NIZK from
standard cryptographic assumptions, resulting in the following theorem.

Assume the existence of enhanced trapdoor permutations.
Then, there exists
a multi-CRS NIZK system that satisfies completeness, zero-knowledge,
and simulation sound extractability.

§.§ Protocol Description

Before the miners start the multi-party computation protocol, they have to reach consensus on which user identities are participating.
This is done by the following protocol.

Protocol $\Pi_{\rm agreement}$

Parameters: Let $m$ be the number of miners.

* Each user sends its (possibly multiple) identities to every miner $j\in[m]$.

* Let ${\sf ID}_j$ denote the set of identities miner $j$ received.
Every miner $j$ broadcasts to all miners the set  ${\sf ID}_j$.

* Let ${\sf ID}$ be the set of identities that appear in a majority number of ${\sf ID}_j, j\in[m]$. Every miner outputs ${\sf ID}$.

At the end of the agreement protocol $\Pi_{\rm agreement}$, the miners reach consensus on the set ${\sf ID}$ of user identities that participate the protocol.
Note that when the number of colluding miners is less than half, each honest user identity must appear in ${\sf ID}$.

Once the miners agree on the set ${\sf ID}$ of the user identities, they can proceed to the following protocol.

Below we give the final multi-party computation protocol $\pmec$.
Roughly speaking, the user identities first secret share
their bids among the miners and prove in zero-knowledge the correctness
of the sharings.
Then, the miners run an MPC protocol
using the shares they have received as inputs.
The MPC protocol will securely compute the
rules of the auction, and determine which bids are confirmed
and how much each confirmed bid pays.
We will use the honest-majority multi-CRS NIZK defined in <ref>.
Moreover, we will describe our protocol $\pmec$ assuming that players have access to an ideal functionality
$\mcal{F}_{\rm TFM}$ which computes the rules of the auction —
the formal description of $\mcal{F}_{\rm TFM}$
will be provided at the end of $\pmec$.
The ideal functionality
$\mcal{F}_{\rm TFM}$ can be realized using
standard techniques — in particular, we can use
an MPC protocol that secures against minority corruptions
providing fairness and guaranteed output <cit.>.
Finally, our $\pmec$ protocol also
makes use of a perfectly binding and computationally hiding
commitment scheme denoted ${\sf comm}$.

Without loss of generality, we assume that each bid is encoded as an element of a finite field $\F$.
We will give the protocol $\pmec$ assuming that players have the access to the ideal functionalities $\zkb$ and $\mcal{F}_{\rm TFM}$ (described at the end of the protocol).
The ideal functionalities can later be replaced with real-world protocols: $\zkb$ can be replaced by Pass's protocol (<ref>) and $\mcal{F}_{\rm TFM}$ can be instantiated using GMW <cit.>.

During the protocol, miners will keep track of a set $\mcal{C}$ containing the set of user identities who have misbehaved.
The bids of those in $\mcal{C}$ will be treated as $0$.
All miners have the same view of $\mcal{C}$ since
$\mcal{C}$ is determined using only messages sent on the broadcast channel.

Protocol $\pmec$ instantiating $\fmec$

Parameters: Let $\secu$ be the security parameter.
Let $m$ be the number of miners running the protocol.
Let $t = \lceil\frac{m}{2}\rceil$ be the reconstruction threshold of secret sharing.
Let ${\sf ID}$ be the agreed-upon set of user identities that are participating in the protocol.
Let $\mcal{C}$ be an initially empty set.

Building blocks:

* Shamir secret sharing.

* A perfectly binding, computationally hiding commitment scheme ${\sf comm}$.

* An honest-majority multi-CRS non-interactive zero-knowledge proof (NIZK) system denoted as $\NIZK:=({\sf K}, {\sf P}, {\sf V})$.

Input: Each user identity $i\in{\sf ID}$ has a bid $b_i\in\mathbb{F}$. Each miner has no input.

Sharing phase

* Each miner $j$ runs ${\sf NIZK.K}(1^\secu)$ and obtains $\crs_j$. Each miner $j$ broadcasts $\crs_j$ to all user identities and miners.
If a miner $j$ fails to broadcast $\crs_j$, set $\crs_j = {\bf 0}$.
Let $\CRS:= \{\crs_j\}_{j\in[m]}$.

Each user identity $i$ splits $b_i$
into $m$ secret shares using a $t$-out-of-$m$ secret sharing scheme.
Let $X_{i,j}$ denote the $j$-th share of $b_i$. Let $\widehat{X}_{i,j} = {\sf comm}(X_{i,j}, r_{i,j})$ where the $r_{i,j}$s are fresh randomness.
Broadcast the commitments of shares $\{\widehat{X}_{i,j}\}_{j\in[m]}$ to the miners.

If a user identity $i$ fails to broadcast all the commitments,
each miner adds $i$ to $\mcal{C}$.

Each user identity $i\in{\sf ID}$ calls $\pi_i\leftarrow {\sf NIZK.P}({\sf CRS, stmt}_i, w_i)$
with the statement $\stmt_{i} = (i,\{\widehat{X}_{i,j}\}_{j\in[m]})$ and the witness $w_i = (b_i, \allowbreak \{X_{i,j}, r_{i,j}\}_{j\in[m]})$ to prove that

* For each $j\in[m]$, $(X_{i,j}, r_{i,j})$ is the correct opening of $\widehat{X}_{i,j}$;

* $\{X_{i,j}\}_{j\in[m]}$ forms a valid $t$-out-of-$m$ secret sharing of $b_i$.

Each user identity $i$ broadcasts $\pi_i$.

* For each user identity $i$, if it fails to broadcast $\pi_i$, or ${\sf NIZK.V}(\CRS, \stmt_i,\pi_i)$ outputs $0$, i.e., the verifier algorithm rejects the proof, each miner adds $i$ to $\mcal{C}$.

Each user identity $i\in{\sf ID}$ sends $(X_{i,j},r_{i,j})$ to miner $j$ for all $j\in[m]$.

Each miner $j$ does the following: for all $i\in{\sf ID}\setminus\mcal{C}$, if it receives a message $(X_{i,j},r_{i,j})$ that is a correct opening with respect to $\widehat{X}_{i,j}$, record $(X_{i,j},r_{i,j})$ and broadcast $({\sf ok}, i, j)$. Otherwise, broadcast $({\sf complain}, i, j)$ to complain about user identity $i$.

Each user identity $i\in {\sf ID}$ does the following: for all $j$ such that there is a complaint $({\sf complain}, i,j)$ from miner $j$ at Step <ref>, user identity $i$ broadcasts the corresponding opening $(i,j,X_{i,j},r_{i,j})$.
Every miner records every correct opening
$(i,j,X_{i,j},r_{i,j})$ it hears.

* If there exists a complaint $({\sf complain}, i,j)$ from miner $j$ in Step <ref> such that user identity $i$ has not broadcast the correct opening $(i, j, X_{i, j}, r_{i, j})$, each miner adds $i$ to $\mcal{C}$.

Computation Phase Miners invoke $\mcal{F}_{\rm TFM}$ parameterized with ${\sf ID}$, $\mcal{C}$, the commitments of shares $\{\widehat{X}_{i,j}\}_{i\in{\sf ID\setminus\mcal{C}}, j\in[m]}$, and the transaction fee mechanism.
Each miner outputs the output of $\mcal{F}_{\rm TFM}$.

Ideal Functionality $\mcal{F}_{\rm TFM}$

Parameters: The sets ${\sf ID}$ and $\mcal{C}$, as well as commitments of shares $\{\widehat{X}_{i,j}\}_{i\in{\sf ID}\setminus\mcal{C}, j\in[m]}$ and the transaction fee mechanism.

Input: Each miner $j$ has input $\{(X_{i,j}, r_{i,j})\}_{i\in {\sf ID}\setminus\mcal{C}}$, where $(X_{i,j}, r_{i,j})$ is a correct opening of $\widehat{X}_{i,j}$.

* Each miner sends its input $\{(X_{i,j}, r_{i,j})\}_{i\in {\sf ID}\setminus\mcal{C}}$ to $\mcal{F}_{\rm TFM}$.

* For each $j\in[m]$, the functionality $\mcal{F}_{\rm TFM}$ checks if $(X_{i,j}, r_{i,j})$ is an correct opening of $\widehat{X}_{i,j}$ for all $i\in{\sf ID}\setminus\mcal{C}$.

* For each $i\in{\sf ID}\setminus\mcal{C}$, the functionality reconstructs $b_i$ only using those correct openings.
If the reconstruction fails, treat $b_i$ as $0$.
For each $i\in\mcal{C}$, set $b_i = 0$.

* Let $\bids = \{b_i\}_{i\in{\sf ID}}$ denote all the bids. The functionality then computes the output of the transaction fee mechanism on input $\bids$ and sends the output to every miner.

If the commitment scheme ${\sf comm}$ is perfectly binding and computationally hiding, and the honest-majority multi-CRS  satisfies completeness, zero-knowledge and simulation sound extractability,
then $\pmec$ securely realizes $\fmec$ (See <ref>) in the $\mcal{F}_{\rm TFM}$-hybrid model as long as the number of colluding miners is less than $\frac{m}{2}$.

§.§ Proof of <ref>

Below we use $\equiv$ to denote identically distributed and $\equiv_c$ to denote computationally indistinguishability.
Let ${\sf Exp}_{\mcal{A}}^{\sf Real}$
denote the joint distribution
of the honest parties and the adversary $\A$'s view in the real-world experiment, where
the adversary $\A$ who controls a subset of the miners and users
interact with honest parties
running the real-world protocol $\pmec$.
Let ${\sf Exp}_{\mcal{S}}^{\sf Ideal}$
denote the joint distribution
of the honest parties and the ideal-world adversary $\mcal{S}$'s
view in the ideal-world experiment, where
$\mcal{S}$ controls
the same subset of miners and users,
and all parties interact with $\fmec$ to compute the outputs.
We want to show that
${\sf Exp}_{\mcal{A}}^{\sf Real}$ and
${\sf Exp}_{\mcal{S}}^{\sf Ideal}$