查表論證

查表論證是一種證明「這個值出現在這張表中」的方法，而無須為每一種可能性都寫出一條約束。某些運算用純粹的加法與乘法閘來表達極其痛苦——檢查一個數能否塞進 8 位元、計算位元級 XOR，或把一個 EVM 操作碼對應到它的行為。你不去把邏輯算術化，而是預先算好一張包含所有有效列的表，然後只需證明你電路所用的每一個值都是其中的某一列。對於有限、可枚舉的關係，這比逐閘約束便宜得驚人。

經典的構造是 plookup（Gabizon 與 Williamson，2020），它藉由檢查一個隨機化的大乘積（排列式）多項式恆等式，來證明「一個被查詢值的多重集合，被包含於某張表中」——這正是 PLONK 早已用於其複製約束的同一套機制。後來的改良如 logUp 把「包含」重新表述為一串對數導數分式之和，而像 cq 這類方案，則讓證明者的成本基本上與表的大小無關，於是連一張巨大的表（每一對位元組，或一整套操作碼）也變得負擔得起。它們全都把「x 在表 T 中嗎？」歸約成一個驗證者能廉價確認的多項式檢查。

查表如今對實務證明而言不可或缺，尤以 zkEVM 為甚。範圍檢查、位元組分解、Keccak 與 SHA 的輪函數，以及操作碼語意，全都交由查表處理，而非讓乘法閘數量爆炸。這正是現代算術化被描述為「PLONK 式搭配查表」的原因——閘系統加上查表，兩者合力，讓「證明真實機器中那些雜亂、玩弄位元的部分」變得可行。