1. bookVolume 2020 (2020): Issue 2 (April 2020)
Journal Details
First Published
16 Apr 2015
Publication timeframe
4 times per year
access type Open Access

A Tale of Two Trees: One Writes, and Other Reads

Published Online: 08 May 2020
Volume & Issue: Volume 2020 (2020) - Issue 2 (April 2020)
Page range: 519 - 536
Received: 31 Aug 2019
Accepted: 16 Dec 2019
Journal Details
First Published
16 Apr 2015
Publication timeframe
4 times per year

The Bitcoin network has offered a new way of securely performing financial transactions over the insecure network. Nevertheless, this ability comes with the cost of storing a large (distributed) ledger, which has become unsuitable for personal devices of any kind. Although the simplified payment verification (SPV) clients can address this storage issue, a Bitcoin SPV client has to rely on other Bitcoin nodes to obtain its transaction history and the current approaches offer no privacy guarantees to the SPV clients.

This work presents T3, a trusted hardware-secured Bitcoin full client that supports efficient oblivious search/update for Bitcoin SPV clients without sacrificing the privacy of the clients. In this design, we leverage the trusted execution and attestation capabilities of a trusted execution environment (TEE) and the ability to hide access patterns of oblivious random access machine (ORAM) to protect SPV clients’ requests from potentially malicious nodes. The key novelty of T3 lies in the optimizations introduced to conventional ORAM, tailored for expected SPV client usages. In particular, by making a natural assumption about the access patterns of SPV clients, we are able to propose a two-tree ORAM construction that overcomes the concurrency limitation associated with traditional ORAMs. We have implemented and tested our system using the current Bitcoin Unspent Transaction Output (UTXO) Set. Our experiment shows that T3 is feasible to be deployed in practice while providing strong privacy and security guarantees to Bitcoin SPV clients.


[1] Address reuse. https://en.bitcoin.it/wiki/Address_reuse. Accessed in Dec 2019.Search in Google Scholar

[2] Bitcoin core. https://bitcoin.org/en/bitcoin-core/. Accessed in Dec 2019.Search in Google Scholar

[3] Bitcoin Developer Reference. https://bitcoin.org/en/\developer-reference. Accessed in Dec 2019.Search in Google Scholar

[4] Bitcoin difficulty and network hash rate. https://bitcoinwisdom.com/bitcoin/difficulty. Accessed in Nov 2019.Search in Google Scholar

[5] Bitcoinj. https://bitcoinj.github.io/. Accessed in Dec 2019.Search in Google Scholar

[6] Dash. https://www.dash.org/. Accessed in Dec 2019.Search in Google Scholar

[7] Deterministic wallet. https://en.bitcoin.it/wiki/Deterministic_wallet. Accessed in Dec 2019.Search in Google Scholar

[8] Electrum Bitcoin Wallet. https://electrum.org/. Accessed in Dec 2019.Search in Google Scholar

[9] Json-roc-cpp. https://github.com/cinemast/libjson-rpc-cpp. Accessed in Dec 2019.Search in Google Scholar

[10] Key stone project. https://keystone-enclave.org/. Accessed in Dec 2019.Search in Google Scholar

[11] Litecoin. https://litecoin.org/. Accessed in Dec 2019.Search in Google Scholar

[12] Python-bitcoinlib. https://github.com/petertodd/python-bitcoinlib. Accessed in Dec 2019.Search in Google Scholar

[13] T3 prototype implementation, 2019. https://github.com/TEE-3/T3.Search in Google Scholar

[14] Adil Ahmad, Kyungtae Kim, Muhammad Ihsanulhaq Sarfaraz, and Byoungyoung Lee. OBLIVIATE: A data oblivious filesystem for intel SGX. In NDSS, 2018.10.14722/ndss.2018.23284Search in Google Scholar

[15] Sergei Arnautov, Bohdan Trach, Franz Gregor, Thomas Knauth, Andre Martin, Christian Priebe, Joshua Lind, Divya Muthukumaran, Dan O’Keeffe, Mark L. Stillwell, David Goltzsche, Dave Eyers, Rüdiger Kapitza, Peter Pietzuch, and Christof Fetzer. SCONE: Secure linux containers with intel SGX. In OSDI, 2016.Search in Google Scholar

