A QR code or an EAN bar code or something similar is fine, but in order to provide validation so it can't be faked, you need some server-side processing which links the user to his purchase.
The rest of this answer is out of scope in terms of UX, but here goes anyway...
The till receipt generates a QR code which contains data like the till receipt number. The app adds the phone identity and contacts the store server (via a web URL, perhaps). The store's server validates the till receipt (valid number which has been issued and not uploaded before) and stores the customer's purchase using the phone identity to identify the customer.
When the customer claims his free gift, use the server-side records to validate that he's entitled to it.
The crucial part for security is that nothing is left in the control of the user. Everything is on the store's servers. The only part which the user has any control over is whether he scans the code on the right phone, or at all.
A standard store loyalty-card scheme which is handled by the checkout clerk does the same thing: the customer hands over his card and the record of his purchases is held by the store along with his card number. All that is in the control of the customer is whether he hands his card over for his purchases to be recorded against it.