Proof of payment dates to the most ancient of antiquity. The Romans were very picky about public accounting, but not much of it survives, and we can find receipts that are much earlier.

Our oldest records of debts satisfied come from Mesopotamia-- their practice of writing on extraordinarily durable clay tablets means that we've got transaction records that are 4000 years old. So, for example, we have a receipt for the delivery of wool from 2039 BCE, written in Sumerian, probably from the town of Girsu.

That's just one of many thousands of financial records we have from this earliest date in history. The Sumerians and subsequent Mesopotamian civilizations didn't have double entry bookkeeping -- that comes much later and famously proliferates as a standard in the Renaissance-- but they did have complex financial and commercial systems. They recorded debts, and debts paid.

Why are they commonplace?

Because if you're going to finance anything, you have to account for it. How else would you establish "yes, Gilgamesh paid the rent"? The receipt is a fundamental instrument, effectively the release of an indebtedness, or alternatively a credit. Without receipts, bookkeeping becomes very difficult.

Sources:

Robson, Eleanor, and Gábor Zólyomi. “MESAG REPORTS A MURDER: CUNEIFORM TABLETS IN THE COLLECTIONS OF NORWICH CASTLE MUSEUM AND CAMBRIDGE UNIVERSITY LIBRARY.” Iraq, vol. 76, 2014, pp. 189–203.

Garbutt, Douglas. “THE SIGNIFICANCE OF ANCIENT MESOPOTAMIA IN ACCOUNTING HISTORY.” The Accounting Historians Journal, vol. 11, no. 1, 1984, pp. 83–101.

Keister, Orville. "Commercial Record-keeping in Ancient Mesopotamia." Accounting Review, Vol. 38 (1963), pp. 371-376.

Mattessich, Richard. “RECENT INSIGHTS INTO MESOPOTAMIAN ACCOUNTING OF THE 3RD MILLENNIUM B.C. — SUCCESSOR TO TOKEN ACCOUNTING.” The Accounting Historians Journal, vol. 25, no. 1, 1998, pp. 1–27