Add `FixedSizeBinary` with support up to at least 32 bytes.

[JayWhite2357]

Background and Motivation

Many data are binary blobs. In particular, the EVM address and hash types are 20 bytes and 32 bytes respectively. We should support these natively within Proof of SQL. See https://docs.rs/arrow/latest/arrow/datatypes/enum.DataType.html#variant.FixedSizeBinary.

Changes Requested

Add full support for a FixedSizeBinary type. In order to do this there are several considerations.

• Since Scalar types support naturally embedding 31 bytes but not 32 bytes, there should be a divergence in how <=31 bytes are handled and 32 bytes are handled.
  • 31 bytes and under should be naturally embedded into the Scalar type. This means simply relying on the conversion from [u64; 4] to the Scalar.
  • 32 bytes should be handled by first hashing the data and then converting it to a Scalar. This is identical to how Strings are handled. See https://github.com/spaceandtimelabs/sxt-proof-of-sql/blob/48b2f0bc8b92dbc3ef9deecfdfc04dfbc2b4460c/crates/proof-of-sql/src/base/scalar/mont_scalar_from.rs#L16.
• ColumnType should probably have a new variant FixedSizeBinary(i32) added. It is not as clear what the variant for Column and OwnedColumn should be.
  • My initial suggestion would be FixedSizeBinary(i32, &'a [u8]) and FixedSizeBinary(i32, Vec<u8>) respectively, but that may not make sense. The reason for this suggestion is because something like Vec<Vec<u8>> has a lot of overhead, and Vec<[u8]> is not allowed by Rust.
  • Alternatively, it may make sense to have two variants: one for the <=31 bytes case, and one for the 32 bytes case. In this case, it may make sense to have the latter simply be Binary instead of FixedSizeBinary.

• 228 is partially motivated by this issue, and may make this issue a bit more ergonomic. However, working on them in parallel will likely lead to some branch conflict, so pay attention to that issue.

• The only expression that needs to be supported is equality (=) and inequality (!=). This is because there is no way to add, subtract, etc. between binary data. Eventually, we may wish to add bitwise operations, but those are beyond the scope of this issue.
• It is not clear what the best way to handle binary literals is. We strive to adhere to PostgreSQL syntax, but this data type is unsupported in PostgreSQL. See https://www.postgresql.org/docs/current/datatype-binary.html. There is some flexibility here, but there should be agreement on this before this particular implementation is done.

[JayWhite2357]

/bounty $1000

[algora-pbc[bot]]

💎 $1,000 bounty • Space and Time

Steps to solve:

1. Start working: (Optional) Comment /attempt #229 with your implementation plan. Note: we will only assign an issue if you include an implementation plan with a time estimate. Additionally, to be assigned an issue, you must have previously contributed to the project. You can still work on an issue and submit a PR without being assigned.
2. Submit work: Create a pull request including /claim #229 in the PR body to claim the bounty
3. Receive payment: 100% of the bounty is received 2-5 days post-reward. Make sure you are eligible for payouts

Thank you for contributing to spaceandtimelabs/sxt-proof-of-sql!

Add a bounty • Share on socials

Attempt	Started (GMT+0)	Solution
🟢 @Ashu999	Oct 7, 2024, 10:45:20 AM	WIP

[Ashu999]

/attempt #229

Algora profile	Completed bounties	Tech	Active attempts	Options
@Ashu999	1 bounty from 1 project	JavaScript, Python, TypeScript		Cancel attempt

[tareknaser]

Hello @JayWhite2357

I’d be happy to take on this issue. I think it could be broken down into multiple PRs for smaller, easier-to-test patches. Let me know if that works for you, or if you’d prefer to handle it all in one go.

I’ve just joined the Discord and would be happy to discuss it further.

[JayWhite2357]

@tareknaser I agree that this makes sense to be broken into smaller PRs. We much prefer smaller PRs over large PRs.

[JayWhite2357]

It looks like there are multiple people working on this issue. It may be wise for you to coordinate via Discord. In the case where there are multiple PRs that get merged from different contributors completing the issue, I will split the bounty according to my best judgement. (Unless the contributors have already agreed on a split.) Alternatively, someone can break this into smaller issues, and I can assign smaller bounties to each.

[tareknaser]

It’s a bit tricky to break the issue into clear pieces right now. I think it’ll become clearer once we begin the actual implementation. I can start with a small PR to implement FixedSizeBinary to set the stage for follow-up PRs. During the PR review, we can probably get a better sense of how to proceed.

Would that be okay with you, @Ashu999 ?

[Ashu999]

sure, go ahead @tareknaser