# Lack of usage of secrets in ZK Bitcoin ownership proof

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?

• 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. – Vadym Fedyukovych Dec 3 '17 at 1:03
• @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? – UTF-8 Dec 3 '17 at 13:19
• 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$. – Vadym Fedyukovych Dec 3 '17 at 14:30
• @VadymFedyukovych Oh, you're right. I didn't remember the definition of $\hat x_i$ correctly. Want to collect the bounty? – UTF-8 Dec 3 '17 at 14:50
• Thank you. Please feel free to update your question in case something is still unclear. – Vadym Fedyukovych Dec 3 '17 at 15:57

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$.