# Cairo Games Vol 2: Writeup

Here are my solutions to the second edition of the Cairo Games.

# Nu

This problem was pretty straightforward. We have to find to integers x,y<2^128 such that x*y=17 in the prime field used by Cairo. We can easily get such a pair as follows:

from sympy import divisors
P = 2**251 + 17 * 2**192 + 1
BOUND = 2**128
target = P + 17

for d in divisors(target):
n = target // d
if n < BOUND and d < BOUND:
break
ids.x = n
ids.y = d


# Pakhet

We get a graph on 18 vertices as an adjacency matrix. We then have to find a path of length 18 path in this graph such that

• assert [path] = [path + N_VERTICES]: The path is a cycle,
• check(path, aux=aux, graph=graph, n=N_VERTICES): This function takes the path as well as an auxiliary array aux and checks that path is a permutation of [0, 1, ..., 17].

These two checks imply that path is a Hamiltonian cycle of the graph. Finding an Hamiltonian cycle is hard in general, but for such a small graph we can find one easily. I used this implementation to find the cycle:

from hamiltonian import Graph

N = 18
graph = list(
reversed(
list(
map(
int,
bin(904711815024524574246580775193158565348810842345109828206640)[
2:
].zfill(200),
)
)
)
)
graph += list(
reversed(
list(
map(int, bin(1662189419663012728075783146332749833)[2:].zfill(N * N - 200))
)
)
)

g = Graph(N)
g.graph = [graph[i * N : i * N + N] for i in range(N)]

path = g.hamCycle()
aux = [18 - path.index(i) for i in range(18)]
print(graph)
print(path + [path[0]])
print(aux)


Note that this problem shows that STARKs contain NP, as finding Hamiltonian cycles is an NP problem.

# Seth

Let $H: \mathbb{F}\times \mathbb{F} \to \mathbb{F}$ be the Pedersen hash function and for an array $A$ of size $N$, let $H^*(A)=H(N, H(A_0,H(A_1,…)))$ be the hash chain function.

In this problem, we have to find an array $D$ of size 100, such that if we let $S_0 = H^*(D)$, we have for $i=0,1,…,99$: $$D_{r_i} = 0 \text{ if } 2|i \text{ else } H(x_i,x_i),$$

$$S_{i+1} = H(H(S_i, x_i), D_{r_i}),$$ where $r_i = S_i \wedge (2^{128}-1) \mod 100$, $\wedge$ being the bitwise AND.

My strategy to find such an array was the following:

1. Set $D_0 = H(c,c)$ and $D_i=0$ for $0<i<100$, with any $c$ such that $r_0\ne 0$. Setting $c=0$ works.
2. Find $x_i$ such that $r_{i+1}=0$.
3. Set $x_{i+1} = c$. Then $D_{r_{i+1}}=D_0=H(x_{i+1},x_{i+1})=H(c,c)$ holds, and $S_{i+2}=H(H(S_{i+1}, c), D_0)$. Go to step 2.

Note that in Step 3, if the new seed $S_{i+2}$ is such that $r_{i+2}=0$, the process fails. In this case, we can just try another initial seed $c$. If setting $c=0$, this never occurs though.

Here is the code to find the $x_i$’s:

from fast_pedersen_hash import pedersen_hash as H

def hash_chain(length, l):
if length == 1:
return H(length, l[0])
h = H(l[-2], l[-1])
for i in range(3, length + 1):
h = H(l[-i], h)
h = H(length, h)
return h

def get_seed(s):
low = s & ((1 << 128) - 1)
r = low % 100
if r == 0:
for j in range(10 ** 10):
ns = H(s, j)
ns = H(ns, 0)
nlow = ns & ((1 << 128) - 1)
nr = nlow % 100
if nr == 0:
s = ns
return s, j

SIZE = 100
def get(c):
data = [0 for _ in range(SIZE)]
h = H(c, c)
data[0] = h

