search

omgnetwork / research

43 stars 2 forks source link

Back To The Snarks #87

Closed paulperegud closed 5 years ago

paulperegud commented 5 years ago

This feature is conditioned on #86 lifting the ban of chaining of transaction spends in the same block.

Not being forced to scale (in terms of orders settled per second) by increasing the size of the settlement means that the trade settlement can be small and snark friendly. We need to figure out how settlement proofs can be organized in situation when proof generation takes time. We can't wait for the proof to be generated to start generating next proof - that would re-introduce the limitations on throughput.

Problem: utxopos of change output

To start generating a snark for N+1 trade settlement, we need a way to spend the change output from N'th trade settlement. Utxopos does not work, it's not yet known. Snark can't be checked recursively since it's also unknown. What we can do instead, it rely on watchers and operator verifying blocks and trade settlement proofs one by one. As for the spend by something else (not trade settlement) - it is done by waiting for the trade settlement to settle, since that would assign utxopos to change output. Every other output (funds moving to traders) needs to be settled before it can be used.

Problem: hashing and signature verification is expensive in snarks

We will need to prove that hash value (public input) corresponds to order body (private input). This is true for both normal orders and partial orders. We also need to create a public commitment to partial order if such is created during this trade. Orders' signatures will be checked outside of the snark.

Solution to potential problem: order book integrity checks

One can create a merkle sum tree (of orders sorted by price) and prove that trading orders are a subset. Unfortunately this reveals at least some information about the prices. Needs more research.

image

boolafish commented 5 years ago

related to #68

boolafish commented 5 years ago

Problem: utxopos of change output

In Kelvin's suggestion to abstract design, it uses "id" for state/output. I am thinking this might be a good idea actually. This would make chaining txs easier and probably solve the issue here as well.

paulperegud commented 5 years ago

One more idea here: look into Powers of Tau ceremony by zcash. Why it is not used to do setup for projects on mainnet today?

boolafish commented 5 years ago

On the way of my random searching I see this idea using SGX for trusted setup: https://ethresear.ch/t/trusted-setup-with-intel-sgx/5531

Did not have real discussion and my intuition is that it probably does not worth dig into it. Just leave a note and see if it triggers any thought here.

boolafish commented 5 years ago

From the Readme of Powers of Tau, it produces parameters for BLS12-381 elliptic curve. Sadly, I believe current ETH curve is using alt_bn128. (unless the exact same curve have different namings XDD) I guess this is why nobody is using that atm

[EDIT: so BLS12-381 is definitely not supported yet in Eth: tracking issue here]

boolafish commented 5 years ago

Another thought, we might be able to claim us "RC" even if OmiseGO do the trusted setup all our own and generate the verifier code to venue. Previous RC trader trust our private key is not leaked, now trader trust the setup is not leaked.

Do you think this thought has potential to remove trust setup as a blocker? @whoisjeremylam @kasima

whoisjeremylam commented 5 years ago

I don't see a problem on a high level. However, I'm concerned about the practical implications - how we perform this trusted set up. If we are the first, then others in the Ethereum space will possibly use our trusted set up. Do we want this?

kasima commented 5 years ago

I'm comfortable breaking down this problem and addressing one piece at a time. If this means doing our own trusted setup while we figure out how apply upcoming research to address the issue, I'm open to the idea of doing our own. The one difference between a compromised private key as an operator and a compromised trusted setup is that plasma gives us recourse for losing the private keys (exit, mostly) while we don't have recourse for a compromised trusted setup. Of course, it's a complex attack and only worth doing once there's enough trade volume. Practically speaking, it seems reasonable to defer that piece of trustlessness.

@whoisjeremylam – can you elaborate further? Other projects have performed elaborate trusted setups. While it might be involved, we could learn from setups that have already happened.

If we are the first, then others in the Ethereum space will possibly use our trusted set up. Do we want this?

How so and what are the concerns?

boolafish commented 5 years ago

[Note] Following up @paulperegud's investigation on MatterLabs's implementation of power of tau (a fork that support curve on ETH)

I don't know how in the detail we could use the lib, but MatterLab probably already did it for their ignis plasma (?) also I see a fork from Gnosis too. So we might consult with them for the detail.

High level wise, it seems to me the path to do zk-snark this way is we write our own rust version of ZKSnarks using the the tools above + their dependency library (eg. bellman, ruby lib for ZKSnarks). Sadly, we could only write the circuit in low level atm if I understand it correctly.

Also, I think there is no rust --> solidity magic in the lib, so we would need to write a solidity version of verification code too.

