Tl;dr

• When preconfirmation providers open a commitment to claim rewards, they now have to prove in zero-knowledge that the bidder could also have opened it.

• The proof aligns provider incentives to act honestly in the protocol, and not make malicious commitments that they can reveal only when convenient.

• This extremely performant proof with only ~0.122 ms proving time and highly efficient proof verification is now available on mev-commit and can be used in low latency applications.

Introduction

The mev-commit protocol allows so-called bidders to send bids to providers, where bids are for inclusion of transactions in a blockchain (possibly with additional execution guarantees), and providers can issue commitments for these bids. When a commitment is issued and the corresponding transactions are included and executed as desired, the bidder pays the bid amount to the provider, if the commitment guarantee is violated, the provider needs to pay the bidder a compensation amount. More details on mev-commit can be found in the mev-commit whitepaper [1].

As described in [2], mev-commit incorporates end-to-end privacy such that when a commitment is issued, only the corresponding bidder and provider learn to which bid a commitment refers, the commitment contents are completely hidden from external parties. To enforce the payments, commitments needs to be publicly opened after the corresponding block has been added to the blockchain, such that it can be publicly verified whether the commitment has been fulfilled or violated. This means in case the commitment is fulfilled, the provider has to publicly open the commitment to get paid the bid amount, whereas if the commitment is violated, the bidder has to publicly open it to receive the compensation from the provider.

In the newest release of mev-commit, zero-knowledge proofs have been introduced to increase the robustness of the commitments. In a nutshell, when providers publicly open a commitment, they now have to prove in zero-knowledge that the corresponding bidder could also have opened it. This prevents griefing attacks in which a malicious provider issues invalid commitments that cannot be opened by the bidder, but could still be opened by the provider. To minimize latency impacts, a highly efficient zero-knowledge protocol is used. The rest of this article describes this protocol in more detail.

DPCOM Without Zero-Knowledge Proof

To obtain the functionality that allows both the bidder and the provider to open the commitment, mev-commit uses a so-called dual-phase commitment (DPCOM) scheme. This is instantiated with a non-interactive key exchange (NIKE) protocol and works as follows: Each provider $P$ has published a public key $P.\mathrm{NIKE}.pk$, where the corresponding secret key $P.\mathrm{NIKE}.sk$ is known to $P$, and each bid $B$ contains a fresh public key $B.\mathrm{NIKE}.pk$, where the bidder knows the corresponding secret key $B.\mathrm{NIKE}.sk$. To open a (honestly generated) commitment, the shared key $\mathrm{SharedKey}(P.\mathrm{NIKE}.pk, B.\mathrm{NIKE}.sk) = \mathrm{SharedKey}(B.\mathrm{NIKE}.pk, P.\mathrm{NIKE}.sk)$ is used (that can be computed by both the bidder and the provider).

Without the zero-knowledge proof, a malicious provider can, instead of generating the commitment as described above, craft a valid “fake” commitment such that the opening is not the shared key as intended, but instead some other value only known to that provider. This means the commitment cannot be opened by the bidder and is therefore useless for the bidder. However, the provider can later decide to open the commitment and get paid even though the bidder did not actually know about the commitment up until this point and could not have opened it to receive the compensation in case of a violation.

High-Level Solution with Zero-Knowledge Proof

To prevent providers from creating and later opening fake commitments, the new release of mev-commit requires the provider to prove in zero-knowledge that the correct shared key was used when opening a commitment. This means a provider can only open commitments that have been generated correctly and could also have been opened by the bidder. More concretely, we require the public key of the bid $B.\mathrm{NIKE}.pk$ to be signed together with the bid by the bidder and stored with the signature inside the commitment on chain and require the provider to prove the following statement in zero-knowledge as part of a commitment opening:

I know a value $P.\mathrm{NIKE}.sk$ such that (i) $P.\mathrm{NIKE}.sk$ is the secret key corresponding to my $P.\mathrm{NIKE}.pk$, and (ii) the commitment opening information used is equal to $\mathrm{SharedKey}(B.\mathrm{NIKE}.pk, P.\mathrm{NIKE}.sk)$.

When a provider opens a commitment, the smart contract on the mev-commit chain checks that the ZK proof is valid, that $P.\mathrm{NIKE}.pk$ indeed matches the provider’s public key, that $B.\mathrm{NIKE}.pk$ matches what was signed by the bidder as part of the revealed bid, and that this signature is valid. If one of these checks fails, the commitment is not opened and no payments are triggered.

Discussion

Before diving into the technical details, we here discuss some design choices.

Only Proving When Opening

