Towards Robust Blockchain Systems: From Fair Consensus to Verifiable Data Access

Abstract

Blockchain technology has transformed distributed systems by enabling mutually untrusted nodes to reach agreement without a central authority. Such trustless decentralized paradigm relies on the robustness of system design mainly from two components: the consensus layer governing block production and the data layer governing data consumption. However, these pillars of robustness could be undermined in a Byzantine environment, where adversarial participants may strategically misbehave, leading to biased data production and compromised data access. This thesis systematically addresses robustness vulnerabilities across both layers, ensuring that blockchain systems remain fair, predictable, and verifiable throughout the entire data lifecycle. At the consensus layer, we first address selfish mining in Proof-of-Work (PoW), which allows adversarial miners to gain disproportionate revenue. We introduce an unfairness metric based on the divergence between computing power and mining revenue, and propose Tit-for-Tat (TFT), a block-promotion strategy that detects suspicious forking behavior and selectively delays block propagation. To optimize this defense, we formulate the Delay Vector problem and develops efficient approximation algorithms. Second, we study block withholding in Byzantine Fault Tolerant Proof-of-Stake (BFT-PoS), where proposers may delay blocks to extract additional Maximal Extractable Value (MEV). To restore predictable block generation, we propose InTime, an incentive mechanism that rewards timely proposals according to transaction arrival rates observed across the network. InTime combines an Arrival Rate Incentive, a Committee Time Witness workflow, and a Shift-Mean Estimation algorithm to collect and verify timing information under adversarial conditions. At the data layer, we propose the Merkle Bloom Filter Tree (MBFT), a framework for authenticated aggregate queries with keyword and range predicates. MBFT supports efficient verification for complex on-chain queries, including time-window queries, while controlling storage overhead. We design a novel Merge Bloom Filter (MBF) for space-efficient handling of dynamic sets during query authentication.