[沒有誰比誰高貴](六之五)
反修例運動此前多場審訊,不論是襲警、藏武器、暴動案,在法庭裡的檢視方法,採取視覺較微觀。示威者在這條街被捕,隔一條街發生的事,不會視為相關。時間上檢視也收得狹窄,例如7.21元朗襲擊,或831太子站事件,示威者受事件影響之後上街,法庭不會視為有參考價值(relevant).
然而國安法第一審,唐英傑開電單車涉衝向警察防線,車上插了「光復香港。時代革命」旗幟,案件搬到法庭,被提升到「恐怖活動」「煽動他人分裂國家」層次。
法庭對刑事案件審訊,多檢視可觸摸之物,如翻看閉路電視、檢視直播片段、化驗被告背包或手袋的物件。
但驗視一句話的意義,用甚麼方法,拉闊到歷史何年何月,翻查幾多本字典,還是要揭開人腦看看人的思想?
早幾天,辯方專家證人,港大學者李詠怡當被控方逼問舉殖民旗的人心裡想甚麼,梁天琦設計口號的心底意思。Eliza一度在庭上表示:「我沒法子有讀心術 (I am not a mindreader).」
如何去讀一場社會運動的集體心理?社會學家,明顯和法律專家有不同看法。
這天,彭寶琴法官問及Francis,他如何理解「反修例運動的時間線(timeline)」。作為專研社運的學者,Francis認為運動由2019年6月9日開始,延續至大約2020年中,但難說某一日正式結束。彭官反問:「逃犯條例不是撤回了嗎?在2019年9月條例撤回後,李教授你仍然覺得運動繼續下去?」Francis說是。
彭官亦問Francis,「你在問卷中問示威者,那一個口號有代表性,但每一個集會不是有主辦單位嗎?大會不是有他們的主題?」(亦即民間所謂的大台)
Francis回應道,每次遊行雖有個別主題,但整場大型反修例運動不只是個別遊行。「例如人們最初對『齊上齊落』口號感到有共鳴,因為此口號表達了整場運動裡,示威者感到的團結精神和聯繫感(togetherness)。很多時候,口號不是直接與政策訴求有關,而是表達示威者的情感和感受。」
這天,辯方專家證人,中大新傳學院教授李立峯Francis進入第二天作供。高個子的他,頭髮長及頸,穿了淺灰色西裝外套,外套布料質地有反光效果,西裝上的縐紋特別顯眼。他出現在證人枱時,拿着橙色的布袋,把厚厚的文件塞在布袋內,擱在證人枱。
Francis喜歡把手踭擱在枱上,竪起前臂,長長的手指揮舞着,談起他熱愛的社科方法論,語速越說越快,微微地左右搖動帶輪辦公室椅子。法官不只一次請他說慢一點。
有些時候,三位法官們發問的問題,比雙方大狀們更多。
Francis說,曾向全香港市民抽樣撥打電話作民意調查。為了要有隨機性,撥打住戶家居電話時,會向聽電話的人問,若家居住戶多於一人,那一位同住者的生日日期較接近,則邀請該人來回答民調。
唯一的男法官陳嘉信,手指之間常夾着筆,雙眉上下舞動,立即發問:「為何打電話去家居要這樣問,而手機則不用問?」
Francis解答道:「在外國,曾有研究發現,在家庭中負責接電話的人,永遠都是家庭主婦。」法官杜麗冰聽到後,臉上綻放出會心微笑,更向陳官互相交換笑容。Francis續說:「又或者是年輕人搶着電話聽,這樣,民調做出來就會有偏差。」
另一個社會學方法論的提問,也是由陳嘉信法官追問出來的。Francis團隊亦曾於廿多場遊行或集會活動中做現場調查。調查員會被分派在集會或遊行現場,邀請參加者填問卷。
但隨着運動變得更流水式,出現更多變數,甚至出現衝突。為了保護調查員安全,例如7.27元朗遊行,他們會派出少量資深調查員到現場,派發含有QR Code的單張,示威者可以事後上網填寫。
無論是代表控方的周天行檢控專員,抑或法官都問Francis,讓人拿單張回去跟QR Code填問卷,怎樣肯定填的人真是去過現場?
陳嘉信法官問:「你說,填問卷的人很熱心,你怎知他們會不會『熱心』過頭,上網虛構答案?」他雙手在空中比劃着括號,把「熱心」二字強調。
Francis說,他們巧妙地在網上問卷中加入了一條題目:「這天在那一個示威地點加入隊伍」,亦有一個選項是:「我今天沒有參加遊行」。填表者並不知道,研究員會剔走沒參加遊行的人的意見。
「他們填的時候,不知道這條題目若答了,其實篩走了自己,最終我們便可以只分析參加過示威的人的數據。」三法官聽罷,明白學者一早想到這些漏洞,點頭表示明白。
法庭裡,尋找「光時」意義之旅,控辯雙方均花心力指斥對方研究方法有漏洞。
代表律政司的署理刑事檢控專員周天行,嘗試從Francis的研究裡,找尋不足之處。Francis和團隊以5種研究方法:全港性電話民意調查、示威現場問卷調查、焦點小組、連登討論區大數據分析、公共討論分析(時評人在傳媒的言論),多管齊下來理解社會運動中口號的意義。
周專員指,調查大部分於2020年初之前進行,而本案發生的日子(2020年7月1日)之前一段時間,即2020年2月至7月,Francis沒有相關研究。周專員問:「沒有任何事阻止你進行更多研究吧。」
Francis指,當他自己知道要做專家證人時,已是2021年4月底,時光追不回了。「我不能坐時光機回到過去(I cannot travel back in time to do it.) 周專員堅持追問,可以做電話民調呀。此時陳嘉信法官插嘴表達其看法:「即係你叫李教授在2021年問番啲人9個月前在想甚麼?」
Francis望着陳官說:「你說的我認同,即使可以問,搜集回來的數據也不會可信。問人今日在想甚麼會較可信,你問人一年前想甚麼,可信性甚低。」
周專員轉以「以子之矛」嘗試再去進攻。「你曾說過口號的意義會隨時間改變,你在案發前一段相關時間,無研究喎。」Francis再解釋,除非遇到重大事件,口號的意思隨時間改變,基本上是以年計,或以十年計,「口號意義改變,並非分分秒秒在變動」。
Francis在庭上首次披露,他團隊進行的「連登討論區」大數據研究,份量之浩瀚,他和團隊從連登「時事台」從2019年6月到8月21日的討論帖子及回應留言,涉及2千5百萬個,電腦檔案足有38GB。
周專員從枱底拿出幾疊白紙,原來他的團隊從連登討論區,人手萃取了一些帖文,叫Francis即場示範如何做Coding (編碼)工作。
西裝骨骨的Francis翻閱着文件,開始說:「呢位網民【四葉妹妹】有提及過「光復香港。時代革命」沒提及「港獨」及「五大訴求」,可算為「1, 1, 0, 0」; 網民【英國男孩】完全沒提,電腦會記為「0, 0, 0, 0」;這位【草尼馬仔】貼了光時旗的照片,不含文字留言,我們技術上沒法認出。但不改變們這個整個研究方法的合理性」。在嚴肅法庭,聽到鬼馬的網名,旁聽者都忍不住笑了出來。
控辯雙方過招,誰的「方法和總結」算是合理,光時究竟意義何在,是否違犯國案法?
Francis今天較完整披露他的看法。他認為,控方專家劉智鵬教授,以歷史及語言學角度去看「光時」這口號的意思,作出一個聲稱,就是「『光復香港。時代革命』這口號,只有唯一一個解讀,並為所有人共知」,「但我認為劉教授沒有提供充足證據去證明這個聲稱」。
Francis解釋,劉教授報告中用了「necessarily」一字,即口號詮釋的唯一可能「必然」是這樣,這是Francis自己認為需要用多種社科方法驗證的假設。
口號究竟是由喊的人那端衍生意思,還是從接收者那邊決定意思?
陳法官指,他理解控方劉專家報告中指的是,「喊口號的人懷有分裂國家意圖和目的」。但Francis卻說,喊口號基本上是一個「傳播行為」,不只是一個人單方面「個人表達」那麼簡單。
一個口號喊出來,是由嗌的人承擔意義發送者責任,還是接收的人也有份貢獻意義?如此哲學性問題,在法庭的空氣裡交鋒。
Francis又像在講課一樣,「作為傳播學者,我認為,喊口號是一個溝通行為,不只是一種自我表達。我嗌一個口號,會考慮接收者如何理解。」
小個子的法官杜麗冰,左手手指戴了綠寶石戒指,她一邊說話一邊以手部語言輔助她的比喻:「好像我跟一百個人說,我喜歡西瓜,有人會覺得我愛吃紅色的生果,另一個人覺得我愛吃綠色皮的水果。我發送一個訊息,但別人接收不同。」
Francis補充:「不止這樣,說話的人會小心用字。例如有一句句子意義明確,另一句句子的意義含糊,如果我要表達自己,減少誤會,我會選較明確的那句。」陳官提出,智力不同的人也會用字不同。
Francis反駁:「不只,也看大家出身甚麼背景,像你們法庭背景的人理解『引導性問題』(leading question)和我們社科人便不同,不只是智力差異的問題。」聽到這句話,杜官和陳官都作深思狀。
控方曾挑戰,指若文字意義多樣,人們便沒辦法溝通。Francis在此反駁:「劉教授說,人們會跟社會慣例(convention)去用字,但問題是,社會有很多慣例。文字使用很複雜,也有修辭學(rhetoric)作為一種慣例。劉教授把語言意義解得太過死板(too rigid),語言意義多樣,修辭令人們變通調適,否則世界便沒有創意寫作了(creative writing)。」
控方周專員指出,劉教授也有其「證據」,就是警方跟據示威錄影片段,數算有多少次出現「光時口號」,而這口號與「顛覆元素」如港獨訴求、暴力行為同時出現。Francis反駁,這數據只在「點算上」可靠,但兩件事同時出現(co-appearance),並不等於有關。
Francis用一個生活化的例子,說明兩種同時出現的東西,無必然關係。「在大學,學生在班房可以自由入座,兩個大學生每次課堂都一起坐,可以解讀為他們是朋友;但在中學,課室座位是被編排的,兩個中學生常並排而坐,只能說他們是一起坐。」
然後,Francis就望着控辯雙方大狀的方向:「就像在這個法庭,李先生和周先生也一起坐,要考慮這是個法庭場景。」眾笑。
至於示威場景,有其特性,Francis解釋:「好像每年香港七一遊行,於同一個示威裡出現的團體,訴求可以不共容。如性小眾、勞工及外傭團體也會各自有訴求。」
即使大型示威有一些共同訴求,各人理解也有差異。Francis指,他有研究2014雨傘運動,其口號為「我要真普選」,「但落實到具體解釋,甚麼是『真』的普選?『真』字既開放又抽象,讓人各自己想象。」
文字容易於不同場景被誤解,Francis特別澄清了一個可能的誤會。焦點小組討論的指引中,研究員需要留意討論覆蓋不同範疇。其中一個範圍呈在法庭文件中,寫道:「社會運動意識形態和激進化(social movement ideology and movement radicalization」。
Francis特別澄清「激進」二字的在的學術意思:「激進化,在研究社運學術世界裡,意思是與社會常態的距離(deviation from social norm ),涉及更重大改變的意思,並沒有『好與壞』的評價。」
「好像反修例運動最初,有人要求『成立獨立調查委員會』,這訴求較溫和,因為過去香港也曾成立過,相比起來,『解散警隊』這口號則較激進」。陳官補充:「即是要求更徹底的社會改變。」
陳官亦引述文件中的資料,好奇地向Francis查問:「為何你認為『光復香港。時代革命』比『五大訴求』更激進呢?」Francis解釋:「修辭學上,『革命』比『訴求』所涉及的改變,幅度更大,這是明顯的。」
在香港的刑事審訊上,「不爭辯事實、客觀存在」是常用術語,去指控一個人做了一件事,作為刑事案的入罪條件。然而一支旗,一句口號,如何建基於事實,使用這種法律語言,又出現了奇特的交雜和火花:
周專員指出,警察報告中點算示威口號出現次數是「客觀、不爭辯的事實」。
Francis反駁道:「你們只是提供了口號在示威現場,曾出現過的這個事實。」
周進逼:「你們只是倚賴別人的意見。」
Francis:「我們紀錄了人們表達意見的這個事實。我們分析的文章、人們論述過這些意見,都是一種『社會現實』(social facts)」
周再問:「你是否同意,劉智鵬教授報告裡,他對光時口號的解釋,是對的(correct)?」
詮譯變成了對和錯,二元對立,二選一,社科學者抗議了。
Francis:「我們的總結是,口號是開放的,抽象的,不只一個解釋,每人有每人的論述。我不會評價一個時評家對口號的解釋,正如我不會評價焦點小組裡一個平凡人的解讀。(I wouldn’t judge)我不會說,這個人的解讀是正確,這只是他自己的說話 (I wouldn’t say if this guy is correct, it is his own articulation)。」
周不放棄:「你不會異議,若我說劉智鵬教授的解讀是對的。」
Francis斬釘截鐵回應:「我會異議,問題並不在對與錯」。
杜麗冰法官嘗試插話,問Francis:「你會否覺得劉教授可以作這樣的解釋,即使你不贊同其解讀?」
Francis說:「我個人不會對口號作這樣的詮釋。劉智鵬教授的詮譯,只是『其中一個詮釋』。其解讀的地位沒有特別高,也沒有特別低。相比起某一個時事評論員,或者我們焦點小組的某一個參與者。」
周天行在盤問到最後,拋出了這個問題:「我說,我方對口號的理解方法(approach)更可靠。」
Francis噗哧笑了,全場亦爆出陣陣笑聲:「哈哈,肯定不是。警察在『點算口號』上或許是可靠,但我挑戰警察報告中『對數據的理解』,當口號與顛覆元素共同於示威場合出現,根本不是支持口號有顛覆意義的證據。我對警察報告是完全不贊同。」
此時,周天行專員彎腰,跟坐在他旁的同事耳語了逾三十秒。
周專員回過頭,橫空拋出這句話:「我向你指出,你的報告不可靠,不相關。」
Francis咬字清晰,語氣肯定回應:「我的報告,既可靠,合乎標準,亦相關。」
誰的解讀更有權威?控方專家認為喊口號的人必然意圖顛覆;辯方則指出,口號是開放和曖昩的,任何人的解讀,都沒有比另一個人的解讀更有權威。
一支旗,八個字,意義之爭,連繫着多位國安法被告的命運。
國安第一被告唐英傑,身型壯碩,年輕的他坐在犯人欄,由幾個懲教署職員押送。
唐的學歷不算高,是一位日本餐廳的厨師,然而穿着深色西服的他,還押了一年後,出席他自己的審訊,連日聽學者解讀他舉過的一支旗,都堅持翻閱着厚厚的法律文件,專心地聽着耳機,坐在他旁邊隔了犯人欄的翻譯先生,即時以廣東話傳譯。
「Rhetoric….修辭學」英語對話,小聲的廣東話,在法庭後方響起了,兩條聲道有些重疊。
幾名穿墨綠色制服的懲教署職員, 和唐一起坐在寬闊的犯人欄內。懲教職員的身體,慢慢挪移越近唐的方向,他們偶爾也竪起耳朵,跟進學者們的辯論進程。連穿着保安制服的叔叔,都聽得懂英語,都留意到辯論擦出火花,露出驚訝的表情。
八個字,有罪還是無罪,全城關注。誰的解讀更高貴?
時鐘已到下午四時半,明天Francis繼續作供。
***
國安法首審專家證人系列(六之一):[Regime & Redeem]
7月2日控方專家劉智鵬作供
https://www.facebook.com/wwviviantam/photos/a.1435553239866430/4210137115741348/
國安法首審專家證人系列(六之二):[Just Do it]
7月9日辯方專家李詠怡作供
https://www.facebook.com/wwviviantam/photos/a.1435553239866430/4229321820489544/
國安法首審專家證人系列(六之三):[過去與未來]
7月12日辯方專家李詠怡作供
https://www.facebook.com/wwviviantam/photos/a.1435553239866430/4237523026336090/
國安法首審專家證人系列(六之四):[知行合一]
7月13日辯方專家李詠怡及李立峯作供
https://www.facebook.com/wwviviantam/photos/a.1435553239866430/4240215429400183/
國安法首審專家證人系列(六之五):[沒有誰比誰高貴]
7月14日辯方專家李立峯作供
https://www.facebook.com/wwviviantam/photos/a.1435553239866430/4243328702422189/
國安法首審專家證人系列(六之六):[選櫻桃的人]
7月15日辯方專家李立峯作供
https://www.facebook.com/wwviviantam/photos/a.1435553239866430/4245860505502342/
(圖為辯方專家證人中大新傳學院教授李立峯離開高等法院)
簡單隨機抽樣例子 在 李懂媽 Facebook 的最佳貼文
《 講真話 救香港 》
聶德權今早表示,全港已經有接近五份一人口接受自願檢測,找出19宗確診個案,因此推算全港約有90至100隱形患者。
首先重申立場,個人信奉獨立思考,每一個市民可以自己決定是否接受檢查,但看見政府鋪天蓋地宣傳仍然效果不彰,希望在這裏進言幾句。
眾所周知,第三波嚴峻疫情的起因,就是政府決定讓帶病毒的海員免檢進入社區,但政府至今仍沒有向市民道歉一句,市民心中不忿,理所當然。
若果政府能講真話,開誠布公向市民認錯:「由於政府決策出錯,令香港飽受第三波疫症煎熬,政府願意為此真誠道歉,希望市民給政府一個機會將功補過,配合全民檢測找出社區中隱形患者。」
我絕對相信政府如果能夠打開心扉,必定可以大大提升接受檢測人數,無需狂谷廣告。
至於聶德權推算的數字,根本完全unscientific。
以五分一人口的檢測率去乘大五倍,只適用於隨機抽樣(random sampling),但普及檢測只屬於自願性質(即 non-random sampling),統計學上並不能從這數字上推斷總體。
舉一個簡單例子:
小學校長向全校100名小學生宣佈:「由於你哋好鍾意食糖,開始蛀牙都未必察覺,今日學校搵咗牙醫嚟幫你做免費檢查,邊個自願接受檢查嘅,下晝可以去操場排隊。」
結果只有50名學生接受牙醫檢查,找出20個有蛀牙。
但不能因此得出全校100名學生有40人蛀牙的結論。
原因很簡單,理論上甚少吃糖、又早晚刷牙的學生,會傾向不去操場排隊,相反經常吃糖又不刷牙的高危學生會較踴躍去排隊。
最後,仍然衷心奉勸各位高官,只要講真話,市民一定會明白。
李懂媽
簡單隨機抽樣例子 在 Taipei Ethereum Meetup Facebook 的最佳解答
📜 [專欄新文章] 瞭解神秘的 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.
👏 歡迎轉載分享鼓掌
簡單隨機抽樣例子 在 簡單隨機抽樣例子在PTT/Dcard完整相關資訊 - 數位感 的必吃
(一)簡單隨機抽樣(simple random sampling; ... | [PDF] 二階段分層叢集抽樣的設計效應、估計: - 國立臺灣師範大學edu.tw )由抽樣各學校中隨機抽出l 至2 個班級作為 ... ... <看更多>
簡單隨機抽樣例子 在 簡單隨機抽樣例子在PTT/Dcard完整相關資訊 - 數位感 的必吃
(一)簡單隨機抽樣(simple random sampling; ... | [PDF] 二階段分層叢集抽樣的設計效應、估計: - 國立臺灣師範大學edu.tw )由抽樣各學校中隨機抽出l 至2 個班級作為 ... ... <看更多>