Last year I was working on a new sort of blockchain that would enable instant transactions. I'm dumping some info here so it's searchable and maybe inspires someone or w/e.
The basic idea is that each TX has a small PoW attached and is 'mined' instantly. Larger miners (who are in it for the money) mine TXs with *large* PoWs and point back to other 'work heavy' blocks but also link back to these 'lighter' txs from regular joes.
The blockchain is actually a DAG instead of a linked list.
One challenge was ordering txs, I think I've come up with a pretty good solution that's included in the source here:
https://github.com/XertroV/quanta-test/blob/master/quanta.py#L204. Basically it recurses down the heaviest path until it reaches a common point between all paths, then it recurses down the second heaviest path till it hits a block in the first path, and so on down all paths. In this way it can operate as a DAG, has a deterministic ordering, and not worry about people inserting blocks into history or anything like that (though there might be a DoS angle here on computationally heavy re-orgs).
It relies on treating the pool of workers available as producing a *stream* of work, rather than the discrete blocks that we're used to. By treating it as a stream you get (nearly) infinite granularity, enabling near instant TXs. You still have to wait an hour for a good confirmation, though (like all networks).
One downside is all TXs have lots of metadata about links so they can be 500 bytes for a simple TX.
Source code is here:
https://github.com/XertroV/quanta-testI can't remember if it works or not when you run it.