barrywhitehat / roll_up Goto Github PK

Meeting Time/Date: Thursday 14 December 2018 at 12:00 UTC

https://meet.jit.si/SlyMushroomsCommunicateFlatly

• Introductions
• Circuit implementer updates
• Should we freeze spec? Just features there will probably still be a bunch of changes. But no new feature or optimizations.
• Smart contract interfaces and definitions, even if the circuits are slightly different, is there a common interface for the smart contracts that is easier / faster to define now?
• How to deal with the next version of roll_up and spec implementation in parallel?
• Batch verification of signatures, example code: https://gist.github.com/HarryR/917a7d8596be745967655e3d33d2e7b4 - reduces the number of scalar multiply operations necessary to verify a batch of signatures by 50%, but introduces an aspect of malleability. Is vulnerable to the 'Rogue Key' attack, so would need a signature to be provided by every key that's being inserted into the accounts tree.
• Further optimisation to batch verification which requires only 2 scalar multiplies per-batch... but the scalars need to be sum'd by the operator as the circuit cannot do anything modulo the curve order in-circuit.
• Creating a 'small tree' of all accounts used in the current batch of transactions at the beginning of the batch, using that tree (with shorter merkle auth paths) for every TX, then doing a batch update at the end. For 1024 transactions per block, would reduce the depth of each merkle auth path from 24 to 10.
• Jordi's optimisation for Pedersen Hash multiplication, using a bigger lookup table with the same properties as the 2bit signed lookup table.

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

https://meet.jit.si/SlyMushroomsCommunicateFlatly

1. Introductions
2. roll_up on chain data availability Implementations
3. Proving time optimizations

Meeting Time/Date: Thursday 27 Sept 2018 at 12:00 UTC

https://meet.jit.si/SlyMushroomsCommunicateFlatly

1. Introductions
2. Could collaboratively write a high level summary of exit/rollback so its easy to digest. https://hackmd.io/Vf0UGeuvR2mgApVS60VepQ?both
3. Questions about yellow paper https://github.com/barryWhiteHat/roll_up_yellow_paper
4. Other?

Because input variables are quite expensive to pass to snark verification I would be interested to hear thoughts on a compression function that can be uncompressed inside the snark cheaply.

So you would pass the compressed data and then expand it in snark. Allowing us to compress multiple field elements into fewer elements to reduce the inputs.

This could let us with our data availability problems #6

I've been looking at the preprocessing behavior of the Python test case in order to wrap my head around the interface to this library. There is some logic that, according to the documentation, is changing the endian-ness of the public keys.

As far as I've seen the term used before, "reversing the endianness" of a series of bytes requires reversing the order of bytes in the series without also reversing the order of bits within each byte. There is such a thing as 16-bit endianness and 32-bit endianness, but without such qualification, my understanding is that 8-bit bytes are the usual word size.

Big-endian order feels natural to native English speakers as we typically write our numerals left to right in decreasing order of significance. One might send "120" emails in a day in decimal big-endian, or 021 emails in decimal little-endian. And 8-bit little-endian is sometimes also known as "network byte order"

So consider a 4-byte string encoded in hexadecimal using big-endian byte order. Imagine that looks like 8c94ab3f. Security absurdities aside, lets presume this happens to have been one coordinate of a generated public key that we want to put into the witness for a roll_up proof. If the documented requirement is that this is sent in little-endian order, I would expect the required input to be 3fab948c. The content and relative order of each pair of hex characters would have been preserved, reflecting the fact that I have not changed the bit order within each byte, but the order in which each pair of characters occurs has been reversed.

Using the same methods as the Python test case, however, I wind up with the value fcd52931. Looking more closely at this value, I can see that it is a bit-by-bit reversal of the input string, not an endianness reversal. The following uses some helper routines I used to capture useful subsets of the complete statement used in the Python test suite, but contains the very same logic:

>>> hex(binaryToInt(hexToBinary("0x8c94ab3f"))) # This is documented to reverse the endianness
'0xfcd52931'
>>> hexToBinary("0x8c94ab3f"))
[1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1]
>>> hexToBinary("0xfcd52931")
[1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1]

A theory that the test case is actually revering the entire bit sequence, not altering its endianness is supported by the fact that, at least for this input, it is symmetrical:

>>> hex(binaryToInt(hexToBinary("0xfcd52931")))
'0x8c94ab3f'

...However, it is also possible to provide inputs where the passing the output of the first call to the input of a second call does not is asymmetric, but when that output is passed to a third call, we find that the sequence stabilizes on a symmetrical pair of reversible bit sequences...