s = hash_chain(SIZE, data)
preims = []
while True:
s, j = get_seed(s)
preims.append(j)
preims.append(0)
if len(preims) == SIZE:
break
s = H(s, 0)
s = H(s, h)

return data, preims

c = 0
while True:
try:
print(get(c))
break
except:
pass
c += 1


# Montu

This problem was very easy if you knew about FRI, but probably quite hard otherwise. I’ll assume knowledge of FRI. A good introduction can be found here.

We get an array $A_0$ of 8 field elements and a field element $G$ of multiplicative order 8. We then have to come up with a modified array $A$ such that the Hamming distance $d(A_0, A)=3$, i.e., $A$ is equal to $A_0$, except at 3 points, and such that $A$ is constant after two FRI reduction steps. Unless we’re cosmically lucky, the easiest way to achieve this is to set $A$ to be a low-degree extension of a degree 3 polynomial. In FRI jargon, we would say that we need to prove that $A_0$ is $\frac{3}{8}$-far from $RS[\langle G \rangle, \frac{1}{2}]$.

To find $A$, we iterate over all combinations of $A_0$ minus 3 points, and stop when we find one that interpolates a degree 3 polynomial:

P = 2**251 + 17 * 2**192 + 1
F = GF(P)
G = F(2804690217475462062143361339624939640984649667966511418446363596075299761851)
domain = [pow(G, i) for i in range(8)]

L = [2760163267763136926307712447289333015931143661720962520709479367174330989984,
620345510678501588305616341951109830750033614090225920347864657883483407165,
3181959697776337130511545402257206919343979808211484609881516936335798865334,
1830152343057623004121086982129442788610913917055044983876581372969127139593,
3553572895696142252358926310847411672039878792883770142922873977486098926969,
2462248735454554379268841047904517280521029943202779759148500485193601548624,
792090413233267968557021563731724001464889355006703125688313681478453789157,
1348005446214778757482455457529115254152067928062775094282398020688141612139]

R.<x> = F[]

for t in combinations(range(8), 5):
l = [A[i] for i in t]
d = [domain[i] for i in t]
P = R.lagrange_polynomial(zip(d, l))
if P.degree()==3:
LDE = [P(x) for x in domain]
print(LDE)
break


# Amun

This problem was harder and more contrived than the others. The gist of it is as follows:

1. We are given six 48-permutations $\sigma_0,…,\sigma_5\in S_{48}$.
2. We have to find an array $A$ of length 48 that satisfies some checks $H^* (A[i_0:i_1]) = h_i$, where $H^*$ is the hash chain function already seen in Seth, and $i_0, i_1, h_i$ are given indices and hashes.
3. We have to find a word in $\sigma \in \langle \sigma_0, …, \sigma_5\rangle$ (taken as a monoid, so inverse permutations are not allowed) such that $\sigma \cdot A = [0,…,0,1,…,1,…,5,…,5]$, i.e., the array $B$ of size 48 with $B_i = \left\lfloor{i/8}\right \rfloor$.

Step 2 can be solved by brute-forcing some of the hashes $h_i$ and using the fact that $A$ must be a permutation of $B$.

My solution to Step 3 is very brute-forcy, so I guess that there probably is a much cleaner way. Here it is anyway. We note that $\sigma_i^4=1$ for all $0\leq i<6$ and that $\sigma_0\sigma_5=\sigma_5\sigma_0$, $\sigma_1\sigma_3=\sigma_3\sigma_1$, $\sigma_2\sigma_4=\sigma_4\sigma_2$. These relations mean that when searching for $\sigma$, we can add the following rules:

