WIP: Bulletin Chains (Sharded Inclusion Lists)

This work can be seen as a type of hierarchical consensus where each sub component implements causal broadcast instead of total order broadcast.

• WIP: Bulletin Chains (Sharded Inclusion Lists)
  • Set Up and Goals
    • SUAVE
    • Orderflow Auctions
    • Design Goals
    • Prior Art
  • Proposed Algorithm Description
    • Naive Approach - DAG (Order Indepedent) "RollUps"
    • Better Approach - Parallel Narwhal w/ Independent Validator Sets
    • Better Approach - Parallel Narwhal w/ Validator Sub Duties
    • Better Approach - Hierarchical Vector Clock
    • Open Questions
  • Implementation
  • Prior Art
    • Narwhal
    • Heterogenous Narwhal
  • Motivation
  • Naive Approach
    • Interplanetary Consensus
    • Hierarchical Vector Clocks
    • ChatGPT Recommendations
  • References

Set Up and Goals

Establishing a total order of transactions is one of the main scalability bottlenecks in blockchain networks. There have been numerous attempts at scaling blockchains, exemplified by the Lightning Network, Optimistic and ZK roll ups, sharding, and many more. Here we outline an approach for scaling built upon the observation that a total ordering is not required for all applications looking to achieve consensus faster than their base chain.

SUAVE

After Flashbot's successfully isolated the centralizing effects of MEV to the block builder role in Gasper PoS using a PBS design, the next goal became to decentralize the block builder role itself. In attempt to do so, the MEVM was released, a modification of the EVM with precompiles to support MEV use cases, all running on top of a network of Trusted Execution Environments (TEEs). This architecture allows users to send bids to an encrypted mempool and allow their bids to be processed by MEV applications written as smart contracts in Builder Solidity. By offering a higher level blockchain where these programs live, users are guranteed that the rules of the orderflow auction they grant premission to, are verifiably run over their bids.

One of the most powerful parts of the MEVM design is that components that are common between OFAs, Solver Networks, RFQs, and Block Building can all be reused. Below we can see an example of what an early MEVM ecosystem might look like and how the components interact.

Orderflow Auctions

Credible auctions on SUAVE consist of three parts:

• A well designed mechanism - i.e. no leaks and optimal matching, routing, etc.
• A censorship resistant inclusion list of bids that were available at auction run time
• Proof of auction computation (ZK, TEE signature, etc)

Using the last two pieces a user should be able to construct a fraud proof in the event that their bid was not included.

One example of a MEVM powered orderflow auction is a walrassian auction, "a type of simultaneous auction where each agent calculates its demand for the good at every possible price and submits this to an auctioneer. The price is then set so that the total demand across all agents equals the total amount of the good." [1].

To translate this example onto SUAVE we simply need to write our auction logic into a smart contract with solidity, deploy it, and then users can start to send bids to the chain to be incorporated into the auction. Because the auction does better with more inputs (not sure this is strictly true) and users want censorship resistance, they can store those encrypted transactions onchain to be used when enough bids have been aggregated.

This observation, that our system needs consensus on a set, not on a single ordering, will form the basis for all designs mentioned in this document. Another way to say this is that we do not require Total Order Broadcast, instead we can use one of many other options [2]:

• Causal Broadcast: This ensures that if a message m1 causally precedes another message m2, then no correct process delivers m2 before m1. It respects the causal order but not necessarily the total order.
• FIFO Broadcast: This ensures that messages from the same sender are delivered in the order they were sent. However, messages from different senders can be delivered in any order.

Of the above broadcast types, the Reliable Broadcast variant of each should be used. In reliable broadcast, the goal is to ensure that if a correct process broadcasts a message, then all correct processes will eventually deliver it. It doesn't guarantee any specific order of delivery.

Lastly, it should be noted that this design choice forces a strong opinion on all future auctions living on SUAVE, which should not be taken lightly.

Design Goals

