The Many Neighbours of Arbistreet

Arbitrum Street is in chaos! The world famous ETH Bucharest hackathon is starting soon, and the entire foundation is counting on him, but Pepe and his friends on Arbitrum Street are nowhere near ready! Thankfully, he has a powerful ally to support him in making preparations… you!

You, equipped with the most powerful of EVM-compatible smart contract technology, Stylus, must develop a powerful tool to support him and his friends. His friends need help preparing food for the event, making sure their stall is ready, and making sure that their merch is delivered succesfully. For this occassion, he has prepared a suite of drones to build ultra high powered keyboards and to quickly 3D print tools.

For the drones to work effectively, a superpowered algorithm to reconfigure their circuitry must be discovered! Thiss algorithm is known as the “Bucharest Proof of Work” algorithm. This algorithm on the fly reconfigures the drones in what’s known as the “King Formation” – an alignment of nodes that seemingly resemble chess pieces.

Competition background

Picture Tic-Tac Toe:

Tic-Tac-Toe

The object of this simple game is to find three in a row.

Imagine we want to play this game on-chain without any humans placing pieces themselves, how would we do so? One strategy is to take a hash (the following is keccak):

keccak("Hello, Bucharest!") = 864cf9d8d24bcfb0789d488b5992a6dd225837382f69dd9f839a34ad9301dc9c

We could use this hash to derive bits of information from it which appear seemingly random. For example, we could concatenate a random number together with it:

keccak("Hello, Bucharest!" . 0) = 92bef68ba76edccbcca303b0cc9200845b7321fb7b7e0adc6ff5b835f767a6e0

In the above, we can assume we’re simply appending the base10 of the 0 to the string without any padding or packing. It’s difficult to predict what the next iteration of the hash would be alongside the number!

import binascii

BOARD_SIZE = 9 # Three pieces on each row!

h = "92bef68ba76edccbcca303b0cc9200845b7321fb7b7e0adc6ff5b835f767a6e0"

From hashing this concatenated word, we have a large word we could play around with, 32 bytes in fact. This is way more than we need for the simple game of Tic-Tac-Toe that we’re playing! Let’s cut it up to get the location of a piece, and whether it’s a nought or a cross:

import binascii

BOARD_SIZE = 9 # Three pieces on each row!

h = binascii.unhexlify("92bef68ba76edccbcca303b0cc9200845b7321fb7b7e0adc6ff5b835f767a6e0")
i = int.from_bytes(h)              # 66375078430131441827371246052168348963468487841192525321425022850624005842656
piece_type = i & 1 # 0             # 0 (nought)
piece_log = (i >> 32) % BOARD_SIZE # 6

The board state would currently look like:

|---|---|---|
|   |   |   |
|---|---|---|
|   |   |   |
|---|---|---|
| O |   |   |
|---|---|---|

So from one word of seemingly random information, we’ve derived some meaningful borad state for our game!

We can play this quite a bit:

keccak(“Hello, Bucharest!” . 1):

|---|---|---|
|   |   |   |
|---|---|---|
| O |   |   |
|---|---|---|
| O |   |   |
|---|---|---|

…

keccak(“Hello, Bucharest!” . 24):

|---|---|---|
| X | X | X |
|---|---|---|
| O | O | X |
|---|---|---|
| X | X | O |
|---|---|---|

…

Cool! We played this game 23 times from the start of 0 to find the first three in a row. We could remember this, and tell our friends when to start simulating Tic-Tac-Toe (and when they’ll find the solution).

How to play

ETH Bucharest hashing is based on this game: instead of playing Tic-Tac Toe, we play Chess to find the first instance of check for the last placed king.

Contracts must be developed and released on-chain, where they are benchmarked against each other, with the number one submission winning a static amount of points token per second, sent to the creator.

Submissions must be made accompanied by a source code release, for competitors to understand how a developer took took the approach they did, to be used as reference.

The deployment where you should submit solutions lives at 0x on the Superposition Testnet.

You can register your submission to have its performance benchmarked by calling register(address,address,string) at 0x, for example using Cast:

cast send \
        --rpc-url https://testnet-rpc.superposition.so \
        --private-key <your private key here> \
        0x
        'register(address,address,string)'
        <your contract address> \
        <the address you used with the Superposition faucet> \
        <your repository link>

Webapp coming soon!

Prizes

There are several prizes up for grabs! These include:

  1. $5,400 USD in cash distributed by the share of points in the game

  2. 5 Superposition Superkeyboards, Superposition Midnight and Quantum Daybreak. Top prizes hotswappable (Pro), usual soldered normally. Pro keyboards are tactiles, and normals linear.

To win a keyboard, you must come either first place in this or the other Stylus competition, or you must register via the faucet and be chosen at random for deploying a contract to Superposition testnet or mainnet. A keyboard will also be given to a top performing student.

Keyboards Keyboard back plate