作者：RareSkills
“Pedersen 承諾” 讓我們可以使用一個橢圓曲線點來表示任意大的向量，同時可以選擇隱藏關於這個向量的任何信息。它給了我們一個重要的元件，讓我們可以證明用這個點來編碼的向量，又不必暴露這個向量本身。
動機
在討論 Bulletproot 零知識證明技術的時候，人們常常這樣說：“我們有兩個向量，它們的內積（inner product）是 c。” 似乎這很普通，但實際上，你可以用這個機制來證明非常複雜的陳述（claim）。我們後面展開說。
但為了讓這樣的證明系統可以工作，這些向量就不能只有證明者知道 —— 不然證明者就可以隨意改變它們。它們必須是真實世界中的數學實體。一般來說，證明者肯定不想直接把這兩個向量交給驗證者，但依然需要 “傳遞一些東西” 給驗證者，表示自己已經選定了一對向量，不能再改變了。
這就是我們需要 Pedersen 承諾的地方。
前置知識
我們假設讀者已經熟悉了橢圓曲線點加法和點乘法，以及 “曲線上的一個點” 意味著什麼。如果你還不瞭解，請參考我們的《零知識證明之書》的前面四章。
至於記號，我們用 [A] 來表示一個橢圓曲線（EC）點，用 a 表示一個有限域內的元素，而 a[A] 表示這個有限域元素 a 與橢圓曲線點 [A] 的點乘法。而表達式 [A] + [B] 表示這兩個點的點加法。
傳統的承諾方案
在設計智能合約中的承諾揭曉函數時，我們通常使用這樣的形式：
commit = hash(value, salt)其中的 “salt（鹽）” 是一個隨機數值，用來阻止攻擊者的暴力搜索猜測。比如說，如果我們是在承諾投出的一票，由於票的可選項是有限的，那麼我們的票到底投給了誰，就可以通過嘗試所有的選項、檢查哈希值匹配來發現。（而加了鹽，這樣的暴力搜索就行不通了。）
鹽在這種場景中的用法，有一個學術名詞，叫做 “盲化（blinding）因子”。因為它是隨機的，攻擊者就彷彿失明瞭，猜不出被承諾的數值（上面式子中的 “value”）到底是什麼。
因為攻擊者無法通過 “諾言” 猜測出其背後的數值，我們就說這種承諾方案有藏匿效果。
而揭曉數值的階段，承諾者揭曉數值和鹽（在文獻中，它們叫做 “契機（opening）”），另一方（或者智能合約）可以驗證它們跟原本的承諾相匹配。如果在同一承諾方案中不可能用另一對 (value, salt) 來獲得相同的諾言，我們就說這種方案有綁定效果 —— 承諾者一旦揭曉諾言，就不可能再改變被承諾的數值（也即兩者就綁定了）。
術語總結
- 有藏匿效果的承諾方案不允許敵手知曉承諾者選擇的數值。這通常是通過加入一個攻擊者無法猜測的隨機數來實現的。
- 盲化因子則是讓被承諾的數值無法通過暴力搜索得出的隨機數。在一些我們並不在乎零知識性（而只在乎簡潔性）的場景中，可能不使用盲化因子。
- 契機則是計算出諾言的數值（被承諾的數值和鹽）。
- 有綁定效果的承諾方案不允許承諾者使用不相同的契機計算出相同的諾言。也就是說，他們不應能夠找出兩對
(value, salt)，計算得出相同的諾言（在這裡是哈希值）。
Pedersen 承諾
Pedersen 承諾方案的模式沒有什麼不同，只不過，它用的是橢圓曲線群，而不是密碼學哈希函數。
在 “橢圓曲線上離散對數難解” 假設下，給定橢圓曲線點 [U] 和 [G]，我們無法計算出能讓 [U] = u[G] 的 u 。
用 Python 語言的代碼來說，就是：
from py_ecc.bn128 import G1, multiplyu = 569723450 # chosen randomlyU = multiply(G1, u)print(U, "cannot compute the discrete log of U")我們說，u 是 [U] 的離散對數。即使我們並不能計算出 u，也依然管它叫 [U] 的離散對數，因為我們知道它存在。所有的（密碼學）橢圓曲線點都有一個離散對數，即使我們無法計算出它。
在這個意義上，橢圓曲線點乘法就像一種哈希函數。它們是有綁定效果的，只要我們只允許在曲線階數內的契機。
不過，雖然它有綁定效果，我們無法通過點反轉出其離散對數，如果 u 的取值範圍很小，我們就會遇到（跟上述投票案例）完全一樣的問題。敵手可以通過遍歷所有可能的 x、計算 x[G] 來猜測我們的 x 。
我們可以用下列方式實現 “Pedersen 式隱匿”：
commitment = v[G] + s[Q]這裡的 v 就是我們要承諾的數值，而 s 是鹽（盲化因子）；Q 是另一個橢圓曲線點，承諾者不知道其離散對數。
我們要強調的是，雖然它們的離散對數都是未知的，[G] 和 [Q] 都是公開的，驗證者和承諾者都知曉。
為什麼不能讓承諾者知道 [Q] 的離散對數
假設承諾者知道 [Q] 背後的離散對數 [Q] = d[G] 。這會讓承諾者可以找出兩個擁有相同諾言的契機。原理如下。
[C] = v[G] + s[Q] = 10[G] + 15[Q] = 10[G] + 15[dG] [C′] = 11[G] + (15d−1)[G] [C] = [C′]讀者可以手動為 d 代入任意數字，看看它是怎麼工作的。
承諾者不能知道他們所用的橢圓曲線點的離散對數關係。
保證這一點的一個辦法是，讓驗證者來為承諾者提供這個橢圓曲線點。不過，更簡單的辦法是，以隨機且透明的辦法選出一個橢圓曲線點，例如，偽隨機地選出橢圓曲線點。給定一個隨機的橢圓曲線點，我們就不知道其離散對數。
舉個例子，我們可以從生成元（[G]）開始，哈希其 x 座標值和 y 座標值，然後喂入一個偽隨機但確定的函數，用來尋找下一個點。
Pedersen 承諾有用在哪？
看起來 Pedersen 承諾只是使用另一種哈希函數的常規承諾方案，它有用在哪兒？
這個方案有許多好處。
同態可加
給定一個生成元 [G]，我們可以將兩個承諾加在一起：a[G] + b[G] = (a + b)[G] 。即使我們再加入隨機盲化隱私，我們依然可以製作出有效的契機：
$$
C_1 = a[G] + s_1[Q] \
C_2 = b[G] + s_2[Q] \
C_3 = C_1 + C_2 \
承諾揭曉 \
(a, b, s_1 + s_2) \
驗證者檢查 \
C_3 ?= a[G] + b[G] + (s_1 + s_2)[Q]
$$
常規的密碼學哈希函數（比如 SHA256）是做不到這樣的。
（在 Pedersen 承諾中）b[G] 和 s[Q] 在相加時不會彼此 “衝突”。
你看下面這個等式成立嗎？
(a[G]+b[H]) + (c[G]+d[H]) = (a+c)[G] + (c+d)[H]（這裡的 [G] 和 [H] 都是未知離散對數的兩個橢圓曲線點）。
你可以把橢圓曲線點理解成正交維度（orthogonal dimensions）上的一種線性組合（linear combination）的基（basis）。
當存在有限域元素 $a_1, a_2, b_1, b_2$，以及橢圓曲線點 [G] 和 [H]，且 [G] 不等於 [H] 、$a_1 \ne a_2$、$b_1 \ne b_2$，即使 $a_1[G] + b_1[H] = a_2[G] + b_2[H]$，依然不可能繞過離散對數難題而解出 $(a_1, a_2, b_1, b_2)$ 。
而且，當我們的橢圓曲線群的階數足夠大的時候，靠運氣找出這樣的匹配，更是渺茫。
換句話說，假設兩個人計算各自的承諾 [C] = a[G] + b[H] 和 [C'] = a'[G] + b'[H]，且 $a \ne a’$ 且 $b \ne b’$。只要 [G] 和 [H] 的離散對數未知，[C] 就不太可能等於 [C'] 。
Pedersen 承諾是 zk 友好的
為橢圓曲線上的加法和乘法制作電路相對容易，因為唯一要求是常規的算術運算；但常規的哈希函數卻要用到比特位移（bitshifting）和異或運算（XOR），需要棟樑的約束才能編碼成零知識證明的電路。
我們可以將任意多的點編碼成一個點
我們使用 [G] 和 [Q] 的例子也可以認為是一個不設盲化因子的 2 維的向量承諾。但我們也可以加入任意多的橢圓曲線點 $[G_1, G_2,…, G_n]$，承諾任意多個標量。
Pedersen 向量承諾
我們把上述方案再推進一步，從而承諾一組數值，而不是一個數值和一個盲化銀子。
向量承諾方案
假設我們有一組隨機的橢圓曲線點（$[G_1, G_2,…, G_n]$）（它們的離散對數我們全都不知道，那麼我們可以這樣做：
$$\underbrace{[C] = v_1[G_1] + v_2[G_2] + … + v_n[G_n]}{被承諾的數值} + \underbrace{r[Q]}{盲化因子}$$
這讓我們可以用一個諾言 [C] 承諾許多個數值，並用 r 來藏匿。
因為承諾者並不知道任何一個生成元背後的離散對數，所以他們將無法知道 [C] 的離散對數。因此，這個方案有綁定效果：他們只能用 $[v_1, v_2,…, v_n]$ 來產生諾言 [C]，無法用另一組向量做到。
向量承諾可以聚合
我麼可以把兩個 Pedersen 向量承諾相加，得到一個對兩個向量的諾言。承諾者依然可以用原本的向量來揭曉。這裡有一個重要的實現細節，就是原本的兩個向量承諾必須使用兩組不同的橢圓曲線點來生成。
$$
[C_1] = v_1[G_1] + v_2[G_2] + … + v_n[G_n] + r[Q] \
[C_2] = w_1[H_1] + w_2[H_2] + … + w_n[H_n] + s[Q] \
[C_3] = [C_1] + [C_2]
$$
這裡，r[Q] 和 s[Q] 是盲化因子。即時承諾者沒有承諾向量，整個諾言看起來依然像是一個隨機的點。
承諾者後面可以揭曉原本的向量 $[v_1, v_2,…, v_n]$ 和 $[w_1, w_2,…, w_n]$，以及盲化因子 r + s。這也是有綁定效果的，無法用另一組向量和盲化因子產生相同的諾言。
我們給一組向量使用 $[G_1, G_2,…, G_n]$、給另一組使用 $[H_1, H_2,…, H_n]$ 不暗示著這些 [G_i] 生成元和 [H_i] 生成元內部有什麼特殊關係。所有這些點都需要偽隨機地選出來。它們僅僅只是記號上的重合，便於我們直接說 “這些橢圓曲線點向量與這組有限域元素向量搭配，那些橢圓曲線點向量與那些有限域元素向量搭配”。
我們可以承諾的向量的數量是沒有內在上限的。
考考讀者：如果我們給兩個承諾使用相同的生成元 $[G_1, G_2,…, G_n]$，然後再相加，承諾者如何為 $[C_3]$ 揭曉兩組不同的向量？舉個例子，使用另一組橢圓曲線點 $[H_1, H_2,…, H_n]$ 是不是可以避免這一點？
考考讀者：如果承諾者在揭曉時調換被承諾的值的位置，會發生什麼事？
舉個例子，他承諾的是：
$$[C_1] = v_1[G_1] + v_2[G_2] + … + v_n[G_n] + r[Q]$$
然而公開的契機是：
$$[v_2, v_1, v_3, v4,…，v_n]$$
也就是說，承諾者調換了前面兩個元素的位置，但其它東西一切不變。假設向量 $[G_1, G_2,…, G_n]$ 是不可調換的。
透明地生成隨機點
我們如何能生成這些隨機的橢圓曲線點？一種顯然的解決方案是使用一個受信任的啟動設置，但這並不是必要的。承諾者可以通過透明地隨機選出一些我們不知道其離散對數的點。
他們可以先選擇生成元 [G]，混合一個公開選出的隨機數，然後哈希這個結果（需要對 field_modulus 取模），從而獲得另一個數值。如果這個結果作為 x 值能夠落在橢圓曲線上，那麼就使用它作為下一個生成元，再次哈希它的 (x, y) 座標值。相反，如果它作為 x 值，在橢圓曲線上沒有對應點，那我們就遞增 x 值，直到它有對應的橢圓曲線點。因為並不是由承諾者來生成這些點的，他們也不可能知道這些點的離散對數。這種算法的實現細節交給讀者當作練習。
在任何情況下，都不應該通過乘法來生成一個點，因為這將導致我們知道其離散對數。你需要通過一個哈希函數來偽隨機地得出一個 x 值，然後看看它是否落在橢圓曲線上。
從生成元 [G] 開始也是可以的（眾所周知，其離散對數是 1），然後生成其它點。
留給讀者的練習：假設我們用點 [G1] 和 [G2] 承諾了一個 2 維向量。[G1] 的離散對數已知，但 [G2] 的離散對數未知。（我們暫時忽略盲化因子）。承諾者能夠使用另一個 2 維向量來揭曉這個承諾嗎？為什麼呢？
（完）
