0%
#Bitcoin

zkSNARKS and Cryptographic Accumulators

2020년 8월 24일 10 분 읽기
뉴스 기사 배너 이미지

In the cryptocurrency world, trading and spending works only if transactions cannot be double spent. So, two checks are performed: one, a transaction must be valid; and two, a transaction must not have been spent. Essentially the first check is a set membership test, and the second is a set non-membership test. A membership test is used to determine if an element is present in a set of values. A non-membership test is used to determine the absence of an element in a set of values. The most popular set of values in production are Merkle-Trees since checking if a value is in the set doesn’t require knowledge of the entire tree, only enough of the subset to validate a specific path to a value. Yet, applying ZKPs to a Merkle-Tree is complicated. The reason to use ZKPs is to hide the value and the path being checked to preserve privacy. But in order to do so, custom circuit-based ZKPs have to be designed which consider the various setup parameters:

  • Which cryptographic hash function to use?

  • What’s the maximum depth?

  • Are transactions allowed to be pruned?

  • Selection of elliptic curves

  • Proving time and computational requirements

  • Verification time

  • Proof size

  • Proving key size

  • Set size

zkSNARK is the technique receiving the most attention and research to optimize the landscape. Coda is applying zkSNARKS in a recursive manner to shrink the size of the blockchain for validation. ZCash uses SNARKS to anonymize parties and obscure amounts exchanged by performing multiple proofs: one for signature validation, the other to ensure the transaction is valid. However, SNARKs come with some drawbacks. For one thing, the desired arithmetic circuit needs to be designed so a proper Common Reference String (CRS) can be generated. The CRS is the public parameters of the system [ ZCash]. Then, which system should the SNARK use? Spartan, Halo, Hyrax, Libra, Sonic, Plonk, Marlin… Each one has tradeoffs between trusted setups, proof size, bilinear pairings or other elliptic curves, proof generation and generation time. SNARKS are not the only circuit based systems that can be used. Bulletproofs, Bulletproofs+, STARKS, SNARGS… the list goes on but there is no clear winner and all of them require advanced knowledge in cryptography. Fortunately, another cryptographic primitive exists for performing fast set membership (and non-membership) proofs that preserves privacy (in that the element being checked is not revealed), and provides succinct proofs. These are called cryptographic accumulators.

Cryptographic Accumulators

Accumulators allow parties to prove that an element x is in a set S or not regardless of the number of elements in S, while not disclosing which element was checked. Accumulators work by adding a value x to (or removing from) a constant-size accumulator A, and proving that membership witness u, when combined with x, equals accumulator A. Accumulator values are short fixed-length digests (similar to hash functions), but also support short proofs for membership and non-membership checks for any element in the set. In other words, an accumulator represents the entire set of elements by a single value, the size is independent of the number of elements. An accumulator is dynamic if elements can be efficiently added or removed from the set. Otherwise the accumulator is static. A universal accumulator is dynamic and supports both membership and non-membership proofs. Otherwise the accumulator is said to only support membership proofs.

Due to the simpler setup and shorter proofs, these offer an interesting alternative to SNARKs. This is not a new concept to replace the membership test portion of proofs with an accumulator [see OWWB19]. However, OWWB19 proposes using an accumulator inside the SNARK versus dropping SNARKs altogether. They show the accumulator SNARK combination has less expensive cost requirements in space and performance as will be shown in this article as well.

Accumulators fall into the following three categories: Unknown-Order e.g. [ Sander97, BP97, BM93, CL02, LLX07, Lip12, BCDLRSY17, BBF18, OWWB19, DGS20], Bilinear Maps [ Nguyen05, ATSM09, CKS08, DT08, Thakur19, VB20], and hash-based [ CHKO08]. Each one offers tradeoffs between setup parameters, accumulator sizes, witness and proof performance and space. Unknown order accumulators are subdivided into RSA-based and Hyperelliptic curve based (class orders). The remainder of this article focuses on the story about implementing the RSA-based accumulator and how they work.

