# Upholding CR in an encrypted mempool with trusted sets ## Introduction Encrypted mempools can let key publishers specify which other key publishers they trust not to front-run transactions, as proposed in [EIP-8105](https://eips.ethereum.org/EIPS/eip-8105). This is beneficial under commit–reveal schemes, where a key publisher could probabilistically front-run and decide not to reveal, and where a failure to reveal is observable by all parties. One issue with such a design is upholding CR, since transactions with incompatible trusted sets cannot always be included together. Without a fixed rule, a builder could choose among the compatible sets in a way that censors transactions. ## Possible mechanism A possible mechanism will here be outlined. Whether it is desirable or not remains to be seen. The biggest downside is the introduction of IL roots and added complexity. The ILs that apply to a bid are determined canonically under the IL rules, and the builder commits to their roots. Validators reject a bid that omits a required IL root. Everyone then derives and deduplicates the same candidate commitments from those roots. The candidate set is bounded before selection so that its total gas obligation fits within the reserved ToB capacity. The protocol selects the compatible set with the highest total ToB fee, and the builder must include it. The ToB fee used for this score is burned, so the builder cannot recover the weight added to a preferred set. The mechanism uses the directional trust relation defined in EIP-8105. If A trusts B, transactions using B may come before transactions using A. Trust also follows paths. If A trusts B, B trusts C, and C trusts A, all three publishers trust one another through the cycle. Publishers that can reach one another are therefore grouped into one node. After all such groups have been formed, the remaining graph has no cycles: it is a directed acyclic graph, or DAG. Each node is assigned a weight equal to the total ToB fees of its candidate commitments. Nodes without candidates receive weight zero but remain in the graph, since they may connect two candidate nodes through indirect trust. The exact selection is found using the standard [weighted longest-path algorithm for a DAG](https://en.wikipedia.org/wiki/Longest_path_problem). The nodes are first placed in an order where every trust arrow points forward. They are then processed in the opposite order, so that every node a given node points to has already been processed. For each node, the algorithm records its own weight plus the largest total available from any node it points to. It also records which next node produced that total. Once all nodes have been processed, the algorithm chooses the candidate-containing node with the largest recorded total and follows the recorded choices. This gives the path with the highest total ToB fee. Any compatible set forms such a path under the reachability relation, possibly with zero-weight nodes between its candidate nodes. For example, given: ```text A → B → C ``` the graph calculation produces the path `A → B → C`. The block order is reversed: ```text C → B → A ``` This follows from the EIP-8105 rule: B trusts C, while A trusts both B and C. Ties are resolved locally during the calculation. Each grouped node has a fixed identifier, such as the smallest publisher identifier it contains. If several next nodes produce the same total, the node with the smallest identifier is chosen. The same rule resolves a tie between possible starting nodes. All candidate commitments belonging to nodes on the winning path are mandatory and form a prefix of the LUCID commitment order. Other commitments may only be added after the mandatory prefix and cannot change which IL commitments are selected. ## Complexity Validators can keep the trust graph, its grouped nodes, and their ordering between blocks. Selection uses the graph from the parent state, so trust updates in a block only affect later blocks. The protocol can bound the number of active publishers, direct trust links per publisher, candidate commitments, and trust updates per slot. Clients may update the stored graph incrementally, but the reference procedure can rebuild it whenever it changes. The hard graph limits ensure that even a full rebuild remains bounded. Let $n$ be the number of candidate commitments, $p$ the number of active publishers, and $e$ the number of direct trust links. Grouping the candidates, constructing the grouped graph, and finding the winning path takes: $$ O(n+p+e) $$ If each publisher may declare at most $d$ direct trust links, then $e \leq pd$, giving the fixed worst-case bound: $$ O(n+pd) $$ The weighted longest-path calculation itself is linear in the stored graph. The number of candidate transactions therefore does not produce a quadratic transaction-by-transaction comparison. ## Relationship to whitelist design A separate whitelist mechanism has [recently been proposed](https://hackmd.io/65f2AsqPSSGl4ea_eG2-jQ). Such a design is inherently simpler, if the trusted set can be treated as a single node.