Introduction to Technology | Understanding Bulletproofs of Zero-Knowledge Proof Algorithms: Range Proof II

Foreword

In the first article of this series, we introduced the application of Bulletproofs to Range proof. When the prover wants to prove that the value of v is in the range [0, 2 ⁿ -1], he needs to send 2n + 7 elements. However, this type of O (n) CC is not what we want. I hope to find a way to reduce CC to O (log (n) level. In this article, we mainly introduce this optimization process. It is mainly divided into Two parts:

1. Explain this optimization process with a simple scenario

2. Embed the results of the first Range proof into the optimization process

Note: Due to formatting reasons, the formula of the first article is incorrect, and the special marks of the vectors are not displayed. Therefore, this article will show the entire process in the form of pictures; in addition, the first article is also attached at the end of this article Figure to help everyone understand ^ _ ^

• Technical Guide | Building IPFS Applications with Node.Js
• Smart Contract Series 1: The Cornerstone of the Digital Society-Smart Contracts
• Technical Guide | Understanding Zk-stark for Zero Knowledge Proof Algorithms

Improved Range proof

A simple example

Preliminary knowledge

2. A simple scenario

3.Complexity optimized to O (log (n))

The following figure is an interactive protocol based on the above process

There are a few things to note:

1. The right half of the figure is divided into two parts

a. The yellow part is the process described earlier in the article. This is divided into three parts:

i. Initialization: The calculation and interaction of P is omitted. We assume that the verifier already has some basic information before starting this proof protocol. This is not rigorous, just to clearly show the subsequent interaction process

ii. LOOP: a process of continuous iteration, each iteration, will:

1). Generate a pair (L _i , R _i ),

2). Halve all vector lengths

3). Verifier calculates P _i `/ g i` / h _i `

iii. End: In the last step, the vectors a, b have been halved to a constant a, b

b. The green part is the further optimization of the yellow part. The optimization idea is mainly to reduce the multiple power multiplication operation to the word power multiplication operation, specifically:

i. The third step in the above LOOP is postponed to the last one-time calculation,

A real Rang proof

Looking back at the first article, we know that when we want to prove that v belongs to [0, 2n-1], the verifier finally verifies:

P =? H ^μ * g ^l * (h`) ^r

t =? <l, r>

Transform the relation:

P * h ^-μ =? * g ^l * (h`) ^r

t =? <l, r>

Therefore, prover is to prove that there are vectors l, r satisfying the relationship:

Relation: ((g, h ⸦ G ⁿ , P * h ^{– μ}   ⸦ G, t ⸦Z _p ): P = g ^l h ^r ^ t = <a, b>)

Based on this relationship, using the above protocol, the interaction complexity of range proof can be reduced to the logarithmic level. Now, did you find something inside? ^ _ ^

                        

to sum up

This article mainly talked about how BulletProof reduced the CC of Range proof to O (log (n)), and introduced a further optimization. Combined with the first article, I believe you have a general understanding of the principle of Range proof based on Bulletproofs. In the third article of this series, I will share the implementation details of the Range proof project.

appendix

1.Bulletproofs thesis: chrome-extension: //cdonnmffkdaoajfknoeeecmchibpmkmg/assets/pdf/web/viewer.html? File = https% 3A% 2F% 2Feprint.iacr.org% 2F2017% 2F1066.pdf

2.     Attach a picture for everyone to understand the first article ( https://www.8btc.com/media/530155 )

We will continue to update Blocking; if you have any questions or suggestions, please contact us!