ZK-Hack is a 7-week long event that is still active right now. The event includes cool workshops to introduce people to the field of Zero-Knowledge Proofs and their uses in the real world! It also includes fun puzzles that help to really understand the given material by playing around with the underlying mathematical structures used in some ZK Proof systems (the event is hosted at https://www.zkhack.dev/). This post is a writeup of the second puzzle that I solved together with Matan and Elichai, and is a follow-up post to the solution of the first puzzle (available here).
If it's small, it should not be here
This is the clue we are given as the challenge begins. We are also referred to a paper on prime order subgroups. And as usual the documentation of the arkworks library.
The challenge is hosted on Github here.
First, let's talk about prime order subgroups and elliptic curve cofactors.
The Pohlig-Helman algorithm allows us to compute the discrete log of some element in an abelian group efficiently, given that its order has small prime factors. For full details read here. We will describe a simplified version to focus on the key points.
Given two group elements (using additive notation)
We know, by the Chinese Remainder Theorem, that if we can find
Now, we can compute
Now we use the Chinese Remainder Theorem to compute
Overall, the time complexity of solving the Discrete Log Problem becomes:
Elliptic Curves are complex objects with a lot of interesting properties, we will try here to focus specifically on the properties that are relevant to the solution of this challenge. Full details here.
We are working with the BLS12-381 Curve.
However these are actually 2 curves:
However, the orders of these groups have small prime factors (example below).
And we just learned why this is bad.
So what is usually done, is working in a subgroup on the curve that is of a large prime order (denote as
factor(E.order())
> 3 * 11^2 * 10177^2 * 859267^2 * 52437899^2 * 52435875175126190479447740508185965837690552500527637822603658699938581184513
# pick r = the large prime, so:
cofactor = 3 * 11^2 * 10177^2 * 859267^2 * 52437899^2
hex(cofactor)
> 0x396c8c005555e1568c00aaab0000aaab
And this is indeed the cofactor used for
Already we can develop some intuition (based on the clues given), that in the challenge we should be able to find an opportunity to compute the discrete log of some group element in a scenario that allows the Pohlig-Hellman algorithm to be utilized.
Alice has computed a trusted setup for a Groth16 proof scheme. She decided to use a 128-bit long secret, and she swears that she does not know the secret s needed to get this setup. The trusted setup is constructed as follows using two additional scalars α and β:
- [s^i] G1 for 0 ⩽ i ⩽ 62,
- [α s^i] G1 for 0 ⩽ i ⩽ 31,
- [β s^i] G1 for 0 ⩽ i ⩽ 31,
- [s^i] G2 for 0 ⩽ i ⩽ 31. Can you recover the secret anyway?
We then find the corresponding
To solve the challenge, all we have to do is find
Note that for
Keeping in mind our intuition for this challenge, it seems we must be able to utilize the Pholig-Hellman algorithm here in some way.
In order to use the Pohlig-Hellman algorithm we must first know the prime factorizations of the orders of both
factor(E.order())
> 3 * 11^2 * 10177^2 * 859267^2 * 52437899^2 * 52435875175126190479447740508185965837690552500527637822603658699938581184513
G1 = E(/*coordinates of ts1_0 in rust code*/)
factor(G1.order())
> 3 * 11 * 10177 * 859267 * 52437899 * 52435875175126190479447740508185965837690552500527637822603658699938581184513
Now we can see that the order of the subgroup generated by the point
We can now almost use the Pohlig-Hellman algorithm, the only problem is that
However, exactly as cofactors are used on curve points to project them into a "safe" subgroup of a large prime order, we can use the same method to project the points into an "unsafe" subgroup:
If we multiply
This means we can run the Pohlig-Hellman algorithm to find
s_times_g1 = E(/*coordinates of ts1_1 in rust code*/)
discrete_log(s_times_g1,G1,operation='+')
> 2335387132884273659
However,
We now come back to E2.order()
directly won't return a result anytime soon).
We know that the cofactor of 0x5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5
(taken from here)
We also know that the order of the "safe" subgroup of
factor(E2_cofactor)
> 13^2 * 23^2 * 2713 * 11953 * 262069 * 402096035359507321594726366720466575392706800671181159425656785868777272553337714697862511267018014931937703598282857976535744623203249
We see it's just
If we use the same projection trick as before and compute
However, it is not certain that
discrete_log(exp, base, 2713 * 11953 * 262069, operation='+')
> 6942769366567
Note that
We now have
crt([s_mod_n1, s_mod_nt2], [n1, nt2])
> 62308043734996521086909071585406
Yet again, note that
Well, if you think about it, knowing that
let (_ts1, _ts2) = puzzle_data();
let n1_times_nt2 = Fr::from_str("128602524809671824928355010578973").unwrap();
let s_tag = Fr::from_str("62308043734996521086909071585406").unwrap();
for k in 0..4000000 {
let s = n1_times_nt2*Fr::from(k) + s_tag;
if _ts1[0].mul(s) == _ts1[1] && _ts2[0].mul(s) == _ts2[1] {
println!("{}", s);
return;
}
}
After 893,754 iterations, this prints out:
0x56787654567876541234321012343210
In decimal: 114939083266787167213538091034071020048
We run:
let s = Fr::from_str("114939083266787167213538091034071020048").unwrap();
assert_eq!(_ts1[0].mul(s), _ts1[1]);
assert_eq!(_ts2[0].mul(s), _ts2[1]);
The asserts pass! We did it! 👏
Footnotes
-
Given a cyclic group $G$, $g$ a generator, and $g^x$, find $x$. ↩ ↩2
-
By Lagrange's theorem. ↩