> I'm still trying to figure out the best design for such a system.

Easy answer: distributed consensus, à la Bitcoin.