「二十一世紀的運算」－學術研討會，A Modern Theory of Trust-but-Verify

先聲明一下，我的寫作習慣是將講者的意思經自己的思考融入後，以自己的觀點描述出來，不見得表示原講者就是這麼說。

第二位講者是姚期智院士 Andrew Chi-Chih Yao，唯一得到Turing Award的華人，相當有學者風範的人，這點在Q&A時特別感受得到，回答問題的第一件事是：”先讓我重述你的問題，確定我是否有弄懂你的意思．．．”，可惜姚院士是講理論，沒有相關背景很難明白，所以問的人問得莫名其妙，回答時有點雞同鴨講。

我有幸於四下時修了sctsai老師的Randomized Algorithm，加上幾前週在seminar聽到呂及人博士演講，今天姚院士的演講和呂及人博士講的課題差不多，差別在於姚院士用系統化的流程點出”Trust-but-Verify”。

40分鐘左右的演講分成四個段落，可說是今天演講裡最有系統，會讓人想看slide的演講，但是．．．為什麼不用中文講啊？

I. Transform of Knowledge

主旨是”讓你相信我了解這事”，比方老警探聲稱：”我閒一下就知道誰是壞人誰是好人”，但他無法系統化的證明給你看，他只能藉多次事件證明他確實有這能力（當然，姚院士不是舉這個例子）。比方有兩杖硬幣，一真一假，常人無法分辨，路人甲說他有能力判斷，但很難說明。在你知道答案的前提下，可以隨機取其中一個問路人甲，這是真的還假的，顯然路人甲只有1/2機率能猜對，連玩 N 次都被猜中的機率是 1/(2^N)，比方20次全中的機率只有百萬分之一，在這樣的前提下，我們有很大的”證據”相信路人甲有能力判斷。

這有很多相關想法，像是密碼學中講的zero-knowledge proof，在不讓對方獲知任何資訊的情況下證明一件事，實例是身份辨別。或是用演化計算(Evolutionary Computation）產生判斷下棋殘局的程式，演化計算的”產物”，通常是人類無法讀懂的程式（演算法），若我們能經由實驗和機率分析得知這個程式以極低的機率（可能比隕石擊中你家還低）完全答對殘局的結果，那我們確實可以相信這個程式有能力判斷殘局，就可以在無法理解卻信任的情況下使用它。

The Interactive Proof Theorem：Any game has a convincing efficient Interactive Proof.

這裡強調的Interactive Proof，是用實測證明，而不是用理論證明，對我來說是是很有新意的想法，用理論的方式證明實務的做法，和一般測試的含意不同，有興趣了解這類思維，可以看看Randomized Algorithm的書。但還是要注意測試的方式確實會影響結果，比方輸入隨機兩個數字給排序程式，測個三萬次都對也只能證明這個排序程式有正確的比大小（comparison）能力，不表示它有能力做一般排序（輸入三個數字以上）。

II. Probabilistic Checkable Proofs

問題描述：別人寫了500頁的證明，你就得讀500頁的證明才能判斷證明是否正確。希望能做到隨機讀一小段，比方某頁的4行描述，就能驗證原證明有很大的機率正確。

上次呂及人博士講這個時我做一些質疑，呂博士說實際使用沒這麼簡單，要將待驗證的證明轉為Probabilistic Checkable Proofs規定的格式，才能讓Probabilistic Checkable Proofs Verifier驗證。不管是上次還是這次，我都聽不懂。

III. Application to Software Download

given program, certificate，verifier(program, verifier) will output true or false，藉由verifier驗證program是否安全，現行的做法是用MD5演算法將program產生很小的字串，下載program後，執行MD5(program)，看結果和網站上的MD5 message是否一致。不過姚院士這裡指certifiacte >> program，和現行制度大大相反，在這樣的前提下，想想是否可以不用certificate就能做到驗證，也就是verifier(program)就能做出正確判斷，這個講題和Probabilistic Checkable Proofs相關。

IV. Conclusion

Trust-but-verify，讓人”相信（trust）”的成本是遠低於”驗證（verify）”的，證明很難完成，完成後又很難驗證證明的正確性，理論研究不見得都要用寫證明（proof）的方式做驗證（verify)，可以用Interactive Proof的方式使人信服（trust）而願意使用。

個人心得

姚院士的講題算是這個領域較一般性的說明，之前或多或少聽過，沒能有更多的知識增進有點可惜，但能看到學者風範的談吐，演講和回答問題的態度，讓我直接感受到言教身教，咦？我好像愈寫愈把心中姚院士的形象美化++了 。