arXiv CSopen access

AMP: Arc Multi-Proposer Protocol with Bounded Inclusion Guarantees

AMP: Arc Multi-Proposer Protocol with Bounded Inclusion Guarantees Daniel Cason Adi Seredinschi

Gordon Liao Alessandro Sforzin

Sergio Mena João Sousa

Nenad Milošević Preston Vander Vos

arXiv:2605.23677v1 [cs.DC] 22 May 2026

Circle

Abstract Blockchain systems that settle financial transactions face a structural tension: the single validator that assembles each block holds unilateral power over transaction inclusion and ordering. Traditional markets curb this very power through front-running and marketmanipulation laws. Regulators have flagged the absence of such rules as a first-order concern for blockchain-based financial infrastructure. In response, we introduce AMP, a multiproposer protocol, on top of the Tendermint consensus algorithm, where no validator can control the flow of transactions into blocks. Instead, dedicated nodes called proposers sit between users and validators. They collect user transactions, group them into payloads, and broadcast the payloads to all validators. Consequently, there is no mempool, and AMP applies the design principle of separating dissemination from agreement, which can lead to higher throughput. Validators publicly attest to receiving payloads and run consensus to decide the set of payloads to include in the next block. When all correct validators attest to a given payload, AMP guarantees that payload will be included in the next block; a block thus contains payloads from multiple proposers, allowing for bulk finalization. This bounded inclusion guarantee along with a deterministic ordering algorithm which is run over all payloads included in a block, curbs the power of any single validator. Validators no longer control what is included in a block, nor can they arbitrarily order the contents of blocks.

1

Introduction

Most blockchain systems delegate block construction to a single validator per height. This validator—the block assembler—decides which transactions enter the block and in what order. The design is a pragmatic inheritance from classic BFT consensus [22, 49], but it concentrates two powers in one actor: the power to exclude transactions and the power to order them. The exclusion power enables censorship as the assembler can delay or omit transactions at will. The ordering power enables maximal extractable value (MEV) [26, 32, 33]. The block assembler can reorder transactions to extract profit at users’ expense through strategies such as front-running and sandwich attacks. In traditional financial markets, analogous behavior is prohibited by regulation. The Bank for International Settlements has identified validatordriven transaction reordering as “activities that would be illegal in traditional markets” [7]. For blockchains that aspire to settle regulated financial flows such as foreign-exchange trades or capital-markets settlement, this gap between protocol design and market-integrity standards is a very important concern. The single-assembler model also creates a performance bottleneck. Throughput is capped by the assembler’s bandwidth, leaving the aggregate capacity of the remaining validators idle. Further, block dissemination and ordering are tightly coupled. Large blocks take longer to propagate to all validators and thus increase consensus latency. This highlights the inherent tradeoff between throughput and finalization time. Lastly, transactions are typically disseminated twice.

1

First, as part of mempool gossip across all validators, and second, the assembler sends them again in the proposed block. This redundant communication is wasteful. The above problems are well recognized. For example, to mitigate transaction exclusion risks, inclusion-list proposals such as FOCIL [47] in Ethereum constrain the block assembler’s discretion by enforcing transaction inclusion via validator committees. MCP [33] creates a multi-proposer layer with censorship resistance that works with many consensus algorithms. To address performance concerns, DAG-based protocols [27, 43, 8] allow all validators to propose blocks at the same time and can lead to higher throughput, while multi-leader protocols [44, 45] parallelize the workload by partitioning transactions across concurrent consensus instances. This list of solutions is not exhaustive, and highlights that multi-proposer designs can be compelling. As part of our research and development on the Arc L1 blockchain [38], however, we encounter a unique set of conditions, and we explore a different approach. We introduce the Arc Multi-Proposer Protocol, or AMP. This is a protocol layer that composes specifically on top of a Tendermint consensus algorithm to enable multiple concurrent proposers. AMP inherits the safety and liveness guarantees of Tendermint, which has been formally verified and battle-tested over years of deployment [3, 4, 14, 21]. The design separates two roles that the single-assembler model conflates: • Proposers collect transactions from end-users, package them into bundles called payloads and disseminate each payload to all validators. Any node can act as a proposer—this is the “multi” in multi-proposer. • Validators participate in Tendermint consensus. They observe payloads that proposers broadcast, attest to them, and agree on assembling multiple of them into a block. The separation of concerns is architecturally important: proposers are responsible for transaction dissemination (bandwidth-bound), while validators are responsible for attestation and agreement (latency-bound). Attestation is done by exchanging payload identifiers via vote extensions. A vote extension is a feature of Tendermint consensus implementations which allows validators to attach application-defined data to their consensus votes. The concern of proposers is the collection and propagation of user transactions as they represent the limiting factor on the network’s throughput. The concern of validators is maintaining safety and liveness to keep the network secure. In this way, AMP decouples dissemination from agreement and enables higher throughput. It does so on two grounds. First, it eliminates the egress bandwidth bottleneck at the block assembler, as it avoids disseminating bulky blocks of transactions, and instead only deals with concise payload identifiers. Second, the network propagates each user transaction only once, as part of a payload. We say that a payload is certified if all correct validators attest to that payload via their vote extensions. The key invariant is this: If a payload is certified, it must be included in the next block. Any block proposal that omits a certified payload will be rejected by honest validators. This bounds the assembler’s discretion, resulting in a bounded inclusion guarantee: any payload attested by all correct validators by height h is finalized at height h+1. Bounded inclusion addresses the assembler’s exclusion power. AMP also constrains the assembler’s ordering power through a deterministic ordering function that fixes the execution sequence of all finalized transactions within a height. We discuss the MEV implications and connection to competitive priority ordering [40] in Section 5.1. Beyond the technical contribution, the guarantees that AMP provides address concerns that international standard-setting bodies have articulated for blockchain infrastructure in financial markets: deterministic settlement finality, protection against validator-driven transaction manipulation, and operational resilience against single points of failure [7, 25, 29]. AMP addresses each of these directly (i) it inherits Tendermint’s deterministic finality, (ii) constrains the block assembler’s inclusion and ordering power, and (iii) distributes across the set of proposers the power over what payloads, and therefore which transactions to include in a block. 2

As mentioned, AMP is grounded in our work on Arc. This provided the motivation for a Tendermint-based multi-proposer design, because Arc is production-ready and operating on top of Malachite [36], a state-of-the-art Tendermint implementation. Replacing this would carry significant risk, so it is important to build on top of this existing robust foundation. The architectural separation between proposers and validators is also an interesting design decision in the context of Arc. This decouples security and reliability concerns (which validators cover), from participation in block construction (which proposers cover). It could be useful that many, various parties can participate in block construction as proposers, for instance institutions engaging in foreign exchange, stablecoin payments, or teams that operate Automated Market Making protocols. But these parties need not be validators themselves, which have specific requirements in Arc [38]. There can be an overlap between the two types of roles, e.g., a validator could also be a proposer, but this decoupling allows the two to scale and specialize independently. Contributions.

We summarize our contributions as follows:

1. We introduce AMP, a protocol that composes on top of the Tendermint consensus algorithm. It inherits the safety and liveness guarantees of the underlying algorithm, while enabling multiple concurrent proposers. 2. AMP decouples dissemination (proposers) from agreement (validators), which is a known strategy to improve throughput. This design also removes the need for a mempool. 3. We also prove that AMP provides bounded inclusion, which, combined with deterministic ordering, fixes the execution sequence of finalized transactions, bounding the block assembler’s discretion over ordering and inclusion of transactions in a block. Additionally, we provide correctness proofs for AMP, analyze the protocol’s complexity, and show that it matches existing lower bound latency for guaranteed transaction inclusion [1]. Organization. The rest of this article is organized as follows. Section 2 presents the system model, Section 3 introduces the building blocks of AMP, and Section 4 describes the protocol. Section 5 discusses design tradeoffs and MEV implications of AMP. Section 6 surveys related work and Section 7 concludes the paper. Appendixes A and B argues the protocol’s correctness and analyzes its complexity.

