【重返○○】黃崇凱／但不能想起太多

圖◎吳怡欣

2019年的最後幾分鐘，我在台南市區一家沒有名字的酒館。室內爆棚，許多人沒地方坐，店貓鑽進來客堆放的羽絨外套，穿行窗外，從煙霧熱烈交談的陽台吸菸區繞了進來，找不到一個角落窩著。我問朋友十年前在哪裡跨年，朋友露出被迫面對三角函數習題的表情，好像沒人可以準確回想起來。
　
我記得的是二十年前20世紀結束的午夜，我跟高中同學在往淡水的捷運上跟一大群陌生乘客互祝新年快樂。那列捷運中途停下，車廂廣播傳來司機急促的倒數聲，像是臨時決定那樣，帶點喘地從九開始數起。那時我回嘉義蹲重考班不到一個月，每天擠公車通勤，在兩百人的大教室裡分到一小塊位置，聽著全台跑的名師授課，在布道會般的氣氛下，反覆參詳考試拿高分的祕密。我忘了怎麼收到通知，在那個B. B. Call褪流行（我沒有），小海豚手機正在興起（我也沒有）的通訊過渡期，讀淡江大學的高中同學號召大家到台北跨年（難道是誰寫信給我）。當時沒多想上去要住哪裡，重考班年末最後一堂課結束，我跳上客運巴士，一路晃上台北。由南向北的高速公路，像是從很深很深的地底往上的電梯，我在一個方形鐵盒緩緩迎向最亮的夜空。
　
找到同學住處，發現他的學生套房門口疊了有十幾公分那麼高的鞋子，沒人清楚知道等等要去哪裡、怎麼移動。有同學說，當然去市政府那裡啊，我們這些桃園來的、新竹來的、台中來的、嘉義來的毫無地理概念，只能跟著走。所有開往市區的捷運列車都塞滿人，一路塞到台北車站換線過程中，有些人沖散了。擠上藍線列車，隨著人潮吞吐推擠到市政府周邊，又沖散一些人。我跟搭著彼此肩膀的兩、三個同學決定放棄，打算折回淡水，但無法估算時間，就這樣在捷運上像一包冷凍雞肉被拎到新世紀的起點。
　
到了夏天，我重考完，聽說讀淡江的同學兵役體檢出心臟雜音，還來不及進一步安排檢查，某天午後他突然心口絞痛昏倒，被送到北港的媽祖醫院。他沒再醒來，幾個星期後過世。
　
2005年的最後一晚，我在巴黎的旅館房間，跟當時共處一室的女友嘔氣不說話，偶然想起那個早逝的同學。我從沒到過那麼冷的地方，而在將近兩個星期的旅行後，我非常疲憊。旅行之初，我一抵達戴高樂機場就轉高鐵往女友住的小城翁傑待幾天。接著我們一起到史特拉斯堡、日內瓦、尼斯，完成法國東部外掛瑞士的大縱走，最後回到巴黎。起先幾天，我們懷著些微焦慮跟彼此相處，擔心自己和電話裡、信件裡的形象不符。因為我們真的不是那麼熟。但戀愛濾鏡開到最大，一切都很好。我向熟識的學長借了十萬元好讓我開立存款證明，以便申請申根簽證買機票。我向我媽說我非到法國找這女孩子不可，拜託借我旅費。那陣子我病急亂投醫似地丟文學獎比賽，讓我那僅有的幾篇爛小說四處流浪。沒有一篇中獎。我蹺了兩星期的研究所課程，不遠千里為的是專程戳破我的幻想大泡泡。我本來以為我是去合唱那首陳綺貞的〈太多〉，一起上巴黎鐵塔、寄明信片給彼此，到羅浮宮看畫。結果一項也沒達成，只有在羅浮宮外面的玻璃金字塔周圍頂著冷雨寒風走來走去。回程飛機上，我才明白自己唱的其實是巫啟賢的〈太傻〉。還不到夏天，那段短促的感情就像包廂時間快用完時，潦草唱個幾段就切歌了。
　
有兩、三年，我幾乎每星期都會從公館出發，騎摩托車過橋，沿著中永和旁邊的環河路找那時在蘆洲經營卡拉OK小吃店的媽媽拿零用錢。媽媽做了大半輩子的紡織女工，婚後生完兩個孩子，在農村糾集一批主婦開設代工廠專攻絨毛娃娃，據說代工品質一流。90年代曾有玩具製造商到對岸設廠，找她去做管理職，她說我又不認識字去那裡做什麼。但我很確定她識字。她曾經堅持下工後每晚騎機車到嘉義市區讀小學補校，從ㄅㄆㄇ學起。有次我跟著她去上課，順手和她一起作弊應付隨堂考試。課程結束，我媽拿到畢業證書，據說是全班第三名。媽媽在兩個兒子上大學後，突發奇想北上蘆洲找地方開卡拉OK店。她獨自找店面、搞定一切，開張營業，居然生意不惡。隔年我爸就隨著妻子的腳步，在店裡做起頭家，幫忙上菜、敬酒，招呼客人。我總是在週末傍晚六、七點到蘆洲，店裡偶有三兩來客，打完招呼隨即上二樓，窩在客房看電視。我國中時在家聽過我媽深夜call-out給電台節目，握著麥克風似地對話筒唱歌。她坐在裁縫車前，歌聲迴盪在漆黑的鐵皮屋內，穿過其他裁縫車、裝訂絨毛娃娃眼珠的橡膠槌、分堆放置的組裝零件、拆解的樣品模版。如果拿著電話分機聽，大概會有多聲道環繞感。她似乎跟電台主持人、常常call-in到節目唱歌的其他聽眾也成了朋友。我想她真的很喜歡唱歌，也很喜歡交朋友，才會想開一家唱歌的店。
　
那時我也很愛唱歌，三不五時約同學挑便宜的通宵時段唱整晚。但我從來不在我媽的店裡唱歌。我討厭每星期都要騎車到蘆洲拿零用錢。我討厭那家卡拉OK小吃店，我甚至不覺得那是可以唱歌的地方。我討厭到了蘆洲店裡整晚只想窩在二樓房間的自己。我跟爸媽沒太多話好說，於是每週來找他們就只是為了零用錢，讓我變得更厭惡自己。只要我能忽略他們「錢怎麼用那麼快」的輕微抱怨，我就能要到兩千塊。SARS爆發期間，城裡人人戴口罩，電影院、KTV這類公共娛樂場所生意慘澹，自然也包括我媽那家店。那陣子的週末，我總會看到我爸稀釋一水桶漂白水，拿著拖把勤快拖地，要不就拿著酒精噴槍、抹布，擦拭店內桌椅。我只是在一旁看著，從沒出手幫忙。我知道店的生意不好，我知道我的學費是親戚湊錢幫忙出的，但我還是要來拿我的兩千塊。有時我甚至不過夜，拿了錢就掉頭騎回宿舍。
　
在我整個大學四年加研究所四年總共八年的學習年代，我爸媽只來過學校看我一次。雖然他們的主要目的是要去看師大路的超高人氣皮膚科診所。他們讓朋友送進城，來我宿舍，東看看西看看，最後像對沒錢開房間的小情侶爬上我宿舍的單人床睡午覺。他們睡到傍晚起來，我幫他們叫了計程車到師大路。送走他們後，我發現我們沒說幾句話，我沒帶他們到校園走走，也沒買福利社的牛奶或冰淇淋給他們嘗嘗。後來聽我媽說，他們等到將近半夜才看到醫生，醫生看不到五分鐘就打發他們領藥了。
　
我媽在我大學最後一年頂讓蘆洲店面，準備回鄉開一間更大的卡拉OK小吃店。她的大計除了開店，還要找地蓋新屋，串連各路親友，打算弄民宿套裝行程。我乍聽覺得真是異想天開，在這個每逢大雨就淹水的海邊鄉里，哪有什麼景點可看？海岸堤防外，隨著浪潮推擠的是漂浮垃圾、保麗龍碎粒和消波石粽，沒有一片可以活動的沙灘。堤防內是切割成一塊塊的養殖魚塭，只有細得像血管的小路延伸連接。靠近鄉公所的街上有當時唯一一家便利超商，各村落都只有一、兩條街能擺上菜販肉攤，間有賣羹麵、炸粿之類的攤商、小吃店。我那時想，難不成有人會專程來看「汪洋中的一條船」鄭豐喜的爬行路線？或者有人要看亞洲鐵人李福恩國中時候練標槍跳高跳遠的操場？還是要探訪秦漢當年拍電影飾演鄭豐喜任教的口湖國中教師辦公室場景？或者包幾架膠筏載客看每隔幾年就來一次的淹水，附贈全身防水撈海藻的工作服可下水體驗救災？反正我媽就是有信心做民宿能成，她照樣開店，慢慢看地，找朋友打牌聊天。
　
那年夏初口湖鄉做大水，我毀棄了一個女孩子的心，投向另一個即將飛往法國的女生。我媽找到一塊法拍魚塭地，打算填土蓋房子，規畫在這間大平房弄五間套房，內含寬敞的飯廳、客廳，完全以日後的民宿想像來設計。我年初向她要錢補習日文，年末又跟她借旅費到法國。隔年我沒等到對方回來，我的日文拖拖拉拉學到五段動詞就停滯，直到補習班會員資格過期。我總是這樣隨便浪費我媽辛苦賺來的錢。
　
在我困於感情、寫作和一無是處的課業期間，我媽生病，我媽跟我爸吵架，新房子施工走走停停，我媽開車到處拜訪親友。有一小段時間，我會到三重的老公寓看她。那是設有神壇的迷你宮廟，起乩的神要她吃蓬萊蕉還什麼神祕草藥治病，要她在神壇下打地舖睡覺養病。一年過去，我媽依然走跳各地，我申請到浙江大學交流三個月。我天天揹著筆電到分配的研究室看書、看電影，到校外吃五塊人民幣一盤的雞蛋炒飯，有時騎著龍頭歪一邊的腳踏車，奮力避開洶湧人車，繞西湖一圈。浙大認識的朋友常跟我聊侯孝賢、楊德昌、蔡明亮和馬英九。我跟媽媽通過幾次電話，她都說還不錯。
　
回到台灣，我得在年限最後半年寫出論文。我媽愈來愈頻繁進出醫院。那年的總統大選，我媽要我相信台灣選給民進黨，我陪她到投票所，心裡不以為然地投了廢票。當晚她靜靜睡著了。當年的美國職棒大聯盟開季，王建民投得極其神勇。我媽在清明假期後的一天清晨，永遠睡著，成了新房子第一個離開的人。那之後，王建民跑壘受了大傷。我總算趕上期限交出論文畢業，在夏天入伍。那個夏天來了六個颱風，據說幫《海角七號》創下票房紀錄。我在嘉義中坑新訓中心打掃營區好多次，穿了好多天又重又臭的軍用雨衣。結訓前抽籤，我志願到南沙太平島，但體檢沒過，沒成，回到雲林海邊服完兵役。大概是我媽不讓我去的緣故。

photo：吳怡欣。www.facebook.com/yihsinwuillustration/

📜 [專欄新文章] 瞭解神秘的 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.

👏 歡迎轉載分享鼓掌