Proof of Stake, aka corporate democracy, a form of federation, is one model for semi-trust situations, one that only works when that power doesn't include continuing to consolidate position, which leads to corruption. It can be implemented on top of Bitcoin using time delay transactions and/or threshold multisig.

Proof of Storage is pretty much useless, though Chia and Spacemesh projects both use it as a form of PoW, they don't prove actual storage but rather, consumption of storage space, by cryptographic problems that are easiest solved by using large amounts of storage. Proof of Storage Usage might be a more accurate description.

Proof of Delivery is a bit easier, but still very knotty. It's my view that it's also a dead end. Part of the reason being that it inevitably involves random transmit requests that don't actually relate to real usage.

In Indranet, what we are using is something which might be more accurately called "Proof of Service". The service being the relaying of data across multiple nodes, of onion packet data that nodes cannot identify either the origin, their position in the circuit, except when they are delivering exit relaying service. The onions are constructed so that they form a hexagonal graph starting with the client and returning to the client. In this way, by receiving the final message, which is encoded by the client, of confirmation of delivery, it can then mark off all the nodes in the circuit as being functional and cooperative.

The secret sauce in the method essentially requires the anonymity to take away that "this is a test" awareness by the relays. I'm inclined to say that fundamentally the two strategies you speak of wind up being examples of the travelling salesman problem, similar in some ways to the routing problem in Lightning Network.

I'd be inclined to say that the only way Nostr can have a similar, provable delivery scheme is also the same as how it works for LN and Indranet: there has to be intermediary relays, the signals have to be anonymised in order to eliminate the possibility of relays recognising they are just being probed and to satisfy the probe but not do actual work.

My intuition is that actually, there won't be a robust mechanism to prove either delivery or storage in Nostr unless you can do it via a "secret shopper" scenario that Indranet enables. The darkness of the network is required to make it work. The cost of sending messages is also required, or you will fall vulnerable to sybil and spam attacks.

I am pretty sure that Indranet will prove to be the missing ingredient that makes a user-funded, self supporting Nostr relay network possible. Yes I'm working as hard as I can on getting it out there, but I really get this sense that integrating with Indra would be the key to enable trustless service payment for Nostr relays. I have thought a long time about all of these problems, and the darkness of the network prevents "for show" "proof of service" because the relay does not know who it is delivering to.

In Indranet, relays advertise services, and set a price on them. So they are also incentivised to perform the work because the relay operator benefits. I think that Indranet will solve this intractable problem not just for Nostr but every similar kind of system where you simply cannot trust relays to actually deliver what you paid for. This payment is inside the Indranet protocol, and does not require the external protocol to have any awareness of it.

It would require some small extra considerations in the design of the Nostr protocol to make it aware. That is, you would send packets via Indranet to the relay, along with a payment via side channel that is identifiable as being related. The node would never be able to determine that the request comes from the payer in other situations, and so it either would deliver it or not, and the payer would then have proof of service as requested. I don't think it would require tight coupling with Indranet, but rather, would involve some kind of escrow scheme where your payment can be revoked for a time afterwards using cryptography that proves the payer did not see the result it expected, this is the complicated part. But on the Indranet side, a payer's client could then also mark the node as faulty and not use it either for anything at all, thus cutting at the bottom line of the paid Nostr relay.

One key thing is the idea of "streaming" the payments on a regular basis. This lowers the cost for taking the risk to pay it and thus also enables the payer to take their business elsewhere. This is how Indranet's session payment system will work also. New nodes in Indranet have lower chance of being selected to open sessions, mitigating the fly by night problem, and clients only pay a little at a time, meaning if service is unsatisfactory, the relay loses a customer.