Blockchains and Byzantine Fault Tolerance form the basis of decentralized currencies and ledgers, such as Bitcoin, Ripple, ZeroCash, and Ethereum. Several studies have focused on the currency aspects (e.g. authenticity, integrity, anonymity, and independence from central banks). In this thesis, we start by exploring to understand the security challenges and practical solutions for building simple payment networks. Then, we leverage such understanding in identifying the security challenges of more advanced and complex systems, in particular Futures Exchanges. The decentralization of a Futures Exchange poses new security challenges: i) the interplay between the security and economic viability, i.e. using the Price Discrimination Attack one can strategically force a trader out of the market when the trader's anonymity is broken; ii) the non-monotonic security behavior of an Exchange, i.e. an honest action may invalidate security evidence; and iii) the proportional burden requirement in the presence of high-frequency participants. Our goal is to enucleate the non-trivial design principles to resolve these challenges for building secure and distributed financial exchanges. We demonstrate the application of the distilled design principles by building a cryptographic reference for a futures exchange called FuturesMEX. We also simulate the performance of a FuturesMEX Proof-of-Concept with the Lean Hog market data obtained from the Thomson Reuters Ticks History DB. The results show that the obtained protocol is feasible for a low-frequency market such as Lean Hog. Furthermore, we investigate an extension of public markets, i.e. dark pools (private markets), in which the order book information is conditionally visible to some (financially) suitable parties. We propose a new cryptographic scheme called Witness Key Agreement that makes dark trading possible by probing prices and volumes based on committed financial information Finally, we evaluate the theoretical and practical performance of the new scheme; using a simulation of the dark pool data collected from the aggressive Bloomberg Tradebook, we obtain positive results.