zkevm-specs
zkevm-specs copied to clipboard
privacy-scaling-explorations
Spec for opcode `SAR`
Circuit: https://github.com/privacy-scaling-explorations/zkevm-circuits/pull/727
@LuozhuZhang could you make a textual description about the strategy and the constraints used to build this gadget, please? It will help a lot to do a review!
@LuozhuZhang What's the status of this PR? Is there any blocker?
No. I was working on other things before, now to work on this spec :D
Very nice job I have to say. It's not an easy opcode and the spec looks really solid. Just have some questions and nits. But looking great so far! :)
Thank you! Very interesting work. I will make some changes based on your review
@LuozhuZhang could you make a textual description about the strategy and the constraints used to build this gadget, please? It will help a lot to do a review!
Received, I will add text description
@LuozhuZhang could you make a textual description about the strategy and the constraints used to build this gadget, please? It will help a lot to do a review!
Received, I will add text description
Hey, @LuozhuZhang finally had you time to add a text description?
@LuozhuZhang could you make a textual description about the strategy and the constraints used to build this gadget, please? It will help a lot to do a review!
Received, I will add text description
Hey, @LuozhuZhang finally had you time to add a text description?
Sorry for the delayed reply. Could you give me an example of text description, it will be helpful. Thanks!
@LuozhuZhang could you make a textual description about the strategy and the constraints used to build this gadget, please? It will help a lot to do a review!
Received, I will add text description
Hey, @LuozhuZhang finally had you time to add a text description?
Sorry for the delayed reply. Could you give me an example of text description, it will be helpful. Thanks!
Oh, I would say that Rohit's EXP explanation of constrains (https://github.com/privacy-scaling-explorations/zkevm-specs/blob/master/specs/exp-proof.md) it's fantastic, as a reference.
@LuozhuZhang could you make a textual description about the strategy and the constraints used to build this gadget, please? It will help a lot to do a review!
Received, I will add text description
Hey, @LuozhuZhang finally had you time to add a text description?
Sorry for the delayed reply. Could you give me an example of text description, it will be helpful. Thanks!
Oh, I would say that Rohit's EXP explanation of constrains (https://github.com/privacy-scaling-explorations/zkevm-specs/blob/master/specs/exp-proof.md) it's fantastic, as a reference.
Yes, we have this text description :D (https://github.com/scroll-tech/zkevm-specs/blob/feat/opcode-sar/specs/opcode/1dSAR.md) Which part of the content do you think needs to be more precise?
@LuozhuZhang could you make a textual description about the strategy and the constraints used to build this gadget, please? It will help a lot to do a review!
Received, I will add text description
Hey, @LuozhuZhang finally had you time to add a text description?
Sorry for the delayed reply. Could you give me an example of text description, it will be helpful. Thanks!
Oh, I would say that Rohit's EXP explanation of constrains (https://github.com/privacy-scaling-explorations/zkevm-specs/blob/master/specs/exp-proof.md) it's fantastic, as a reference.
Yes, we have this text description :D (https://github.com/scroll-tech/zkevm-specs/blob/feat/opcode-sar/specs/opcode/1dSAR.md) Which part of the content do you think needs to be more precise?
Sorry, I've been busy with other stuff. If you can explain the b64s[x], it will be great!
Thanks, @adria0
I am working on some other things recently, I will add the text description of b64s[x] later
After discussing with @LuozhuZhang , I will try to update this PR based on previous @LuozhuZhang 's great fixes.
Hi @CPerezz and @adria0, I try to refactor and update code according to your code review.
And added description for calculating b64s in Markdown doc as below (and also update other parts in Markdown doc).
Could you help review again when you have time? No hurry. I will try to update the circuit PR. Thanks.
Special case (shift < 64)
The following figure illustrates how SAR opcode works under the case of shift < 64.
+-------------------------------+-------------------------------+-----
|a0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| ...
+-------------------------------+-------------------------------+-----
| a64s[0] | a64s[1] | ...
+------------+------------------+------------+------------------+-----
| a64s_lo[0] | a64s_hi[0] | a64s_lo[1] | a64s_hi[1] | ...
+------------+------------------+------------+------------------+-----
| b64s[0] | b64s[1]
+-------------------------------+------------------------
First we could define below constants for calculating b64s.
MAX_U64 = 2**64 - 1
is_neg = is_neg(a)
shf_div64 = shift // 64
shf_mod64 = shift % 64
p_lo = 1 << shf_mod64
p_hi = 1 << (64 - shf_mod64)
# The top new bits are set to 1 if `a` is negative, otherwise set to 0.
p_top = is_neg * (MAX_U64 - p_hi + 1))
a64s = word_to_64s(a)
a64s_lo[idx] = a64s[idx] % p_lo
a64s_hi[idx] = a64s[idx] / p_lo
Under this special case of shift < 64, b64s could be calculated as:
b64s[0] = a64s_hi[0] + a64s_lo[1] * p_hi
b64s[1] = a64s_hi[1] + a64s_lo[2] * p_hi
b64s[2] = a64s_hi[2] + a64s_lo[3] * p_hi
b64s[3] = a64s_hi[3] + p_top
Also updated the circuit PR https://github.com/privacy-scaling-explorations/zkevm-circuits/pull/727 according to this spec code.
Should we re-use the
MulAddWordsgadget to constrain theSARopcode, similar toSHLandSAR?
After discussing with @icemelon , it seems to be simple and clear to implement SAR with MulAddWords. Will create a new branch and give a try. Thanks.