Mempool Communication and Design

[isheff]

Task description

Arguably, we can break down Typhon into layers, which include:

• Transaction dissemination from Clients to Storage (probably on validators, who may also be orderers)
• Mempool Organization, wherein organized portions of the transactions are identified for consensus to decide on. (This Issue)
• Consensus, which chooses an ever-growing sub-dag from the mempool representing "ordered" transactions.
• Execution, wherein state "after" each transaction is calculated and published.

In order to order transactions that have been stored, we need to organize them into a partially-ordered DAG structure from which Consensus can choose an ever-growing non-conflicting closed sub-DAG. I suspect that something similar to Narwhal can help us here, but we have to adapt it for the Heterogeneous setting.

Ultimately, we want this design formalized in something like TLA+, and integrated with the Heterogeneous Paxos spec. We may even want to prove some safety or liveness (or even fairness) properties along the way.

Sub-tasks (no particular order)

• Describe where and how Narwhal fits in Anoma's layered architecture (see figure)
• Analyse Narwhal for the mempool layer (in depth)
• Study an easy example of TLA+ (perhaps Paxos)
• Document findings
• https://github.com/anoma/specs/issues/306
• Heterogeneous Narwhal English Spec #41
• Heterogeneous Narwhal Formal Spec #42

Definition of Done

• We have a human-readable document of the mempool layer architecture
• We have formalized the design in TLA+

[nzarin]

@heindel I just extended the original text with some sub-tasks and DoD. Do you agree?

[heindel]

DoD is great
Formalize the design of the mempool layer in TLA+ : here I'd proceed as follows

• find highest sensible level of abstraction (inspired by lamports lecture on paxos
• refine one step down for inclusion of validators (no workers)
• refine one step down for splitting up validators (primaries vs workers)
• "ideally" / refine down to communication as in issue anoma/specs#306

[nzarin]

Layered architecture and some brief elaboration : https://hackmd.io/_LxxCSAmRwW28fNquMW81A

[nzarin]

@isheff a few questions you might have an answer to regarding the problem of "which worker receives what transaction?" :

1. How do the public identifiers (I assume public keys?) from worker machines look like?
2. Same for primary machines
3. How do transaction messages look like? How are they identified?
4. Can they be from the same address space?

Perhaps we can use a scheme where some distance function is leverages to decide which worker gets what transaction? For example, imagine we have a distance function XOR(a, b) where a is a (hashed) transaction and b is the pk of the worker. Then, the worker for which this distance is smallest could be selected as the receiver of this transaction. This will also later help the execution engine to locate the transaction (which is by then in some batch) in worst case O (log n ) time.