When is Spring coming A Security Analysis of Avalanche Consensus Ignacio Amores-Sesar

2025-04-29 0 0 476.61KB 25 页 10玖币

侵权投诉

When is Spring coming? A Security Analysis of Avalanche

Consensus

Ignacio Amores-Sesar

University of Bern*

ignacio.amores@unibe.ch

Christian Cachin

University of Bern*

christian.cachin@unibe.ch

Enrico Tedeschi

The Artic University of Norway†

enrico.tedeschi@uit.no

10th October, 2022

Abstract

Avalanche is a blockchain consensus protocol with exceptionally low latency and high throughput.

This has swiftly established the corresponding token as a top-tier cryptocurrency. Avalanche achieves

such remarkable metrics by substituting proof of work with a random sampling mechanism. The

protocol also differs from Bitcoin, Ethereum, and many others by forming a directed acyclic graph

(DAG) instead of a chain. It does not totally order all transactions, establishes a partial order among

them, and accepts transactions in the DAG that satisfy speciﬁc properties. Such parallelism is widely

regarded as a technique that increases the efﬁciency of consensus.

Despite its success, Avalanche consensus lacks a complete abstract speciﬁcation and a match-

ing formal analysis. To address this drawback, this work provides ﬁrst a detailed formulation of

Avalanche through pseudocode. This includes features that are omitted from the original whitepaper

or are only vaguely explained in the documentation. Second, the paper gives an analysis of the formal

properties fulﬁlled by Avalanche in the sense of a generic broadcast protocol that only orders related

transactions. Last but not least, the analysis reveals a vulnerability that affects the liveness of the

protocol. A possible solution that addresses the problem is also proposed.

1 Introduction

The Avalanche blockchain with its fast and scalable consensus protocol is one of the most prominent al-

ternatives to ﬁrst-generation networks like Bitcoin and Ethereum that consume huge amounts of energy.

Its AVAX token is ranked 14th according to market capitalization in August 2022 [8]. Avalanche offers a

protocol with high throughput, low latency, excellent scalability, and a lightweight client. In contrast to

many well-established distributed ledgers, Avalanche is not backed by proof of work. Instead, Avalanche

bases its security on a deliberately metastable mechanism that operates by repeatedly sampling the net-

work, guiding the honest parties to a common output. This allows Avalanche to reach a peak throughput

of up to 20’000 transactions per second with a latency of less than half a second [28].

This novel mechanism imposes stricter security constraints on Avalanche compared to other net-

works. Traditional Byzantine fault-tolerant consensus tolerates up to a third of the parties to be cor-

rupted [23] and proof-of-work protocols make similar assumptions in terms of mining power [12, 11].

Avalanche, however, can tolerate only up to O(√n)malicious parties. Furthermore, the transactions in

the “exchange chain” of Avalanche (see below) are not totally ordered, in contrast to most other cryp-

tocurrencies, which implement a form of atomic broadcast [5]. As the protocol is structured around a

*Institute of Computer Science, University of Bern, Neubr¨

uckstrasse 10, 3012 CH-Bern, Switzerland.

†Institute of Computer Science, The Artic University of Norway, Hansine Hansens vei 54, 6050 NO-Langnes, Norway.

arXiv:2210.03423v1 [cs.DC] 7 Oct 2022

directed acyclic graph (DAG) instead of a chain, it permits some parallelism. Thus, the parties may

output the same transactions in a different order, unless these transactions causally depend on each other.

Only the latter must be ordered in the same way.

The consensus protocol of a blockchain is of crucial importance for its security and for the stability

of the corresponding digital assets. Analyzing such protocols has become an important topic in current

research. Although Bitcoin appeared ﬁrst without formal arguments, its security has been widely under-

stood and analyzed meanwhile. The importance of proving the properties of blockchain protocols has

been recognized for a long time [7].

However, there are still protocols released today without the backing of formal security arguments.

The Avalanche whitepaper [28] introduces a family of consensus protocols and offers rigorous security

proofs for some of them. Yet the Avalanche protocol itself and the related Snowman protocol, which

power the platform, are not analyzed. Besides, several key features of this protocol are either omitted or

described only vaguely.

In this paper, we explain the Avalanche consensus protocol in detail. We describe it abstractly

