Substrate depends on finality for its block production by default. Looking also into the application database layer with blocks, it seems that block reverting isn't normally possible with arbitrary depth. Does that mean it's impossible to have probabilistic finality in substrate?
Context to the problem:
In Bitcoin, Ethereum and other probabilistic-finality-based chains, the chain can reorg with as many blocks as the system needs. It can even be thousands of blocks if need be. Consequently, the state transition function (using substrate terminology) must be reversible. Hence, when a reorg happens, blocks are reverted in a way where (in bitcoin), outputs are removed and inputs become unspent in the UTXO set.
In the most abstract form, this can be functionally represented as:
Apply(StateA, blockX) -> StateB
Revert(StateB, blockX) -> StateA
This strictly requires that it's known how a revert is done, given a block. In bitcoin, this is easily achievable as we know exactly how to "unspend" inputs and delete outputs by a simple database change.
The current situation in substrate (as far as I understand it):
But in a general purpose chain like substrate, this cannot be done without storing the set of state changes per block over the whole blockchain, which has a huge diskspace/memory requirement (called archive-pruning mode in substrate). Or, the developer has to provide the mechanism for reversibility, which doesn't seem to be a requirement in the pallet standard interface, as people are only required to provide the changes that have to be done in the database only when applying a block, not when removing/reverting a block from the tip of the mainchain.
As can be seen in the database handling of a block, it's not possible to revert an arbitrary number of blocks the same way it's possible in probabilistic finality blockchains (unless pruning mode is archive, which is impractical to assume for all users). Substrate seems to assume that finality is an inevitability, where in the technical underlying database/storage, the concept of "canonicalization" is defined. A canonicalized block is a block that's technically irrevertible/irreversible, because its state transaction function has been applied to the database. And given that pallets don't define any mechanism for reverting extrinsics/transactions and hence blocks, there's absolutely no way to revert a block after it gets canonicalized. So, substrate stores a tree of all possible block candidates that are not yet canonicalized/finalized.
This caused me lots of confusion because it seems that substrate does support proof-of-work consensus, but the canonicalization concept completely eradicates the possibility to revert blocks, which is typically a requirement in proof of work due to its probabilistic nature. (and on a humorous note, congratulations, 51% attacks with shadow mining are not possible anymore :-), but on a serious note, spontaneous contentious forks and chain-splits are possible if a group of honest nodes get isolated long enough, which is not that unrealistic, e.g., if a country decides to block the internet for a few days or block the node ports for political reasons, which should never be a problem in normal proof-of-work systems).
The question
This question is based on the requirement of building a substrate-based blockchain that follows bitcoin.
Is it possible to make substrate consensus completely operate with correct probabilistic finality (without canonicalization and with proper definitions of reversible operations)? What would have to be changed? Is it a realistic change or is it drilled to the bones such that it's practically impossible? I honestly don't know where to start and would like to get an overview of the changes that have to be done to make the substrate blockchain work with probabilistic finality.
I will post this answer since the only other answer available in this post is wrong and the comments seem to be overseen.
The answer is no. Substrate, with its canonicalization of the database that can happen even before finalization, it's not possible to have a proper proof of work blockchain, as it's impossible to reverse blocks after canonicalization.
It was decided by the management of the project I'm working with to move off substrate because of this issue. Technical details here.
I'm posting this information about substrate regardless of whether this design good or bad, it's what it's. I can see pros and cons to it.