Abstract
Cryptocurrency exchange services are either trusted central entities that have been routinely hacked (losing over 8 billion USD), or decentralized services that make all orders public before they are settled. The latter allows market participants to “front run” each other, an illegal operation in most jurisdictions. We extend the “Insured MPC” approach of Baum et al. (FC 2020) to construct an efficient universally composable privacy preserving decentralized exchange where a set of servers run private cross-chain exchange order matching in an outsourced manner, while being financially incentivised to behave honestly. Our protocol allows for exchanging assets over multiple public ledgers, given that users have access to a ledger that supports standard public smart contracts. If parties behave honestly, the on-chain complexity of our construction is as low as that of performing the transactions necessary for a centralized exchange. In case malicious behavior is detected, users are automatically refunded by malicious servers at low cost. Thus, an actively corrupted majority can only mount a denial-of-service attack that makes exchanges fail, in which case the servers are publicly identified and punished, while honest clients do not to lose their funds. For the first time in this line of research, we report experimental results on the MPC building block, showing the approach is efficient enough to be used in practice.
This work was supported by the Concordium Foundation, by Protocol Labs grant S2LEDGE and by the Independent Research Fund Denmark with grants number 9040-00399B (TrA2C) and number 9131-00075B (PUMA).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Throughout this work, we treat \(\mathcal {F}_{\mathsf {EX}}\) as an ordinary UC functionality and not a global functionality (which would intuitively make more sense). This is due to subtle issues that would arise in the proof if \(\mathcal {F}_{\mathsf {EX}}\) was global, namely the simulator would not be able to equivocate the necessary outputs.
- 2.
To ensure that all clients can be reimbursed in case of a malicious server, the deposit from each server must have value equal or greater to the total value of input given by clients during an exchange. However, in practice only a small percentage of this would be sufficient to incentivize honest behaviour and the requirement could even be considered equivalent to the reserve requirement of banks.
- 3.
This is possible, even if \(\mathcal {F}_{\mathsf {Ident}}\) is global, as \(\mathcal {S}\) can alter all messages between \(\mathcal {A}\) and global functionalities. This will not be noticeable for \(\mathcal {Z}\) as \(\mathcal {F}_{\mathsf {Ident}}\) only outputs information for a specific \(sid\) to TMs acting in that session.
- 4.
All this information was signed by \(\mathcal {F}_{\mathsf {TSig}}\) and must therefore be valid.
- 5.
Although we should note that the benchmarks of threshold signatures by Gennaro and Goldfeder [34] are not optimized and run on a single-core consumer laptop whereas our benchmark of \(C_\mathtt {compSwap}\) runs on a powerful AWS instance. We expect that the time required for the threshold signatures can be reduced significantly.
- 6.
Technically 4 transactions are needed since the servers must put down a deposit to the smart contract, and receive this back at the end. However, the deposit can be reused for an arbitrary amount of executions of exchanges, and we consider this as purely overhead related to system setup. In case of malicious behaviour our protocol uses at most 7 transactions to either complete the exchange or refund the clients and return the honest servers’ deposits.
References
Alexandra Institute. FRESCO - a FRamework for Efficient Secure COmputation. https://github.com/aicis/fresco
Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, L.: Secure multiparty computations on bitcoin. In: 2014 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, May 2014
Badertscher, C., Maurer, U., Tschudi, D., Zikas, V.: Bitcoin as a transaction ledger: a composable treatment. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 324–356. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_11
Baum, C., David, B., Dowsley, R.: A framework for universally composable publicly verifiable cryptographic protocols. Cryptology ePrint Archive, Report 2020/207 (2020). https://eprint.iacr.org/2020/207
Baum, C., David, B., Dowsley, R.: Insured MPC: efficient secure computation with financial penalties. In: Bonneau, J., Heninger, N. (eds.) FC 2020. LNCS, vol. 12059, pp. 404–420. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-51280-4_22
Baum, C., David, B., Dowsley, R., Nielsen, J.B., Oechsner, S.: CRAFT: composable randomness and almost fairness from time. Cryptology ePrint Archive, Report 2020/784 (2020). https://eprint.iacr.org/2020/784
Baum, C., David, B., Frederiksen, T.: P2DEX: privacy-preserving decentralized cryptocurrency exchange. Cryptology ePrint Archive, Report 2021/283 (2021). https://eprint.iacr.org/2021/283
Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: 22nd ACM STOC. ACM Press, May 1990
Benhamouda, F., Halevi, S., Halevi, T.: Supporting private data on hyperledger fabric with secure multiparty computation. In: IEEE IC2E, pp. 357–363, April 2018
Bentov, I., Ji, Y., Zhang, F., Breidenbach, L., Daian, P., Juels, A.: Tesseract: real-time cryptocurrency exchange using trusted hardware. In: ACM CCS 2019. ACM Press, November 2019
Bentov, I., Kumaresan, R.: How to use bitcoin to design fair protocols. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 421–439. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44381-1_24
Bentov, I., Kumaresan, R., Miller, A.: Instantaneous decentralized poker. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 410–440. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_15
Binance: Binance DEX Documentation (2020). https://docs.binance.org
Bowe, S., Chiesa, A., Green, M., Miers, I., Mishra, P., Wu, H.: ZEXE: enabling decentralized private computation. In: 2020 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, May 2020
Bulck, J.V., et al.: Foreshadow: extracting the keys to the intel SGX kingdom with transient out-of-order execution. In: USENIX Security Symposium 2018, pp. 991–1008. USENIX Association (2018)
Bünz, B., Agrawal, S., Zamani, M., Boneh, D.: Zether: towards privacy in a smart contract world. In: Bonneau, J., Heninger, N. (eds.) FC 2020. LNCS, vol. 12059, pp. 423–443. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-51280-4_23
Camenisch, J., Drijvers, M., Gagliardoni, T., Lehmann, A., Neven, G.: The wonderful world of global random oracles. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 280–312. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_11
Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd FOCS. IEEE Computer Society Press, October 2001
Canetti, R.: Universally composable signature, certification, and authentication. In: IEEE (CSFW), p. 19. IEEE Computer Society (2004)
Canetti, R., Dodis, Y., Pass, R., Walfish, S.: Universally composable security with global setup. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 61–85. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70936-7_4
Canetti, R., Gennaro, R., Goldfeder, S., Makriyannis, N., Peled, U.: UC non-interactive, proactive, threshold ECDSA with identifiable aborts. Cryptology ePrint Archive, Report 2021/060 (2021). https://eprint.iacr.org/2021/060
Canetti, R., Makriyannis, N., Peled, U.: UC non-interactive, proactive, threshold ECDSA. Cryptology ePrint Archive, Report 2020/492 (2020). https://eprint.iacr.org/2020/492
Cartlidge, J., Smart, N.P., Alaoui, Y.T.: Multi-party computation mechanism for anonymous equity block trading: a secure implementation of Turquoise Plato Uncross. Cryptology ePrint Archive, Report 2020/662 (2020). https://eprint.iacr.org/2020/662
Cartlidge, J., Smart, N.P., Talibi Alaoui, Y.: MPC joins the dark side. In: ASIACCS 2019. ACM Press, July 2019
Choudhuri, A.R., Green, M., Jain, A., Kaptchuk, G., Miers, I.: Fairness in an unfair world: Fair multiparty computation from public bulletin boards. In: ACM CCS 2017. ACM Press, October/November 2017
Cleve, R.: Limits on the security of coin flips when half the processors are faulty (extended abstract). In: 18th ACM STOC. ACM Press, May 1986
Cramer, R., Damgård, I., Escudero, D., Scholl, P., Xing, C.: SPD \(\mathbb{Z}_{2^k}\): efficient MPC mod \(2^k\) for dishonest majority. In: CRYPTO, Part II, 2018. LNCS. Springer, Heidelberg, August 2018
Daian, P., et al.: Flash boys 2.0: frontrunning in decentralized exchanges, miner extractable value, and consensus instability. In: 2020 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, May 2020
Damgård, I., Escudero, D., Frederiksen, T.K., Keller, M., Scholl, P., Volgushev, N.: New primitives for actively-secure MPC over rings with applications to private machine learning. In: 2019 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, May 2019
Damgård, I., Pastro, V., Smart, N., Zakarias, S.: Multiparty computation from somewhat homomorphic encryption. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 643–662. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_38
Dziembowski, S., Eckey, L., Faust, S.: FairSwap: how to fairly exchange digital goods. In: ACM CCS 2018. ACM Press, October 2018
Escudero, D., Ghosh, S., Keller, M., Rachuri, R., Scholl, P.: Improved primitives for MPC over mixed arithmetic-binary circuits. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 823–852. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_29
Ga̧gol, A., Kula, J., Straszak, D., Świȩtek, M.: Threshold ECDSA for decentralized asset custody. Cryptology ePrint Archive, Report 2020/498 (2020). https://eprint.iacr.org/2020/498
Gennaro, R., Goldfeder, S.: One round threshold ECDSA with identifiable abort. Cryptology ePrint Archive, Report 2020/540 (2020). https://eprint.iacr.org/2020/540
Jakobsen, T.P., Nielsen, J.B., Orlandi, C.: A framework for outsourcing of secure computation. In:Ahn, G., Oprea, A., Safavi-Naini, R. (eds.) ACM CCSW 2014, pp. 81–92. ACM (2014)
Katz, J., Maurer, U., Tackmann, B., Zikas, V.: Universally composable synchronous computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 477–498. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_27
Kiayias, A., Zhou, H.-S., Zikas, V.: Fair and robust multi-party computation using a global transaction ledger. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 705–734. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_25
Knuth, D.E.: The Art of Computer Programming, Sorting and Searching, 2nd edn., vol. 3. Addison-Wesley, (1998)
Kosba, A.E., Miller, A., Shi, E., Wen, Z., Papamanthou, C.: Hawk: the blockchain model of cryptography and privacy-preserving smart contracts. In: 2016 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, May 2016
Kumaresan, R., Bentov, I.: Amortizing secure computation with penalties. In: ACM CCS 2016. ACM Press, October 2016
Kumaresan, R., Moran, T., Bentov, I.: How to use bitcoin to play decentralized poker. In: ACM CCS 2015. ACM Press, October 2015
Massacci, F., Ngo, C.N., Nie, J., Venturi, D., Williams, J.: FuturesMEX: secure, distributed futures market exchange. In: 2018 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, May 2018
Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008)
Selfkey: A Comprehensive List of Cryptocurrency Exchange Hacks 2020. https://selfkey.org/list-of-cryptocurrency-exchange-hacks/
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendix A Smart Contract Functionality \(\mathcal {F}_{\mathsf {SC}}\)
Appendix A Smart Contract Functionality \(\mathcal {F}_{\mathsf {SC}}\)
We now describe the smart contract on a high level, meaning its different states and state transitions. This is to ease understanding, the full description will be presented later. The Smart Contract will have 7 different states \(\mathtt {init},\mathtt {ready},\mathtt {abort},\mathtt {ok1},\mathtt {ok2},\mathtt {reimburse1},\mathtt {reimburse2}\) where \(\mathtt {init}\) is the initial state. State transitions are performed whenever the global clock \(\mathcal {F}_{\mathsf {Clock}}\) changes and depending on the messages that are present on the ledger that \(\mathcal {F}_{\mathsf {SC}}\) acts upon.
-
\(\mathtt {init}\) If a tick happens, then check if all servers signed the same \(\mathsf {vk},\widehat{\mathsf {vk}}_{{1}},\dots ,\widehat{\mathsf {vk}}_{{n}}\) using their individual \(\widehat{\mathsf {sk}}_{{i}}\) and that \(\mathcal {P} _i\) sent \(\mathsf {coins}(d)\). If so then change state to \(\mathtt {ready}\), otherwise reimburse all servers and stay in \(\mathtt {init}\).
-
\(\mathtt {ready}\) If a tick happens and a message “done” is present, signed by \(\mathsf {sk} \), then reimburse all servers and set the state to \(\mathtt {init}\). If a tick happens and a message “abort” is present, signed by a \(\widehat{\mathsf {sk}}_{{i}}\) that initialized the contract, then change the state to \(\mathtt {abort}\).
-
\(\mathtt {abort}\) If a tick happens and a message “done” is present, signed by \(\mathsf {sk} \), then reimburse all servers and set the state to \(\mathtt {init}\). Else, if a tick happens and a message “ok”, signed by \(\mathsf {sk} \), is present, then change state to \(\mathtt {ok1}\). Else, if no such message is present at the tick, then change to \(\mathtt {reimburse1}\).
-
\(\mathtt {ok1}\) Call Test Reveal on each \(\mathcal {F}_{\mathsf {Ident}}^{a,b}\). If no parties J are returned as cheaters by Test Reveal then check if for each \(\mathcal {P} _i\) and each \(\mathcal {F}_{\mathsf {Ident}}^{a,b}\) a message \(\mathbf {s}_i^{a,b}\) signed by \(\widehat{\mathsf {sk}}_{{i}}\) is present. If indeed, then verify the output for each \(\mathcal {F}_{\mathsf {Ident}}^{a,b}\) using Verify. If any of the aforementioned steps fails, then let \(I_1\) be the set of cheating servers. If \(I_1=\emptyset \) then change the state to \(\mathtt {ok2}\). If \(I_1\ne \emptyset \) then identify all the m clients by finding all messages of the form \((\mathcal {C} _j|\mathcal {L}_{{j}}^{\mathsf {src}}|\mathsf {am}_{j}^{\mathsf {src}}|\mathsf {vk} _{{j}}^{\mathsf {src}} |\mathsf {vk} _{{j}}^{\mathsf {ex}}|\mathcal {L}_{{j}}^{\mathsf {trg}}|\mathsf {vk} _{{j}}^{\mathsf {trg}} )\) that are signed by \(\mathsf {sk} \). Furthermore, identify all the transaction ids \(\mathtt {id}_j\) to burner addresses \(\mathsf {vk} _{{j}}^{\mathsf {ex}}\) signed by \(\mathsf {sk} \). For each party in \(I_1\) share the deposit among all m clients. Then return the deposit of the parties in \([n]\setminus I_1\) and change the state to \(\mathtt {init}\).
-
\(\mathtt {ok2}\) Compute for each \(\mathcal {L}_a\) in clear text the values \(\mathtt {id}_a,\mathsf {In}_a,\mathsf {Out}_a\) from the outputs of each \(\mathcal {F}_{\mathsf {Ident}}^{a,b}\) as well as the client registration data and transaction ids using \(\mathtt {makeTX}\). For each \(\mathcal {L}_a\) check if each \(\mathcal {P} _i\) sent shares of \(\mathsf {Sig}_a\) signed with \(\widehat{\mathsf {sk}}_{{i}}\). If so, then check that each share of \(\mathsf {Sig}_a\) is valid using \(\mathcal {F}_{\mathsf {TSig}}\) by running Share Combination. If any of the previous steps fails, then let \(I_2\) be the set of cheaters. If \(I_2=\emptyset \) then reimburse all \(\mathcal {P} _i\) with their deposit and change the state to \(\mathtt {init}\). Otherwise identify all the m clients by finding all client registration data and transaction ids to burner addresses signed by \(\mathsf {sk} \). For each party in \( I_2\) share the deposit among all m clients. Then return the deposit of the parties in \([n]\setminus I_2\) and change the state to \(\mathtt {init}\).
-
\(\mathtt {reimburse1}\) If a tick happens, then continue to \(\mathtt {reimburse2}\). Intuitively, during this step all clients that get reimbursed are already fixed so the servers will create the signatures on reimbursement transactions.
-
\(\mathtt {reimburse2}\) If a tick happens, consider all messages provided by each \(\mathcal {P} _i\) to \(\mathcal {F}_{\mathsf {SC}}\) that are of the form \((\mathcal {C} _j|\mathcal {L}_{{j}}^{\mathsf {src}}|\mathsf {am}_{j}^{\mathsf {src}}|\mathsf {vk} _{{j}}^{\mathsf {src}} |\mathsf {vk} _{{j}}^{\mathsf {ex}}|\mathcal {L}_{{j}}^{\mathsf {trg}}|\mathsf {vk} _{{j}}^{\mathsf {trg}} )\) that are signed by \(\mathsf {sk} \) as well as all messages \((\overline{\mathtt {id}}_j|\overline{\mathsf {In}}_j|\overline{\mathsf {Out}}_j,\mathsf {vk} _{{j}}^{\mathsf {src}} )\in \mathcal{M}\) (transaction ids) where \(\overline{\mathsf {In}}_j=(\mathsf {vk} _{{j}}^{\mathsf {src}} ,\mathsf {am}_{j}^{\mathsf {src}})\) and \(\overline{\mathsf {Out}}_j=(\mathsf {am}_{j}^{\mathsf {src}},\mathsf {vk} _{{j}}^{\mathsf {ex}})\). If there are multiple messages for \(\mathcal {C} _j\) then ignore \(\mathcal {C} _j\) Locally compute for each \(\mathcal {C} _j\) the transaction \(\mathsf {tx}_j\) to reimburse \(\mathcal {C} _j\). Therefore set \(\mathsf {In}_j=(\overline{\mathtt {id}}_j,\mathsf {am}_{j}^{\mathsf {src}})\), \(\mathsf {Out}_j=(\mathsf {am}_{j}^{\mathsf {src}},\mathsf {vk} _{{j}}^{\mathsf {src}} )\) and set \(\mathtt {id}_j\) as the hash of both. If each \(\mathcal {P} _i^j\) provided \(\rho _j^i\) then check using Share Combination on \(\mathcal {F}_{\mathsf {TSig}}\) that it outputs a valid signature \(\mathsf {Sig}_j\) on \(\mathtt {id}_j,\mathsf {In}_j,\mathsf {Out}_j\). If all such \(\mathsf {Sig}_j\) are valid signatures then reimburse all \(\mathcal {P} _i\) and set the state to \(\mathtt {init}\). If some signature shares are not valid or some shares \(\rho _j^i\) are not present on \(\mathcal {F}_{\mathsf {SC}}\) then let J be the set of cheaters. Reimburse all servers \([n]\setminus J\) and distribute the deposit of the parties of J evenly to all \(\mathcal {C} _j\). Then set the state to \(\mathtt {init}\).
Formalizing the Smart Contract. We use a combined smart contract and public ledger functionality \(\mathcal {F}_{\mathsf {SC}}\). It is an extension to \(\mathcal {F}_{\mathsf {BB}}\), tailored to be combined with an MPC protocol and similar to the functionality used in [5]. For technical reasons, \(\mathcal {F}_{\mathsf {SC}}\) has a hard-coded reference to the publicly verifiable MPC functionality \(\mathcal {F}_{\mathsf {Ident}}\) in order to be able to verify outputs. \(\mathcal {F}_{\mathsf {SC}}\) is described in Fig. 10 and Fig. 11 and considered as an ordinary UC functionality in our work. Again, this is due to technical limitations of UC, which would not make it possible for the simulator we construct in our security proof to equivocate the necessary outputs.
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Baum, C., David, B., Frederiksen, T.K. (2021). P2DEX: Privacy-Preserving Decentralized Cryptocurrency Exchange. In: Sako, K., Tippenhauer, N.O. (eds) Applied Cryptography and Network Security. ACNS 2021. Lecture Notes in Computer Science(), vol 12726. Springer, Cham. https://doi.org/10.1007/978-3-030-78372-3_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-78372-3_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-78371-6
Online ISBN: 978-3-030-78372-3
eBook Packages: Computer ScienceComputer Science (R0)