search

barryWhiteHat / roll_up

scale ethereum with snarks
360 stars 50 forks source link

Roll Up Meeting 8 Agenda #36

Closed barryWhiteHat closed 5 years ago

barryWhiteHat commented 5 years ago

Meeting Time/Date: Thursday 22 November 2018 at 12:00 UTC

https://meet.jit.si/SlyMushroomsCommunicateFlatly

  1. Introductions
  2. Circuit implementer updates
  3. Prover updates
  4. Whats the best way of supporting multiple tokens in one chain
  5. What hash functions to use from deposits / withdraws?
barryWhiteHat commented 5 years ago

Circuit implementer updates

Harry is almost done with EDDSA, looking at pedersen hash next.

Alex is working on bellmen implementation.

Prover updates

Test with belman on large server in progress. AWS numbers to be reported soon.

Whats the best way of supporting multiple tokens in one chain

Agree its a good idea to allow multiple tokens but need to think more about

  1. data availability
  2. how many tokens to support

How to allow contracts to interact with roll_up

We could hae special transaction type where contracts can interact

How to allow roll_up users to interact with contracts

Possibly allow users to withdraw on mass, interact with contract then redeposit.

HarryR commented 5 years ago

EdDSA and Pedersen hash are done, apart from one failing test. What's next is Pedersen Hash integration with Merkle Tree as an alternative to MiMC/LongsightL. I don't think it's feasible at all to do pedersen hash proving on EVM due to the high cost of scalar multiplication operations.

Another thing which came up was the programming style of Bellman vs libsnark, and are there programming practices which can make libsnark easier / more straightforward to program (Alex mentioned cognitive load of a C++ codebase, being split into construction, witness generation and constraint generation). I will investigate this as I think there are different ways of constructing circuits using libsnark which would be easier to understand and faster to program.

Also need to investigate further into why Pedersen Hash (or MiMC-p/p) could not be used as the message digest for EdDSA signatures, need to ask in zapps-wg about proof of insecurity for non-Random-Oracle-Model hashes being used for the Fiat-Shamir transform (as used by Schnorr signatures, and EdDSA). Related links:

From 2012/721:

This generic transformation leads to very efficient schemes and has thus grown quite popular. However, this transformation is proven secure only in the random oracle model. In FOCS 2003, Goldwasser and Kalai showed that this transformation is provably insecure in the standard model by presenting a counterexample of a 3-round protocol, the Fiat-Shamir transformation of which is (although provably secure in the random oracle model) insecure in the standard model, thus showing that the random oracle is uninstantiable. In particular, for every hash function that is used to replace the random oracle, the resulting signature scheme is existentially forgeable. This result was shown by relying on the non-black-box techniques of Barak (FOCS 2001).

From Zcash-wg:

Because a Pedersen hash only provides collision-resistance, whereas we need a PRF (or at least properties close to that - daira will correct me 😅) in RedDSA.

We need a hash suitable for Fiat-Shamir, which is usually modelled as a random oracle. Schnorr signatures are derived from the Schnorr identification scheme using the Fiat-Shamir heuristic there's no standard-model hash function property that is sufficient for that also, we need a hash with a 512-bit output [while] Pedersen hashes only produce an output as large as the field, which is 255 bits for Jubjub.

From https://ed25519.cr.yp.to/eddsa-20150704.pdf

EdDSA with prehash parameter H' is also written H'-EdDSA. The signature of M under H'-EdDSA is the signature of H'(M) under PureEdDSA. One can take H' to be a different hash function from H: for example, the SHA-256-Ed25519-SHA-512 signature of M is the Ed25519-SHA-512 signature of SHA-256(M). See below for details of Ed25519-SHA-512.

Selecting hash functions: SHAKE256, part of the forthcoming SHA-3 hash-function standard, is designed to straightforwardly generate arbitrary output lengths at a 256 security level. (Efficiency note: SHAKE256 internally generates outputs as 136-byte blocks, so a single SHAKE256 block handles b as large as 544.) Choosing SHAKE256 with 2b-bit output as the hash function inside EdDSA has the benefit of allowing multiple curve sizes to be handled directly by a single hashing module. SHA-3 has many other advantages over SHA-2, not summarized here.

However, in recognition of today’s widespread deployment of SHA-512, this document instead presents EdDSA parameters that use SHA-512 for hashing. SHA-512 was originally defined to produce only one output length, 512 bits, but can easily be reused to produce shorter output lengths by truncation, and longer output lengths by concatenation.

Where H is used to derive r from k and m, and H' is used to derive M from m.

Specifically where replacing H' with MiMC-p/p, Jarvis or Pedersen Hash, I don't see how it could affect the integrity of the message being signed as long as it's pre-image collision resistant. Nor is there any requirement for H' to be 2b-bits long.

Whereas, with H (used to derive r), a larger hash function is used and it doesn't affect verification or add extra work in-circuit.