Cluster mempool definitions & theory

Cluster mempool definitions & theory

Posted on: December 11, 2023 04:57 UTC

In the discussion of optimizing transaction ordering within a blockchain block, several key points are addressed regarding the selection and linearization of transactions.

The primary focus is on the optimization for the last few transactions in a block to maximize the use of space by breaking up clusters into smaller chunks, which provides more flexibility for fitting transactions into the available space. The significance of splitting these clusters is highlighted as being more crucial than the order in which they are arranged since achieving a strictly unique "perfect" linearization is not possible due to the potential for equally valid arrangements.

The conversation delves into the technical aspects of defining an optimal linearization. It is suggested that the optimal linearization of a set of transactions ( G ) can be expressed as the sum of the first valid linearization of the highest-feerate subset of ( G ) plus the optimal linearization of the remaining transactions in ( G ). This definition leads to a proof strategy for the existence of an optimal linearization without constructing it explicitly, using the function ( f(L) ) that counts linearizations greater than or equal to ( L ).

A contradiction is used to prove the existence of an optimal linearization, where if an assumed optimal linearization does not compare greater than or equal to all other linearizations, a new linearization can be created through a merge process that will surpass the original, contradicting its optimality. Additionally, an alternative proof is proposed, which involves considering the set of maximal elements among valid linearizations. If there is only one maximal element, it is inherently optimal. However, if there are multiple maximal elements, merging them would result in a superior linearization, which contradicts their status as maximal.

Overall, the conversation underscores the complexity of transaction linearization in a blockchain context, with a focus on theoretical approaches to defining and proving the existence of an optimal solution rather than practical implementation details.