• Horizontal Scalability - The way to achieve higher TPS should not be by increasing size of validator hardware.
• Tunable Security - Trading off security and liveliness risk for faster consensus should be an option left to developers and users. At one extreme we have large and geographically decentralized validator sets and at the other end we have small and hyper local validator sets.
• Sub SUAVE (main chain) block times - any design should only be chosen if it can enable faster sychronous periods than the SUAVE main chain (currently ~2seconds).

Prior Art

For brevity I have moved prior art to the end but will highlight the key ideas from each:

Narwhal [3]:

• Separate data out from consensus and use fixed size references (metadata) to lower message sizes
• Coming to consensus on what transactions are avaiable before ordering eases the job of the consensus protocol responsible for ordering.

Heterogenous Narwhal [4]:

• Two protocols, each with their own narwhal mempool and some overlapping validators, can enable atomic cross-chain transactions by super-imposing their DAG-mempools
• If overlapping validators are small there is a liveliness risk. Somehow they lessen this but not clear from WIP paper.

A large inspiration for Heterogeneous Narwhal is the validator topology in Cosmos and Cosmos Hub where some nodes validate for multiple networks and others a single network.

Hierarchical Consenus [5]:

• Instead of algorithmically assigning node membership and load balancing the distribution of the state, this ia an approach where users and miners are grouped into subnets in which they can freely partake.
• Subnets help secure their descendant subnets through checkpointing—which helps alleviate attacks on a child subnet, such as long-range and related attacks in the case of a PoS-based subnet. (How this is different than rollups Im not sure yet)

Hierarchical Consenus [5]:

• Instead of algorithmically assigning node membership and load balancing the distribution of the state, this ia an approach where users and miners are grouped into subnets in which they can freely partake.
• Subnets help secure their descendant subnets through checkpointing—which helps alleviate attacks on a child subnet, such as long-range and related attacks in the case of a PoS-based subnet. (How this is different than rollups Im not sure yet)

Proposed Algorithm Description

Before getting into designs let's go through an example distributed block building flow that we can use as a basis to compare across designs. This flow starts with users sending in bids and ends with blocks being sent to validators.

Our example set up consists of:

• validators set v = { v₀, v₁, …, v_n } where n = 9
• 5 SUAVE apps : UniX, CowSwap, Mev-Share, Default Builder, Otter Builder
• 3 sub-committees, SUAVE, UniX, and CowSwap:
  • with validator sets respectively v_m, v_u, and v_c where v_m ∪ v_u ∪ v_c = v the validator set of the entire network
  • the first validator in UniX is denoted v_u1 which could be equivalent to any v_i for i <= n
• Δ is the max length of the sychronous period during consensus.
  • Δ_S, Δ_U, and Δ_C are the sychronous periods for subcommittees SUAVE, UniX, and CowSwap respectively
  • additionally our example applications have preferences such that : Δ_S > Δ_C > Δ_U meaning that the consensus time for main SUAVE chain is strictly greater than the consensus time for CowSwap which is strictly greater than Uniswap consensus time.

Transactions/Bids/Confidential Compute Requests:

• 4 bids to UniX
  • 2 calls to run the UniX auction
• 2 bids to CowSwap
  • 1 call to run CowSwap auction
• 2 bids to Mev-Share
• 6 calls to build blocks, largely clustered towards the end of the orderflow when we naturally might expect the most calls to perform block building computation.

Here is a view from the current SUAVE chain of how a progression of txns like this would go:

Note: One thing this diagram does a poor job of is differentiating confidential compute requests, which can trigger sending a block to a validator for example. The effects from confidenitla computation which results in a block being sent isn't necessarily only registered once the tx responsible for the request lands onchain. The block will be sent to a validator once an executor node runs the request and then whatever callback that function returns will then eventually make it's way to the chain.

Naive Approach - DAG (Order Indepedent) "RollUps"

I am calling this a Roll Up because it's pushing updates back to the main chain with those arrows, but the key point is it's only pushing summaries of what was available, not what the order of things received was.

