Physicists love paradoxes, and the firewall paradox is one of the craziest ones out there. The gist of it can be summed up in about seven points.
1) The smoothness of space requires local correlations (local entanglement):
Ordinary space is smooth in the sense that we can move around it without encountering much resistance. This relies on the fact that any neighboring patches of space must all be in a roughly similar state. If the character of a patch of space was suddenly very different from those around it, we might call that a wall. If we imagine that space is made up of a collection of bits, then there must be a high degree of correlation (re: entanglement) between neighboring bits. The picture below shows Alice flying through a smooth space. The degree of correlation between bits is represented by the shade of the lines connecting them. Black connections represent so-called "maximal entanglement".
If one patch of space is totally uncorrelated with the patch next to it, then what Alice encounters upon crossing between the patches might be totally random. The thermal distribution would generically produce something very energetic, known as a firewall. In the language of Shannon information, you had better be able to predict the energy density of the patch you're flying into using the patch that you're currently in. If you cannot, then it means you are toast.
Einstein's theory of general relativity says that the event horizon of a black hole should be smooth in the sense that we've discussed. For nearly 80 years it was considered an obvious fact to physicists that Alice could fly into a black hole if she wanted to. This is sometimes called the "no-drama" postulate for black holes.
2) Entanglement (correlation) is monogamous:
It is useful to think of entanglement as a kind of substance whose quantity is conserved. If two particles are maximally entangled (re: 100% correlated), then they cannot be at all entangled with anything else. This has further consequences which are illustrated in the picture below. In the left panel, Particle A and Particle B are maximally entangled with each other. Particle B lives in a box with a number of other particles which are totally uncorrelated with anything else. In the middle panel, we let the particles in the box interact with each other for a long time. Like billiard balls they will soon reach a configuration where all of the particles in the box are correlated with each other to some degree. Now Particle A is correlated with several other particles in the box. In the right panel, we look at the box as a whole and observe that although Particle B has been polygamous with other particles in the box, Particle A remains maximally entangled with the box system. Thus it is still true that Particle A cannot be entangled with anything else.
3) Black holes evaporate by radiating particles:
This is just a fact of nature. Famously Stephen Hawking showed that this was true by identifying the mechanism behind it, and verifying its veracity through calculations. The technical details of this mechanism are actually crucial to the original firewall argument, but I will try my best to explain the paradox without it. The important parts are summarized below. As a black hole evaporates it releases particles out into space and its size shrinks. The particles that come out of a black hole are maximally entangled with whatever lies inside the black hole interior.
4) The Firewall Paradox:
The firewall paradox is not so much a true paradox. It is really just an argument for why something totally ridiculous must be true. If entanglement is monogamous and black hole radiation is maximally entangled with the interior. This means that at a certain point, when the black hole is almost exactly halfway done evaporating, the interior of the black hole will be maximally entangled with a box of particles that are enormously far away by this point in time. The particles in the box are highly scrambled, but Bob has meticulously collected every single one of them. Now there is no longer "enough" entanglement in the black hole for it to also produce a smooth space at its boundary and a firewall spontaneously forms. This seems totally crazy to most physicists. But the firewall paradox is like a straw man that no one seems able to knock down.
5) Proving entanglement is hard:
One very important fact related to the firewall paradox, is that in general it is very difficult to verify the degree to which two systems are entangled. This is especially true if one of the systems is extremely scrambled, like the collection of particles in Bob's possession. Nevertheless if Bob has an infinitely powerful quantum computer and knows the right algorithm, then he can descramble everything and figure out exactly what the interior of the black hole looks like.
6) It's only a paradox if you can prove it's a paradox:
As I alluded to at the top of this page, physics has tons of examples of dualities in which two observers can look at the same event and see something totally different. For example due to relativity, two observers moving at different velocities can see the same objects/events and measure vastly different lengths/durations, thus eliminating the notion of "absolute truth" in nature. Could it be that from Alice's perspective there is no firewall? Even though Bob can verify that there is a firewall? One way to prove this wrong would be to find a scenario where it results in a contradiction. The original firewallers found such a scenario which is pictured below. Alice could verify that a firewall exists by using Bob's infinitely powerful quantum computer to descramble all of the past radiation. She could even grab the specific bits that are maximally correlated with the future radiated particles that she expects to find while crossing, thus proving that the space there cannot be smooth. In a beautiful paper, Harlow and Hayden analyzed the computational complexity of this descrambling process and found compelling evidence that there are fundamental mathematical limits to how quickly it can be performed. They argue that there is not really a paradox because the minimum time it would take to run the quantum computation is longer than the entire lifetime of the black hole. If this is true it would imply that Alice and Bob experience two drastically different descriptions of the same reality. It would also imply that computational complexity is a kind of fundamental constant of nature that prevents the appearance of inconsistencies, similar to the way a finite speed of light prevents the violation of causality. This proposal is extremely radical and I find it extremely intriguing.
7) Space could be made out of wormholes:
There is another possible resolution to the paradox which is complementary to the Harlow-Hayden conjecture. This arguably more radical proposal says that all of the entanglement between all particles can be thought of as resulting from microscopic wormholes. Since smooth space requires entanglement, this would mean that space could be viewed as a literal fabric, woven out of threads made from wormholes! This is known at the ER=EPR conjecture. "ER" refers to wormhole (sometimes called an Einstein-Rosen bridge) and "EPR" refers to entanglement (named after Einstein-Podolsky-Rosen who analyzed the properties of entanglement). In a another beautiful paper, Maldacena and Susskind used several concrete examples to show that the entanglement between a black hole and its radiation is equivalent to the entanglement between two sides of a holographic wormhole. Using this correspondence they were able to show that Alice's act of descrambling the qubits is equivalent to an interaction with the black hole in the far distant past. As she runs the algorithm on the quantum computer, she increasingly entangles herself with the black hole interior. Thus even if she could run the algorithm in time to jump in she would be spared the fate of seeing a firewall.