Add HD wallets support

[survived]

Adds HD-wallets support (that requires hd-wallets feature) based on slip_10 crate.

Spec was updated to reflect changes in the protocol.

I also updated keygens to use utils::blame which appeared after keygen was written

Diff is huge bc I regenerated precomputed shares

[github-actions[bot]]

Crate direct deps

Direct deps

```text digest v0.10.6 futures v0.3.24 generic-ec v0.1.2 generic-ec-zkp v0.1.1 hex v0.4.3 paillier-zk v0.1.0 rand_chacha v0.3.1 rand_core v0.6.4 round-based v0.2.0 serde v1.0.188 serde_with v2.3.3 sha2 v0.10.6 thiserror v1.0.48 udigest v0.1.0 ```

Compared to base branch

Diff

```text No changes ```

All deps

cargo tree

```text cggmp21 v0.1.1 (/home/runner/work/cggmp21/cggmp21/pr_branch/cggmp21) ├── digest v0.10.6 │ ├── block-buffer v0.10.3 │ │ └── generic-array v0.14.6 │ │ ├── serde v1.0.188 │ │ │ └── serde_derive v1.0.188 (proc-macro) │ │ │ ├── proc-macro2 v1.0.66 │ │ │ │ └── unicode-ident v1.0.4 │ │ │ ├── quote v1.0.33 │ │ │ │ └── proc-macro2 v1.0.66 (*) │ │ │ └── syn v2.0.32 │ │ │ ├── proc-macro2 v1.0.66 (*) │ │ │ ├── quote v1.0.33 (*) │ │ │ └── unicode-ident v1.0.4 │ │ └── typenum v1.15.0 │ └── crypto-common v0.1.6 │ ├── generic-array v0.14.6 (*) │ └── typenum v1.15.0 ├── futures v0.3.24 │ ├── futures-channel v0.3.24 │ │ ├── futures-core v0.3.24 │ │ └── futures-sink v0.3.24 │ ├── futures-core v0.3.24 │ ├── futures-executor v0.3.24 │ │ ├── futures-core v0.3.24 │ │ ├── futures-task v0.3.24 │ │ └── futures-util v0.3.24 │ │ ├── futures-channel v0.3.24 (*) │ │ ├── futures-core v0.3.24 │ │ ├── futures-io v0.3.24 │ │ ├── futures-macro v0.3.24 (proc-macro) │ │ │ ├── proc-macro2 v1.0.66 (*) │ │ │ ├── quote v1.0.33 (*) │ │ │ └── syn v1.0.101 │ │ │ ├── proc-macro2 v1.0.66 (*) │ │ │ ├── quote v1.0.33 (*) │ │ │ └── unicode-ident v1.0.4 │ │ ├── futures-sink v0.3.24 │ │ ├── futures-task v0.3.24 │ │ ├── memchr v2.5.0 │ │ ├── pin-project-lite v0.2.9 │ │ ├── pin-utils v0.1.0 │ │ └── slab v0.4.7 │ ├── futures-io v0.3.24 │ ├── futures-sink v0.3.24 │ ├── futures-task v0.3.24 │ └── futures-util v0.3.24 (*) ├── generic-ec v0.1.2 │ ├── generic-ec-core v0.1.2 │ │ ├── generic-array v0.14.6 (*) │ │ ├── rand_core v0.6.4 │ │ ├── serde v1.0.188 (*) │ │ ├── subtle v2.4.1 │ │ └── zeroize v1.6.0 │ │ └── zeroize_derive v1.3.2 (proc-macro) │ │ ├── proc-macro2 v1.0.66 (*) │ │ ├── quote v1.0.33 (*) │ │ ├── syn v1.0.101 (*) │ │ └── synstructure v0.12.6 │ │ ├── proc-macro2 v1.0.66 (*) │ │ ├── quote v1.0.33 (*) │ │ ├── syn v1.0.101 (*) │ │ └── unicode-xid v0.2.4 │ ├── getrandom v0.2.10 │ │ ├── cfg-if v1.0.0 │ │ └── libc v0.2.148 │ ├── hex v0.4.3 │ │ └── serde v1.0.188 (*) │ ├── phantom-type v0.4.2 │ │ └── educe v0.4.19 (proc-macro) │ │ ├── enum-ordinalize v3.1.11 (proc-macro) │ │ │ ├── num-bigint v0.4.3 │ │ │ │ ├── num-integer v0.1.45 │ │ │ │ │ └── num-traits v0.2.15 │ │ │ │ └── num-traits v0.2.15 │ │ │ ├── num-traits v0.2.15 │ │ │ ├── proc-macro2 v1.0.66 (*) │ │ │ ├── quote v1.0.33 (*) │ │ │ └── syn v1.0.101 (*) │ │ ├── proc-macro2 v1.0.66 (*) │ │ ├── quote v1.0.33 (*) │ │ └── syn v1.0.101 (*) │ ├── rand_core v0.6.4 │ ├── serde v1.0.188 (*) │ ├── serde_with v2.3.3 │ │ ├── serde v1.0.188 (*) │ │ └── serde_with_macros v2.3.3 (proc-macro) │ │ ├── darling v0.20.1 │ │ │ ├── darling_core v0.20.1 │ │ │ │ ├── fnv v1.0.7 │ │ │ │ ├── ident_case v1.0.1 │ │ │ │ ├── proc-macro2 v1.0.66 (*) │ │ │ │ ├── quote v1.0.33 (*) │ │ │ │ ├── strsim v0.10.0 │ │ │ │ └── syn v2.0.32 (*) │ │ │ └── darling_macro v0.20.1 (proc-macro) │ │ │ ├── darling_core v0.20.1 (*) │ │ │ ├── quote v1.0.33 (*) │ │ │ └── syn v2.0.32 (*) │ │ ├── proc-macro2 v1.0.66 (*) │ │ ├── quote v1.0.33 (*) │ │ └── syn v2.0.32 (*) │ ├── subtle v2.4.1 │ ├── udigest v0.1.0 │ │ ├── digest v0.10.6 (*) │ │ └── udigest-derive v0.1.0 (proc-macro) │ │ ├── proc-macro2 v1.0.66 (*) │ │ ├── quote v1.0.33 (*) │ │ └── syn v2.0.32 (*) │ └── zeroize v1.6.0 (*) ├── generic-ec-zkp v0.1.1 │ ├── generic-array v0.14.6 (*) │ ├── generic-ec v0.1.2 (*) │ ├── rand_core v0.6.4 │ ├── serde v1.0.188 (*) │ ├── subtle v2.4.1 │ └── udigest v0.1.0 (*) ├── hex v0.4.3 (*) ├── paillier-zk v0.1.0 │ ├── digest v0.10.6 (*) │ ├── fast-paillier v0.1.0 │ │ ├── bytemuck v1.13.1 │ │ │ └── bytemuck_derive v1.4.1 (proc-macro) │ │ │ ├── proc-macro2 v1.0.66 (*) │ │ │ ├── quote v1.0.33 (*) │ │ │ └── syn v2.0.32 (*) │ │ ├── rand_core v0.6.4 │ │ ├── rug v1.21.0 │ │ │ ├── az v1.2.1 │ │ │ ├── gmp-mpfr-sys v1.6.1 │ │ │ │ └── libc v0.2.148 │ │ │ ├── libc v0.2.148 │ │ │ └── serde v1.0.188 (*) │ │ ├── serde v1.0.188 (*) │ │ └── thiserror v1.0.48 │ │ └── thiserror-impl v1.0.48 (proc-macro) │ │ ├── proc-macro2 v1.0.66 (*) │ │ ├── quote v1.0.33 (*) │ │ └── syn v2.0.32 (*) │ ├── generic-ec v0.1.2 (*) │ ├── rand_core v0.6.4 │ ├── rug v1.21.0 (*) │ ├── serde v1.0.188 (*) │ ├── serde_with v3.0.0 │ │ ├── serde v1.0.188 (*) │ │ └── serde_with_macros v3.0.0 (proc-macro) │ │ ├── darling v0.20.1 (*) │ │ ├── proc-macro2 v1.0.66 (*) │ │ ├── quote v1.0.33 (*) │ │ └── syn v2.0.32 (*) │ └── thiserror v1.0.48 (*) ├── rand_chacha v0.3.1 │ ├── ppv-lite86 v0.2.17 │ └── rand_core v0.6.4 ├── rand_core v0.6.4 ├── round-based v0.2.0 │ ├── futures-util v0.3.24 (*) │ ├── phantom-type v0.3.1 │ │ └── educe v0.4.19 (proc-macro) (*) │ ├── round-based-derive v0.2.0 (proc-macro) │ │ ├── proc-macro2 v1.0.66 (*) │ │ ├── quote v1.0.33 (*) │ │ └── syn v1.0.101 (*) │ ├── thiserror v1.0.48 (*) │ └── tracing v0.1.36 │ ├── cfg-if v1.0.0 │ ├── pin-project-lite v0.2.9 │ ├── tracing-attributes v0.1.22 (proc-macro) │ │ ├── proc-macro2 v1.0.66 (*) │ │ ├── quote v1.0.33 (*) │ │ └── syn v1.0.101 (*) │ └── tracing-core v0.1.29 │ └── once_cell v1.17.0 ├── serde v1.0.188 (*) ├── serde_with v2.3.3 (*) ├── sha2 v0.10.6 │ ├── cfg-if v1.0.0 │ ├── cpufeatures v0.2.5 │ └── digest v0.10.6 (*) ├── thiserror v1.0.48 (*) └── udigest v0.1.0 (*) ```

Compared to base branch

Diff

```text No changes ```

[github-actions[bot]]

Benchmark Result

Benchmarks

```text RUST_TESTS_SEED=d51e05e1c96ccfce76ed824b1a45af99a68a4af38a442e21e27f5d5dd6e2710a n = 3 Non-threshold DKG Protocol Performance: - Protocol took 429.51µs to complete In particular: - Stage: 10.05µs - Setup networking: 9.86µs (98.1%) - Unstaged: 191.00ns (1.9%) - Round 1: 148.47µs - Compute execution id: 8.35µs (5.6%) - Sample x_i, rid_i, chain_code: 64.35µs (43.3%) - Sample schnorr commitment: 59.65µs (40.2%) - Commit to public data: 15.78µs (10.6%) - Unstaged: 341.00ns (0.2%) - Round 2: 1.07µs - Hash received msgs (reliability check): 892.00ns (83.2%) - Unstaged: 180.00ns (16.8%) - Round 3: 291.00ns - Assert other parties hashed messages (reliability check): 151.00ns (51.9%) - Unstaged: 140.00ns (48.1%) - Round 4: 31.14µs - Validate decommitments: 29.79µs (95.7%) - Calculate challege rid: 1.03µs (3.3%) - Prove knowledge of `x_i`: 180.00ns (0.6%) - Unstaged: 140.00ns (0.4%) - Round 5: 238.49µs - Validate schnorr proofs: 238.15µs (99.9%) - Unstaged: 342.00ns (0.1%) Threshold DKG Protocol Performance: - Protocol took 1.25ms to complete In particular: - Stage: 1.89µs - Setup networking: 1.79µs (94.7%) - Unstaged: 100.00ns (5.3%) - Round 1: 203.21µs - Compute execution id: 841.00ns (0.4%) - Sample rid_i, schnorr commitment, polynomial, chain_code: 180.07µs (88.6%) - Commit to public data: 22.13µs (10.9%) - Unstaged: 170.00ns (0.1%) - Round 2: 1.08µs - Hash received msgs (reliability check): 901.00ns (83.2%) - Unstaged: 182.00ns (16.8%) - Round 3: 280.00ns - Assert other parties hashed messages (reliability check): 140.00ns (50.0%) - Unstaged: 140.00ns (50.0%) - Round 4: 776.44µs - Validate decommitments: 43.49µs (5.6%) - Validate data size: 291.00ns (0.0%) - Validate Feldmann VSS: 357.45µs (46.0%) - Compute rid: 300.00ns (0.0%) - Compute Ys: 359.80µs (46.3%) - Compute sigma: 310.00ns (0.0%) - Calculate challenge: 14.46µs (1.9%) - Prove knowledge of `sigma_i`: 181.00ns (0.0%) - Unstaged: 160.00ns (0.0%) - Round 5: 266.46µs - Validate schnorr proofs: 264.87µs (99.4%) - Derive resulting public key and other data: 1.32µs (0.5%) - Unstaged: 270.00ns (0.1%) Auxiliary data generation protocol Protocol Performance: - Protocol took 9.55s to complete In particular: - Stage: 11.47µs - Retrieve auxiliary data: 241.00ns (2.1%) - Setup networking: 9.99µs (87.1%) - Precompute execution id and shared state: 1.13µs (9.9%) - Unstaged: 110.00ns (1.0%) - Round 1: 1.16s - Retrieve primes (p and q): 90.00ns (0.0%) - Compute paillier decryption key (N): 4.59µs (0.0%) - Generate auxiliary params r, λ, t, s: 9.00ms (0.8%) - Prove Πprm (ψˆ_i): 1.15s (99.2%) - Sample random bytes: 1.88µs (0.0%) - Compute hash commitment and sample decommitment: 299.73µs (0.0%) - Unstaged: 230.00ns (0.0%) - Round 2: 1.47µs - Hash received msgs (reliability check): 1.11µs (75.4%) - Unstaged: 362.00ns (24.6%) - Round 3: 320.00ns - Assert other parties hashed messages (reliability check): 180.00ns (56.2%) - Unstaged: 140.00ns (43.8%) - Round 4: 5.89s - Validate round 1 decommitments: 628.74µs (0.0%) - Validate П_prm (ψ_i): 2.28s (38.8%) - Add together shared random bytes: 2.23µs (0.0%) - Compute П_mod (ψ_i): 3.43s (58.3%) - Assemble security params for П_fac (ф_i): 7.27µs (0.0%) - Compute П_fac (ф_i^j): 171.32ms (2.9%) - Unstaged: 1.40µs (0.0%) - Round 5: 2.49s - Validate ψ_j (П_mod): 2.32s (93.1%) - Validate ф_j (П_fac): 172.23ms (6.9%) - Assemble auxiliary info: 147.55µs (0.0%) - Unstaged: 891.00ns (0.0%) Signing protocol Protocol Performance: - Protocol took 4.17s to complete In particular: - Stage: 135.72µs - Map t-out-of-n protocol to t-out-of-t: 64.70µs (47.7%) - Retrieve auxiliary data: 67.22µs (49.5%) - Precompute execution id and security params: 732.00ns (0.5%) - Setup networking: 2.96µs (2.2%) - Unstaged: 120.00ns (0.1%) - Round 1: 188.76ms - Generate local ephemeral secrets (k_i, y_i, p_i, v_i): 49.63µs (0.0%) - Encrypt G_i and K_i: 107.71ms (57.1%) - Prove ψ0_j: 81.00ms (42.9%) - Unstaged: 1.39µs (0.0%) - Round 2: 15.58µs - Hash received msgs (reliability check): 15.31µs (98.3%) - Unstaged: 272.00ns (1.7%) - Round 3: 2.23s - Assert other parties hashed messages (reliability check): 1.06µs (0.0%) - Verify psi0 proofs: 268.65ms (12.1%) - Sample random r, hat_r, s, hat_s, beta, hat_beta: 49.44µs (0.0%) - Encrypt D_ji: 70.65ms (3.2%) - Encrypt F_ji: 35.85ms (1.6%) - Encrypt hat_D_ji: 559.45ms (25.1%) - Encrypt hat_F_ji: 35.81ms (1.6%) - Prove psi_ji: 791.35ms (35.5%) - Prove psiˆ_ji: 209.17ms (9.4%) - Prove psi_prime_ji : 257.98ms (11.6%) - Unstaged: 2.82µs (0.0%) - Round 4: 1.56s - Retrieve auxiliary data: 6.06µs (0.0%) - Validate psi: 164.69ms (10.5%) - Validate hat_psi: 164.98ms (10.6%) - Validate psi_prime: 935.87ms (59.9%) - Compute Gamma, Delta_i, delta_i, chi_i: 215.38ms (13.8%) - Prove psi_prime_prime: 81.54ms (5.2%) - Unstaged: 772.00ns (0.0%) - Presig output: 184.99ms - Validate psi_prime_prime: 184.85ms (99.9%) - Calculate presignature: 135.00µs (0.1%) - Unstaged: 1.86µs (0.0%) - Partial signing: 9.29µs - Signature reconstruction: 201.45µs ```

[github-actions[bot]]

The spec was successfully compiled. PDF is available here.

[maurges]

Compared to base branch

Diff No changes

I think our bot is broken