關於 量子演算法原理 ，我們在網路上蒐集到這些相關的討論、資訊與評價

【快來抽書：重磅科幻小說】《AI 2041：預見10個未來新世界》
(送出2本)

#李開復說看完這本精彩小說你就懂AI了
#歡迎青少年與所有大人提前進入美麗AI新世界
#李開復架構10幅技術藍圖
#科幻小說家陳楸帆依藍圖築構10個AI新世界

💖【參加辦法】(四步驟：按讚、留言、標兩個朋友，公開分享)

1. 即刻起至7/24(六)晚上12點止，在本文按讚
2. 在本文底下留言【AI 2041：預見10個未來新世界】並【標註兩個朋友】
3. 在自己臉書公開分享本文

4. 7/26(一)進行電腦亂數抽獎(共抽出2本，將以私訊通知)

💖這不是業配文喔，菊仙純粹分享
💖一人僅限參加一次(貼文兩次以上也只算一次喔)

─────科學 + 科幻─────

➤李開復架構10幅「技術藍圖」，科幻小說家陳楸帆依藍圖築構10個「AI新世界」
➤李開復40年的AI專業經驗 + 科幻小說家陳楸帆的無邊想像
➤「虛構的敘事」與「非虛構的科技評論」完美結合
➤展現20年後被AI 技術深刻改變的未來世界。

AI時代已經開啟。在我們面前，機遇與挑戰並存。
如AI與人性特質如何共存等諸多課題，都需要深入探索和思考。──李開復

想要創造什麼樣的未來，就從想像那樣的未來開始。──陳楸帆

　　．AI能否幫助人類從根源上預防疫情？
　　．如何應對未來的職場挑戰？
　　．在AI主導的世界中如何確保文化多樣性？
　　．如何教導下一代適應人類與AI共存的新社會？
　　．面對AI帶來的社會問題所隱含的人性拉鋸戰，我們如何抉擇？

AI能創造前所未有的財富與價值，能徹底改變醫學和教育，能提升人類的工作、娛樂和交流的品質，能把人類從日常工作中解放出來。

不過，AI也會帶來無數挑戰和風險：

•演算法偏見
•安全隱患
•深度偽造
•隱私資料的侵犯
•自主武器的使用
•取代人類員工。

不過，以上情況並非AI主導造成的，而是惡意或草率使用AI技術的幕後黑手。

全球AI領軍人物李開復最關切的是，AI正飛速發展，人類的未來將通往何方？
　　
歡迎來到2041！

全球重磅推薦

　　✓劉慈欣│2015年雨果獎得主、《三體》作者
　　✓雷．達里歐（Ray Dalio）│橋水基金創辦人
　　✓薩蒂亞．納德拉（Satya Nadella）│微軟董事長
　　✓楊立昆（Yann LeCun）│圖靈獎得主

★本書有著開創性的結構，用前所未有的跨越文類的多視角，展望人工智慧構造的未來，讓我們從理性上把握未來發展趨勢的同時，也從感性上觸摸未來的質感和溫度。生動逼真的科幻想像與嚴謹深入的技術論述完美地結合，讓本書無論是從科幻還是從技術現實的角度，都具有無與倫比的魅力。──劉慈欣，2015年雨果獎得主、《三體》作者　

★對未來的解析精闢又精采。──雷．達里歐（Ray Dalio），橋水基金創辦人、《紐約時報》第一名暢銷書《原則》作者

★陳楸帆的創作實力，加上李開復的科技功底，建構出令人好奇又恐懼的AI未來世界。閱讀這本絕無冷場的好書，就能明白某些科技會在何時，又會如何發展成熟，而全體人類又會面臨什麼樣的影響。──薩蒂亞．納德拉（Satya Nadella），微軟董事長

★唯有有膽有識之人，才敢預測AI的未來。這是一位科技界的先驅泰斗，與一位洞悉未來的科幻作家，攜手打造的開示之書，對於AI科技會如何影響我們的生活，提出大膽又殷切的見解。──楊立昆（Yann LeCun），圖靈獎得主，臉書首席AI科學家

