Consider the Proof-of-Work mechanism used for block validation in a distributed system. In the general setting, we are given two hash functions

$$ H1, H2 : A \times B \rightarrow {0, 1, \ldots, 2^{256} - 1} $$

where $A = B = \{0,1\}^{512}$.

To verify a block, the following cryptographic protocol is executed:

1. The validator publishes values $a \in A$ and $L \in \mathbb{N}$.
2. To prove correctness of the block, a participant must provide $b \in B$ such that $$ H1(a, b) < L, \quad H2(a, b) < L $$ where $$ H1(a, b) = \mathrm{SHA\text{-}256}(a \oplus b), \qquad H2(a, b) = \mathrm{SHA\text{-}256}((a \oplus b) \cdot 2025 + 1). $$
3. The validator checks the correctness of these computations.

Questions:

1. Are there any methods to find y for a fixed L that are faster than brute-force?
2. What protocol improvements are known in the literature for increasing the attack complexity in this context? More generally, how could the presented protocol be modified to make such attacks more difficult?