search

barryWhiteHat / roll_up

scale ethereum with snarks
360 stars 50 forks source link

Compress data passed as public inputs to the snark #33

Open barryWhiteHat opened 5 years ago

barryWhiteHat commented 5 years ago

Each public input that is passed to the snark costs ~ 40k gas. We want to reduce this by hashing together all the inputs inside the EVM and then hashing them together again inside the snark and ensuring that they match. The data being the merkle tree address of each leaf updated AND its new leaf. We can reduce the size of the data we need to pass in the future but this is a good conservative first step.

https://github.com/barryWhiteHat/roll_up/blob/master/src/roll_up.tcc#L40 we start to pack our inputs into feild elements so we can pass them.

https://github.com/barryWhiteHat/roll_up/blob/master/src/roll_up.tcc#L82 is where we define the number of public inputs we want to allow. We want to in the snark

  1. reduce this to one
  2. perform the hashing inside teh snark

And In the contract

  1. compute the input from the passed transactions https://github.com/barryWhiteHat/roll_up/blob/master/contracts/roll_up.sol#L48

And in python

  1. pass the transactions to the EVM

We can use https://github.com/HarryR/ethsnarks/pull/78 once it is ready. @HarryR can you advise when this is ready?

HarryR commented 5 years ago

https://github.com/HarryR/ethsnarks/pull/78 has been tested and merged.

FYI every public input costs 40k gas, not 200k.

With the new sha256_many gadget you can pass-in an arbitrary sized array of bits, so a large amount of data can be verified between Ethereum and the circuit using only 2 public puts to verify (or a single input, truncated to 253 bits, and it's safe to truncate SHA256 outputs in the random oracle model)

mathcrypto commented 5 years ago

What is the difference between "sha256_many" gadget and the one from libsnark https://github.com/scipr-lab/libsnark/blob/master/libsnark/gadgetlib1/gadgets/hashes/sha256/sha256_gadget.hpp?

HarryR commented 5 years ago

The sha256_many gadget is compatible with the SHA256 function as used on Ethereum, in Python and generally everywhere, whereas only the raw compression function gadget is implemented in libsnark.

sha256_many extends the compression function gadget to perform input padding for arbitrary length inputs, and chains the raw compression function together.