Updates for CGGMP'24 #170

fjarri · 2024-12-17T23:45:59Z

Fixes #157
Fixes #43 (in progress)
Fixes #91 (in progress)
Fixes #5 (in progress)

Updated paper references in PAPER.md, removed obsolete items.
Updated to the new range definition (±2^l now means [-2^(l-1)+1, 2^(l-1)] instead of the previous [-2^l, 2^l]). This caused a bit of a chain reaction:
- SecretSigned::assert_exponent_range() logic changed.
- SecretSigned::random_in_exp_range*() logic changed, and also exp was changed to exponent to match the assertion name.
- PublicSigned::from_xof_reader_bounded() changed its behavior to produce the number according to the new range definition, and was renamed to from_xof_reader_in_range().
- PublicSigned::in_range_bits() changed its behavior according to the new range definition, and was renamed to is_in_exponent_range().
- Wherever scalars are passed to proofs and Ciphertext constructor they are passed as SecretSigned, to comply with the range requirements in the proofs.
- conversions::secret_unsigned_from_scalar() removed.
- Added SecretSigned::new_modulo() constructor to make a signed number in range [-N/2, N/2] from an Uint in range [0, N).
- Removed Ciphertext::new() and decrypt() (which took unsigned plaintexts), renamed new_signed() and decrypt_signed() to new() and decrypt().
- Ciphertext::new_with_randomizer() was renamed to new_with_randomizer_unsigned(), since it's now a special one, only used in P_mul. Renamed new_with_randomizer_signed() to new_with_randomizer(), and new_public_with_randomizer_signed() to new_public_with_randomizer().
Following that, wherever in the paper e <-- ±q is used, we are sampling the challenge as a Scalar using the new Scalar::from_xof_reader() method (and using that in П^sch as well).
Updated paper references and notation in aff-g proof.
Updated paper references in prm proof, and started using BitVec for its commitment.
Updated dec proof (there were significant changes). Temporarily, it is located in dec_new.rs, will be moved to dec.rs when Presigning is updated.
Added elog proof.
Added enc-elg proof.
Added aff-g* proof.
Updated paper references and notation in fac proof, and implemented necessary changes to the algorithm (some variables are calculated differently, and the challenge is now a signed Uint and not a Scalar)
Updated paper references and notation in mod proof, and enforced invertibility conditions that were added in '24
Updated paper references and notation sch proof
Encapsulated the invertibility check in an IsInvertible trait, documenting the choice between GCD and invert()
Updated KeyInit and filled in the code for evidence generation/checking. In particular, fixed Self-contained proof of malicious behavior for Round 3 of KeyGen #103 (by using an echo broadcast in Round 2)
Updated KeyRefresh to the new version and filled in the code for evidence generation/checking.

In progress:

Updating Presigning/Signing

TODO:

Implement AuxGen by cutting out parts of KeyRefresh responsible for share changes (this should wait until we stabilize all the shortcuts and code style)
Implement the recommended scheme parameters from Section C.1. Note that there are two possible sets, for 112 bits and 128 bits of security.

codecov · 2024-12-19T02:50:15Z

Codecov Report

Attention: Patch coverage is 94.59642% with 160 lines in your changes missing coverage. Please review.

Project coverage is 94.20%. Comparing base (423f1b5) to head (0f86f18).

Files with missing lines	Patch %	Lines
synedrion/src/cggmp21/aux_gen.rs	40.81%	29 Missing ⚠️
synedrion/src/cggmp21/interactive_signing.rs	65.88%	29 Missing ⚠️
synedrion/src/www02/key_resharing.rs	30.55%	25 Missing ⚠️
synedrion/src/cggmp21/key_refresh.rs	96.42%	19 Missing ⚠️
synedrion/src/cggmp21/key_init.rs	88.05%	16 Missing ⚠️
synedrion/src/cggmp21/sigma/aff_g_star.rs	96.42%	7 Missing ⚠️
synedrion/src/cggmp21/sigma/enc_elg.rs	96.55%	6 Missing ⚠️
synedrion/src/cggmp21/sigma/dec_new.rs	97.26%	5 Missing ⚠️
synedrion/src/cggmp21/sigma/elog.rs	96.58%	4 Missing ⚠️
synedrion/src/tools/protocol_shortcuts.rs	91.66%	4 Missing ⚠️
... and 8 more

Additional details and impacted files

@@            Coverage Diff             @@
##           master     #170      +/-   ##
==========================================
+ Coverage   93.06%   94.20%   +1.13%     
==========================================
  Files          36       42       +6     
  Lines        7012     8779    +1767     
==========================================
+ Hits         6526     8270    +1744     
- Misses        486      509      +23

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

To replace the old dec when we are converting Presigning

dvdplm