[16] Andrew Baumann, Marcus Peinado, and Galen Hunt. Shielding applications from an untrusted cloud with haven. In OSDI, 2014.10.1145/2799647Search in Google Scholar

[17] Iddo Bentov, Yan Ji, Fan Zhang, Lorenz Breidenbach, Philip Daian, and Ari Juels. Tesseract: Real-time cryptocurrency exchange using trusted hardware. In CCS, 2019.10.1145/3319535.3363221Search in Google Scholar

[18] Ferdinand Brasser, Urs Müller, Alexandra Dmitrienko, Kari Kostiainen, Srdjan Capkun, and Ahmad-Reza Sadeghi. Software grand exposure: SGX cache attacks are practical. In WOOT, 2017.Search in Google Scholar

[19] Anrin Chakraborti and Radu Sion. ConcurORAM: High-throughput stateless parallel multi-client ORAM. In NDSS, 2019.10.14722/ndss.2019.23411Search in Google Scholar

[20] Chia che Tsai, Donald E. Porter, and Mona Vij. Graphenesgx: A practical library OS for unmodified applications on SGX. In USENIX ATC, 2017.Search in Google Scholar

[21] Stephen Checkoway and Hovav Shacham. Iago Attacks: Why the System Call API is a Bad Untrusted RPC Interface. SIGARCH Comput. Archit. News, 2013.10.1145/2451116.2451145Search in Google Scholar

[22] R. Cheng, F. Zhang, J. Kos, W. He, N. Hynes, N. Johnson, A. Juels, A. Miller, and D. Song. In EuroSP, 2019.Search in Google Scholar

[23] Victor Costan and Srinivas Devadas. Intel sgx explained. Cryptology ePrint Archive, Report 2016/086, 2016. https://eprint.iacr.org/2016/086.Search in Google Scholar

[24] Victor Costan, Ilia Lebedev, and Srinivas Devadas. Sanctum: Minimal hardware extensions for strong software isolation. In 25th USENIX Security Symposium, 2016.Search in Google Scholar

[25] Artur Czumaj. Lecture notes on approximation and randomized algorithms. http://www.ic.unicamp.br/~celio/peer2peer\/math/czumaj-balls-into-bins.pdf. Accessed in 2019.Search in Google Scholar

[26] Sergi Delgado-Segura, Cristina Pérez-Solà, Guillermo Navarro-Arribas, and Jordi Herrera-Joancomartí. Analysis of the bitcoin UTXO set. In BITCOIN, 2018.10.1007/978-3-662-58820-8_6Search in Google Scholar

[27] W. Diffie and M. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 1976.10.1109/TIT.1976.1055638Search in Google Scholar

[28] Saba Eskandarian and Matei Zaharia. Oblidb: Oblivious query processing for secure databases. PVLDB, 2019.10.14778/3364324.3364331Search in Google Scholar

[29] Bin Fan, Dave G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher. Cuckoo filter: Practically better than bloom. In Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies, CoNEXT ’14, 2014.10.1145/2674005.2674994Search in Google Scholar

[30] Arthur Gervais, Srdjan Capkun, Ghassan O. Karame, and Damian Gruber. On the privacy provisions of bloom filters in lightweight bitcoin clients. In ACSAC, 2014.10.1145/2664243.2664267Search in Google Scholar

[31] O. Goldreich. Towards a theory of software protection and simulation by oblivious rams. In STOC, 1987.10.1145/28395.28416Search in Google Scholar

[32] Danny Harnik, Eliad Tsfadia, Doron Chen, and Ronen I. Kat. Securing the storage data path with SGX enclaves. CoRR, abs/1806.10883, 2018.Search in Google Scholar

[33] Mike Hearn and Matt Corallo. Connection Bloom filtering, 2012.Search in Google Scholar

