The Cairo Games - Vol. 2

Update, 04/23/2021: The Cairo Games Vol.2 have ended!

See the solutions to the puzzles of the second round here.

Welcome to the second round of the Cairo Games – where you can test your coding skills by solving puzzles, competing against other coders. Winners get ETH, limited-edition NFTs, and infinite bragging rights. To see the first round, click here.

How does the Competition Work?

On April 18th, at 3PM GMT StarkWare will publish a set of Cairo puzzles. In each puzzle you’ll be given a somewhat obfuscated Cairo program with some missing Prover Hints. You’ll have to understand what the program does, and add the missing Hints to make it run successfully.

The first to solve a puzzle will get a prize (which varies between 0.1 ETH and 1 ETH according to the puzzle’s level of difficulty). Each solution will be published on Ropsten Etherscan.

Each solver gets a limited edition NFT, minted exclusively for this round of the competition, and becomes a member of the Cairo Games Hall of Fame, published on the Cairo Games web page.

The Winners!

Congratulations to all the winners! You can see this list timestamped on Ropsten here


Puzzle Name	1^st Place	2^nd Place	3^rd Place
Nu	Daniel Lubarov	William Borgeaud	Gizem Kara
Pakhet	William Borgeaud	@adr1anh	Gizem Kara
Seth	William Borgeaud
Montu	Daniel Lubarov	William Borgeaud
Amun	William Borgeaud	Adrian Hamelink @ Taurus SA

The Puzzles!

Name	Difficulty	Prize	Hash
Nu	Easy	0.1 ETH	0x0603aa817aa054d58beb522a1e17286e92afbce15009893cbd81d22b7bdc3f56
Pakhet	Easy	0.1 ETH	0x07b60b3745d3c816553bc8b7ac9410b2fc4441d5cd694e5f61226455092a98ce
Seth	Medium	0.3 ETH	0x077bb8982750b5732e37570e20d02d60bc3bad6f9fc413d06a1f95f15dcd6ef0
Montu	Medium	0.3 ETH	0x00a4ca077b0c3f81cc3c813af6ebf16fb83f2bbf96068c5cbe5b4f9e73febfa8
Amun	Hard	1 ETH	0x03a90efd79e07518a02ccdfc0ad37151143827d32ba4a90f284f37e6b040fbe0

All the puzzles will be live at exactly 3PM GMT, Apr 18th on the Cairo Playground

Why the hash?

Each puzzle has a unique program hash (this is the hash of the compiled code, excluding hints) that identifies it. When you register your solution on-chain, you need to supply the program hash.

Puzzle Example

To get you started, we prepared a puzzle example – a dry run – to make sure you understand how everything works.

%builtins output

funcmain(output_ptr : felt*) -> (output_ptr : felt*):

    alloc_locals

    local x

    local y

    assert x * y = 15

    assert x + y = 8

   return (output_ptr=output_ptr + 1)

end

Go to the Cairo Playground, click on “The Cairo Games” and open the “Example” puzzle.

If you try to run it, it will fail saying Unknown value for memory cell. Indeed, the two local variables x and y are not initialized.
Let’s initialize them using a Hint:

%builtins output

funcmain(output_ptr : felt*) -> (output_ptr : felt*):
alloc_locals
local x
local y
%{

          ids.x= 3

          ids.y = 5

      
 %}
assert x * y = 15
assert x + y = 8
return (output_ptr=output_ptr + 1)
end

Now the program runs successfully – which means you’ve solved the puzzle!

It’s very important to understand that you’re allowed to add/change Hints, but you cannot add/change the Cairo code. In this example, removing the asserts is not a valid solution because it changes the code.

Submitting Your Solution to the Blockchain in 3 Steps

Step 1

Once you’ve found how to solve the puzzle, add a Hint that makes the program output your Ropsten Ethereum address (the competition runs using Ropsten Ethereum contracts). For example, if your address is 0x123456789a, write:

%builtins output

funcmain(output_ptr : felt*) -> (output_ptr : felt*):
alloc_locals
local x
local y
%{

          ids.x= 3

          ids.y = 5

          memory[ids.output_ptr] = 0x123456789a
      
 %}
assert x * y = 15
assert x + y = 8
return (output_ptr=output_ptr + 1)
end

You can run it in the playground to verify that the output is indeed your Ethereum address (note that the output is shown as a decimal integer, To see the hexadecimal value, check the tooltip).

Step 2

Next, send your solution to the GPS, by clicking on “Send to GPS”. The GPS service will generate a proof for the validity of the run, and register it as a Fact on the blockchain (see here). This Fact functions as a stamp attesting to the fact you’ve solved the puzzle (without revealing your solution on-chain!).

Step 3

Now register your solution, by invoking the submitPuzzleSolution() method in the competition contract. The first solution to each puzzle will get a prize! (You can find the prize for each puzzle in the table above).

Let’s review the arguments for submitPuzzleSolution():

a. rewardAddress: This is your Mainnet Ethereum address. If you want to get the prize or the puzzle NFTs, make sure you put here the correct address 🙂
b. submitterName: This is easy – your name. It will appear in the list of solvers even if you’re not the first to solve a puzzle.
c. programHash: This is the identifier of the puzzle you’ve solved. You’ll see this value in the Playground.

Note that the time of submitPuzzleSolution() will be used for the order of winners, not the time of sending the solution to the GPS.

How to Win?

Before the competition starts, we recommend that you:

Learn Cairo by following the two tutorials Hello, Cairo and How Cairo Works.
Install Metamask, or another wallet through which you can send Ropsten Ethereum transactions (for registering your solution).
Get some Ropsten ETH (using a Ropsten faucet). You can get it for free, and you just need enough for the gas cost of registration (0.01 ETH should be enough).
Solve the example puzzle in the Playground and register your solution to make sure everything runs smoothly. You can also practice by solving the puzzles of the Cairo Games Vol.1.

And some more information:

If you’re looking for a fast implementation of the Pedersen hash function, don’t use the one in crypto/starkware/crypto/signature/signature.py – it’s meant as a reference.
Check out the one here: crypto/starkware/crypto/signature/fast_pedersen_hash.py. It’s faster.
A few of the puzzles are of a mathematical nature. For those, it’s important to know that the field we’re working in is integers modulo 2^251 + 17*2^192 + 1. Also, some programs like Sage can be used for computations in the field (there are also online versions, such as https://sagecell.sagemath.org/).
You can find the code of the library functions (with some documentation) here.
You can install cairo locally to experiment, using: pip install cairo-lang. Afterwards, you can access cryptographic primitives using import starkware.crypto.signature and cairo compiler internals using import starkware.cairo.lang.compiler.

The Playground has limited computational power, so if you need to, you can precompute things locally and merely write the result of the computation in a Hint.

Good luck!

The Cairo Games – Vol. 2