Monthly Update: October 2022

Monthly Update: October 2022

image

Staffing

Orbis Labs has a team of 13 engineers, mathematicians, and researchers. These people break down by focus and areas of expertise as follows:

Main focus on Orbis:

  • zk-SNARK engineers - 6
  • Protocol engineers - 3
  • Compiler and emulator engineers - 2
  • Devsecops - 1

Areas of expertise relevant to Orbis:

  • Haskell - 12
  • Math - 7
  • Cryptography - 1
  • Rust - 2
  • Formal verification - 2
  • Cardano - 6
  • Decentralized protocol engineering - 3
  • Embedded systems - 1
  • Mathematical logic - 1

Work done so far

Orbis Labs has performed thousands of hours of research and development, resulting in hundreds of pages of research and tens of thousands of lines of code.

This research and development breaks down into three key areas: zk-SNARKs, the Orbis protocol, and compilers and emulators. Here is what has been done in each of these areas:

  • zk-SNARKS:
    • Developing a universal TinyRAM circuit for creating zk-SNARKs verifying the results of smart contract executions(about 90% done)
      • Note: substantial progress has been made in the past month, but the estimated percent done has not increased in the past month, due to inexacitude in sizing
    • Modified Halo 2 to support lookup tables using advice and instance columns
    • Defined a formal circuit specification language (OSL)
    • Defined a spec of the (non-recursive) circuit for verifying Orbis rollups
    • Defined a process for compiling OSL specs into circuits
      • Recently performed theoretical simplifications and performance optimizations on this process, as described here
    • Developed a compiler from OSL to 𝚺11 formulas, without formal verification(done, except for optimization passes)
    • Developing a compiler from 𝚺11 formulas to arithmetic circuits, without formal verification (about 40% done)
      • Remaining work is mainly on optimization passes and witness generation
      • Risk factor: uncertainty about what optimization passes are needed
    • Developing a formally verified 𝚺11 formula to circuit compiler
      • Percent done is inestimable due to additional scope we identified including an inestimable amount of effort on optimization passes
    • Defined a strategy and API for off-chain recursive proof composition
    • Defined an approach for on-chain proof verification and began implementing it(about 60% done)
    • Modifying Halo 2 to use a FRI PCS instead of its IPA PCS(about 75% done)
    • Defined a theory of interaction combinator arithmetization which may be useful for more efficient proving of Plutus script executions
  • Protocol:
    • Designing the layer 1 protocol(about 80% done)
    • Prototyping the layer 1 contract(more than 50% done)
    • Designed the centralized layer 2 protocol
    • Designing the decentralized layer 2 protocol(less than 10% done)
    • Implementing the prover node(about 40% done)
  • Compilers and emulators:
    • Developing an LLVM backend for TinyRAM(about 80% done, now blocked on the zk-SNARKS team)
    • Developed a TinyRAM emulator in Haskell
    • Developed a formally verified TinyRAM emulator in Coq
    • Developing an Untyped Plutus Core (UPLC) to C compiler (in testing phase)
    • Developed glue code for running Plutus validator scripts on TinyRAM
  • Infrastructure & SDK:
    • Decided on architecture for E2E tests, in the process of implementation
  • Miya (next generation ZKPs):
    • Researching Combinatorial Proof arithmetization, for *universal* succinct zero knowledge proofs of statements in full first-order logic
    • Researching grand sum arguments based on the logarithmic derivative for efficient permutation and lookup arguments
    • Researching PCPs over cayley complexes

Links to work:

Note: the Orbis L1 contract and prover node are closed source for the time being. They will be open source at a later date.

Roadmap

Overall estimates of the state of completion of the design and implementation effort required to release Orbis V1, the ratio (effort expended / (effort expended + effort remaining)), broken down by area and expressed as percentages:

  • zk-SNARKS: 55%
  • Protocol: 56%
  • Compilers and emulators: 90%
  • SDK: 0%

The roadmap calls for releasing Orbis V1 on a testnet in Q2 2023. The project is currently on track to release on this timeline. It is a possibility that we will release Orbis on a testnet in Q1 2023.

Posts

Footer Links