Since the introduction of Bitcoin in 2008, blockchain has gained wide attention for its disruptive ability to securely maintain a tamper-proof transaction log among a large group of P2P nodes, without the need of a centralized trusted authority. Blockchain has enabled us a rich spectrum of new financial instruments and tools, and has also brought major impacts on many different data services like data storage, data analytics, data sharing, and data trading. Despite the good wishes of blockchain, there are many hard nuts to crack when we want to utilize it for building advanced data services, such as how to preserve data protection on the "transparent" blockchain, how to devise fair protocols for mutually untrusted parties, and how to minimize the overhead when handling computationally expensive tasks.

This dissertation presents various algorithmic designs to craft privacy-assured and advanced data services atop blockchains, with an aim to resolve central trust issues in versatile data-driven applications, and identify tailored and effective treatments to address critical challenges in decentralized application (Dapp) developments. Firstly, we propose the design of a blockchain-assisted encrypted database with expressive content search capabilities, which enforces a generalized solution for assuring trustworthiness of search results returned by various service providers (e.g., public cloud and P2P nodes in emerging decentralized storage systems). Secondly, we propose the design of a decentralized, privacy-assured, and correct aggregation framework atop blockchain, which totally eliminates the need for a centralized service provider, through crafting an open workforce marketplace atop blockchain and securely conducting the aggregation task with spare computing resources allocated from individuals. Thirdly, we further propose the design of a blockchain-based data marketplace specially for monetizing crowd wisdom solicited in the wild, which aims to achieve large-scale knowledge discovery and monetization in a privacy-preserving, quality-controlled, and fair manner, without the need for a trusted arbiter. Each of the presented system designs is carefully implemented and evaluated, and we believe that our systems could shed lights on how to securely utilize blockchain to revolutionize current data-driven applications, and vastly boost their integrations in real practice.