Reading Encrypted memory Pools: A new design space to solve MEV and audit problems

Reading Encrypted Memory Pools: A New Design Space to Solve MEV and Censorship Problems

Original article by Jon Charbonneau

0x11, Foresight News

Encrypted memory pools are a powerful tool for solving MEV and auditing problems, and several related solutions exist that can be used individually or in combination with each other.

This article is an overview of Justin Drake's talk on the subject (Columbia,Amsterdam  And  Flashbots Roast) to construct the design space. Most of you may find it hard to understand the first time you watch it, so I'll try to break it down and expand on it briefly.

The basic idea: Allow users to submit encrypted transactions that block producers can decrypt by submitting them:

The user encrypts and broadcasts the transaction

Crypto submission

Transaction declassified

Transaction execution (Note: Commit, decrypt, and execute may be in a single slot)

Two problems seem solvable:

MEV: If I can't see it, I can't pre-trade

Review: I cannot review transactions unless I exclude all encrypted transactions (which can be very expensive if many transactions are encrypted)

One key point to ensure here is that decryption is not user-dependent. There are several ways to do this:

1.In-flight

Trust a third party to send him the data privately, and he can decrypt and view it, but promise not to disclose it publicly until it is submitted on the chain. That's it.Flashbots Protect  And the way the product works.

2. Trusted hardware

You can leverage trusted hardware. Plaintext can run on trusted hardware, but is not publicly decrypted until the transaction is submitted. The most famous example is Flashbots SUAVE's  SGX.

3. Threshold Encryption/Decryption (TED)

A committee could band together to force decryption, but signatories would need to meet a threshold to do so. For example, your "threshold" might be a requirement that 2/3 of the verifiers agree to decrypt. TED has conducted research in several different areas, including:

Ethereum L1 --Shutterized Beacon Chain

Shutter Network  -- Ethereum L2  s

Arbitrum - & have spentFSS by Chainlink

Osmosis & Anoma - & have spentFerveo

Shutterized Beacon Chain

Looking closely at the Shutterized Beacon Chain proposal, a subset of validators (" keypers ") generates public/private key pairs using a distributed key generator (DKG). Everyone can see the public key, but the private key is kept in separate pieces in the committee. Reconstruction of the private key and decryption require the key share to reach a certain threshold (e.g.,   2/3 ) .  

Users can selectively encrypt transactions that are included on the chain before their contents are decrypted and executed. Block producers create blocks using plaintext transactions (executed immediately) and cryptographic transactions (planned at a future block height).  

After generating and proving block n-1, keypers should generate and publish block n's decryption key. This key can decrypt transactions in block n. Block n must contain a decryption key to be considered valid. The post-state of the block is calculated by executing the encrypted transactions in the block (in the order they are set) before executing the plaintext transactions in the block.

shortcomings

TED has several disadvantages:

Lack of accountability: Unlike traditional security assumptions, malicious behavior here is not attributable or reportable. Keypers can be decrypted immediately, you can't attribute them. Even if you assume that the verifier's behaviour is compatible with incentives, the three-letter agencies outside the verifier set -- the collective name for the CIA, FBI and the like, which defend the US but are often secretive -- may have influence over them.  

The honest majority hypothesis: Dishonest committees may create problems, such as choosing never to declassify certain messages, or secretly declassifying messages they should not (for example, at the request of a government agency, or selfishly conducting MEV extraction). In most cases, blockchains actually rely on economically rational majorities (i.e., the penalties for forfeiture usually outweigh the economic incentives for acts such as malicious double flowers). Through threshold encryption, this assumption is transferred to a truly honest and selfless majority.

Destabilizing protocol: Essentially a combination of the two above, TED increases the verifier's incentive to do evil and is less prone to punishment.

Reduced activity: Higher decryption thresholds enhance protocol security). However, this directly reduces activity. For example, a massive network outage that causes half of the validators to go down may now cause the protocol to stop. Especially for Ethereum, which puts a lot of emphasis on "World War III" activity, this is an unacceptable trade-off.  

Poor user experience: TED may add varying degrees of delay and cost depending on implementation details.

Suboptimal value allocation: Let's look at a simple frontrunning example:

The price of 1 ETH is 1000 USD.

If I send the transaction to the vanilla pool -- I get $990 (the searchers frontruns and backruns, net $10)

