Multi-cloud environments such as OnApp and Cloudflare have turned the cloud marketplace towards a new horizon where end-users can host applications transparently over different cloud service providers (CSPs) simultaneously by taking the best from each. Existing cloud federations are typically driven by a broker service which provides a trusted interface allowing the participant CSPs and end-users to coordinate. However, such a broker has the limitations of any centralized trusted authority like risk of manipulation, bias, censorship, single point of failure, etc. In this paper, we propose a decentralized trustless cloud federation architecture called CollabCloud which eliminates any central mediator while addressing the challenges introduced by byzantine participants. CollabCloud utilizes blockchain, and introduces a novel interoperability protocol bridging a permissionless blockchain as an open interface for the end-users, and a permissioned blockchain as a coordination platform for the CSPs. We have implemented CollabCloud with Ethereum, Hyperledger Fabric and Burrow platforms. Experiments with a proof-of-concept testbed emulating 3 CSPs show that CollabCloud can operate within an acceptable response latency for resource allocation, while scaling upto 64 parallel requests per second. Scalability analysis over Mininet emulation platform indicates that the platform can scale well with minimal impact on the response latency as the number of participating CSPs increases.