qip-0006.md

Merge-Mined Transactions

  QIP: 6
  Layer: Protocol
  Title: Merge-Mined Transactions
  Author: kiltsonfire
  Comments-Summary: No comments yet.
  Comments-URI: https://github.com/quainetwork/qips/wiki/Comments:QIP-0006
  Status: Draft
  Type: Standards Track
  Created: 2023-11-16
  License: BSD-2-Clause

Abstract

This QIP defines the process and protocol changes required to allow the merge-mining of transactions.

Motivation

Merge-mined transactions (MMTX) enable objective ordering of transactions in proposed blocks, aligning incentives for block producers and miners. Additionally, MMTX reduces the impact of miner extractable value (MEV) on users and incentivizes hash contribution to the network.

Specification

Overview

MEV presents two issues: increased user costs and compromised chain progression and security. Large MEV opportunities can outweigh block reward incentives, leading miners to compete for MEV rather than cooperatively extending the longest chain. Currently, cryptocurrencies use separate mechanisms for ordering blocks and transactions within blocks. This distinction is unnecessary and creates competing markets for the same service: transaction ordering. One unified market for transaction ordering (for both intra and inter-block transactions) would eliminate this competition, enhancing security and finalization speed.

To implement a hash-based ordering market, it must govern both transaction and block ordering, removing conflicts between transaction and block progression.

Ordering of MMTXs in a Block

This QIP suggests a base fee for processing, with transaction order determined by worked ProgPow hashes. Transactions would be merge-mined with blocks, and the mining work done on a transaction would dictate its order in a block. The most worked transactions would be prioritized. Algorithmically, this involves sorting ProgPow hashes within each block based on their values, with lower hashes processed first.

Sorting Criteria and Algorithmic Application

Let $H = { hash_{i,j} \mid 1 \leq i \leq n, 1 \leq j \leq m_i }$ be a set of cryptographic hash values, where $n$ is the number of blocks in the chain and $m_i$ are the transactions in the $i^{th}$ block.

Given the defined set of hashes $H$, we apply a sorting algorithm to order the hashes within each block. Specifically, for each $i^{th}$ block, we ensure the order of the transactions follows the criterion $hash_{i,j} < hash_{i,j-1}$, with the lowest value of $hash_{i,j}$ being processed first in the $i^{th}$ block.

Algorithm 1 Sorting Hashes within Blockchain Blocks
1: H
2: function constructor(H′)
3:   H ← H′ ▷ Set of hash values H
4: end function
5: function sortHashes(H)
6:   for each block i from 1 to n do
7:     for each transaction j from 1 to m_i do
8:       Perform insertion sort on H[i] based on the hash order:
9:       if hash_{i,j} < hash_{i,j-1} then
10:         Swap hash_{i,j} with hash_{i,j-1}
11:       end if
12:     end for
13:   end for
14: end function

This would mean that to MEV a MMTX, say sandwich or front-run, a MEV bot would have to mine a transaction with appropriate order around the targeted transaction. This may seem trivial for transactions which do not have significant amounts of work, however, sandwiching a tx would require finding a mined tx which is in front of and behind the target transaction. Moreover, any MEV bot would have to execute these attacks in real-time.

Weighting of MMTXs

In addition to organizing transactions based on their hash values, the protocol incorporates the work done on each transaction into the overall entropy of the block. This approach means that blocks containing transactions with a higher amount of work, and therefore lower entropy, are more likely to be recognized as the primary block in the chain. This alignment between transaction ordering and the growth of the longest chain is essential for maintaining network integrity.

However, this method requires careful consideration to prevent potential exploits. If miners can mine transactions independently and include them arbitrarily in future blocks, they could amass a large number of mined transactions to dominate block creation. To counter this, the block's hash, with which a transaction is merged-mined, is used as a reference point. The contribution of a transaction's weight to a block's weight diminishes based on the age difference between the transaction and the block. This mechanism incentivizes miners to include transactions in their blocks as quickly as possible.

