Cannot verify orderbook checksums

MaxFangX commented 3 years ago

I am struggling to implement orderbook checksums. As messages are expected to be dropped it is quite important that this function works, so the user knows when to query FTX for a fresh order book snapshot. My current progress is in #22

Resources

FTX documentation on calculating the checksums
FTX-provided Python example client code
ws::tests::order_book_checksum
ws::tests::order_book

What I've confirmed:

The data returned from the API should be interpreted as an unsigned integer u32 despite their documentation calling the checksum a "signed 32-bit integer". u32 is also the output of hasher.finalize()
Number of bids and asks added to the crc32 input is correct
The crc32 input is formatted in the correct order, with the correct number of : separators, with no : at the beginning or the end. The crc32 input looks like

37741:2.0959:37748:0.0500:37740:2.7650:37749:0.1303:37738:3.4262:37750:0.0873:37737:7.4173:37751:0.2960:37735:1.3957:37752:1.8759:37734:0.5218:37754:1.4942:37733:0.9042:37755:0.0325:37732:1.4596:37756:1.6405:37731:0.3473:37757:0.4998:37730:1.1107:37758:1.0184:37729:1.0956:37759:1.3816:37728:0.6690:37760:2.5531:37727:2.0849:37761:0.0108:37726:2.4043:37762:1.6603:37725:0.7519:37763:2.4172:37724:0.9825:37764:1.1406:37723:1.6561:37765:0.2937:37722:1.2277:37766:1.3033 ... 37613:0.1000:37862:0.0073:37612:0.1329:37864:0.5927

What is uncertain:

The exact format of the input to the crc32 value returned by the API, including the number of decimal places to include in order prices and quantities.

Testing their code using Python

Consider the simple order book

bids = [[4, 5], [3, 10], [2, 15]]
asks = [[5, 20], [6, 30], [7, 40]]
orderbook = { 'asks': asks, 'bids': bids }

According to their docs, the crc32 input should be: 4:5:5:20:3:10:6:30:2:15:7:40, the crc32 of which is 640057369

However, when you run their example code:

checksum_data = [':'.join([f'{float(order[0])}:{float(order[1])}' for order in (bid, offer) if order])
    for (bid, offer) in zip_longest(orderbook['bids'][:100], orderbook['asks'][:100])]
computed_result = int(zlib.crc32(':'.join(checksum_data).encode()))

Their crc input to zlib.crc32 is 4.0:5.0:5.0:20.0:3.0:10.0:6.0:30.0:2.0:15.0:7.0:40.0, and the crc32 of that is 3640375499. Even the example in their documentation is 5005.5:10:5001.0:6:4995.0:5, which has no 0s appended to the quantities.

Computing checksums for the simple order book succeeds

Based on this simplified order book data, I can compute a correct crc32 value within verify_checksum for either 4:5:5:20:3:10:6:30:2:15:7:40 or 4.0:5.0:5.0:20.0:3.0:10.0:6.0:30.0:2.0:15.0:7.0:40.0 by changing the string formatting to:

input.push(format!("{}:{}", b.0, b.1)); to yield 640057369
input.push(format!("{:.1}:{:.1}", b.0, b.1)); to yield 3640375499 by padding .0 into the prices and quantities.

These changes allow the ws::tests::order_book_checksum test to pass, and rule out bugs in the separation and ordering of the bids and asks.

Computing checksums for real order book data fails

However, when I try to verify the checksum on real data in the ws::tests::order_book test, the test fails. For example, BTC-PERP has integer prices (0 decimal places), and quantities to four decimal places. None of the following worked:

input.push(format!("{}:{}", b.0, b.1));
input.push(format!("{}:{:.4}", b.0, b.1)); (equivalent to the previous one)
input.push(format!("{:.1}:{:.4}", b.0, b.1));
input.push(format!("{:.1}:{:.1}", b.0, b.1));
input.push(format!("{:.4}:{:.4}", b.0, b.1));

At this point, I don't know what to try next. Any help or suggestions would be greatly appreciated.

fabianboesiger commented 3 years ago

Thanks for the detailed overview. I'll look into it if I have some time available.

Maybe we can look at how checksums are computed in already existing libraries?

MaxFangX commented 3 years ago

Amazing, that helped me solve it. I looked at every repo on Github that surfaced with the search "ftx". Only about 6 had websockets implementations, and only one had implemented the checksum feature aside from the official Python example code. It's written in OCaml (!):

https://github.com/vbmithr/ocaml-ftx/blob/master/src/ftx_ws.ml#L121

Looks like they used the price or quantity float directly, but appended a 0 at the end if it was a whole number float, so e.g. 38000. in OCaml syntax becomes 38000.0.

I just tried input.push(format!("{:.1}:{}", b.0, b.1)); (the one variant I didn't try yesterday) for BTC-PERP (which has whole number prices) and the ws::tests::order_book test passed 🎉.

I should be able to write the code that detects whole number floats so the checksum verification generalizes to other markets, and do the full cleanup and PR later today.

fabianboesiger / ftx