  Initiated from Nakamoto's Bitcoin system, blockchain technology has
demonstrated great capability of building secure consensus among decentralized
parties at Internet-scale, i.e., without relying on any centralized trusted
party. Nowadays, blockchain systems find applications in various fields. But
the performance is increasingly becoming a bottleneck, especially when
permissionless participation is retained for full decentralization.
  In this work, we present a new consensus protocol named GHAST (Greedy
Heaviest Adaptive Sub-Tree) which organizes blocks in a Tree-Graph structure
(i.e., a directed acyclic graph (DAG) with a tree embedded) that allows fast
and concurrent block generation. GHAST protocol simultaneously achieves a
logarithmically bounded liveness guarantee and low confirmation latency. More
specifically, for maximum latency $d$ and adversarial computing power bounded
away from 50\%, GHAST guarantees confirmation with confidence $\ge
1-\varepsilon$ after a time period of $O(d\cdot \log(1/\varepsilon))$. When
there is no observable attack, GHAST only needs $3d$ time to achieve
confirmation at the same confidence level as six-block-confirmation in Bitcoin,
while it takes roughly $360d$ in Bitcoin.

Cryptography and Security;Distributed, Parallel, and Cluster Computing