★我們能不能適應我們一心創造的奇異新世界？我們知道無從想像的改變即將到來，卻不知這些改變對人類有何影響。李開復跟陳楸帆的《AI 2041》，對於我們即將面對的未來有最詳盡的描寫，最深情的叮嚀。──班奈特．米勒（Bennett Miller），「魔球」與「暗黑冠軍路」導演，曾獲奧斯卡獎提名

★我們正處於AI發展史的關鍵時刻。我所讀過的書當中，唯有這本創意四射的佳作，才真正一語道破AI的精髓。與其思考該不該信任AI，還不如將AI當成一種工具，一種由我們人類塑造的工具。李開復在《AI 2041》的精闢分析，凸顯出這項人類必須積極承擔的責任。陳楸帆筆下的精采故事，昭示了AI可將曾經無解的問題，化為充滿新機的未來。──亞利安娜．哈芬登（Arianna Huffington），Thrive Global 創辦人兼執行長

★《AI 2041》是科學與科幻的完美融合，揭示了AI將如何全面滲透我們的生活，而我們想創造造福全人類的科技未來，又會面臨什麼樣的挑戰。──馬克．貝尼奧夫（Marc Benioff），Salesforce董事長兼執行長

★將AI應用於商業經營，通常必須先研究這項科技，再思考如何應用。《AI 2041》卻帶領讀者走上相反的道路。兩位作者李開復跟陳楸帆，透過精采絕倫的故事，引領我們走入逼真的未來世界。再以淺顯易懂的說明，闡述AI科技的原理，造就一本讓人欲罷不能又大開眼界的好書，想了解如何應用AI，絕不可錯過此書。──馬克．庫班（Mark Cuban）
.

…………..【內容快速勾勒】…………

第一章 一葉知命
在印度孟買，一個當地家庭參與了一項由深度學習賦能的智慧保險計畫。為了改善這家人的生活，AI保險程式透過一系列生活應用與這家的每位成員相連，這些應用與保險演算法進行動態互動。然而，正值青春期的女兒卻發現，這套AI保險程式似乎總是在「巧妙」地阻撓她追求愛情。

【開復解讀】
一、什麼是深度學習
二、深度學習：能力驚人但也力有未逮
三、深度學習在網際網路和金融行業的應用
四、深度學習帶來的問題

第二章 假面神祇

一名懷揣電影夢想的奈及利亞影音製作者，被神祕公司招募來製作一段真假難辨的Deepfake（深度偽造）影片。如果他成功地做到瞞天過海，將引發災難性的後果，從而改變整個國家未來的命運……

【開復解讀】
一、什麼是電腦視覺技術
二、電腦視覺技術的應用
三、電腦視覺的基礎─卷積神經網路（CNN）
四、Deepfake
五、生成式對抗網路（GAN）
六、生物特徵識別
七、AI安全

第三章 雙雀

AI教師化身為韓國雙胞胎孤兒所喜愛的卡通化虛擬夥伴，分別幫助他們挖掘和發揮潛能。多虧有了AI的重要分支「自然語言處理技術」，這兩個AI夥伴才能夠用人類的語言流利地和孤兒交談，建立情感連結和信任，幫助兄弟倆在失散多年之後重新找回彼此。

【開復解讀】
一、自然語言處理（NLP）
二、有監督的NLP
三、自監督的NLP
四、NLP應用平台
五、NLP能通過圖靈測試或者成為通用人工智慧嗎？
六、教育領域的AI

第四章 無接觸之戀

在疫苗問世後，新冠病毒毒株定期變異，繼續肆虐人間。二十年後，人類不得不學會與病毒共存，家家戶戶都配有機器人管家，以減少人與人接觸的風險。在這個故事裡，身在上海的女主角患上了一種把自己與世隔絕的恐懼症。當愛神來叩門時，她內心一方面渴望擁抱愛情，另一方面卻極度懼怕和戀人親密接觸。誰能幫助她邁出這關鍵性的一步？