2

System Model

AMP assumes a distributed message-passing system composed of a dynamic set of processes, or nodes. The set of nodes may evolve over time as (non-validator) nodes join and leave the network. Communication takes place over point-to-point channels. AMP considers the Byzantine failure model, where faulty nodes may behave arbitrarily and in potentially malicious ways. This includes crash faults, where a node stops executing and may later recover. A subset of nodes plays the role of validators and executes the Tendermint consensus algorithm [15]. For the sake of simplicity, the set of validators is assumed to be fixed; the handing of dynamic validator sets is outlined in Section 5.3. As detailed in Section 3.2.1, Tendermint assumes that less than one third of the validators are faulty. Proposers in AMP are nodes that intermediate the interaction between users that submit transactions to the network and validators that assemble blocks. Unlike validators, the set of proposers may vary over time. In theory, any node can play the role of proposer, but when describing AMP we assume that all proposers are honest. The implications of faulty proposers are discussed in Section 4.4 (at protocol level) and in Section 5.3 (at application level).

3

Nodes are not assumed to have global knowledge of the full network membership. The network is partially connected, meaning that not every pair of nodes can communicate directly with each other. Each node maintains connections to a subset of nodes, referred to as its peers. Messages destined to non-peer nodes are relayed through intermediate peers. The network is configured so that it is guaranteed that every pair of correct nodes, which are not peers, can rely on correct intermediate nodes to relay exchanged messages. In other words, it is assumed that Byzantine nodes cannot prevent the communication between correct nodes. Messages exchanged in the consensus algorithm are authenticated using digital signatures under a public-key infrastructure (PKI). Message signatures produced by validators can be verified by any node and safely relayed by intermediate peers without losing validity. This transferable authentication model [19] ensures message integrity and non-repudiation. AMP operates in a partially synchronous network [28]. The network may behave asynchronously for a period of time, but eventually becomes synchronous. More precisely, there exists a Global Stabilization Time (GST) after which message transmission delays are bounded by some constant ∆. Neither GST nor ∆ are known a priori by the nodes. AMP inherits the liveness guarantees of Tendermint, proved for the partially synchronous model [15].

3

Building Blocks

We design AMP on top of a dissemination layer (Section 3.1) and an agreement layer (Section 3.2). The design treats these as semi-opaque building blocks, formally defined as follows.

3.1

Dissemination Layer

The dissemination layer allows proposers to send payloads to all validators. It is defined in terms of a broadcast primitive, used by proposers to submit payloads to validators, and a deliver primitive, that notifies the reception of a payload to a validator. We consider a weak form of broadcast [18], known as Best-Effort Broadcast (BEB), formally defined by: • BEB-Validity: If a correct sender node s (proposer) broadcasts a payload p, then every correct destination node (validator) eventually delivers p. • BEB-Integrity: If a destination node (validator) delivers a payload p from sender s and s is a correct node (proposer), then s has broadcast p. BEB is an unreliable broadcast primitive. Delivery of payloads is only guaranteed when the sender (a proposer) is correct—and potentially re-sends the same payload multiple times. If the sender of a payload p is faulty, p may only be delivered to a subset of correct destinations (validators). This is particularly true when a proposer is Byzantine, in which case it may send p to some validators and an equivocating different payload p′ to other validators. As a result, AMP’s correctness should not rely on dissemination-layer guarantees, but on the properties of the agreement layer and the proper construction of the multi-proposer protocol.

3.2

Agreement Layer

The agreement layer enables validators to agree on each block of transactions to append to the blockchain. It runs consensus, defined in terms of proposed values that are eventually decided. We consider a variant of the Byzantine consensus problem that observes the following properties: • Agreement: No two correct validators decide on different values. • Termination: All correct validators eventually decide on a value. • Validity: A decided value is valid, i.e., it satisfies the predefined valid() predicate. 4

This variant of BFT consensus adopts an application-specific valid() predicate to indicate whether a value is valid [20]. In the context of typical blockchain systems, the proposed value is a block and it is only valid if it contains an appropriate hash of the last block added to the blockchain. Moreover, the block should only include valid transactions, where transaction validity is defined by the semantics of the application that builds on top of the blockchain. 3.2.1

Tendermint Consensus

The Tendermint consensus algorithm [15] is AMP’s specific agreement protocol. Tendermint proceeds as a sequence of consensus instances, called heights, where each height decides a value. A height consists of one or more rounds, always starting from round 0. Each round is led by a designated validator, the block assembler1 , and consists of an attempt to reach a decision. Let n denote the number of validators and f the maximum number of faulty validators. Tendermint requires n > 3f . A quorum is any set of at least n − f or, more commonly, 2f +1 validators. Because at most f of them can be faulty, the majority of every quorum is always correct. Note that Tendermint supports weighted voting, where validators hold distinct voting powers and thresholds are expressed over cumulative voting power rather than validator counts [34]. The protocol presented in this paper generalises directly to weighted voting: replace n with total voting power N , f with cumulative faulty voting power F , and validator counts with aggregated voting power in all threshold conditions. However, for simplicity in presentation, we assume equal voting power. The block assembler for the first round of each height is selected by a round-robin schedule over the validator set. A round of consensus consists of three steps: propose, prevote, and precommit, each associated with a message type, mirroring PBFT’s three-phase communication pattern [22]: 1. propose step: at the start of a round, the designated block assembler broadcasts a PROPOSAL message containing a proposed value v to all validators. 2. prevote step: upon receiving a PROPOSAL, and provided that the proposed value v can be accepted, a validator broadcasts a PREVOTE for v; otherwise, it broadcasts a PREVOTE for nil. Acceptance is determined by protocol rules and by an application-specific predicate valid(v). 3. precommit step: if a validator receives a valid PROPOSAL for v and PREVOTE for v from a quorum of validators, it broadcasts a PRECOMMIT for v; otherwise, if no value receives a quorum of prevotes, the validator broadcasts a PRECOMMIT for nil. Upon receiving a valid PROPOSAL for v and PRECOMMIT messages for v from a quorum of validators, the validator decides v at that height. Otherwise, if no value is precommitted by a quorum, the validator waits for a timeout and moves to the next round. We refer to a set of identical PRECOMMITs—for the same height, round, and value—from a quorum of validators as a commit certificate, as it evinces that a round of consensus has reached a decision. 3.2.2

Vote Extensions

Vote extensions are a feature of Tendermint-style consensus2 that allows the application layer to attach arbitrary data to consensus messages broadcast by validators. Concretely, before casting a PRECOMMIT for a non-nil value, a validator invokes the ExtendVote primitive. Through this interface, the application may return an arbitrary value which is attached by the validator to its PRECOMMIT message. The extension, covered by the validator’s signature, is cryptographically 1 In Tendermint, the distinguished validator leading a round is called the proposer. We do not follow the original nomenclature to avoid confusion with the proposer role, key for the introduced multi-proposer protocol. 2 Introduced by CometBFT [24], the implementation of Tendermint’s consensus algorithm used in Cosmos blockchains [14]. More details regarding its release in: https://informal.systems/blog/abci-v2-unlocks-this.

5

Application Layer Finalized(h, {p1 , p2 , ...})

validPayload(pi )

AMP: Arc Multi-Proposer Protocol

deliver(pi )

Dissemination Layer

GetValue(h)

