P(x² + 1) = P(x)² + 1

Answer. $P(x)=x$.

It works. $P(x)=x$ gives $x^2+1=x^2+1$ and $P(0)=0$.

Uniqueness. Let $a_0=0$, $a_1=1$, $a_2=2$, $a_3=5,\dots$ with $a_{k+1}=a_k^2+1$. We prove by induction that $P(a_k)=a_k$. For $k=0$ this is $P(0)=0$. If $P(a_k)=a_k$, then the equation with $x=a_k$ gives
$$P(a_{k+1})=P(a_k^2+1)=P(a_k)^2+1=a_k^2+1=a_{k+1}.$$

Infinitely many roots. The sequence $(a_k)$ is strictly increasing ($a_{k+1}-a_k=a_k^2-a_k+1>0$), so the $a_k$ are pairwise distinct. The polynomial $P(x)-x$ has infinitely many roots, so it is the zero polynomial: $P(x)=x$. $\blacksquare$

Lesson. A functional equation for polynomials plus one starting value often generates infinitely many points where the polynomial agrees with a known one.