[EDIT: we can take an intermediate step to go just RC first, then we don't need the solidity version of code. Operator verifies with zk-snark in rust to decide to mine or not.]

slavamirovsky commented 5 years ago

Hi there, I'm sharing some links. Sorry if they are irrelevant. Please someone take a look briefly. Maybe this somehow helps.

Implementation of zkSnarks (not full): https://devpost.com/software/zexe-on-ethereum https://github.com/edcon-reiwa/zexe-ethereum

Papers / articles: https://eprint.iacr.org/2013/879.pdf https://medium.com/loopring-protocol/loopring-bi-weekly-update-06-08-2019-16fdd110adf4 https://tlu.tarilabs.com/cryptography/bulletproofs-and-mimblewimble/MainReport.html https://github.com/gnosis/dex-research/blob/cc9cdb9ebed2d27732aa512bc649ebbffd5fed91/dFusion/dFusionSpec.md

Russian sources: https://cp0x.com/topic/104-zero-knowledge-zk-snark-stark-bulletproofs/ https://zen.yandex.ru/media/id/5c11686b50fd0800aa141264/primenenie-tehnologii-zkstark-v-decentralizovannyh-birjah-resistance-i-starkware-5cb2075f57a23700b3c31dae (they talk a lot about STARK though)

Example (please translate yourself): Команда Starkware и 0x выпустили демонстрационную версию DEX с использованием технологии STARK на тестовой сети Ethereum Ropsten, в которой были смоделированы сделки Binance как они происходили в реальном времени. Цель была в том, чтобы показать, что DEX могут конкурировать по производительности с централизованными обменами. И кажется, что им это удалось, так как они достигли возможности производить 500 сделок (🔥) в секунду, что примерно в 200 (!) раз больше, чем пиковая мощность Ethereum в данный момент, при использовании не более 1000 газа за сделку.

Каким образом?

StarkDEX обрабатывает большую часть расчётов вне цепочки (оффчейн), отправляя в блокчейн только доказательство нулевого знания целостности расчётов и правильного сопоставления сделок

boolafish commented 5 years ago

[Note]

Some potentially way to implement:

  1. Don't do ceremony at all, just claim us RC. Use Zokrate to generate the codes.
  2. Do ceremony with original powers of tau + phase2, give up verifying on Ethereum, only operator checks via rust code, and claiming us RC. However, we would need to write low level circuit our own, so probably not really feasible.
  3. Use MatterLab's powers of tau + we fork and implement the phase2 ourselves (or find sb's implementation for BN256). Port the parameter of our phase2 result to Zokrate. We don't need to claim the ceremony is 100% safe, but we can claim us better than RC (if #100 solved).
paulperegud commented 5 years ago

Here is a fork of Powers of Tau for Ethereum. https://github.com/matter-labs/powersoftau

It supports BN256 curve, which is supported by Ethereum today. Andy is investigating how much work adopting phase2 will require.

paulperegud commented 5 years ago

Remark on circuit design (popped up in discussion with Andy). Order as whole should be public, only the price needs to be blinded (hash(price, nonce)). This way we can check almost everything outside of the snark.

slavamirovsky commented 5 years ago

Interesting. Sorry for going into details. Maybe this is irrelevant at this point. But what does it mean almost everything?

boolafish commented 5 years ago

[Note on porting phase2 to support Bn256 curve]

TL;DR It seems pretty possible to port phase2, with the following assumption:

  1. MatterLab implementation of bellman that supports BN256 has all interface keeps the same and working perfectly.
  2. Current phase2 package works (it states WIP in readme)

Zokrate notes

whoisjeremylam commented 5 years ago

How so and what are the concerns? If we perform a trusted setup that is Ethereum compatible and are the first, then this set up will probably be re-used by other Ethereum projects.

If we don't perform the ceremony properly and the the set up is compromised, this could lead to loss of funds for everyone who uses our set up.

boolafish commented 5 years ago

@whoisjeremylam curious, are you expecting people aside from our venue using our setup? Or the concern is on venue on top of us? (I thought the second is just covered by RC assumption/limitation)

paulperegud commented 5 years ago

boolafish [4 hours ago] how are we gonna proceed with this? have a call and make decision?

Slava [3 hours ago] I need your opinion and Pepesza's opinion. You share it here. Kasima, Jeremy and me, we analyze it. Then we go for a call if needed.

