Blockchain interoperability protocols enable cross-chain asset transfers or data retrievals between isolated chains, which are considered as the core infrastructure for Web 3.0 applications such as decentralized finance protocols. However, existing protocols either face severe scalability issues due to high on-chain and off-chain costs, or suffer from trust concerns because of centralized designs. In this paper, we propose \texttt{MAP}, a trustless blockchain interoperability protocol that relays cross-chain transactions across heterogeneous chains with high scalability. First, within \texttt{MAP}, we develop a novel \textit{cross-chain relay} technique, which integrates a unified relay chain architecture and on-chain light clients of different source chains, allowing the retrieval and verification of diverse cross-chain transactions. Furthermore, we reduce cross-chain verification costs by incorporating an optimized zk-based light client scheme that adaptively decouples signature verification overheads from inefficient smart contract execution and offloads them to off-chain provers. For experiments, we conducted the first large-scale evaluation on existing interoperability protocols. With \texttt{MAP}, the required number of on-chain light clients is reduced from $O(N^2)$ to $O(N)$, with around 35\% reduction in on-chain costs and 25\% reduction for off-chain costs when verifying cross-chain transactions. To demonstrate the effectiveness, we deployed \texttt{MAP} in the real world. By 2024, we have supported over six popular public chains, 50 cross-chain applications and relayed over 200K cross-chain transactions worth over 640 million USD. Based on rich practical experiences, we constructed the first real-world cross-chain dataset to further advance blockchain interoperability research.