Non member proof of mathematical RSA accumulator in blockchain

blocksight 2021-04-26 16:16:40 阅读数:25

non member proof mathematical rsa

Write it at the front

In the last introduction Accumulator and RSA Accumulator, The accumulator can implement the set member proof , It can also be used as non member certification , This section continues with RSA The nonmember proof part of the accumulator .

This paper is based on the above , All the same symbols have the same meaning , It is suggested to read first !

RSA Accumulator nonmember proof

Non member certification (Non-Membership Witness) Is to prove that an element is not in the set . As a general rule , Positive proof ( In the assembly ) Relatively easy , Reverse proof ( Not in the assembly ) It's relatively difficult .

principle :** Suppose there are three elements in the set , when ,root = mod N To prove that an element is not in a set , You need to prove that it's not pi = Of ( plain ) factor , namely pi, Coprime .** Bezu's theorem (Bézout's identity) It's useful . On bezu's Theorem , It's also mentioned in previous historical articles , Here's a brief introduction :

Bezu's theorem :****ax + by = m (x, y) If and only if there is an integer solution m yes (a, b) Multiple of the greatest common factor of . in other words :ax + by = 1 ,(x, y) If and only if there is an integer solution (a, b) Coprime . On the contrary, relative to a.b also !

that , Our goal is to , Find a set of numbers <a,b> bring a + b pi = 1 You can prove that you are not root It means accumulator Inside .

Illustrate with examples :*** Make =5, = 13, = 17,pi = 5 13 * 17 = 1105, root = mod N

Make = 7, Generate 7 Proof that is not in the accumulator set :***158 7 + (-1)*1105 = 1 namely (a = 158, b = -1)

prove w =

Validation phase :

= g

Blockchain application

Stateless client (stateless client)

The blockchain system has the feature that data only increases but not decreases , The problem of data storage becomes more and more obvious as time goes by , There are only all nodes in the current blockchain system (Full node) All the data is stored , Light node (Light Client) To verify whether the transaction is legal, we need to check the status of the whole blockchain (State) Understanding , So at present, all consensus and verification are completed by the whole node .

Stateless Client early (2013) It is a research and development direction of blockchain , The bitcoin forum is also known as Storageless Client, It's right SPV Light node is an improvement , In short, one doesn't need to store all State, But can participate in the role of transaction verification ( Not like it SPV Light nodes can only be used for probabilistic validity verification ).

RSA Accumulator application

Blockchain existing merkle tree There are some problems with the scheme Stateless Client The obstacles . Such as Ethereum , Three merkle state root Record all state, Let's say there's only one left header Stateless client for , We can provide more than one merkle proof To prove to him that many storage Value , Indirectly proving that a transaction is legal . but merkle root did not stateless update Characteristics of , Can't in don't know all state Under the circumstances , Rely on others to provide proof To make the State root Update . in short , Even if you know the deal's legal , It doesn't update state root In order to verify the next transaction .

Switch to RSA Accumulator, In theory, you can have stateless client The ability to participate in the verification of transactions :** Submit the transaction to a stateless client, Also attach all the State Corresponding proof ( You can also use proof aggregation , Reduce proof size ).** When the stateless node receives a request , Take advantage of these witness To verify the transaction . After accepting the deal , Update local accumulator.

Theory belongs to theory , Reality is thin ! In practical engineering , There are many problems in application , For example, the generation of proof increases the amount of calculation , Trade off required .

Stateless client maintains a RSA Accumulator. This needs to constantly monitor the transactions of Ethereum or let the whole node broadcast the transaction time , It will be attached with witness, Increased traffic .

It adds complexity to the role division of nodes , All nodes may act as Data Provider&witness provider , There are also nodes dedicated to verification , Even specialized stateless client Required for interaction Accumulator node . It's looks good , It needs to be verified step by step !


RSA Accumulator Non member certification , Can carry on if use Accumulator Record a UTXO aggregate , Prove something UTXO There's no such thing as a scene .**** There are other types of accumulators , The application in blockchain is also worth looking forward to !.

Okay , Next, we'll go on to zero knowledge proof !.

Welcome to your attention & Looking at , If you have any questions, please leave a message !

Related reading :

Mathematics in blockchain ( seventy-one ) Accumulator and RSA Accumulator

Mathematics in blockchain ( Sixty-nine ) Kate Promise volume Certification

Mathematics in blockchain ( sixty-seven ) Knowledge and commitment

Mathematics in blockchain ( sixty-six ) Pedersen Key sharing

Mathematics in blockchain ( Sixty five ) Cryptography promises --Pedersen promise

Mathematics in blockchain ( sixty-three ) Oblivious transport protocol

Mathematics in blockchain ( Twelve ) RSA Encryption and decryption algorithm

Mathematics in blockchain ( sixty one ) BLS m of n Threshold signature

Mathematics in blockchain ( fifty-nine ) BLS Key aggregation

Schnorr Signature and elliptic curve Schnorr Signature and elliptic curve

Mathematics in blockchain ( Thirty-seven ) Uniwap Core algorithm analysis ( in )