Rational proofs
We study a new type of proof system, where an unbounded prover and a polynomial time verifier interact, on inputs a string x and a function f , so that the Verifier may learn f (x). The novelty of our setting is that there no longer are “good” or “malicious” provers, but only rational ones. In essen...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | en_US |
| Published: |
© Association for Computing Machinery, New York, NY, USA
2022
|
| Online Access: | https://doi.org/10.1145/2213977.2214069 https://hdl.handle.net/1721.1/141708 |
| _version_ | 1811073018696302592 |
|---|---|
| author | Azar, Pablo Daniel Micali, Silvio |
| author_facet | Azar, Pablo Daniel Micali, Silvio |
| author_sort | Azar, Pablo Daniel |
| collection | MIT |
| description | We study a new type of proof system, where an unbounded prover and a polynomial time verifier interact, on inputs a string x and a function f , so that the Verifier may learn f (x). The novelty of our setting is that there no longer are “good” or “malicious” provers, but only rational ones. In essence, the Verifier has a budget c and gives the Prover a reward r ∈ [0, c] determined by the transcript of their interaction; the prover wishes to maximize his expected reward; and his reward is maximized only if he the verifier correctly learns f (x).
Rational proof systems are as powerful as their classical counterparts for polynomially many rounds of interaction, but are much more powerful when we only allow a constant number of rounds. Indeed, we prove that if f ∈ #P, then f is computable by a one-round rational Merlin-Arthur game, where, on input x, Merlin’s single message actually consists of sending just the value f(x). Further, we prove that CH, the counting hierarchy, coincides with the class of languages computable by a constant-round rational Merlin- Arthur game.
Our results rely on a basic and crucial connection between rational proof systems and proper scoring rules, a tool developed to elicit truthful information from experts. |
| first_indexed | 2024-09-23T09:27:22Z |
| format | Article |
| id | mit-1721.1/141708 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:27:22Z |
| publishDate | 2022 |
| publisher | © Association for Computing Machinery, New York, NY, USA |
| record_format | dspace |
| spelling | mit-1721.1/1417082022-04-07T03:37:31Z Rational proofs Azar, Pablo Daniel Micali, Silvio We study a new type of proof system, where an unbounded prover and a polynomial time verifier interact, on inputs a string x and a function f , so that the Verifier may learn f (x). The novelty of our setting is that there no longer are “good” or “malicious” provers, but only rational ones. In essence, the Verifier has a budget c and gives the Prover a reward r ∈ [0, c] determined by the transcript of their interaction; the prover wishes to maximize his expected reward; and his reward is maximized only if he the verifier correctly learns f (x). Rational proof systems are as powerful as their classical counterparts for polynomially many rounds of interaction, but are much more powerful when we only allow a constant number of rounds. Indeed, we prove that if f ∈ #P, then f is computable by a one-round rational Merlin-Arthur game, where, on input x, Merlin’s single message actually consists of sending just the value f(x). Further, we prove that CH, the counting hierarchy, coincides with the class of languages computable by a constant-round rational Merlin- Arthur game. Our results rely on a basic and crucial connection between rational proof systems and proper scoring rules, a tool developed to elicit truthful information from experts. This material is based on work supported by the U.S. Office of Naval Research, Grant No. N00014-09-1-0597. Any opinions, findings, conclusions or recommendations therein are those of the author(s) and do not necessarily reflect the views of the Office of Naval Research. 2022-04-06T15:42:29Z 2022-04-06T15:42:29Z 2012-05-19 Article https://doi.org/10.1145/2213977.2214069 https://hdl.handle.net/1721.1/141708 Azar, P. D., & Micali, S. (2012). Rational proofs. Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC '12), 1017–1028. en_US Attribution-NonCommercial-NoDerivs 3.0 United States http://creativecommons.org/licenses/by-nc-nd/3.0/us/ application/pdf © Association for Computing Machinery, New York, NY, USA |
| spellingShingle | Azar, Pablo Daniel Micali, Silvio Rational proofs |
| title | Rational proofs |
| title_full | Rational proofs |
| title_fullStr | Rational proofs |
| title_full_unstemmed | Rational proofs |
| title_short | Rational proofs |
| title_sort | rational proofs |
| url | https://doi.org/10.1145/2213977.2214069 https://hdl.handle.net/1721.1/141708 |
| work_keys_str_mv | AT azarpablodaniel rationalproofs AT micalisilvio rationalproofs |