BIP 113 mentions:
Existing consensus rules guarantee this value to monotonically advance, thereby removing the capability for miners to claim more transaction fees by lying about the timestamps of their block.
Can you please explain where this guarantee comes from?
The guarantee comes from the consensus rule that a block's timestamp must be greater than the median timestamp of the last 11 blocks. This median timestamp is known as the median time of the block. Because the median is used, and because timestamps of each block must be greater than their median time, the median time will always increase from block to block. This also means that the median time for a block is set prior to it being mined.
Block timestamps are allowed be to slightly off (up to 2 hours). This poses an issue for locktime transactions, since a miner could claim the block timestamp to be up to two hours in the future, and thus include lock time transactions before they are actually supposed to be mined.
By using the median time over the last 11 blocks, the miner's own choice of timestamp is irrelevant, since the validation is conducted against the median of the previous 11 blocks, which the current block's miner cannot control.
