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

本文一共[544]字，预计阅读时长:1分钟~

mathematics
blockchain
accumulator

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 ！

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 .

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

Accumulator establish ：

- setup: Choose a prime number g As a base , Then secretly choose two large prime numbers and multiply them to get N = p * q
- Add elements ： Set add elements a, Calculation $root =g^a\ mod\ N$
- 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_2*a_3}\ mod\ N=g^{a_2*a_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 .

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 ）

版权声明：本文为[blocksight]所创，转载请带上原文链接，感谢。 https://netfreeman.com/2021/04/20210413194617927u.html

- In depth analysis of the basic components of the defi loan agreement
- 美SEC指控区块链信贷公司非法出售超3000万美元证券
- 深度 | 巴菲特在数字资产的估值中错过了什么？
- The US SEC accused blockchain credit companies of illegally selling securities exceeding US $30 million
- What did Buffett miss in the valuation of digital assets?
- Solana上的跨链生态
- 广东省税务局区块链出口退税业务成功上线
- 区块链50收评 | 成分股涨跌不一 两极分化明显
- 新闻周刊 | 以太坊主网完成伦敦升级
- Cross chain ecology on Solana
- Guangdong provincial taxation bureau successfully launched the blockchain export tax rebate business
- Blockchain 50 closing comments | component stocks did not rise or fall significantly
- Newsweek - Ethereum main network upgraded in London
- 区块链大有前途，数字货币不会消失
- Blockchain has great prospects, and digital currency will not disappear
- 区块链中很重要的10个项目
- 解析去中心化衍生品三大流派：能否撼动中心化交易所地位？
- 技术周刊｜伦敦升级后以太坊平均每分钟燃烧2.36ETH
- 数字人民币本质上不也是人民币吗，为什么说能挑战美元霸权？
- 10 important projects in the blockchain
- Analyzing the three schools of decentralized derivatives: can we shake the status of centralized exchanges?
- Techweek London upgraded Ethereum burns an average of 2.36 eth per minute
- Isn't digital RMB also RMB in essence? Why can it challenge the hegemony of the US dollar?
- Blockchain practice (II) realization of pow workload proof | 15th day of settlement
- 外媒：美国新的比特币税收计划可能扼杀更环保的区块链技术
- Foreign media: the new bitcoin tax plan in the United States may stifle more environmentally friendly blockchain technology
- 【geth】Go调用智能合约 | 一起来学区块链
- 【geth】Go语言调用以太坊 | 一起来学区块链
- [get] go invokes the smart contract | together with the school district block chain
- [get] go language calls Ethereum | together with the school district block chain
- EIP-1559实施后 Gas为什么没有剧烈下降
- Why didn't gas drop sharply after the implementation of eip-1559
- 以太坊伦敦升级已完成 矿工有哪些注意事项?
- Ethereum London upgrade has been completed. What should miners pay attention to?
- 项目周刊｜以太坊在两天内销毁了新币发行量的36%
- Project weekly Ethereum destroyed 36% of the circulation of new coins in two days
- 加密企业如何通过区块链认证绿色能源？
- How can encryption enterprises certify green energy through blockchain?
- 从SEC主席最新演讲谈数字货币行业风控
- On risk control of digital currency industry from the latest speech of SEC Chairman
- DeFi 龙头的再进化之旅：纵览 Uniswap V3 生态全景
- The re evolution journey of defi leader: an overview of uniswap V3 ecology
- 英国拍卖行佳士得拍卖 Cryptopunks、Meebits、Bored Apes NFT
- 卡尔达诺报告：在 Wave Financial Group 的支持下实现完全中心化和全球金融普惠
- NFT，开启“元宇宙”的钥匙
- 以太坊燃烧第一个24小时：中文社区在关心什么
- British auction house Christie's auctions cryptopunks, meebits, bored apes NFT
- Caldano report: complete centralization and global financial inclusion with the support of wave financial group
- NFT, the key to the "meta universe"
- Ethereum burning for the first 24 hours: what does the Chinese community care about
- 趣币早报 |美国阻止财政部挑选加密货币的赢家和输家
- Qu coin morning post | the United States prevents the treasury from selecting the winners and losers of cryptocurrency
- 区块链 公钥 私钥 生成地址 关系
- Address relationship generated by blockchain public key and private key
- 如何实现去中心化跨链消息传递和资产转移？
- 以太坊伦敦升级：随之生效的以太坊EIP-1559是什么
- Tokemak能否支配更多DeFi流动性
- How to achieve decentralized cross chain messaging and asset transfer?
- Ethereum London upgrade: what is Ethereum eip-1559 in effect
- Can tokemak dominate more defi liquidity