One solution to the Sybil problem would be to only allow a certain amount of "providers" in the network. Say, not more than 10,000 (exact number to be determined, you could start with less)

Then, have some sort of proof of work system through which interested parties generate a "provider node" token *. Make it extremely difficult, exponentially, so that it is very hard to become a provider. Make provider nodes expire after say 1 month, but allow existing owners to renew their nodes once they have them.

Allow banning of nodes, effectively making them lose their provider node if they become untrustworthy, and return the node to the pool, giving someone else a chance to run a trusty provider node.

* As an example, you could start with a fork of bitcoin, allow people to mine coins which they can use to buy provider node tokens. Say the first provider node costs 100 qucoins, the second 200, the third costs 400, etc.