Stealth transactions via DAG

[hashdag]

This post elaborates on an MEV-resistance feature I mentioned during a Twitter discussion some time ago.

Flashbots, pretrade privacy, DAGs

Pre-trade privacy means essentially a mechanism that circumvents a public mempool:

“Pre-trade privacy: Pre-trade privacy implies transactions only become publicly known after they have been included in a block. Note, this type of privacy does not exclude privileged actors such as transaction aggregators / gateways / miners.” (MEV-GETH)

One clean way to achieve pretrade privacy is to relay a user’s txn to a specific miner rather than broadcasting it to the entire network of miners. Obviously, this would be possible in a decentralized manner only if small miners mine blocks very frequently. E.g., if we implement a system with 100 blocks per second, a miner with 1% of the hashrate would be able to mine one block per second, on average, which allows the user to send her txn to that miner only without negatively affecting its confirmation time (by more than a negligible time). In contrast, with Ethereum’s one block per 15 seconds, a miner with 25% of the hashrate would mine a block only after one minute, which is a prohibitive delay.

Fast block times in the order of magnitude of 1 or more blocks per second would cause the orphan rate to spike. Thus, enabling pre-trade privacy via fast block times requires employing a blockDAG based protocol such as PHANTOM. A reasonable setup would be to start with 5 blocks per second, allowing any 10% miner to mine txns every 2 seconds; and gradually improving capabilities towards the utopian 100 blocks per second.

MEV, complete privacy, stealth txns

Pre-trade privacy protects users from frontrunning bots, but not from censoring and frontrunning miners / aggregators / consensus participants. To protect from manipulation by miners, we need the stronger property:

“Complete privacy: Complete privacy implies there are no privileged actors such as transaction aggregators / gateways / miners who can observe incoming transactions.” (MEV-GETH)

Complete privacy seems too generic a term, and I propose to replace it with pre-trade stealth transaction mode, or simply stealth transactions.

In a payment oriented system such as Bitcoin stealth transactions seems a bit of an overkill, but in a DeFi oriented system such as Ethereum it is almost a must: Without stealth transactions, every miner can run simple simulations to check whether he is better off mimicking or otherwise manipulating a transaction at the expense of its issuer; non-mining users wouldn’t be able to issue arbitrage-like txns that capitalize on their own algorithms, knowledge, and financial entrepreneurship. You can love or hate the arbitrage game, but you definitely don’t want it to be the privileged game of miners.

Of course, arbitrage is just one example for transactions that suffer from MEV, but attempting to describe the entire attack surface is beyond our scope here.

How to implement stealth txns in a proof-of-work powered DAG

We can utilize network asynchrony to implement stealth txns. One strawman idea is to send the txn in encrypted mode, have it mined as payload unintelligible data, and only then send the decryption key to be mined in a later block. To preserve the irreversibility of the state, the txn must enter the ordering -- i.e., alter the state -- only after its decryption key is included. This constraint renders this idea useless, as the second miner will have access to the decrypted txn before it is mined and can manipulate it all the same.

However, we can fix this idea by sending both the encrypted txn and its decryption key to different factions in the network so that both pieces will be mined in parallel. If the user sends her encrypted txn to one miner with sufficient hashrate, and its decryption key to a different miner with sufficient hashrate, and if these pieces come alongside high enough fees, they will be mined immediately before any of the miners receives the other piece.

The construction is not bulletproof. It relies on timing things right, and on miners not colluding -- an assumption which arguably underlies the security of decentralized consensus anyways. Concretely, it relies on the following assumptions:

1. Miners do not relay txns to one another, or do not have time to do so, due to the competition on fees
2. Users have the option to send their txns directly to miners; moreover, the user can check the distinct hashrate of the recipient miner (implementing this is not difficult, and we only need rough estimates for this to work properly)
3. The block update latency between two random miners is high enough. By block update latency I’m referring to the avg time it takes one miner to receive a block from another miner, validate it, and update its own block template. Note that it is infeasible for the miner to update its block template more frequently than, say, once per 50 milliseconds, as the overhead would harm its efficiency and profitability. Thus, block update latency can be practically much higher than the propagation latency.
4. The blockrate is high; specifically, it should be high enough so that two miners of a certain magnitude are highly likely to mine a new block faster than the block update latency.