【開復解讀】
一、數位醫療與人工智慧的融合
二、傳統藥物及疫苗研發
三、AI在蛋白質折疊、藥物篩選及研發方面的潛力
四、AI與精準醫療及診斷：讓人類活得更加健康長壽
五、機器人技術
六、機器人技術的工業應用
七、機器人技術的商業場景和消費級市場
八、AI時代的數位化工作

第五章 偶像之死

故事描述了未來的娛樂業。到那時，遊戲都將是全感官立體沉浸式的，虛擬和現實之間的界限將變得虛實難辨。本故事發生在日本東京，主角利用AI和VR技術，讓她所愛慕的偶像復活過來，引領她去調查偶像之死背後的真正原因。

【開復解讀】
一、什麼是XR（AR⁄VR⁄MR）
二、XR技術：全方位覆蓋人類的六感
三、XR技術：超感官體驗
四、XR技術的兩大挑戰：裸眼顯示和腦機介面
五、XR技術普及背後的倫理道德和社會問題

第六章 神聖車手

二十年後，自動駕駛技術正處於從人類司機切換到全AI司機的過渡時期。在這個有著動作大片節奏感的故事中，斯里蘭卡一名電競少年被招募進了一個神祕計畫，他將要面對的並不僅僅是遊戲中的對手……

【開復解讀】
一、自動駕駛
二、真正的自動駕駛什麼時候才會出現
三、L5自動駕駛車輛將帶來的影響
四、阻礙L5自動駕駛的非技術性難題

第七章 人類剎車計畫

策劃〈人類剎車計畫〉的惡魔是一名歐洲電腦科學家。他在經歷了一場與氣候變化有關的家庭悲劇後，精神失常，開始利用量子計算、自動武器等突破性技術作惡，對人類進行史無前例的瘋狂報復。駭客與反恐特警聯手力挽狂瀾，人類命運將何去何從？

【開復解讀】
一、量子計算
二、量子計算在安全領域的應用
三、什麼是自主武器？
四、自主武器的利與弊
五、自主武器會成為人類生存的最大威脅嗎？
六、如何解決自主武器帶來的危機？

第八章 職業救星

隨著AI向愈來愈多的行業穩步進軍，愈來愈多職位逐漸被AI技術取代，那麼人類接下來能從事的工作是什麼？一場發生在舊金山的建築業大震盪，帶領我們走入一個新的行業──再就業服務。如何幫助結構性失業人群找回屬於人類的價值與尊嚴感，也許同樣需要AI的幫助。

【開復解讀】
一、AI將如何取代人類員工？
二、AI取代人類員工背後的潛在危機
三、UBI會是一劑良方嗎？
四、從事哪些工作的人不容易被AI取代
五、如何化解AI時代的人類工作危機？
六、迎接AI新經濟以及制定全新的社會契約

第九章 幸福島

一位中東的開明君主想試驗將AI做為給人類帶來終極幸福感的靈丹妙藥。然而，幸福是什麼？幸福如何衡量？這位君主邀請了各界名人聚集在一座私密的島嶼上，讓這些名人共享他們的個人資料，並成為探索這個奇妙命題的小白鼠。然而，試驗卻出人意料地走向了失控……

【開復解讀】
一、AI時代的幸福準則
二、如何利用AI衡量和提升幸福感
三、AI數據：去中心化 vs. 中心化
四、誰值得我們信賴並有資格儲存我們所有的資料？

第十章 豐饒之夢

在布里斯班一座由AI管理的養老社區中，一位原住民女孩如何幫助罹患阿茲海默症的海洋生物學家解開身世之謎？故事中勾勒了在澳大利亞的未來社會的兩種貨幣：一種是錢，其重要性日益減弱；另一種是代表聲譽和尊重的價值的新貨幣，其重要性與日俱增。

【開復解讀】
一、可再生能源革命：太陽能＋風能＋電池技術的有效結合
二、材料革命：走向無限供給
三、生產力革命：AI與自動化
四、豐饒時代：技術發展的必然結果
五、稀缺時代與後稀缺時代的經濟模式
六、豐饒時代的貨幣制度
七、豐饒時代的挑戰
八、豐饒時代之後，會是奇點時代嗎？
九、AI 的故事會是圓滿的結局嗎？

