Solving the Chicken & Hen Problem of MProve

Image courtesy:

MProve is the first proof of reserves for Monero. Monero 1 is a decentralized cryptocurrency, meaning it is secure digital cash operated by a network of users. It uses ring signatures, ring confidential transactions, and stealth addresses to hide the origins, amounts, and destinations of all transactions. Transactions on the Monero blockchain are untraceable. Read more about Monero here.

MProve leverages the ring signatures to generate a proof of reserves. In simple words, it considers an anonymity set Panon\mathcal{P}_{\text{anon}} which includes Pown\mathcal{P}_{\text{own}} the set of exchange-owned addresses. To generate MProve, an exchange selects Panon={P1,P2,,Pn}\mathcal{P}_{\text{anon}} = \{P_1, P_2, \dots, P_n\} from Monero blockchain. The commitment Ci=gyihaiC_i = g^{y_i} h^{a_i} for each PiPanonP_i \in \mathcal{P}_{\text{anon}}. The exchange defines the quantity CiC_i^{\prime} as follows Ci{gziif PiPowngziCiif PiPown C_i^{\prime} \coloneqq \begin{cases} g^{z_i} & \text{if } P_i \in \mathcal{P}_{\text{own}} \\ g^{z_i}C_i & \text{if } P_i \notin \mathcal{P}_{\text{own}} \end{cases} where ziz_i is randomly chosen from Zq\mathbb{Z}_q. Further, the exchange publishes ring signatures γi i{1,,n}\gamma_i \ \forall i \in \{1, \dots, n\} verifiable by the pair of public keys (Ci,CiCi)(C_i^{\prime}, C_i^{\prime} - C_i) and linkable ring signatures σi i{1,,n}\sigma_i \ \forall i \in \{1, \dots, n\} verifiable by the pair of public keys (Pi,CiCi)(P_i, C_i^{\prime} - C_i). Each σi\sigma_i contains key-images IiI_i. These key-images help detect collusion and double spending. Checking if the published key-image doesn’t match existing key-images on the blockchain ensures that the exchange is not using an already-spent address in its proof. Thus, a typical MProve is of the form ΠM={Pi,Ci,Ci,γi,σi}i=1n \Pi_{\text{M}} = \{ P_i, C_i, C_i^{\prime}, \gamma_i, \sigma_i \}_{i=1}^{n}

The problem is with the key-images IiI_i for ii s.t PiPownP_i \in \mathcal{P}_{\text{own}} which are a part of σi\sigma_i. Let’s say an exchange publishes a MProve proof at time t1t_1. Now if that exchange tries to spend from address PiPownP_i \in \mathcal{P}_{\text{own}} at some time t2>t1t_2 > t_1, the transaction also includes the same key-image IiI_i as the one present in the MProve proof. So, any observer will know that address PiP_i was owned by that exchange from the proof given at t1t_1. An obvious way out of this seems to change the way we define key-images in MProve. But then we won’t be able to detect double spending in that case. Revealing key-images seem to be unavoidable.

The way I thought I would solve this paradoxical situtation was to somehow prove that the key-images we generate do not use any of the private information of the existing spent addresses on the blockchain. Solving MProve drawback essentially means that we come up with an efficient proof of reserves which does two things:

  1. Checks for double spending using the already existing key images
  2. Ensure non-collusion between exchanges

Specifically, let PiP_i be a one-time address owned by the exchange with yiy_i as the secret key, and let IjI_j be a key-image from the blockchain, indicating that the funds from address PjP_j have already been spent, we have Pi=gxi, Ij=H(Pj)xj P_i = g^{x_i}, \ I_j = H(P_j)^{x_j}

If we prove, for each PiPownP_i \in \mathcal{P}_{\text{own}}, that the discrete-log of IjI_j w.r.t H(Pi)H(P_i) is not equal to the discrete-log of PiP_i w.r.t gGg \in \mathbb{G}, for each spent address PjP_j on the Monero blockchain, we are done. We can now have another definition of key-images in out proof of reserves. This fixes the paradoxical situation. Stay tuned to know how exactly we do it as we are in process of writing the manuscript of the protocol!