ok, I have my end-term examinations underway, and I found a somewhat interesting topic in cryptology, namely: “Incrementally Verifiable Computation.” writing this microblog so that I get back to the topic after my exams.
i have got the original paper in front of me right now, written by Paul Valiant from MIT. to quote paper’s introduction,
perhaps the simplest way to introduce the computational problem we address is by means of the following.
human motivation: suppose humanity needs to conduct a very long computation which will span super-polynomial many generations. each generation runs the computation until their deaths when they pass on the computational configuration to the next generation. this computation is so important that they also pass on a proof that the current configuration is correct, for fear that the following generations, without such a guarantee, might abandon the project. can this be done?
computational setting: in a more computational context, this problem becomes:
how can we compile a machine M into a new machine M’ that frequently outputs pairs (c_i, pi_i) where the i-th output consists of the i-th memory state c_i of machine M, and a proof pi_i of its correctness, while keeping the resources of M intact?
gonna dive deeper after the exams. i don’t know how, cuz i don’t know blockchain, but think must already be getting used in the field.
peace
da1729
reference:
- Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency by Paul Valiant, MIT