So, we’re told that each individual currency-unit possesses its own cryptographic signature (A Weapon Too Terrible To Use | The Associated Worlds) based on value and serial number. We’re also told that such signatures can be invalidated. Just how big of a database does the Exchequer have to track which signatures are valid or invalid? It’s not as if they have a CRL, do they?
For the unitiated, what’s a CRL?
CRL - Certificate Revocation List
It’s a big long list of certificates (as in SSL/TLS/HTTPS certificates) that a certificate authority issued (so they’re cryptographically valid) but no longer wants honoured.
1 Like
A very, very big one. While I am reluctant to provide any canonical figures for the size of the money supply, the last notes I have on GPP for the Empire puts it around 24.4 quintillion esteyn. The velocity of money is high there by our standards, but still, we’re talking quintillions of entries of lengthy bitstring signatures.
On the other hand, a quintillion is still only 10¹⁸, and memory diamond can store a mole of bits per two moles of carbon; i.e., 6 * 10²³ bits in a cube 2 cm across, so in physical terms, it’s still a very smol database and the Exchequer isn’t going to go broke shipping updates to the database and CRL around to remote nodes any time soon.
Isn’t such a database going to be unwieldy to actually operate on? Like, it’s not as if it’s a sorted list of signatures and an extra bit for valid/invalid status; that would be impossibly difficult to insert new elements in to (assuming signatures are randomly distributed, which seems like it should be necessary for proper cryptographic security)
I guess it might work if you maintained some sort of tree structure, probably a trie; I think you can make the assumption that you rarely, if ever, delete any data from the tree structure, so there’s not going to be much concern about fragmentation, especially since every record is probably going to be of similar size.
Ooh, or you could just do some sort of hash table; you make the assumption that it’s going to be very rare for the first 80 or so bits of two signatures to collide, and make a hash table by truncating the signature to 80 bits. Problem is that increasing the size of the hash table is going to be a right pain; you’d have to rehash every record. So there’s a long-term problem if the economy ever grows large enough that a 80 bit hash has too many collisions.
Hm… this could make for an interesting software engineering interview question - here’s an overwhelmingly large number of records (and you’re constantly getting new ones) with a cryptographic signature as its primary key. Build a data structure that allows for fast lookups given a key and fast modification of the non-key part of the record. How much storage space are you using, and what tradeoffs between space and time complexity can you make?
You aren’t going to be using the signatures as the primary key, any more than, say, GPG does that. They’re too long. The database is going to be keyed on the serial numbers of each currency unit - which, while, okay, they’re not short are still significantly shorter than the signatures. (Also can be broken up into multiple fields, insofar as they incorporate sub-information like the regional mint responsible for producing that particular unit, its denomination, and its century of original production.)
No deletions, not even when a unit is withdrawn, because in that case you want to know that it’s been withdrawn. It’s just flagged thus. Also, to avoid multiplying identities beyond necessity, when issuing fresh currency, it’s policy to start by reissuing withdrawn units and only then moving on to generating new ones.