ReceivedProposal(h, ids) ExtendVote(h, ids), Decided(h, ids) VerifyVoteExtension(ext)

Agreement Layer (Tendermint/Malachite)

Figure 1: Architecture of a validator node. The AMP logic sits between the application and the underlying dissemination and agreement layers. Each pi represents a payload broadcast by a proposer and received by the validator. GetValue(h) returns a commit certificate to propose in the agreement layer; validators extract the decided set of payload ids from it. The Decided primitive also returns a commit certificate, represented as a set of payload ids for brevity. bound to and disseminated together with the PRECOMMIT. Conversely, when a validator receives a PRECOMMIT for a non-nil value from another validator, it invokes the VerifyVoteExtension primitive. Through this interface, the application validates the extension attached to the PRECOMMIT. If this validation fails, the validator disregards the PRECOMMIT message. A validator decides at a consensus height once it obtains a commit certificate, containing PRECOMMIT messages from at least 2f +1 validators. Each of these messages carries a (possibly empty) vote extension produced by the application layer of its sender. This means that vote extensions from at least f +1 correct validators are included in any commit certificate3 . In AMP, validators attest to received payloads by including their concise identifiers in vote extensions. Thus, commit certificates represent a tamper-evident record of the payloads attested to by a quorum of validators. This limits the block assembler’s power of selecting which payloads to include in its proposal, which is at the core of AMP’s bounded transaction inclusion guarantee.

4

Protocol

This section presents AMP. We first provide an overview of the protocol (Section 4.1), then describe the main steps of its operation (Section 4.2), provide some relevant implementation details (Section 4.3), and discuss the concern of malicious proposers (Section 4.4).

4.1

Overview

AMP is a multi-proposer construction on top of Tendermint [15], a single-proposer BFT consensus algorithm where validators take turns as block assemblers4 . In traditional blockchain protocols, the role of block assembler consists of (i) collecting user transactions (e.g., in the mempool), (ii) assembling them into a block, and (iii) proposing the block for consensus. In single-proposer protocols, step (iii) commonly combines both the dissemination of and the agreement on the proposed block. AMP splits those responsibilities across multiple nodes in the same height. A node playing the proposer role assembles user transactions into a payload and sends it to all validators. Each 3 4

A quorum has at least 2f +1 validators and at most f are faulty, so at least f +1 are correct. The construction also fits algorithms where the role of the block assembler is fixed, such as PBFT [22].

6

payload is uniquely identified by a concise identifier: its id. A node that acts as a validator receives and stores payloads from proposers. Validators attest to payloads by exchanging their ids with each other via vote extensions. The block assembler, itself a validator, proposes a set of payload ids attested by more than f validators. Recall that we say that a payload is certified when attested by all correct validators, i.e., by at least 2f +1 validators. This happens because the block assembler can disregard or censor vote extensions from up to f validators; if a payload id appears in more than 2f attestations, then the block assembler has no choice but to include it in its proposal, as discussed in Section 3.2.2. When validators reach a decision for a height, AMP maps the decided payload ids to the set of corresponding full payloads, which are finalized and subsequently delivered to the application. Under normal operation, validators will have already received the payloads corresponding to the set of decided ids. If a validator misses some payload, it will wait until they are obtained, requesting their retransmission if necessary. A payload id can only be decided in a height if it was attested by more than f validators. This means at least one correct validator exists that is able to retransmit the full payload.

4.2

Operation

AMP operates as a layer mediating between the application, on one hand, and the dissemination and agreement layers, on the other hand. Figure 1 illustrates the design, and Algorithm 1 shows pseudo-code that a validator runs. Table 1 summarizes auxiliary methods. A summary of the main steps of the protocol operation, covering both proposers and validators, follows below: 1. Collection. Every proposer collects user transactions and assembles them into payloads. The assembling logic (e.g., how large payloads are, how long to wait to fill a payload) is application specific and therefore not represented in the pseudo-code. 2. Dissemination. A proposer broadcasts the assembled payloads to all validators, using the dissemination layer’s broadcast primitive. Figure 1 does not explicitly call out this primitive, as it does not run at validators. 3. Payload Validation. When a validator receives a payload from the dissemination layer, via the deliver primitive (line 4), it forwards the payload to the application for a validity check. A validator stores valid payloads and drops invalid ones. 4. Vote Extension. When Tendermint requests a vote extension (line 11), as part of the precommit step, each validator returns its set of pending payload ids. A payload id is pending when it is valid but was not yet ordered by the agreement layer. Also, a payload whose id is being accepted by the validator when casting the PRECOMMIT message should not be attested again—otherwise, it can be decided in this and the next height, being finalized in two heights. Validators verify each other’s vote extensions (line 13) by checking that all included payload ids are well-formed, using the auxiliary validExtension() method. 5. Tendermint Proposal. The block assembler proposes for height h (line 15) the commit certificate it collected for height h−1. The certificate carries vote extensions, from which validators extract the decided payload ids. The block assembler proposes the full commit certificate because this enables other validators to validate the proposal construction. 6. Proposal Validation. When a validator receives the Tendermint-level proposal from the block assembler, it asks AMP to validate it (line 9). This proposal is a commit certificate, and the validator check whether it is valid via the validCommit() auxiliary method. 7. Decision. When the agreement layer reaches a decision (line 17), a validator learns: (i) the decided value v, itself a commit certificate, and (ii) the commit certificate for height h, 7

Algorithm 1 AMP pseudo-code at a validator running Tendermint consensus protocol. 1 upon initialization do 2 ordered, payloads ← nil ▷ Maps ids → values 3 next ← 1, attestations ← ∅, pending ← ∅ // A validator receives payloads from proposers, via the dissemination layer 4 upon deliver⟨payload⟩ from some proposer do 5 id ← id(payload) S 6 if id ∈ / ordered ∧ payloads[id] = ∅ ∧ validPayload(payload) then 7 pending ← pending ∪ {id} 8 payloads[id] ← payload // The agreement (Tendermint) layer triggers these callbacks 9 upon ReceivedProposal⟨PROPOSAL(h, r, v, vr)⟩ do 10 return validCommit(v) 11 upon ExtendVote⟨PRECOMMIT(h, r, v)⟩ do 12

return pending \ soundIDs(v)

▷ Return a set of payload ids ▷ Skip ids already included in v

13 upon VerifyVoteExtension⟨PRECOMMIT(h, r, v), ext⟩ do 14

return validExtension(ext)

15 upon GetValue⟨h⟩ do 16

return attestations

▷ Propose in height h the commit certificate of height h − 1

17 upon Decided⟨h, v, commit⟩ do 18 19 20

attestations ← commit ordered[h] ← soundIDs(v) pending ← pending \ ordered[h]

// The multi-proposer layer delivers totally-ordered payloads to the application layer 21 when ordered[next] ̸= ∅ ∧ (∀id ∈ ordered[next] : payloads[id] ̸= ∅) do 22 decidedPayloads ← {payloads[id] | id ∈ ordered[next]} 23 trigger Finalized⟨next, sort(decidedPayloads)⟩ 24 next ← next + 1 25 function soundIDs(commit) 26 27 28 29

for (validator, extension) ∈ commit do for id ∈ extension do count[id] ← count[id] + 1 return {id | count[id] > f }

evincing that v was decided. From (i), soundIDs(v) extracts the payload ids attested by more than f validators in v’s vote extensions; those payloads are finalized in height h. The commit certificate of height h (ii) is what the validator will use as the proposed value for the subsequent height h+1 (line 15), in the case it is assigned as the block assembler. 8. Finalization. Once a decision for a height is reached, a validator checks if all referenced payloads are available. If payloads are missing, the validator asks for their retransmission from the dissemination layer, and waits until they are received. Given the availability guarantees for ordered payloads, the missing payloads are eventually retrieved. Once all the required payloads are available (line 21), each validator derives from them the block to be finalized, via the sort() auxiliary method. This deterministically derives, from 8