I have looked at Key_init and Key_refresh tests only.

As mentioned I think it's very cool to see the fault injection machinery come together, it's going to be a major help. The code is verbose and repetitive at times, but this is a complex protocol and its tests are always going to reflect that complexity.
Having the right testing tools is about finding that delicate balance between readability&maintainability and expressiveness. I'm sure we'll fiddle with this plenty mroe in the future but this strikes me as much better than we had before.

dvdplm · 2025-01-10T15:00:16Z

synedrion/src/cggmp21/key_init_tests.rs

+        .collect()
+}
+
+fn check_evidence<M>(expected_description: &str) -> Result<(), LocalError>


Naming nitpick: this does more than merely checking some data against some other; it actually drives the protocol (and checks the outcome). In my head "check" is more "compare these two things and yell if they don't match".

How about a refactor to something more classic like "let r: Result<…, …> = run(); assert_eq!(r, …, "bla bla");"?

Less invasively: a rename to assert_outcome(expected)?

How about a refactor to something more classic like "let r: Result<…, …> = run(); assert_eq!(r, …, "bla bla");"?

It checks a number of things internally:

the malicious node does not create any malicious behavior evidence

all the other nodes create an evidence for the malicious node

the evidence description matches the expected one

Not sure if it's worth packing in one variable.

dvdplm · 2025-01-10T15:03:53Z

synedrion/src/cggmp21/key_init_tests.rs

+}
+
+#[test]
+fn invalid_messages() {


We could make the tests return Result<(), LocalErr> and then use ? instead of the unwraps... I'd cut down one line for each check_invalid_message_evidence...

Hm, right, I keep forgetting that's a possibility for Rust tests. I'll try it out.

dvdplm · 2025-01-10T15:04:56Z

synedrion/src/cggmp21/key_init_tests.rs

+        }
+    }
+
+    check_evidence::<Override>("Protocol error: A hash mismatch in Round 2").unwrap();


I have to say that these overrides allowing fault injection are REALLY cool; a long time in the making and it's nice to see them come together.

dvdplm · 2025-01-10T15:06:03Z

synedrion/src/cggmp21/key_refresh_tests.rs

+    let signers = (0..3).map(TestSigner::new).collect::<Vec<_>>();
+    let all_ids = signers
+        .iter()
+        .map(|signer| signer.verifying_key())


Suggested change

.map(|signer| signer.verifying_key())

.map(TestSigner::verifying_key)

Huh, strange that clippy did not suggest that

dvdplm · 2025-01-10T15:08:12Z

synedrion/src/cggmp21/key_refresh_tests.rs

+
+fn check_evidence<M>(expected_description: &str) -> Result<(), LocalError>
+where
+    M: Misbehaving<Id, (), EntryPoint = KeyRefresh<P, Id>>,


It's a pity that check_evidence and make_entry_points have to be instantiated for each EntryPoint. As a new reader of the code, I have to look rather carefully before I spot that this one is for KeyRefresh and the other is KeyInit.
Maybe we can have a macro at some point to make the critical parts more visible, e.g.:
check_evidence!(KeyInit, …, …);
check_evidence!(KeyRefresh, …, …);

dvdplm · 2025-01-10T15:11:04Z

synedrion/src/tools/protocol_shortcuts_dev.rs

+    rng: &mut impl CryptoRngCore,
+    entry_points: Vec<(SP::Signer, M::EntryPoint)>,
+    behavior: &B,
+    associated_data: &<<<M::EntryPoint as EntryPoint<SP::Verifier>>::Protocol as Protocol<SP::Verifier>>::ProtocolError as ProtocolError<SP::Verifier>>::AssociatedData,


Yeah... I wish it either allowed me to create temporary aliases, or did not require explicit trait qualifications when there's no ambiguity

dvdplm · 2025-01-10T15:11:57Z

synedrion/src/tools/protocol_shortcuts_dev.rs

