Even though there should be gameplay growth, there is a danger in adding too much -- which leads to the next consideration.
The player should not earn any upgrades or abilities that supersede player skill. Because the player's skill is the main factor in the game, giving the player something that undervalues skill can break the game. In Ninja Gaiden, the developers gave the player the ability to counter-attack after the first few stages. By timing their blocks, players could avoid all damage and deal it back to the enemy. The developers saw that this was making the game too easy and removed the feature for Ninja Gaiden Black, as they wanted the player to see that constant movement was required to win.
That is why health upgrades are the safest bet; they give the player a greater buffer between life and death, but don't get in the way of player skill. Many of the bosses in Demon's Souls can kill the player in a few hits; having a greater health bar may give the player a little more of a chance to survive, but if the player doesn't learn how to avoid the attacks, they'll lose no matter what.
The flipside of this consideration is that you should never change the game in a way that negates previous mechanics and skills. Getting rid of a mechanic that the player spent time learning and improving at will make the player feel like that wasted their time -- and this hurts the design.
You can find an example of this in Bayonetta. At the start, the player is introduced to the concept of "Witch Time". By dodging attacks at the precise moment of impact, the world slows down for the player, allowing for an increased window for attack. Slowing down time also allows players a chance to hit enemies which are more agile then the player.
However, halfway through the game, the designers introduce "gold-plated" enemies, whose attacks will not trigger Witch Time if the player dodges them. Because Witch Time is one of the only two ways of avoiding damage for much of the game, players are left severely handicapped while fighting these enemies.
The last consideration is that even though these titles are harder compared to other games, it is alright to throw the player a bone by implementing a difficulty selection system. Granted, an "easy mode" in a game with Darwinian Difficulty is still harder than in normal games, but it does give less experienced players a chance to "pump up" before trying the higher settings. Ninja Gaiden Black featured multiple difficulty levels, ranging from very easy to experts only.
Ninja Gaiden Black
Putting all the considerations together, we can take a closer look at Ninja Gaiden Black and Demon's Souls, and what makes them challenging.
Ninja Gaiden Black's enemy design is built around forcing the player to keep moving. The way the designers did this was giving just about every enemy (including bosses) a grab attack. Grab attacks are unblockable and do immense damage. Some grab attacks are telegraphed, while others are used immediately once the player blocks a few attacks by an enemy.
The sooner the player masters the dodge roll, as oppose to regular blocking, the better. As the game goes on, enemies will become faster, and the challenge of "sticking and moving" will become greater.
The challenge culminates in two ways. First are mirror battles. Players who are skilled enough to play on the higher difficulty levels will run into battles with their doppelganger. The doppelganger will use one of the player's weapons, and all the same tactics and techniques the player has, and it will be up to the player to deal with an enemy who is their equal.
Second, regardless of the difficulty level, before the player can fight the final boss, they will be put through a gauntlet of boss fights and arena battles. Taking too much damage early on will leave the player in a bad position to finish the fights, forcing the player to get as close to a "perfect run" as possible. On the harder difficulty levels, the gauntlet is extended with more battles and bosses, including one that was never shown to the player until now.
The unique boss is easily one of the toughest enemies in the game, as mastering the timing needed to dodge attacks is required for both offense and defense. Her main attack is a beam of energy that can only be avoided by dodging just before she uses it. To complicate matters, only attacks issued after dodging her moves will connect. Getting through this fight without a scratch requires "master level" play, and is a sign that the player is good enough to finish the game.
Moving onto Demon's Souls, the game also requires players to understand all defensive options available. To avoid damage, players can block attacks, dodge out of the way, or attempt a riposte to counter. Blocking and dodging will consume stamina, which also affects how often the player can attack.
When the player blocks, the strength of the shield will determine if any damage "leaks through". The stronger the attack, the more stamina is drained. Dodging uses more stamina with each individual use, but its cost remains fixed. The other benefit is that dodging guarantees that the player will not take any damage, and it can be used to set up a follow-up attack from the enemy's blind side.
The final option is the riposte, which requires the player to time the move just before impact. Pulling this off uses no stamina, and the following counterattack will do extra damage. Missing the timing will punish the player -- the full hit from the enemy will connect.
The toughest lesson for the player to learn is to master dodging and only use blocking as a last resort. Blocking should be avoided at all cost against bosses and larger enemies, as the stamina drain is intense. When fire and magic attacks are introduced, normal shields will not absorb either damage regardless of their strength, signaling the player even more that dodging is needed.
Like Ninja Gaiden Black, this lesson culminates with a final battle. The last boss in Demon's Souls does immense damage with each attack -- along with a major stamina drain if the player blocks. Taking its full combo attack is fatal. One of its most frequently used attacks is a dash that requires the player to dodge just as it reaches the player; dodging too soon or too late will result in the player getting hit.
The boss also has two powerful attacks that it uses rarely. The first is an explosion with an area effect that is fatal to all but the most heavily-armored players. The only options available to the player are to get as far away as possible, or to hit the boss, canceling the attack.
The second is a close range telegraphed grab. If it connects, the boss will permanently remove one experience level off the player. Beating the boss requires players to have mastered dodging and fully understand when there is an opening to attack. Both games are clear examples of Darwinian Difficulty and highlight the advantages and disadvantages of the design.