SNARKs and Proofs of faithful execution

Various SNARKs things would be nice, such as:

blockchain becomes "one big snark" instead of a growing data set forever, SNARK proofs would be nearly instantaneously verifiable although costly to construct a new proof (which is itself problematic...)
Construction of easy-to-verify proofs that transactions selected by a miner were all following consensus rules
proof that consensus rules were followed or are being followed by a certain participant
proof of validation
"SNARKs" without SNARKs?
SNARKs without trusted setup?

CPU mining

It would be interesting to give a way for CPU mining to give subsidy rewards to anyone, even for absurdly weak PoW.

Consensus-enforced sub-satoshi micropayments maybe? extension blocks? etc.
transactions + PoW + new consensus rule that transactions must contain PoWs (and the PoW could be something other than sha256d), also the PoW could be related to the public key or something, "transaction PoW miners" could get paid partial fees for their CPU mining efforts by the transaction signers

Fraud proofs

fraud proof
non-fraud proof
what to do about non-publication of data? Parties that have incriminating evidence (against themselves) might not be incentivized to publish that information.
Need fraud (or non-fraud) proof of every consensus rule
How to recover consensus after mining cartel fraud or multisig fraud on a proof-of-publication platform? You shouldn't keep using the same consensus history, so what do you do instead?
consider federated multisig groups, p2sh escrow stuff, etc.

Push problems and bottlenecks to edges (wallets/nodes)

(1) wallets provide UTXOs and proofs when spending coins, see 'transaction linearization' proposal. Recipients are responsible for checking validity and proofs. Bandwidth-consuming proof for the occassional spend of old coins.
(2) Interactive protocol and proofs between 2 nodes to do secure multiparty computation, to prove that all parties are running bitcoin consensus validation rules. Don't send coins to someone who isn't running bitcoin consensus rules. Or, alternatively, don't send coins to somebody who isn't at least participating in CPU mining.
(3) Transactions could encode proofs of consensus enforcement and validation work by their nodes (either sender or recipient, probably sender). Consensus-enforced rule could be introduced that transactions must conform to this format?
(4) utxo set + private key + snark could be used to show that a node at least has a utxo set that they can do computation with (or that they are silly enough to outsource their private key...) however it only shows that they have the utxo set data, not that they are doing validation work with consensus rules... oops.

"coinbase txout hashcash"

Proof of consensus rule validation: must be easy to verify, computation must require exact consensus rules.

Full node incentives

Could there be a more direct and more obvious incentive to run a full node (validating all blockchain data and running consensus rules), other than security? Perhaps lotteries ?

joinmarket or some other coinjoin implementation directly in Bitcoin Core (could provide income to users, although it's not physically coupled to running a full node itself)

Economies of scale and PoW

There is an economy of scale for doing Proof-of-Work and probably any other conceivable computation. This might be bad? How to fix...

Recovering and spending tiny UTXOs (below the average transaction fee)

There might be a way to "sweep" unspendable UTXOs into schnorr multisig pools. This is useful when early UTXOs were created and later the average transaction fee becomes perpetually high. See http://gnusha.org/bitcoin-wizards/2016-11-24.log for more details.

transaction format where it is possible to have "one signature covering multiple inputs"