多項式承諾的選擇

一個承諾方案，其實需要一個證明者演算法及一個驗證者演算法。

1. 證明者演算法:
   允許將訊息以隨機值的形式提交。而輸出的承諾字串可以是非常短 (只有32位元組)，證明者所取得到的輸入有2個，分別是訊息和隨機值。

2. 驗證者演算法:
   它透過取得輸入訊息、證明字串和隨機數來實行演算法。

在目前的市場上，大部分的承諾方案都會利用到雜湊函數，最簡單的承諾方案會對多項式的係數使用雜湊函數，從而產出一個證明用用於驗證上。換言之，這表示證明者需要發送包含多項式所有係數的承諾證明。不過，在真實應用中，多項式的長度可能會非常長，所以只是單單通過以上形式產出證明是明顯在效率上會有所影響。由於SNARK的出現，要求需要一個更有效率的方式來產出謐明。因此就出現了多項式承諾方案。

多項式承諾方案其實是一種密碼協議，可以透過多項式 IOP 轉換為一個簡潔參數。
同時，多項式承諾方案能讓證明者模擬多項式 IOP，從而避免向驗證者發送大量的多項式的證明。
在多項式承諾方案，證明者只需向驗證者發送一個多項式的承諾。而多項式承諾方案能夠支持驗證者自己選擇一個隨機點，然後要求證明者評估該點的多項式。正因為驗證者可以選擇隨機點數再讓證明者進行多項式的評估，所以當在一個有足夠的正確評估證明，驗證者就會相信證明者提交的證明是真確的。

透過使用多項式承諾方案，驗證者不再需要取得完整的多項式的證明，反面讓驗證者使用:

• 能夠接收以多項式形式發送的單一雜湊值。
• 能夠接收所自己向證明者提出請求的多項式評估以及對相關的多項式證明進行驗證。

由於多項式承諾方案可以讓證明者提交一個簡單的多項式 IOP，所以證明者不需要將整個多項式發送給驗證者，只需對多項式計算及產出一個證明就可以。多項式承諾方案也可以把電路正確性的要求進一步場地簡化為多項式的評估。
其實可以在驗證者角度去理解，驗證者的作用就是對證明進行驗證，只要證明愈簡單，驗證的時間也會愈少，從而提升到驗證的效率。

所以驗證者只需要評估點並查詢相關的評估。當進行評估的查詢時，驗證者可以將多項式承諾(證明)視為一個「預言機」。
驗證者需要「預言機」形式來進行評估查詢。而向驗證者提供預言機的方法就是將預言機實例化，成為一個多項式承諾方案。
然而預言機只是一個概念，要進行真正運用，就需要透過多項式的評估來實現。

當涉及到多項式時，我們可能需要考慮四個重要的函數族:

1. 多項式承諾 (次數最多為 d 的單個變數多項式)
2. 多線性承諾 (最多 k 個變數的多線性多項式，而每個變數的次數為 1)
3. 向量承諾 (對一個向量產出一個證明)，例子: Merkle Threes 是一種實現向量承諾方案的方法。
4. 內部乘積承諾: 對一個向量產出一個證明，然後證明所承諾的向量和驗證者選擇的向量的內的乘積是滿足某些要求。

不同的 SNARKS 系統會使用到不同的承諾方案。一般而言，各種承諾方案是相等的，能夠做到相等的值。所以各種承諾方案可以相互構建。在應用中，線性承諾方案會比多線性承諾方案更普遍，而多線性承諾方案比多項式承諾方案更普遍。由於各方案是相等，所以也可以從常見的線性承諾方案轉換成多項式承諾方案。

多項式承諾方案可以分成以下類型:

1. 基於配對+可信設定 (不透明或後量子):
   例如: KZG，在這種情況下，會有一個常數的評估證明，這是因為相關元素中只有常數數字(取自配對友好的密碼組)。這些類型的承諾也是同態的，也可以實現高效的批量提交及進行分期證明。由於同態的屬性，可以在不知道兩個多項式的情況下進行提交的動作。基於同樣的屬性，可以獲得兩個不同的多項式相加的承諾，而這些承諾會使用到雙線性群組。
2. 基於橢圓曲線，其中的離散對數是困難的 (透明的，但不是後量子):
   例如: IPA、Bulletproofs等等，這些類型的承諾也是同態的，也可以實現高效的批量提交及進行分期證明。它可以協助證明者在需要證明不同的證人的情況下，不需付出更大的成本來實現相關動作。這與 Schnorr 簽名的工作原理相似。
3. 基於 IOP + 哈希:
   例如: FRI、Ligero、Orion等等。這類證明一般是更大型，由於它們不是同態的 (不可進行批量提交)。例如: FRI 可以用作 STARK 系統中的區塊或用於構造一個多項式承諾方案。
4. 不知道次序的群，例如:DARK20。不需要可信任設定。而這種多項式承諾方案通常不會被大量使用，因為在一些場景中不可行，仍存在問題。