Mathematics in blockchain -- accumulator

blocksight 2021-04-13 19:59:51 阅读数:595

mathematics blockchain accumulator

Write it at the front

In the last introduction merkle Commitment principle , Recent papers have focused on the promise of cryptography , Let's make a summary . There is a good metaphor , Commitment is like putting a letter in a safe, locking it and sending it to the receiver , Because the safe is on the receiving side , The sender has been unable to modify the contents of the letter , Meanwhile, the key to the safe is in the sender's hand , The content of the letter will not be seen by the receiver , Play a hidden role ！

This paper introduces a technology closely related to cryptography commitment --- Accumulator( accumulator ), In the past two years, it has been mentioned more in the area of blockchain stateless ！

Accumulator( accumulator )

In cryptography , The accumulator is a one-way member hash function . It allows users to prove that potential elements are members of a collection , Without revealing the individual members of the collection . This concept is applicable to 1993 Year by year J.Benaloh and M.de Mare Formally put forward , According to this definition ,Merkle tree It can also be regarded as simple Accumulator A kind of . Later, the meaning of accumulator has been extended , If you are interested, please refer to ！

There are two types of accumulators: dynamic and static ：

Dynamic accumulator ： When elements are added or removed , Commitment and corresponding proof can be effectively updated , It means that the cost of updating should be independent of the number of accumulated elements Static accumulators ： When elements are added or removed , Commitment and corresponding member certification need to be regenerated in general , And can't update effectively .

General purpose accumulators are dynamic accumulators , At the same time, it supports two parts: member proof and non member proof . We use the usual RSA The accumulator is illustrated as an example .

RSA accumulator

Why is it called RSA The accumulator ？ Because the implementation process and RSA Algorithm Close , The same is true of security assumptions .

Accumulator establish ：

1. setup: Choose a prime number g As a base , Then secretly choose two large prime numbers and multiply them to get N = p * q
2. Add elements ： Set add elements a, Calculation \$root =g^a\ mod\ N\$
3. Remove elements ： Set add elements a, Calculation \$root = root /g^a\ mod\ N\$

Illustrate with examples ： There's only one element a When ,\$root =g^a\ mod\ N\$ Add new elements again \$a_2,a_3\$ when , to update \$root =root^{a_2a_3}\ mod\ N=g^{a_2a_3*a}\ mod\ N\$

Accumulator Member Certification :

Suppose you want to prove \$a_2\$ It's really in this Accumulator In , We need to provide proof ：\$w = root /a_2 =g^{a*a_3}\ mod\ N\$

It's very simple to get rid of \$a_2\$ part

Accumulator verification : The verifier gets root, w And the elements to verify \$a_2\$, Calculation \$root' =w^{a_2}\ mod\ N =?= root\$

If it's equal, prove \$a_2\$ It's really in the accumulator .

You can see , Whether or not the current Accumulator How many elements have been stored , Can be passed through in only know Accumulator At present root When it's worth it , With O(1) Add new elements to the complexity of the meta . So it belongs to dynamic accumulator .

Aggregation proves （Aggregating Proofs): There is also a case where it is possible to verify that multiple elements belong to the accumulator set at the same time ？ Yes. . The idea is to put multiple values that you want to verify , A merger produces witness（ That is to say w）.

Then the example above , We can verify it all at once \$a_2,a_3\$, All contained in Accumulator in . Calculate first \$w =g^{a_2a_3}\$ verification ：\$root' =w^a\ mod\ N =?= root\$

We can integrate multiple witness The property of being one is called accumulation (Aggregating), And efficiently verify multiple witness It's called batch (Batching), stay Kate Promise batch processing in , There has been a similar treatment .

Summary

This paper describes the concept and properties of accumulator , Specify RSA Accumulator implementation process . It can be seen that Accumulator Have some advantages over merkle Where there are advantages , For example, aggregate proof , Prove that the size does not increase with the increase of set elements . In practical application RSA The accumulator also has some preprocessing operations , For example, map the original data to the value on the selected prime field .

Okay , About RSA accumulator , Next, we will continue to introduce non member proof and its application in blockchain .

In this paper, the reference ：https://www.cs.purdue.edu/homes/ninghui/papers/accumulator_acns07.pdf

Link to the original text ：https://mp.weixin.qq.com/s/3JqXXbt0HYwKmWC2SBk2HA Welcome to the official account ：blocksight

Mathematics in blockchain --Merkle Make a promise merkle promise

Mathematics in blockchain - Kate promise batch opening Kate Promise volume Certification

Mathematics in blockchain - I promise Knowledge and commitment

Mathematics in blockchain - Pedersen Key sharing Pedersen Key sharing

Mathematics in blockchain - Pedersen promise Cryptography promises --Pedersen promise

Mathematics in blockchain - Inadvertently transmit Oblivious transport protocol

Mathematics in blockchain - RSA Algorithm encryption and decryption process and principle RSA Encryption and decryption algorithm

Mathematics in blockchain - BLS Threshold signature BLS m of n Threshold signature

Mathematics in blockchain - BLS Key aggregation BLS Key aggregation

Schorr Signature and elliptic curve Schorr Signature and elliptic curve

Mathematics in blockchain -Uniwap Automated market maker core algorithm analysis Uniwap Core algorithm analysis （ in ）