2
$\begingroup$

I am working in the secp256k1 elliptical curve, though I suspect this would apply to any elliptical curve. I have a Pedersen Commitment of the $x$ and $y$ coordinates in some discrete log scheme with generators $g$ and $h$. The point described by $x$ and $y$ is equal to $G^n$, where $G$ a public generator and $n$ is a secret (using exponentiation to represent point scalar multiplication on elliptic curves). Is there a method to get from the $g^x h^{r_1}$ and $g^y h^{r_2}$ to $G^n H^{r_3}$, where $H$ is a second generator in the curve and all $r$ values are secret random numbers, using Zero Knowledge Proofs where needed? A method in the other direction, going from the commitment of $n$ to a commitment of the two coordinates $x$ and $y$ would also be applicable. I haven't been able to find such a proof in my research and I have not been able to think about how to create one.

My goal is to design a Zero Knowledge Proof of Knowledge of the private key associated with a public key which has been hashed (using the Bitcoin address hash) in such a way that the only public information is the environments (generators, settings, etc) and the result of the hash function, as well as all associated functions like the Bitcoin Hash. This proof can be used to prove ownership of a non-spending Bitcoin account without revealing the public key. If someone has done this, then I guess the question is moot and I will reference an applicable paper instead of designing it myself, thus a link to any such paper would also be an acceptable answer to this question. Unfortunately, I have not seen such a paper myself in my research.

EDIT:

I should also note that before the commitments of the coordinates were in the form $g^x h^{r_1}$ and $g^y h^{r_2}$, they were two lists of bitwise commitments that were homomorphically combined to become $g^x h^{r_1}$ and $g^y h^{r_2}$. I did not lose those commitments, so they are available. It was probably a mistake to suggest combining them, as it could introduce problems in performing operations on them due to differing orders between groups.

Improve this question
$\endgroup$
1
  • $\begingroup$ I should clarify: Any proof that proves that $g^x \cdot h^{r_1}$ and $g^y\cdot h^{r_2}$ corresponds with $G^n \cdot H^{r_3}$ would apply here. $\endgroup$
    – Zarquan
    Commented Oct 31, 2017 at 17:19

4 Answers 4

Reset to default
1
$\begingroup$

It's quite useful that you included yuor actual goal in the question, to avoid the XY problem.

My goal is to design a Zero Knowledge Proof of Knowledge of the private key associated with a public key which has been hashed (using the Bitcoin address hash) in such a way that the only public information is the environments (generators, settings, etc) and the result of the hash function, as well as all associated functions like the Bitcoin Hash.

If we assume that pulic parameters are known by everyone, you only give the verifier a single piece of information: The hash-value of the public key. And here it is quite irrelevant what kind of public key is used - you need a ZK proof for a preimage under the according hash function.

I am not sure what you mean with "all associated functions like the Bitcoin Hash". But the goal here seems to be keeping the identity of the Bitcoin account secret, so I guess that additional information does not reveal the public key either.

This proof can be used to prove ownership of a non-spending Bitcoin account without revealing the public key.

Actually, this is probably wrong. The reason for this is, that knowledge of a preimage under a hash function does not guarantee that the preimage is actually a valid Bitcoin account. For that you would need a different ZK proof, in which the verifier actually needs the according public key.

In the setting of Bitcoins, I think your agoal is not achievable. What you actually would need is a proof for membership of a group, e.g. the group of owners of valid accounts, and I can imagine that being possible - if the system is designed that way. This would be similar to group signatures, etc. But without an according setup, I don't see any way to achieve your goal.

Regarding your idea with the commitments and the EC public key:

You have two Pedersen commitments $a = g^xh^{r_1}, b = g^yh^{r_2}$ and then $c = G^nH^{r_3}$, which is like a Pedersen commitment but not in a prime order group but an elliptic curve.

Now, regardless of what $x$ and $y$ actually are, $a$ and $b$ could potentially be any element of the group, because the Pedersen commitments are perfectly hiding. So maybe you can generate $G^nH^{r_3}$ somehow from $a$ and $b$, but that will definately reveal $n$ itself and it has actually no relation to $x$ or $y$.