If I send the trade to the TED memory pool -- I get $995 (the searcher can't jump start, but I push the local spot price, creating a $5 arbitrage opportunity for the searcher)

I send the transaction toBest order stream auction-- I got $1,000 (I didn't get frontruns or backruns. Or similarly, I do get frontruns and/or backruns, but the searcher has to bid $10 in a competitive auction for the right to do so, and the end result is the same.)

In this case, you leave money on the table for someone else to take. An economically rational user should disclose enough information about the order so that they can be compensated close to the full value of the order. They should not naively encrypt their transactions to the threshold, hiding the value it provides (allowing others to capture it).  

This is a hyper-idealized example, but you get the idea that glossing over a problem doesn't always solve it. TED can be a useful tool, but it is not a panacea for MEVs. In some cases, CR is better.  

In addition, Ethereum introduces additional complexity. For example, its lack of immediate finality (although this may one day change with single-slot finality) was introducedQuestions around restructuring. I believe that at least in Ethereum L1, the trade-offs here outweigh the trade-offs. Increasing Ethereum's assumption of trust, increasing the incentive for collusion (not to be detected), and lowering its activity may do more harm than good.  

However, some of these trade-offs may be more acceptable for L2 or other L1s than for Ethereum L1.  

4. Delayed Encryption/Decryption (DED)

With deferred encryption, you can set encrypted messages to automatically decrypt them after a certain amount of time, which is a sequential calculation associated with VDF.

To actually implement DED, you need a VDF ASIC. Fortunately, the Ethereum Foundation and Protocol LABS have been working on building them, and recently acquired the first test samples of chips built by GlobalFoundries. These VDF evaluators should be able to perform extremely fast sequential calculations. These VDF Asics are also suitable for time-locked puzzles and DED.  

The VDF also needs to generate SNARKs. This can be done using Gpus, but ideally the Ethereum Foundation would like to produce related ASics for SNARK as well.  

In general, you no longer trust a committee, so the safe assumption is usually preferred. However, requiring specialized hardware is not ideal, and the required latency may add to the system's latency. Interestingly, you can combine the strengths of TED + DED...

5. Witness Encryption/Decryption (WED)

WED is strong, but don't get too excited, it won't come soon. This is something very peculiar and will take many years to achieve. But it's cool and helpful to understand, so I'll go through it briefly.  

WED allows any witness to force decryption of ciphertext. For example, your rule could be "Decrypt only after Ethereum has completed the block containing the encrypted payload", and only if this is proven. You can imagine that basically any complex statement you want to implement requires SNARK.

WED is actually TED or DED in general. You can even build a hybrid of the two. For example, a designated witness may testify that:

Happy outcome: The Threshold committee has signed off on declassification, or.

Preparation: The required time has expired, return to delay decryption

This provides a cushion in case the threshold committee does not respond. This also allows you to be more conservative in parameterizing the m/n threshold assumptions (i.e., you can ask every committee member or almost all of them to sign off).

Happy Results: Best User Experience, instant confirmation from the entire Board.

Preparation: Delay and UX are temporarily affected, but activity is preserved

In fact, WED may validate SNARK for any declaration you want. For example:  

TED: You can have a SNARK that proves "I have m signatures out of n signatures" to force decryption.

DED: You can use VDF and do sequential calculations (which are very expensive). And then at the end of your calculation, you have a short proof. Then you take that short proof and wrap it in a SNARK (make it shorter) and enter it to force decryption.

homomorphism

Each of these encryption schemes (threshold, delay and witness), you can have homomorphism. That is, thresholds can be created.FHE  Delay FHE and witness FHE schemes to realize arbitrary operation of ciphertext.

in-flight and trusted hardware (for example, SGX) solutions can simulate the same functionality -- manipulating private data. This is because in both cases, a trusted third party or hardware has access to the plaintext itself to operate. Ideally, however, we would like to remove these trust assumptions and rely solely on enhanced cryptography.

We can imagine an example:

m  1 = transaction 1 

m  2 = transaction 2 

f(x) = build a block  

All five solutions can then replicate the following features:  

Keep this capability in mind as we consider how to hide transaction metadata and build the best blocks with encrypted input. In theory, each of the five options here can be used for the following solution that requires "homomorphism."  

metadata

Metadata is data that provides information about other data, but not the content of that data (such as the text of a message or the image itself). For our purposes, transaction metadata can include the sender's IP address, random numbers, Gas payments, and so on.

Ideally, we want to hide as much metadata as possible. Otherwise, it may give away information that an outsider can infer about your transaction (perhaps giving them enough information to try to jump start or review, etc.). However, we need metadata to verify that the transaction is valid, that necessary fees have been paid, that it is spam, and so on.

Let's look at some solutions for masking various types of metadata.

1. IP address -Tor

Very simple - people can use a service like Tor to broadcast privately and block their IP address.

2. Signature -SNARK

You need to know at the p2p level that an encrypted transaction is valid, especially if it has a valid signature. We can use SNARK to prove that the signature is valid, which will accompany each encrypted transaction. SNARK has three important parts:

The user wants to prove that the ciphertext of the transaction is valid. It corresponds to the plaintext of the transaction and its signature is valid. To prove that any signature is valid, you need the public key associated with the account to verify it.

Find the Ethereum state root (public).

Provides the sender's public key Merkle proof corresponding to this state root (private)

To verify the signature, you need to verify the sender's public key Merkle proof against the state root. Use SNARK to prove that your sender's public key Merkle proof is valid and your signature is valid.

3. Gas Payment -- SNARK

You need to prove that the sender of the encrypted transaction has enough ETH to cover the cost. We can use SNARK again.  

This is a similar process, but now you provide a Merkle path to the state root, which proves the sender's balance (rather than the sender's public key). You verify the Merkle path and verify that the balance is sufficient to pay for the required Gas.

Perform only the minimum Gas required for basic operations such as deserializing a transaction, checking its balance, and checking signatures. You can stipulate that the sender must always pay this minimum amount.  

But in terms of execution time, you also need to have a Gas limit for the actual transaction itself, which can also be encrypted. So when you go to actually execute the transaction itself, you check that the sender has enough balance to cover the full Gas of the transaction at that time:

If so: Run the transaction and issue a refund at the end

If not: abort the transaction and the sender only has to pay 21000 Gas

4. Sender and random number - SNARK

A random number is a value equal to the number of transactions sent from an address (or the number of contracts created by an account). The user's random number increases by 1 per transaction from their address. .  

One reason we have random numbers today is that users cannot spam mempools (DoS attacks) with a large number of transactions to increase the likelihood that their transactions will be executed. The node looks at only one transaction with that random number and discards the others.  

For crypto transactions, you will use SNARK to prove that the random number is the previous random number. . However, if the node will no longer be able to tell that many encrypted transactions have the same random number, then the above DoS attacks can have adverse effects.

To preserve this anti-DOS property, we want to add a "replay tag". It uniquely flags transactions so you can no longer send a lot of transaction spam for an address. To create this tag, you can simply hash (random number, private key). Because both the random number and the private key are fixed, if the user tries to send both using the same random number and private key, different transactions will have the same replay label.

Finally, you may want to retain some degree of flexibility. Assuming the Gas price has moved, you would reasonably want to re-broadcast the deal at a higher price. To mitigate this, you can hash (random number, private key, slot). Now you can adjust your transactions once per slot, and only one transaction can be sent per slot per address.    

5. Data size - homomorphism

A plaintext of the encrypted data size n creates a ciphertext of the encrypted data size n. Even this size is sufficient to calculate certain transactions probabilistically. We can alleviate this problem by "padding" -- adding 0  to the plaintext before encrypting it. To expand the number of bits to the next power of 2 (for example, add three 0  to a 5-bit ciphertext) .  

In the following example:

White = filled 0 

Other colors = actual transaction data

When you build blocks, you can connect these ciphertexts, but there are two problems with this:

Imperfect packaging - Extra zeros mean you have to pay for extra data availability

Imperfect privacy - maybe a power of two provides enough information. The distribution of transaction sizes is not clear, so some sizes may still reveal enough information probabilistically.

A better solution involves "cutting out" the fill:  

Fill each transaction to its maximum size (16  here). Parallel homomorphic encryption

Apply a function to the ciphertext to efficiently pack the plaintext and remove unnecessary padding

Now you've got the best package.

By padding to the "maximum" size, this can actually set the maximum to what the actual block size limit converts to (i.e., if 30  mm Gas converts to about x kB). This means populating each transaction to a size of x kB. Alternatively, if 99.9% of transactions are typically in the y kilobyte range, you can set a smaller and more practical y kilobyte size.

Again, this "clipping" can be simulated using trusted hardware instead of the FHE discussed earlier. For example, you can run SGX and receive encrypted transactions to your trusted enclave. In an enclave, the data can be manipulated in plain text to cut out unnecessary padding to densely pack blocks. The data is then encrypted and shipped back, followed by a forced decryption method (threshold, delay, witness).  

Note that in either case, the output should be of some fixed size, so you may be left with a small amount of padding.  

Transaction package selection: Homomorphic and disjoint state access list

Assuming we solve all of the above problems, the block producer is able to pack everything into one block optimally based on size. But we have another question -- can block producers package everything optimally in economic terms? We want to centralize building blocks without throwing away value. Otherwise, it cannot compete with centralized entities.

Solution 1 - FHE EVM

Direct answer: Run EVM entirely in FHE. This will allow decentralization to build the best blocks, capturing maximum value for block producers. They select and rank transactions that maximize value.  

Unfortunately, it's not easy. The biggest cost of an FHE circuit is its "depth" (i.e. the number of gates in the longest path). In particular, its depth of multiplication is very important. For example, the transaction "clipping" described earlier to remove padding is a fairly "shallow" circuit (i.e., it is very simple). With hardware acceleration, such use cases may be computationally feasible within 2-3 years.  

However, running the entire EVM with FHE requires very deep and complex circuits. We're finally starting to make some meaningful progress with zkEVM circuits (which are orders of magnitude more computation-intensive than running standard EVMs), but FHE EVMs are even further away.  

Again, note that it is possible to emulate this functionality using trusted hardware (for example, SGX in SUAVE does so).

Solution 2 - Status access list

Alternatively, we can use FHE and access lists more limited. This is easier to implement than running a full FHE EVM -- it's a shallower circuit. In this setup, the transaction package can include an encrypted status access list and its bids. This specifies exactly what part of the state their packages will access.  

Now, the block producer's homomorphic circuit only has to pick the highest bid for a transaction packet with a disjointed state access list.  

Note that this is not strictly optimal. For example, the second highest bid (T 2) in a block may reach the exact same state as the highest bid (T 1). In this access list example, the block producer discards the second transaction. However, it's possible that both T 1 and T 2 will work. In this case, FHE EVM (or today's centralized block production) will gain more value.  

