Proving the output of a generic function

Matteo Monti

4/22/23, 3:57 PM

Is there any generic construction to prove the correctness of the output of a function? In other words, is there a general way to produce a witness for the statement $y = f(x)$?

More formally, let $f: X \rightarrow Y$ be a generic function. Given $f$, is there any general way to build a witness-generating function $p: X \rightarrow W$ and a proposition $V(x, y, w)$ such that, for all $x$, only $V(x, f(x), p(x))$ is true, and verifying $V(x, y, w)$ is faster than computing $f(x)$?

0 + 0

zero-knowledge-proofs

snarks

Maarten Bodewes

4/22/23, 4:07 PM

Don't one way functions disprove this?

poncho

4/22/23, 6:52 PM

One function that may be a counterexample is the function $f(x)=0$ (for any $x$); yes, it is easy to build a proposition for this $f$; I don't know if you can build one that runs **faster** than computing $f$...

Matteo Monti

4/22/23, 11:39 PM

@poncho that's quite a fair point I guess.

Wilson

4/23/23, 5:02 PM

To clarify, if I'm reading this correctly. You are wondering if there exist a succinct proof and efficient verification algorithm (in time less than evaluating the function) to check if for a public f, x, and y that y=f(x)?

Matteo Monti

4/26/23, 3:00 PM

@Wilson precisely! I know it exists for some functions (e.g., one-way functions can use their output as witnesses), so I am wondering if some more general mechanism exists!

Wilson

4/27/23, 6:01 PM

Consider a generic function f represented by an ensemble of arithmetic circuits, isn't this problem resolved by preprocessing SNARKs? The verifier time complexity is poly-logarithmic in the circuit complexity. There is also a line of literature called verifiable computation that maybe also what you are looking for.

Wilson

4/27/23, 6:12 PM

Let's take poncho's counterexample in context. $f(x)=0$ is a function computable in constant time. Thus, the constant factors in the verification algorithm will outweigh the logarithmic complexity, but for non-trivial functions, this method will beat evaluating the function.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Proving the output of a generic function

TH: การพิสูจน์ผลลัพธ์ของฟังก์ชันทั่วไป

RO: Demonstrarea ieșirii unei funcții generice

RU: Доказательство вывода универсальной функции

VI: Chứng minh đầu ra của một chức năng chung

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.