Name

Description

id(payload) validPayload(payload) validCommit(commit) validExtension(extension)

The concise unique identifier for a given payload. Application-specific validation of a payload. Validates a commit certificate and its vote extensions. Validates a vote extension, a signed set of payload ids.

soundIDs(commit)

The set of payload ids attested in the commit certificate by more than f validators.

sort(payloads)

Deterministically orders a given set of payload contents.

Table 1: Auxiliary methods adopted by AMP (Algorithm 1) and their meaning. a set of payloads, a block of transactions ordered by priority fees.

4.3

Implementation Details

This section details the auxiliary methods (Table 1) and the operation of core steps of AMP. Payload Identifiers. AMP separates payload dissemination from agreement, and the agreement stage (consensus) operates on concise payload ids. As Table 1 shows, we assume an id() method that produces a unique identifier for a payload. A minimal implementation of this can just return a hash of the full payload, using a modern collision-resistant hash function. A more elaborated implementation for id() may include the address of the proposer that has broadcast the payload, plus a sequence number. In combination with a compatible implementation of validPayload(), this would enable ensuring a FIFO order for disseminated payloads. The compatible validPayload() method would only accept a payload from a sender with a given sequence number after having received and validated all payloads from the same sender with smaller sequence numbers. This would render the validPayload() call of line 6 blocking. The validExtension() implementation would also need to be updated accordingly. Commit Certificates. The Tendermint consensus algorithm does not adopt the concept of certificate, although it is present in several implementations: a certificate is a set of votes that share some characteristics. A commit certificate is a set of identical PRECOMMITs that evinces a decision, including the attached vote extensions, produced by their senders. The validCommit() method receives a commit certificate and the height h it belongs to, and checks its validity. A valid commit contains identical PRECOMMITs that only differ by their sender, signatures, and vote extensions. A commit can have a single message per validator. All signatures are verified, the number of distinct validators is checked, and all vote extensions should be valid, according to the validExtension() method. An important corner case for the validCommit() method are the first heights: the genesis height, typically 0, and the subsequent height, typically 1. The genesis height is not decided via consensus, but pre-agreed: there is no commit certificate for it. As a result, there are no vote extensions for the subsequent height, that is not supposed to order any payload. Proposal Construction. As Algorithm 1, line 15 shows, a block assembler proposes as value for height h the commit certificate it has collected at height h−1. A commit certificate is made of PRECOMMITs, and associated vote extensions, from at least 2f +1 validators. A validator can wait a short period before starting the next height, to possibly accumulate PRECOMMITs and vote extensions from more than 2f +1 validators. On the one hand, this is positive, as it increases the payloads count that can be decided upon in that height. On the other hand, this creates an

9

opportunity for a malicious block assembler to manipulate the proposal by selectively including or excluding vote extensions and, consequently, payloads. AMP limits the block assembler’s power of selecting which payloads are proposed. A valid proposal must include vote extensions from at least 2f +1 validators. In addition, as detailed in Section 3.2.2, vote extensions are tamper-evident: any alteration would invalidate their signatures. So, if a payload id is attested by all correct validators (i.e., by at least n−f validators), then that payload id must be present in any valid proposal, being attested by more than f validators. This happens because at most f validators can be excluded from the at least 2f validators attesting the payload id. This is the mechanism that enforces the bounded inclusion property, formally proved in Appendix A. Transaction Ordering. Once a set of payload ids is decided for a height and the full payloads are available (line 21), all correct validators must apply the same logic to produce the same finalized block. This means transforming a set of payloads, each one assembling multiple user transactions, into a single totally-ordered sequence of transactions. AMP delegates this logic to the sort() method (line 23), which is subject to a single requirement: it must be deterministic. The specific ordering policy, however, is defined at the application level. We recommend sorting transactions across all decided payloads in descending order of priority fee per unit of computation, breaking ties by payload ids and transaction hashes. This ordering is deterministic, manipulation-resistant, and market-based: users who value earlier execution pay a higher fee. Section 5.1 analyzes the MEV implications of this choice. Payload Availability. It is possible for validators to decide on payload ids that they do not locally possess. After determining the set of ids to be ordered at a specific height (line 19), validators consult their local payloads store to verify availability. For any missing id, the validator requests transmission of it from the other validators. Retrieval is guaranteed because any id included in the ordered set must be supported by more than f validators (line 29). This threshold ensures that at least one correct validator has received, validated, and stored the payload, making it available to the rest of the network. While this retransmission logic is omitted from the pseudocode for simplicity, it would be triggered following the Decided primitive (line 17) to satisfy the finalization condition for payloads required at line 21.

4.4

Malicious Proposers

While AMP is described under the assumption of honest proposers, it is valuable to consider what happens if some proposers are Byzantine. The first and more evident consequence is the production and dissemination of payloads at a very high rate to exhaust the resources of validators. In this case, it is up to the application layer, via the validPayload() primitive, to identify and drop payloads that do not contain unique and valid transactions. Practical setups of AMP should enable the application layer to block proposers identified as malicious. A second modality of attack consists of the production of valid payloads that are selectively disseminated so they only reach a subset of validators. Those payloads are thus stored and attested to by correct validators, but they do not reach the availability threshold of more than f attesting validators (line 29), required to finalize them. As a result, their ids remain in the pending set of correct validators, which may increase indefinitely in size, leading also to an equivalent increasing in size of the exchanged vote extensions, that however does not result in more payloads being ordered. Although this form of attack cannot be prevented, its consequences can be attenuated. At AMP’s level, validators can have policies restricting the size of their pending sets. For instance, a payload received during height h is removed from the pending set and marked as aged, if not ordered by height h+k, where k is a protocol constant. At the dissemination layer, correct validators can exchange ids of payloads that do not receive enough

10

attestations, rebroadcasting them on-demand. Another approach is to rely on a strong form of broadcast, with increased communication costs, such as reliable broadcast [18]. A third form of attack is a variation of the second one where valid payloads are selectively disseminated to an important portion but not to all correct validators. Those payloads therefore become certified and are ordered, but several validators will request their retransmission, thus increasing network usage. In the most extreme version of this attack, a payload is only sent to one correct validator and attested by all Byzantine validators, thus reaching the minimal availability threshold. The Byzantine validators can then ignore retransmission requests for that payload, that needs to be disseminated (again) by the single correct validator that has received it. It is very hard to distinguish this attack from a legitimate scenario of unreliable communication and, as previously discussed, a dissemination layer with stronger guarantees should minimize the impact of such attack—the cost of which is higher message complexity in the common case. Finally, when considering the operation of proposers at application level—assembling user transactions into payloads—a number of additional attacks should be considered. Section 5.3 overviews some forms of proposers attacks at transaction assembling level.

5

Discussion

We now discuss briefly how AMP deals with harmful MEV activities (Section 5.1), tradeoffs this design makes (Section 5.2), and open questions (Section 5.3).

5.1

MEV Implications

