Don't be so concerned about botnets and ec2, botnets were and will always be out there, just accept it, if you got the criminal energy to control a 100k+ botnet you can mine whatever you like no matter what you do - this is starting to become a DRM vs warez analogy which always ended bad for the important part, the user / customer. And ec2 is always only a viable option at the beginning, it is not cost effective pretty soon unless you front a serious amount of cash which in turn could have bought rigs aswell - same same but different
Captcha's would make it so a human would have to be involved in the process of mining. Botnets cannot easily solve these captchas yet and when they can an update can change them. The original Bitcoin protocol has an alert functionality built in to tell the user to update and this could be extended to include alert captcha. That is just one solution. Another is to shuffle the algorithm in such a way that a botnet cannot optimize for it.
One thing about botnets is they run unattended. A popup alert which asks (are you a bot?) with a captcha would make it a lot harder to do botnets even if not impossible. I'm sure there are more creative ways too.
A solution to botnets is a human user authentication protocol. To come up with an optimal algorithm I recommend a SWOT analysis of the latest botnet technologies. What are the strengths and what are the limitations of botnets? The knowledge of limitations of botnets should be exploited in the protocol design. One example of a strength of a botnet is that it allows a central controller to control a bunch of computers at a time, potentially millions. The weakness of a botnet is the central controller is usually just one person or a group of people in an IRC chatroom and they cannot monitor 100 computers in real time 24/7.
The easy solution is to build in a reverse turing test and require every human miner solve the puzzle before they are allowed to mine. The botnet operator would have to solve each individual puzzle on each computer manually which would be as time consuming as the person using digital ocean. If the puzzle is designed right the botnet operator would not be able to solve it easily at all. For instance a lot of botnets rely on a keylogger so if you use the mouse for data entry then it would defeat the botnet. Additionally a game which is really simple like tic tac toe or something similar would be helpful as well. The most extreme solution is to just link all mining to a Keyhotee ID and have signed mining.
I don't know what algorithm would work best for an anti-botnet solution but I think it is necessary to find one if the DAC idea is to work long term. If there are botnets then proof of stake voting is impossible as it would be impossible to determine whether a real human voted or a botnet. The voting could be accomplished by code voting, but proof of stake is ruined if botnets have the highest stakes.
Unless you come up with an idea how to prevent a botcontrolled pc from mining but a normal one not without crippling everything and making the whole process a pain in the ass, thats the way it is and you are just whining because you think something is unfair - welcome to the real world.
There may be ways but none are easy to implement without bringing in some level of centralization. If you use captchas it would require either centralization or an external data stream. If you do some scheme with cellphone txt message authentication then the miner loses anonymity. Eventually the best solutions will make mining unprofitable for botnets and make mining a process where a human being has to attend to the process and interact with it somehow.
The lottery mining idea is great because it increases human interaction with the process which exploits the fact that botnets cannot gain any benefit from it because botnets don't have any human interaction capability. So a botnet is not going to benefit very much from a lottery like they would from a mining pool.
This is a good time for experimentation to find out if its theoretically possible to provide disincentives for botnets and incentives for humans.