Possibly... Proof Of Work is already in the protocol...You can test it with Nostrid. https://github.com/lapulpeta/Nostrid
Discussion
Good point, if being verified and using paid relays become the standard, that might eliminate the need to combat spam with this kind of "collateral".