Security proof for CBC as a prefix-free PRF I am currently trying to fully understand Dan Boneh's/ Victor Shoup's proof in their excellent crypto book draft, that the raw CBC construction is a secure pseudo random function family for prefix-free adversaries (see Section 6.4.1). 

The methodology of the proof is to replace the PRF $E_K: \mathcal{X} \rightarrow \mathcal{X}$ with a function $f:\mathcal{X} \rightarrow \mathcal{X} $, that is chosen uniformly from random from set of all functions $f \stackrel{\$}{\leftarrow} \text{Funs}_{x,x}$:




The crux is then to calculate an adversary's ability to distinguish this $\text{CBC-}f$ construction from a random choice out of $\text{Funs}_{mx,x}$ (the set of all functions $\mathcal{X}^{\leq m_\text{max}}\rightarrow \mathcal{X}$ with $1\leq m \leq m_\text{max} $). For this, a rooted tree is used, where each query represents a path in this tree. The goal is to find the probability, that two inputs for $f$ collide (CBC chain value $\oplus$ some $X_i$ collides with some other CBC chain value $\oplus$ some $X_j$). This is where the prefix-freeness comes into play, because it ensures, that the message blocks are statistically independent from the CBC chain values and hence two inputs for $f$ collide with probability $1/|\mathcal{X}|$. 

Last but not least my question: Why do we have to consider internal collisions too? Why is it not sufficient to only consider collisions on the last $f$ invocation for every query? How can a prefix-free adversary know, if there was an internal collision, when he only sees $Y$?
The answer is in the last sentence of the proof: "Once we have established that there are no collisions of these types, it will follow that all values associated with non-root nodes are random and independent, and this holds in particular for the values associated with the leaves, which represent the outputs of FCBC seen by the adversary."

To explain: we are only interested in the leaves which is the last invocation. However, the way to prove it is by proving it for all invocations. This seems quite natural because once there is an internal collision, the question of whether or not this leads to a final collision depends on the query contents, and this is unknown.