In this paper, we investigate a fundamental assignment problem for a type of constrained group service. A group is considered successfully formed only if the number of assigned patrons falls within the specified lower and upper-bound constraints. We introduce the concept of rank-consistent to characterize a useful subset of the assignment problem. Although the problem is still NP-hard, we introduce the technique of allocation vectors to handle the complexity. This technique not only allows us to exploit several characteristics for performance optimization but also enables us to design a generic procedure to obtain the optimal physical assignment under a given allocation vector. We lay the foundation of a 1/2 approximation algorithm and a branch and bound algorithm for seeking the optimal solution. The branch and bound algorithm employs a specific pattern of optimal allocation vector and several newly proposed pruning techniques, especially the one that utilizes the dominance relations between allocation vectors. Extensive experiments demonstrate that our algorithm is much more effective than a set of heuristic greedy algorithms.

The distributed cryptocurrency networking is critical because the information delivered through it drives the mining consensus protocol and the rest of the operations. However, the cryptocurrency peer-to-peer (P2P) network remains vulnerable, and the existing security approaches are either ineffective or inefficient because of the permissionless requirement and the broadcasting overhead. We design and build a Lightweight and Identifier-Oblivious eNgine (LION) for the anomaly detection of the cryptocurrency networking. LION is not only effective in permissionless networking but is also lightweight and practical for the computation-intensive miners. We build LION for anomaly detection and use traffic analyses so that it minimally affects the mining rate and is substantially superior in its computational efficiency than the previous approaches based on machine learning. We implement a LION prototype on an active Bitcoin node to show that LION yields less than 1% of mining rate reduction subject to our prototype, in contrast to the state-of-the-art machine-learning approaches costing 12% or more depending on the algorithms subject to our prototype as well, while having detection accuracy of greater than 97% F1-score against the attack prototypes and real-world anomalies. LION therefore can be deployed on the existing miners without the need to introduce new entities in the cryptocurrency ecosystem.

Bitcoin P2P networking is especially vulnerable to networking threats because it is permissionless and does not have the security protections based on the trust in identities, which enables the attackers to manipulate the identities for Sybil and spoofing attacks. The Bitcoin node keeps track of its peer’s networking misbehaviors through ban scores. In this paper, we investigate the security problems of the ban-score mechanism and discover that the ban score is not only ineffective against the Bitcoin Message-based DoS (BM-DoS) attacks but also vulnerable to the Defamation attack as the network adversary can exploit the ban score to defame innocent peers. To defend against these threats, we design an anomaly detection approach that is effective, lightweight, and tailored to the networking threats exploiting Bitcoin’s ban-score mechanism. We prototype our threat discoveries against a real-world Bitcoin node connected to the Bitcoin Mainnet and conduct experiments based on the prototype implementation. The experimental results show that the attacks have devastating impacts on the targeted victim while being cost-effective on the attacker side. For example, an attacker can ban a peer in two milliseconds and reduce the victim’s mining rate by hundreds of thousands of hash computations per second. Furthermore, to counter the threats, we empirically validate our detection countermeasure’s effectiveness and performances against the BM-DoS and Defamation attacks.

Payment Channel Network (PCN) is a scaling solution for Cryptocurrency networks. We advance the practicality of the PCN multi-path routing by better modeling the system to incorporate the cost of routing fee and the privacy requirement of the channel balance. We design our Auto-Tune algorithm to optimize the routing concerning both the success rate and the routing fee and utilizing the limited channel capacity information (due to the privacy of the PCN user, the channel balance information is withheld). The simulation result shows Auto-Tune outperforms the current PCN implementation based on single-path routing in the success rate. We compare Auto-Tune against the state-of-the-art Flash algorithm, utilizing the channel-balance information, violating the PCN user privacy, and diverging from current implementation practices. Auto-Tune achieves the routing fee close to the optimal fee obtained by Flash, and its success rate is also close to the success rate achieved by Flash.

Blockchain technology is gaining popularity in industries and governments for information monitoring, distribution, and tracking. Thanks to the built-in security properties, blockchain provides security integrity to various decentralized applications (dApps) involving distributed operations including supply chain, healthcare, banking, internet of things (IoT), and networking. In this paper, we propose a generic blockchain framework (GBF) for applying two blockchains to the dApp systems, one to establish trust and the other to use the trust for securing applications. GBF provides a generally applicable framework and addresses the foundational questions of the blockchain objectives, participants, and the underlying distributed consensus protocol in use. We apply GBF to various case studies from the recent blockchain research to show its effectiveness and generality. We also prototype GBF using smart contract and experiment on CloudLab for preliminary evaluations focusing on the application-general metrics. We propose GBF to facilitate blockchain/dApp research and development by providing the initial framework and enable the preliminary analyses so that the decentralized applications with specific aims can build on GBF.

Blockchain relies on the underlying peer-to-peer (p2p) networking to broadcast and get up-to-date on the blocks and transactions. It is therefore imperative to have high p2p connectivity for the quality of the blockchain system operations. High p2p networking connectivity ensures that a peer node is connected to multiple other peers providing a diverse set of observers of the current state of the blockchain and transactions. However, in a permissionless blockchain network, using the peer identifiers—including the current approach of counting the number of distinct IP addresses and port numbers—can be ineffective in measuring the number of peer connections and estimating the networking connectivity. Such current approach is further challenged by the networking threats manipulating the identifiers. We build a robust estimation engine for the p2p networking connectivity by sensing and processing the p2p networking traffic. We implement a working Bitcoin prototype connected to the Bitcoin Mainnet to validate and improve our engine’s performances and evaluate the estimation accuracy and cost efficiency of our estimation engine.

Group services are highly important for a variety of computing application domains. In this paper, we study the fundamental problem of allocating a set of service patrons to a set of service groups in an attempt to maximize the total profit gained by the grouping platform. The problem under consideration is unique in that group service is not provided at all unless its lower bound requirement is satisfied. In addition, we allow each service patron to join multiple groups. In this paper, after proving the hardness property of the problem, we focus first on a special case of the problem. To this end, we propose two approaches. One aims at providing a suboptimal solution using a 1/2-approximation algorithm. The other approach turns to seeking an optimal solution using a branch and bound technique. For this purpose, we introduce a theorem that captures a useful property of an optimal allocation. Based on this theorem, we design an efficient branch and bound algorithm to find an optimal solution. We then extend these methods to solve the general problem. Extensive experiments show that our branch and bound algorithm is able to obtain an optimal solution with a small amount of computation time in many different settings.