boolafish [3 hours ago] okay, one piece unclear for me is about flexibility. That was one critical reason that we choose trade verifier path because zk-snark would (potentially) need to custom for every new venue. But I don’t know how much we care/value that as it seems like we are on-boarding our venue one by one now anyway.

boolafish [3 hours ago] zk-snark sounds pretty doable, ceremony is quite possible to do if we want. However, it would have limit on numbers of order per tx (latest data from Pepesza seems like only around 1~2 hundreds). Seems to me that it would work well with continuous trading as we can chain txs to increase throughput. However for call market I doubt that size can be enough (edited)

boolafish [3 hours ago] I think zk-snarks works well and could differentiate us with existing exchanges for retail exchange as it would be continuous trading. (edited)

Slava [2 hours ago] As flexibility, this is a valid point. Totally :slightly_smiling_face: However the most important thing for now is: next level of security. We need to have some value proposition and security with zk-snarks would be a good selling point.

Slava [2 hours ago] As per limit on numbers, good observation. Thanks for sharing this piece of data. Continuous trading (or batch trading) has its characteristics. This is the approach taken by most of the stock exchanges, derivatives exchanges and forex market now. In other words, for retail traders should be fine.

Slava [2 hours ago] @jeremy I'm happy to hear your opinion on continuous trading. Please share your experience. (edited)

Slava [2 hours ago] @boolafish totally agree with your opinion. @pepesza happy to hear your thoughts on the topic. Reminder, there are three options: a) snarks & retail traders, b) intermediate solution & retail traders, c) institutions. A, B, C works for u better?

boolafish [2 hours ago] hmmm so far it seems to me for b/ we can go straight to a/ instead.c/ is still a pretty valid option to me though. If trade verifier + idea3 (limit custody) does has enough value to institution then it is almost as same effort we need to pay anyway to snark. Feel like why not just as well verify that (?) and we could test other part of our dex faster and get feedback earlier.

boolafish [2 hours ago] but if it is obvious any intermediate security is not able to compromise, then yeah….let’s go straight snark.

pepesza [2 hours ago] I also think that SNARKs are the primary viable option. Agree with @boolafish assessment of fit for retail trade.re: ceremony. We should treat this one as a one-by-one process only short term - because SONIC is coming. Also, I don't think that bar for this ceremony is that high in our case. Unlike in ZCash case, compromised ceremony would be easy to detect and potential losses would be very limited.

Slava [2 hours ago] Thanks. Let me rephrase the question. So I can understand for 100%. Are we ready to implement SNARKs (we are going for them then) or no (we are discussing other options)? :wink:

Slava [2 hours ago] As per institutions (I understood the validation part is about them), we cannot do it that easily. Clearpool is pretty much nowhere with their implementation yet.

pepesza [2 hours ago] We should go SNARKs route because: 1) SGX is just crazy - it's unknown unknowns. 2) The only possible way of doing STARKs today is buying stack from Starkware. I don't believe we have a mandate to spend community money on proprietary stack. 3) SNARKs, while it would require some programming usually reserved to implementers of cryptographic stacks, are really doable. In the worst case we will pay someone in the field to help us review/audit the code. The rest of the implementation is clearly in our reach.

Slava [2 hours ago] @boolafish @pepesza I understand your point is: A) SNARKs and retail traders then. Good. @kasima @jeremy what are your thoughts? Can we assume this is doable and proceed with this option? Meaning we are going for super security with SNARKs. This is our selling point.

kasima [32 minutes ago] Is the biggest risk here the ceremony? Let's work through the details and figure out how we can mitigate. I like Pepesza's thinking here:

Unlike in ZCash case, compromised ceremony would be easy to detect and potential losses would be very limited.

Noted, @boolafish, about the flexibility. Let's figure out a working end-to-end solution and we can think about flexibility from potentially a product/business perspective. From an engineering angle, it would be a big milestone to see the system work with one production venue.

kasima [32 minutes ago] @pepesza – can you talk more about SONIC?

kasima [31 minutes ago] From an engineering perspective, how much more complexity will it be to support snarks in the development? Assuming we finish the abstract contract work for MoreVP + broken ERC-20 tokens, roughly how much more time do you think it would be to add SNARKs? (very very loose estimate) (edited)

jeremy [29 minutes ago]

I'm happy to hear your opinion on continuous trading.

We should continuous trading as a priority to be able to support liquidity. Auctions (batch trading) are useful for assets where price discovery is difficult.

jeremy [23 minutes ago]

compromised ceremony would be easy to detect

This is very interesting - how would we be able to detect this? Can we pull the plug on settlement if we detect?

