PoS, while useless for securing a currency, will do for this network. The advantages with PoW become disadvantages here: we actually want maximum speed, not "security" (in this case minimal bad actors). A small fee for relays would probably do nicely. Eg. a massive spam attack would require an equally massive transfer of BTC to the relay operator, which they can then use to fight the bots with a profit.