Over the course of the past semester, we, a student project from Technical University of Berlin, engaged in making a Chess game for Ethereum, a blockchain-based distributed computing platform.
The project was overseen by the TU department of Information Systems Engineering and Dr. Christian Reitwiessner from the Ethereum foundation.
The goal of the project was to develop a real application using the available tools and evaluate challenges and advantages of this new platform.
In this first article, we will explain the application we made, and go into detail about the main lessons learned. We are planning to release two more articles on Solidity data structures and Ethereum development tools.
Online gaming
Traditionally, most online games work using an intermediary to setup the communication and ensure everything works correctly. This is a third-party that players have to trust to do the right thing. If you consider gambling, players have to transmit money to a black box. They only do it because they have trust in the service provider, or because they value the upside of winning more than the risk of losing money to whichever party.
Additionally, providing this service costs money, so the provider must generate some sort of income, be it through fees or advertisement.
The idea of the decentralized web, and in particular platforms like Ethereum, is to eliminate trust, the need for continuously running servers and maintaining the service, and a central single point of failure. All transactions take place on a global, publicly verifiable database called blockchain. These operations are referred to as on-chain. Messages are sent via a peer-to-peer network. No central servers have to be deployed and maintained unlike in traditional web applications. There is no party that can shut down the service, cheat, or run away with any money.
After forming a team of students who all had some prior experience in web development, we set out to make a usable online Chess game. Chess is a well-known turn-based two-player game with well defined rules. It is also well-studied in Computer Science, and thus a good candidate for a first project.
On a high level, Chess consists of the following entities: two players, a board of 64 squares, 16 pieces per player, and a series of piece moves from one square to another. We will need data structures for all of these, plus logic for making and verifying moves and end game conditions. To really demonstrate the usefulness of making this a distributed Ethereum app, we will also add methods to bet and win money.
Contract
Ethereum works with Smart Contracts, which are programs that are executed on the global blockchain. The code is public, as well as all messages and data, making the system reliable. If designed correctly, the system is uncheatable.
After many iterations, this is the contract architecture that we ended up with. The contracts were written in Solidity, which supports inheritance and libraries to improve the design.
We abstracted all code that applies to turn-based games in general into an abstract base class. Chess is the main contract the clients interact with. Game rules (state and move validation) are in a sub-library ChessLogic. Some helper functions like signature validation (Auth) and Elo score calculation are also outsourced into libraries.
A complete game of Chess can be played reliably on-chain, meaning no other communication is involved except messages from and to the Smart Contract.
However, there is one huge problem with Chess: Verifying a game’s end is incredibly costly. For checkmate (king is in check and player cannot make any move to escape) and stalemate (same, except that king is not in check), to verify the condition all possible moves have to be calculated and verified, which is unfeasible on the blockchain. We actually implemented the logic in Solidity, only to find out it exceeds the current limits of a transaction.
First lesson: Computationally expensive calculations are usually not suitable to be run on-chain.
Challenge response
A possible solution for this is to rethink the problem and tackle it from the another side.
What is the problem? Player A puts Player B into checkmate and wants the contract to verify and acknowledge this condition. If this cannot be done, can we verify the opposite?
Consider that Player A simply claims that the condition has been reached, and then it is Player B’s chance to refute that claim. Which is easy — they just have to submit another valid move, and the original claim is proven to be false. This interactive way of verification also relates to how people play real (analogue) check — I say “check mate”, and either you agree that you lost or you show me a move you can still make.
This is a form of “Challenge–response”. It seems easy, but you have to look at all possible states and provide ways to resolve them fairly and without deadlocks.
For our game, after a challenge was created, a timer is started. If the other player does not respond within this time, the challenger can claim the game to be finished.
At this step we also added a general “timeout condition” which means a player can win the game if the other player stopped playing. Think of it as a turn time.
A few more logical problems arose while implementing all protocols (win, draw, timeout). Finally we came up with this solution, which looks pretty complicated but mostly follows the abstract version above. Feel free to skip this diagram.
Second lesson: For efficient distributed decentralized communication, rethink the problem and come up with alternative solutions.
Off-chain
The biggest problem in making completely on-chain games, however, is the lack of real time. Ethereum transactions are processed in blocks which occur approximately every 14 seconds. This is pretty fast, but definitely not fast enough for a game that is supposed to feel real time.
One approach to improve this is to move some part of the communication away from the blockchain (hereafter called off-chain). We still want to keep our serverless architecture, so we can use peer-to-peer web protocols to achieve this. In the future, Ethereum’s own Whisper can be used for this exact use case. Until then, we implemented a dummy proxy server to imitate communication over Whisper to test out this kind of architecture.
Let’s think again about our problem. Which part of the game can be done off-chain without loss of the on-chain advantages?
As long as the game runs smoothly, i.e. each player is alternatingly sending a correct move, we don’t really need the blockchain to verify all these correct moves — the clients can do that. What if we sent all moves directly between the clients and only resort to the blockchain for disputes and recording the end result?
Turns out, this is pretty easy to achieve. We just need to give each player the possibility to independently prove the current game state. To prohibit them from cheating, each report to the blockchain should consist of the complete game state with a valid signature from the other player. That way it can be cryptographically proven that both players accept the current state.
In other words, during normal gameplay each player keeps sending their next move and the resulting game state, plus a cryptographic signature. If the other player disagrees, they can submit this data to the Smart Contract for verification. The same can be done at the end of the game. Furthermore, clients will acknowledge each other’s messages to discover problems faster.
Apart from setting up the game (Initialize and Join), clients only send messages to the Blockchain when they want to claim something (timeout, win, draw), and to withdraw their prize.
Third lesson: To increase performance, move computation and communication to clients, ensuring security with smart communication protocols.
Now, at first this might seem like a step back — after all, weren’t we trying to make “unstoppable applications” by keeping all data and implementing all logic on the blockchain?
We think that the main point still stands: The application is serverless, secure and trustless. In the end, the blockchain is the single source of truth, but the clients help in making it more efficient. In case of a problem, however, the game can fully degrade to run on the Blockchain.
Conclusion
Fundamentally, the decentralised web is about a new way of modelling problems. For that, Smart Contracts provide a good framework of thinking, but additional ideas have to be employed.
The Ethereum virtual machine is turing-complete, but that doesn’t mean that everything should be computed on it. Since there is a clear cost assigned to every operation, we have to model our applications in creative ways to use the available resources effectively.
In conclusion, we think that it is definitely feasible to implement decentralized games using Ethereum, but one needs a smart model to make them efficient and usable.
PS: All our code is open-source and can be found here. The repository still needs some cleanup, but if you want to you can dig into the contracts right now.
