Schnorr 的批量驗證
在最近關於 Schnorr 標準化的 BIP 中，Pieter Wuille 提出了一種批量驗證算法。在我的理解中，最繁重的操作是乘以一個標量：為了使批量驗證安全，我們需要將每個公共 nonce 乘以一個隨機因子，因此我們回到每個簽名的兩個乘法（加一個）。我不明白為什麼在 BIP 開頭的圖中會出現加速。有人可以幫忙嗎？
提前感謝您的回答！
沒錯，橢圓曲線乘法確實是驗證算法中最昂貴的操作。由於單個簽名驗證和批量驗證都需要每個簽名進行兩次 EC 乘法，因此批處理似乎無法獲得加速。
然而，已知有幾種算法用於計算多個 EC 乘法之和的速度比對單個乘法求和的速度更快。Straus 算法（也稱為 Shamir 技巧）、Bos-Coster 算法和 Pippenger 算法都提供加速，並且適用於不同的場景。在我們的 BIP 草案的圖表中，使用了 Straus 和 Pippenger（取決於批次的大小；Pippenger 僅在超過 100 個鍵的批次中獲勝）。對於足夠大的批次，Bos-Coster 和 Pippenger比單個乘法快*O(log n)*倍。
為了讓您直覺地了解這是如何實現的，這裡是對 Bos-Coster 算法的總結（雖然在實踐中它不是最快的，但它是最容易解釋的）：
從*(a 1 , P 1 ), (a 2 , P 2 ), …, (a n , P n )*對的列表開始。
將此列表從大到小a i排序（並對其重新編號，以使1現在是最大的數字，…）。
雖然列表的長度大於 1：
- 將前兩個元素*(a 1 , P 1 )和(a 2 , P 2 )替換為兩個元素(a 1 - a 2 , P 1 )* , (a 2 , P 1 + P 2 )。請注意，a 1 P 1 + a 2 P 2 = (a 1 - a 2 )P 1 + a 2 (P 1 + P 2 )。
- 如果這導致一個元素的係數為 0，則將其刪除（當a 1 = a 2時會發生這種情況）。
- 再次對列表進行排序。
當只剩下一個元素時，它將採用*(a, P)形式，其中a是所有輸入的GCD。對於足夠大的n*，該 GCD 幾乎可以肯定是1，在這種情況下，解決方案就是P。否則a將是一個小數字，解決方案只是aP。
這裡的直覺是，當你說要執行 100 次乘法運算時，a 1 - a 2平均會比它替換的數字（a 1）小 100 倍，所以在每一步中，我們都將其中一個係數除以 100 ，而只進行一次 EC 加法。這與簡單的 EC 乘法相反，在這種乘法中，您通常需要對輸入中的每一位執行一次加法。