As we discussed, in single-proposer BFT protocols, the block assembler holds unilateral power over transaction inclusion and ordering, creating opportunities for Maximal Extractable Value (MEV) strategies such as front-running, sandwich attacks, and transaction censorship. AMP constrains this power in two ways: (i) bounded inclusion prevents payload exclusion (and by extension, transaction censorship), and (ii) the function sort deterministically orders transactions and removes the block assembler’s discretion to order transactions across the set of decided payloads within any height. In this section, we assume that sort orders transactions in descending order of priority fee per unit of computation. AMP provides the basis for deterring harmful MEV activities while allowing the efficient capturing of benign MEV gains at the protocol and application layers. Robinson et al. [40] formalize four requirements for competitive priority ordering: (i) priority ordering, (ii) censorship resistance, (iii) pre-transaction privacy, and (iv) no proposer last-look. When all four hold, priority-fee competition channels MEV into fees rather than enabling extraction. AMP natively satisfies three of these four conditions (i), (ii) and (iv), while (iii) can be met with additional configurations. Priority ordering is achieved in sort. Bounded inclusion provides censorship resistance for payloads. A payload attested by all correct validators must appear in the next block, so the block assembler cannot selectively exclude competing transactions. The block assembler submits a certificate assembled from the previous height’s vote extensions rather than constructing proposals from observed transactions, which prevents last-look advantages. We provide a full proof of correctness for this bounded inclusion property in Appendix A. The remaining condition, pre-transaction privacy, can be composed independently and is discussed in Section 5.3. Two potential residual MEV vectors are also mitigated. First, a Byzantine validator can strategically compose vote extensions by omitting payload identifiers. This delays finalization by at most one additional height, after which all correct validators will have re-attested and bounded inclusion takes effect. Second, a block assembler collecting additional vote extensions can choose which ones to include in the certificate, potentially affecting certification of “marginal” payloads not yet in all correct validators’ pending sets; nonetheless, once payloads are disseminated at all

11

correct validators, the bounded inclusion property takes effect and this flexibility disappears. With front-running and sandwich attacks mitigated, the remaining forms of MEV are economically benign. Backrunning arbitrage, liquidation competition, and time-sensitive oracle updates generate priority fee revenue for the protocol: searchers compete by bidding up fees, transferring opportunity value to the validator set. Priority-fee ordering also enables MEV taxes [40]. These are application-level fees set as a function of the transaction’s priority fee, allowing applications to recapture a fraction of competitive MEV. Empirical evidence from existing chains supports this model. On Solana, where the mempool is not publicly visible, approximately 75% of transactions carry priority fees, accounting for 39% of total fee revenue [41]. On Ethereum, where over 40% of retail order flow routes through private RPCs [31], priority fees, not MEV extraction, drive the majority of validator compensation.

5.2

Tradeoffs

AMP gains a form of censorship resistance and fairness by distributing the collection role across multiple proposers. This introduces some tradeoffs relative to vanilla Tendermint and other multi-proposer designs. We discuss here briefly some of these aspects, and expand on related work later in Section 6. AMP achieves bounded inclusion with two additional communication rounds over standard Tendermint—matching the tight lower bound established by Abraham et al. [1] for any protocol providing censorship resistance guarantee. Standard Tendermint finalizes a block in three communication steps (propose, prevote, precommit). AMP adds the payload dissemination and vote-extension attestation steps on top of these, but removes the need for mempool gossip. Garimidi et al. [33] (MCP) also target next-slot inclusion together with a formal hiding property—guaranteeing that the adversary learns nothing about honest nodes’ transactions before the consensus decision is final. As a consequence of bundling censorship resistance and hiding into a single construction, MCP’s concrete parameterization targets a system-wide resilience of f < n/5. This is required to satisfy all properties simultaneously (safety, liveness, selective-censorship resistance, and hiding). AMP maintains the standard f < n/3 threshold by treating hiding as an orthogonal concern: bounded inclusion and no-last-look are provided natively, while pre-transaction privacy can be layered independently—either operationally, through a permissioned and auditable proposer set, or cryptographically, via threshold encryption (Section 5.3). The tradeoff is that AMP does not natively provide hiding, whereas MCP does, at the cost of operating under a stronger assumption on the fraction of honest nodes. Unlike single-proposer protocols, and similarly to other multi-proposer algorithms [47, 35], AMP can be affected by the “free data availability” problem [17]. Every correct validator must store all payloads it observes. If the same transaction is duplicated across payloads, this multiplies per-height storage proportional to the number of copies. Only the first instance of the transaction will succeed, but the others are still included in the block. We consider this to be an acceptable tradeoff in the first version of AMP.

5.3

Open Questions

Three questions are immediately relevant in our short-term investigations with AMP. Pre-transaction privacy. Pre-transaction privacy can be achieved through at least two complementary approaches. First, a permissioned proposer set operating over a private network provides operational privacy: transactions are never exposed to a public mempool, and proposers are auditable entities subject to off-chain accountability. This is the model already deployed in single-proposer architectures such as currently implemented in Arc. Second, threshold encryption—where transaction content is encrypted under a key requiring multiple validators to decrypt after certification—provides cryptographic privacy even against proposers themselves. 12

This idea has been explored extensively in blockchains [23, 10, 2, 9, 11, 12, 13, 50] and fits AMP’s architecture, since each payload already requires attestations from multiple validators before finalization. The two approaches differ in trust assumptions: the first relies on proposer honesty and auditability; the second removes that assumption at the cost of additional cryptographic machinery. Integrating either approach into the multi-proposer setting is left for future work. Experimental evaluation. We anticipate that AMP can lead to increased throughput over standard Tendermint. An early prototype shows a promising increase of up to 10x in the amount of bytes decided per second, with a validator set size of 50 nodes, each acting as a proposer. These are very preliminary results, however, and the implementation is still in flux. We plan to continue working towards a more mature implementation, an in-depth understanding of the bottlenecks, and eventually a comprehensive performance evaluation of AMP, which are very important for validating the protocol’s practicality. Dynamic validator sets. In the current protocol formulation, we assume a fixed validator set. Supporting dynamic membership with changing voting weights can be accomplished by introducing epochs that lock the validator set for a fixed number of heights. The principal subtlety is payload availability across epoch boundaries: if a correct validator v is the sole guarantor of some payload p and v leaves the validator set, p may become unavailable. Ensuring that at least one correct validator in the new set holds each pending payload may require a handoff protocol at epoch transitions, which is left for future work.

6

Related Work

There are several lines of research representing important prior art that are related to AMP. A well-explored vein of multi-proposer protocols are DAG-based consensus algorithms. They allow all validators to propose simultaneously and create a directed acyclic graph on top of the blocks, since each block references multiple prior blocks. DAG-based protocols, which are often focused on achieving high throughput, include Tusk [27], Bullshark [43], Mysticeti [8], Shoal [42] and Shoal++ [6]. While allowing for parallel proposals, DAG-based protocols fail to strip validators of discretion over the final execution order. In contrast, AMP mitigates this through the bounded inclusion guarantee paired with deterministic ordering algorithm. Multi-leader protocols such as Mir-BFT [44] and ISS [45] enable concurrent ordering by partitioning transactions across leaders running parallel consensus instances. Autobahn [35] further scales this model by pipelining consensus across multiple “lanes”, where each lane is associated to a leader. AMP differs from these complex approaches as it does not partition transactions or require parallel consensus instances. Instead, it is designed as a modular protocol layer that composes on top of a single Tendermint instance, and avoids re-implementing a fullfledge consensus protocol from scratch, as that is a significant effort. Research in censorship resistance focuses on the eventual inclusion of a valid transaction despite adversarial attempts to exclude it. Prefix Consensus [48] guarantees inclusion in a leaderless architecture [5] within f +1 consensus heights, where f is the number of Byzantine nodes. Tendermint also achieves the same guarantee with its rotating block assembler. Since each height has a new block assembler, a transaction which Byzantine validators attempt to censor will be included within f +1 heights, as at least one block assembler will be honest during that interval. AMP’s inclusion guarantee is the next height. The FOCIL protocol [47] also provides assurances for some transactions to be included in the next block, but come at the cost of creating committees of validators who determine which transactions will be included. MCP [33] aims to achieve next block transaction inclusion and hiding where adversaries are not able to see the contents of blocks. However, this is only certain