It's not perfect, but from where we are today, this shortcut should be close enough to optimal. Most MEVs will still use disjoint access lists because examples of conflicts like the one above are rare.  

6. Time stamp - homomorphism

You can even try to hide a leak in the existence of a transaction by allowing the verifier to make a "virtual" transaction, so the memory pool is always full. The verifier also needs a SNARK to prove that they are the verifier that is allowed to create these virtual transactions. When there is a spike in "real" transactions, the verifier will broadcast fewer virtual transactions. As the real transaction drops, the validator will issue more fictitious transactions.  

Assuming everything is encrypted using FHE, you will be able to detect the "virtual flag" added to the corresponding transaction. You can ignore these transactions while packaging the actual blocks.

Status difference - FHE EVM

Background: One advantage of ZK Rollup is that they do not need to publish complete transaction data on the chain. The "status difference" between the status updates they post is sufficient. Instead, Optimistic Rollups must publish the full data on the chain in case of arbitration of proof of fraud. This lower data requirement saves money for ZK Rollup because they consume fewer resources in the data availability layer.  

Bring this into our conversation -- ideally, you don't want to lose this benefit with an encrypted memory pool. You want to get the encrypted memory pool and still retain the ability of ZK Rollup to publish only state differences. Here's the answer -- FHE zkEVM. Sounds cool, but you may have to wait a long time.

One disadvantage is that publishing state differences separately may slow down the response time of a Rollup full node. For example, in the pure fork selection rule Rollup, full nodes can complete their view of Rollup as soon as the data availability layer is completed and validated. If you only publish state differences (not complete transaction data), even complete nodes will need to submit ZK certificates to confirm their view of Rollup. As things stand -- these proofs take a while to generate, but scalable data availability layers are expected to become very cheap very soon.

conclusion

Encrypted memory pools are a fascinating and promising design space, but there are still some practical challenges. For example, you might simply move certain problems elsewhere on the stack. Wallets can vet you at source to prevent transaction encryption/routing, they can submit payloads to run (or sell rights) before/after your transaction, etc. One possible answer is for users to create transactions locally rather than depending on the service provider.  

The point is that there is no magic bullet here, but if designed properly, they could be an important part of the solution that could improve the current situation with different functional and trust assumptions.

Original link

Welcome to join the official BlockBeats community:

Telegram Subscription Group: https://t.me/theblockbeats

Telegram Discussion Group: https://t.me/BlockBeats_App

Official Twitter Account: https://twitter.com/BlockBeatsAsia