The described solution prevents providers from opening maliciously crafted commitments that bidders cannot open. It does not prevent, however, to post such commitments in the first place. The reason for this approach is two-fold:

1. Posting commitments that nobody can open essentially corresponds to spam/DoS and does not allow for an actual attack where bidders lose funds. This type of spam cannot be prevented cryptographically anyway, since a provider can set up a bidder account, issue a meaningless bid, commit to it, and never open the commitment. Since both bidder and provider (the same entity) can choose to not open, this is a legitimate behavior, and has the same effect as the provider crafting a commitment that is impossible to open. Preventing such spam thus is disincentivized by transaction fees instead.

2. Making commitments is time critical, while opening commitments is much less so. We thus want to perform as little checks as possible when committing. Only making ZK proofs when opening commitments thus keeps these operations out of the time-critical path.

No Proofs for Bidder Opening

The described solution only requires the provider to generate a proof of a valid commitment when opening, while bidders can open without any such proofs. This is not necessary, since bidders can not cause any harm by tampering with the process: Bidders could choose $B.\mathrm{NIKE}.pk$ such that they do not know the corresponding secret key and thus cannot open the commitment. But in this case, the provider could still open, and the bidder not being able to has the same effect as the bidder choosing to not open, which is an allowed behavior. The commitments are generated by the providers, so invalidly generated commitments could only be opened by the bidder if the bidder colludes with the provider to obtain the fake opening information. But in this case, it is the bidder’s own fault and there is nobody to be protected.

Instantiation of ZK Proof

The NIKE scheme used in mev-commit corresponds to Elliptic Curve Diffie-Hellman (ECDH). More concretely, a group $G$ of points on that curve is considered, where $g$ is a generator of this group and the group has order $p$. A NIKE secret key then corresponds to an integer modulo $p$, $a \in \mathbb{Z}/p\mathbb{Z}$, and the corresponding public key is $g^a$. For another key pair $b, g^b$, the shared key is then $g^{ab}$, which can be computed by both parties using $(g^a)^b = g^{ab} = (g^b)^a$.

When the provider’s public key is $g^a$ and the bid’s public key is $g^b$, the high-level statement that needs to be proven by the provider in ZK thus in this special case translates to

I know a value $a$ such that (i) $a$ is the discrete logarithm of my NIKE public key $g^a$, and (ii) the commitment opening information used is equal to $(g^{b})^a$.

Sigma Protocols Introduction

The type of statement that needs to be proven in this case can be proven very efficiently using so-called sigma protocols. We here give a short introduction following the formalism of Maurer [3]. We first describe the basic interactive sigma protocols, in which the prover and verifier need to exchange three messages, and then describe below how to make such protocols non-interactive using the Fiat-Shamir transformation [4].

Let $\varphi : G \to H$ be a group homomorphism between group $(G, +)$ and $(H, \cdot)$. A sigma protocol allows a prover to prove knowledge of a preimage of $\varphi$, i.e., for a given value $y \in H$ (known to both the prover and verifier), the prover proves knowledge of a value $x \in G$ such that $\varphi(x) = y$. The protocol further considers a so-called challenge space $\mathcal{C} \subseteq \mathbb{N}$ of natural numbers and works as depicted in Figure 1 below.

It has been shown by Maurer [3, Theorem 3] that this protocol is “secure” (more precisely, has special soundness and is special honest verifier zero-knowledge) if values $l \in \mathbb{Z}$ and $u \in G$ are known such that

• $\forall c_1, c_2 \in \mathcal{C} : c_1 \neq c_2 \Rightarrow \mathrm{gcd}(c_1 - c_2, l) = 1$,

• $\varphi(u) = y^l$, and

• $1/\lvert\mathcal{C}\rvert$ is negligible.

Opening Proof as Sigma Protocol

We now show how the statement the provider needs to prove can be proven in the model described above. Recall that for publicly known $g$, provider NIKE public key $A$, bid public key $B$, and commitment opening information $C$ (all in group $G$), the provider needs to prove knowledge of $a$ such that

To this end, consider the group homomorphism

The statement the provider needs to prove is thus equivalent to proving knowledge of a preimage of $y = (A, C)$, i.e., of a value $a$ such that $\varphi(a) = (A, C)$.

Note that $\varphi$ is indeed a group homomorphism since

Furthermore, the conditions required for security are satisfied when $\mathcal{C}$ is a sufficiently large subset of $\mathbb{Z}/p\mathbb{Z}$ and for values $l = p$ and $u = 0$:

• For all distinct $c_1, c_2 < p$, $c_1 - c_2$ and $p$ are coprime since $p$ is prime and $-p < c_1 - c_2 < p$.