13

if the fault tolerance of the protocol is reduced to f < n/5. Otherwise, achieving censorshipresistance, hiding, and liveness becomes probabilistic. Moving from a single proposer to multiple concurrent proposers changes the structure of the fee market and the MEV landscape. Stouka et al. [46] design a transaction fee mechanism for FOCIL that achieves bribery-resistant censorship resistance while preserving EIP-1559 incentive compatibility, showing that economically sound multi-proposer fee mechanisms are feasible. Landers and Marsh [37] identify MEV channels unique to concurrent-proposer blockchains— duplicate steals, proposer-to-proposer auctions, and timing races driven by proof-of-availability latency—and show that deterministic priority scheduling combined with duplicate-aware payouts can neutralize same-tick extraction. As described earlier (Section 5.1), Robinson et al. [40] identify four conditions for achieving competitive priority ordering, and AMP can satisfy all four when combined with pre-transaction privacy. Proposer-Builder Separation (PBS) [16, 30] addresses the single proposer monopoly power by splitting block construction into two market roles: builders assemble transaction-optimized blocks, and the consensus proposer selects the highest-bidding block via an auction. The separation prevents the proposer from needing to run sophisticated MEV strategies itself, but it does not curtail the proposer’s power to censor transactions or the builder’s power to order them extractively. It relocates that power to builders who compete on MEV extraction efficiency. Trusted relays (mev-boost [30]) or proposed enshrined auction mechanisms (ePBS [39]) mediate the proposer/builder interaction, and may introduce additional trust assumptions or protocol complexity. AMP takes a structurally different approach. Our proposer role can be seen as a mix between builders and relays in PBS, but two key differences are: (i) by distributing the collection role, any node can act as a proposer, and (ii) bounded inclusion ensures that certified payloads must appear in the next block.

7

Conclusions

We presented AMP, a multi-proposer protocol layer that composes on top of the Tendermint consensus algorithm. The protocol distributes transaction collection across dedicated proposers, separates dissemination from agreement, and uses vote extensions to enforce bounded inclusion: transactions included in any payload attested by all correct validators must appear in the next block. The bounded inclusion guarantee, combined with deterministic transaction ordering, constrains both the block assembler’s power over inclusion and over ordering. The requirements for this protocol are grounded in research we have been doing on the Arc L1 blockchain. Arc aims to be a bridge between traditional and decentralized finance. In this context, it is useful to allow various parties—teams or institutions running flows or trades on Arc—to participate directly in block construction, without necessarily assuming they need to run a validator. Adding validators to the network can affect performance or security. Validators in AMP specialize in securing the network, while proposers engage in assembling payloads that compose into blocks. The key mechanism behind AMP—using vote extensions at height h to certify payloads for inclusion at height h+1—is not specific to Tendermint consensus algorithm. Any BFT consensus protocol that can support vote extensions likely admits the same construction. AMP was designed for the Arc blockchain, which is built on the Malachite consensus engine, but we believe the approach applies wherever a single-proposer bottleneck limits transaction throughput or fairness, or the architectural decoupling of block assemblers from proposers can serve to scale and specialize the two roles independently.

14

References [1] Ittai Abraham, Yuval Efron, and Ling Ren. The latency cost of censorship resistance. Cryptology ePrint Archive, Paper 2025/2136, 2025. [2] Amit Agarwal, Rex Fernando, and Benny Pinkas. Efficiently-thresholdizable batched identity based encryption, with applications. In Advances in Cryptology – CRYPTO 2025, volume 16002 of Lecture Notes in Computer Science, pages 69–100. Springer, 2025. [3] Yackolley Amoussou-Guenou, Antonella Del Pozzo, Maria Potop-Butucaru, and Sara TucciPiergiovanni. Correctness of Tendermint-Core Blockchains. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018), volume 125, pages 16:1–16:16, 2019. [4] Yackolley Amoussou-Guenou, Antonella Del Pozzo, Maria Potop-Butucaru, and Sara TucciPiergiovanni. Dissecting Tendermint. In Networked Systems (NETYS 2019), volume 11704 of Lecture Notes in Computer Science, pages 166–182, Cham, Switzerland, 2019. Springer. [5] Karolos Antoniadis, Antoine Desjardins, Vincent Gramoli, Rachid Guerraoui, and Igor Zablotchi. Leaderless consensus. In 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS), pages 392–402. IEEE Computer Society, 2021. [6] Balaji Arun, Zekun Li, Florian Suri-Payer, Sourav Das, and Alexander Spiegelman. Shoal++: High throughput DAG BFT can be fast! arXiv preprint arXiv:2405.20488, 2024. [7] Raphael Auer, Jon Frost, and Jose Maria Vidal Pastor. Miners as Intermediaries: Extractable Value and Market Manipulation in Crypto and DeFi. BIS Bulletin 58, Bank for International Settlements, June 2022. [8] Kushal Babel, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris KokorisKogias, Arun Koshy, Alberto Sonnino, and Mingwei Tian. Mysticeti: Reaching the limits of latency with uncertified DAGs. arXiv preprint arXiv:2310.14821, 2023. [9] Joseph Bebel and Dev Ojha. Ferveo: Threshold decryption for mempool privacy in BFT networks. Cryptology ePrint Archive, Paper 2022/898, 2022. [10] Dan Boneh, Benedikt Bünz, Kartik Nayak, Lior Rotem, and Victor Shoup. Contextdependent threshold decryption and its applications. Cryptology ePrint Archive, Paper 2025/279, 2025. [11] Dan Boneh, Evan Laufer, and Ertem Nusret Tas. Batch decryption without epochs and its application to encrypted mempools. Cryptology ePrint Archive, Paper 2025/1254, 2025. [12] Jan Bormet, Arka Rai Choudhuri, Sebastian Faust, Sanjam Garg, Hussien Othman, GuruVamsi Policharla, Ziyan Qu, and Mingyuan Wang. BEAST-MEV: Batched threshold encryption with silent setup for MEV prevention. Cryptology ePrint Archive, Paper 2025/1419, 2025. [13] Jan Bormet, Sebastian Faust, Hussien Othman, and Ziyan Qu. BEAT-MEV: Epochless approach to batched threshold encryption for MEV prevention. Cryptology ePrint Archive, Paper 2024/1533, 2024. [14] Ethan Buchman and Jae Kwon. Cosmos Whitepaper: A Network of Distributed Ledgers. Whitepaper, Tendermint, Inc., 2016. Accessed: 2026-03-13, Available on: https://cosmos. network/resources/whitepaper. 15

