junyechen1996 / draft-chen-cfrg-vdaf-pine

VDAF to support aggregating real number vectors with L2-norm bound
Other
4 stars 0 forks source link

Improve wraparound check parameter search #81

Closed junyechen1996 closed 5 months ago

junyechen1996 commented 6 months ago

The improvements come as:

Turns out with num_frac_bits = 24, neither Field56, nor Field48 can satisfy the field size requirement in wraparound checks.

junyechen1996 commented 6 months ago

Even with r = 1500, we cannot find possible alpha that can satisfy 2^-100 ZK error for Field48 and Field56, when num_frac_bits = 24, but it's possible for num_frac_bits = 15,

|r         |r_succ    |l2_norm   |frac_bits |field     |-log2(eta)     |-log2(zk)      |-log2(sound)   |overhead  |alpha               |
|:---------|:---------|:---------|:---------|:---------|:--------------|:--------------|:--------------|:---------|:-------------------|
|1500      |971       |1         |15        |Field48   |3              |376            |99             |27000     |1.6920026163616637  |
|1500      |971       |1         |15        |Field56   |3              |376            |99             |27000     |1.6920026163616637  |
|1500      |971       |1         |15        |Field64   |3              |376            |99             |27000     |1.6920026163616637  |
|1500      |971       |1         |24        |Field64   |3              |376            |99             |40500     |1.6920026163616637  |
|1500      |971       |1         |15        |Field128  |3              |376            |99             |27000     |1.6920026163616637  |
|1500      |971       |1         |24        |Field128  |3              |376            |99             |40500     |1.6920026163616637  |
junyechen1996 commented 6 months ago

With num_frac_bits = 20, Field56, there are some interesting outputs (num_wr_successes < num_wr_checks):

Parameters to satisfy 2^-100 soundness and 2^-100 ZK error
Failed to find alpha in [0.8325546111576977, 10.0] with any combination of num_wr_checks and num_wr_successes, for user parameters l2_norm_bound = 1, num_frac_bits = 20, field = Field48.
Displaying feasible set of wraparound check and user parameters:
|l2_norm   |frac_bits |field     |num_wr_checks  |num_wr_successes    |alpha               |-log2(eta)     |-log2(zk)      |-log2(sound)   |overhead  |
|:---------|:---------|:---------|:--------------|:-------------------|:-------------------|:--------------|:--------------|:--------------|:---------|
|1         |15        |Field48   |100            |100                 |8.639207325093722   |106            |99             |100            |2100      |
|1         |15        |Field56   |100            |100                 |8.639207325093722   |106            |99             |100            |2100      |
|1         |20        |Field56   |150            |140                 |3.2676572925689347  |14             |100            |99             |3600      |
|1         |15        |Field64   |100            |100                 |8.639207325093722   |106            |99             |100            |2100      |
|1         |20        |Field64   |100            |100                 |8.639207325093722   |106            |99             |100            |2600      |
|1         |24        |Field64   |100            |100                 |8.639207325093722   |106            |99             |100            |3000      |
|1         |15        |Field128  |100            |100                 |8.639207325093722   |106            |99             |100            |2100      |
|1         |20        |Field128  |100            |100                 |8.639207325093722   |106            |99             |100            |2600      |
|1         |24        |Field128  |100            |100                 |8.639207325093722   |106            |99             |100            |3000      |

Displaying full VDAF parameters:
|l2_norm   |frac_bits |dimension |chunk_len |field     |proofs    |num_wr_checks  |num_wr_successes    |-log2(zk) |-log2(sound)        |
|:---------|:---------|:---------|:---------|:---------|:---------|:--------------|:-------------------|:---------|:-------------------|
|1         |15        |1000      |57        |Field48   |3         |100            |100                 |99        |99                  |
|1         |15        |10000     |110       |Field48   |3         |100            |100                 |99        |99                  |
|1         |15        |100000    |319       |Field48   |3         |100            |100                 |99        |99                  |
|1         |15        |1000      |57        |Field56   |3         |100            |100                 |99        |99                  |
|1         |15        |10000     |110       |Field56   |3         |100            |100                 |99        |99                  |
|1         |15        |100000    |319       |Field56   |3         |100            |100                 |99        |99                  |
|1         |20        |1000      |69        |Field56   |3         |150            |140                 |100       |99                  |
|1         |20        |10000     |117       |Field56   |3         |150            |140                 |100       |99                  |
|1         |20        |100000    |322       |Field56   |3         |150            |140                 |100       |99                  |
|1         |15        |1000      |57        |Field64   |2         |100            |100                 |99        |99                  |
|1         |15        |10000     |110       |Field64   |2         |100            |100                 |99        |99                  |
|1         |15        |100000    |319       |Field64   |2         |100            |100                 |99        |99                  |
|1         |20        |1000      |61        |Field64   |2         |100            |100                 |99        |99                  |
|1         |20        |10000     |113       |Field64   |2         |100            |100                 |99        |99                  |
|1         |20        |100000    |320       |Field64   |2         |100            |100                 |99        |99                  |
|1         |24        |1000      |64        |Field64   |2         |100            |100                 |99        |99                  |
|1         |24        |10000     |114       |Field64   |2         |100            |100                 |99        |99                  |
|1         |24        |100000    |321       |Field64   |2         |100            |100                 |99        |99                  |
|1         |15        |1000      |57        |Field128  |1         |100            |100                 |99        |99                  |
|1         |15        |10000     |110       |Field128  |1         |100            |100                 |99        |99                  |
|1         |15        |100000    |319       |Field128  |1         |100            |100                 |99        |99                  |
|1         |20        |1000      |61        |Field128  |1         |100            |100                 |99        |99                  |
|1         |20        |10000     |113       |Field128  |1         |100            |100                 |99        |99                  |
|1         |20        |100000    |320       |Field128  |1         |100            |100                 |99        |99                  |
|1         |24        |1000      |64        |Field128  |1         |100            |100                 |99        |99                  |
|1         |24        |10000     |114       |Field128  |1         |100            |100                 |99        |99                  |
|1         |24        |100000    |321       |Field128  |1         |100            |100                 |99        |99                  |
junyechen1996 commented 5 months ago

Open thread: https://github.com/junyechen1996/draft-chen-cfrg-vdaf-pine/pull/81#discussion_r1555717886. Not sure why after computing GF(Field48.MODULUS), initializing a Field from an integer always makes Field.val be 0.

junyechen1996 commented 5 months ago

Squashed.