In this work we develop a rewarding framework that can be used to enhance existing crowd-sensing applications. Although a core requirement of such systems is user engagement, people may be reluctant to participate because sensitive information about them may be leaked or inferred from submitted data. The use of monetary rewards can help incentivize participation, thereby increasing not only the amount but also the quality of sensed data. Our framework allows users to submit data and obtain Bitcoin payments in a privacy-preserving manner, preventing curious providers from linking the data or the payments back to the user. At the same time, it prevents malicious user behavior such as double-redeeming attempts, where a user tries to obtain rewards for multiple submissions of the same data. More importantly, it ensures the fairness of the exchange in a completely trustless manner; by relying on the Blockchain, the trust placed on third parties in traditional fair exchange protocols is eliminated. Finally, our system is highly efficient as most of the protocol steps do not utilize the Blockchain network. When they do, only the simplest of Blockchain transactions are used as opposed to prior works that are based on the use of more complex smart contracts.