Improve this answer
$\endgroup$
12
  • $\begingroup$ I assure you I can hide $n$ in a satisfactory way with my preliminary solution, though the protocol would be extremely expensive. Any problem in NP is possible in Zero Knowledge and this is certainly an NP problem. $\endgroup$
    – Zarquan
    Commented Nov 3, 2017 at 16:40
  • $\begingroup$ @Zarquan Even if you manage to hide $n$ by using a general MPC protocol, it has no meaning. The relation you need does not exist - the zero knowledge proof does actually not prove anything. Oh, and your circuit is not polynomially sized if you consider $n$ as input and not hard-coded into the circuit. $\endgroup$
    – tylo
    Commented Nov 3, 2017 at 16:49
  • $\begingroup$ @Zarquan Regardless, on some parts I can only speculate what you mean, because you have no clear definitions of who knows what in the beginning, the algebraic structures and which relation should be proven in ZK. Without that, it's just guesswork about soundness, zero knowledge and what information is actually kept private (not the same as zero-knowledge). $\endgroup$
    – tylo
    Commented Nov 3, 2017 at 16:55
  • 1
    $\begingroup$ I think I am fairly clear, both parties have the commitments. Only the prover knows $x$, $y$, $n$, and $r$ values. The proof proves knowledge of $n$. I later say that there already exists a list bitwise commitments representing $x$ and $y$ as well (as that is the format you would give to a hash). The commitments can be in which ever secure discrete log scheme makes this most simple. In my solution, you would want to use elliptic curves because that is fastest for this kind of thing. You can run any circuit using commitment and zero knowledge proofs, though it may be inefficient. $\endgroup$
    – Zarquan
    Commented Nov 3, 2017 at 20:02
  • 1
    $\begingroup$ How does it not prove anything? I proved that I could take $G$, multiply it by a secret $n$ (creating commitments following the circuit w/proofs), and get a point represented by the committed coordinates $x$ and $y$. This must mean that I know $n$ from $nG$. It is like proving knowledge of the contents of a Pedersen Commitment, except convoluted because of the incompatible representations. This is a Zero Knowledge Circuit, where you create a boolean circuit and prove that with your committed inputs, you can get the committed outputs. Recall that bitwise $x||y$ is the preimage of a public hash. $\endgroup$
    – Zarquan
    Commented Nov 3, 2017 at 20:23
1
$\begingroup$

My goal is to design a Zero Knowledge Proof of Knowledge of the private key associated with a public key which has been hashed (using the Bitcoin address hash) in such a way that the only public information is the environments (generators, settings, etc) and the result of the hash function, as well as all associated functions like the Bitcoin Hash.

This is my attempt to reconcile bits and pieces stated already, and to suggest some known results. This is not a complete answer. This question shows diversity of points of view, indicating potential for interesting research.

The hash destroys the information in the public key.

It would be great to follow definition and refer to the general theorem: Oded Goldreich, Silvio Micali, Avi Wigderson, "Proofs that Yield Nothing But Their Validity for All Languages in NP Have Zero-Knowledge Proof Systems". In this particular case, hash is an instance and private key is a witness certifying language membership. Extractor algorithm is introduced at Mihir Bellare, Oded Goldreich, "On Defining Proofs of Knowledge".

With two relations, public key might be considered an intermediary: preimage of the hash and result of double-and-add algorithm.

I don't think this works, because the EC skalar multiplication (usually add-and-double is used) reveals n.

In particular, double is followed by add for "1" bits of private key. One would express this loop as \begin{equation} (PrivKeyBit == 0 \land pointX == DoubleX \land pointY == DoubleY) \lor (PrivKeyBit == 1 \land pointX == DoubleAddX \land pointY == DoubleAddY) \end{equation} One could implementing this as a $\Sigma$-protocol with challenges and responses, following Ronald Cramer, Ivan Damgard, Berry Schoenmakers, "Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols" for OR proof. Alternatively, one could do this part with a polynomial quadratic in challenge of Verifier, as shown at a related question and a protocol for proving Hamiltonian cycle. Let $B(z)$ be a linear polynomial such that degree-1 coefficient is the bit of private key. Then Pedersen commitment to $x$-coordinate would be verified with degree-2 coefficient of polynomial \begin{gather} (z - B(z)) D(z) + B(z) A(z) \end{gather} where $D(z)$ and $A(z)$ are linear polynomials (Schnorr-like responses) with degree-1 coefficients $DoubleX$ and $DoubleAddX$. For a valid $B()$ one would require $B(z)(B(z) - z)$ to be a linear (zero degree-2 coefficient) polynomial. One would complement this with equations to verify $DoubleX$ and $DoubleAddX$ against coordinates from previous run of the cycle. One could produce a linear combination of equations corresponding to all 256 cycles to reduce verification cost.

