The monster with ten thousand secrets

On thinking some more about the hash cash for virtual real estate idea, one possibility I imagined was that it could be applied to possession of items as well as real estate.  I imagine a game something like Legend of the Red Dragon (LORD), which was very popular back in the BBS era.

LORD was a very simple "work through the levels" type of game in which you got a weapon and some armour and then you'd fight with monsters to earn money which you could then take back to the town and spend on better weapons and armour to enable you to fight bigger monsters and so on.  Meanwhile there were subplots going on, like your ongoing attempts to get the barmaid into bed, and the wacky intrigues that the human players would create for themselves by dragging disputes from real life into the game.  All good clean fun.  It seems to me that there could be a lot of peer-to-peer possibilities if everyone had the opportunity to create their own "town" similar to the town in LORD, set the prices in the shops, script out the interactions of NPCs like the barmaid, and choose the mix of monsters to stock in the forest.  Then players could travel around from server to server, interacting with each other and with the server operators.

So, my first thought was that a cool weapon or whatever could consist of a hashcash token:  that is, a certificate proving that the bearer had performed a certain amount of computation.  Players would be kept honest by that computation requirement:  because we all have roughly comparable amounts of CPU power available, we can all mint items for ourselves at roughly the same rate.  If you have a lot of cool items, it must be because either you spent a whole lot of CPU power to get them, or you legitmately bought or stole them from lots of other participants.  An economy can exist in which things have real value because of scarcity, even though an unlimited number of participants can join and there's no central authority needed.

That idea probably still has a lot of life in it, but on thinking it over some more, I don't think it's what's really needed for a LORD-type game.  What I'm about to describe isn't exactly a complete solution either, but it's a cool idea worth sharing anyway.  The bottom line is that in order to successfully claim to be a high-level character, you shouldn't just prove you've done a lot of CPU work.  You should prove you've done a lot of work with your character specifically; that is, your skills should improve with exercise and the certificate of your skills should be a proof that you've used the skills a lot.  The thing that allows you to succeed in tests of skills should be the thing that proves you have previously failed, or run the risk of failure, a number of times.

Suppose you're going to face a monster, let's say a zombie, and attempt to attack it.  Combat, fundamentally, in a typical RPG situation consists of a bunch of random chances which may go your way or the zombie's way.  If you're a completely unskilled character then there's a certain chance of success or failure; as you gain experience your chance of success increases.  So let's model that by saying that the zombie has ten thousand secrets.  Each time you take a chance in facing the zombie, one of the secrets is selected at random, and then you have to guess it.  If you guess right, you win that round; otherwise you lose; but either way, you learn the secret.  So next round, or next time you face a zombie, you have a better chance of success.

The simplest protocol:  every combat round the server gives you a random "secret number".  You have to guess the secret; the server tells you whether you guessed right or not.  Your client stores it against future demands for the same secret.  The secret might typically be one bit long, so on your first round you have a 50 percent chance of winning and on subsequent rounds your chance of winning gradually increases.  After about 130 thousand rounds you're pretty much assured of winning every time; that's how long it takes to learn to be invincible against zombies.  Of course, the probabilities and amount of practice needed are completely flexible by changing the parameters of the system.

What if you don't trust the server to give you randomly chosen secrets?  That can be solved by doing secure coin-flip to establish a psuedorandom seed.  Before combat, the server generates a random seed and gives you the secure hash of the seed.  Then you provide a random seed, and the server reveals its previous choice; the two are combined to seed a random number generator.  That way neither you nor the server can influence which secrets are chosen.

But in that case, you'll be able to run the generator ahead and predict what secrets you'll be asked for in the future; that could give you a premonition of how well the combat is going to go, and whether you should continue it or run away.  So instead, the server will generate its random seed, hash that a large number of times (say a thousand - more hashes than the maximum number of rounds in the combat) and reveal the result.  You provide a random seed.  In each combat round, the server reveals the previous hash value (so, the result of the 999-times iterated hash on the first round, the 998-times iterated hash on the second, and so on).  You can verify that that hash really is an input value producing the previously-revealed hash value, so the server has committed to its side of the random number exchange right from the start.  The current hash value is combined with your random seed to create the random choice of secret for the current round.  Thus, neither you nor the server can influence which choice will be made, and you can't predict the future choices.  The server could, but that doesn't seem to be a problem; if it were, then a similar iterated-hash protocol could be applied on both sides.

There's a worse problem:  what if the server lies about the secrets?  There ultimately has to be a fair bit of trust placed on the server anyway, but we could make things a little better and save you some storage space on your client by applying another set of iterated hashes.  The idea is that secret number k is the hash value (probably the lowest bit of the hash value, actually) of secret k+1.  If you present the server with all the secrets from 0 up to n, in a bundle, then the server will offer you the seed value that generates them.  Then you only have to store that seed value.  Similarly, the server only has to store the seed value.

Using seed values to generate the monster secrets also provides us with the ability to do some clever PKI stuff on the side of people who want to build servers of their own.  The more secrets a monster has, the tougher it will be to defeat.  Let's make the server software automatically use the secrets you collect with the client software.  If you've fought enough zombies to know the first five thousand zombie secrets, then you'll have a code you can use to create zombies on your own server, with five thousand secrets themselves.  As you learn more zombie secrets, you'll get better codes which allow you to create more powerful zombies.  So the level of challenge you can create on your own server depends on the level of challenge you've defeated on other servers.  Low-level players get to build low-level challenges.

To enforce that kind of scarcity, I envision a public key infrastructure of monster certificates.  Anybody can set up as a root, but will other clients and servers trust them?  The roots that will be trusted in your session would be negotiated when you connect.  Each monster would come with a certificate describing the monster's name, the minimum and maximum number of secrets it ought to have, and another hash (salted to prevent duplication) of the secret-generating code for the monster at its weakest level.  When you've fully defeated the monster at its weakest level, you can compare the secret-generating code against the one specified in the certificate, and verify that no tampering occurred.

Weapons and armour and so on might be treated similarly to monsters; to successfully use the weapon or armour in your combat, you'd have to guess one of its secrets in the same way as for monsters.  In order for that approach to work, the server must already know the secrets for your weapon, which means that you can't just bring in a random weapon from some other server that nobody here has ever seen before.  There may be some way of fixing that issue with more sophisticated cryptographic tricks.

If it's desirable to leak less information than the entire secret each round, the server could instead give you a "share" from a threshold secret-sharing scheme.  Then you don't get the secret until you've accumulated enough shares of it.

I'm not sure if the above made any sense; it's a rather cursory overview of a concept I don't have fully worked out anyway; but it might be an idea starter for somebody.