How Coindroids Deals with Forks - Volume 1(Adapted from the original post
here)
Many people have heard of forks as they related to cryptocurrencies, and understand that they represent what happens when two different portions of the same community both love their users very much but can longer stay together. The divorce leads to double the gifts during special occasions, and the two newly independent communities can live their separate lives.
What many people are not aware of is that small forks are actually happening constantly as part of a healthy distributed network.
Consider the following instance. Two perfectly valid blocks are mined around the same time, likely containing a very similar set of transactions, and are distributed around the network. Miners pick the first one they see and start to mine the next block on top of it. At the same times, Coindroids would see one of these blocks and start to process it as well.
Once the next block is found and distributed around the network, there is now an orphaned block that is no longer valid. If Coindroids learned of, and processed, the block that is no longer part of the chain with the most proof of work, we are now on the incorrect side of the micro-fork that took place. We learn this as soon as we receive a new block and check that the previous block is already one we have processed.
For a lot of systems, this is not a problem. As mentioned above, it is usually very likely that all the transactions that would have been in Block A will also be in Block B, maybe with some slight differences based on miner preferences to fees and friends.
With a centralized game built on top of a blockchain, this makes for some very fun problems to solve. We just processed the entire blocks worth of relevant transactions, all those attacks, item purchases, drop registrations, etc, and now our processor has learned that they were all invalid.
Note: In the Ethereum ecosystem, as long as all your code resides on chain, this is not a problem. Your code and state are part of the logical flow of the Ethereum system. If any part of your system syncs with a centralized database though, it can be equally as susceptible.Blockchains may be specifically designed for immutability, but we had to write the Coindroids system with undo as a key process within.
Our First Solution The first solution we experimented with was a reversible audit systems. Every time an action takes place, we keep track of how much of something was changed, and in what direction.
1. Droid A attacks Droid B
2. Droid A gains 5 experience, with a new total of 15 experience
3. Droid B loses 10 health, with a new total of 90 health
So, if we wanted to roll back, we would work backwards...
1. Droid B gains 10 health, for a restored total of 100 health
2. Droid A loses 5 experience, for a restored total of 10 experience
3. Droid A attack of Droid B is voided
This is pretty simple here, but with many attribute changes and actions taking place all 'at once' when a block is processed, this actually quickly becomes error-prone and time consuming. The audit system is still important overall to Coindroids, but it's use here in the fork processing system was quickly phased out.
Solution Two, SnapshotsReading an audit long in reverse ended up as a bit of a dud, at least within our implementation. As both error-prone and slow, the true cause was easily defined as one theme: unnecessary complexities.
So how did we simplify? All the data we need is pretty small, so we just create a copy of it and tie it to the processed block.
Now our example looks like this:
1. Droid A attacks Droid B
2. Droid A gains 5 experience, with a new total of 15 experience
3. Droid B loses 10 health, with a new total of 90 health
So, if we wanted to roll back, we would:
1. Lookup the highest height in our system that relates to the new tip
2. Copy the old state of droid & inventory back into place based on this last good block
New Pros As it turns out, this strategy gives us the backbone for eventually exposing a feature that allows users to view the full history of a droid over it's lifetime. Watching it evolve, or get it's ass handed to it, block by block.
New Cons This strategy will no-doubt start to create a really big table over time, especially as the number of users grow. Designing this table properly early on in your development will be something you look back on fondly.
At least, we think you will look back fondly on your grand design. We certainly didn't do this properly, so we get to deal with upgrading a giant F*&$-off table into a better system now. We'll write up a much more technical post in the future about how we are now using PostgreSQL's new built-in
PARTITION feature.
What if Coindroids already sent out coin?The other very fun, and potentially devastating part about forks. Yes it's possible that we sent out a completely valid transaction, maybe to reward a player for a kill, or to reimburse overpayment on an item. Now that we've re-processed up the new real chain we wish we hadn't. But wishing doesn't get you too far when it comes to immutable ledgers.
Want to know how we solved this problem? Check back next time for another volume of Fork'n Around.
