Requests for step changes

Technologies that already work, but still have room for order-of-magnitude improvement.

Verifiable computation

  • Reduce the cost and time required to generate proofs that a computation was performed correctly.
  • The premise is simple: given a known input, a known program, and a claimed output, produce a proof that the output is correct. Where homomorphic encryption and zero-knowledge proofs are about hiding information from some party, verifiable computation is simply about proving correctness.
  • A proof system can be judged by three things: how expensive the proof is to generate, how large the proof is, and how expensive the proof is to verify.
  • Proofs can already be compact and fast to verify, but generating them for arbitrary computations remains far slower than simply running the computation.
  • Cheap proof generation would let computational outputs carry certificates of correctness, making outsourced computation, computation markets, and long-lived computational results viable.
  • Trusted execution environments are a practical stand-in today, but they rely fully on trust in the underlying hardware.
  • For more frontiers related to computation and cryptography, see 0xPARC.