kasima [23 minutes ago] Any way we could move this conversation to somewhere less ephemeral than Slack? GitHub would work for me

Slava [21 minutes ago] KK

pepesza [4 minutes ago] @kasima SONIC is a version of zkSNARK with same asymptotic characteristics but with universal trusted setup. There will be only one trusted setup ceremony, done by Ethereum community as whole, which will cover all existing and all future circuits.

re: engineering complexity. There ceremony needs to be done once. Software for the ceremony was written in Rust and requires a change in the elliptic curve used to one used by Ethereum (BN256). For the production snark would involve proving on the venue side (prover is written in Rust, can be called as a batch job). Verifier will be written in solidity. We can use it by calling ethereum node via RPC on operator and watcher nodes.

One more interesting note - we want trading to be performed without waiting for proofs to be generated. For that a venue would need to provide traders with a (trustless) feed with information about trade settlements already finalized so the traders can continue trading. Settlements would be emitted with time delay needed to generate proofs (<5 minutes, exact numbers TBD). Emitted settlement included into block and consumed by trader's watcher would enable trader to withdraw the money safely.

boolafish commented 5 years ago

[Note]

whoisjeremylam commented 5 years ago

A question about the construction of the SNARK. How would we go about building a SNARK based upon an existing order-book algorithm?

paulperegud commented 5 years ago

fast insert / deletion (within log(n) complexity)

The possible solution is having two circuits - one for processing, one for tree balancing.

paulperegud commented 5 years ago

fast insert / deletion (within log(n) complexity)

@boolafish Re: using two heaps - one for asks, other for bids is viable after all. Random access delete is possible with heap (correcting my statement from before).

slavamirovsky commented 5 years ago

Hi there, things around SNARKs are getting crystal clear step by step. But we still need to deep dive. I know that some of the questions were asked this week. Anyway, I need precise answers: 1) If we eventually go for SNARKs, does it mean we don't need a third party to play a role of trade validator? In other words, what is the relationship between 3rd party and SNARKs in terms of retail traders? My understanding is that our venue (CEX) should generate a proof (confirmation), right? 2) Can we get some detailed sequence diagram (we can literally copy and paste the current and make some changes). So far I remember we said that flow will be the same. Please confirm or adjust our diagram. 3) How would we go about building a SNARK based upon an existing order-book algorithm? We heard so far that the possible solution is having two circuits - one for processing, one for tree balancing. Shortly, what does it mean? How does it look like? 4) I feel like in general we would like to learn what does it mean SNARK step by step for end traders, for venues, for our implementation (operator), etc? Are we ready to explain that? Have we already covered all doubts?

boolafish commented 5 years ago

@Nikodemek18

paulperegud commented 5 years ago 
1. If we eventually go for SNARKs, does it mean we don't need a third party to play a role of trade validator?

No third party needed. CEX will generate the proof, participants (operator, watchers) will check the proof.

We heard so far that the possible solution is having two circuits - one for processing, one for tree balancing. Shortly, what does it mean? How does it look like?

4. I feel like in general we would like to learn what does it mean SNARK step by step for end traders

Snark is transparent to traders.

for venues

Every change in trading algo would require a new trusted setup ceremony. Basically - changes are hard to do until community deploys SONIC. 

for our implementation (operator)

Not much. eth_call to a solidity based verifier (a predicate in terms of our plasma framework) OR a call to rust-based external process that would check the snark. In case of need to optimize this call, we can turn it into NIF and make it blazing fast. Speed in not really a concern here anyway - settlement can only be a dependency of other settlement in a single block.

slavamirovsky commented 5 years ago

@paulperegud thanks for explaining. Do you think it would be possible for us to create the list of things we still need to learn / verify in regards to SNARKs? Then we would just go one by one and everyone would see how many have left? Is that doable at this point?

boolafish commented 5 years ago

From software perspective, I think we need to learn the followings risk:

paulperegud commented 5 years ago

Nothing of that is production ready (as linux kernel; maybe it is production ready as elixir-omg). None of it is safe as in bug free. Risks are there. Fortunately we are software engineers and we know how to test stuff. There will be bugs in implementation. But there should not be any bugs in math - zcash people put enough work into that already.

As for production readiness - verifier and prover will be in production. Interesting part is the prover. ZoKrates one is multicore capable and it gave us some nice performance numbers. Will it crash on us at some point? No idea, really.

boolafish commented 5 years ago

One more thing I am a bit worried is also about compiling part, unless we are code reviewing the circuit that it generates (awwwww....though it is possible that we do so).