•關於2041年的預測

【書訊】https://www.books.com.tw/products/0010895593?sloc=main

四兩撥千斤！ 創新工場首席科學家AI大牛周明博士率瀾舟團隊刷新CLUE新紀錄，輕量化模型孟子一鳴驚人！

本週，中文語言理解權威評測基準CLUE榜單，被「低調」刷新。

不同的是，不是大公司、不是超大模型……

一個新面孔，一個輕量化模型，首戰即登頂，四兩撥千斤。

CLUE榜單近年來由巨頭——騰訊、搜狗、華為、阿里達摩院輪番霸榜的格局，被首次打破。

瀾舟科技-創新工場推出的孟子模型，以十億參數完成了此前百億、千億參數模型刷新的紀錄。

這也是瀾舟科技首次對外曝光，背後團隊負責人，正是創新工場首席科學家、全球AI大牛周明博士。以下文章解釋了這個模型的原理，文章來自《量子位》微信公眾號，經授權轉載。

▎輕量化模型孟子？

孟子，基於瀾舟團隊自研技術研發的大規模預訓練語言模型。

包括創新工場、上海交通大學、北京理工大學等單位參與聯合研發。

可處理多語言、多模態數據，同時支持多種文本理解和文本生成任務，能快速滿足不同領域、不同應用場景的需求。

孟子模型基於Transformer架構，僅包含十億參數量，基於數百G級別涵蓋互聯網網頁、社區、新聞、電子商務、金融等領域的高質量語料訓練。

但誰也沒想到，小模型卻有大智慧，一經登場，打破格局。

CLUE，中文語言理解領域最具權威性的測評基準，涵蓋文本相似度、分類、自然語言推理、閱讀理解等共10項語義分析和理解類子任務。

該榜單競爭激烈，幾乎是業內所有自然語言理解玩家必爭之地。

騰訊、搜狗、華為、阿里達摩院等更是輪番霸榜刷新紀錄。

而且隨著大參數模型愈演愈烈，CLUE還漸有巨頭壟斷之勢。

因為百億、千億甚至萬億參數的大模型，已然不再是創業或其他玩家可與之爭鋒。

萬萬沒想到，瀾舟科技-創新工場團隊出手，四兩撥千斤。

因為孟子，走的是基於輕量級、高效訓練的研究路線，致力於構建十億級別的小模型，充分發揮已有參數下的模型潛力，有利於快速、低成本地落地現實業務場景。

孟子預訓練模型性能比肩甚至超越千億大模型，在包含文本分類、閱讀理解等各類任務上表現出色。

相對已有的中文語言模型，孟子模型實現了多項突破性進展：
 1） 堅持「小而精」的輕量化訓練策略。實現在同等模型規模下，遠超公開模型的性能。作為精巧的小模型，對標「巨無霸」，小模型性能超越千億規模模型。
 2）使用知識圖譜增強模型，讓 AI 真正獲得知識。孟子模型具備頂尖的語言理解能力，在權威CLUE中文理解評測的總排行榜，以及分類排行榜和閱讀理解排行榜均位列第一，刷新三項榜單世界紀錄。總排行榜分數突破84分，逼近人類基準分數（85.61）。
 3）靈活的領域和場景適應能力，方便快速定制和應用。基於T5-style的端到端生成的訓練範式，同步適配BERT-style的判定式架構，既能理解也能生成。便於適配行業應用，覆蓋廣泛業務場景。

當然，隨著孟子一鳴驚人，也必然能讓輕量化模型研究來到聚光燈下。

▎原理方法和應用？

在輕量化模型算法研究方面，基於自研的基於語言學知識、知識圖譜和領域數據增強等技術，從模型架構（包括基礎層Embedding表示和交互層Attention機制）到預訓練策略進行了全方位改進。

