# ZK HACK: 1st puzzle write up
Last Tuesday was the start of [ZK HACK](https://www.zkhack.dev), a "7-week virtual event featuring weekly workshops and advanced puzzle solving competitions". All related to zero-knowledge proofs, as the name suggests. The talks of the first day were really good, and you can rewatch them [here](https://www.youtube.com/watch?v=Vaz4a_Vhntk&list=PLj80z0cJm8QFGB6AsiAG3EB06L7xr5S1c). At the end of the first day, a puzzle called [Let's hash it out](https://www.zkhack.dev/puzzle1.html) was released. This post about solving this puzzle.
## The puzzle
The puzzle is a [Github repo](https://github.com/kobigurk/zkhack-bls-pedersen) containing a Rust program. If you run it, it displays the following message:
> Alice designed an authentication system in which users gain access by presenting it a signature on a username, which Alice provided.
> One day, Alice discovered 256 of these signatures were leaked publicly, but the secret key wasn't. Phew.
> The next day, she found out someone accessed her system with a username she doesn't know! This shouldn't be possible due to existential unforgeability, as she never signed such a message.
> Can you find out how it happend and produce a signature on your username?
Looking at the code, it looks like there's indeed 256 signatures over 256 messages (that are just hexadecimal strings though, not usernames).
## The signature verification
The signatures are **BLS signatures** (a signature scheme that makes use of pairing and that [I've talked about it here](https://www.cryptologie.net/article/472/what-is-the-bls-signature-scheme/)).
Looking at the code, there's nothing fancy in there. There's a verification function:
```rust
pub fn verify(pk: G2Affine, msg: &[u8], sig: G1Affine) {
let (_, h) = hash_to_curve(msg);
assert!(Bls12_381::product_of_pairings(&[
(
sig.into(),
G2Affine::prime_subgroup_generator().neg().into()
),
(h.into(), pk.into()),
])
.is_one());
}
```
which pretty much implements the BLS signature verification algorithm to check that
$$
e(\text{sig}, -G_2) \cdot e(\text{h}, \text{pk}) = 1
$$
---
**Note**: if you read one of the linked resource, ["BLS for the rest of us"](https://hackmd.io/@benjaminion/bls12-381#BLS12-381-For-The-Rest-Of-Us), this should make sense. If anything is confusing in this section, spend a bit of time reading that article.
---
We know that the signature is simply the secret key $sk$ multiplied with the message:
$$\text{sig} = [\text{sk}]h$$
The public key is simply the secret key $\text{sk}$ hidden in the second group:
$$\text{pk} = [\text{sk}]G_2$$
So the check gives us:
$$
\begin{align}
& \;e([sk]h, -G_2) \cdot e(h, [sk]G2) \\
=& \;e(h, G_2)^{-\text{sk}} \cdot e(h, G_2)^\text{sk} \\
=& \;1
\end{align}
$$
## The hash to curve
Actually, the username is not signed directly. Since a signature is the first argument in the pairing it needs to be an element of the first group (so $[k]G_1$ for some value $k$).
To transform some bytes into a field element $k$, we use what's called a **hash-to-curve** algorithm. Here's what the code implements:
```rust
pub fn hash_to_curve(msg: &[u8]) -> (Vec<u8>, G1Affine) {
let rng_pedersen = &mut ChaCha20Rng::from_seed([
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1,
]);
let parameters = CRH::<G1Projective, ZkHackPedersenWindow>::setup(rng_pedersen).unwrap();
let b2hash = blake2s_simd::blake2s(msg);
(
b2hash.as_bytes().to_vec(),
CRH::<G1Projective, ZkHackPedersenWindow>::evaluate(¶meters, b2hash.as_bytes())
.unwrap(),
)
}
```
What I'm reading is that it:
1. initializes some collision-resistant hash function (CRH) from a hardcoded seed
2. uses the [BLAKE2](https://www.blake2.net) hash function to hash the username (`msg`) into 256 bits.
3. Uses the CRH to hash the BLAKE2 digest into a group element
Looking at CRH, it's simply a **Pedersen hashing** ([I've talked about that hash function here](https://www.cryptologie.net/article/528/what-is-an-inner-product-argument-part-1/)) that converts a series of bits $b_1, b_2, b_3, \cdots$ into
$$
[b_1]G_{1,1} + [b_2]G_{1, 2} + [b_3]G_{1, 3} + \cdots
$$
where the $G_{1,i}$ are curve points that belongs to the first group (generated by $G_1$) and derived randomly via the hardcoded seed (in a way that prevents anyone from guessing their discrete logarithm).
## What are we doing?
What are we looking for? We're trying to create a valid signature (maybe a signature forgery attack then?) on our own nickname (so more than just an existantial forgery, a chosen-message attack).
We can't change the public key (so no [rogue key attack](https://medium.com/@coolcottontail/rogue-key-attack-in-bls-signature-and-harmony-security-eac1ea2370ee)), and the message is fixed. This leaves us with the signature as the only thing that can be changed. So indeed, a **signature forgery attack**.
To recap, we have 256 valid signatures:
$$
\begin{cases}
e(\text{sig}_1, -G_2) \cdot e(h(m_1), \text{pk}) = 1\\
\vdots \\
e(\text{sig}_{256}, -G_2) \cdot e(h(m_{256}), \text{pk}) = 1\\
\end{cases}
$$
and we want to forge a new one such that:
$$
e(\text{bad_sig}, -G_2) \cdot e(h(\text{"my nickname"}), \text{pk}) = 1
$$
## Forging a signature
Reading on the aggregation capabilities of BLS, it seems like the whole point of that signature scheme is that we can just add things with one another. So let's try to think about adding signatures shall we?
What happens if I add two signatures?
$$
\begin{align}
&\; \text{sig}_1 + \text{sig}_2 \\
=&\; [\text{sk}]h_1 + [\text{sk}]h_2
\end{align}
$$
if only we could factor $sk$ out... but wait, we know that $h_1$ and $h_2$ are additions of the same curve points (by definition of the Pedersen hashing):
$$
\begin{align}
&\; \text{sig}_1 + \text{sig}_2 \\
=&\; [\text{sk}]h_1 + [\text{sk}]h_2 \\
=&\; [\text{sk}]([b_{1}]G_{1, 1} + [b_{2}]G_{1, 2} + [b_{3}]G_{1, 3} + \cdots)\\
&\; + [\text{sk}]([b'_{1}]G_{1, 1} + [b'_{2}]G_{1, 2} + [b'_{3}]G_{1, 3} + \cdots)
\end{align}
$$
where the $b_{i}$ (resp. $b'_{i}$) are the bits of $h_1$ (resp. $h_2$). So the added signature are equal to the signature of the added bitstrings:
$$
[b_{1} + b'_{1},\; b_{2} + b'_{2},\; b_{3} + b'_{3},\; \cdots]
$$
**We just forged a signature**! Now, that shouldn't mean much, because remember, these bits represent the output of a hash function and a hash function is resistant against pre-image attacks.
Wait a minute...
Our hash function is a collision-resistant hash function, but that's it.
## Linear combinations
OK, so we forged a signature by adding two signatures. But we probably didn't get what we wanted, what we wanted is to obtain the bits $\tilde{b}_1, \tilde{b}_2, \tilde{b}_3, \cdots$ that represent the hashing of my own username.
Maybe if we add more signatures together we can get? Actually, we can use all the signatures and combine them. And not just by adding them, we can take any linear combination (we're in a field, not constrained by 0 and 1).
So here's the system of equations that we have to solve:
$$
\begin{cases}
\tilde{b}_1 = x_1 b_1 + x_2 b'_1 + x_3 b''_1\\
\vdots \\
\tilde{b}_{256} = x_1 b_{256} + x_2 b'_{256} + x_3 b''_{256}\\
\end{cases}
$$
Note that we can see that as solving $xA = b$ where each row of the matrix $A$ represents the bits of a digest, and $b$ is the bitvector of my digest (the hash of my username).
Once we find that linear combinations, we just have to apply it to the signatures to obtain a signature that should work on my username :)
$$
\text{bad_sig} = x_1 \text{sig}_1 + x_2 \text{sig}_2 + x_3 \text{sig}_3 + \cdots
$$
## Coding the answer
Because I couldn't find a way to solve a system of equations in Rust, I simply extracted what I needed and used [Sage](https://www.sagemath.org) to do the complicated parts. Here's the Rust code that creates the matrix $A$ and the vector $b$:
```rust
// get puzzle data
let (_pk, ms, _sigs) = puzzle_data();
// here's my name pedersen hashed
let (digest_hash, _digest_point) = hash_to_curve("mimoo".as_bytes());
// what's that in terms of bits?
use ark_crypto_primitives::crh::pedersen::bytes_to_bits;
let bits = bytes_to_bits(&digest_hash);
let bits: Vec<u8> = bits.into_iter().map(|b| b as u8).collect();
// order of the subgroup of G1
println!("R = GF(0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001)");
// xA = b
print!("A = matrix(R, [");
for m in ms {
let (digest, _point) = hash_to_curve(&m);
let bits = bytes_to_bits(&digest);
let bits: Vec<u8> = bits.into_iter().map(|x| x as u8).collect();
print!("{:?}, ", bits);
}
println!("b = vector(R, {:?})", bits);
```
---
**Note**: the system of equation is over some field $R$. Why? Because eventually, the linear combination happens between curve points that are elements of the first group, generated by $G_1$, and as such are scalars that live in the field created by the order of the group generated by $G_1$.
---
In sage, I simply have to write the following:
```python
x = A.solve_left(b)
```
and back in Rust we can use these coefficients to add the different signatures with one another:
```rust
let mut bad_sig = G1Projective::zero();
for (coeff, sig) in coeffs.into_iter().zip(sigs) {
let coeff = string_int_to_field_el(coeff);
bad_sig += sig.mul(coeff);
}
// the solution
verify(pk, "mimoo".as_bytes(), bad_sig.into());
```
It works!

This is a list of terms that are often used throughout these general-purpose zero-knowledge proof systems. This is not meant to be a list that you should read through, but rather a reference if you sometimes encounter a term that you don't know about. In no order: constraint: generally, a constraint can be thought of as an equation where the lhs is whatever you want, and the right handside is zero. This way, the equation constraints the values of some variables. For example, $x(x-1) = 0$ constraints $x$ to be equal to 0 or 1. Sometimes, the term constraint refers to a [gate] in a circuit (for example, "this circuit has 30 constraints" really means "this cicruit has 30 gates") gate: usually used to refer to arithmetic gates, which allow you to do addition or multiplication of two inputs into one output. A circuit is a list of gates. The concept of arithmetic gate was generalized in plonk to a "generic gate" that is more versatile ($c_l \cdot l + c_r \cdot r + c_o \cdot o + c_m l \cdot r + c_c$), and in turboplonk with "custom gates" that are specialized for certain tasks (for example, hashing with poseidon, or doing parts of a scalar multiplication) row: a row is really the synonym for a gate. As circuits are usually layed out as tables where gates are listed as rows, we sometimes just say things like "this circuit has 30 rows". column: if you represent a circuit as a table, where [rows] are the [gates], then the columns are the variables used in those gates (for example, the witness variables $w_0, w_1, \dots$, the coefficients, etc.) Columns are usually interpolated into polynomials in the protocol. Some columns are secret (the 15 witness columns or kimchi), others are public (coefficients, selector polynomials). table: a circuit table, made out of rows (gates) and columns (variables). register: another term for a witness column.

7/5/2022Written for running in production kimchi (rust) zk-garage/ark-plonk (rust) dusk network plonk (rust) astar (rust) aztec network barretenberg (C++) ty plonk (rust) matterlabs based on bellman (rust) jellyfish (rust)

4/7/2022In 2020, plookup showed how to create lookup proofs. Proofs that some witness values are part of a lookup table. Two years later, an independent team published plonkup showing how to integrate Plookup into Plonk. This document specifies how we integrate plookup in kimchi. It assumes that the reader understands the basics behind plookup. Overview We integrate plookup in kimchi with the following differences: we snake-ify the sorted table instead of wrapping it around (see later) we allow fixed-ahead-of-time linear combinations of columns of the queries we make we only use a single table (XOR) at the moment of this writing

4/4/2022(photo by @micheile) Snapps are zero-knowledge smart contracts that will launch on Mina next year. You can learn more about them here. This tutorial teaches you how to write a tic-tac-toe game using snarkyjs, the official library to write snapps on Mina. Set up You can quickly create a project by using the Snapp CLI: $ npm install -g snapp-cli $ snapp project my-proj

1/13/2022
Published on ** HackMD**