Proposal: Using DV clusters for encrypted transaction mempools

[Michal]

Main author: @olegjakushkin

Task

Idea: have a Shutter-alike mechanism for securing transaction data from builders used in Obol

Given

Here, we assume that each DV cluster knows a set of its active validators and keeps its state in a directed acyclic graph (DAG) controlled by a leader-based BFT and stored in Charon clients. We also assume that operators can exchange information and check the block that the consensus leader built. We also assume individual DV states are publicly inaccessible.

Background

There is an interesting application of DVs: harmful MEV avoidance by transaction body encryption. Encrypted mempools ensure TX publishers that the blocks published have their transactions included without ordering issues and other censorship.

Shutter’s approach to encrypted mempools utilizes committees called keypers who create a master public key mpk later used by transaction senders to encrypt their transactions. Each sender determines epoch i, when their transaction should be decrypted. In each epoch, the keypers publish an epoch decryption key k_i to reveal transactions.

Challenges

1. Shutter logic related:

   1. Pending transactions shall stay encrypted for more than one slot/epoch.

      In real life, transactions become outdated much later than in one epoch, so publishing a key for all pending transactions will make many messages that have not yet been processed vulnerable. For example, say we had 100 messages in a pool that should be included in block i. Unfortunately, not all of them can be added to a block, e.g. because of the gas limit. In the current solution, revealing the epoch key allows to decrypt all of the messages regardless of whether they have been included in a block or not. The remaining, non-included, messages are then susceptible to harmful MEV.

   2. Opening assumes transactions are first published in an encrypted format. In Ethereum, transactions are checked before being published as open-source data. To facilitate a structure similar to Shutter, there is a Proposer Builder Separation (PBS) concept in Ethereum. It allows proposers to sign and publish a block header before getting transaction bodies and publishing them. This, however, relies on the assumption that a signed block header has only valid transactions in it.

2. Keypers construction related:
   1. Using DVs as keypers directly increases incentives for their collusion as they could benefit from MEV.

Proposed solutions

In this section, we will describe 2 alternative approaches with trade-offs. In the first one, we assume that DV clusters act as keypers. In the latter, we take PBS as a blueprint and propose to instantiate it using distributed builders and relays.

Approach 1: DVs as Builders and relayers

For censorship resistance purposes, block creation and delivery speed in PBS are distributed by three different active parties: builders, relays, and proposers. In PBS, block production works as follows:

1. Builders gather transactions from sources in a non-encrypted way, composing a block prioritizing resulting profitability.
2. Builders send blocks to the relays they trust in a non-encrypted way.
3. Relays then show block headers to the proposers. Here, every relayer chooses a single block (the most profitable one) from the candidates created by builders and checks its validity before it sends the block header to the proposer.
4. A proposer can select a header from any relay and sign it.
5. A relay then broadcast that block contents onto the chain.

This makes

• Sources trust builders not to perform harmful MEV reordering.
• Builders trust relays under the risk of transactions MEV reordering.
• Proposers trust relays that block is valid.

PBS is widely used, yet trust assumptions in it mainly rely on the fact that given two identical network views builder that does not perform MEV reordering would reach the relay earlier than one that would.

MEV-Boost state Builders, Relays, (source: https://mevboost.pics/)

In this approach, we will investigate a construction of Builders and Relays on top of the DV infrastructure, such that a DV can be a Relay or a Builder. This allows:

• Builders to see not all of the Sources’ transaction bodies but selectively open only the most profitable ones available that can fit into a single block while keeping the block valid
• Relays to see not all of the Builders’ blocks but only the first valid, most profitable (giving the highest fee to the block proposer) block that arrived

Assumptions

By such construction, we will allow:

1. Sources to only partially trust Builders (tolerate a certain proportion (1/3) of faulty nodes in a builder-DV under BFT rules)
2. Builders to only partially trust Relays (tolerate a certain proportion (1/3) of faulty nodes in a relay-DV under BFT rules)
3. Trust assumptions for proposers are kept as in pure PBS.

Thus risks for PBS actors are reduced.

Note **that on small DV cluster sizes (less that 5-10 nodes) BFT implementations may have special rules on the amount of minimal tolerable faulty nodes.

Description

• A set of all DVs comprises subsets, i.e., DV_{builders} and DV_{relays}. Thus, the flow of data like in PBS would look as shown in the figure below:

Builders setup:

1. Each DV DV_{builders}^i \in DV_{builders} publishes to sources public key pk_b^i that sources would use in a threshold encryption scheme to encrypt the transaction bodies. (that key is generated in DKG)
2. Each DV DV_{builders}^i \in DV_{builders} hosts a Data Availability layer (DA) filled with encrypted transactions for all DV_{builders}^i nodes to see and be able to post new TXs into.
3. After a predefined time period T set by the DV configuration, or by inclusion into a block, transactions are marked as used or discarded by DV leader.

Relays setup:

1. Each DV DV_{relays}^j\in DV_{relays} publishes to builders a public key pk_r^j that builders would use in a threshold encryption scheme to encrypt the block bodies. (that key is generated in DKG)
2. Each DV DV_{relays}^j\in DV_{relays} hosts an inner Data Availability layer (DA) filled with encrypted blocks for all DV_{relays}^j nodes to see and be able to post new blocks into.
3. After a predefined time period T set by the DV configuration, or following a block’s publication or a missed slot, these blocks are then classified as either ‘used’ or ‘discarded’ by the DV leader.

Posting:

1. Each DV_{builders}^i gathers encrypted TXs from sources, and the leader of DV_{builders}^i orders TXs by maximizing profit and limiting their amount by gas available in the block under construction. (we assume that every encrypted transaction makes its gas limit public - only body stays encrypted).
2. DV_{builders}^i decrypts the minimal required set of transactions using sk_b^i (generated via DKG)
3. The leader of DV_{builders}^i tries to build a block
   • If block building out of the given set of TXs is not possible, the leader appeals to the DV to open more transactions to fill the gas.
   • If DV reaches a consensus, additional transactions will be opened
   • Such a loop happens until the block is built successfully.
4. Let known_i be a set of all relays known and trusted by the DV^i_{builders}. For each j \in known_i, the leader of DV_{builders}^i encrypts the block with pk_r^j and sends it to DV^j_{relays}.
5. Each relay DV_{relays}^j gathers encrypted block bodies from builders. The leader of DV_{relays}^j selects the most profitable block and establishes it with his DV committee which does threshold decryption to see its body. If the leader of DV_{relays}^j detects a bad block (in terms of verification), it repeats the block selection process.
6. The leader of DV_{relays}^j picks a block and makes its header available for proposers to pick and sign. Over a single slot time frame, new blocks can be selected and proposed; the header for signing is updated.

Opening:

• The proposer P signs a header of any DV_{relays}^j he deems most trusted and profitable. Asks its leader for decryption. The leader verifies that the signature was generated by the proposer P with his DV committee and uses threshold decryption to decrypt the block. The block gets published by the relay using their local beacon nodes and returned to the proposer.
• If P publishes another block, he will get slashed.

Simplified this process can be seen in the figure below:

Data flows

Such an approach allows for better censorship resistance and MEV reordering avoidance by:

• Making builders select the most profitable transactions in the “first” round; see their bodies in the “second” round. Thus minimal amount of transactions is viewed as a whole
• Making relays select the most profitable block available in the “first” round; see their bodies in the “second” round. Thus minimal amount of blocks is viewed as a whole

In general, this approach is similar to Shutter in the ideas of transaction encryption prior to decrypt and expands its ideas by then encrypting the block bringing its ideas more aligned with PBS.

Drawbacks

• Latency will increase, yet looking at the figure below, there is definitely at least 5-10 seconds of free time left in a slot for most of the current MEV-boost proposers.

current PBS bid selection by block proposers in a slot time frame (source: https://mevboost.pics/)

• Computational penalty:
  • encryption-decryption takes time
  • network communication takes time
  • BFT consensus reiteration takes time
• Only BFT security grantees can be provided (dependent on underlying DV nodes count, which is better than the current relay as a trusted party situation)
• Selection of the best relay is delegated to the block proposer

Approach results

The provided approach aims to keep the familiar to participants PBS architecture, make it more trustless, and pay with speed for it (as there is time that can be spent in block slots currently available). It is important to note that blocks are delivered to proposers in a complete, profit-maximized way. Censorship-resistance is achieved by builder-relay separation typical for PBS and enhanced by proposed blocks and transactions encryption. Typical PBS procedure of header signing by the publisher is kept in place, making this scheme require minimal changes to the proposer’s side.

Approach 2: DVs as Keypers

Setup and assumptions

• Each source S_i has at least one DV it trusts, DV_i.
• Each DV_i has a threshold decryption public-private key pair pk_i, sk_i. That is, each DV_i node O_j stores a share sk_{i, j} of sk_i. When sufficiently many operators collaborate, they can decrypt ciphertexts encrypted using pk_i.
• There is a DA layer DA with fast-progressing blocks. (This DA can be provided locally by all Obol DV-s jointly).
• Proposers have their stake restaked in a keypers AVS K, what provides economical incentives for their non-malicious behaviour. We denote by P_s the proposer for a blok at slot s.

Workflow

Here we describe a workflow for publishing encrypted transactions at slot s.

• In a block s - 2 the latest, the source S_i sends to a proposer P_s
  • their encrypted transaction Enc(pk_j; tx), where pk_j is the public key of DV_j who is trusted by S_i
  • gas_limit,
  • gas_price, and
  • index j.
• proposer P_s builds an encrypted block eB using the encrypted transactions Enc(pk_{i_1}, tx_1), \ldots, Enc(pk_{i_n}, tx_n). Here, pk_{i_k} are public keys of the DV clusters trusted by transaction sources. That is, the proposer gathers transactions encrypted under multiple public keys, which corresponding secret keys might not be known for them.
• P_s computes a signature-encryption pair c = (eB, Sign(eB)) of the ordering of the transactions in the block. The signature is sent to DVs, whose public keys were used to encrypt transactions in eB, and to a data availability protocol DA in slot s - 2
• DV_j decrypts the transactions that are included in eB, re-encryptes them using $P_s$’s public key and sends them to both P_s and the data availability layer DA. This data should be included in a slot s - 1
• P_s builds a block B using the decrypted transactions. If some of the transactions are invalid, then P can skip them. In that case, the emptied block space if filled up with the following transactions, and the space at the bottom of the block is emptied. The proposer can use this space as he pleases.

Challenges

P_s doesn’t include transactions, although the payload was published on a DA

Assume that the omitted transaction was tx_j. The DV, whose transactions were omitted, sends to the AVS K, where P_s subscribed to, information containing:

• omitted transaction tx_j
• the block produced by P_s
• DA confirmation about including Enc(pk_P, tx_j)
• ZK proof showing that tx_j revealed by DV is the same as the transaction encrypted in Enc(pk_P, tx_j).

P changed the ordering of the transactions

This is processed similarly the point above, except that the DV, whose transaction was moved, sends

• moved transaction tx_j
• the block produced by P_s
• $P_s$’s signature on encrypted block eB
• zk proof that tx_j encrypts to a particular transaction in the signed and encrypted block eB

DV_i does not provide the payload.

P_s drops the corresponding transactions from the block. Since the payload is not in the DA, the proposer is not going to be punished.

DV_i provided a transaction which cannot be included in the block

Say that DV_i provided transactions which inclusion would redeem the block invalid. In that case, we need to allow P_s to drop them and “pull” the following transactions up. In that case, some space of the block is freed. The proposer can fill it up as it pleases.

Importantly, the proposer may learn about impossibility of attaching the transactions after it sent its signature c. To protect the proposer from slashing, we observe that since all of the nodes in K knows the signature c, they can determine how the block is built, which transactions are included and which cannot be added to the block.

Instantiation

Encryption scheme

Threshold encryption scheme. E.g. threshold El-Gamal.

Signature

The signature c needs to meet the following requirement: Everybody who holds an encrypted transaction Enc(tx) should be able to tell whether the transaction was included in and at which spot.

Signature c compounds of the encrypted block built by the proposer and proposer’s signature on that block.

DA

E.g. EigenDA, as it publishes blocks with Ethereum’s speed

Problems

Latency

The transactions need to be known 2-3 slots before publishing.

Single proposer does all the block building

As proposer is solely responsible for the most profitable block building he is limited in his own resources to gather transactions, check, redo.

Comparison

Approach	DV as Keypers	DVs as builders and relays
Penalty	Restaking-based penalties for proposers	Slashing for proposers
Trust Assumptions	Sources trust specific DVs for transaction handling. They don’t need to trust the proposers.	Sources trust builders not to engage in MEV reordering, builders trust relays for handling blocks without MEV reordering, and proposers trust relays to provide valid blocks.
Problems	Latency in block rebuilding visible to the proposer.
As the proposer is responsible for the “best” block building, he is limited in his own resources to gather transactions, check, redo	Latency in double encryption-decryption
Competitive benefits	Restaking-based penalties can be much softer than slashing	Blocks are build in a concurrent manner, proposer only signs

Criteria/Approach	Resilient Shared Sequencers Shared Sequencers - HackMD	Fair Exchange in PBS Fair Exchange in Proposer-Builder Separation - HackMD	PEPC-DVT	DVs as Keypers	DVs as Builders and Relays	DVs as only Relays
Can work on top of Eth 2.0 as is	No, block is posted in encrypted form	N/A	Yes	Yes	Yes	Yes
Senders issues	Not covered	MEV sources txs reordering is not addressed: block builders are free to do as much reordering on TXs before passing on a block as they desire	TX ordering is in focus, yet only by special arrangement or financial incentives transactions are not MEV reordered. That incentives shall be prerecorded into a SmartContract (raises latency disclosure and censorship issues)	Sources sends the TXs to the DVs they trust.	Sources transactions are partly decoded by builders, some portion of TXs may be reordered in case of a malicious DV Builder	Builders can do MEV reordering
Builders Issues	Blocks exploitation by the proposer of the (n+2)th block in case of time outs	* S1 builders of this block have access to antiquated state of the system. This also disallows them from accurately determining whether transactions that they subsequently add are valid, or figuring out the gains through MEV for the block they build * S2 builder reveals the block content at the same time as revealing the block commitment with the proposer. However, to ensure privacy of the block content, it instead secret-shares the block with a committee of (or all of the) stakes. builder ends up paying without having any guarantees of the other side of the exchange.	Proposer is a builder	Proposer is the builder (who has limited information on what block it builds due to encrypted TXs)	No censorship, slower speed due to encrypted TXs	Any Builder can do censorship on sources transaction and do MEV reordering, insert transactions that would cover MEV attack for Relay while getting out more from MEV attack
Proposers issues	Penalties for misbehavior (e.g., slashing) not clearly defined, dependent on specific network rules.	a Sybil attack by builders posting high bids but not performing subsequent actions; Bad#invalid block proposals;	Proposer in part shares its key to a DV committee. If a DV colludes no block is produced and part of signature can be reviled. But the proposer can generate a signature in any case as it has a complete key. Even if DKG was used and proposer kept n/2 shares, if there are at most n/3 malicious nodes in the DV, since the proposer has n/2 of all shares, they can collude and have n/3 + n/2 = 5n/6 shares	- Latency The transactions need to be known in advance - Single proposer does all the block building	Latency between Source->Builder->Relay may affect potential reward	A relay selection is main source of trustfulness
Relays	No relays	PBS is described with no relays	No relays	No relays	Need to publish blocks on time	Have to deal with much more Builders → attacks
Proposition	Implementing a Security Deposit Mechanism (added liquidity); Introducing FIFO Ordering to Prevent MEV Extraction (implies single network view or source);	Builder reveals the commitment to the proposer, gives blocks in a sharded secret manner to comity members to test and approve	Key is shared between Proposer and DV Comity, promises to the order of transactions are recorded on chain, DV checks proposed block against it and if disagrees no block publishing happens	The proposer collects encrypted TXs from sources, builds an encrypted block, commits to ordering, and sends the commitment to the DVs and the DA layer. The DVs send decryption of the TXs (included in encrypted block) to the proposer. The DVs also encrypt TXs using proposer’s public key and send the encrypted TXs to DA layer.	Make Relays, Builders out from DV; Use DKG/TSS or similar mechanisms to do transactions (from sources) and blocks (from builders) encryption	Make only relays from DVs while keeping builders as they are in MEV-Boost PBS
Participants Set	Sequencer nodes responsible for transaction ordering and block proposal. Interaction primarily among sequencers.	Builder → proposer → committee	Sources, Participant, SmartContract to order/prioritize, DV to check and publish	Sources, Proposers, and DVs as Keypers, DA layer	Sources, DV based Builders, DV based Relays, Proposers	Sources, Builders, DV based Relays, Proposers

Supplementary material:

A and B approaches of Resilient Shared Sequencers

Fair Exchange in PBS scheme

DVs as Builders and Relays scheme

DVs as Relays scheme