Preventing selective transaction censorship and MeV using time-locked encryption

Time-locked encryption based on witness encryption can be used to prevent MeV (miner-extractractable value) by forcing miners to accept transactions in certain order before they are able to know the their content. The existing time-locked encryption schemes could be useful but but very complex and I’m not aware of public implementation. I think we could achieve a similar result incorporation proof-of-work to the scheme.

I was thinking about using SNARK-friendly Verifiable Encryption with an discrete-log based PoW, to create a time-locked encryption scheme useful for a PoW blockchain.
The method could also be adapted to be executed inside a smart contract in RSK, provided there are enough monetary incentives to periodically solve the discrete log PoW puzzle. Solving discrete-log puzzles for PoW is something already proposed.

The procedure would be the following:

A smart-contract chooses periodically a pair of EC points (Y,G) such that Y=xG and x is unknown, using the RSK PoW of the previous RSK block as a cryptoeconomic seed.
The pair is chosen such that the discrete log for (Y,G) can be found in approximate T time (an “epoch”), and therefore x is recovered by a party we’ll call simply “miner”.
When x(j) is found, a new epoch starts and a new x(j+1) and Y(j+1) are chosen (G(j+1) may or may not need to be chosen again).
The curves are created with adjusting difficulties so that the average time per recovered x is T on average, in a similar way PoW difficulty is adjusted.

For each epoch j, users send new transactions Tx(i) to a smart-contract in RSK that we call the BATCH contract.
Each Tx(i) contains the message E(m(i),Y) which is an encryption of a message m(i) with the public key Y (using ECIES-like Diffie-Hellman encryption), and also a proof that the message m(i) is syntactically and semantically correct. Users either delegate the use of their tokens to the BATCH contract (with approve()), or users have smart-wallets that accepts commands from the BATCH contract. Also users can have their balances held inside the BATCH contract as a multi-user wallet. In any case, the BATCH contract is trusted by users.
The encryption is performed using a SNARK-friendly Verifiable Encryption scheme. Messages can only be decrypted by a party that knows x.
As previously stated, each Tx(i) also contains a proof that m(i) is correct, having some syntactical and semantical properties. Some of the properties are:

  • It requires certain gas limit for transaction execution (this value can be public).
  • It pays some transaction fees to the BATCH contract (this value can be private or open)

The BATCH contract keeps count of the sum of all gas limits declared by Tx(i) transactions . Once a cap of gas is reached, no more transactions are accepted by the BATCH contract for that epoch.

Mining

For each sequential epoch j, the BATCH contract accepts a message commit(j) from any miner that is able to recover x.
The message commit(j) contains a proof of knowledge of x(j) that is tied to a miner public key Kpub(j). This message is commitment to the public key Kpub, without revealing x. For example, a signature of Kpub with private key x.
After a number N blocks have confirmed the commit(j) message, the miner reveals x and Kpub.
At that point, the BATCH contract performs the following actions:

  • Decrypt all transactions Tx(i) using x(j).
  • Execute all transactions Tx(i) in the order they were received.
  • Pays a reward to the miner to the address represented by Kpub. The reward consist of a function of the transaction fees from transactions Tx(i).

Alternatively, instead of using a commit-reveal stage for the miner to reveal x associated with Kpub, the miner could also in a single step reveal all m(i) and prove correctness of all the the relations (Tx(i),m(i)). He can easily so it because he knows x. However, this is costly because all messages m(i) must be re-transmitted to the blockchain.

Sender’s Privacy

To prevent selective-censorship based on sender’s account, we could use anonymization techniques based on nullifiers in the same way as zCash does, so the user also hides where the funds are coming from. Account records would be stored into the leaves of a Merkle tree built using a SNARK-friendly hash function.
To avoid UTXO-fragmentation, and keep using an account model, we could force users to commit to long hash-chain.
For each user, each hash-chain element is C(u)=H(v(u),n(u),C(u-1)). C(0)=c.
The latest C(u) value for each user is public and stored in the account record.
Every transaction Tx(i) requires proving knowledge of an element C(u-2) and showing v(u-1) so that the relation between C(u-1) and C(u) is verified.
The hash chain is built using a SNARK-friendly hash function.
When a user submits a transaction Tx(i), it proves the relation of C elements for one of the existing accounts on the Merkle-tree, but without revealing which. The values v(u) have a similar role that the nullifiers in zCash.

This scheme does not provide full unlikability of payments due to the fact that if the same account perform several payments in different epochs, then when the x(j) values are reveled the link is revealed.
However, it fulfills our needs to prevent MeV, since this knowledge is only spread only when transactions are executed and selective-censorship or selective-front-running is not possible.
If the user wants to perform more than one action in the same epoch, then it has to use multiple accounts, which in turns increases his privacy.

Open Questions

It would be better if instead of breaking the discrete log for the pair (Y,G) the miner could perform a VDF (a function that is known to be not easily parallelizable), to prevent unfair advantages against algorithmic optimizations.
Another question is if there will be enough incentives for miners to participate or if the system will be incentive compatible or not.

References

See https://link.springer.com/article/10.1007/s10623-018-0461-x to learn about time-locked encryption and witness encryption.
See https://eprint.iacr.org/2019/1270.pdf for references to a SNARK-friendly, Additively-homomorphic, and Verifiable Encryption and decryption with Rerandomization.
To choose the curve parameters with adjusting difficulty, we can use the method of http://ceur-ws.org/Vol-2580/DLT_2020_paper_1.pdf.

Somebody pointed out the project libsubmarine to me. While libsubmarine does provide protection from transaction reordering, it does not provide protection from censorship.
In any commit-reveal system without encryption, the reveal of a transaction can be censored by 51% miners. However, such attack would only be perpetrated for a very high profit, as 51% attacks are generally attributable and a dangerous game to play by the miners.

On the other hand, libsubmarine on RSK can benefit from the 4000 block header access precompile for a long commit phase. In Ethereum the commit phase is limited to 256 blocks.

CensorshipCon enables transaction censorship attacks in Ethereum for an attacker having only 1/3 of the hashrate.
RSK is more vulnerable to censorship attacks due to lower block rewards and reward sharing.