For Privacy, Hunt The (zk-)Snark
For Privacy, Hunt The (zk-)Snark
How Does Peggy Prove She Knows The Solution to x²-x-42 To Victor, Without Showing The Answer?
Here is the demo of the code we will use in this article: [Link].
Lewis Carroll’s wrote a poem The Hunting of the Snark and which is extremely difficult to read:
So, let’s meet the Snark that does privacy: the zk-SNARK, and which is a puzzle which can only be solved by someone who knows a secret.
Zero-knowledge Proof
We give away too much of our data. Why should we give away our password every single time that we log into a system? Why can’t we just prove that we still know it? Thus Victor (the verify) can prompt Peggy (the prover) with a puzzle, and where she can show that she can solve it. This is the method that zero-knowledge proof (ZKP) uses to prove things. In this case, we will use the method used by zk-SNARKs to prove that we still know a secret. This method is used in blockchain methods to anonymise transactions. In this, we use the pairing property (e()) of:
First we have two elliptic curves (G1 and G2). Crypto pairs can then be used to prove that Peggy still knows a secret. For this we may have a quadratic equation of:
x²−x−42=0
Then, we will ask Peggy to prove that she knows the value of x. In this case, the solution is x=7 or x=−6. Now Peggy has to pass something to Victor to prove that she knows the solution, without giving away the value.
For this, we have a point on an elliptic curve of G, and use the pairing property of (and where e() is the pairing function):
and thus:
In pairing this then becomes:
and which becomes:
Peggy will then provide xG and Victor will check the pairings multiplied equals unity. If real-life x will be a large value, and it will not be possible to determine x from xG.
Coding
The outline coding using the library from the MIRACL library [here] is
A sample run is [here]:
x = -6
Eqn: x^2 - 1 x - 42
xG1: (047551bec1e6c80724663110982520fe8c88db44a4d42397ac219a1098d2763b,22936568b0f9da59025efcca3cbf0d40621e23ebd942985af7d213dcb427a922)
xG2: ([1ce69dc8742f5bb8a732dfe653515a23347fabdb638b00576008db7cb187f95a,01f33ef07a1fc794b14791741384fc9d0fcbe6abfa3570a374a8fb17d23657ed],[0b07db18cf5c53ba0897aedd52a96c638f466da17188b24ae0faf8011a0ff385,21bb29f6350e41819f2f1f959bde4decefed111f37767b5530cc898cf65f2adc])
xGa: ([061a10bb519eb62feb8d8c7e8c61edb6a4648bbb4898bf0d91ee4224c803fb2b,0516aaf9ba737833310aa78c5982aa5b1f4d746bae3784b70d8c34c1e7d54cf3],[230acce1d4506cbe1fa36ce996737de53763f5194241f6568d0f1f876e32d479,16683973c374eadb2ac709290a0c72d0b090f90028c636bc1cd2e51394c53178])
xGb: ([02347e5c2f0802a05e43267fe89de3dedc77d64556b495610913e6a767db7871,079078e9427f50798e62c1f804562a9326760f5d94f0a4206dd149d3f037d680],[0d250f7544ee22bc914c8d902b0a18c8a8613543217c01a07a3e73b380ddf93f,0c7cdecc7b14c33886d39fd4275f079c6a2d1639dc582262f231eece38b1987b])
Pair 1 - first 20 bytes: 0x006ce88251e092379d2d84308b8f76e908bf546e
Pair 2 - first 20 bytes: 0x05fb152b7cb6575543a9ac09ba4d8843da54f954
Pair 3 - first 20 bytes: 0x0b938a5c00b8130a459d660e1587afa15132a566
Pair Result - first 20 bytes: 0x0000000000000000000000000000000000000000
You have proven you know the value of x
If we try an incorrect value, such as x=5, we get a not proven result:
x = 5
Eqn: x^2 - 1 x - 42
xG1: (23edc69a751b579a14bc178029c6a6776a17fab345de03331bd905985b94daf0,215f727b315191c38806742b359c1aa7ebc35f65f5632eb8e9e6602f8890706b)
xG2: ([0b1d84f4d56634326a9c59f8161dd78be24b56b48a728012afea461f9191d674,21c158326bd5f7b921e22d5a528740d1fa40d4ad5924ab1d11c56a9f0a80b0c4],[0070bea4ee500dced8932db3b13554cdb986169e1a1180575562c32a6697afc4,20164c93784ca3c6b1db4fde1f24b8063a7a26b61ab465944ddffa3ce9cba6e5])
xGa: ([061a10bb519eb62feb8d8c7e8c61edb6a4648bbb4898bf0d91ee4224c803fb2b,0516aaf9ba737833310aa78c5982aa5b1f4d746bae3784b70d8c34c1e7d54cf3],[230acce1d4506cbe1fa36ce996737de53763f5194241f6568d0f1f876e32d479,16683973c374eadb2ac709290a0c72d0b090f90028c636bc1cd2e51394c53178])
xGb: ([02347e5c2f0802a05e43267fe89de3dedc77d64556b495610913e6a767db7871,079078e9427f50798e62c1f804562a9326760f5d94f0a4206dd149d3f037d680],[0d250f7544ee22bc914c8d902b0a18c8a8613543217c01a07a3e73b380ddf93f,0c7cdecc7b14c33886d39fd4275f079c6a2d1639dc582262f231eece38b1987b])
Pair 1 - first 20 bytes: 0x0992fbe1be5fa730dd57a1cb271d0b509d3bca98
Pair 2 - first 20 bytes: 0x2379e3f2a5512f8968af20800c70526b3a59897f
Pair 3 - first 20 bytes: 0x0b938a5c00b8130a459d660e1587afa15132a566
Pair Result - first 20 bytes: 0x0e7399bb64062eeab29b61a0067d9fd651f170b4
You have NOT proven you know the value of x
Conclusions
The development of blockchain has seen us move from the basic methods used in Bitcoin, where there is no real anonymity to the latest methods which preserve privacy with methods such as zk-SNARKs.
Here are more examples: