blocksight 2021-04-26 16:16:40 阅读数:25
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 ！
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 ：
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 ）.
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 ！
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 ）