A consensus tree is a phylogenetic tree that summarizes the evolutionary relationships inferred from a collection of phylogenetic trees with the same set of leaf labels. Among the many types of consensus trees that have been proposed in the last fifty years, the frequency difference consensus tree is one of the more finely resolved types that retains a large amount of information. This article presents a new deterministic algorithm for constructing the frequency difference consensus tree. Given k phylogenetic trees with identical sets of n leaf labels, it runs in O ( k n log ⁡ n ) time, improving the best previously known solution. Furthermore, we demonstrate that the implementation of our algorithm is faster in practice than the prior implementations for the same problem.

Sidechains allow transaction dissemination and execution outside the blockchain main network (i.e., the mainchain), enabling a scalable, efficient, and secure financial infrastructure for the Internet of Things (IoT) without trusting any central authority. Existing sidechains either have online requirements or rely on intensive computation on a central operator, which does not meet the needs of IoT for dynamic changes and high performance. This article proposes an alternative sidechain construction, called Cumulus, which meets the needs of IoT by leveraging the classic Byzantine fault-tolerant (BFT) consensus protocols, such as PBFT, that have commonly been applied in permissioned blockchains. Cumulus builds BFT-based sidechains atop public blockchains (e.g., Ethereum) using smart contracts and ensures the bidirectional safety of users’ assets. Cumulus sidechains periodically interact with the mainchain and submit checkpoints through representatives selected in an efficient and decentralized manner. The experiments show that Cumulus sidechains outperform rollup-based sidechains, and state-of-the-art sidechain constructions, achieving two and three orders of magnitude improvement in throughput and latency while retaining comparable operational cost.

As adoption of blockchain-based systems grows, more attention is being given to privacy of these systems. Early systems like BitCoin provided few privacy features. As a result, systems with strong privacy guarantees, including Monero, Zcash, and MimbleWimble have been developed. Compared to BitCoin, these cryptocurrencies are much less understood. In this paper, we focus on MimbleWimble, which uses the Dandelion++ protocol for private transaction relay and transaction aggregation to provide transaction content privacy. We find that in combination these two features make MimbleWimble susceptible to a new type of denial-of-service attacks. We design, prototype, and evaluate this attack on the Beam network using a private test network and a network simulator. We find that by controlling only 10% of the network nodes, the adversary can prevent over 45% of all transactions from ending up in the blockchain. We also discuss several potential approaches for mitigating this attack.

Sidechains enable off-chain scaling by sending transactions in a private network rather than broadcasting them in the public blockchain (i.e., the mainchain) network. To this end, classic Byzantine fault-tolerant (BFT) consensus protocols such as PBFT seem an excellent fit to fuel sidechains for their permissioned settings and inherent robustness. However, designing a secure and efficient BFT-based sidechain protocol remains an open challenge.This paper presents Cumulus, a novel BFT-based sidechain framework for blockchains to achieve off-chain scaling without compromising any security and efficiency properties of both sides’ consensus protocols. Cumulus encompasses a novel cryptographic sortition algorithm called Proof-of-Wait to fairly select sidechain nodes to communicate with the mainchain in an efficient and decentralized manner. To further reduce the operational cost, Cumulus provides an optimistic checkpointing approach in which the mainchain will not verify checkpoints unless disputes happen. Meanwhile, end-users enjoy a two-step withdrawal protocol, ensuring that they can safely collect assets back to the mainchain without relying on the BFT committee. Our experiments show that Cumulus sidechains outperform ZK-Rollup, another promising sidechain construction, achieving one and two orders of magnitude improvement in throughput and latency while retaining comparable operational cost.