Consenting on the Web, in the context of online privacy and data protection, is universally accepted as a difficult problem, mainly because of its cross-disciplinarity. For example, any approach to online Consenting needs to meet usability, legal, regulatory, technical, and business requirements. To date, effort has been predominantly focused on meeting compliance with regulations and automation, and less on the true re-empowerment of users with respect to their personal data. One approach that has not seen sufficient research is the use of ’Consent Receipts’, which offer a new paradigm of recording interactions concerning consent and using them as proofs in future actions, similar to familiar use of a common shopping receipt. In addition to being a record, receipts encourage accountability in how technology handles consent and is beneficial for all involved stakeholders. For organisations, it assists with legal requirements for demonstration of valid consent, while for users it provides transparency and accountability by being a proof to be used against malpractices related to consent. Receipts also have uses in addition to those related to consent, such as for authorising the holder in exercising related rights. This paper analyses the requirements, uses, and benefits offered by Consent Receipts with an extensive and broad literature review. Since receipts are a novel concept, we identify properties and requirements, and then new mechanisms necessary for the Web to support receipts. We then demonstrate feasibility of receipts through proof-of-concepts in three common real-world use-cases: (a) acceptance of a privacy policy and its subsequent changes; (b) choices expressed via consent dialogues or cookie banners; and (c) verbal interactions with Amazon Alexa.