Tally sticks: medieval receipts that burned down Parliament.
Before paper was common, debts were cut as notches into a wooden stick, which was then split lengthwise: creditor and debtor each kept a half that only matched its partner. In German, having many notches still means having a 'record'. The English Exchequer used tally sticks until 1826; burning the leftovers in 1834 set Parliament on fire.
Useful: Tamper-proof bookkeeping didn't need cryptography, just a stick of wood.
Source: en.wikipedia.org