RSA accumulators afford the most efficient tradeoff between the number of setup parameters, updating witness requirements, proof computation and succinctness. The accumulator value and witness are the size of an RSA modulus. When implemented, the modulus, accumulator value and witnesses are 256 bytes with 32 byte elements, and membership proofs are 800 bytes and only require 90 milliseconds(ms) to compute, uses 2KB of RAM and 30ms to verify. Witness updates can be computed in 5–10ms depending on the underlying system. Non-membership proofs require creating two proofs but the proofs can be computed in parallel which takes the same amount of time but twice the space with 1.6KB.

Contrast this to ZCash’s JubJub SNARK which requires downloading the entire Merkle-Tree which is a couple of gigabytes, downloading the proving key around 32MB, generating a 458KB witness in 1 second using 150MB of ram, generating the proof using 106MB of RAM, taking 3 seconds, and producing a 1.4 KB byte proof [ CryptQuest2018]. The advantage of cryptographic accumulators is that proofs are succinct and fast to compute.

How it works

To set up an RSA accumulator requires generating two safe primes ( p, q) of sufficient size (≥ 1024-bits) to compute the coprime modulus n and creating a generator that is a quadratic residue g, essentially find a random number and compute the modular squaring. g is the empty accumulator value and used for creating non-membership proofs. The generation of ( p, q) is commonly done with a trusted dealer but some distributed methods allow it to be done in a decentralized manner [ AVD19] (trustless) albeit more complicated. Each element to be accumulated must be a unique prime number. Values can be mapped to prime numbers by a function that is usually either a lookup table or a hashing algorithm and added to the set S. The accumulator value is computed as follows:

Values are accumulated by computing the modular exponentiation of the current accumulator value to the new element. Removals can be computed two ways: with knowledge of p, q and without. The trusted accumulator creator (or dealer) uses p, q to compute Euler’s totient and compute:

Mind your p’s and q’s, because without them, the accumulator has to be recomputed by multiplying all elements in the accumulator with a modular exponentiation, again. A user has a membership witness or non-membership witness (or both) depending on the type of proof that is expected by a relying party. The membership witness u is computed:

The witness must be updated to reflect any changes made to the accumulator otherwise proofs will be invalid. Users can efficiently update their witnesses as elements are added to and deleted from the accumulator. Unfortunately, implementing the non-membership variant was much more complicated than the membership version. The batching paper shows the non-membership witness as

This works okay, proofs compute normally and work out just fine. The caveat happens when attempting to update the witness w. The batching paper refers to another paper LLX07 for this math. At first the math appears simple in section 4.2 where it says to do the following for addition:

To verify the correctness of the update, compute a current non-membership witness without doing an update and compare for equality. However, they don’t match (overturn desk).

Implementation headache

To check if the match is working properly, I insert multiple assert statements that check the assumptions made in LLX07. All pass minus the final assumption. After being puzzled by this for a while, I read the LLX07 from the beginning and discover that the non-membership witness differs by a sign, Bg-b. I made this change and non-membership updates work correctly, but now the proofs are broken. The only option is to work through the math again to make sure things check out and look for where it doesn’t. The equation at fault here is the proof that computes the proof of knowledge of exponents (POE, proof that the exponents are known to the prover without revealing them) with the current accumulator A and non-membership value a. Instead of inverting V, the generator g needed to be inverted, moving the modular inverse operation. Here’s a before and after:

Send V, Q, B to be verified:

Why this change? Let’s look at before and after in depth.

Before:

B was changed to B=gb to B=g-b the old equation becomes:

The goal of the non-membership proof is to get the exponents to equal ax*+bx = 1. Thus the change to g-¹. With that change it becomes:

