I've never programmed anything in my life and even I find this question a bit too simple, so I'm not bumping this thread. But I have a little idea that is related: People often like to post screenshots with their scores, and you could put in mechanisms to work out for yourself whether people make fake claims about scores without even having any sort of database.
That is, the score screen could have some details like background color and some border around the numbers based on some attributes of the score, like whether its even or odd or how many sevens appear or whatever, working like a checksum. So you could tell with good probability whether a score screenshot was faked. But you don't even need a screenshot. If your game has really long scores, you can put in a speed bonus at the end of the game for say the last four digits that in reality is only a speed bonus for the left half of these, and the other two are really a sneaked-in checksum.