privacy-scaling-explorations / halo2curves

Other
172 stars 137 forks source link

EC point serialization #141

Closed davidnevadoc closed 6 months ago

davidnevadoc commented 7 months ago

This PR follows up the serialization issue that was brought up in #109.

This PR applies the proposed solution for serialization of EC defined over prime fields with 0, 1 or 2 spare bits. (Bls12-381 has its own standard and has been left out).

Here is a summary with the main changes:

For the serialization of elliptic curve points defined over prime fields:

Change in flags:

Flag bits, according to the number of spare bits.

1 Spare bit.

Compressed format

| ---- | ------------ |
| sign | x-coordinate |
| ---- | ------------ |
  1 bit
sign x-coordinate
Identity 0 0
Non-identity $P$ $sgn0(P)$ $P.x$

Uncompressed format

| ---- | ------------ | ---- | ------------ |
|   0  | x-coordinate |   0  | y-coordinate |
| ---- | ------------ | ---- | ------------ |
  1 bit                 1 bit
0 x-coordinate 0 y-coordinate
Identity 0 0 0 0
Non-identity $P$ 0 $P.x$ 0 $P.y$

2 Spare bits.

Compressed format

| ---- | ------ | ------------ |
| sign | ident  | x-coordinate |
| ---- | ------ | ------------ |
 1 bit  1 bit  
sign ident x-coordinate
Identity 0 1 0
Non-identity $P$ $sgn0(P)$ 0 $P.x$

Uncompressed format Spare bits are set to 0.

| ------ | ----  | ------------ | ------ | ---- | ------------ |
| 0      |  0    | y-coordinate | 0      | 0    | x-coordinate |
| ------ | ----  | ------------ | ------ | ---- | ------------ |
  1 bit    1 bit                  1 bit    1 bit
0 0 x-coordinate 0 0 y-coordinate
Identity 0 0 0 0 0 0
Non-identity $P$ 0 0 $P.x$ 0 0 $P.y$

0 Spare bits.

Add an extra byte in the compressed format to hold the flags. Then follow the 2 spare bit flag format.

Compressed format

| ---- | ----- | ------ | ------------ |
| sign | ident | 000000 | x-coordinate |
| ---- | ----- | ------ | ------------ |
 1 bit  1 bit       6 bit   

Same as 2 spare bits, with padding:

sign identity 000000 x-coordinate
Identity 0 1 000000 0
Non-identity $P$ $sgn0(P)$ 0 000000 $P.x$

Uncompressed format

| ------------ | ------------ |
| x-coordinate | y-coordinate |
| ------------ | ------------ |
x-coordinate y-coordinate
Identity 0 0
Non-identity $P$ $P.x$ $P.y$