An additional layer of complexity arises with merge-mined transactions. These transactions can only be included if they are merged-mined with a canonical block. By mining on top of an already existing block, the work invested in merge-mined transactions serves to validate and reinforce the legitimacy of that block. This process not only enhances the security of the chain through implicit verification but also contributes to the overall chain entropy.

The decay in the contribution of a transaction's work to a block's entropy over time is also an important factor. The further away a transaction is from the current chain tip, the less it contributes to the block's entropy. Therefore, it's proposed that the weight of a transaction's work should decrease by half for each block that passes after it becomes eligible for inclusion. This approach encourages producers of merge-mined transactions to reference the most recent block, ensuring their transactions are included promptly. It also motivates miners to quickly include valid merge-mined transactions in their blocks, maximizing the total entropy and thereby strengthening the blockchain.

Formal Definitions

• Let $Tx_{i,n}$ denote a MMTX, where $i$ is the block index referenced by the MMTx, $n$ is the current block index, and $j$ is the index for each MMTx referencing block $i$ included in block $n$.
• Define $S_{int}$ as the bits of entropy achieved from mining a block, and $S_{target}$ as the entropy target in bits. A block is successfully mined when the condition $S_{int} > S_{target}$ is met.

Transaction Entropy Computation

The transaction entropy for a set of transactions included in block $i$ is computed as follows:

$$ x_{tx,i,j} = log(k/hash_{tx,i,j}) $$

$$ S_{tx,i} = \sum_{l=i-m}^{i} \frac{1}{2^{l}} \times e^{-S_{int,i}} \sum_{j=0}^{q_i} \frac{x_{tx,i,j}}{e^{-x_{tx,i,j}}} $$

In this expression:

$k$ represents the field size. $q_i$ denotes the number of transactions in block $i$, and $m$ is the depth of computation for the transactions contributing to the block entropy.

Total Block Entropy

The total entropy of a block is given by:

$$ S_{block,i} = S_{tx,i} + S_{int,i} + S_{block,{i-1}} $$

Although, the entropy of MMTx could be calculated going all the way back to genesis, from the view of practical computations the depth of computation, $m$, should be limited to a practical value. It is proposed that this could be set to m=16. This would provide a mechanism wherein latent transactions would still add entropy but would prevent the entropy computation from becoming impractical.

Additionally, it should be noted that the expected maximum contribution of transactions to the block entropy total is the square of the intrinsic threshold. For example, if $S_{target} = 20$ then $S_{tx,i}$ could be upto 400.

MMTX propagation incentives

Counting the work of transactions towards the weight of a block can have unintended consequences. Specifically, it might motivate miners to hold back transactions with substantial work to gain an advantage in block mining. This could negatively impact the network since blocks containing unpropagated transactions take longer to verify and unpropogated transaction will provide the miner that includes it an advantage over other miners which is not proportional to their hashrate.

This issue is partially mitigated by two factors. First, if the inclusion of unpropagated transactions significantly delays block validation, the block is more likely to be rejected (become an uncle block), penalizing the miner responsible. Second, users who broadcast transactions with a substantial amount of work are motivated to ensure rapid network propagation of their transactions, increasing the likelihood of their inclusion in a block with high priority.

However, if these incentives aren't enough, the marginal cost of mining an MMTX can be changed with the demand for interblock ordering. As long as the marginal cost of MMTX production is not allowed to be zero, there will always be an incentive to propogate MMTXs.

MMTX variable cost

When a MMTX is constructed to allow the work to be counted for both a transaction and a block, an issue arises due to the zero marginal cost of reusing the hash to mine a transaction that was going to mine a block. This is also the origin of potential withholding attacks when mined transactions are introduced. To eleviate these issues, it is proposed that a new merge mining scheme is introduced which allows MMTX marginal cost of production to decrease with increased demand for transaction ordering. Thus a new mechanism is proposed that will change the percentage of work that can count torwards merge mined blocks. This will prevent a withholding incentive while also creating a mechanism that will guarantee that the blockchain remains lively when there is high demand for ordering. The goal is to make it so that the marginal cost of mining a transaction is high when demand for ordering is low, and conversley the marginal cost for mining is low when the demand for ordering is high. It is important to note, that the marginal cost cannot allowed to be zero else the withholding incentives will be reintroduced.

