ZKEVM 的 Word Encoding 教學

在以太坊虛擬機(EVM)中，每個字(word)是256位元的。在zkevm中，由於兩個限制，我們需要將這個字分成8位元的塊。在本教學中，我們將探討zkevm的word encoding的重要性和工作原理。

為什麼要有 Word Encoding？

1. 尺寸限制：BN254曲線可以表示的最大數字是254位元。所有算術運算都是以一個254位元的質數作為模數。
2. 運算限制：透過 plookups，我們執行條件檢查和位元運算，需要在較小的塊上操作。Plonk prover 使用 FFT 來高效進行多項式除法，而 BN254 曲線允許最大 2^28 的FFT。所以多項式的需限制在 2^25。

編碼方式: Little Endian

以 256 位元值 1 為例：

word256 = 1

這個 word256 可以被分解為 32 個 8 位元的字。

word8s = [
    1, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0,
]

Commitment

256位元字以其8位元字的隨機線性組合來表示。commitment檢查應保證8位元範圍內的32個塊。

加法運算檢查

檢查a256 + b256 = c256的有效性。支援溢位以匹配EVM的行為。

範例：

a8s    ff 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0
b8s     2 1 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0
carry     1 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 0
sum8s   1 2 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0

比較器

檢查 a256 > b256、a256 < b256、a256 == b256 的關係。

我們將 8 位元的塊組合成 16 位元的塊以優化表格。結果將更高的塊的比較結論傳播到下方的所有塊。

範例：

a       1 0 0 0 | 0 0 0 0 | 0 0 0 0 | 0 1 0 0 |
b       1 0 0 0 | 0 0 0 0 | 0 0 0 0 | 0 0 0 0 |
result  1 1 1 1 | 1 1 1 1 | 1 1 1 1 | 1 1 0 0 |

結語

在zkevm中，word encoding 不僅能夠將每個 256 位元的字分割成更小的塊進行處理，更能夠透過一系列的運算與檢查保證其準確性與安全性。在智能合約的運算中，這種編碼方式能夠確保資料

參考資料

https://github.com/privacy-scaling-explorations/zkevm-specs/blob/master/specs/word-encoding.md