Reducing ETH Gas 23x by converting Arrays to Bytes
This month (Aug/Sept 2017) I built my first Solidity Contract for the Ethereum Virtual Machine and ran into all sorts of pitfalls. The first one was realizing that some of the most trivial operations cost tons of gas, especially those involving Arrays and Loops. My contract was full of them and costing an arm and a leg, but I realized a way to refactor the Arrays into Bit Strings and use Bit Operators for reading and writing, then ultimately storing them as Bytes to save Millions in Gas.
The Contract requires a user to submit chess notation moves of a complete game of Reversi (also known as Othello). If the moves play a valid game and if the endgame board is visually symmetrical, the user receives a reward in an ERC20 Token. Essentially it substitutes traditional mining with searching the massive game tree of Reversi as a Proof-Of-Work with a reward payout based on the rarity of the symmetry (for more details check out the about page). It wouldn’t do for users to submit invalid but symmetrical games, so validation needed to take place on the contract. (If you’re curious how the project turned out check it out at Clovers.network)
The game Reversi is pretty easy to program but has a really large game tree (estimated to be 10⁵⁴ possible leaf nodes). That’s why it was a good challenge for game heuristic research that wanted to avoid expensive lookahead. When modeling the game one typically uses a 2 dimensional array to keep track of the state of the 8x8 board and an array of up to 60 moves (each of which might also be an array of column and row positions). First I tackled the Board Array.
BoardArray to ByteBoard
// EXPENSIVE !!!uint8 EMPTY = 0;
uint8 BLACK = 1;
uint8 WHITE = 2;uint8[8][8] boardArray;boardArray[3][3] = WHITE;
boardArray[3][4] = BLACK;
boardArray[4][4] = WHITE;
boardArray[4][3] = BLACK;
I began representing empty squares with 0, black with 1 (since black moves first) and white as 2. This allowed everything within the 8x8 boardArray to be correctly assigned to an empty 0 by default (Solidity doesn’t have an undefined property, everything defaults to some variation of 0 or false). This created an array that essentially looked like this:
[[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,2,1,0,0,0],
[0,0,0,1,2,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0]]
Which might as well have just been a really long string but represented as a binary value or hexadecimal value:
String:
000000000000000000000000000210000001200000000000000000000000000000000000Binary:
0b00000000000000000000000000000000000000000000000000000010010000000000000110000000000000000000000000000000000000000000000000000000Decimal:
10625432672847758622720Hexidecimal:
0x2400180000000000000
Later on down the road I got frustrated with prefixing the proper number of 0s when the board was partially empty so I decided to substitute the empty 0 for an empty 3, after all 3 still fits into 2 bits (0b11)which was all the space I wanted to spare for each square on the board.
String:
333333333333333333333333333213333331233333333333333333333333333333333333Binary:
0b11111111111111111111111111111111111111111111111111111110011111111111110110111111111111111111111111111111111111111111111111111111Decimal:
340282366920938456379662753540715053055Hexadecimal:
0xFFFFFFFFFFFFFE7FFDBFFFFFFFFFFFFF
This new representation of the board is now so small it can fit into 128 bits, which is only 16 bytes (don’t forget it’s 8 bits per byte yall).
// EXPENSIVE !!!// uint8 EMPTY = 0;
// uint8 BLACK = 1;
// uint8 WHITE = 2;// uint8[8][8] boardArray;// boardArray[3][3] = WHITE;
// boardArray[3][4] = BLACK;
// boardArray[4][4] = WHITE;
// boardArray[4][3] = BLACK;// CHEAP !!!uint8 BLACK = 1;
uint8 WHITE = 2;
uint8 EMPTY = 3;bytes16 byteBoard;
byteBoard = bytes16(340282366920938456379662753540715053055);
Now all I had to do was figure out how to read and write to the byte string!
Reading and Writing to ByteBoard
For this part of the work I’m incredibly thankful to Maksym for his article on bitwise operators in Solidity. It was actually the first time I understood what bit operators were and how to use them—I know I’m late to the game but better late than never. After going over the idea of masking I set about creating a method for reading from my ByteBoard.
Reading from ByteBoard
To read a selection of a binary string you need to first decide where that section is, create a mask of 1s, shift them over to that desired read point, and use an & operator to extract them. Finally shift them back the same amount and you’ve got your value. Before building the mask I needed to find out where my desired read point was.
I made a function that took column and row positions to help me determine the read point. I know that each tile consists of two bits to make up a Black tile 0x01 a White tile 0x10 or an Empty tile 0x11 so whatever my position is I’ll have to double it eventually. I also know that each Row has 8 tiles so my placement would be (8 * col) + row. All of that is a description of how far from the beginning of the binary string it would be, but I need to know how far it is from the end, so I subtract that value from the total length of the 8x8 board (64 — (8*col) + row) . This would bring me to the end of my desired read location so I add back 1 place for the span of the mask and multiply by 2 for each bit:
uint128 shiftAmount = posToPush(col, row);function posToPush (uint8 col, uint8 row) returns(uint128) {
return uint128( ( (64) - ( (8 * col) + row + 1) ) * 2);
}
Now I build a mask of two bits in length with both bits turned on (0x11). This will get moved on top of the read point of my target string in a new and otherwise empty string. The & bitwise operator will return a new string where the only bits on will be present in both previous strings. That way all of the tiles around my target will result in 0, and only the bits that were also present in my target will persist:
function returnTile (bytes16 board, uint8 col, uint8 row) returns (uint8){
uint128 push = posToPush(col, row); bytes16 mask = bytes16(3);
// 0b00000011 (mask) mask = shiftLeft(mask, push);
// 0b00110000 (mask shifted if push was equal to 4) bytes16 before = board & mask;
// (board)0b01010101
// & (mask)0b00110000
// = (tile)0b00010000 bytes16 tile = shiftRight(before, push);
// 0b00000001 = 0b01 = 1 = Black Tile
return uint8(tile);
// returns 1
}function shiftLeft (bytes16 a, uint128 n) returns (bytes16) {
uint128 shifted = uint128(a) * 2 ** uint128(n);
return bytes16(shifted);
}
function shiftRight (bytes16 a, uint128 n) returns (bytes16) {
uint128 shifted = uint128(a) / 2 ** uint128(n);
return bytes16(shifted);
}
And now we know whether the tile at column X and row Y is equal to Black, White or Empty. (If you’d like more info about the shifting functions check out Maksym’s Article)
Writing to ByteBoard
In order to write a new value to a specific point on our binary board we follow the same steps as reading, only using different bit operators. This time instead of extracting the value with a mask, we use it to clear out a space for our new tile using XOR, then write to it using OR.
function turnTile (bytes16 board, uint8 color, uint8 col, uint8 row) returns (bytes16){ uint128 push = posToPush(col, row);
bytes16 mask = bytes16(3);
// 0b00000011 (mask) mask = shiftLeft(mask, push);
// 0b00110000 (mask shifted if push was equal to 4) board = ((board ^ mask) & board);
// (board)0b01010101
// ^ (mask)0b00110000
// = 0b01100101
// & (board)0b01010101
// = 0b01000101 bytes16 tile = bytes16(color);
// 0b00000010 (if tile was White)
tile = shiftLeft(tile, push);
// 0b00100000 (tile shifted if push was equal to 4) return board | tile;
// (board)0b01000101
// | (tile) 0b00100000
// = 0b01100101 (original board was 0b01010101)
}
In this case we use XOR to make a copy of the board only inverted at the mask. After using AND on that copy with the original the modified mask section gets erased completely, leaving a space for the new tile. Next we use the OR operator on our shifted new tile value and return the whole board with our newly flipped tile 🎉
Conclusion
We’ve taken care of reducing the 8x8 array of integers to a single Bytes16 value and the same technique can be used to convert other arrays. I also had an array of column and row positions for moves in the game. I was able to convert that into a couple Bytes28 values with a modified naming convention. I’ll save the details on exactly how for another day but the basics were the same. After doing both I took my contract which cost 95,000,000 gas to validate a game down to 4,109,875. Somewhere in the fluctuating cost of ETH and Gas prices that was a difference between $566.60 and $26.26. Now obviously $26.26 to validate a single game is still not ideal. One solution in the works is to use an Oracle to validate the game. Otherwise we’ll have to wait for Proof of Work or adoption of Ethermint to reduce the price of gas.
Until those happen we’re using the Rinkeby Test network where Ether is free for anyone with a github account. If you’d like to try mining a Symmetrical board of Reversi visit Clovers.network or the repo to mine directly.