Notice that mev-share bids can still go onto the main chain. Ideally subnets are completely optional.

This satisfies our goal of set up where ΔU < ΔC < ΔS, but is it as fast as possible?

Remember that Observation 1 implies that the ordering of Bid's within a bucket or slot don't actually matter since the user's mechanism should be ordering independent. Thus we may be wasting communication rounds in order to come to agreement upon ordering.

ToDo: Create chart similar to below with communication complexity of Narwhal compared to PBFT and Gasper.

The problem with the security of checkpointing is that you get safety but the use case we have in mind doesn't require safety. Because we are influencing how other chains are working, as soon as the next block is produced it doesn't matter if we retroactively look back and say "oh hey this was invalid" like rollups do

Better Approach - Parallel Narwhal w/ Independent Validator Sets

A couple thoughts here:

• 1. I'm not sure this protocol is sound or captures the concept of offchain transactions
• 2. Not sure it makes sense for the SUAVE main chain validators to propagate back to the UniX and CowSwap Validators.
  • I think it does because they want to know they're being included in the chain. But do they need to submit a vote back? If so that would mean the need the CowSwap blocks and we're in the same place. Thus perhaps the could send back votes siging off on the parts that come from their chain and the SUAVE main chain validators would aggregate these partial signatures from subcommittees and full signatures from SUAVE main chain validators.
• 3. This fragments our security from 9 nodes to 3 per chain. One point to note is that from a processing powering standpoint, the subcommittee validators could be much less resource intensive since they only maintain bids for one protocol and have lower communication costs. But typically security is referred to as the stake associated, not the resources of the machine running the validator.

Better Approach - Parallel Narwhal w/ Validator Sub Duties

This is the same as the prior approach except that UniX and CowSwap validators would also take part in the voting on blocks proposed by SUAVE main chain validators aka all validators are SUAVE main chain validators except some have extra duties.

The advantage of this approach though would be that we don't fragment our validator set security for the main chain.

Better Approach - Hierarchical Vector Clock

Maybe I'm not sure.

A hierarchial vector clock is well suited for modern, message-passing distributed systems which make use of highly hierarchical communication networks.

Open Questions

• What is the aggregate fork choice rule?
• Interaction between subnets?
• Are subnets sovereign or a hierarchy?

Cons of this approach:

• bids cannot span across multiple subnets unless something like heterogenous narwhal/paxos is used
• Is the above true and is it an issue?
  • Narwhal still has some expected TPS, when we push this boundary don't we encounter the same issue? (troll answer: if we used this as a reason not to build then ethereum would've never started. But it is a fair question to consider in the limit)

Implementation

We can use a similar idea as mempool IDs in the ERC 4337 bundler spec potentially, but this doesn't answer the stake question.

The metadata associated to each mempool that a bundler supports is documented and stored in IPFS (a copy of this is also suggested to be submitted to eth-infinitism Github repo). This IPFS hash of the file is called mempool-id and this is used as the topic for subscription in the bundlers. The proposed structure of the mempool metadata is as follows

chainId: '1'
entryPointContract: '0x0576a174d229e3cfa37253523e645a78a0c91b57'
description: >-
  This is the default/canonical mempool, which will be used by most bundlers on
  Ethereum Mainnnet
minimumStake: '0.0'

The mempool-id of the canonical mempool is TBD (IPFS hash of the yaml/JSON file).

Questions:
- Can anyone deploy mempool IDs?
- How do users know the safety of the mempool?
- How do

Prior Art

Narwhal

Directed acyclic graphs (dags) feature in several recently proposed consensus
protocols Danezis et al. 2022; Keidar et al. 2021; Spiegelman et al. 2022. - 🔗 sauce

Narwhal claim: The leader is the bottleneck

Narwhal ideas:

• tx data is not included in consenus => Smaller message size
• Parallelization via workers

Key difference with heterogenous narwhal is that we can have varying validator sets for underlying certificates. This of course comes at a risk of liveliness, but ideally the liveliness of a "higher order" subnet is not affected by an underlying subnet being offline.