• $\varphi(u) = \varphi(0) = (g^0, B^0) = (1, 1) = (A^p, C^p) = (A,C)^p$ since $G$ is of order $p$.

• $1/\lvert\mathcal{C}\rvert$ is negligible if $\mathcal{C}$ is sufficiently large.

Making the Proof Non-Interactive

Since we want to verify the proof of the provider inside a smart contract call, we do not want to use an interactive protocol where the provider exchanges messages with a verifier, but instead a non-interactive proof that can be verified directly by anyone (including the smart contract). The Fiat-Shamir transformation [4] allows to turn an interactive sigma protocol into a non-interactive proof. The basic idea is to replace the challenge $c$ from the verifier by the hash of $(y, a)$. This allows the prover to generate the full transcript of the proof (by first computing $a$, then computing $c = H(y,a)$, and finally computing $z$). Note that since $H$ typically outputs bitstrings, this requires a mapping from bitstrings to the challenge space $\mathcal{C} \subseteq \mathbb{N}$, which can be done in a straightforward way (e.g., let $l$ be the largest integer such that $2^l < p$ and interpret the first $l$ bits of the hash as an integer). It has been shown by Bernhard, Pereira, and Warinschi [5] that this transformation yields a secure ZK proof of knowledge (more precisely, the obtained protocol is zero-knowledge and simulation sound extractable) if $H$ is modeled as a random oracle.

Especially for non-interactive proofs, it is often desirable to bind a proof to the context in which it was used, to prevent proofs from being reused by third parties elsewhere. This can easily be accomplished by including a string describing the context in the value that is hashed, i.e., the prover computes the challenge $c = H(\mathtt{ctx}, y, a)$ with, e.g., $\mathtt{ctx} = \mathtt{"mev{-}commit\ opening, mainnet, v1.0"}$.

Implementation and Performance

The described zero-knowledge proof has been implemented in the mev-commit protocol in two separate places: The software for the provider node implements the logic for opening commitments and thus for generating the described zero-knowledge proofs. The proof verification is implemented inside the smart contract on the mev-commit chain such that whenever a provider submits a transaction to open a commitment, it must come with a ZK proof that is verified inside the smart contract and the opening is rejected if the verification fails.

A benchmark of the proof generation has been performed on a Mac M1 Pro. Generating a single zero-knowledge proof for the commitment opening takes on average only 0.122 milliseconds on this hardware. Figure 2 below shows a graph of the proving time for multiple iterations.

For the proof verification in the smart contract, around 32k gas is consumed. For comparison, the overall gas cost of the commitment opening transaction is around 488k gas. Hence, only less than 7% of the gas cost is attributed to the zero-knowledge proof verification. See Figure 3 for a graphical depiction. Note that commitment openings are executed on the mev-commit chain with a low gas price.

Overall, this shows that the employed zero-knowledge proof is highly efficient, adding almost no latency and only minimal additional gas cost.

Conclusion

To prevent a griefing attack from malicious providers, a highly efficient zero-knowledge proof has been implemented in the newest release of the mev-commit protocol. It requires providers who want to open a commit to prove in zero-knowledge that the commitment has been honestly generated and could therefore also have been opened by the bidder. The implementation adds almost no latency to the commitment opening and only minimal additional gas cost for verifying the proof in a smart contract on the mev-commit chain.

References

[1] Primev (2024). mev-commit whitepaper. https://primev.xyz/whitepaper

[2] Magri, B., Matt, C. (2024). Pioneering End-to-End Privacy for Intra-Block Commitments. Mirror. https://mirror.xyz/preconf.eth/iz2J0uTXHhl8DiAkG-VLLwvCp-8qcc_Z7A8_4rU0A3g

[3] Maurer, U. (2015). Zero-knowledge proofs of knowledge for group homomorphisms. Des. Codes Cryptogr. 77, 663–676. https://doi.org/10.1007/s10623-015-0103-5, https://crypto.ethz.ch/publications/files/Maurer15.pdf

[4] Fiat, A., Shamir, A. (1987). How To Prove Yourself: Practical Solutions to Identification and Signature Problems. In: Odlyzko, A.M. (eds) Advances in Cryptology — CRYPTO’ 86. Lecture Notes in Computer Science, vol 263. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47721-7_12

[5] Bernhard, D., Pereira, O., Warinschi, B. (2012). How Not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios. In: Wang, X., Sako, K. (eds) Advances in Cryptology – ASIACRYPT 2012. Lecture Notes in Computer Science, vol 7658. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34961-4_38