The article seemed pretty open about major mistakes that ShapeShift made and lessons learned. It's a good postmortem to learn from, and far more open than most would have posted.
Everything should be fully encrypted such that even a breach of trust from the hosting provider would not compromise your data/funds. I know this is hard to do, but it's mandatory when you're handling digital currency.
If you don't want to trust your hosting provider with anything, you have to own the hardware.
Because they control the hypervisor, they control everything. That means they have as much access and authority as the code that you are running on their servers have. So the only way to protect yourself from them is to limit what your servers (deployed on their cloud) can actually do.
So for instance you could have a secure backend server on a dedicated host in a trusted environment, with the cloud servers using an API to the backend server. If the API is suitably secure then the cloud servers could be compromised without allowing them to directly issue invalid commands in the same way the backend server could. Then you could use the cloud to scale out your web frontend without compromising yourself.
The same is true of hardware on the dedicated host (such as the "Trusted Computing" Module) that you do not control. If that (or the BIOS) gets compromised you might not even know that your host is no longer secure.
There's always the in-memory vulnerability, which is harder to mitigate, but requires an attacker with physical access to the hypervisor, so it's much more difficult to execute (as most meat-space hacks are).