Secondary threshold criteria for MMTX block

A secondary threshold can be used to establish a criteria for determining if a share meets the block criteria and this criteria can be adjusted by what is in the proposed block dynamically to ensure that the chain always remains lively. The secondary threshold criteria will be based on the trailing zeros of the hash. Specifically, the criteria to become an MMTX block will be met if:

$$ TX_{hash,val} < B_{mmtx,t} $$

where $ TX_{hash,val} = TX_{hash}[end-2:] $ or more simply the last two bytes in the hash, and the $ B_{mmtx,t} $ is the block threshold for the MMTTX to be valid. The block threshold $ B_{mmtx,t} $ will be adjusted such that the threshold is high when ordering demand is low and gets lower as ordering demand increases. This will ensure that blocks remain lively even if there is high instantaneous changes in demand for mined transactions. The block threshold will be calculated as follows:

$$ B_{mmtx, t} = t_{max} * \frac{\Delta S_{tx}}{\Delta S_{int} + \Delta S_{tx}} $$

where $t_{max} = 2^{16} - 2^{12}$ to ensure there is always a marginal cost to an MMTX. The $B_{mmtx,t}$ threshold can be computed instantaniously and adjust to the changes in ordering demand in real-time. NOTE: That because a MMTX commits to a block the value of $B_{mmtx,t}$ is deterministic and cannot be changed without changing the commitment or the work done on that commitment, ie the workObject.

It is interesting to note the impact of the block expectation time on the change in $B_{mmtx,t}$ with the total work included in the block. Specifically, an empty block has the nominal expectation time. The block time will increase to maximum of 2 times the expectation time before it logorithmically approaches the nominal expectation time as the block continues to fill. This will actually allow blocks to slow down when there is a high change in demand of ordering, but also gaurantee liveliness as the demand continues to grow.

WorkObject

The interesting implication of MMTX is the creation of a new datastructure that will be referred to as a workedObject. All data that may be inserted or appended to the blockchain highest abstract form is now a workObject. More specifically, a MMTX must take the form of a workObject. Depending on the weight of the workObject, it will become either a header or a MMTX.

Impact on Header

The fields that will be needed to compute a workObject's work, or entropy reduction, need to be removed from the header so that they are not needlessly replicated.

The fields that will be removed from the header are as follows:

Field	Type
ParentHash[2]	common.Hash
Number[2]	*big.Int
Nonce	uint64

The following fields will be renamed:

Old Field	New Field
ParentHash[]	DomParentHash[]
Number[]	DomNumber[]

WorkObject Structure

Field	Type
HeaderHash	common.Hash
ParentHash	common.Hash
Number	*big.Int
TxHash	common.Hash
Nonce	uint64

The astute reader will notice that the fields that were deleted from the header are now included in the workObject structure. The sealHash for the workObject will be computed by hashing all of the fields except for the Nonce. Mining of the workObject will take place by grinding the Nonce field. Once a workObject is found the producer will be able to determine if it is a MMTX or a Block based on the entropy threshold acheived. This workObject can then be combined with either the corresponding Header or Transaction body to create either an MMTX or a block. The MMTX must then be signed by the appropriate private key and the MMTX and the signature can be transmitted to form a transaction. If a block is achieved, the workObject can be combined with the header and optionally the block body to produce a valid header or valid block and transmitted with no further processing.

Effect of MMTX on Adversarial Resiliance