[34] Ryan Henry, Amir Herzberg, and Aniket Kate. Blockchain access privacy: Challenges and directions. IEEE Security & Privacy, 16(4):38–45, 2018.Search in Google Scholar

[35] Thang Hoang, Muslum Ozgur Ozmen, Yeongjin Jang, and Attila A. Yavuz. Hardware-Supported ORAM in Effect: Practical Oblivious Search and Update on Very Large Dataset. In PoPETs, 2019.10.2478/popets-2019-0010Search in Google Scholar

[36] Tyler Hunt, Zhiting Zhu, Yuanzhong Xu, Simon Peter, and Emmett Witchel. Ryoan: A distributed sandbox for un-trusted computation on secret data. In OSDI, 2016.Search in Google Scholar

[37] Angela Jäschke, Björn Grohmann, Frederik Armknecht, and Andreas Schaad. Short paper: Industrial feasibility of private information retrieval. In SECRYPT, 2017.10.5220/0006382003950400Search in Google Scholar

[38] Paul Kocher, Jann Horn, Anders Fogh,, Daniel Genkin, Daniel Gruss, Werner Haas, Mike Hamburg, Moritz Lipp, Stefan Mangard, Thomas Prescher, Michael Schwarz, and Yuval Yarom. Spectre attacks: Exploiting speculative execution. In S&P, 2019.10.1109/SP.2019.00002Search in Google Scholar

[39] Jaehyuk Lee, Jinsoo Jang, Yeongjin Jang, Nohyun Kwak, Yeseul Choi, Changho Choi, Taesoo Kim, Marcus Peinado, and Brent ByungHoon Kang. Hacking in darkness: Return-oriented programming against secure enclaves. In 26th USENIX Security Symposium, 2017.Search in Google Scholar

[40] Sangho Lee, Ming-Wei Shih, Prasun Gera, Taesoo Kim, Hyesoon Kim, and Marcus Peinado. Inferring fine-grained control flow inside SGX enclaves with branch shadowing. In 26th USENIX Security Symposium, 2017.Search in Google Scholar

[41] Joshua Lind, Oded Naor, Ittay Eyal, Florian Kelbert, Emin Gün Sirer, and Peter Pietzuch. Teechain: A secure payment network with asynchronous blockchain access. In SOSP, 2019.10.1145/3341301.3359627Search in Google Scholar

[42] Moritz Lipp, Michael Schwarz, Daniel Gruss, Thomas Prescher, Werner Haas, Anders Fogh, Jann Horn, Stefan Mangard, Paul Kocher, Daniel Genkin, Yuval Yarom, and Mike Hamburg. Meltdown: Reading kernel memory from user space. In 27th USENIX Security Symposium, 2018.Search in Google Scholar

[43] Sinisa Matetic, Karl Wüst, Moritz Schneider, Kari Kostiainen, Ghassan Karame, and Srdjan Capkun. BITE: Bitcoin lightweight client privacy using trusted execution. In 28th USENIX Security Symposium, 2019.Search in Google Scholar

[44] Mohsen Minaei, Pedro Moreno-Sanchez, and Aniket Kate. R3c3: Cryptographically secure censorship resistant rendezvous using cryptocurrencies. Cryptology ePrint Archive, Report 2018/454, 2018. https://eprint.iacr.org/2018/454.Search in Google Scholar

[45] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system,” http://bitcoin.org/bitcoin.pdf, 2008.Search in Google Scholar

[46] Olga Ohrimenko, Felix Schuster, Cedric Fournet, Aastha Mehta, Sebastian Nowozin, Kapil Vaswani, and Manuel Costa. Oblivious multi-party machine learning on trusted processors. In 25th USENIX Security Symposium, 2016.Search in Google Scholar

[47] Meni Orenbach, Pavel Lifshits, Marina Minkin, and Mark Silberstein. Eleos: Exitless os services for sgx enclaves. In EuroSys, 2017.10.1145/3064176.3064219Search in Google Scholar

