Let $P(x)=a_1x+a_2x^2+…..+a_nx^n$ be a polynomial such that $$P(x^2+1)=(P(x))^2+1$$ and $P(0)=0$
(it is immediate that $P(1)=1$). We have
$$P(x^2+1)=\sum a_k(x^2+1)^k=\sum a_k\sum\binom{k}{ l}(x^2)^{k-l}$$
$$\\((P(x))^2+1=\sum a_k^2x^{2k}+2\sum a_ka_jx^{k+j}+1$$ It follows that the polynomial
$$R(x)= \sum a_k\sum\binom{k}{ l}(x^2)^{k-l}-\left(\sum a_k^2x^{2k}+2\sum a_ka_jx^{k+j}+1\right)$$ must be identically zero because it has more roots than its degree so all the coefficients must be zero.
It can be seen that even for the second degree this is not the case and that the only possibility is $$\color{red}{P(x)=x}$$
$$***$$
We give another solution because the verification about coefficients in the precedent one is not immediate
$$***$$
SECOND SOLUTION.-It is clear that $P(x)=x$ goes well. Put $$P(x)=x+Q(x)$$ so that
$$ P(x^2+1)=(P(x))^2+1\iff Q(x^2+1)=2xQ(x)+(Q(x))^2\qquad (*) $$
We have from $(*)$, $$ (Q(x))^2+2xQ(x)-Q(x^2+1)=0\iff Q(x)=-x\pm\sqrt{x^2+Q(x^2+1)}\qquad (**)$$
Note that if $Q(x_0)=0$ then $Q(x_0^2+1)=0$
Because of $P(0)=0\Rightarrow P(1)=1\Rightarrow P(2)=2\Rightarrow P(5)=5$, one has
$Q(0)=Q(1)=Q(2)=Q(5)=0$.
It follows from $(**)$ we can deduce an infinity of roots for $Q(x)$ (for example $26,677$ and $458330$ the three first deduced from $Q(5)=0$).
Consequently $Q(x)=0$ for all $x$
and $$P(x)=x$$ is the only solution.
for infinite values of x
"For infinitely many values of x" would sound better. $\endgroup$