I have done some research but I couldn't find a conclusive answer for this.
I want to build a bridge between two Ethereum test nets as a proof of concept and initially thought it would be possible to have a fully on chain, decentralized and trustless system. However, the biggest problem to that seems to be communication, how one side of the bridge will know that coins have been deposited to the other.
Basically the solution I've seen consists on a deposit on one side, which emits an event. A relayer (or network of relayers) listens to these events and publishes a signature somewhere. The depositor then uses this signature on the other side of the bridge to claim his assets.
I do not like this much because you have to trust the relayers.
So the question is, can fully decentralized and trustless bridges between blockchains exist?