24 Mar 2003 ciphergoth   » (Journeyer)

Partial busy-work functions

Bram writes about partial busy-work functions. I need to know more about the requirements for generation and verification before I can see how to attack it. The only requirements I have are these:

  • There is a graph with n nodes
  • Each node is associated with a puzzle, and there's a puzzle for the whole graph
  • Each node puzzle should take k work to solve
  • The whole graph puzzle is easy to solve if you have the solution for any two nodes on the same arc.
  • The solution is the same no matter which arc you use.

I can see several trivial solutions, but they have these disavantages: it takes as much work to verify a solution ans it does to generate it, and generating all the puzzles takes nk time. Usually you want a busy-work puzzle to be trivial to generate and verify, eg "find a 160-bit value that hashes to something with the prefix 72f3ab81". Bram, what are your reqirements with this?

Bayes and scoring

I've got a better grasp on what these probabilities really mean, and why (as I wrote last time) (a o_s b) = (a o b o (1-s)). If anyone's reading, mail me, I'd be happy to write it up...

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!