It's hard to see what the benefits of allowing empty accounts to be on the blockchain are. This was a known subtlety (see "note: there is a difference between zero-balance and nonexistent") and exploited by a "state-bloat" attack.
What were the technical challenges why the protocol didn't prevent them in the first place?
What are the "flaws" in the protocol as mentioned in the State Clearing EIP158 rationale and this question?
What were the technical challenges why the protocol didn't prevent them in the first place?
There weren't any particular technical challenges. It was simply an oversight, "a mistake, a flaw in the protocol."
This was a known subtlety (see "note: there is a difference between zero-balance and nonexistent")
It was always understood that zero-balance accounts can exist as a node in the state tree, whereas nonexistent accounts do not have a node in the state tree. Creating a new account (whether zero-balance or not) will also create a new node in the state tree. Making new account creation expensive was the reason for the noted extra gas cost:
CALL has a multi-part gas cost:
* 40 base
* 9000 additional if the value is nonzero
* 25000 additional if the destination account does not yet exist (note: there is a difference between zero-balance and nonexistent!)
But the oversight was that there was another way besides CALL to create new accounts, namely SUICIDE, which circumvented the 25000 gas surcharge. This was exploited by the "suicide bomb" DoS transactions. For example, the first one created many new zero-balance accounts, from the 0x00..05 address to the 0x00..2170. That's about 8560 accounts for only 800000 gas, or around 95 gas per account (much cheaper than the 25000 gas per account that it would've cost using CALL).
What are the "flaws" in the protocol as mentioned in the State Clearing EIP158 rationale and this question?
The main flaw was the ability to cheaply create new accounts with SUICIDE, which the DoS attack exploited to bloat the state. If the protocol had only specified that state tree nodes are not created for zero-balance accounts, then the SUICIDE attack could've still been exploited by transferring 1 wei to the new accounts. To fully prevent the attack, the protocol would've also had to specify an additional gas cost when new accounts are created regardless of how they are created (whether by CALL or by SUICIDE). This oversight that was fixed in EIP150: long-term gas cost changes:
If SUICIDE hits a newly created account, it triggers an additional gas cost of 25000 (similar to CALLs)
Since users and miners need to store the entire state tree in order to calculate the state root and validate blocks, every new account increases their required disk space. The DoS attack increased the total number of accounts to around 20 million, or 30 million state tree nodes (the structure of the state tree is not one-to-one between accounts and tree nodes), which required around 10 gigabytes of disk space, depending on the particular client implementation. With state clearing complete, the total number of accounts was brought back down to 772530, or 3.3 million state tree nodes, which require around 1 gigabyte of disk space.
