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 n -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 ^ _ ^

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 n , 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!

Share:

Was this article helpful?

93 out of 132 found this helpful

Discover more

Bitcoin

Arizona Senate Proposes Including Bitcoin ETFs in State Retirement System

Arizona's retirement systems, ASRS and PSPRS, are proactively seeking to enhance their portfolios by including Bitcoi...

Bitcoin

BlackRock’s Mind-Boggling ETF Change Opens Door for Wall Street Banks

Proposed spot bitcoin ETFs may soon allow authorized participants (APs) to create new shares in the fund using cash i...

Bitcoin

Vanguard Blocks Access to Spot Bitcoin ETFs: A Surprising Stance

As many institutions embrace Spot Bitcoin ETFs, Vanguard takes a more selective approach to customer access.

Finance

BlackRock's Bitcoin ETF Trading Giants Jane Street, Jump, and Virtu Might Back It Up! Insider Report

With recent crackdowns on crypto, a potential BTC ETF approval could offer U.S. fashion firms a new way to participat...

Opinion

Crypto in 2024: Building Trust and Embracing Growth

In light of the recent backlash towards the digital asset industry, Beth and Clay Haddock strongly believe that the p...