Is this a difference: In our SUAVE use case, the transactions that mempool is coming to consensus on availability, and the resulting computation from the auction, don't need to be run on the SUAVE chain. They just need to end up in a block sent to the validator on a different domain. Although eventually I think we should

central narwhal concepts

• each validator can propose at most one block at each height;
• each block after genesis must reference a quorum (i.e., at least 2f + 1) of
  blocks of the previous round;
• a block needs to be referenced from a weak quorum (i.e., at least f + 1) of
  blocks the next round to be a leader block (a.k.a. anchor).
• fork choice rule is such that each validator attests to any block it sees as long as it is the first from that validator for that round and as long as it is valid ( a notion defined later )

System Assumptions

• Message-passing system with a set of ( n ) parties.
• Adversary can corrupt up to ( f < \frac{n}{3} ) parties.
• Asynchronous eventually reliable communication links among honest parties.

Narwhal Mempool Abstraction

• Block: A block ( b ) contains a list of transactions and references to previous blocks. Its unique digest ( d ) is used as its identifier.
• Rounds: Each validator maintains a current local round ( r ), starting at zero. Validators accumulate transactions into a transaction list and certificates of availability for blocks at ( r ) into a certificate list. Once certificates for round ( r - 1 ) are accumulated from ( 2f + 1 ) distinct validators, a validator moves to round ( r ) and creates a block for the new round.
• Operations:
  • write(d,b): Stores a block ( b ) with its digest ( d ).
  • valid(d, c(d)): Checks if a certificate is valid.
  • read(d): Returns a block ( b ).
  • read_causal(d): Returns a set of blocks ( B ) with a transitive happened-before relationship with ( b ).

Algorithm Description

1. Block Creation: Once a validator has accumulated certificates for round ( r - 1 ) from ( 2f + 1 ) distinct validators, it moves to round ( r ), creates, and broadcasts a block for the new round.
2. Block Validation: A block is valid if it contains a valid signature from its creator, is at the local round ( r ) of the validator checking it, and meets other specified conditions.
3. Certificate of Availability: Once the creator gets ( 2f + 1 ) distinct acknowledgments for a block, it forms a certificate of block availability. This certificate is then shared and potentially included in blocks at round ( r + 1 ).
4. Garbage Collection: Validators can decide on the validity of a block only from information about the current round. Blocks from earlier rounds can be safely stored off the main validator. Validators agree on the garbage collection round to maintain consistency.
5. Reliable Broadcast: Narwhal uses a pull mechanism that is DoS resistant and efficient. At any time, only ( O(1) ) requests for each block are active, and all pending requests can be dropped after receiving a correct response.

function MAIN_LOOP(validator v):
    WHILE TRUE DO
        TRANSACTION_ACCUMULATION(v)
        CERTIFICATE_ACCUMULATION(v)
        IF COUNT(v.certificate_list) ≥ 2f + 1 THEN
                v.r ← v.r + 1
                BLOCK_CREATION(v)
        END IF
        BLOCK_VALIDATION(v)
        CERTIFICATE_FORMATION(v)
        CERTIFICATE_HANDLING(v)
        GARBAGE_COLLECTION(v)
    END WHILE

Properties

