A bug report for decentralized block chains.
However, there is a third category of double-spends that is barely documented as far as I can tell: double-spending through full node consensus failure. There is a risk that a significant portion of nodes fall out of consensus and this can be taken advantage of to double-spend bitcoin. No one has quantified this risk, therefore we cannot claim that Bitcoin solves the Byzantine Generals problem.
Below is a bug report with potential workarounds.
As you know, bitcoin nodes accept the valid block chain with the most work. Now, imagine that there is a majority consensus (eg. 60%) among network nodes that a non-backward-compatible protocol change will happen at block height X and that these nodes are not running the reference client (not Bitcoin Core). This change can be, for example, a change to the PoW algorithm to mitigate miner centralization.
A block chain making non-backward-compatible protocol changes (fromhere)
After block height X, bitcoin nodes all follow the valid most work chain because there can only be 1 valid chain.
At block height X, bitcoin nodes will disagree on what valid means and perpetuate two chains of bitcoin. For example, the majority-supported chain may claim that valid means uses s-crypt hashing and the minority-supported chain may claim that valid means uses SHA-256 hashing. The majority of nodes will relay new-PoW blocks but the Bitcoin Core nodes will relay a differentstill validblock chain, where valid means something different.
The risk is a loss of funds through double-spending. The potential damage is hard to estimate because double-spending can happen for as long as the majority-supported chain disagrees with the minority-supported chain on the definition of valid. Unlike a hash-rate double-spend, this is not necessarily an attack. It is more simply a system failure.