Let us consider a system with 100 blocks per second, miner granularity of 5%, and block update latency of 200 milliseconds. A miner controlling 5% of the hashrate is mining one block every 200 milliseconds, on average. Thus, we can achieve a satisfying degree of stealthiness with the following txn flow:

1. Alice encrypts her transaction and sends enc(tx) to Bob alongside a high fee, where Bob is a miner who controls ~5% of the hashrate.
2. Simultaneously, Alice sends the decryption key dec(tx) to Charlie alongside a high fee, where Charlie is a different miner who controls ~5% of the hashrate.
3. Thanks to the high fee, Bob will mine enc(tx) in his next block, which will be created within 100 milliseconds, on average.
4. Similarly, Charlie will mine dec(tx) within ~100 milliseconds.
5. Thanks to block update latency, Charlie will mine dec(tx) before he receives enc(tx) from Bob, which implies neither Charlie nor Bob had access to the ciphertext tx before both have been mined.
6. tx will enter the ordering and alter the state by the first block that references both Bob’s and Charlie’s blocks.

This construction does not pretend to provide bulletproof privacy of the kind we are used to being required from crypto systems. Instead, it is intended to impose prohibitive inefficiencies to miners aiming to frontrun users’ txns, and to eliminate the ability of (non-mining) bots to do so. Implementing stealth transactions in a cryptographically robust manner requires deeper conceptual breakthroughs. (MEV-GETH)'s landing page reads: “We expect a complete privacy design to necessitate some sort of private computation solution like SGX, ZKP, or MPC to withhold the transaction content from miners until it is mined in a block.” It is not clear yet how to achieve bulletproof stealth txns even with ZKPs.

Further notes

1. Many txn types won’t require the stealth mode, though financial non-payment txns are increasingly consuming a larger portion of the blockspace. Nonetheless, it might be worthwhile to implement this feature by default, in order to provide more resilience to txns that do require it (avoiding ZCash-like design decisions to make shielded txns non-default).

2. In principle, instead of sending the txn to two specific miners only, stealth txns is achieved even if Alice sends enc(tx) to half of the miners, and dec(tx) to the other half. However, this would rely too heavily on the resiliency of the miner-discovery mechanism. Furthermore, for efficiency and guaranteed fees, miners would likely mine with high preference txns sent to them by retained users which commit to send the txn to that miner only.

3. The tradeoff between the parameters of the construction are as follows: The lower the size of the miners which the user can access, the higher the degree of decentralization, but the higher the blockrate should be relative to the block update latency.

4. Stealth txns do not fully guarantee that miners will not ignore the txn and coordinate a reorg. This Consensus Instability is impossible to solve in all setups (see this paper by Liao and Katz). However, by ensuring that the txn was mined by two and potentially more miners before it propagates in the entire network, we render its censoring much more difficult to coordinate.

[thegostep]

Can you give me an intuition for how the two blocks end up being ordered on the chain?

How is the sequence of block determined under a dag model ?

[hashdag]

The DAG is ordered according to the GHOSTDAG consensus protocol, see here https://eprint.iacr.org/2018/104.pdf.

Intuitively, the protocol greedily builds a chain by selecting the heaviest k-cluster, where a k-cluster is a parameterized set of well connected blocks -- each block must be connected (directly or indirectly) to all blocks in the cluster up to at most k blocks. The parameter k represents therefore the expected width of the DAG when all miners are honest and communicating (the k-cluster, "blue blocks"), and is used to mark withheld or otherwise outlier blocks ("red blocks") and push them late in the ordering.

[jianyu-niu]

In this solution, Charlie and Bob should be honest and always include the txs immediately. How to guarantee this from either the protocol level or economic level?