Repository navigation
Elements: parity bit of confidential asset/amount points uses Elements' square-y encoding, but decompress treats it as odd-y #349
Description
Activity
So, despite the naming, only
decompresshere is actually "wrong". (And it's wrong in the sense that it's the wrong jet for the job.) Every other function just copies the bit around as a bit without interpreting it. It's true that for CT objects this bit has a different meaning than it does for signature objects.In SimplicityHL we should use the type system to distinguish between "CT points" and "normal points" so we can somewhat disable this footgun.
Meanwhile lemme see if there's another jet rather than
decompresswe can use here.Reacted by Yevhenii Sekhin....no, there is not. In fact
ge_set_xquaddoes not occur anywhere in libsimplicity. So this was a pretty big oversight on our part. Nor do any of the modinv functions that might give us a Jacobi symbol which would let us efficiently patch the point after-the-fact.Both
decompressandpoint_verify_1read compressed points and interpret the bit as even/odd (and have no "alternate form" that reads it as a xquad bit), so these two jets specifically cannot be used with CT points. AFAICT no other jets have this issue; they mostly read uncompressed points.The difference between the two methods is that
- for even/odd, we interpret the bit as "derive the y coordinate, then flip it so its parity matches the parity of the bit"
- for xquad, we interpret the bit as "derive the y coordinate, then flip it if the bit is set"
Unfortunately after calling
decompressthere isn't a way to tell "after the fact" whether the flip was done. So we cannot simply "undo the flip" and then reapply it. I think the most efficient thing then is to reimplementsecp256k1_generator_parsein Simplicity. The algorithm is:- Compute
x^3wherexis the field element (the 32-byte part of the point). You will need to squarexthen multiply byxbecause there is no fe_cube jet. (wg 556 + 808) - Add 7 to this using the
fe_addjet. (wgt 755 + whatever the weight of a 32-byte 7 is) - Take its square root with the
fe_square_rootjet. (wgt 10275) - If the bit is 1, then
fe_negatethe result (wgt 531).
Your total weight is 12925 plus whatever overhead you have composing these, producing a
feof 7, etc. Vs decompress which is10861. Remember that these are milliweight units, so the difference here is about 2 actual weight units. So the cost is mostly in programmer time/annoyance rather than on-chain weight,Alternately you can:
- Call
decompressas per usual (wg 10861) - Square the y-coordinate with
fe_squarethen sqrt it withfe_square_root. (You can throw away the return value sincedecompressalready checked it.) (wg 10275 + 556) - If
y == sqrt(y^2)matches the bit, callfe_negateto negate the bit (wgt 531).
This is easier to implement but it costs roughly twice as much so I wouldn't recommend it.
Reacted by Yevhenii SekhinThere are a few more considerations:
- In both situations the final
ifcould be kinda expensive if it leads to a hidden branch. There are some shenanigans you can do to avoid hiding but I think that's the job of an (eventual) optimizer so let's not worry about it. - In the first solution, ChatGPT 6 claims it can get the cost of
7down to 14 bytes from the naive 32 bytes. Furthermore, the7construction will be shared across every decompression call so we can probably disregard its weight. - ChatGPT 6 also proposes a solution where we add an auxiliary witness which is the fourth root of
x^3 + 7. We can square this to get a proposedy, then call thege_on_curvejet to check that it's the correcty, and then conditionally negate it based on our bit. If it weren't for the extra 32-byte witness (which cannot be shared or compressed) this would dramatically better. (Though with a bit more prodding, it pointed out that in cases where we need padding anyway, then extra witnesses are "free".)
- In both situations the final
Oh, and if you're just computing an asset/value and then asserting that it matches what's on-chain, don't even bother decompressing. Just assert that the
xcoordinates match. The consensus code will enforce that theycoordinates have the correct sign, as long as your amounts are nonzero. (And if they are zero, the sign doesn't matter.)Thanks! I've applied this in BlockstreamResearch/simplicityhl-std#44:
For checks against a computed point compare only the x-coordinate, as you suggested. That covers all of
commitment.simf, and the final comparison inrelations.simf(scaled_eq,value_eq,asset_eq,sum_eq).
Regarding points used in calculations (most ofrelations.simfand all ofproofs.simf) are decoded with your first approach:pub fn conf_point_to_ge(p: Point) -> Ge { let (not_square, x): (u1, u256) = p; // `fe_square_root` always returns the root that is itself a square. let y: Fe = unwrap(jet::fe_square_root(jet::fe_add(jet::fe_multiply(jet::fe_square(x), x), 7))); match u1_to_bool(not_square) { true => (x, jet::fe_negate(y)), false => (x, y), } }
About the type-system fix: separate "CT point" and "normal point" types need nominal types, which SimplicityHL doesn't have yet. They're under discussion in Nominal types and module identification in SimplicityHL (add link here, for quick look), and CT points could be another motivating case there.
Since that will take a while, we could add a new jet that decodes CT points:
ge_set_xquadplus a conditional negation, likesecp256k1_generator_parse. Or is it better to keep the stdlib helper for now, and add the type distinction once nominal types land?We cannot add new jets without forking Liquid.
Reacted by Yevhenii Sekhin
Description
Confidential assets and amounts returned by the Elements jets (
input_amount,output_amount,output_asset,current_amount, ...) arePoint = (u1, Fe)values. Decoding them withjet::decompressgives the negated point for about half of all values.Cause
The two sides read the
u1differently:0x0a/0x0b,0x08/0x09) means "y is not a square".generator_serialize:output[0] = 11 ^ fe_is_square_var(&ge.y)pedersen_commitment_load:ge_set_xquad(&ge, &x); if (input[0] & 1) ge_neg(&ge, &ge);copyRawConfidential/copyRawAmt(C/elements/env.c) copy that bit asODD_Y, andjet::decompressreads it as y is odd (secp256k1_ge_set_xo_var).Whether y is a square and whether it is odd are unrelated, so the two readings disagree on about 50% of points.
Impact
CT arithmetic on commitments taken from the transaction fails on about half of honest inputs. The
ODD_Ynaming hides this. We found it while writing CT functions for BlockstreamResearch/simplicityhl-std#44.