foonetic / agnostic-orderbook

Asset agnostic orderbook

Orderbook program which can be used with generic assets.

Overview

This program is intended to be called upon by other programs that implement specific on-chain orderbooks. These "caller" program can use the agnostic orderbook as an underlying infrastructure.

Documentation

Run cargo doc --open in the program directory to open detailed API documentation.

agnostic-orderbook's Issues

investigate `const generics` for `EventQueue` and `Slab`

Currently both the event queue and bid/ask critbits hold opaque buffer ([u8]) and a lot of manual fudging with bytes. It's difficult to understand and error-prone.

Rust introduced a feature const generics which I have not really used, but I think may be able to help us. Briefly:

struct ArrayPair<T, const N: usize> {
    left: [T; N]
}

We know N is bounded, given Solana's limits on BPF memory usage - given N we can also express transformations like N-1

Specifically if we can work with [Event; N] instead of [u8] (and have Anchor code-gen the zero-copy serde, types of next_account_info, etc.) I think this could greatly help both the understandability and correctness of the API.

different trees and matching engines

@jarry-xiao had a good suggestion in Slack:

I was thinking we could have different trees and different matching_engines that we test against

we could design a trait in the AOB's API - refactoring both the program and library (data structure) crate to use the interface instead

(current program is fifo critbit)

remove usages of `.unwrap()`

The existing AOB uses .unwrap() in various places it should probably return a Result.

Downsides of unwrap:

• you get runtime panic message that can easily get lost in program logs
• this can lead to a very confusing client / caller experience if something panics
• it's not at all unsafe to .unwrap() / panic, just arguably poor API design and Rust anti-pattern. instead, it's idiomatic to reify errors (i.e. use Result)
  • i think this especially holds for on-chain programming where it's a "shared" runtime environment (compared to a local Python stack trace)

The exception to above is if you can prove an invariant about the code path: "if I have reached this block of code, the Option cannot be empty", and for whatever reason it's too verbose / annoying / impractical to actually do that in the type system. Such scenarios probably warrant a comment "why this cannot panic".

On the flip side, ? makes it very tempting to just make everything return Result, but I'd argue it's best to push Result as much to the edge of programs as possible and think carefully about what is fallible and what isn't.

https://blog.burntsushi.net/rust-error-handling/

consider refactoring to Anchor

I'd like to propose we consider refactoring the AOB on-chain program to use Anchor:

• AOB already sort of uses it's own Anchor-esque macro generation (see bonfida_utils::InstructionAccount)
  • But it doesn't actually "give you types", as everything is still just an AccountInfo and you have to manually impl how to parse the accounts_iter
• A few benefits of Anchor
  • "Real types" when passing around accounts
  • Declarative specification of PDAs, account initialization, checks, etc. (separate from orderbook processor logic)
  • IDL (makes writing JS clients a lot easier and less boilerplatey)
  • Toolchain (anchor test is quite a nice experience, feels just like browser hot-reloading)
  • Eliminate a lot of boilerplate and reduce size of the codebase

Downside is Anchor will require use to think about the discriminant when writing client code that does not use Anchor's built-in client. And as with any refactor we will have to test to make sure it didn't break anything (but the test coverage and usage is arguably not that great to begin with)

Please comment, especially if you don't think this is a good idea

publish on `crates.io`

replace this once done: https://github.com/foonetic/dex-v4/blob/main/program/Cargo.toml#L22

zero-copy the headers

zero-copy the SlabHeader and EventQueueHeader. this is actually quite gnarly and requires:

• changing the buffer to hold only the non-event queue header
• refactoring away the Rc<RefMut> stuff (not sure if it's possible to pointer cast otherwise)
• zero-copy deserialization of the above
  • probably requires a manual combo of array_refs! and raw pointer casts (because bytemuck doesn't support DST)
  • serum-dex has a good example of how to do this for their own Queue
• updating the manually-defined schema in eventQueue.ts (for our Anchor JS client / integration tests)

improve CI

it'd be nice if we had the Solana toolchain (+Anchor toolchain?) on the CI runners, so that test-bpf, anchor test could all run as part of checks

SPL and Anchor repos look like good starting points:
https://github.com/solana-labs/solana-program-library/blob/master/.github/workflows/pull-request-token.yml
https://github.com/project-serum/anchor/blob/master/.github/actions/setup-ts/action.yaml

Organize code as a workspace with separate lib and bin

• Allow the lib dependencies to float with downstream users like dex-v4.
• Pin the bin dependencies so that the on-chain program deployment is reproducible.

better errors

Anchor's latest release (0.22) introduces some very handy new features and ergonomics for error handling. we can leverage them in the AOB now that it's using Anchor

test coverage and profiling

currently landscape is some minimal tests:

• functional.rs (from upstream) is the existing solana-program-test (BanksClient)
  • it's rather minimal: creates 1 bid, 1 ask, 1 cancel then checks the event queue
• integration.rs is the same test, programmatically standing up the solana-test-validator
  • more "e2e" than above but still equally minimal at testing logic

tasks:

• add more orderbook tests for more higher volume / nefarious scenarios
• property-based tests for verifying orderbook invariants (e.g. n bids, n asks at same price, size = 10 fills)
  • simulate_operations in critbit.rs already does something like this: generate n random tree instructions, it should match the output of BTreeMap
• performance tests / profiling (e.g. what are the perf characteristics of various data structures wrt compute units, how much does 1000 new orders cost in compute, 1000 cancels, etc.)