Roll Up Meeting 10 Agenda

[barryWhiteHat]

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.

[HarryR]

Four potential optimisations:

1. 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.
2. 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.
3. 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.
4. Jordi's optimisation for Pedersen Hash multiplication, using a bigger lookup table with the same properties as the 2bit signed lookup table.

Impact:

1. reduces signature verification cost by 50%
2. reduces signature verification cost by 99% (ish)
3. reduces merkle path verification cost by 30-40% (depends on size of batch)
4. reduce signature verification by ~20%

Overall... 2x-5x potential improvement

Also - specification freeze?

[HarryR]

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?

[barryWhiteHat]

Notes:

• Agreed to freeze features/complex optimizations in the spec.
• Talked about some signatures encryption security.
• Jordi taked about sparse merkle trees