I'm playing around with the idea of a blockchain where both the proof-of-work and verification steps are NP-hard. It seems the NP-hard verification step can be resolved if you allow for multiple parallel blockchains with different sets of blocks in the head of each version. This of course creates another problem of trying to reconcile multiple blockchains in a secure manner.
The go-to proof-of-work method of reconciliation seems to be "take whichever chain has the most work in it," but is there anything out there already which allows for the reconciliation of the blocks without a loss of proof or transactional data?