through pseudocode and highlight features that may be overlooked in the whitepaper (Sections 3–4).

Furthermore, we use our insights to formally establish safety properties of Avalanche. Per contra, we

also identify a weakness that affects its liveness. In particular, Avalanche suffers from a vulnerability in

how it accepts transactions that allows an adversary to delay targeted transactions by several orders of

magnitude (Section 5), which may render the protocol useless in practice. The problem results from de-

pendencies that exist among the votes on different transactions issued by honest parties; the whitepaper

does not address them. The attack may be mounted by a single malicious party with some insight into

the network topology. Finally, we suggest a modiﬁcation to the Avalanche protocol that would prevent

our attacks from succeeding and reinstantiate liveness of the protocol (Section 6). This version, which

we call Glacier, restricts the sampling choices in order to break the dependencies, but also eliminates the

parallelism featured by Avalanche.

The vulnerability has been acknowledged by the Avalanche developers. The deployed version of the

protocol differes however from the protocol in the whitepaper in a crucial way. It implements another

measure that prevents the problem, as we explain as well (in Appendix B).

2 Related work

Despite Avalanche’s tremendous success, there is no independent research on its security. Recall that

Avalanche introduces the “snow family” of consensus protocols based on sampling [28, 3]: Slush,

Snowﬂake, and Snowball. Detailed proofs about liveness and safety for the snow-family of algorithms

are given. The Avalanche protocol for asset exchange, however, lacks such a meticulous analysis. The

dissertation of Yin [31] describes Avalanche as well, but does not analyze its security in more detail

either.

Recall that Nakamoto introduced Bitcoin [22] without any formal analysis. This has been corrected

by a long line of research, which established the conditions under which it is secure (e.g., by Garay,

Kiayias, and Leonardos [12, 13] and by Eyal and Sirer [11]).

The consensus mechanisms that stand behind the best-known cryptocurrencies are meanwhile prop-

erly understood. Some of them, like the proof-of-stake protocols of Algorand [14] and the Ouroboros

family that powers the Cardano blockchain [16, 9], did apply sound design principles by ﬁrst introducing

and analyzing the protocols and only later implementing them.

Many others, however, have still followed the heuristic approach: they released code ﬁrst and were

confronted with concerns about their security later. This includes Ripple [2, 1] and NEO [30], in which

several vulnerabilities have been found, or Solana, which halted multiple times in 2021–2022. Stellar

comes with a formal model [20], but it has also been criticized [17].

Protocols based on DAGs have potentially higher throughput than those based on chains. Notable

examples include PHANTOM and GHOSTDAG [26], the Tangle of IOTA (www.iota.org), Con-

ﬂux [19], and others [15]. However, they are also more complex to understand and susceptible to a wider

range of attacks than those that use a chain. Relevant examples of this kind are the IOTA protocol [21],

which has also failed repeatedly in practice [29] and PHANTOM [26], for which a vulnerability has been

shown [18] in an early version of the protocol.

3 Model

3.1 Avalanche platform

We brieﬂy review the architecture of the Avalanche platform [3]. It consists of three separate built-in

blockchains, the exchange or X-Chain, the platform or P-Chain, and the contract or C-Chain. Addition-

ally there are a number of subnets. In order to participate in the protocols and validate transactions, a

party needs to stake at least 2’000 AVAX (about 50’000 USD in August 2022 [8]).

The exchange chain or X-Chain secures and stores transactions that trade digital assets, such as the

native AVAX token. This chain implements a variant of the Avalanche consensus protocol that only

partially orders the transactions and that is the focus of this work. All information given here refers to

the original speciﬁcation of Avalanche [28].

The platform chain or P-Chain secures platform primitives; it manages all other chains, designates

parties to become validators or removes them again from the validator list, and creates or deletes wallets.

The P-Chain implements the Snowman consensus protocol: this is a special case of Avalanche consensus

that always provides total order, like traditional blockchains. It is not explained in the whitepaper and

we do not describe it further here.

The C-Chain hosts smart contracts and runs transactions on an Ethereum Virtual Machine (EVM).

It also implements the Snowman consensus protocol of Avalanche and totally orders all transactions and

blocks.

3.2 Communication and adversary

We now abstract the Avalanche consensus protocol and consider a network of nparties N={p, q, . . . }