具體有四方面：
 1) 模型結構方面，將語義角色、詞性標註等語言學特徵融合到Embedding表示中，基於句法約束引入註意力機制中，從而提升模型對語言學知識的建模能力。
 2) 訓練策略上，引入基於實體知識和Discourse的Mask機制，強化模型對語言成分和語篇關係的表徵。
 3) 為進一步提高訓練效率，使用了大模型蒸餾和初始化小模型策略。
 4) 為更好地將孟子模型適應垂直領域如金融、營銷，使用了領域數據繼續訓練並構造相應的提示模版（Prompt），取得了明顯的性能提升。

基於以上算法策略，實現從語料中高效學習涵蓋詞級、句子級和語篇級知識，大幅提升語言模型提煉語言結構和語義信息能力，以及良好的領域遷移能力，適應廣泛的產品應用場景。

另外，在Finetune的進展方面，如何將預訓練模型用於各項任務？

瀾舟團隊也有總結，從數據增強、知識蒸餾、遷移訓練、訓練優化等方面展開了一些探索，進一步提升語言模型的性能：

 1) 數據增強：使用領域相關數據；
 2) 知識蒸餾：基於Teacher-Student自蒸餾提升訓練效率；
 3) 遷移訓練：結合課程學習的思想，由易到難訓練下游模型；
 4) 訓練優化：使用多種訓練目標，多角度提升模型能力；

而且孟子還已經展開了垂直化領域應用。

基於領域適應技術，孟子模型已深度垂直化賦能相應行業。典型的例子為適用於金融領域的孟子模型，領域適應策略主要包含兩大方面：

 1) 通過大規模的泛金融領域語料，將通用孟子模型遷移到金融領域。金融版孟子模型已經應用於多個金融行業的合作企業，在金融知識圖譜搭建、脫水研報、公告抽取等多個任務上獲得了出色的表現。
 2) 通過大規模的營銷領域語料，將孟子模型遷移到數字營銷領域，完成了營銷文案生成、新聞摘要等多項任務，將用於行業頭部的數字營銷公司和多個世界五百強企業的合作之中。

瀾舟方面還透露，孟子模型已在多個領域成功落地實踐，衍生出多項行業領先的產品，涵蓋文本生成、行業搜索、機器翻譯等諸多領域。

並且毫無疑問的是，因為輕量級模型具有的模型參數較少、快速推斷的特點，更易於線上部署和推廣到移動設備中，自然不會局限於現有應用和場景，接下來還會有更廣泛的研究和應用場景中。

▎瀾舟團隊？

最後，也簡單介紹本次一鳴驚人的新面孔瀾舟科技。

瀾舟科技是創新工場孵化的一家認知智能公司。公司創始人——周明博士。

AI領域內，周明已不用過多介紹，他是公認的世界級AI科學家，自然語言處理領域的代表性人物。

周明博士在2020年加盟創新工場，擔任創新工場首席科學家。
而瀾舟科技則針對商業場景的數字化轉型，基於大數據、知識圖譜和行業模型，提供新一代的信息檢索、知識推理和商業洞見技術和相關產品。

據稱目前已與國內外幾十所著名高校和十餘個相關領域的頭部企業建立了穩定的合作關係。

值得注意的是，瀾舟科技除了大牛坐鎮，其實也是行業趨勢的體現。

引用創新工場董事長兼CEO李開復最新分享來說：

AI的發展可以按照兩個時間點劃分。

第一個時間點是2015年，以CNN為核心的計算機視覺技術讓機器超越了人類，帶來了人臉識別、智能質檢、無人零售、智慧城市、無人駕駛等商機。

而第二個時間點出現在2019年，以大模型為代表的自然語言方向取得突破性進展，讓NLP從數據、信息走向知識和洞見成為可能，將會在翻譯、語音識別、法律、金融、新聞、廣告、醫療、娛樂等大賽道帶來機遇。

「如果說CNN造就了今天計算機視覺領域的突破和眾多應用，預訓練大模型+微調也將帶來自然語言的百花齊放的發展，用數據智能驅動各類業務的升級。瀾舟科技在周明老師的帶領下取得了今天的成果，在新機遇面前躬身入局，一起發掘NLP領域的黃金發展期」，李開復說到。

