This paper presents a new consensus algorithm, Proof of Usage (PoU), for the blockchain technology. This consensus is introduced for permis-sioned (or private) blockchains and is designed for a user-centric personal data market. This market is subject to specific regulations with which conventional blockchains fail to comply. Proof of Usage aims to promote a new paradigm dedicated to usage incentivization, valuation, and control of user data in various sectors, such as banking and insurance. Other consensuses such as Proof of Stake or historical Proof of Work do not encourage coin spending and usage (in fact, Proof of Stake promotes the opposite). However, the value of the currency mainly depends on its use. This paper first introduces a contextualization of blockchain technology and decentralized consensus models. The motivation is then discussed for a new model of personal data exchange in a decentralized but supervised environment. The PoU protocol and its process flow are defined in detail. Furthermore, the paper explores two different approaches regarding the reward mechanism and the incentive model. Finally, the paper focuses on security requirements and how PoU meets such requirements in a permissioned-based blockchain system.