>>> hex(binaryToInt(hexToBinary('0x2c94ab38')))
'0x7354a4d'
>>> hex(binaryToInt(hexToBinary('0x7354a4d')))
'0x5929567'
>>> hex(binaryToInt(hexToBinary('0x5929567')))
'0x7354a4d'

Looking at the bit-strings makes it easy to see why things have become so apparently scrambled:

>>> hexToBinary('0x2c94ab38')
[1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0]
>>> hexToBinary('0x7354a4d')
[1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1]
>>> hexToBinary('0x5929567')
[1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1]

In the first iteration, we not only reversed the sequence, we also lost the trailing 0s. By chance, the number of affected digits was not an even multiple of either a byte or a nibble, so we transposed every remaining character by a bit shift operation before the sequence reached equilibrium.

If the goal really is to switch endianness, the easiest path I can see to doing so would be to use the bitstring import dependency already present in this projects' requirements.txt file. Assuming that public_key[j-1][0] is one of two coordinates we want to encode as a hex string using non-default endianness:

from bitstring import BitArray;

swapUtil = BitArray(public_key[j-1][0]);
swapUtil.byteswap(0)
altEndianHex = swapUtil.hex;

This shouldn't be hard to get implemented in a deterministically clear way once its understood what the contractually expected Witness input should be. I'm attaching a bit of code I extracted from the rest case and its utilities to help observe what was happening here.

Archive.zip

We need to build a consensus mechanism for More viable Roll_up so we can move the data availability guarantees off chain.

Meeting Time/Date: Thursday 18 October 2018 at 12:00 UTC

https://meet.jit.si/SlyMushroomsCommunicateFlatly

1. roll_up spec with data availbility on chain.
   • is the snark definition ready for implementation
   • is the contract definition ready for implementation
   • is the network layer definition ready for implementation
   • is the operator definition ready for implementation
   • are there any other things we need to spec out ?
2. recursive snarks road map.
3. trusted setup
4. Can we start building

Meeting Time/Date: Thursday 10 October 2018 at 12:00 UTC

https://meet.jit.si/SlyMushroomsCommunicateFlatly

1. Introductions
2. Final thoughts from peer review of https://ethresear.ch/t/roll-up-roll-back-snark-side-chain-17000-tps/3675
3. Transaction abstraction
4. Roadmap for POC2 (non fungible token), where POC3 would be a fungible token.
5. RSA accumulators
6. Notary for data availability

There are two modes of operation for the merkle tree:

1. Updates in-place
2. Nullify & append

The first approach proves the path and preimage of a leaf, then updates it with a new leaf.

The second approach keeps the 'discarded' items in the tree, and appends a new item along with a 'nullifier' that prevents double spends.

In order to maintain privacy (e.g. not revealing which item is changing hands) the merkle tree authentication path must remain secret. In the first approach you don't get privacy if you have to provide the tree paths to a third party to roll-up, it just provides transaction aggregation.

Lets say we use the first approach for roll_up, where updates to the database are authenticated by some criteria (proof of a preimage), the authentication path is verified, and a new leaf is provided, then the new root is calculated.

The problem is if you are performing multiple updates at the same time which share intermediate nodes, one would overwrite anothers root if calculated separately as the path for the next item (which shares a common ancestor) wouldn't have the updated values.

Anyway.... that means doing in-place updates where n-items > 2 is more complicated, but lets stay on track and just solve the replay protection problem.

Each leaf has a unique ID, say the serial number of absolute offset at the lowest level of the tree.

You must prove, using a signature (or other piece of private information) that you are authorised to modify that leaf.

There are a few formats for the leaf:

• leaf = H(pubkey)
• leaf = H(offset, pubkey)
• leaf = H(offset, nonce, pubkey)
• leaf = H(image)
• leaf = H(offset, image)
• leaf = H(offset, nonce, image)

The offset makes that leaf unique, e.g. if two public keys were used for different leafs, a signature for a public key that's used by multiple leaves could be used to modify multiple leaves. You would need to sign H(offset, new-owner) with the public key to provide a unique signature for that specific leaf to unlock it and transfer to a new owner.

But then there's the problem if the same public key is given ownership of the leaf again, its previous signature could be used to transfer it back to whomever had it before. So we use nonce as a sequence for that specific leaf to order a series of operations and prevent replays like that.

We can't use image as proof of the preimage would need to be distributed to the transaction aggregator... which means we have to use signatures.