📜 [專欄新文章] 瞭解神秘的 ZK-STARKs
✍️ Kimi Wu
📥 歡迎投稿： https://medium.com/taipei-ethereum-meetup #徵技術分享文 #使用心得 #教學文 #medium

上一篇關於 zkSNARK扯到太多數學式，導致很難入手，這次介紹 STARK 會盡量減少數學式，以原理的方式跟大家介紹。

STARK 被視為新一代的 SNARK，除了速度較快之外，最重要的是有以下好處1. 不需要可信任的設置（trusted setup），以及
2. 抗量子攻擊

但 STARK 也沒這麼完美，STARK 的證明量(proof size)約 40–50KB，太佔空間，相較於 SNARK 只有288 bytes，明顯大上幾個級距。此外，這篇論文發佈約兩年的時間，就密碼學的領域來說，還需要時間的驗證。

STARK 的 S 除了簡潔（Succinct）也代表了擴展性（Scalable），而T代表了透明性（Transparency），擴展性很好理解，透明性指的是利用了公開透明的算法，可以不需要有可信任的設置來存放秘密參數。
SNARK 跟 STARK 都是基於多項式驗證的零知識技術。差別在於，如何隱藏資訊、如何簡潔地驗證跟如何達到非互動性。

快轉一下 SNARK 是如何運作的。
Alice 有多項式 P(x)、Bob有秘密 s，Alice 不知道 s、Bob 不知道 P(x)的狀況下，Bob 可以驗證P(s)。藉由同態隱藏（Homomorphic Hindings）隱藏Bob的 s → H(s)，藉由 QAP/Pinocchio 達到了簡潔地驗證，然後把 H(s) 放到CRS（Common Reference String），解決了非互動性。細節可以參考之前的文章 。

問題轉換

零知識的第一步，需要先把「問題」轉成可以運算的多項式去做運算。這一小節，只會說明怎麼把問題轉成多項式，至於如何轉換的細節，不會多琢磨。

問題 → 限制條件 → 多項式

在 SNRAK 跟 STARK 都是藉由高維度的多項式來作驗證。也就是若多項式為： x³ + 3x² + 3 = 0，多項式解容易被破解猜出，若多項式為 x^2000000 + x^1999999 + … 則難度會高非常多。

第一步，先把想驗證的問題，轉換成多項式。
這邊以Collatz Conjecture為例子，什麼是Collatz Conjecture呢？（每次都用Fibonacci做為例子有點無聊 XD）
1. 若數字為偶數，則除以2
2. 若數字為奇數，則乘以3再加1 (3n+1)

任何正整數，經由上述兩個規則，最終結果會為 1 。（目前尚未被證明這個猜想一定成立，但也還未找出不成立的數字）

52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.

把每個運算過程的結果紀錄起來，這個叫做執行軌跡（Execution Trace），如上述52 -> 26 -> … -> 1。接著我們把執行軌跡轉換成多項式（由執行軌跡轉成多項式不是這裡的重點，這裡不會贅述，細節可以參考 StarkWare的文章 ）如下

https://medium.com/starkware/arithmetization-i-15c046390862

合成多項式

接著就把這四個限制條件的多項式合成為一個，這個最終的多項式就叫做合成多項式（composition polynomial），而這個合成多項式就是後面要拿來驗證的多項式。

就像一開始提的，SNARK跟STARK都是使用高維度多項式，接著，來介紹STARK是藉由哪些方式，達到零知識的交換、透明性(Transparency)跟可擴展性(Scalability)。

修改多項式維度

這一步是為了後面驗證做準備的。在驗證過程使用了一個技巧，將多項式以2的次方一直遞減為常數項（D, D/2, D/4 … 1），大幅減低了驗證的複雜度。因此，需要先將多項式修改為2^n維度

假設上述的每個限制多項式（不是合成多項式喔）為Cj(x)，維度為 Dj，D >= Dj 且 D 等於2^n，為了達到 D 維度，乘上一個維度（D -Dj）的多項式，

