Breaking the binding: Attacks on the Merkle approach to prove liabilities and its applications. Issue 87 (November 2019)

• Record Type: Journal Article
• Authors: Hu, Kexin; Zhang, Zhenfeng; Guo, Kaiwen
• Is Part Of: Computers & security. Issue 87(2019)
• Publication Date: 2019-11
• Subjects: Summation Merkle tree -- Proof of liabilities -- Maxwell protocol -- Bitcoin exchanges -- The DAM scheme -- The Provisions scheme; Computer security -- Periodicals; Electronic data processing departments -- Security measures -- Periodicals; 005.805
• DOI: 10.1016/j.cose.2019.101585
• Languages: English
• ISSNs: 0167-4048

Abstract

Abstract: Proofs of liabilities are used for applications, function like banks or Bitcoin exchanges, to prove the sums of money in their dataset that they should owe. The Maxwell protocol, a cryptographic proof of liabilities scheme which relies on a data structure well known as the summation Merkle tree, utilizes a Merkle approach to prove liabilities in the decentralized setting, i.e., clients independently verify they are in the dataset without any trusted auditor's involvement. In this paper, we go into the Maxwell protocol and the summation Merkle tree. We formalize the Maxwell protocol and show it is not secure. We present an attack with which the proved liabilities are less than the actual values when adopting the Maxwell protocol. This attack can have significant consequences: A Bitcoin exchange controlling a total of n client accounts can present valid liabilities proofs including only one account balance. We suggest two improvements to deal with this problem, and we present a formal proof for the improvement that is closest in spirit to the Maxwell protocol. Moreover, we show the DAM scheme, a micropayment scheme of Zerocash which adopts the Maxwell protocol as a tool to disincentivize double/multiple spending, is vulnerable to a multi-spending attack. We show the Provisions scheme, which adopts the Maxwell protocol to extend its privacy-preserving proof of liabilities, is also infected by a similar attack.