[15] Ethan Buchman, Jae Kwon, and Zarko Milosevic. The latest gossip on BFT consensus. arXiv preprint arXiv:1807.04938, 2018. [16] Vitalik Buterin. Proposer/builder separation (PBS). Ethereum Research, https:// ethresear.ch/t/proposer-block-builder-separation-friendly-fee-market-designs/ 9725, 2021. Accessed: 2026-03-13. [17] Vitalik Buterin. State of research: increasing censorship resistance of transactions under proposer/builder separation (PBS). Ethereum Notes, January 2022. Accessed: 2026-03-13. [18] Christian Cachin, Rachid Guerraoui, and Luis Rodrigues. Introduction to Reliable and Secure Distributed Programming. Springer, 2011. [19] Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. On the (limited) power of non-equivocation. In Proceedings of the 18th ACM Symposium on Principles of Distributed Computing (PODC), pages 53–62, 2001. [20] Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and efficient asynchronous broadcast protocols. In Advances in Cryptology – CRYPTO 2001, pages 524–541. Springer Berlin Heidelberg, August 2001. [21] Daniel Cason, Enrique Fynn, Nenad Milosevic, Zarko Milosevic, Ethan Buchman, and Fernando Pedone. The design, architecture and performance of the Tendermint Blockchain Network. In 40th IEEE International Symposium on Reliable Distributed Systems (SRDS 2021), pages 23–33. IEEE, 2021. [22] Miguel Castro and Barbara Liskov. Practical Byzantine fault tolerance. In Proceedings of the 3rd USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 173–186, 1999. [23] Arka Rai Choudhuri, Sanjam Garg, Julien Piet, and Guru-Vamsi Policharla. Mempool privacy via batched threshold encryption: Attacks and defenses. In Proceedings of the 33rd USENIX Security Symposium. USENIX Association, 2024. [24] CometBFT Contributors. CometBFT: A distributed, Byzantine fault-tolerant state machine replication engine. https://github.com/cometbft/cometbft. Accessed: 2026-0313. [25] CPMI-IOSCO. Application of the Principles for Financial Market Infrastructures to Stablecoin Arrangements. CPMI Papers 206, Bank for International Settlements, July 2022. [26] Philip Daian, Steven Goldfeder, Tyler Kell, Yunqi Li, Xueyuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels. Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability. In Proceedings of the 2020 IEEE Symposium on Security and Privacy (SP), pages 910–927. IEEE, 2020. [27] George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. Narwhal and Tusk: A DAG-based mempool and efficient BFT consensus. In Proceedings of the 17th European Conference on Computer Systems (EuroSys), pages 34–50, 2022. [28] Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):288–323, April 1988. [29] Financial Stability Board. High-level Recommendations for the Regulation, Supervision and Oversight of Crypto-Asset Activities and Markets. Technical report, Financial Stability Board, July 2023. Accessed: 2026-03-13.

16

[30] Flashbots. mev-boost: MEV-boost relay for ethereum. https://boost.flashbots.net/, 2022. Accessed: 2026-03-13. [31] Flashbots. Illuminating Ethereum’s order flow landscape. https://writings.flashbots. net/illuminate-the-order-flow, November 2023. Accessed: 2026-03-13. [32] Elijah Fox, Mallesh Pai, and Max Resnick. Censorship resistance in on-chain auctions. arXiv preprint arXiv:2301.13321, 2023. [33] Pranav Garimidi, Joachim Neu, and Max Resnick. Multiple concurrent proposers: Why and how. arXiv preprint arXiv:2509.23984, 2025. [34] David K. Gifford. Weighted voting for replicated data. In Proceedings of the 7th ACM Symposium on Operating Systems Principles (SOSP ’79), pages 150–162, New York, NY, USA, December 1979. Association for Computing Machinery. [35] Neil Giridharan, Florian Suri-Payer, Ittai Abraham, Lorenzo Alvisi, and Natacha Crooks. Autobahn: Seamless high speed BFT. arXiv preprint arXiv:2401.10369, 2024. [36] Circle Internet Group. Malachite: Flexible BFT consensus engine in Rust. https:// github.com/circlefin/malachite, 2026. Accessed: 2026-03-13. [37] Steven Landers and Benjamin Marsh. MEV in multiple concurrent proposer blockchains. arXiv preprint arXiv:2511.13080, 2025. [38] Gordon Y. Liao, Rachel Mayer, Adrian Soghoian, Sanket Jain, and Erik Tierney. Arc: An Open Layer-1 Blockchain Purpose-Built for Stablecoin Finance. Litepaper, Circle Internet Group, 2025. Accessed: 2026-03-13, Avaliable on: https://www.arc.network/litepaper. [39] Mike Neuder and Justin Drake. Enshrined proposer-builder separation (ePBS). Ethereum Research, https://ethresear.ch/t/ why-enshrine-proposer-builder-separation-a-viable-path-to-epbs/15710, 2023. Accessed: 2026-03-13. [40] Dan Robinson, Dave White, and Georgios FKonstantopoulos. Priority is all you need. Paradigm Research, https://www.paradigm.xyz/2024/06/priority-is-all-you-need, June 2024. Accessed: 2026-03-13. [41] SolanaCompass. Solana fee statistics. https://solanacompass.com/statistics/fees, 2025. Accessed: 2026-03-13. [42] Alexander Spiegelman, Balaji Arun, Rati Gelashvili, and Zekun Li. Shoal: Improving DAG-BFT latency and robustness. arXiv preprint arXiv:2306.03058, 2023. [43] Alexander Spiegelman, Niv Giridharan, Alberto Sonnino, and Lefteris Kokoris-Kogias. Bullshark: DAG BFT protocols made practical. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 2705–2718, 2022. [44] Chrysoula Stathakopoulou, Tudor David, Matej Pavlovic, and Marko Vukolić. Mir-BFT: High-throughput robust BFT for decentralized networks. arXiv preprint arXiv:1906.05552, 2019. [45] Chrysoula Stathakopoulou, Matej Pavlovic, and Marko Vukolić. State machine replication scalability made simple. In Proceedings of the 17th European Conference on Computer Systems (EuroSys), pages 17–33, 2022.

17

[46] Aikaterini-Panagiota Stouka, Julian Ma, and Thomas Thiery. Multiple proposer transaction fee mechanism design: Robust incentives against censorship and bribery. arXiv preprint arXiv:2505.13751, 2025. [47] Thomas Thiery, Francesco D’Amato, et al. EIP-7805: Fork-choice enforced inclusion lists (FOCIL). Ethereum Improvement Proposal, https://eips.ethereum.org/EIPS/ eip-7805, November 2024. Accessed: 2026-03-13. [48] Zhuolun Xiang, Andrei Tonkikh, and Alexander Spiegelman. Prefix consensus for censorship resistant BFT. arXiv preprint arXiv:2602.02892, 2026. [49] Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan-Gueta, and Ittai Abraham. Hotstuff: Bft consensus with linearity and responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC), pages 347–356. ACM, 2019. [50] Haoqian Zhang, Louis-Henri Merino, Ziyan Qu, Mahsa Bastankhah, Vero EstradaGaliñanes, and Bryan Ford. F3B: A low-overhead blockchain architecture with pertransaction front-running protection. In Proceedings of the 5th Conference on Advances in Financial Technologies (AFT 2023), volume 282 of LIPIcs, pages 3:1–3:23, 2023.

A

Correctness

This section argues the correctness of AMP, more specifically proving the following properties: • Agreement: No two correct validators finalize different values. • Termination: All correct validators eventually finalize a value. • Validity: A finalized value is valid, i.e., it satisfies an application-specific valid() predicate. • Bounded Inclusion: Any payload p attested by all correct validators at height h is finalized at height h + 1. The first three properties define BFT consensus, as in Section 3.2, but replacing decision by finalization. This is because, while Tendermint consensus (the agreement layer) decides values, the interface provided by AMP (Algorithm 1) finalizes values. Theorem 1. AMP satisfies Agreement. Proof. Agreement is inherited from Tendermint consensus (agreement layer), which ensures that no two correct validators decided different values in the same height. The agreement layer returns the decision of height h via the Decided primitive (line 17). AMP stores in ordered[h] the result of the execution of the soundIDs() method over the decision value v. soundIDs() is deterministic because the set of validators is fixed. As a result, all correct validators, upon the decision of h, store the same value in their ordered[h]. The content of ordered[h] is then processed by the when condition in line 21, where next = h. This code retrieves payloads from their ids. The association of a payload to its id is assumed to be unique. As a result, every correct validator will produce the same set decidedP ayloads for h. Since the sort() method is, by definition, deterministic, the values finalized by every correct validator at h are the same. Finally, while phrased for a specific height h, this rationale can be extended for every finalized height. Theorem 2. AMP satisfies Termination.

18

Proof. Termination is inherited from Tendermint consensus (agreement layer), which ensures that every correct validator eventually decides a value in a height h. From Lemma 4, proved below, we know that once a value is decided for h, correct validators eventually satisfy the condition on line 21 for next = h and finalize a value for h. Theorem 3. AMP satisfies Validity. Proof. AMP uses validCommit() to check the validity of a proposed value v (line 10), where v is a commit certificate—since the proposed value is a commit certificate (line 15). So, if the agreement layer returns v as the decision of height h, via the Decided primitive (line 17), then v is necessarily a valid commit certificate. Section 4.3, in the “Commit Certificates” block, precisely defines the validity of a commit certificate. AMP, in its turn, needs its own definition of valid(). Let V be a value finalized by AMP. V is built, via the deterministic sort() method, from a set of payloads P (line 23). We thus define the valid() predicate for AMP as valid(V ) := ∀p ∈ P : validPayload(p). AMP validates the received payloads (line 6) using the validPayload() method. Only payloads considered valid by this method are stored and have their ids added to the pending set by any correct validator. As a result, a correct validator only attests to payloads that are valid. Since payloads attested by at least one correct validator can be finalized, finalized values have necessarily to be valid, according with above defined valid() predicate. Theorem 4. AMP satisfies Bounded Inclusion. Proof. Bounded Inclusion is the property of AMP that is not directly inherited from Tendermint consensus, but relies on some lemmas defined later. Lemma 3 states that if all correct validators attest payload p in height h, then p will be present in the certificate decided in h + 1. By Definition 3 (Present in Certificate), id(p) appears in vote extensions of more than f validators in the commit certificate, which is the condition checked by soundIDs() (line 29). Therefore, id(p) will be selected by the soundIDs() method over the decision of height h+1 and will be part of ordered[h+1]. Lemma 4 states that eventually all correct validators receive a payload that is present in a certificate. This means that if a correct validator included id(p) in its ordered[h+1] set, then every correct validator eventually retrieves the full payload p. This is valid not only for p but for every payload with id in ordered[h+1]. As a consequence, the when condition on line 21 is eventually satisfied for next = h+1 and p is finalized in height h+1, as established by the property. In the following, we define some important terms and formalize the required lemmas. Definition 1 (Commit certificate). A commit certificate for height h is a collection of valid, unique PRECOMMIT messages (along with their vote extensions) evincing the same decision from at least 2f +1 validators. Definition 2 (Attest). A validator attests to a payload p for height h if the validator includes id(p) in any of the vote extensions it produces in height h. Definition 3 (Present in Certificate). A payload p is present in a commit certificate c if id(p) is included in the vote extensions of more than f validators. Lemma 1. If a correct validator includes id(p) in its vote extension for round r of height h, then it includes id(p) in its vote extension for every subsequent round r′ > r of height h in which the proposed value does not already contain id(p).

19

Proof. A correct validator’s vote extension is produced by ExtendVote (line 11), which returns pending \ soundIDs(v), where v is the proposed value for that round. The pending set is modified in two places: identifiers are added upon delivery of valid payloads (line 8) and removed only when the agreement layer decides a height (line 17). No decision occurs between rounds of the same height, so pending can only grow during h. Therefore, if id(p) ∈ pending at round r, then id(p) ∈ pending at every round r′ > r of h. The only reason id(p) would not appear in the vote extension at r′ is if id(p) ∈ soundIDs(v ′ ), where v ′ is the value proposed in round r′ —meaning id(p) is already attested by more than f validators in v ′ . Lemma 2. If payload p is attested to by all correct validators at height h, then p will be present in any certificate c for h. Proof. Assume for the sake of contradiction that p is attested to by all correct validators at height h but not present in some certificate c′ for height h. By Lemma 1, every correct validator that attests to p in any round of h also attests to p in the deciding round—unless id(p) is already present in the proposed value, in which case p is present in c′ by definition. So assume id(p) is not in the proposed value of the deciding round. Then all correct validators include id(p) in the deciding round’s vote extensions, yet p is not present in c′ . This means that no more than f validators included id(p) in their vote extensions in c′ . However, any certificate must contain valid PRECOMMIT messages from at least 2f +1 validators. Since at most f validators are Byzantine, c′ must contain PRECOMMIT messages from more than f correct validators. Tendermint requires n > 3f , so n − 2f > f . p is attested to by all correct validators at h and more than f correct validators are in c′ . This contradicts our assumption. Corollary 1. If payload p is attested to by all correct validators at height h, then it is impossible to create a certificate c for h such that p is not present in c. Proof. Follows directly from Lemma 2. Lemma 3. If payload p is attested to by all correct validators at height h, then p is present in the certificate decided in h + 1. Proof. Let us consider the execution flow during h+1. From lines 15–18, we see that any correct block assembler submits a proposal consisting of a certificate for the previous height. Since p is attested to by all correct validators at h then, by Lemma 2, p is present in any certificate for h. Therefore, any correct block assembler submits a proposal in h + 1 where p is present. Byzantine block assemblers may attempt to propose a certificate in h + 1 where p is not present. However, by Corollary 1 this is impossible without invalidating the certificate. Invalid proposals are rejected by correct validators (line 10), causing the round to fail, and a new round to begin. By Tendermint’s termination property, a value is eventually decided. Lemma 4. Correct validators eventually receive all payloads present in a certificate. Proof. By definition, payloads present in a certificate are attested to by more than f validators. Since at most f validators are Byzantine, at least one correct validator attests to each payload. Thus, at least one correct validator has the payload’s identifier in its pending set (lines 11–12) which only happens if the validator has received the payload (lines 4–8). Correct validators can therefore ask other validators for the retransmission of any payloads present in the certificate that they do not know about. At least one correct validator has the missing payload, so this will succeed.

20

B

Analysis

We analyze the complexity of the AMP protocol under the following assumptions: • n is the total number of validators; • Every validator is also a proposer; • m is the maximum size of a payload; • Payload identifiers byte size is O(1); • Each proposer broadcasts one payload per consensus height (n payloads total); • Communication is via gossip, with latency O(log n), and message complexity O(n · log n). Latency. Proposers broadcast payloads to validators in O(log n) message delays. Validators then exchange the payload identifiers via vote extensions in O(log n) message delays. Consensus requires 3 communication steps, each one in O(log n) message delays. The total good-case latency is 5 communication rounds or 5 × O(log n) message delays. Message Complexity. The gossip of a message incurs message complexity O(n · log n). Proposers send n payloads per height, yielding a O(n2 ·log n) complexity for the dissemination layer. Next, each of the n validators broadcasts one vote extension, with the same O(n2 · log n) complexity. The three communication steps of consensus are O(n · log n) (PROPOSE) and O(n2 · log n) (PREVOTE and PRECOMMIT). The message complexity is therefore O(n2 · log n). Byte Complexity. Gossiping a payload of size m takes O(n · log n · m) bytes. As there are n payloads per height, the cost is O(n2 · log n · m). Vote extensions contain up to n identifiers, so PRECOMMIT messages are O(n) bytes, including vote extensions. All validators broadcast PRECOMMIT messages, which leads to a O(n3 · log n) byte complexity. The PROPOSE message carries a full commit certificate of O(n) such PRECOMMITs, totaling O(n2 ) bytes and O(n3 · log n) bytes when gossiped. PREVOTE messages are O(1) bytes each, contributing O(n2 · log n) bytes. Since the relation between the number of validators n and payload size m is unknown, the overall communication complexity is O((m + n) · n2 · log n).

21