Permissionless blockchains offer pseudonymity rather than complete anonymity to their users. To enhance privacy for blockchain participants, on-chain mixers have been introduced. On-chain mixers enable users to deposit a fixed quantity of coins into a pool governed by smart contracts and subsequently withdraw those coins to a different address, thus breaking the linkability between users' addresses.

In this thesis, we first examine the usage of existing on-chain mixers. We show the wide use of on-chain mixers by malicious actors seeking to launder money. Additionally, on-chain mixers have a privacy feature known as the anonymity set, allowing users to blend in with a set of k other users. Our empirical findings show that privacy-ignorant users fail to interact with mixers correctly, thus not contributing effectively to the anonymity set.

Furthermore, we reveal that centralized regulators' sanctions have reduced the activities of on-chain mixers. We investigate the efficiency and potential security implications of censorship at various steps of a mixer-related transaction's lifecycle, including its generation, propagation, and validation. We indicate that fine-grained censorship could potentially lead to attacks. We also show that several blockchain application platforms' censorship is at the frontend level, and users can efficiently bypass the censorship using intermediary addresses.

Lastly, we develop two approaches to achieve cost-effective and cost-fair on-chain mixers. The first one is the improved Merkle Pyramid Builder (iMPB) approach, in which we batch deposits to update the Merkle tree, and propose a mechanism to amortize deposit fees in the batch over time. Our evaluation results show that this approach can remarkably reduce up to 7× in the amortized deposit cost. Additionally, we show that combining the iMPB approach and off-chain verification can reduce the cost further. Our analysis shows that the improved mixers can guarantee the properties of correctness, privacy, availability, efficiency, and fairness.