Cryptology ePrint Archive: Report 2018/1139

Breaking the Binding: Attacks on the Merkle Approach to Prove Liabilities and its Applications

Kexin Hu and Zhenfeng Zhang and Kaiven Guo

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 with no trusted auditor. 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 using the Maxwell protocol are less than the actual value. 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 in its dataset. We suggest two improvements to the Maxwell protocol and the summation Merkle tree, and 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 an multi-spending attack. We show the Provisions scheme, which adopts the Maxwell protocol to extend its privacy-preserving proof of liabilities scheme, is also infected by a similar attack.

Category / Keywords: applications / proof of liabilities, Maxwell protocol, summation Merkle tree, the DAM scheme, the Provisions scheme

Date: received 22 Nov 2018

Contact author: hukexin at tca iscas ac cn

Available format(s): PDF | BibTeX Citation

Version: 20181129:150929 (All versions of this report)

Short URL: ia.cr/2018/1139


[ Cryptology ePrint archive ]