[48] K. Qin, H. Hadass, A. Gervais, and J. Reardon. Applying private information retrieval to lightweight bitcoin clients. In 2019 Crypto Valley Conference on Blockchain Technology (CVCBT), 2019.10.1109/CVCBT.2019.00012Search in Google Scholar

[49] Ashay Rane, Calvin Lin, and Mohit Tiwari. Raccoon: Closing digital side-channels through obfuscated execution. In 24th USENIX Security Symposium, 2015.Search in Google Scholar

[50] Cetin Sahin, Victor Zakhary, Amr El Abbadi, Huijia Lin, and Stefano Tessaro. Taostore: Overcoming asynchronicity in oblivious data storage. In S&P, 2016.10.1109/SP.2016.20Search in Google Scholar

[51] E. B. Sasson, A. Chiesa, C. Garman, M. Green, I. Miers, E. Tromer, and M. Virza. Zerocash: Decentralized Anonymous Payments from Bitcoin. In S&P, 2014.10.1109/SP.2014.36Search in Google Scholar

[52] Sajin Sasy and Ian Goldberg. ConsenSGX: Scaling anonymous communications networks with trusted execution environments. PoPETs, 2019.10.2478/popets-2019-0050Search in Google Scholar

[53] Sajin Sasy, Sergey Gorbunov, and Christopher W. Fletcher. Zerotrace : Oblivious memory primitives from intel SGX. In NDSS, 2018.10.14722/ndss.2018.23239Search in Google Scholar

[54] Elaine Shi, T. H. Hubert Chan, Emil Stefanov, and Mingfei Li. Oblivious ram with o((logn)3) worst-case cost. In ASIACRYPT 2011.Search in Google Scholar

[55] Emil Stefanov, Marten van Dijk, Elaine Shi, Christopher Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas. Path oram: An extremely simple oblivious ram protocol. In CCS, 2013.10.1145/2508859.2516660Search in Google Scholar

[56] Florian Tramer and Dan Boneh. Slalom: Fast, verifiable and private execution of neural networks in trusted hardware. In International Conference on Learning Representations, 2019.Search in Google Scholar

[57] Muoi Tran, Loi Luu, Min Suk Kang, Iddo Bentov, and Prateek Saxena. Obscuro: A bitcoin mixer using trusted execution environments. In ACSAC, 2018.10.1145/3274694.3274750Search in Google Scholar

[58] Chia-Che Tsai, Kumar Saurabh Arora, Nehal Bandi, Bhushan Jain, William Jannen, Jitin John, Harry A. Kalodner, Vrushali Kulkarni, Daniela Oliveira, and Donald E. Porter. Cooperation and security isolation of library oses for multi-process applications. In EuroSys, 2014.10.1145/2592798.2592812Search in Google Scholar

[59] Wenhao Wang, Guoxing Chen, Xiaorui Pan, Yinqian Zhang, XiaoFeng Wang, Vincent Bindschaedler, Haixu Tang, and Carl A. Gunter. Leaky cauldron on the dark land: Understanding memory side-channel hazards in sgx. In CCS, 2017.10.1145/3133956.3134038640521430853868Search in Google Scholar

[60] Xiao Wang, Hubert Chan, and Elaine Shi. Circuit oram: On tightness of the goldreich-ostrovsky lower bound. In CCS, 2015.10.1145/2810103.2813634Search in Google Scholar

[61] Karl Wüst, Sinisa Matetic, Moritz Schneider, Ian Miers, Kari Kostiainen, and Srdjan Capkun. ZLiTE: Lightweight Clients for Shielded Zcash Transactions using Trusted Execution. In International Conference on Financial Cryptography and Data Security, 2019.10.1007/978-3-030-32101-7_12Search in Google Scholar

[62] Yuanzhong Xu, Weidong Cui, and Marcus Peinado. Controlled-Channel attacks: Deterministic side channels for untrusted operating systems. In S&P, 2015.Search in Google Scholar

[63] Fan Zhang, Ethan Cecchetti, Kyle Croman, Ari Juels, and Elaine Shi. Town crier: An authenticated data feed for smart contracts. In CCS, 2016.10.1145/2976749.2978326Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo