Accounting and billing of cloud resources is vital for the operation of cloud service providers and their tenants. In this paper, we categorize the trust models of current industrial and academic cloud billing solutions, and discuss the problems with these models in terms of degree of trust, scalability and robustness. Based on the analysis, we propose a novel public trust model to ensure natural and intuitive verification of billable events in the cloud. Leveraging a Bitcoin-like mechanism, we design BitBill, a scalable, robust and mutually verifiable billing system for cloud computing. Our initial results show that BitBill has significantly better scalability (supporting 10x concurrent tenants using the billing service) than the state-of-the-art third-party centralized billing system.