All of the parameters for the leaf and transaction need to be signed, these are:

• offset
• nonce
• new-owner

So: SIGN(H(old_leaf, new-owner), secret-key) is provided with the authentication path and public key (assuming it can't be recovered from the signature).

The circuit for verification would be something like:

def transaction(offset, nonce, new_owner_pubkey, pubkey, signature, path, root):
    old_leaf = H(offset, nonce, pubkey)
    assert merkle_verify(old_leaf, path) == root
    assert signature_verify(H(old_leaf, new_owner_pubkey), signature)
    new_leaf = H(offset, nonce + 1, new_owner_pubkey)
    return merkle_update(old_leaf, new_leaf, path)

This introduces a new problem: From just the leaf hash and the offset you can't determine the nonce or the public key - this is data that needs to be available.

The data that needs to be available, after each modification to the root is the new values of:

• offset, nonce, new_owner_pubkey

Meeting Time/Date: Thursday 13 Sept 2018 at 12:00 UTC
Agenda:

1. Introductions
2. zknifty update
3. Requirements for zknifty to become good PoC example of an application using roll_up
4. How do we get to minimal viable roll_up?
5. How to provide data availability guarantees. See this (issue)[https://github.com/barryWhiteHat/roll_up/issues/6]
6. How to decrease proving times, aws , server tests. 
7. Discuss how to proceed with additional improvements to roll_up

Meeting Time/Date: Thursday 20 Sept 2018 at 12:00 UTC
https://meet.jit.si/SlyMushroomsCommunicateFlatly

1. Introductions

2. Updates from last meeting

3. Data avilibiilty inside the EVM possible approaches

4. Two options for data availability guarrentees outside the EVM;
   4.1 SNasma + priority que which means that in the happy case users don't have to watch the chain. So that seems like a candidate for POC approach. #15 (comment)
   4.2. Another IMO would be the most burned chain approach which removes the needs for exits even in the unhappy case we just have to wait for the attacker to run out of money. Tho that will work best in bigger chains with many tps. #7 (comment)

5. Data availability inside the EVM V data availability outside the EVM. Which is better for MVP ?

6. Finalize leaf format for zksnark. Are there any undecided decisions which are likely to fundamentally change the circuit and in-circuit leaf format?

6.1 Should we change the signature format. We may be able to add transaction abstraction here.

7. Should we add Replay protection at this layer. If so how?

8. Open requests
   8.1 someone to coord the meetings , take notes organize the issue.
   8.2 someone to record to meetings and put them online.

9. Any other things to talk about ?

So roll_up POC has data availbiltiy guarrentees inside the snark. But this kind of sucks and the best we can optimize this to is ~ 5000 gas per tx. Which limits our scaling. So now we want to provide data availability guarrenetees outside the EVM so that there is no gas cost per tx.

hello

The number of transactions collected by the coordinator is different when generate proof. So does it mean that the circuit is different every time. If my understand is correct, then how to get an common CRS preset.

https://github.com/barryWhiteHat/roll_up/blob/master/src/roll_up_wrapper.cpp#L89~L102
https://github.com/barryWhiteHat/roll_up/blob/master/src/roll_up_wrapper.cpp#L268~L271

The verify key is generated when generate proof every time. And the contract also use the key from the key file. Normally, should the key be hard-coded in the contract? The protocol will become interactive if there isn't an general CRS preset.

Thanks and wait for your response.

There was a model proposed, similar to Casper, where one validator is chosen to decide which transactions are included in a specific block, then the remaining validators confirm data availability for that block.

Approach 1

That process is:

• RNG selects 1 of N validators as the 'choose which transactions are included in the next block'
• That selected validator compiles all the transactions, puts them in a content-addressable block
• Publishes that block (and metadata) to the block-chain as its commitment
• Other validators confirm the data is available, is valid etc.
• Majority of validators sign the data, committing to the block
• Data availability happens?
• Prover watches for validator commitments, retrieves data and provides zkSNARK proof for that block
• Prover can only submit a proof which match the validators commitment to the new merkle root

Approach 2

What I'm proposing is the following:

• As each transaction is submitted by a user, the validators reach a consensus about which TX to include in the block next
• The user is provided with a receipt, signed by a majority of the validators, that their transaction will be item number N in the sequence.
• This receipt contains:
  • The merkle roots of every previous item in the block
  • Previous value
  • Previous merkle path
  • New value
  • This receipt shows the state transition from Merkle root N-1 to N
• Validators commit to a sequence of Merkle roots as being the next block, this sequence is published on-chain, along with the content addressable hash for the block
• Data availability happens?
• Prover can only submit proof where the sequence of transactions applied in-order result in the sequence of merkle roots previously committed to.

So, the interesting differences between the two approaches are that with the second the user gets a receipt for every transaction from the validator consensus, this essentially is finality on a tx-by-tx basis, the information included in this receipt verifies the order of every transaction so far in that block.

If the validators publish a different set of merkle roots on-chain, any user with a receipt signed by a majority of validators can prove that their transaction was excluded from the commitment.

Likewise any user, after receiving a signed receipt for their TX can, upon publishing of the validators commitment, verify that their transaction was not only included in that block, but was included in the agreed order.

This requires the validators to do the following:

• Agree on a sequence of transactions, one-at-a-time (e.g. a 'live consensus' providing instant finality)
• The majority of them provide signatures for each transaction
• Provide proof that they applied that specific transaction in-sequence
• Their own signatures can be used against them if they later commit to a different block content
• The prover also proves data availability, as the validators commit to not only the content of the raw content of the block (which must be proven in-circuit), but also the actions of each block being applied (via the merkle root updates)

More notes:

Philippe Castonguay @PhABC 21:09
tho I'd possibly increase it to RNG selects 50% of the validators deterministically to run the same algorithm and come up with the same result. and there must be a consensus with the remaining 50% that the data is consistent and available, or something like that.

That's hard because if using a p2p messaging framerwork, no validators will have the same set of txs.

HaRold @HarryR 21:09
ya it'd be a multi-round common-subset problem, which has way more edge cases
so maybe simpler is best, pick one validator to pick the TXs
the remaining provide proof of data availability?
there are so many edge cases though

Philippe Castonguay @PhABC 21:10
You make each validator provide a deterministically random entry in the tree as part of their signature

That's not bad, but I think that it's not sufficient. If you have a large amount of leaves, it's very likely you could have a few leaves that are unavailable and these would almost never be detected.

Imagine you have 2^32 leaves, you can predict what's the probability that a given leave will be picked for any given round, and know that you can make 1 leaf unavailable and it will take about 1 year before it has a good chance of it being selected. You have plenty of time to leave the validator pool for this.

HaRold @HarryR 21:12
nah, you can't make only one leaf unavailable, the entire block of TXs needs to be published in one block, content addressed
proof of ingesting that block is providing a proof of any leaf, as you must update the merkle tree to reach the same root
if any one transaction isn't processed by a validator the root won't be the same
so, the nominated validator, says 'I picked these TXs, the root is X, the content addressable block (IPFS, or BitTorrent) is Y'

Philippe Castonguay @PhABC 21:14
So, let's clarify something.

As a majority validator can make data unavailable for a few parties ;

Other validators
Users
Prover
Correct?

HaRold @HarryR 21:15
yes, with a majority they can pass the information internally and externally appear to be agreeing on the same information, even though it's unavailable to others

Philippe Castonguay @PhABC 21:16
The ultimate risk is the users not having the data, correct? If the prover doesn't have the data, they can't build a proof. If the majority of the validator dont have the data, they won't sign. In both cases, blocks can't be included. However, if data is unavailable to users, chain is still live, but users don't know what's happening.
Is this correct?

HaRold @HarryR 21:17
so by committing to the data in content-addressable form, you would require that the chosen validator to pick the TX pool was one of your insiders

Philippe Castonguay @PhABC 21:17
Yeah

HaRold @HarryR 21:18
which can either deny data (by passing internally), or scramble it to make it useless externally, but with a majority they can force it through as being the next block

Philippe Castonguay @PhABC 21:18
I'm asking, what happens when validators (majority) and prover collude, how can users challenge this and say "wait a second, we think the system is colluding against the users"

HaRold @HarryR 21:18
hmm

Philippe Castonguay @PhABC 21:19
So far, it seems like we are fine in terms of data availability unless majority of validators and prover collude. Wondering if we can get better with an extra, expensive step.
For instance, the silliest example would be to request validators to rebuild the tree on-chain directly, with all the leaves. If they can't, they get slashed. However, this seems crazy expensive
What i'm asking is ; What do validators have to risk by witholding data? How do they get penalized?

HaRold @HarryR 21:21
I was thinking about sequentially updating the merkle tree in-circuit, where each TX is applied in sequence, with a path and new value which generates a new root, this is required to be in-sequence and in-order
that's how the circuit has to work anyway
could you make the validators commit to the merkle root after each transaction is applied in-order?

Philippe Castonguay @PhABC 21:21
Right, but how many blocks and gas would that take and how can users resort to that option without griefing the validators?

HaRold @HarryR 21:24
so, instead of picking one validator to decide the TXs in the block, for each TX the validators (as a group) must come to a consensus about which TX will be accepted next, then provide a proof signed by all that says 'the merkle roots in sequence so far are this, your TX is this, the root after applying is this'. Where in order for the proof to be accepted it must provide the merkle roots in-sequence (so 1 per TX)
where, as a user, I have a signed commitment that my TX will be included at sequence number N, and all the merkle roots before that are X
then I can show that the validators committed to something which differed from what the prover prooved

Philippe Castonguay @PhABC 21:25
And do the prover pass this signed data on-chain?

HaRold @HarryR 21:26
ideally only a hash of it, a hash of the sequence of merkle roots, to keep it cheap (public inputs are expensive)

Philippe Castonguay @PhABC 21:26
Right, so they can still withold what creates that hash from the users, no?

HaRold @HarryR 21:26
but the validators could commit to a sequence of hashes, in order to commit to the next block
where if you provide an input, which is signed by the validators, for a specific item in the sequence, which doesn't match the preimage
then it's a certified validator fraud
so say the validator commitment phase they agree on sequence of TXs, a majority of validators signs each TX, in-order
each transaction the user submits will get a receipt, which specifies its order and validator signatures
if the validators don't include that in a block, the user can prove their signatures on-chain as proof that they didn't include their TX

Philippe Castonguay @PhABC 21:29
Let me rehash this a bit to be more precise ;

then provide a proof signed by all that says 'the merkle roots in sequence so far are this, your TX is this, the root after applying is this'.

You have such a signed message for each tx / user?

HaRold @HarryR 21:30
I want to avoid a signature for each TX, only a hash of the information for that TX (the leaf value, in-sequence merkle tree update info) - which is verified by the SNARK circuit and not on-chain
but, the validators provide the user a signature, so it's not necessary on-chain
that signature can be used against them on-chain when the validators submit the sequence of TX hashes as a commitment to the next block
in the window between the validators commitment and the next block, users can use the receipt they got from the validators to prove that the validator rescinded on their obligation to include the TX in the block
likewise, because the TX block is content addressable, you can (possibly very expensively) prove that your TX wasn't included in it, even though the validators signed proof that you were
where the block is N*16 bytes long for N transactions

Philippe Castonguay @PhABC 21:36
If the validators withold the data, can't they just not provide these signed commitment in the first place as well?

HaRold @HarryR 21:40
for them to agree to include a users TX, a majority of the validators have to provide the user with their signatures for that TX. so yes, a majority of them can not sign that specific users TX to censor them. but any user who is provided with a receipt has enough information to prove they were included in a specific block
which means, as long as the users hold on to their receipts, they have provable data availability
where any one of the receipts can prove the availability of the data for that one TX, and the block being mined by the prover where at least one receipt is provably a constituent of that block, then at least one person has data availability
hmm this is getting complicated
was thinking about censorship resistance, blind commitments, where you can prove that they excluded something after discovering what it was, but then it becomes a race between the TX submitter, the prover, and network congestion, for the proof to be valid

HaRold @HarryR 21:46
I will write up these notes anyway and dump them in a ticket

Philippe Castonguay @PhABC 21:52
Yeah, thanks Harry, will be good to summarize all this in a ticket.

Philippe Castonguay @PhABC 22:00
I think we will be able to make all this much simpler once ideas are summarized and written down

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

https://meet.jit.si/SlyMushroomsCommunicateFlatly

1. Introductions
2. Circuit implementer updates
3. Hash function in edDSA
4. Prover updates
   • Prover input format
5. Open issues, help wanted
6. Should we include nonce in EVM data availability https://hackmd.io/Sz3t1a4bRauXjhj1ZYzlBw#
   • EVM data availability considerations in multioperator model: nonces and signatures on chain
7. Use 2 byes for value in a floating point format. 12bits mantisa and 4bits exponent.

Proposal: for nullification checks, let's use a 253 bit unique immutable leaf id stored in the leaf instead of its address.

Rationale: it allows to split leaves in-circuit in such a way that allows efficient checks of nullification. This is important in the context of Plasma Debit.

How it works:

When a new leaf is inserted, its id equals its address (padded to 32 bits: bit 0x80000 must be set).

When we want to split it, two new leafs are created with ids appended by a single bit:

id(child 1) = id(parent)*2
id(child 2) = id(parent)*2 + 1

When the nullified status is checked in isLeafNullified(uint256 leaf_id), checks are required for all parent ids (max. 224 SLOAD operations):

var sub_leaf = leaf_id;
while(sub_leaf > 0x800000) { // until we reach prefix length
    checkNullifier(sub_leaf);
    sub_leaf /= 2; // shift one bit right
}

Having a long proving time can be a big problem for alot of use cases. So its possible to have a bonded prover who guarrentees a users transaction will get into block X.

1. The user creates a Tx to pay for Coffee.
2. The recipient of the TX want to make sure they will get paid. So they send the tx to the prover who hashes it with the block number they plan to insert it in.
3. If the proof is included everything is fine.
4. if the proof is not included the recipient can burn a prortion of the provers bond and recive a payment by providing the signautres of the prover to a smart contract which checks that number block to see if the quoated transaction was included.

We want to use ethsnarks gadgets wherever we can. This can be

1. The sha256 hash function
2. The eddsa signatures
3. #33
4. Switch the groth16 prover and verifiyer provided by ethsnarks.

No 1 is ready to be used but the other two are not. @HarryR please advise when they are.

So far we have talked about how to build a NFT with roll_up. Which boils down to basic read and writes.

Here i describe how to do efficiently do general dapps inside roll_up.

So far we have maintained a single merkle tree, which hold the user specific data. But we can add another tree that holds the app specific data. Which can only be updated by the snark according to rules defined in the snark.

So this should work and allow us to build basic applications. However they would be quite expensive to prove. This is because snarks are not good for general dapps with the following limitations

1. We cannot make loops
2. If we want to do an IF else we need to check the code inside the if and else loop in both execution paths. So it gets to be quite expensive. Tho there may be some nice ideas https://www.cs.virginia.edu/~sza4uq/index/geppetto.pdf for the if else case.

If we compare this to the EVM we notice that loops are used very rarely as they can be a problem if its impossible to complete loop execution inside the gasBlockLimit. Also in the EVM its rare to have a single master function that uses if loops to define the execution path. Most developers prefer to have a single function per task.

We can do the same with snarks where we have multiple functions defined by different snarks which should cut down the the repeated if code inside the snark. Where either the IF is true or the code fails. We need to think about consensus meacahisms that order which snarks get proved and in which order because there is a possibility of DOS attacks that disallow certain kinds of function calls. More discussion on that #7

It would be nice to mock up some simple examples inside this new paradigm and see if these ideas hold, if there is anything we have not considered.

Improve the cpp code similar to HarryR/ethsnarks#3 and run it on Enterprise hardware.

Seems like are limited to 20 million constraints on traditional hardware. See the introduction https://eprint.iacr.org/2018/691.pdf

This leaves us with 3 approaches

1. Improve cpp code so that it runs closer to 20 million constraints
2. use https://github.com/scipr-lab/dizk and try and push these proofs to the cloud. This would mean we can make proofs about billions of constraints.
3. improve the efficency of the underlieing snarks so that we have fewer constraints. Right now it is VERY in efficient.

Thanks for the code. Very helpful to understand the details. I have one question though:

In order to ensure this, we pass every updated leaf to the smart contract so that data will always be available.

Does the prover prove the correctness of these data? Are they taken into account when the contract verifies the snark?

1. Assume centralized operator model.
2. We have 'priority request queue' on chain. Operator is obliged to serve it.
3. If operator fails to serve a request for N blocks, then we have a proovable data unavailability event as operator's fault.
4. When and only when this event is triggered:
   4.1. Everyone is allowed to exit under the improved plasma rules described by @barryWhiteHat
   4.2. Anybody can object to stale claim, not only the owner.
   4.3. Opearator's security deposit is used to compensate gas and processing costs to everyone (it must be sufficient).
5. If the failure was purely technical, operator can resume service anytime.

In this scenario there is no need for anybody to watch the chain 24/7 until unhappy event happens. If it happens, it will become news soon, and a lot of people will run watching software for a while, allowing everyone to exit safely. Emergency expenses are kept to a minimum. Operator can in no way profit from failure.

Originally posted by @gluk64 in #15 (comment)

If we use so #18 then we don't have to do plasma exit we can safely roll back the chain.

Say we have a list of states.

s1 - > s2 -> s3 -> s4 -> s5 

Where we start at s1 and end at s5

at s1 data is available and s5 it is not. But we do not know when it became unavailable.
So tell everyone we are going to roll back the state from s5 to s4. Does anybody

1. Have a leaf that they want to withdraw at the state s5.
2. Does anyone want to add state and become the new operator at s5.

If we don't get anyone for s5 we withdraw anyone who asked and step the state back to s4 and repeat.

This way we start to go back in time and once an available state appears we will hopefully get a new operator. Or else we just withdraw everyone.

So we can recover without everyone having to move to a new chain. Only the inflight transactions that have their data available. Everyone else just waits for a new operator.

Originally posted by @barryWhiteHat in #18 (comment)

Example rollback mechanism

request exit

If the operator fails to process requests in the pritoirty que. We will begin to roll back the chain. Allowing users to exit and offering the position of operator in an open auction.

Firstly we pause the system for a long period of time to allow users to prepare their exit requests. A user can submit an exit request by calling
roll_back_exit(uint merkle_tree_address, uint state, bytes32[tree_depth] markle_proof, bytes32 leaf, bytes32 authorization_signature bytes32 public_key_of_leaf, bytes32 rhs_of_leaf )

1. The contract then validates these requests are valid as in "Example exit using the priority queue"
2. It confirms that that leaf has not been exited.
3. It confirms that that leaf is not already in the exit request. If it is it will use the request with the latest state.

bid to be operator

A user can request to be the new operator by calling

bid_new_operator( uint state, bytes32[tree_depth] markle_proof, bytes32 leaf )

They pass state which is the state that they want to start operating from aswell as a deposit.

They must also provide a valid proof of knoledge of the data that resulted in the previuos operator being slashed.

For each request we check weather the their state is newer than the current higest bid and that their bit is higher than the current highest bit. If either is true we add repalce the current highest bidder with them.

rolling back

Then we start to roll back the chain. We step back the state to the previous one. We then

1. Process all exit requests
2. Check if we have a new opeartor

We continue this until we either have a new operator or roll the state back to state zero.

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?

Meeting Time/Date: Thursday 18 October 2018 at 12:00 UTC

1. https://docs.google.com/spreadsheets/d/1DFrZJA23GQb0YkedUkobbuEZb3mXR4-btQjZACC0vAA/edit
   multi operator DOC (data on chain) (mDOC) Vrs single operator Nullifier on chain (NOC)
2. Good beginner issues
   https://meet.jit.si/SlyMushroomsCommunicateFlatly

I've tried to condense what I remember, along with my understanding so far, into a specification which contains the on-chain method signatures, their descriptions, some information about leaf verification etc. and generating circuit inputs etc.

View: https://hackmd.io/s/rJWBpmbFQ
Edit: https://hackmd.io/Vf0UGeuvR2mgApVS60VepQ

Meeting Time/Date: Thursday 21 December 2018 at 12:00 UTC

https://meet.jit.si/SlyMushroomsCommunicateFlatly

1. Updates
2. Length/Format of the Balance in the TX (floating point) and in the merkle tree (fix): Take a look at this spreadshit for varous options: https://docs.google.com/spreadsheets/d/1ouJaRJiNreVkkoVrl_ODPnAz0U9GSNUOrU50IypEyQg/edit?usp=sharing
3. Conditional payments
4. Fee payments
5. Signature standardization

Meeting Time/Date: Thursday 03 December 2018 at 12:00 UTC

https://meet.jit.si/SlyMushroomsCommunicateFlatly

• Updates
• Spec review
• Pedersen hash V MimiC
• Additions to the spec that are cheap and allow us to do other cool things. Like conditional payments.
• Plan for meeting Monday

trevor@prkap:/rollup/roll_up/build$ cmake .. & make
[1] 23780
make: *** No targets specified and no makefile found. Stop.
trevor@prkap:/rollup/roll_up/build$ -- Found PkgConfig: /usr/bin/pkg-config (found version "0.29.1")
-- Checking for module 'libprocps'
-- No package 'libprocps' found
CMake Error at /usr/share/cmake-3.10/Modules/FindPkgConfig.cmake:415 (message):
A required package was not found
Call Stack (most recent call first):
/usr/share/cmake-3.10/Modules/FindPkgConfig.cmake:593 (_pkg_check_modules_internal)
CMakeLists.txt:99 (pkg_check_modules)

-- Configuring incomplete, errors occurred!
See also "/home/trevor/rollup/roll_up/build/CMakeFiles/CMakeOutput.log".
See also "/home/trevor/rollup/roll_up/build/CMakeFiles/CMakeError.log".

I am using the README - I get this libprocps error. Do we need libprocps?

Due to #3 its quite expensive to add a public input to the snark. So we cannot provide data availability that way. We need to provide this some how in Minimal Viable Roll_up (MVR)

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 HarryR/ethsnarks#78 once it is ready. @HarryR can you advise when this is ready?

This should reduce the gas required for proving.

HarryR/ethsnarks#17

Proposal

Implement an account model with arbitrary-denominated balances and Plasma-Cash-like exit guarantees (originally proposed here).

Rationale

No sidechain solution has been proposed yet which doesn't require a fall-back on the normal Plasma exit (individual exits on the root chain) in the worst case. In such an exit scenario, the system must be designed to protect against an attack vector in which an operator attempts to exit with more money than they actually own, while withholding data in order to prevent others from challenging the illigitimate exits.

Plasma Cash offers such protection by having the value split into descrete leaves in the Merkle tree and only allowing to change the ownership of a leaf, but not its value. Each leaf can only be exited once, enforced by a requirement to publish a nullifier to a root chain contract, along with a proof of ownership at some state S. The current leaf owner can always cancel an attempted exit by publishing the proof of ownership at a later state S'.

Security of this scheme is based on the following idea: current money owners affected by a attempted attack by previous owners of this money always posses succint data sufficient to easily detect and stop the attack. It's difficult to adapt this scheme to the arbitrary denominated accounts, because with arbitrary money flows everyone quickly becomes dependent on everybody's else previous account states.

Plasma Debit solves this problem, but it comes at a cost of additional capital requirement on the operator side.

The Idea

• Each leaf in the Merkle tree represents a value.
• Creating new leafs requires locking additional capital into the sidechain contract.
• The ownership of the value is split between the leaf owner and the operator in some proportion.
• Leaves can change owners.
• A transfer of value V to a leave in which operator ownes more value than V can be performed without locking extra capital.
• In case of the Plasma exit, the value is split on the root chain between the operator and the owner.
• Plasma exit is governed by the Plasma Cash rules (single exit per leaf, challenge period, etc.).

Optimizations

To minimize extra capital requirements and equip the operator with a lot of flexibility, we can introduce a few simple optimizations.

Top-ups

The value of a leaf can always be increased by the operator (a top-up). It is safe to increase the value, because if somebody exits the leaf at an earlier state, they can only steal less than the full value locked for this leaf.

Top-ups, like new leafs, require locking additional capital.

In-Circuit Capital Locks: Non-Exitable Operator Balanace Leaf

Creating new leaves or topping-up existing ones requires locking additional captial. To avoid the need to do this on the root chain for every leaf, we can introduce special non-exitable leaf for operator balance. An operator can lock funds into this leaf on chain once and use it later to create or top-up multiple other leafs in-circuit.

The value of this leaf can safely be decreased because it will never be exited.

We could create such leaves for other users too, not only for the operator. But this requires absolute trust in the operator from these users, because in case of data unavailability non-exitable leaves can not be recovered.

Leaf Splitting

We can introduce a 253 bit leaf-id, which will allow splitting the leaves in two up to 221 times with small nullifier check overhead on chain.

For example, if an operator holds 50% of the leaf with 8 tokens, it can be split into 2 leaves of 4 tokens each, one owned entirely by the original owner and the other one assigned to a new owner.

The benefit of leaf-splitting is that it doesn't require additional capital.

Atomic Swaps

If owners of two leaves cooperate with the operator, they can atomically swap ownership of their leaves. Operator can use it for defragmenting undercapitalized leaves.

Leaf Data Model

We can have several different Merkle trees for records with different update frequency:

Accounts (height: 24):

• owner_pub_key (253 bit)

Leaf_IDs (height: 32):

• id (253 bit)

Values (shares structure with Lead_IDs tree):

• account (24 bit): reference to the Accounts tree
• balance (32 bit)
• balance_operator (32 bit)
• nonce (16 bit)

Maybe it's better to merge Leaf_IDs and Values into one tree.

Operations

Onchain

tbd

In-Circuit

tbd

Meeting Time/Date: Thursday 6 December 2018 at 12:00 UTC

https://meet.jit.si/SlyMushroomsCommunicateFlatly

1. Introductions
2. Circuit implementer updates
3. Fees
4. Spec review
5. Formal verification update
6. FAQ

Meeting Time/Date: Thursday 14 January 2018 at 12:00 UTC

https://meet.jit.si/SlyMushroomsCommunicateFlatly

When noTx > 11 then the smart contract fails verification

libsnark still says the proof is correct.