# What is the collision resistance of a 2048-bit hash based on SHA-3?

Let $M$ denote the message. Let $B_i$ denote eight different bitstrings (chosen arbitrarily or randomly) such that $$0 \le \text{length}(B_i) \le 12345678.$$ Consider the following function (it outputs a 2048-bit hash of the input): $$H(M) = {H_1} \mathbin\Vert {H_2} \mathbin\Vert {H_3} \mathbin\Vert {H_4},$$ where $\mathbin\Vert$ denotes concatenation and $$\begin{array}{l} {h_1} &= \text{SHA-3-512}({B_1} \mathbin\Vert M),\\ {h_2} &= \text{SHA-3-512}({B_2} \mathbin\Vert M),\\ {H_1} &= \text{SHA-3-512}({h_1} \mathbin\Vert {h_2}),\\ {h_3} &= \text{SHA-3-512}({B_3} \mathbin\Vert M),\\ {h_4} &= \text{SHA-3-512}({B_4} \mathbin\Vert M),\\ {H_2} &= \text{SHA-3-512}({h_3} \mathbin\Vert {h_4}),\\ {h_5} &= \text{SHA-3-512}({B_5} \mathbin\Vert M),\\ {h_6} &= \text{SHA-3-512}({B_6} \mathbin\Vert M),\\ {H_3} &= \text{SHA-3-512}({h_5} \mathbin\Vert {h_6}),\\ {h_7} &= \text{SHA-3-512}({B_7} \mathbin\Vert M),\\ {h_8} &= \text{SHA-3-512}({B_8} \mathbin\Vert M),\\ {H_4} &= \text{SHA-3-512}({h_7} \mathbin\Vert {h_8}). \end{array}$$

Since all values of $h_i$ are the outputs of a simple MAC (which is known to be secure enough for SHA-3) and all values of $H_i$ are taken by extracting one cryptographically secure 512-bit hash of two independent 512-bit bitstrings, I would expect that the collision resistance of $H(M)$ is close to 1024 bits of security. Is this assumption correct?

It turns out that for a tree composition and concatenation of $n$-bit hash functions, collisions can be found at $O(2^{n/2}\operatorname{poly}(n))$ cost. So it still has pretty much 256-bit collision resistance. The additional complexity buys you essentially nothing.
Side note: If the adversary knows the $B_i$, the antiforgery property of a MAC, derived from the prefix-PRF $m \mapsto \operatorname{SHA3-512}(k \mathbin\Vert m)$, is not relevant. If the adversary doesn't know the $B_i$, then this is not the scenario of collision resistance—but you're not going to get better than ‘512-bit security’ anyway, which is already (completely meaningless)^2.