所以最終的合成多項式，如下

其中的αj、βj是由驗證者(verifier)所提供，所以最終的多項式是由證明方(prover)跟驗證方所共同組成。

*這小節的重點是將多項式修改成D維度，覺得多項式太煩可忽略

FRI

FRI 的全名是”Fast RS IOPP”（RS = “Reed-Solomon”, IOPP = “Interactive Oracle Proofs of Proximity”）。藉由FRI可以達到簡潔地驗證多項式。在介紹FRI 之前，先來討論要怎麼證明你知道多項式 f(x) 為何？

RS 糾刪碼：

糾刪碼的概念是把原本的資料作延伸，使得部分資料即可以做驗證與可容錯。其方式是將資料組成多項式，藉由驗證多項式來驗證資料是否正確。舉例來說，有d個點可以組成 d-1 維的多項式 y = f(x)，藉由驗證 f(z1) ?= y，來確定 z1是否是正確資料。

回到上面的問題，怎麼證明知道多項式？最直接的方式就是直接帶入點求解。藉由糾刪碼的方式，假設有d+1個點，根據Lagrange插值法，可以得到一個 d 維的多項式 h(x)，如果如果兩個多項式在（某個範圍內）任意 d 點上都相同（ f(z) = h(z), z = z1, z2…zd），即可證明我知道 f(x)。但是我們面對的是高維度的多項式，d 是1、2百萬，這樣的測試太沒效率，且不可行。FRI 解決了這個問題，驗證次數由百萬次變成數十次。

降低複雜度

假設最終的合成多項式為 f(x)，藉由將原本的1元多項式改成2元多項式，以減少多項式的維度。假設 f(x) = 1744 * x^{185423}，加入第二變數 y，使 y = x^{1000}，所以多項式可改寫為 g(x, y) = 1744*x^{423}*y^{185}。藉由這樣的方式，從本來10萬的維度變成1千，藉由這種技巧大幅降低多項式的維度。在 FRI 目前的實做，是將維度對半降低 y = x²（f(x) = g(x, x²)）。

此外，還有另一個技巧，將一個多項式拆成兩個較小的多項式，把偶數次方跟奇數次方拆開，如下：

f(x)= g(x²) + xh(x²)

假如：

f(x) = a0 + a1x + a2x² + a3x³ + a4x⁴ + a5x⁵
g(x²) = a0 + a2x² + a4x⁴, （g(x) = a0 + a2x + a4x²）
h(x²) = a1x + a3x² + a5x⁴, （h(x) = a1 + a3x + a5x² ）

藉由這兩個方法，可以將高維度的多項式拆解，重複地將維度對半再對半，以此類推到常數項。而 FRI 協議在流程上包含兩階段 — 「提交」跟「查詢」。

提交階段：提交階段就如同上述過程，將多項式拆解後，由驗證者提供一亂數，組成新的多項式，再繼續對多項式拆解，一直重複。

f(x) = f0(x) = g0(x²) + x*h0(x²)
==> f1(x) = g0(x) + α0*h0(x), ← α0（驗證者提供）
==> f2(x) = g1(x) + α1*h1(x), ← α1（驗證者提供）
==> . . .

查詢階段：這個階段要驗證證明者所提交的多項式 f0(x), f1(x), f2(x), … 是否正確，這邊運用一個技巧，帶入任意數 z 及 -z（這代表在選域的時候，需滿足 L²= {x²：x ∊ L}，這邊不多提）。所以可以得

f0(z) = g0(z²) + z*h0(z²)
f0(-z) = g0(z²) -z*h0(z²)

藉由兩者相加、相減，及可得g0(z²)、h0(z²)，則可以計算出f1(z²)，再推導出f1(x)，以此類推驗證證明者傳來的多項式。

Interactive Oracle Proofs (IOPs)

藉由FRI（RS糾刪碼、IOPs），將驗證次數由數百萬降至20–30次（log2(d)），達到了簡潔地驗證。不過，我們解決了複雜度，但還有互動性！