• Integrity: For any certified digest ( d ), all invocations of read(d) by honest parties return the same value.
• Block-Availability: If read(d) is invoked after write(d, b) by an honest party, it returns ( b ).
• Containment: For every block ( b' ) in ( B ), the set ( B' ) returned by read_causal(d') is a subset of ( B ).
• 2/3-Causality: A successful read_causal(d) returns a set ( B ) that contains at least 2/3 of the blocks written before write(d, b).
• 1/2-Chain Quality: At least 1/2 of the blocks in the returned set ( B ) of a successful read_causal(d) were written by honest parties.

–

Heterogenous Narwhal

The present paper is rather about heterogenizing existing
protocols, choosing dag-based consensus as an example that goes together with
heterogeneous Paxos I. Sheff et al.

Along the way, we shall describe how heterogenization applies differently to
matters of availability and integrity I. C. Sheff et al. 2019:
availability all relevant transaction data is certified to be available
integrity the available data is unaltered, e.g., no double spends, equivocation,
etc..

Motivation

As running example, let us consider two base ledgers with proof-of-stake.
The validators set out to build a single shared Narwhal dag that comprises the
information of two separate “native” Narwhal dags. The rationale is that then
blocks may contain cross-chain transactions that can be executed atomically.

Naive Approach

Naïve superposition of narwhal DAGs comes at the price of risks to liveliness.

Now, as a first thought, we can restrict anchor blocks to those that satisfy the conditions for both base ledgers; in fact, we obtain a safe implementation of a combined Narwhal mempool. However, apart from obvious questions about skewed incentives for the validators that only hold stake of one of the base ledgers, the “perfect” safety guarantees of the naïve superposition come at the price of risks for liveness: roughly, superimposing Narwhal dags leads to a “less live” dag, relative to each one of the base ledgers.

Interplanetary Consensus

https://docs.filecoin.io/basics/interplanetary-consensus/hierarchical-consensus

Hierarchical Vector Clocks

ChatGPT Recommendations

Q: What are example of algorithms which implement casual broadcast?

A: Causal broadcast is a communication primitive that ensures messages are delivered respecting their causal order. Several algorithms have been proposed to implement causal broadcast in distributed systems. Here are some notable ones:

1. Vector Clocks:

   • Introduced by Colin Fidge and later independently by Friedemann Mattern.
   • Each process maintains a vector of counters, one for each process in the system.
   • When a process sends a message, it increments its own counter in its vector.
   • Upon receiving a message, a process updates its vector clock using element-wise maximum with the vector in the received message and then increments its own counter.
   • Messages are delivered only when their vector clock is such that it can be causally delivered (i.e., the message's vector is just one unit ahead of the receiving process's vector for the sender's entry and not ahead for all other entries).

2. Logical Clocks (Lamport Timestamps):

   • Introduced by Leslie Lamport.
   • Each process maintains a single counter.
   • The counter is incremented before each event, and its value is sent with every message.
   • While simpler than vector clocks, Lamport timestamps only provide a partial ordering of events. They can be used to determine if one event causally precedes another but not if they are concurrent.

3. Birman-Schiper-Stephenson Protocol:

   • A specific protocol for causal broadcast using vector clocks.
   • It uses vector clocks to timestamp messages and employs a delivery mechanism that ensures causal order by buffering out-of-order messages.

4. Triggered Message Sequence Charts (TMSC):

   • A formalism that combines message sequence charts with triggers to specify causal relationships between messages in distributed systems.

5. Dependency Sequences:

   • An optimization over vector clocks for systems where the communication graph is sparse. Instead of maintaining a full vector, processes maintain dependency sequences that capture causal dependencies more compactly.

6. Hierarchical Vector Clocks:

   • An optimization for large-scale systems organized hierarchically. It reduces the size of vector clocks by maintaining different vectors for different hierarchical levels.

These algorithms and protocols provide mechanisms to ensure that if a message m1 causally precedes another message m2, then no correct process delivers m2 before m1. The choice of a particular algorithm or protocol often depends on the specific requirements of the distributed system and the trade-offs between time and space complexity.

References

[1] : https://en.wikipedia.org/wiki/Walrasian_auction
[2] : https://www.doc.ic.ac.uk/~ac3419/notes/year3/distributed_algorithms/03_fct_broadcast.pdf
[3] : https://arxiv.org/pdf/2105.11827.pdf
[4] : https://github.com/anoma/research/blob/master/distributed-systems/heterogeneous-narwhal/HeterogeneousNarwhal.pdf
[5] : https://research.protocol.ai/publications/hierarchical-consensus-a-horizontal-scaling-framework-for-blockchains/delarocha2022.pdf