The solution I found is to assign a hash-signing private key. The node who owns this key verifies that the ramhog hash for a particular block is accurate, and then signs it. Any node that trusts that key uses the signed hash instead of computing it itself. All nodes propagate these signed hashes so that they are easily accessible.
Some quick questions. Sorry if I am missing something here:
Is there one hash-signing private key shared by all nodes (A) or each node generates its own priv key (B) or is there a single node with the capability to sign (the only node with the priv key) (C)?
In case A: What would happen if someone infected the network with many nodes using a different priv key?
In case B: Shouldn't there be a web of trust for all those priv/pub keypairs? I guess this web of trust should be built outside of the p2p network. Each node should sign the public keys of the nodes it trusts.
In case C: Doesn't such a centralized infrastructure make the network vulnerable to ddos attacks?
After reading more carefully, I think there is one node with signing capability (has the priv key). Making it decentralized would be complicated. Here is a quick idea how it could be possible.
We would have to utilize two keypais, one used to verify hash signatures and another used to verify nodes. So:
Keypair A
privA: (not secret, shared by all nodes, used to sign hashes)
pubA: (not secret, shared by all nodes and clients, used to verify hash signatures created by privA)
Keypair B
privB: (TOP SECRET, used to sign the pubA of nodes OFFLINE)
pubB: (not secret, shared by all nodes and clients, used to verify signed pubAs)
So, before a hash is accepted by a client as trusted, the chain of verifications would be:
1. client uses public key B (pubB) to verify the signature on public key A (pubA) of the node, which has been created by private key B (privB). => Success -> node is a trusted node of the network. In other words, the node's pubA is verified as authentic.
2. client uses public key A (pubA) to verify the hash signature created by private key A (privA) => Success -> hash is trusted
The big problem is where private key B should be hidden safely. This key is the root of all trust in the network.
Anyway, just an idea. Written quite fast. I hope I haven't written anything stupid.
Corrections are welcome.
The hash signing can happen anywhere (unknown to an attacker) and there can be more than one hash signing node using the same privkey to sign, so DDoS doesn't seem to be the issue. If you're going to have an algorithm that takes forever to verify and now you're taking shortcuts something has to be relied upon to verify for you. Maybe have all the active nodes sign, and have the nodes instant-ban a node that signs something invalid. The default ban times on shiny are very harsh so someone would need many unique IP addresses to even mildly annoy the network for a very short period of time. It would be better if there was a financial penalty for signing something invalid but I'm not sure how something like that can be implemented. Maybe each block the winner gets to sign, and forfeits his block reward (and gets banned) if his hash verification is invalid.