• No $\sigma_i$ appears more than three time,
• $\sigma_0$ always appear before $\sigma_5$,
• $\sigma_1$ always appear before $\sigma_3$,
• $\sigma_2$ always appear before $\sigma_4$. These reduce the search space quite substantially. Then I used an $A^ *$-search using the following heuristic $$h(\sigma) = d(\sigma\cdot A, B) - \alpha |\sigma|,$$ where $d$ is the Hamming distance, $|\sigma|$ is the word length of $\sigma$, i.e., the number of $\sigma_i$’s in the product to get $\sigma$, and $\alpha\in \mathbb{R^+}$ is an hyperparameter. The idea is to optimize for distance to the desired array $B$, while trying to keep the words small.

Using a grid-search on $\alpha$, I finally found a valid $\sigma$ of word length 74.

Here is my uncleaned $A^*$-search code:

use std::collections::BinaryHeap;

const DATA: [usize; 120] = [
0, 2, 4, 6, 1, 3, 5, 7, 8, 32, 24, 16, 9, 33, 25, 17, 10, 34, 26, 18, 24, 26, 28, 30, 25, 27,
29, 31, 4, 32, 44, 20, 3, 39, 43, 19, 2, 38, 42, 18, 16, 18, 20, 22, 17, 19, 21, 23, 6, 24, 42,
12, 5, 31, 41, 11, 4, 30, 40, 10, 8, 10, 12, 14, 9, 11, 13, 15, 0, 16, 40, 36, 7, 23, 47, 35,
6, 22, 46, 34, 32, 34, 36, 38, 33, 35, 37, 39, 2, 8, 46, 28, 1, 15, 45, 27, 0, 14, 44, 26, 40,
42, 44, 46, 41, 43, 45, 47, 22, 30, 38, 14, 21, 29, 37, 13, 20, 28, 36, 12,
];

const RES: [usize; 48] = [
5, 0, 0, 3, 3, 1, 4, 0, 4, 1, 0, 4, 0, 5, 4, 2, 3, 4, 0, 1, 5, 5, 1, 3, 2, 2, 1, 0, 1, 2, 2, 5,
2, 4, 1, 1, 3, 2, 2, 3, 4, 4, 3, 0, 5, 5, 5, 3,
];

fn trans(s: [usize; 48], se: [usize; 48], x: usize) -> ([usize; 48], [usize; 48]) {
let mut state = s;
let mut seen = se;
for inc in [0, 4, 8, 12, 16].iter() {
let i = 20 * x + inc;
let ds = &DATA[i..i + 4];
let mut nstate = state;
for j in 0..4 {
seen[ds[j]] = 1;
nstate[ds[j]] = state[ds[(j + 3) % 4]];
}
state = nstate;
}
(state, seen)
}

fn ev(s: [usize; 48], seen: [usize; 48]) -> usize {
(0..48).filter(|&i| seen[i] == 1 && s[i] == (i / 8)).count()
}

fn astar(scale_len: usize) {
let mut best = 0;
let init = RES;
let mut q = BinaryHeap::new();
q.push((ev(init, [0; 48]), init, [0; 48], vec![]));

loop {
let (_e, s, seen, l) = q.pop().unwrap();
for i in 0..6 {
if l.len() > 0 {
let ll = *l.last().unwrap();
if ll == i {
continue;
}
if ll == 3 && i == 1 {
continue;
}
if ll == 4 && i == 2 {
continue;
}
if ll == 5 && i == 0 {
continue;
}
}
let mut ns = s;
let mut nseen = seen;
for j in 1..4 {
let r = trans(ns, nseen, i);
ns = r.0;
nseen = r.1;
let ee = ev(ns, nseen);
if best > 30 && ee < 25 {
continue;
}
if best > 40 && ee < 27 {
continue;
}
let e = ee - (scale_len * l.len()) / 10;
let mut nl = l.clone();
for _ in 0..j {
nl.push(i);
}
if ee == 48 {
println!("Sols is: {:?}", nl);
return;
}
if ee > best {
best = ee;
}
q.push((e, ns, nseen, nl));
}
}
}
}

fn main() {
astar(13);
}