Below you will find the solutions to the puzzles presented in the second volume of the Cairo Games. If you are still working on solving the puzzles – major spoilers ahead!
Nu
#########################################################################
# SPOILER ALERT #
# #
# This is the solution to the puzzle. #
# You can find the puzzle without its solution in the Cairo Playground. #
#########################################################################
# Program hash: 0x0603aa817aa054d58beb522a1e17286e92afbce15009893cbd81d22b7bdc3f56.
# Prove that the prime number 17 is in fact composite!
# Well, 17 is not really a composite number, so there must be a bug in the program.
# The bug turns out to be an integer overflow that occurs when x and y are multiplied.
# assert_nn() implies that both x and y are less than 2^128.
# On the other hand the product is computed modulo the field's size,
# which is P=2^251 + 17*2^192 + 1.
# Since this number is less than 2^128 * 2^128, we have a potential overflow.
# Therefore, if the product x*y is in fact 17 + P (rather than 17), the code will succeed.
#
# Computing the factorization of 17 + P (which *is* composite) gives:
# 2 * 11 * 137659 * 1991573 * 109785357751 * 576309240307649 *
# 9482118669354530065856070474433091563.
# Splitting it to:
# x = 2 * 9482118669354530065856070474433091563,
# y = 11 * 137659 * 1991573 * 109785357751 * 576309240307649,
# solves the puzzle.
#
# When you write real Cairo code, you should make sure computations do not overflow.
# In this example, a simple way to achieve it is to enforce a stricter bound on
# x and y. For example, that both of them are less than 2^64.
%builtins output range_check
from starkware.cairo.common.math import assert_nn
func main(output_ptr : felt*, range_check_ptr) -> (output_ptr : felt*, range_check_ptr):
alloc_locals
local x
local y
%{
ids.x = 2 * 9482118669354530065856070474433091563
ids.y = 11 * 137659 * 1991573 * 109785357751 * 576309240307649
# Output the user's public key.
memory[ids.output_ptr] = 0x1234
%}
assert_nn{range_check_ptr=range_check_ptr}(x - 2)
assert_nn{range_check_ptr=range_check_ptr}(y - 2)
assert x * y = 17
return (output_ptr=output_ptr + 1, range_check_ptr=range_check_ptr)
end
Pakhet
#########################################################################
# SPOILER ALERT #
# #
# This is the solution to the puzzle. #
# You can find the puzzle without its solution in the Cairo Playground. #
#########################################################################
# Program hash: 0x07b60b3745d3c816553bc8b7ac9410b2fc4441d5cd694e5f61226455092a98ce.
# In this puzzle you have to find a Hamiltonian cycle in a graph.
# The graph has 18 vertices and it is encoded using its (symmetric) adjacency matrix.
# In order to find the Hamiltonian cycle you can start by drawing the graph.
# For example, you can use networkx and matplotlib:
#
# import networkx
# import matplotlib.pyplot as plt
#
# encoding = 904711815024524574246580775193158565348810842345109828206640 + \
# (1662189419663012728075783146332749833 << 200)
# graph = networkx.Graph()
#
# for u in range(18):
# for v in range(u):
# if encoding & (1 << (18 * u + v)) != 0:
# graph.add_edge(u, v)
# networkx.draw_planar(graph, with_labels=True)
# plt.show()
#
# Then, find vertices of the form x--y--z where y is connected *only* to x and z: the
# edges x--y and y--z must be in the Hamiltonian cycle.
%builtins output range_check
from starkware.cairo.common.alloc import alloc
from starkware.cairo.common.math import assert_nn_le
const N_VERTICES = 18
# Unpacks an integer x to its bit representation, least significant bit first.
# Note that arr_size must be less than the log of field size to guarantee a unique unpacking.
func preprocess(x, arr : felt*, arr_size):
if arr_size == 0:
assert x = 0
return ()
end
%{ memory[ids.arr] = ids.x % 2 %}
tempvar v = [arr]
assert v = v * v
preprocess((x - v) / 2, arr + 1, arr_size - 1)
return ()
end
# Checks that 'path' (a list of n+1 vertices) is a valid path in the graph.
# For each i < n (note that the last one is excluded), writes aux[path[i]] = len(path) - i.
# This ensures that each vertex appears at most once.
func check{range_check_ptr}(path : felt*, aux : felt*, graph : felt*, n : felt):
if n == 0:
return ()
end
tempvar cur = [path]
# Make sure the current vertex index is valid, and set aux[cur] = n to make sure each vertex
# appears at most once.
assert_nn_le(cur, N_VERTICES - 1)
assert [aux + cur] = n
tempvar next = [path + 1]
assert [graph + cur * N_VERTICES + next] = 1
return check(path=path + 1, aux=aux, graph=graph, n=n - 1)
end
func main{output_ptr, range_check_ptr}():
alloc_locals
# Unpack the graph's encoding.
let (local graph : felt*) = alloc()
preprocess(904711815024524574246580775193158565348810842345109828206640, graph, 200)
preprocess(1662189419663012728075783146332749833, graph + 200, N_VERTICES * N_VERTICES - 200)
let (local path : felt*) = alloc()
%{
segments.write_arg(
ids.path, [12, 13, 5, 0, 4, 6, 7, 1, 11, 2, 15, 3, 8, 9, 10, 16, 14, 17, 12])
memory[ids.output_ptr] = 0x1234
%}
# Make sure it's a cycle - the first and last vertices must be the same.
assert [path] = [path + N_VERTICES]
let (local aux : felt*) = alloc()
# Check that path forms a Hamiltonian cycle.
# Since [path] = [path + N_VERTICES] it is a cycle.
# check() verifies that each vertex appears at most once.
# Since the length of the path is the same as the number of vertices,
# we obtain that each vertex appears *exactly* once.
check(path, aux=aux, graph=graph, n=N_VERTICES)
let output_ptr = output_ptr + 1
return ()
end
Seth
#########################################################################
# SPOILER ALERT #
# #
# This is the solution to the puzzle. #
# You can find the puzzle without its solution in the Cairo Playground. #
#########################################################################
# Program hash: 0x077bb8982750b5732e37570e20d02d60bc3bad6f9fc413d06a1f95f15dcd6ef0.
# This puzzle demonstrates a wrong use of the Fiat-Shamir heuristic.
# In this puzzle you should provide a sequence of 100 values, which, when sampled "randomly",
# should be 0 for 50 samples and hash(x, x) for the other 50 samples.
# If the samples were truly random, this would have been infeasible.
# In this implementation (which incorrectly uses the Fiat-Shamir heuristic),
# you can control the randomness between the samples and thus make the test pass.
%builtins output pedersen range_check
from starkware.cairo.common.alloc import alloc
from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.hash import hash2
from starkware.cairo.common.hash_chain import hash_chain
from starkware.cairo.common.math import split_felt, unsigned_div_rem
const SIZE = 100
const COUNT = 100
func check{pedersen_ptr : HashBuiltin*, range_check_ptr}(items : felt*, seed, n, type):
if n == 0:
return ()
end
alloc_locals
let (high, low) = split_felt(seed)
let (_, r) = unsigned_div_rem(low, SIZE)
local preimage
%{
if ids.type == 0:
# preimage is not really used in this case, but it's taken into the seed hash.
# Thus, you can pick a value that will make the next two samples pass.
for preimage in range(100):
# Predict the next two values.
next_seed = pedersen_hash(pedersen_hash(ids.seed, preimage), 0)
next_value = (next_seed % 2**128) % ids.SIZE
# Make sure it's in the second half of the array. Otherwise, try a different value.
if next_value < ids.SIZE // 2:
continue
next_next_seed = pedersen_hash(pedersen_hash(next_seed, 0), H)
next_next_value = (next_next_seed % 2**128) % ids.SIZE
# Make sure it's in the first half of the array. Otherwise, try a different value.
if next_next_value >= ids.SIZE // 2:
continue
break
else:
raise Exception('Failed')
else:
preimage = 0
ids.preimage = preimage
%}
let (image) = hash2{hash_ptr=pedersen_ptr}(preimage, preimage)
tempvar item = [items + r]
if type == 0:
assert item = 0
else:
assert item = image
end
let (seed) = hash2{hash_ptr=pedersen_ptr}(seed, preimage)
let (seed) = hash2{hash_ptr=pedersen_ptr}(seed, item)
return check(items=items, seed=seed, n=n - 1, type=1 - type)
end
func main{output_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}():
alloc_locals
let (local data : felt*) = alloc()
assert [data] = SIZE
%{
# Create an array where the first half is zeros and the second is h(0, 0).
from starkware.crypto.signature.signature import pedersen_hash
H = pedersen_hash(0, 0)
segments.write_arg(
ids.data + 1, [0] * (ids.SIZE // 2) + [H] * (ids.SIZE // 2))
memory[ids.output_ptr] = 0x1234
%}
# Compute the initial seed, by taking the hash of the array.
let (seed) = hash_chain{hash_ptr=pedersen_ptr}(data)
check(items=data + 1, seed=seed, n=COUNT, type=0)
let output_ptr = output_ptr + 1
return ()
end
Montu
#########################################################################
# SPOILER ALERT #
# #
# This is the solution to the puzzle. #
# You can find the puzzle without its solution in the Cairo Playground. #
#########################################################################
# Program hash: 0x00a4ca077b0c3f81cc3c813af6ebf16fb83f2bbf96068c5cbe5b4f9e73febfa8.
# This puzzle is about Reed–Solomon codes and the FRI algorithm. FRI gets a sequence of N field
# elements a_i and checks whether there exists a polynomial f(x) of some bounded degree such that
# a_i = f(g^i) (where g is an N-th root of unity in the field).
#
# For those of you familiar with the FFT algorithm, FRI is very similar except that it uses
# randomness to reduce an instance of size N to *one* instance of size N/2 (rather than two such
# instances in FFT). This means the running time is O(N), rather than O(N * log N).
#
# The puzzle goes as follows: you're given an array of 8 numbers, and you should modify 3 of them
# so that the resulting sequence will be the evaluation of a polynomial of degree less than 4.
# You can use math programs, such as sage, to enumerate over the 56 options of which elements
# should be modified, until you find one where the 5 other values lie on the required polynomial.
# Then you evaluate it on the 3 wrong values. (This is in fact error correction in a
# Reed–Solomon code.)
%builtins output pedersen
from starkware.cairo.common.alloc import alloc
from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.hash_state import HashState, hash_finalize, hash_init, hash_update
func compute_next_layer(
input : felt*, output : felt*, length : felt, alpha : felt, x : felt, g : felt):
tempvar a = [input]
tempvar b = [input + length]
assert [output] = (a + b) / 2 + alpha * (a - b) / (2 * x)
if x * g == -1:
return ()
end
return compute_next_layer(
input=input + 1, output=output + 1, length=length, alpha=alpha, x=x * g, g=g)
end
# Verifies that there exists a polynomial f(x) of degree less than length/2 where input[i] = f(g^i).
# Implemented using FRI.
func verify{hash_ptr : HashBuiltin*, hash_state_ptr : HashState*}(
input : felt*, length : felt, g : felt):
alloc_locals
if length == 2:
# If length is 2, the degree should be less than 1, which means f(x) is a constant
# polynomial. Just check that the two values are indeed the same.
assert [input] = [input + 1]
return ()
end
# Compute alpha.
let (hash_state_ptr) = hash_update(
hash_state_ptr=hash_state_ptr, data_ptr=input, data_length=length)
let (alpha) = hash_finalize(hash_state_ptr=hash_state_ptr)
local hash_ptr : HashBuiltin* = hash_ptr
local hash_state_ptr : HashState* = hash_state_ptr
let (local next_layer : felt*) = alloc()
compute_next_layer(input=input, output=next_layer, length=length / 2, alpha=alpha, x=1, g=g)
return verify(input=next_layer, length=length / 2, g=g * g)
end
# Counts the number of differences between the input and the output arrays.
func compare(input : felt*, output : felt*, length : felt) -> (diff : felt):
if length == 0:
return (diff=0)
end
let (diff) = compare(input=input + 1, output=output + 1, length=length - 1)
if [input] == [output]:
return (diff=diff)
else:
return (diff=diff + 1)
end
end
func main{output_ptr : felt*, pedersen_ptr : HashBuiltin*}():
alloc_locals
const LENGTH = 8
const G = 2804690217475462062143361339624939640984649667966511418446363596075299761851
let (input) = alloc()
# The input sequence.
assert [input] = (
2760163267763136926307712447289333015931143661720962520709479367174330989984)
assert [input + 1] = (
620345510678501588305616341951109830750033614090225920347864657883483407165)
assert [input + 2] = (
3181959697776337130511545402257206919343979808211484609881516936335798865334)
assert [input + 3] = (
1830152343057623004121086982129442788610913917055044983876581372969127139593)
assert [input + 4] = (
3553572895696142252358926310847411672039878792883770142922873977486098926969)
assert [input + 5] = (
2462248735454554379268841047904517280521029943202779759148500485193601548624)
assert [input + 6] = (
792090413233267968557021563731724001464889355006703125688313681478453789157)
assert [input + 7] = (
1348005446214778757482455457529115254152067928062775094282398020688141612139)
let (local modified_input) = alloc()
%{
values = [memory[ids.input + i] for i in range(8)]
# Modify the three wrong values.
values[0] = 2832196451828398372049458809620220651104433024139451345189664845961660092224
values[1] = 2973895000156339190100688610451105694809999170219600703266872401149050581336
values[6] = 2665075268248548789750464358384411881228826548637091142553388576352235017646
segments.write_arg(ids.modified_input, values)
memory[ids.output_ptr] = 0x1234
%}
# Checks that exactly 3 values were modified.
let (diff) = compare(input=input, output=modified_input, length=LENGTH)
assert diff = 3
let (hash_state_ptr) = hash_init()
verify{hash_ptr=pedersen_ptr, hash_state_ptr=hash_state_ptr}(
input=modified_input, length=LENGTH, g=G)
let output_ptr = output_ptr + 1
return ()
end
Amun
#########################################################################
# SPOILER ALERT #
# #
# This is the solution to the puzzle. #
# You can find the puzzle without its solution in the Cairo Playground. #
#########################################################################
# Program hash: 0x03a90efd79e07518a02ccdfc0ad37151143827d32ba4a90f284f37e6b040fbe0.
# This is a Rubik's 3x3x3 cube.
# To solve it you should find the initial state and identify the possible moves (which are
# U, R, F, L, B, D, representing the faces of the cube - Up, Right, Front, Left, Back and Down,
# respectively).
%builtins output pedersen range_check
from starkware.cairo.common.alloc import alloc
from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.dict_access import DictAccess
from starkware.cairo.common.hash_chain import hash_chain
from starkware.cairo.common.math import assert_nn_le
from starkware.cairo.common.registers import get_fp_and_pc
from starkware.cairo.common.squash_dict import squash_dict
# Describes the six permutations U, R, F, L, B, D according to their action on the stickers.
# Each permutation is represented as 5 cycles of 4 stickers each (note that rotating a face
# by 90 degrees, changes 20 stickers, and the cycles are all of length 4).
# The stickers are ordered as follows: all the stickers on U, then on L, F, R, B, and D,
# where the 8 stickers of each face (center excluded) are ordered clockwise.
func get_data() -> (res : felt*):
alloc_locals
# Up.
local a0 = 0
local a = 2
local a = 4
local a = 6
local a = 1
local a = 3
local a = 5
local a = 7
local a = 8
local a = 32
local a = 24
local a = 16
local a = 9
local a = 33
local a = 25
local a = 17
local a = 10
local a = 34
local a = 26
local a = 18
# Right.
local a = 24
local a = 26
local a = 28
local a = 30
local a = 25
local a = 27
local a = 29
local a = 31
local a = 4
local a = 32
local a = 44
local a = 20
local a = 3
local a = 39
local a = 43
local a = 19
local a = 2
local a = 38
local a = 42
local a = 18
# Front.
local a = 16
local a = 18
local a = 20
local a = 22
local a = 17
local a = 19
local a = 21
local a = 23
local a = 6
local a = 24
local a = 42
local a = 12
local a = 5
local a = 31
local a = 41
local a = 11
local a = 4
local a = 30
local a = 40
local a = 10
# Left.
local a = 8
local a = 10
local a = 12
local a = 14
local a = 9
local a = 11
local a = 13
local a = 15
local a = 0
local a = 16
local a = 40
local a = 36
local a = 7
local a = 23
local a = 47
local a = 35
local a = 6
local a = 22
local a = 46
local a = 34
# Back.
local a = 32
local a = 34
local a = 36
local a = 38
local a = 33
local a = 35
local a = 37
local a = 39
local a = 2
local a = 8
local a = 46
local a = 28
local a = 1
local a = 15
local a = 45
local a = 27
local a = 0
local a = 14
local a = 44
local a = 26
# Down.
local a = 40
local a = 42
local a = 44
local a = 46
local a = 41
local a = 43
local a = 45
local a = 47
local a = 22
local a = 30
local a = 38
local a = 14
local a = 21
local a = 29
local a = 37
local a = 13
local a = 20
local a = 28
local a = 36
local a = 12
let (__fp__, _) = get_fp_and_pc()
return (res=&a0)
end
# Gets a cycle of 4 stickers and applies it on the state dictionary.
func cycle{state : DictAccess*}(values : felt*):
let state0 = state
let state1 = state0 + DictAccess.SIZE
let state2 = state1 + DictAccess.SIZE
let state3 = state2 + DictAccess.SIZE
assert state0.key = [values + 0]
assert state1.key = [values + 1]
assert state2.key = [values + 2]
assert state3.key = [values + 3]
%{
ids.state0.prev_value = arr[ids.state0.key]
ids.state1.prev_value = arr[ids.state1.key]
ids.state2.prev_value = arr[ids.state2.key]
ids.state3.prev_value = arr[ids.state3.key]
%}
assert state0.new_value = state3.prev_value
assert state1.new_value = state0.prev_value
assert state2.new_value = state1.prev_value
assert state3.new_value = state2.prev_value
let state = state + 4 * DictAccess.SIZE
%{
arr[ids.state0.key] = ids.state0.new_value
arr[ids.state1.key] = ids.state1.new_value
arr[ids.state2.key] = ids.state2.new_value
arr[ids.state3.key] = ids.state3.new_value
%}
return ()
end
# Executes the solution on the state dictionary.
func run{range_check_ptr, state : DictAccess*}(data : felt*, sol : felt*, sol_size : felt):
if sol_size == 0:
return ()
end
tempvar x = [sol]
assert_nn_le(x, 5)
cycle(data + 20 * x)
cycle(data + 20 * x + 4)
cycle(data + 20 * x + 8)
cycle(data + 20 * x + 12)
cycle(data + 20 * x + 16)
run(data=data, sol=sol + 1, sol_size=sol_size - 1)
return ()
end
# Returns the initial state of the cube.
func get_initial_value{hash_ptr : HashBuiltin*}() -> (initial_value : felt*):
alloc_locals
let (local initial_value : felt*) = alloc()
assert [initial_value] = 48
%{ segments.write_arg(ids.initial_value + 1, initial_state) %}
# This is the hash of the full state of the cube. It's the last thing to look at.
let (res) = hash_chain(initial_value)
assert res = 402684044838294963951952172461450293510735826065192598384325922359699836469
# The state is encoded using various hash chains on slices of the state.
# Each hash chain starts with its length (excluding the length item).
# For example, [2, 2, 5] where 2 is the length of [2, 5].
# Since we know that all the values should be in the range 0, 1, ..., 5 we can enumerate
# over all options and compute the preimage of the hashes below.
# For example hash_chain([2, 2, 5]) is pedersen_hash(2, pedersen_hash(2, 5)) =
# 1501038259288321437961590173137394957125779122158200548115283728521438213428,
# which appears below.
#
# Not all the values are revealed this way. We are left with 7 unknown numbers.
# Since we know that each number in the range 0, 1, ..., 5 appears exactly 8 times,
# we know that the missing numbers are 0, 1, 1, 2, 3, 3, 5.
# We enumerate on all possible options until we get the final hash written above.
let (res) = hash_chain(initial_value + 1)
assert res = 1508108551069464286813785297355641266663485599320848393798932455588476865295
let (res) = hash_chain(initial_value + 7)
assert res = 2245701625176425331085101334837624242646502129018701371434984384296915870715
let (res) = hash_chain(initial_value + 12)
assert res = 3560520899812162122215526869789497390123010766571927682749531967294685134040
let (res) = hash_chain(initial_value + 18)
assert res = 196997208112053944281778155212956924860955084720008751336605214240056455402
let (res) = hash_chain(initial_value + 24)
assert res = 1035226353110224801512289478587695122129015832153304072590365512606504328818
let (res) = hash_chain(initial_value + 30)
assert res = 1501038259288321437961590173137394957125779122158200548115283728521438213428
let (res) = hash_chain(initial_value + 34)
assert res = 3537881782324467737440957567711773328493014027685577879465936840743865613662
let (res) = hash_chain(initial_value + 39)
assert res = 1039623306816876893268944011668782810398555904667703809415056949499773381189
let (res) = hash_chain(initial_value + 42)
assert res = 2508528289207660435870821551803296739495662639464901004905339054353214007301
return (initial_value=initial_value + 1)
end
# Verifies that we obtained a solved cube.
func verify(squashed_dict : felt*, initial_value : felt*, n):
if n == 6:
return ()
end
assert [squashed_dict + 0] = n * 8
assert [squashed_dict + 1] = [initial_value]
assert [squashed_dict + 2] = n
assert [squashed_dict + 3] = n * 8 + 1
assert [squashed_dict + 4] = [initial_value + 1]
assert [squashed_dict + 5] = n
assert [squashed_dict + 6] = n * 8 + 2
assert [squashed_dict + 7] = [initial_value + 2]
assert [squashed_dict + 8] = n
assert [squashed_dict + 9] = n * 8 + 3
assert [squashed_dict + 10] = [initial_value + 3]
assert [squashed_dict + 11] = n
assert [squashed_dict + 12] = n * 8 + 4
assert [squashed_dict + 13] = [initial_value + 4]
assert [squashed_dict + 14] = n
assert [squashed_dict + 15] = n * 8 + 5
assert [squashed_dict + 16] = [initial_value + 5]
assert [squashed_dict + 17] = n
assert [squashed_dict + 18] = n * 8 + 6
assert [squashed_dict + 19] = [initial_value + 6]
assert [squashed_dict + 20] = n
assert [squashed_dict + 21] = n * 8 + 7
assert [squashed_dict + 22] = [initial_value + 7]
assert [squashed_dict + 23] = n
verify(squashed_dict=squashed_dict + 24, initial_value=initial_value + 8, n=n + 1)
return ()
end
func main{output_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}():
alloc_locals
let (local data : felt*) = get_data()
let (local sol : felt*) = alloc()
local sol_size
%{
memory[ids.output_ptr] = 0x1234
# Prepare the initial state.
arr = [
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,
]
initial_state = list(arr)
rotations = {'U': 0, 'R': 1, 'F': 2, 'L': 3, 'B': 4, 'D': 5}
solution = 'LULLLUUFFFDDDFFBBBUUULLLFFUUUDDDLLUBBUBBRRLL'
ids.sol_size = len(solution)
segments.write_arg(ids.sol, [rotations[x] for x in solution])
%}
let (state : DictAccess*) = alloc()
local state_start : DictAccess* = state
run{state=state}(data, sol, sol_size)
let (local squashed_dict : DictAccess*) = alloc()
let (squashed_dict_end) = squash_dict(
dict_accesses=state_start, dict_accesses_end=state, squashed_dict=squashed_dict)
assert squashed_dict_end = squashed_dict + DictAccess.SIZE * 48
local range_check_ptr = range_check_ptr
let (initial_value) = get_initial_value{hash_ptr=pedersen_ptr}()
local pedersen_ptr : HashBuiltin* = pedersen_ptr
verify(squashed_dict=squashed_dict, initial_value=initial_value, n=0)
let output_ptr = output_ptr + 1
return ()
end