* 與SNARK比較 ：SNARK在驗證方面利用了QAP跟Pinocchio協定。

非互動性

藉由 Micali 建構（Micali construction）這個概念來解釋如何達到非互動的驗證。Micali 建構包括兩部分，PCPs（Probabilistically checkable proof）跟雜湊函數。PCPs 這是一個隨機抽樣檢查的證明系統。簡單來說，證明者產出一個大資料量的證明（long proof），經由隨機抽樣來驗證這個大資料量的證明。過程大約是這樣，證明者產出證明𝚿，而驗證者隨機確認 n 個點是否正確。

在STARK，我們希望達到：1.小的證明量，2.非互動。隨機抽樣可以讓達到小的證明量，那互動性呢? 想法很簡單，就是預先抽樣，把原本 PCPs 要做的事先做完，然後產出只有原本證明 𝚿 抽樣出的幾個區塊當作證明。但想也知道，一定不會是由證明者抽樣，因為這樣就可以作假。這裡是使用 Fiat-Shamir Heuristic 來作預先取樣。

首先，先把證明 𝚿組成 merkle tree，接著把 merkle root 做雜湊可得到一亂數 𝛒，而 𝛒 就是取樣的索引值。將利用𝛒取出來的區塊證明、區塊證明的 merkle tree 路徑跟 merkle root, 組一起，即為STARK 證明 𝛑。

到目前，只使用雜湊函數這個密碼學的輕量演算法。而雜湊函數的選擇是這個證明系統唯一的全域參數（大家都需要知道的），不像是 SNARK 有 KCA 使用的(α, β, 𝛾)等全域的秘密參數，再藉由 HH（同態隱藏）隱藏這些資訊來產生 CRS。因為證明的驗證是靠公開的雜湊函數，並不需要預先產生的秘密，因此 STARK 可以達到透明性，也不用可信任的設置。

接著，將FRI中需要互動的部分（驗證者提供 α 變數），使用上述的 PCP + Fiat-Shamir Heuristic， 即可達到非互動性。

* 與SNARK比較： SANRK 的非互動性是將所需的全域參數放到CRS中，因為全域參數是公開的，所以CRS裡的值使用了 HH 做隱藏。

MIMC

大部分證明系統，會使用算數電路來實作，此時，電路的複雜程度就關係到證明產生的速度。 STARK 的雜湊函數選用了電路複雜度較簡單的 MIMC，計算過程如下：

https://vitalik.ca/general/2018/07/21/starks_part_3.html

這樣的計算有另一個特性，就是無法平行運算，但卻又很好驗證，因此也很適合 VDF 的運算。Vitalik有一個使用 MIMIC 作為 VDF 的提案。

ps. 反向運算比正向慢百倍，所以會是反向計算，正向驗證

從上面的解釋，可以理解為什麼 STARK 不需要可信任設置，至於為什麼能抗量子？因為 SNARK 中使用了 HH 來隱藏秘密，而 HH 是依靠橢圓曲線的特性，但橢圓曲線沒有抗量子的特性（也就是可以從公鑰回推私鑰）。而STARK在整個過程中只使用了雜湊函數，而目前還沒有有效的演算法能破解雜湊函數，因此可以抵抗抗量子攻擊。

有錯誤或是不同看法，歡迎指教

參考：
StarkDEX Deep Dive: the STARK Core Engine
STARK 系列文：
STARK Math: The Journey Begins
Arithmetization I
Arithmetization II
Low Degree Testing
A Framework for Efficient STARKs
Vitalik 系列文：
STARKs, Part I: Proofs with Polynomials
STARKs, Part II: Thank Goodness It’s FRI-day
STARKs, Part 3: Into the Weeds
ZK-STARKs — Create Verifiable Trust, even against Quantum Computers
https://ethereum.stackexchange.com/questions/59145/zk-snarks-vs-zk-starks-vs-bulletproofs-updated

Originally published at http://kimiwublog.blogspot.com on November 12, 2019.

瞭解神秘的 ZK-STARKs was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.

👏 歡迎轉載分享鼓掌