+    EP: 'static + Debug + EntryPoint<SP::Verifier>,
+    SP: SessionParameters,
+{
+    let prefix = match part {


Not sure, but maybe "phase" is more descriptive than "part" here? ModifyPhase and CheckPhase etc?

dvdplm · 2025-01-10T15:12:21Z

synedrion/src/tools/protocol_shortcuts_dev.rs

+        "The payload was expected to contain a message, but is `None`"
+    };
+
+    let expected_str = format!("{prefix} error: {error}");


Suggested change

let expected_str = format!("{prefix} error: {error}");

let expected_description = format!("{prefix} error: {error}");

dvdplm · 2025-01-10T15:12:38Z

synedrion/src/tools/protocol_shortcuts_dev.rs

+        entry_points,
+        &ModifyPart::new(round_num, part),
+        associated_data,
+        &expected_str,


Suggested change

&expected_str,

&expected_description,

dvdplm · 2025-01-10T15:19:05Z

synedrion/src/cggmp21/key_init_tests.rs

+                let context = &round3.context;
+                let aux = (&context.sid_hash, &context.my_id, &round3.rho);
+
+                // Make a proof for a random secret. This won't pass verification.


These comments are very useful.

I'll add more on the second pass, I was just a little tired of writing all these tests :)

fjarri · 2025-01-10T19:22:41Z

synedrion/src/tools/protocol_shortcuts_dev.rs

+        "Deserialization error"
+    } else {
+        // TODO: a bug in `manul`, this message should be the exact opposite
+        "The payload was expected to contain a message, but is `None`"


Fixed in entropyxyz/manul#86

fjarri · 2025-01-10T19:23:47Z

synedrion/src/cggmp21/key_refresh_tests.rs

+}
+
+#[test]
+fn invalid_messages() {


Echo broadcast tests to be added after entropyxyz/manul#86 is in

fjarri self-assigned this Dec 17, 2024

fjarri force-pushed the new-cggmp branch from b9ed866 to 68a123a Compare December 19, 2024 02:47

fjarri force-pushed the new-cggmp branch 10 times, most recently from 12afc7a to e0565ce Compare December 25, 2024 21:04

fjarri force-pushed the new-cggmp branch 2 times, most recently from cdb7c84 to 0ca10d8 Compare December 31, 2024 22:56

fjarri mentioned this pull request Dec 31, 2024

API adjustments for CGGMP'24 entropyxyz/manul#79

Merged

fjarri force-pushed the new-cggmp branch 2 times, most recently from 0fc38fb to 235afa0 Compare January 3, 2025 22:51

fjarri mentioned this pull request Jan 4, 2025

Protocol writing shortcuts entropyxyz/manul#81

Open

fjarri force-pushed the new-cggmp branch from e85f157 to bbb0b6f Compare January 5, 2025 19:11

fjarri added 10 commits January 5, 2025 15:11

Update to manul trunk

1ec90f6

Update the paper Q&A to the new version

e8e3c1e

Change to the new range definition.

ed44946

Create challenges as Scalars where +-q range is used

18088a6

Add some operator impls

46e88b1

Update aff-g

4f75b58

Update prm, and use BitVec for its challenge

d3b0a7d

Add the new version of dec

685c908

To replace the old dec when we are converting Presigning

Add elog

35f55eb

Add enc-elg

2489db2

fjarri added 7 commits January 5, 2025 15:11

Add aff-g*

5dab612

Update fac

7c2e922

Update mod

bc4691a

Update sch

94f5307

Use a single method to check for invertibility

68dbf56

Move uint_from_xof to uint::traits

3c11be8

Update README

3430716

fjarri force-pushed the new-cggmp branch 7 times, most recently from 3fdc0fa to 3efcfd4 Compare January 10, 2025 02:33

fjarri added 2 commits January 9, 2025 18:46

Update KeyInit

d24b6fc

Update KeyRefresh

0f86f18

fjarri force-pushed the new-cggmp branch from 3efcfd4 to 0f86f18 Compare January 10, 2025 02:47

dvdplm reviewed Jan 10, 2025

View reviewed changes

fjarri commented Jan 10, 2025

View reviewed changes

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Updates for CGGMP'24 #170

Updates for CGGMP'24 #170

fjarri commented Dec 17, 2024 •

edited

Loading

codecov bot commented Dec 19, 2024 •

edited

Loading

dvdplm left a comment

dvdplm Jan 10, 2025

fjarri Jan 10, 2025

dvdplm Jan 10, 2025

fjarri Jan 10, 2025

dvdplm Jan 10, 2025

dvdplm Jan 10, 2025

fjarri Jan 10, 2025

dvdplm Jan 10, 2025

dvdplm Jan 10, 2025

fjarri Jan 10, 2025

dvdplm Jan 10, 2025

dvdplm Jan 10, 2025

dvdplm Jan 10, 2025

dvdplm Jan 10, 2025

fjarri Jan 10, 2025

fjarri Jan 10, 2025

fjarri Jan 10, 2025

	.map(\|signer\| signer.verifying_key())
	.map(TestSigner::verifying_key)

	let expected_str = format!("{prefix} error: {error}");
	let expected_description = format!("{prefix} error: {error}");

Updates for CGGMP'24 #170

Are you sure you want to change the base?

Updates for CGGMP'24 #170

Conversation

fjarri commented Dec 17, 2024 • edited Loading

codecov bot commented Dec 19, 2024 • edited Loading

Codecov Report

dvdplm left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

fjarri commented Dec 17, 2024 •

edited

Loading

codecov bot commented Dec 19, 2024 •

edited

Loading