Byte packing

[eerkaijun]

Context (Problem, Motivation, Solution)

Constraint number is very large with merkle tree approach. This PR changes all zk circuits design, where each card is only one byte, and thus each uint256 would be able to hold 32 cards. The committed root is now a hash of these elements together with the salt of the user. https://github.com/norswap/0xFable/issues/50

Describe Your Changes

Remove all merkle related circuits and change them to byte packing. Also fix the bug where lastIndex is assumed as the last card of the deck.

Checklist

• [x] I have performed a self-review of my code
• [x] I ran make lint and fixed resulting issues
• [x] I ran the relevant tests and they all pass
• [x] I wrote tests for my new features, or added regression tests for the bug I fixed

Testing

Have updated the corresponding tests.

[eerkaijun]

This PR is NOT ready yet, as I've not updated the tests and contracts. But thought it would be nice for everyone to see the new circuits in the meantime. The byte packing approach is indeed a good approach, as now all three circuits have constraints only around 20k (compared to 200k for the previous DrawHand circuit, which is 10 fold better!).

(Edit: It's now ready!)

[eerkaijun]

As discussed in chat, currently some of the field elements will be larger than circom prime field element, which makes it incorrect after being modulo-ed. I think using 0 as the null value, since it's used to pad the array and thus appears the most. What was the reason for not using 0 as null previously? I remembered you mentioned it before but I couldn't recall.

[norswap]

Regarding the issue of 64 cards not fitting in the Circom prime (which is between 2^253 and 2^254, meaning the 3 higher-orde bits are unusable and MUST be 0 for the packing/unpacking logic to succeed):

• We should change the empty item to 0.
  • No real reason it wasn't that except that cards are laid out in a solidity array that starts at 0. But very easy to start indexing at 1 instead.
• We should parameterize the packing/unpacking template with the number of cards we want, and then we can create a new template for unpacking decks & hands that calls this three times (e.g with parameters, 30, 30, 4).
  • OR we simply further restrict the size of decks to 62 items, and we pack 31 cards per felt.

[eerkaijun]

Actually just realized that we can keep the null value as 255, as long as each felt only encodes 31 cards instead of 32 cards. As long as we leave the most significant bytes as 0, then it won't hit the circom prime field. I think the cleanest way is perhaps to standardize each felt to encode 31 cards, and the max deck size can be anything and we'll just use the corresponding number of felts needed. For example, if max deck size is 64, then we need 3 felts (31, 31, 2).

Have also updated the packing and unpacking of cards array to directly use your Num2Bytes template, that's pretty clean so thanks! There's some slight performance improvement but not too much (you could check out the last commit to see constraints improvement).

[norswap]

Actually just realized that we can keep the null value as 255, as long as each felt only encodes 31 cards instead of 32 cards. As long as we leave the most significant bytes as 0, then it won't hit the circom prime field. I think the cleanest way is perhaps to standardize each felt to encode 31 cards, and the max deck size can be anything and we'll just use the corresponding number of felts needed. For example, if max deck size is 64, then we need 3 felts (31, 31, 2).

Is this possible with a fixed-size circuit though? Feels like you need to know the number of felts in advance.

[eerkaijun]

Fixed size circuit as in?

[norswap]

Fixed size circuit as in?

Just any circuit, since they all have to be fixed size (fixed number of constraints, which as I understand translates to loops that have a fixed number of iterations (known at compile time). So we (0xFable devs) would still have to pick a maximum deck size that would apply to everyone.e.

[eerkaijun]

Fixed size circuit as in?

Just any circuit, since they all have to be fixed size (fixed number of constraints, which as I understand translates to loops that have a fixed number of iterations (known at compile time). So we (0xFable devs) would still have to pick a maximum deck size that would apply to everyone.

Yes, we would have to pick a max deck size. With that, we would then know the number of felts needed, which would be our compile time constant.

I have switched the bytes packing to be little endian, and made sure tests passed. This PR should be ready to go :) Let me know if any feedback!

[norswap]

Fantastic work! 🚀🚀