that communicate with each other by sending messages. An adversary may corrupt up to fof these

parties and cause them to behave maliciously and diverge arbitrarily from the protocol. Non-corrupted

parties are known as honest, messages and transactions sent by them are referred to as honest. Analo-

gously, corrupted parties send malicious transactions and messages. The parties may access a low-level

functionality for sending messages over authenticated point-to-point links between each pair of parties.

In the protocol, this functionality is accessed by two events send and receive. Parties may also access

a second low-level functionality for broadcasting messages through the network by gossiping, accessed

by the two events gossip and hear in the protocol. Both primitives are subject to network and timing

assumptions. We assume partial synchrony, as in the original Avalanche whitepaper [28]. Messages are

delivered according to an exponential distribution, that is, the amount of time between the sending and

the receiving of a message follows an exponential distribution with unknown parameter to the parties.

However, messages from corrupted parties are not affected by this delay and will be delivered as fast as

the adversary decides. This model differs from the traditional deﬁnition of partial synchrony [10], since

the adversary does not possess the ability to delay honest messages as it pleases.

3.3 Abstractions

The payload transactions of Avalanche are submitted by users and built according to the unspent trans-

action output (UTXO) model of Bitcoin [22]. A payload transaction tx contains a set of inputs, a set of

outputs, and a number of digital signatures. Every input refers to a position in the output of a transaction

executed earlier; this output is thereby spent (or consumed) and distributed among the outputs of tx. The

balance of a user is given by the set of unspent outputs of all transactions (UTXOs) executed by the

user (i.e., assigned to public keys controlled by that user). A payload transaction is valid if it is properly

authenticated and none of the inputs that it consumes has been consumed yet (according to the view of

the party executing the validation).

Blockchain protocols are generally formalized as atomic broadcast, since every party running the

protocol outputs the same ordered list of transactions. However, the transaction sequences output by

two different parties running Avalanche may not be exactly the same because Avalanche allows more

ﬂexibility and does not require a total order. Avalanche only orders transactions that causally depend on

each other. Thus, we abstract Avalanche as a generic broadcast according to Pedone and Schiper [24],

in which the total-order property holds only for related transactions as follows.

Deﬁnition 1. Two payloads tx and tx0are said to be related, denoted by tx ∼tx0, if tx consumes an output

of tx0or vice versa.

Our generic broadcast primitive is accessed through the events broadcast(tx)and deliver(tx). Sim-

ilar to other blockchain consensus protocols, it deﬁnes an “external” validity property and introduces a

predicate Vthat determines whether a transaction is valid [6].

Deﬁnition 2. A payload tx satisﬁes the validity predicate of Avalanche if all the cryptographic require-

ments are fulﬁlled and there is no other delivered payload with any input in common with tx.

For the remainder of this work, we ﬁx the external validation predicate Vto check the validity of

payloads according to the logic of UTXO mentioned before.

Since Avalanche is a randomized protocol, the properties of our broadcast abstraction need to be

fulﬁlled only with all but negligible probability.

Deﬁnition 3. A protocol solves validated generic broadcast with validity predicate Vand relation ∼if

it satisﬁes the following conditions, except with negligible probability:

Validity. If a honest party broadcasts a payload transaction tx, then it eventually delivers tx.

Agreement. If a honest party delivers a payload transaction tx, then all honest parties eventually de-

liver tx.

Integrity. For any payload transaction tx, every honest party delivers tx at most once, and only if tx was

previously broadcast by some party.

Partial order. If honest parties pand qboth deliver payload transactions tx and tx0such that tx ∼tx0,

then pdelivers tx before tx0if and only if qdelivers tx before tx0.

External validity. If a honest party delivers a payload transaction tx, then V(tx) = TRUE.

Note that different instantiations of the relation ∼transform the generic broadcast primitive into well-

known primitives. For instance, when no pair of transactions are related, generic broadcast degenerates

to reliable broadcast. Whereas when every two transactions are related, generic broadcast transforms

into atomic broadcast. In our context, broadcasting corresponds to submitting a payload transaction to

the network, whereas delivering corresponds to accepting a payload and appending it to the ledger.

The Avalanche protocol augments payload transactions to protocol transactions. A protocol transac-

tion additionally contains a set of references to previously executed protocol transactions, together with

further attributes regarding the execution. A protocol transaction in the implementation contains a batch

of payload transactions, but this feature of Avalanche is ignored here, since it affects only efﬁciency.

Throughout this paper, transaction refers to a protocol transaction, unless the opposite is indicated, and

payload means simply a payload transaction.

A transaction references one or multiple previous transactions, unlike longest-chain protocols, in

which each transaction has a unique parent [22]. An execution of the Avalanche protocol will therefore

create a directed acyclic graph (DAG) that forms its ledger data structure.

Given a protocol transaction T, all transactions that it references are called the parents of Tand

denoted by parents(T). The parents of Ttogether with the parents of those, recursively, are called the

ancestors of T, denoted by ancestors(T). Analogously, the transactions that have Tas parent are called

T2T3

T4T5T6

T7T8

u1!u2!

u3!

u6!

u3!

u10

u9!

u11

u13!

u15

u19!

u20

u12!

u13 u21!

u9!

u12!

u16!

u17!

u18

u2!u3!u4!u5!

Input Output

Tag

Figure 1. The UTXO model, conﬂicting transactions, and related transactions in Avalanche. The eight

transactions are labeled T1, ..., T8. Each transaction is divided into three parts: the left part is a tag Tito

identify the transaction, the middle part is its set of inputs, and the right part is its set of outputs. The

solid arrows indicate the references added by the protocol, showing the parents of each transaction. For

instance, T5references T2and T3and has them as parents. The dashed double-arrows indicate related

transactions. For example, T5and T2are related because u3is created by T2and consumed by T5. The

conﬂict sets are denoted by the shaded (red) rectangles. As illustrated, conﬂict sets can be symmetric, as

for T4and T5, where the conﬂict sets are identical (conﬂictSet[T4] = conﬂictSet[T5]) or asymmetric, as

for T6,T7, and T8where conﬂictSet[T6]∪conﬂictSet[T7] = conﬂictSet[T8].

the children of Tand are denoted by children(T). Finally, the children of Ttogether with their recursive

set of children are called the descendants of T, denoted by descendants(T).

Note that two payload transactions tx1and tx2in Avalanche that consume the same input are not

related, unless the condition of Deﬁnition 1 is fulﬁlled. However, two Avalanche payloads consuming

the same output conﬂict. For each transaction T, Avalanche maintains a set conﬂictSet[T]of transactions

that conﬂict with T.

4 A description of the Avalanche protocol

Avalanche’s best-known quality is its efﬁciency. Permissionless consensus protocols, such as those of

Bitcoin and Ethereum, are traditionally slow, suffer from low throughput and high latency, and consume

large amounts of energy, due to their use of proof-of-work (PoW). Avalanche substitutes PoW with a

random sampling mechanism that runs at network speed and that has every party adjust its preference to

that of a (perceived) majority in the system. Avalanche also differs from more traditional blockchains by

forming a DAG of transactions instead of a chain.

4.1 Overview

Avalanche is structured around its polling mechanism. In a nutshell, party urepeatedly selects a trans-

action Tand sends a query about it to krandomly selected parties in the network. If a majority of

them send a positive reply, the query is successful and the transaction contributes to the security of other

transactions. Otherwise, the transaction is still processed but does not contribute to the security of any

other transactions. Then the party selects a new transaction and repeats the procedure. A bounded num-

ber of such polls may execute concurrently. Throughout this work the terms “poll” and “query” are

interchangeable.

In more detail, the protocol operates like this. Through the gossip functionality, every party is aware

of the network membership N. A party locally stores all those transactions processed by the network

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

WhenisSpringcoming?ASecurityAnalysisofAvalancheConsensusIgnacioAmores-SesarUniversityofBern*ignacio.amores@unibe.chChristianCachinUniversityofBern*christian.cachin@unibe.chEnricoTedeschiTheArticUniversityofNorwayenrico.tedeschi@uit.no10thOctober,2022AbstractAvalancheisablockchainconsensusprotocolwi...

展开>> 收起<<

When is Spring coming A Security Analysis of Avalanche Consensus Ignacio Amores-Sesar.pdf

共25页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

When is Spring coming A Security Analysis of Avalanche Consensus Ignacio Amores-Sesar

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: