And at least as of a few years ago, Truecaller would upload a copy of your phonebook to their servers. That's how they bootstrapped their database - from user's addressbooks. I only ever used it on a burner with an empty phone book, and occasionally get Truecaller pearls like "Annoying John - do not answer" as the caller's name.