Examine whether a hash function is collision-resistant Assume a collision-resistant hash function $h$ which compresses sequences of length $2n$ to length $n$. It must be examined whether the hash function which compresses seqs. length $4n$ to $n$:
$$
h_1(x_1 || x_2 || x_3 || x_4) = h((x_1 \oplus h(x_2 || x_2)) || (h(x_3 || x_3) \oplus x_4))
$$
is collision-resistant or not. ($\oplus$ is XOR, $||$ is concatenation and $|x_i| = n$).
Attempt:
Assume we can easily find two distinct sequences $(y_1, y_2) = (x_1 || x_2 || x_3 || x_4, x_5 || x_6 || x_7 || x_8)$ such that $h_1(y_1) = h_1(y_2)$.
Then, we can easily find $(y_1, y_2)$ such that:
$$
h(g(y_1)) = h(g(y_2))
$$
where $g(y) = g(x_1||x_2||x_3||x_4) = (x_1 \oplus h(x_2 || x_2)) || (h(x_3 || x_3) \oplus x_4)$.
But then, if we can easily find such $(y_1,y_2)$, we can also easily find $(g(y_1), g(y_2))$ and thus $h$ is not collision-resistant.
In case the above argument isn't valid, another idea would be to state that $g(y_1), g(y_2)$ cannot be distinct (with non-negligible probability) since $h$ is collision-resistant and continue with solving $g(y_1) = g(y_2)$ etc until we get $y_1 = y_2$.
It'd be very helpful if someone pointed out to me which of the two (if any) is the correct proof.
Your proof starts with the correct approach, but $h_1$ is not collision-resistant (CR), and therefore your proof should give you a hint as to why it's not CR.
Edit: I have removed the counterexample, since it should be easy to figure out using the proof attempt below.
Attempt to prove
You want to prove that:
If $h$ is CR, then $h_1$ is CR.
We prove the contraposition of that statement:
If there exists an adversary $\mathcal{A}^{h_1}$ breaking $h_1$,
then there exists an adversary $\mathcal{A}^{h}$ breaking $h$.
We want to assume the existence of $\mathcal{A}^{h_1}$ and use it to
construct $\mathcal{A}^{h}$.
$\mathcal{A}^{h}$ is playing the CR game, and
is supposed to output a collision for $h$.
To achieve that, we let $\mathcal{A}^{h_1}$ run.
Since by assumption $\mathcal{A}^{h_1}$ has a non-negligible
probability of succeeding, it will output a collision of $h_1$ with non-neglibile probability, i.e. a $x^a \neq x^b$ such that $h_1(x^a) = h_1(x^b)$.
We now want to win the CR game against $h$ and construct a collision for $h$ from $x^a$, $x^b$.
We know that $h_1(x^a) = h_1(x^b)$, and $x^a \neq x^b$.
Therefore, using your $g(\cdot)$,
$h(g(x^a)) = h(g(x^b))$.
There are two cases here:
1. Either: $g(x^a) \neq g(x^b)$
then we immediately find a collision:
since $h(g(x^a)) = h(g(x^b))$
and $g(x^a) \neq g(x^b)$,
the pair $(g(x^a), g(x^b))$ is a collision for $h$.
2. Or not: $g(x^a) = g(x^b)$
then we have to look further for a collision.
by $g(x^a) = g(x^b)$ we know that
$\underbrace{(x^a_1 \oplus h(x^a_2 || x^a_2))}_\text{first part}\ ||\ (h(x^a_3 || x^a_3) \oplus x^a_4)
 = (x^b_1 \oplus h(x^b_2 || x^b_2))\ ||\ (h(x^b_3 || x^b_3) \oplus x^b_4)$.
By $x^a \neq x^b$ we know that at least one of these 4 cases must hold:
2.1. $x^a_1 \neq x^b_1$
By $g(x^a) = g(x^b)$,
the first part of the input of the outer $h$ must be equal:
$x^a_1 \oplus h(x^a_2 || x^a_2) = x^b_1 \oplus h(x^b_2 || x^b_2)$.
This is where the proof breaks down. You cannot construct a collision from this.
2.2. $x^a_2 \neq x^b_2$
2.3. $x^a_3 \neq x^b_3$
2.4. $x^a_4 \neq x^b_4$
Hope I could help!