前言
在本系列的第一篇文章中，我們介紹了 Bulletproofs 在 Range proof 上的應用，當 prove r想要證明v值在范圍 [0, 2n-1] 內時，他需要發送 2n+7 個元素，然而，這種 O(n) 級的 CC 并不是我們想要的，希望能尋找一種方法可以把 CC 降低到 O(log(n) 級，
所以，本篇我們就主要介紹這個優化過程，主要分為兩部分：
- 以簡單的場景去闡述這個優化過程
- 把第一篇的 Range proof 結果嵌入到優化過程
注：第一篇文章由于格式的原因，公式顯示會有誤差，向量的特殊標記也沒有顯示出來，因此本篇將以圖片的形式展示整個過程；另外，本文最后也附上了第一篇文章的圖，幫助大家理解 ^_^
Improved Range proof—- A simple example
1. 預備知識
2. 一個簡單的場景
3. 復雜度優化到 O(log(n))
下圖是一張基于上述過程的交互協議
有幾點需要說明：
- 圖的右半部分分為兩個部分
- a. 黃色部分為文章前面部分講述的過程。這又分為三個部分：
i.初始化：省略了 P 的計算和交互的過程，我們假定開始此證明協議前，驗證者已經有了一些基本的資訊，這并不嚴謹，僅僅是為了清晰的表示后面的交互過程
ii. LOOP ：一個不斷迭代的過程，每次迭代，會:
- 產生一對 (Li, Ri)，
- 所有向量長度減半
- Verifier 計算 P i /g i / h i`
iii. End：最后一步，向量 a, b 已減半成常量 a, b
b. 綠色部分為黃色部分的進一步優化，優化思想主要是多次冪乘操作縮減成單詞冪乘操作，具體的是：
i. 上述 LOOP 中的第3步，延遲到最后一部一次性計算
A real Rang proof
回顧第一篇文章，我們知道，當我們要證明 v 屬于 [ 0, 2n-1 ] 時，驗證者最終要驗證：
對關系式做個變換：
因此，prover 是要證明有向量 l，r 滿足關系：
基于此關系，使用上述協議，就可以使 range proof 的交互復雜度降低到對數級，現在，是不是找到點內味了？
總結
本篇文章主要講到了，BulletProof 是如何把 Range proof 的 CC 降低到 O (log(n))，并且介紹了更近一步的優化。結合第一篇文章，相信你已經對基于 Bulletproofs 的 Range proof 原理有了整體的了解，在本系列的第三篇文章中，將給大家分享 Range proof 的工程上實現細節。
