Variance: Secure Two-Party Protocol for Efficient Asset Comparison in Bitcoin

Secure multiparty protocols are useful tools for parties wishing to jointly compute a function while keeping their input data secret. The millionaires' problem is the first secure two-party computation problem, where the goal is to securely compare two private numbers without a trusted third-party. There have been several solutions to the problem; however, these solutions are either insecure in the malicious model or cannot verify the validity of inputs. In this paper, we introduce Variance, a privacy-preserving two-party protocol for solving Yao's millionaires' problem in a Bitcoin setting, in which each party controls several Bitcoin accounts (single and multi signature addresses) and they want to find out who owns more bitcoins without revealing (1) how many accounts they own or the addresses associated with their accounts, (2) the balance of any of their accounts, and (3) their total wealth of bitcoins while assuring the other party that they are not claiming more bitcoin than they possess. We utilize zero knowledge proofs to provide a solution to the problem, and subsequently prove that Variance is secure against active adversaries in the malicious model.