Musings on the HashGraph Protocol Its Security and Its Limitations Vinesh Sridhar

2025-05-02 0 0 1.68MB 30 页 10玖币
侵权投诉
Musings on the HashGraph Protocol:
Its Security and Its Limitations
Vinesh Sridhar
vsridhar@umd.edu
Erica Blum
erblum@umd.edu
Jonathan Katz
jkatz@cs.umd.edu
October 26, 2022
Abstract
The HashGraph Protocol is a Byzantine fault tolerant atomic broadcast protocol. Its novel use of
locally stored metadata allows parties to recover a consistent ordering of their log just by examining
their local data, removing the need for a voting protocol. Our paper’s first contribution is to present a
rewritten proof of security for the HashGraph Protocol that follows the consistency and liveness paradigm
used in the atomic broadcast literature. In our second contribution, we show a novel adversarial strategy
that stalls the protocol from committing data to the log for an expected exponential number of rounds.
This proves tight the exponential upper bound conjectured in the original paper. We believe that our
proof of security will make it easier to compare HashGraph with other atomic broadcast protocols and to
incorporate its ideas into new constructions. We also believe that our attack might inspire more research
into similar attacks for other DAG-based atomic broadcast protocols.
1 Introduction
Say that you have several databases around the world and want them all to store identical copies of data that
you input over time. This level of redundancy is common in cloud storage applications for example because
it makes the services resilient to database failures and errors accumulated during data transmission. The
most obvious solution has us construct a centralized system in which a single server disseminates the data to
the rest. However, this produces a single point of failure and requires recipients to trust the central server.
These drawbacks motivate the study of decentralized systems, in which trust and resiliency are spread over
many parties rather than just one.
Blockchain protocols, in which parties maintain a distributed log of transactions, are a popular application
of this concept. For such protocols to be practical, parties must be able to maintain consistent local logs
and commit new transactions to their log promptly. When a protocol is able to do this, we say that it solves
the atomic broadcast problem. More formally, we require any atomic broadcast protocol to have these two
properties: consistency, that everyone’s logs agree, and liveness, that an inputted transaction will eventually
be placed in every party’s log. We would like this to hold even if transactions may be delayed and reordered
and a fraction of the parties act arbitrarily.
The HashGraph Consensus Protocol [1] [2] is an example of an atomic broadcast protocol. Often these
protocols are divided into two stages: Parties first distribute their transactions and thereafter vote on whose
transactions will be added to the network and in what order. HashGraph differentiates itself from other
constructions, such as HoneyBadgerBFT [12], Dumbo [9], and BEAT [5], in the way it handles voting
on the final ordering of the log. Rather than utilizing a separate voting protocol, votes are embedded
into the structure of each party’s log itself. The authors call the data structure that represents the log a
hashgraph. It is a directed acyclic graph (DAG) that not only stores the transactions a party has received,
but also the communication history that led up to the distribution of that transaction. As it accumulates
transactions, a party’s own hashgraph eventually contains enough information to let them decide on a globally
1
arXiv:2210.13682v1 [cs.CR] 25 Oct 2022
consistent transaction log. As long as parties can maintain consistent hashgraphs, they can eventually output
transactions in a consistent order.
Our first contribution is a more formal analysis of HashGraph’s consistency and liveness properties than
the ones in the original papers [1] [2], showing that it is indeed a secure atomic broadcast protocol. On
the negative side, we show that although liveness holds it may take Θ(2n) rounds for a transaction to be
committed to a party’s log. The original HashGraph papers [1] [2] only showed an O(2n) upper bound; we
have proved it tight.
In Section 2, we discuss related work. In Section 3, we explain the model and define relevant terms.
Section 4 describes the HashGraph data structure and protocol. In Section 5, we present our consistency
and liveness proofs, and in Section 6 we show that transactions may require a long time to be committed.
Lastly, in Section 7 we provide some concluding remarks.
2 Related Work
The original HashGraph Consensus paper was published in 2016 [1], and a sequel that clarified the protocol
was published in 2020 [2]. Lasy [11] presents an analysis of the protocol and several variants, focusing on
empirical performance tests. Crary [3] also presents a proof of security for the HashGraph protocol, but
their article mainly focuses on applying the original paper’s proof to the Coq proof assistant. We aim to
rewrite the proof to emphasize how the protocol satisfies liveness and consistency, making the proof more in
line with other atomic broadcast protocol proofs of correctness.
In the HashGraph protocol, parties maintain a directed acyclic graph called a hashgraph to store metadata
about messages sent and received. Other DAG-based asynchronous Byzantine fault tolerant consensus
protocols include Aleph [7], DAG-Rider [10], Bullshark [8], Tusk [4], and JointGraph [13].
3 Model
Let ndenote how many parties participate in the protocol. Let tbe an upper bound on the number of
corrupted parties. These parties may act arbitrarily, and we may consider them coordinated by a single
entity called the adversary. The remaining parties are honest and follow the protocol exactly as specified.
Throughout, we assume that t < n/3. We consider a static adversary that chooses which parties to corrupt
at the beginning of execution.
We also consider an asynchronous network, where message delays are unbounded and the adversary may
delay and reorder messages arbitrarily. However, we assume that messages must be delivered eventually.
The HashGraph protocol solves the atomic broadcast problem, which we will now formally describe.
Definition 1 (Atomic Broadcast).Let Πbe a protocol executed by nparties p1, . . . , pn, in which each party
receives transactions from an external mechanism and outputs to a write-once log of transactions. We say
that Πis a secure atomic broadcast protocol if it has the following properties:
•(Consistency) Let logi, logjbe logs held by honest pi, pj(possibly at different points in time). Then,
logiis a prefix of logjor vice-versa.
•(Liveness) Every transaction placed in an honest party’s buffer is eventually included in every honest
party’s log.
The HashGraph protocol also assumes that the parties have established a public key infrastructure (PKI),
allowing them to sign arbitrary messages. We assume the signature scheme is unforgeable, preventing the
adversary from spoofing a message to seem as if it were sent by an honest party. Finally, the protocol
assumes that all parties agree on some collision-resistant hash function.
2
4 Consensus Protocol
Throughout the protocol, each party builds and processes their own hashgraph. A hashgraph is a directed
acyclic graph which represents the flow of gossip through the network from its owner’s perspective. Its
vertices store the messages it has received from other parties and its edges help determine the set of parties
that propagated that message before it was first seen by the hashgraph’s owner. Thus, when a party plearns
a new message, it also learns the chain of parties that gossiped the message before preceived it. We will see
below that enough information is embedded in a hashgraph to allow parties to commit transactions to their
log without needing a networked voting protocol.
At a high level, the protocol works like so: Upon receiving a message m, a party adds it as a vertex to its
hashgraph. It then processes its locally-stored hashgraph to see if any new information should be committed
to the log. Then it produces a message of its own that it adds to its hashgraph. This message points to m,
encoding the chain of gossip, and contains a set of transactions the party wants to add to everyone’s log.
The networked and local aspects of the protocol trigger each other in this way indefinitely, as the parties
construct an ever-increasing log of transactions.
We will first describe the hashgraph data structure and the way it can be used to commit transactions
in more detail. Then we will discuss the protocol itself and how it applies the properties of a hashgraph to
implement atomic broadcast.
4.1 The HashGraph data structure
The hashgraph data structure is a directed acyclic graph. We call the messages sent during the protocol
events. The vertices in a hashgraph represent events that its owner has either created or validated upon
receipt. As noted above, honest parties create events upon receiving an event from another party. An event
contains a set of transactions that its creator wants to commit to the log as well as these pieces of metadata:
a creator ID, a timestamp from the creator’s local clock, and a cryptographic signature by the creator. It
also holds hashes of two other events, called a self-parent and an other-parent respectively. These effectively
act as parent pointers, and we represent them as such in hashgraph diagrams. If an event was created by an
honest party, we call it an honest event.
Given some event y, we will use the notation y.transactions,y.timestamp,y.creator, etc. to refer to
these fields. We will now formally define the event properties mentioned above.
Definition 2 (self-parent).An honest event’s self-parent is its creator’s previous event.
Definition 3 (other-parent).An honest event’s other-parent is some earlier event created by a different
party. Honest parties only create events upon receiving an event from another party.
Definition 4 (ancestors and descendants).An ancestor of some event xis any event that can be reached
by traversing parent pointers in the subgraph rooted at x. An ancestor of xis a self-ancestor if it can be
reached solely using self-parent pointers. If some event yis an ancestor of x, we say xis a descendant of
y.
The above description applies to all honest events except the very first “genesis” event each party creates.
A genesis event is a dummy event with no parents that parties create on their own in order to start the
protocol.
Figure 1 is a diagram of a hashgraph. The vertices represent events, and the edges represent parent
relationships. Events in the same column are created by the same party and time flows upward. As a result,
when an honest party creates an event, that event’s self-parent is directly beneath it and its other-parent
lies in a different column. In the diagram, we say that event Ais an ancestor of event D. Likewise, event D
is a descendant of event A.
A hashgraph is supposed to reveal what participating parties have learned over time. For example, if
party p1holds the hashgraph in Figure 1, then columns 2 through 5 tell p1about what events p2through
p5are aware of. To maintain this property, we require that an honest party only adds a new event yto its
3
p1p3p4p5
p2
D
A
Figure 1: An example hashgraph where n= 5.
hashgraph after receiving all of y’s ancestors. The ancestors of yindicate the events y.creator knew about
and gossiped about at the time it created y, so if we were to omit this requirement and consider yin isolation,
the hashgraph would no longer track the spread of gossip through the network.
Because honest events are only created upon receiving another event and p1only adds some event yto
its hashgraph after receiving all of y’s ancestors, p1can learn every event that y’s creator knows by tracing
through y’s ancestors in its own hashgraph. This would be sufficient if all parties were honest, but the
adversary might try to disrupt this system by introducing forks into honest hashgraphs.
Definition 5 (fork).Afork is a pair of events (x, y)from the same creator such that xis not an ancestor
of yand yis not an ancestor of x.
A corrupted party may choose to fork by creating two events (z, z0) that point to the same self-parent.
zand z0may have different other-parents, hold different transactions, have conflicting timestamps and
signatures, or a combination of the above. Ultimately, this allows the adversary to obscure the events it
really knows by cultivating two disjoint branches in its hashgraph. It can then tell some honest parties it
has some set of events and other honest parties that it has some other set of events. This temporarily causes
their hashgraphs to differ. Even once all honest parties discover the fork, they then must agree upon a
branch to process and a branch to ignore. Figures 2 and 3 show an example of a fork. We will see how the
protocol mitigates the effect of forks below.
We say an event xobserves a fork if xis a descendant of two events zand z0such that (z, z0) is a
fork. Honest parties never create forks, so a fork betrays that its creator is corrupted. Similarly, other
relationships between events disclose information about other parties. Below we define seeing,strongly
seeing, and graph-consistency.
Definition 6 (seeing).Fix some hashgraph H. An event xsees an event yin Hif yis an ancestor of xin
Hand xdoes not observe a fork from y’s creator.
Definition 7 (strongly seeing).Fix some hashgraph H. An event xstrongly sees an event yin Hif x
sees a set of greater than 2n/3events with distinct creators that each see y.
4
z′
p1p3p4A
p2
z
p1p3p4A
p2
Figure 2: Honest party p2’s hashgraph is on the left and honest party p3’s hashgraph is on the right. Vertices
in the same locations represent the same events held by both parties. The adversary has created a fork by
gossiping the conflicting events zand z0.
Definition 8 (graph-consistent).Let Aand Bbe two hashgraphs. Aand Bare graph-consistent if for
every event xthat appears in both Aand B, the subgraph containing x’s ancestors is the same in Aand B.
Note that the original paper uses the term consistent to refer to this property [1]. We have opted to use
the term graph-consistent to reduce confusion between this and consistency for atomic broadcast.
4.2 The HashGraph Protocol
We will now describe the protocol in more detail (Pseudocode appears in Algorithm 1). At the beginning of
the protocol, each party multicasts their own genesis event. Unlike a regular event, this one has no parents.
Parties then perpetually wait for new events. Consider some honest party p. Upon receiving some new event
ysuch that p’s hashgraph contains all of y’s ancestors, padds yto its hashgraph. It then creates a new
event whose self-parent is p’s previous event and whose other parent is y. Lastly, pprocesses its hashgraph
locally to see if it contains enough information to commit more events to its log. It does this by invoking
three functions: divideRounds,decideFame, and findOrder.
In practice, parties share multiple events at the same time. This is called a sync. When honest party
pisyncs with honest party pj,pjreceives all of the events pihas. Even if it adds several events to its
hashgraph, pjonly creates a single event in response. That event’s self-parent is pj’s previous event and its
other-parent is the latest event pishared in its sync. By definition, this must be the event picreated right
before it synced with pj.
Incorrectly formatted events are discarded, and an honest party buffers a received event until it has added
all of its ancestors to its hashgraph.
We will now describe how divideRounds,decideFame, and findOrder allow a party to commit transactions
just by examining its own hashgraph. We reproduce the original HashGraph paper’s [1] pseudocode for these
three functions in Appendix A.
5
摘要：

MusingsontheHashGraphProtocol:ItsSecurityandItsLimitationsVineshSridharvsridhar@umd.eduEricaBlumerblum@umd.eduJonathanKatzjkatz@cs.umd.eduOctober26,2022AbstractTheHashGraphProtocolisaByzantinefaulttolerantatomicbroadcastprotocol.Itsnoveluseoflocallystoredmetadataallowspartiestorecoveraconsistentorde...

展开>> 收起<<
Musings on the HashGraph Protocol Its Security and Its Limitations Vinesh Sridhar.pdf

共30页,预览5页

还剩页未读， 继续阅读

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

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：30 页 大小：1.68MB 格式：PDF 时间：2025-05-02

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 30
评分 收藏
分享
立即下载
客服
关注