What's the incentive created in order to justify the computation?
Did you know that the Tor Project is close to implementing proof-of-work as a method of DDoS prevention?
https://darkdot.com/articles/tor-ddos-leads-to-proof-of-work/
Their PoW algorithm was built by the same main developer as that of Monero (RandomX) and shares many similarities:
github.com/tevador/equix
Very excited to see this built out as it poses the most promising fix for the ongoing attack against the Tor network. The current (WIP) merge request for PoW support in Tor can be followed here:
https://gitlab.torproject.org/tpo/core/tor/-/merge_requests/702
Discussion
A working network is the incentive, and the cost for a normal user is negligible, likely won't even notice PoW being done in the background at all.
For a service under heavy attack that ups the difficulty for the hidden service it may take a few seconds to connect initially but then just be like normal Tor browsing.
PoW is only done during circuit creation, not all the time.