This is often one of the trickiest parts of implementing cryptography is checking equations for errors and making necessary corrections. The contact for the batching paper was notified of these changes but has not yet responded to the update. The working code implementation can be found here. We see that the code, while it had some hiccups, was much easier to use and implement than SNARKs.

Stay tuned to the Coinbase Engineering blog, as a follow-up article will dive into Bilinear Accumulators to compare and contrast RSA and SNARKs.

If you are interested in the complexity of applying zero-knowledge cryptography, Coinbase is hiring .

This website contains links to third-party websites or other content for information purposes only (“Third-Party Sites”). The Third-Party Sites are not under the control of Coinbase, Inc., and its affiliates (“Coinbase”), and Coinbase is not responsible for the content of any Third-Party Site, including without limitation any link contained in a Third-Party Site, or any changes or updates to a Third-Party Site. Coinbase is not responsible for webcasting or any other form of transmission received from any Third-Party Site. Coinbase is providing these links to you only as a convenience, and the inclusion of any link does not imply endorsement, approval or recommendation by Coinbase of the site or any association with its operators.

was originally published in The Coinbase Blog on Medium, where people are continuing the conversation by highlighting and responding to this story.

트레이딩을
자동화
하세요!

세계적 수준의 자동화된 암호화폐 거래 봇

시작하기
트레이딩 자동화

인기 뉴스

How to Set Up and Use Trust Wallet for Binance Smart Chain
#Bitcoin#Bitcoins#Config+2 더 많은 태그

How to Set Up and Use Trust Wallet for Binance Smart Chain

Your Essential Guide To Binance Leveraged Tokens

Your Essential Guide To Binance Leveraged Tokens

How to Sell Your Bitcoin Into Cash on Binance (2021 Update)
#Subscriptions

How to Sell Your Bitcoin Into Cash on Binance (2021 Update)

What is Grid Trading? (A Crypto-Futures Guide)

What is Grid Trading? (A Crypto-Futures Guide)

Cryptohopper에서 무료로 거래를 시작하세요!

무료 사용 - 신용카드 필요 없음

시작하기
Cryptohopper appCryptohopper app

면책 조항: Cryptohopper는 규제 기관이 아닙니다. 암호화폐 봇 거래에는 상당한 위험이 수반되며 과거 실적이 미래 결과를 보장하지 않습니다. 제품 스크린샷에 표시된 수익은 설명용이며 과장된 것일 수 있습니다. 봇 거래는 충분한 지식이 있거나 자격을 갖춘 재무 고문의 조언을 구한 경우에만 참여하세요. Cryptohopper는 어떠한 경우에도 (a) 당사 소프트웨어와 관련된 거래로 인해, 그로 인해 또는 이와 관련하여 발생하는 손실 또는 손해의 전부 또는 일부 또는 (b) 직접, 간접, 특별, 결과적 또는 부수적 손해에 대해 개인 또는 단체에 대한 어떠한 책임도 지지 않습니다. Cryptohopper 소셜 트레이딩 플랫폼에서 제공되는 콘텐츠는 Cryptohopper 커뮤니티 회원이 생성한 것이며 Cryptohopper 또는 그것을 대신한 조언이나 추천으로 구성되지 않는다는 점에 유의하시기 바랍니다. 마켓플레이스에 표시된 수익은 향후 결과를 나타내지 않습니다. Cryptohopper의 서비스를 사용함으로써 귀하는 암호화폐 거래와 관련된 내재적 위험을 인정하고 수락하며 발생하는 모든 책임이나 손실로부터 Cryptohopper를 면책하는 데 동의합니다. 당사의 소프트웨어를 사용하거나 거래 활동에 참여하기 전에 당사의 서비스 약관 및 위험 공개 정책을 검토하고 이해하는 것이 필수적입니다. 특정 상황에 따른 맞춤형 조언은 법률 및 재무 전문가와 상담하시기 바랍니다.

©2017 - 2024 저작권: Cryptohopper™ - 판권 소유.