Knowledge of hash preimage could be proven with snarkfront or related tools: libsnark, pinocchio, pepper. This technique might be yet another alternative replacing verification outlined above. Please note "knowledge of exponent" assumption would not result in any explicit extractor algorithm.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry for my delayed response. I like what I am seeing here. How do would you handle infinity in this system though? Because the beginning state is INF (which has no $x$ or $y$ values) in this algorithm unless you assume that the most significant bit is 0. My instinct is to act like the bit at 2^256 (a nonexistent bit) is 1 and then cancel it out at the end, which would be annoying, but it would be better than adding something like "OR all previous bits from $n$ are 0 AND the current bit from $n$ is 1 AND $pointX$ AND $pointY$ correspond with $G$." at the end of each bit. $\endgroup$
    – Zarquan
    Commented Jan 22, 2018 at 7:50
  • $\begingroup$ Projective coordinates $(X, Y, Z)$ might be handy here, at the cost of 3-vs-2 field elements in the representation. $\endgroup$
    – Vadym Fedyukovych
    Commented Jan 22, 2018 at 8:59
0
$\begingroup$

I have a preliminary process that would sort of work essentially by brute force, but I suspect it would be unreasonably expensive. I would take $G$ and convert it in to two sets of bit commitments ($G_x$ and $G_y$) and run the EC scalar multiplication times $n$ without revealing $n$ and proving this $n$ is the same as from $G^n H^{r_3}$, which can be done. I then show that the result $x$ and $y$ from this point are the same as the $x$ and $y$ from the $g^x h^{r_1}$ and $g^y h^{r_2}$. I would like to find something better, but this would work.

EDIT 1: This multiplication operation can be done in O(log($t$)) time, where $t$ is the number of bits in $n$. However, $t$ is always equal to 256, as I do not wish to leak any information about $n$, and the maximum value for $n$ in the curve secp256k1 is $q-1$, where $q$ is the order and $q$ has 256 bits.

Improve this answer
$\endgroup$
10
  • $\begingroup$ For the time being, I will leave this question open. If someone posts a better solution, I will happily mark that answer as the best answer. $\endgroup$
    – Zarquan
    Commented Oct 31, 2017 at 17:32
  • $\begingroup$ Double-and-add is an option for scalar multiplication, with logarithmic complexity. Did you mean using libsnark? $\endgroup$
    – Vadym Fedyukovych
    Commented Nov 1, 2017 at 22:34
  • $\begingroup$ That is the algorithm I was intending to implement in the circuit. I don't think libsnark has this exact functionality I am looking for because I am taking about implementing the point scalar multiplication on a committed bitwise representation of the coordinates $G_x$ and $G_y$ rather than an actual point object to show that the result is equivalent to the commitments $g^x h^{r_1}$ $g^y h^{r_2}$, essentially doing the point scalar multiplication manually. This operation is odd, so I doubt that this is in libsnark. If they do, I would be very happy to know. $\endgroup$
    – Zarquan
    Commented Nov 1, 2017 at 23:42
  • $\begingroup$ Commitments to coordinates and to index (logarithm) $n$ suggest groups of different orders, that reminds pairs of MNT curves mentioned in libsnark. $\endgroup$
    – Vadym Fedyukovych
    Commented Nov 3, 2017 at 9:25
  • 1
    $\begingroup$ I should add that the Prover knows the hash, the public key, the private key, $n$, $x$, $y$, the generators $G$ and $H$, and the curve. The Verifier only knows the hash, the generators, and the curve. $\endgroup$
    – Zarquan
    Commented Dec 4, 2017 at 22:22
-2
$\begingroup$

the proof that you have knowledge of the private key is the signature.

you're basically asking if the hashed public key(ie. the Bitcoin Address) can be used to verify a signature and the answer is no. The hash destroys the information in the public key.

btw- you can prove ownership of a non-spending bitcoin account by endorsing a plaintext and publishing the signature. The standard Bitcoin wallet has this feature last I checked.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ One could define an NP language of (verifiable signature, hash) tuples with public key being a witness. $\endgroup$
    – Vadym Fedyukovych
    Commented Dec 3, 2017 at 18:55
  • $\begingroup$ explain how you would use this to accomplish verification using the hash of a public key. $\endgroup$
    – Joshua Zeidner
    Commented Dec 3, 2017 at 19:08
  • 1
    $\begingroup$ ..exactly like any other witness: as a private input to a proving protocol. $\endgroup$
    – Vadym Fedyukovych
    Commented Dec 3, 2017 at 19:15
  • $\begingroup$ that's not an answer $\endgroup$
    – Joshua Zeidner
    Commented Dec 3, 2017 at 19:16
  • 1
    $\begingroup$ I should refer to a general theorem that any NP relation can be verified in zero knowledge. It might be not very efficient, not elegant, not publishable, but it is doable. $\endgroup$
    – Vadym Fedyukovych
    Commented Dec 3, 2017 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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