In PoW systems it is shown in {Everything is a Race and Nakamoto Always Wins} that all attacks on safety of a PoW blockchain can be simplified to a private mining attack. This means that in a theoretical network a PoW chain has adversarial resiliance if $(1-\beta) &gt; 0.5$. This is were the classical statement about being resiliant to a %51 attack originates. However, moving beyond the simple analysis, accounting for the fact that the honest majority has a disadvantage due the coordination delay, $\Delta$, it has been shown this decreases to 33% adversarial resiliance. The interesting thing to note here is the effect of the delay, $d_{tx,i,j}$, on the private mining attack. Specifically, if $\max(d_{tx,i,j}) &gt; \Delta$ the network delay can be offset by the processing delay associated with MMTXs which a private miner will need to produce in order to create a competitive privately mined chain greater than length 1. Therefore, it is likely that PoEM with MMTX will create a consensus mechanism that is resiliant to attackers that control the majority of the hashrate.

There is however, a contravening consideration, which is the ability for late joining clients to join the network. Specifically, will a late joining client or a non-nefarious network partition be able to catch up to the honest majority? The answer to this questions depends on the number of threads that a node has to validate MMTXs relative to the number of MMTXs included in a block on expectation.

For example, if a honest node has a modern GPU, it will have > 16,000 threads. Each on of these could be used to validate the SDF of MMTXs in parallel. Thus if the average block has 2,000 MMTXs and the average $mean(d_{tx,i,j}) = 1/2 * Block_{time}$ a late joining client would be able to catch up to the network at a rate $r$, which is 1/16th of clock-time in this example. This could be further improved by running a client with a more performant GPU or multiple GPUs. However, the ability for a client to catch up will only be compressed by honest nodes to a finite degree. This means that if an attacker is running a private chain in which they are creating and referencing MMTXs to enable the creation of a competitive chain, they will suffer a processing delay penalty for a fork of depth, $f$, of $d_{fork} = fBlock_{time}\bar{r}$. This offsets the disadvantage of the honest majority due to the coordination delay and will incrase the adversarial resiliance of the system to > 51% if $Block{time}*\bar{r}&gt;\Delta$.

Impact of MMTX on MEV

Lets explore what would happen here if there was a transaction that can be exploited by being front run by a MEV bot. All MEV exploits normally require a MEV bot to get at least 1 tx in-front of the $tx_{MEV}$ they are trying to exploit. To front run $tx_{MEV}$ the MEV bots would have the option of mining a transaction which has a greater workObject than tx_{MEV} or by attempting to mine an alternate chain tip. Lets assume that there are at least 2 competing MEV bots, Alice and Bob, which have roughly the same amount of hash power which in total are both less than 50% of the hash rate. If Alice finds a MMTX with a workObject greater than the mined $S_{tx,Alice} &gt; S_{tx,MEV}$, Bob will need to mine his transaction such that $S_{tx,Bob} &gt; S_{tx,Alice}$. This back and forth competition will proceed until Alice, Bob, or some other miner finds a entropy of $S_{tx} &gt; S_{int}$ which would lead to the mining of a new block.

Lets say that at this point in time Alice has managed to order her transaction in front of Bobs. That means that the block will have a block entropy of at least $S_{block} &gt;= S_{int} + S_{tx,Alice} + S_{tx,MEV}$.

If Bob is unsatisfied with this result he can try and mine a new tip which is a fork with the block that was just mined. Bobs expected entropy for the nth block will be $S_{block,bob} &gt;= S_{int} + S_{tx,bob} + S_{tx,MEV}$. However, we can assume that Bob will take some period of time, $\delta$ after Alice produces her block to produce a workObject that is greater than Alice's as well as produce a block which meets the intrinsic block entropy threshold.

That means that for the time $\delta$ Bob is additionally competing against the honest network hashrate $\gamma * (1-\beta)$ where gamma is the total network hashrate and Bob's hashrate being the dishonest party is $\beta$. This means that we can quantify Bob's disadvantage in producing a chain with greater entropy with his perferred transaction ording he would need to have greater than 50% of the network hashrate, or would need to achieve a "lucky" result that is outside the expectation value.

Moreover, after Bob produces his block $n$, if he decided to continue mining to try and achieve a win at $n+1$ he would not have any $S_{tx,i}$ to add to the weight of his next block ensuring that he will lose if the $n+1$ honest block has any MMTX workObjects included that are not produced directly produced by Alice.

Copyright

This QIP licensed under the BSD 2-clause license.