3
$\begingroup$

I read the paper "Provisions: Privacy-preserving proofs of solvency for Bitcoin exchanges" which is available for download on http://crypto.stanford.edu/~dabo/pubs/abstracts/provisions.html and have some questions about it. For discussing the single question I want to address here, having read the entire paper is not necessary as it is limited to what the authors describe in section 4.1.

The authors claim:

Now, to prove that $Z_\text{Assets}$ computed in (2) is a commitment to (a lower bound of) the exchange’s assets, the exchange proves knowledge of quantities:

$s_i \in \{0, 1\}$ and $v_i, t_i, \hat x_i \in \mathbb{Z}_q$

When you read the definitions of these symbols right before that claim, you notice (or at least I think I did) that none of these values require knowledge of any secrets to be computed.

$x_i$ describe the private keys, $y_i$ the public keys. As $y_i = g^{x_i} \forall i \in [1, n]$, knowing the values of $x_i$ is not required to commit to the values of $x_i \cdot s_i$ when using Pedersen commitments.

I don't see how any secrets were used when computing the values the exchange is going to prove ownership of and therefore not how proving knowledge of these values proves knowledge of the $x_i$. Yet in their protocol 1 (page 9), these values constitute the entire input of the prover (apart from the publicly available data on the blockchain).

As this is a published paper, I assume that they're right with that this is sufficient and I'm wrong. But what am I missing?

Improve this question
$\endgroup$
  • $\begingroup$ Regarding "..knowing the values of $x_i$ is not required to commit to the values of $x_i s_i$ when using Pedersen commitments." part: could you see that proving knowledge is not the same as creating commitment? Please note the name of section 4.1 is "$\Sigma$ protocol" and later at step 1(d) "Protocol 1: Privacy-preserving proof of assets", private key is used to create response of this protocol. $\endgroup$ – Vadym Fedyukovych Dec 3 '17 at 1:03
  • $\begingroup$ @VadymFedyukovych I don't see how step 1d in protocol 1 uses any private keys. Only $u_i$ and $c_i$ are used additionally to $s_i$, $v_i$, $t_i$, and $\hat x_i$. $u_i$ and $c_i$ are chosen randomly. Where do private keys come into play? $\endgroup$ – UTF-8 Dec 3 '17 at 13:19
  • $\begingroup$ Last response at 1(d) is $r_{\hat x_i} = u_i^{(4)} + c_i \hat x_i$, challenge is $c_i$ and secret proved is $\hat x_i = x_i s_i$. Private key is $x_i$, bitcoin public key is $y_i = g^{x_i}$. Still not sure about "Only $u_i$ and $c_i$ are used additionally to $s_i, v_i, t_i$, and $\hat x_i$" part. Let us consider this: to complete the protocol, in particular produce responses at 1(d), proving party must hold coins with private keys $x_i$. $\endgroup$ – Vadym Fedyukovych Dec 3 '17 at 14:30
  • $\begingroup$ @VadymFedyukovych Oh, you're right. I didn't remember the definition of $\hat x_i$ correctly. Want to collect the bounty? $\endgroup$ – UTF-8 Dec 3 '17 at 14:50
  • $\begingroup$ Thank you. Please feel free to update your question in case something is still unclear. $\endgroup$ – Vadym Fedyukovych Dec 3 '17 at 15:57
1
+50
$\begingroup$

Yes, $\Sigma$-protocol is described at section 4.1 of the paper referenced. This is a 3-move protocol, with the last message "response" computed from second message "challenge" and a secret. In particular, 4 responses are computed at step 1(d) of the protocol presented. Coin private keys $x_i$ held by exchange is the input for computing the last response, selected by binary mask $s_i \in \{0, 1\}: \; \hat x_i = x_i s_i$.

Improve this answer
$\endgroup$
0
$\begingroup$

The only thing this protocol proves is that the set of all "committed" account balances is equal to all outstanding liabilities(and their use of homomorphic encryption is questionable and not even thoroughly explained in the paper). The author has some rather demented ideas about what assets and liabilities actually mean historically or conventionally. An exchange could hypothetically include in that summation accounts controlled by an insider interest rather than a true customer, making the scheme completely pointless. There is no way for an individual to prove that the accounts included in that computation are held by other individuals like themselves with similar rights in the case of insolvency. Not surprising that the Bitcoin world has once again degraded the standards simultaneously in both finance and cryptography as well as attempting to draw attention to their work by staging contests reminiscent of a pie eating contest.

Improve this answer
$\endgroup$
  • $\begingroup$ the danger in this of course is they will use this pseudo science that it is ubiquitous in the Bitcoin world to "prove" an exchange is safe to use when in fact the method proves absolutely nothing. The paper is filled with your typical gratuitous use of scientific jargon and nomenclatures when in reality what they are claiming is fairly rote simple cryptographic usages. $\endgroup$ – Joshua Zeidner Dec 3 '17 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.