I know it has been quiet here ... but we've been working hard on getting the project forward. I'm very excited to share with everyone now an important improvement that we've made to the original game-channels concept, which will further boost Chimaera's ability for trustless off-chain games:
Improved Game ChannelsScalability is a critical difficulty for blockchains in general. If one tries to put entire game worlds (like Huntercoin and Chimaera) onto a blockchain, this is even more true. Therefore, off-chain solutions are critical for the future development and success of these projects.
A possible concept for off-chain interactions are game channels [1]. In the simplest case, they can be used to perform two-player, turn-based games. It is possible to generalise the concept to other situations, but for the purpose of this post, we will consider this situation for simplicity. (The same ways to generalise the concept as described in [1] can be applied, though.)
Roughly speaking, such a game works like this:
- Both players send a transaction to the public blockchain which locks the prize money contributed by either player and fixes the conditions of their game as well as a key pair for each player.
- The actual moves in the game are sent privately between the two players, signed by their keys.
- Ideally, both players agree on the final outcome, and sign a release transaction together that pays the locked funds to the winning party.
- In case of a dispute (one of the players stops to send moves, sends an invalid move or claims that the opponent did any of that), a special "dispute transaction" is sent and mined into the public blockchain. This transaction publishes all moves, so that the "general public" can verify the claim and determine who is correct.
- The disputed player gets a certain window of time to respond to the dispute, and may resolve it by sending a valid next move (again to the public blockchain). In this case, the game continues privately between the two players as before.
- If no dispute resolution is mined before the deadline, the dispute is deemed successful by the network and the locked funds are paid to the disputing player.
In theory, this system enforces that the game is performed fairly and in a trustless manner. No-one can abuse it to "steal" the locked funds without properly winning the game (or if the opponent stops to respond).
However, an attacker might repeatedly wait with sending a next move, let the opponent dispute, and then resolve the dispute. This is not a "rational" behaviour, but it could be used to annoy players on the network and bloat the blockchain in a bid to discredit any project built on top of game channels. This kind of behaviour would also force (both) players to repeatedly pay transaction fees to the miners for including their dispute and resolution transactions.
We believe that there is an evolution to game channels that fixes this issue. Before we can describe this protocol, let us introduce "ephemeral timestamps" first -- the core technology that enables the improved game channels.
[1]
http://www.ledgerjournal.org/ojs/index.php/ledger/article/view/15Ephemeral TimestampsEphemeral timestamps are a feature of a blockchain-based P2P network, which can satisfy these properties:
- Nodes in the network can submit an arbitrary piece of data D for "ephemeral timestamping". This gives them a timestamp for the current time T.
- At a later stage, the timestamps obtained can be used to prove to the network that another node knew (or could have known if it would have cared) D at time T. Such proofs can, in particular, be used in the consensus rules for transaction verification.
- Such timestamps only need space in the blockchain when actually used later. If not used, they burden the network only temporarily (processing cost and storage), but can be discarded after some time (thus "ephemeral").
- Similarly, timestamps are free for nodes to send. Only using them later requires a transaction fee. Nevertheless, miners still have an incentive to process all timestamps (or at least nodes can incentivise miners to process theirs).
The actual implementation of this feature looks like this:
- A timestamp request sent to the network contains the data D a node wants to store, as well as an entry promising a certain fee upon usage of the timestamp in the future.
- Nodes on the network (in particular, miners) keep a memory pool for timestamp requests in addition to transactions.
- When building a block, the miner selects timestamp requests it likes (for a rational miner those with the highest fee promise), and creates a Merkle tree with them. The Merkle root hash is included into the block.
- The full Merkle tree, on the other hand, is not part of the core block data. Thus, at this point, the timestamps are not directly part of the blockchain, and do not cost any blockchain space (except for the constant overhead from the root hash).
- However, nodes expect blocks that are not too old to be accompanied with the full Merkle tree when they receive them over the network. Otherwise, the block will be considered invalid. (Roughly speaking, this should apply to all blocks the node receives while running "fully synced". During the initial blockchain sync or when catching up after being shut down for some time, the node accepts blocks without the Merkle tree.)
Note that this does not cause issues with blockchain reorgs, either, if the time interval for which it is kept is not too short. There is no fundamental harm in requiring the data to be kept for a day or a week (it is still ephemeral and won't lead to eternal blockchain growth), so that one can set the keep-time long enough to never see a reorg beyond that time. - To actually use a timestamp, a node has to send a transaction that includes the Merkle branch linking the data it timestamped to one of the blocks in the chain. This transaction also needs to pay at least the fee promised in the timestamp request to the miner that originally confirmed the request, otherwise it is invalid. It may also need to pay an extra fee on top for confirming the transaction itself, of course.
Finally, let us discuss how this implementation satisfies the claims:
- Since the full Merkle tree of timestamping data is sent around the network at the time when the block was originally propagated, every node in the network that follows the regular rules sees all data. This guarantees in particular that it was able to know the timestamped data around the time the block was created. (This assumes that no partitioning-attack is going on and that propagation of a new block throughout the network is relatively fast. Both assumptions should be valid for a healthy P2P network.)
- The full Merkle tree can be discarded after some time, so that timestamp requests only burden the network temporarily and are not immediately part of the blockchain.
- When the timestamps actually need to become part of the blockchain to prove something for consensus purposes, the node is forced to pay an appropriate fee. This incentivises miners to actually include high-promising requests into the ephemeral Merkle tree, since it creates at least some probabilistic expectation of earning the fee later. (See the next section for some more discussion about the incentive structure.)
The Incentive with Fee PromisesLet us now discuss the incentive structure provided to miners by the "fee promises" attached to timestamping requests. It is of course very important to give miners an incentive to include requests into their blocks, and it is not directly clear that this is possible without actually paying a fee for the mere request alone. However, we believe that the system described above provides sufficient incentive for miners.
The idea is this: Even if a time-stamping request does not by itself pay the miner a fee, there is a certain probability p that the user creating the request will actually want to use it later (as otherwise it would be pointless to create the request in the first place). p can actually be measured in a real system by the miners and/or the network. Then, since the user needs to pay at least the promised fee F to the original miner upon usage of the timestamp, the miner can (on average) expect a gain of p F for confirming the request.
It can of course be that p is quite low, but this just means that the fee promise F needs to be high enough to compensate the marginal cost that the miner has (e. g., in longer propagation time of its block). Furthermore, we believe that this cost will be rather low, since the processing of timestamp requests should not be very expensive to the miner and the network.
However, one potential issue remains: Even if there is some overall average probability p that each request will be used later and thus actually pays fees, a particular user could still send an unlimited number of timestamp requests for free with the intent to just DoS the network and never pay any fees. If this turns out to be a problem, we can solve it by limiting the rate at which individual users can send requests: We can require that each time-stamping request must be signed by the private key of an output holding some minimum amount M of coins, and allow each such output to be used only for one request in each block. With a maximum number C of coins in existence, this implies a hard cap of C / M timestamp requests per block. Thus, as long as there are at least some legitimate users in the system (which have a non-zero probability of using their timestamps later on), p will be bounded from below and thus provide a non-zero incentive to miners for including every timestamp request.
(Instead of a strict rule that each output may only do a single request per block, one could also leave the decision to the miners. By requiring deposited coins, one adds "valuable identities" to the requests. With that, miners themselves can decide upon the rate of requests they accept from each such identity, and how they limit spam.)
Finally, note that if the ephemeral timestamps are used in a setup for game channels as described in the introduction, then the security deposits come for free: In this situation, one might require each timestamp to be linked to one of the game-opening transactions and signed by one of the keys published by the players. This leads to a similar effect on adding a "valuable identity" and preventing abuse, while not requiring any additional effort on the side of the users.
Game Channels AgainLet us now finally come back to the topic of game channels, and discuss how ephemeral timestamps as discussed above can be used to improve them. The idea here is pretty simple: For creating and resolving disputes, we no longer require nodes to get certain transactions mined. Instead, they should send the corresponding data as timestamp requests. By doing so, there is no actual cost in fees as long as all disputes get resolved. Overall, the dispute process between Alice and Bob looks like this:
- As already mentioned, if Bob stops to send his next move to Alice or sends only an invalid move, Alice sends a timestamp request with the history of the game, showing that she last made a move and is now waiting for Bob.
- Since this data is published to the whole network, Bob will certainly receive it as long as he is still paying interest to the game. In this case, he can send his next move in a dispute resolution to be timestamped as well. To be valid, the resolution needs to be timestamped at most N blocks after Alice's dispute.
- If all is well, Alice has now received a next move from Bob, and the game can continue privately.
- If Bob does not send a resolution in time or if his move is actually invalid, Alice may send a claim transaction to the network after, say, 2 N blocks. This transaction uses her original dispute timestamp to prove that she opened the dispute sufficiently long ago. She pays the required fees out of pocket for this transaction.
- Alice might try to cheat Bob out of the prize money by sending a claim even though Bob sent his next move. In this case, Bob can create a counter-claim with his timestamp. If the move was valid and sent in time (which can both be judged by the network), then he can prove that Alice' claim was fraudulent. In this case, he gets the prize money unlocked and paid out by the network.
- If, on the other hand, Alice' claim was right, she gets the prize money paid out after a certain amount of time in which no valid counter-claim is received.
This procedure ensures, in particular, that as long as a player is honest himself, he need not pay any fees except if successfully making a claim or counter-claim. In this case, he also gets the prize money for sure, which then ideally pays for the fees and some. So a dishonest player can never actually cause damage to the honest player, except for delaying the game to a certain limit.
There is one tiny issue that remains, though: If a player determines that her chance of actually winning the game is very small based on the current state, she may decide to stop responding instead. This doesn't cause any extra loss for her and the opponent will get the prize, but will need to wait a bit longer for it and also needs to pay some more in fees. This, however, is probably not a very bad situation, and we believe that it won't be a big problem in practice. (Since, as mentioned, it is at least ensured that an honest player can never have any actual loss, and gets at least the prize money minus fees if the opponent misbehaves.)
