--- Log opened Mon Feb 20 00:00:49 2023
01:25 -!- tromp [~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl] has quit [Quit: My iMac has gone to sleep. ZZZzzz…]
02:23 -!- tromp [~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl] has joined #secp256k1
08:18 -!- tromp [~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl] has quit [Quit: My iMac has gone to sleep. ZZZzzz…]
08:21 -!- tromp [~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl] has joined #secp256k1
09:53 -!- tromp [~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl] has quit [Quit: My iMac has gone to sleep. ZZZzzz…]
10:15 -!- clewe [~clewe@66.183.0.205] has joined #secp256k1
10:24 -!- ariard_ is now known as ariard
10:36 -!- tromp [~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl] has joined #secp256k1
11:10 < clewe> Hi. I have a question about field elements
11:10 < clewe> Field elements can be normalized or unnormalized; they also have some extra bits and a magnitude
11:11 < clewe> I originally thought that methods like fe_add produce normalized outputs upon normalized inputs, but this doesn't seem to be the case
11:11 < clewe> Is there a rule for when an output is normalized?
11:17 < sipa> It's documented per field operation how magnitude and normalization carry forward.
11:17 < sipa> But the entire point of having this denormalized representation is so that we don't need a carry/reduce after every addition.
11:18 < sipa> So making addition automatically normalize would defeat the entire purpose.
11:18 < sipa> https://github.com/bitcoin-core/secp256k1/pull/1066 formalizes and clarifies a lot of those rules
11:19 < sipa> It's perhaps easier to look at that if you want to understand the rules; very little changes in practice w.r.t. master (possibly nothing I don't exactly remember).
11:19 < sipa> Specifically, src/field.h in that PR.
11:54 < clewe> Thanks, that helps a lot
11:54 < clewe> I will read this in more detail tomorrow
11:55 < clewe> Is there a definition somewhere of what the magnitude stands for? It's "how far away a FE is from its normalization", but what does that actually mean?
11:56 < sipa> So from the "field interface" perspective, there is no meaning. It's just a property of field elements that is subject to the specified rules, and is entirely abstract in that regard.
11:57 < sipa> The two field implementation give it a specific meaning that relates to how they represent the numbers.
11:58 < sipa> In particular, it's related to the maximum ratio between individual limbs in the representation and how high that limb can be in normalized form.
11:58 < sipa> 1066's src/field_5x26.h will help perhaps.
12:13 < clewe> Right, so the magnitude represents a state of the Fe that is highly technical and of which there are 32 kinds
12:14 < clewe> Magnitude = 0 is normalized and magnitude = 1 is still kind of normalized if the normalized flag is set
12:14 < clewe> Everything above is denormalized
12:14 < sipa> magnitude 0 is always normalized, 1 may be normalized, 2-32 are never normalized
12:14 < sipa> indeed
12:15 < roconnor> magintude 0 also means the number is 0.
12:15 < sipa> indeed
12:16 < sipa> but normalized/magnitude just establish upper bounds; value 0 can just as well be represented by an unnornalized magnitude 32 field element
12:16 < sipa> it's only in the other way around, that magnitude 0 implies the value is 0
12:16 < clewe> Is it true that there are many FE values where the internal representation doesn't fit the ratios at all and there is no magnitude that we can assign? Super-denormalized elements, so to speak
12:17 < sipa> those are invalid
12:18 < sipa> and that reasoning is backwards too: we don't assigned magnitude/normalized to field elements
12:18 < sipa> the magnitude/normalized values are a eay to encode known constraints the field element representation satisfied
12:19 < clewe> If you get the FE from a 32-byte value and use the available secp methods, you probably never reach an invalid element
12:19 < sipa> yeah, don't do that
12:19 < sipa> wait, 32-byte value, how?
12:20 < sipa> if you load it using secp256k1_fe_set_b32, it'd work
12:20 < clewe> That's what I meant
12:20 < sipa> if you assign the individual 5x64 representation's uint64 directly, you'll break all sorts of invariants
12:21 < clewe> Makes sense
12:22 < sipa> Note that there are 2^(5*64) = 2^320 such values for the tuples
12:23 < clewe> That's almost everything
12:24 < clewe> I will make sure to use the methods and respect those invariants
12:40 < sipa> It's important to note that while normalization/magnitude are tracked at runtime in DEBUG builds, they're primarily compile-time properties of the code.
12:40 < sipa> Like you should be able to say for each field element at every point in the code what its magnitude is going to be, and whether it'll be normalized or not.
12:45 < clewe> That's the VERIFY flag, right?
12:45 < sipa> err yes that's what I mean
12:45 < clewe> You know what you are doing, you have pre and post conditions, but it's good to check that all equations hold during debug
12:46 < clewe> At some point, we verify all that stuff in Coq. Russell has already putting in some work from what I hear
12:46 < sipa> If libsecp256k1 was written in a language with dependent types or something resemblinb type-level naturals, the magnitude/normalization would be part of the type of field elements, and we would have the compiler prevent incorrect usage.
12:47 < sipa> The runtime-tracking-under-VERIFY is a best approximation we can do in C.
13:05 -!- clewe [~clewe@66.183.0.205] has quit [Quit: leaving]
13:07 -!- clewe [~clewe@66.183.0.205] has joined #secp256k1
14:09 -!- tromp [~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl] has quit [Quit: My iMac has gone to sleep. ZZZzzz…]
23:20 -!- tromp [~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl] has joined #secp256k1
--- Log closed Tue Feb 21 00:00:50 2023