Arthur-Merlin protocol（以下简称AM）为交互式证明系统，其中Merlin为prover, Arthur为verifier。verifier公开投掷硬币（对prover也可见）来query prover，并对prover提供的proof进行验证来决定是否接受。
1. interactive proof system交互式证明系统源自论文《Private coins versus public coins in interactive proof systems》： 交互式证明系统中的prover通常被认为具有无限的资源，verifier具有有限的资源。verifier通过抛硬币的方式query prover（有可能询问相同的问题），并对prover返回的结果（proof）进行验证测试，通过测试才认为prover的回答为正确的。 可把这个证明系统扩展为NP问题，其中verifer不需要抛硬币或询问问题，仅需要听（接收）及验证。 在交互式证明系统中，proof的正确性不是数学意义上的，而是概率意义上的，具有一个非零可忽略的错误概率。
可把verifier想象为具有随机数生成器的普通计算机，而将prover想象为具有无限算力的预言机。prover需回答verifier的询问，由verifier来判断prover的回答是否可信。
在论文《Private coins versus public coins in interactive proof systems》中，证明了verifier秘密抛硬币和公开抛硬币在交互式证明系统中的等价性。
2. MA（Arthur-Merlin protocol的1-message模式）
如上图所示，若在AM中仅有一次消息交互，则可称为该种情况下可称为MA，
M
A
⊆
A
M
MA\subseteq AM
MA⊆AM。pover对
x
x
x的proof
m
m
m若为真，则verifier通过运行polynomial time test信服该proof的概率应不低于2/3，若proof为假，则信服该结果的概率应不高于1/3。
- if x ∈ L x\in L x∈L, then ∃ m \exist m ∃m, P r r ( V ( m , r ) = 1 ) ≥ 2 3 Pr_r(V(m,r)=1)\geq \frac{2}{3} Prr(V(m,r)=1)≥32,
- if x ∉ L x\notin L x∈/L, then ∀ m \forall m ∀m, P r r ( V ( m , r ) = 1 ) ≤ 1 3 Pr_r(V(m,r)=1)\leq \frac{1}{3} Prr(V(m,r)=1)≤31.
若并行运行以上流程 n n n次，则有，对于 ∀ n \forall n ∀n:
- if x ∈ L x\in L x∈L, then ∃ m \exist m ∃m, P r r ( V ( m , r ) = 1 ) ≥ 1 − 1 2 n Pr_r(V(m,r)=1)\geq 1-\frac{1}{2^n} Prr(V(m,r)=1)≥1−2n1,
- if x ∉ L x\notin L x∈/L, then ∀ m \forall m ∀m, P r r ( V ( m , r ) = 1 ) ≤ 1 2 n Pr_r(V(m,r)=1)\leq \frac{1}{2^n} Prr(V(m,r)=1)≤2n1.
所以，综上对MA的perfect completeness表述可为：
- if x ∈ L x\in L x∈L, then ∃ m \exist m ∃m, P r r ( V ( m , r ) = 1 ) = 1 Pr_r(V(m,r)=1)=1 Prr(V(m,r)=1)=1,
- if x ∉ L x\notin L x∈/L, then ∀ m \forall m ∀m, P r r ( V ( m , r ) = 1 ) ≤ 1 2 Pr_r(V(m,r)=1)\leq \frac{1}{2} Prr(V(m,r)=1)≤21.
参考资料： [1] https://en.wikipedia.org/wiki/Arthur–Merlin_protocol [2] 讲义：lect22-An Arthur-Merlin proof for the Hilbert’s Nullstellensatz [3] 讲义：Lecture 17- Arthur-Merlin games, Zero-knowledge proofs [4] 论文《Private coins versus public coins in interactive proof systems》
