Nocturne
Search
⌃K
Comment on page

Encodings

Details about encodings used to represent core data structures using both field elements and bits.

Compressed Point Encoding

We often represent Baby Jubjub curve points in a "compressed" 255-bit encoding to save on hashing, bandwidth, and calldata. Our encoding scheme is identical to the scheme used in circomlib's PointBits templates and circomlibjs's packPoint and unpackPoint methods.
For a given point
P=(X,Y)P = (X, Y)
, the compressed encoding is the pair
(s,Y)(s, Y)
, where
ss
 is a single bit representing the "sign" (
11
 means negative) of
XX
, and a field element
x∈Fpx \in \mathbb{F}_p
 is considered "negative" if
x>p−12x \gt \frac{p - 1}{2}
.
To decompress a pair
(s,Y)(s, Y)
, we do the following:
  1. 1.
    check that
    ss
     and
    YY
     are well-formed.
  2. 2.
    compute
    X2=1−Y2A−DY2X^2 = \frac{1 - Y^2}{A - DY^2}
    , where
    AA
     and
    DD
     are Baby Jubjub's curve parameters
  3. 3.
    check that the square root exists. If it doesn't, the pair does not represent a valid curve point.
  4. 4.
    if the square root is
    00
    , assert that
    ss
     is also
    00
    . Otherwise, the pair is an invalid encoding
  5. 5.
    otherwise, there will be two square roots - return the one whose "sign" matches
    ss
    :
    1. 1.
      compute one of them and call it
      XX
      .
    2. 2.
      compute the sign
      s′s'
       of
      XX
      by comparing with
      p−12\frac{p-1}{2}
      ​
    3. 3.
      if
      s′=ss' = s
      , return
      XX
      . Otherwise, return
      p−Xp-X
      .
We encode
(s,Y)(s, Y)
 pairs into a 255-bit value as the sign bit followed by the binary representation of
YY
, which is 254-bits. In code:
function encodePair(signBit: bool, y: uint256) returns (uint256) {
return uint256(signBit) << 254 | y
}
Note that the compressed encoding does not fit in a field element, even though it does fit in a uint256. Therefore it is (for the most part) not used in-circuit.

Asset Encoding

We define an Asset by the following struct:
struct Asset {
// an enum representing the type of the asset
AssetType assetType,
// a 160-bit address
address assetAddr,
// the "ID" of the asset. This is only relevant for ERC721 and ERC1155
uint256 assetId,
}
​
enum AssetType {
// maps to integer value `0`
ERC20,
// maps to integer value `1`
ERC721,
// maps to integer value `2`
ERC1155
}
To represent the asset using only valid elements of
Fp\mathbb{F}_p
, we transform it into the following form:
struct EncodedAsset {
// the asset address with the top-3 bits of `assetId`
// and `assetType` packed into it
uint254 encodedAssetAddr;
// the bottom 253 bits of `assetId`
uint254 encodedAssetId;
}
  1. 1.
    encodedAssetId is the number represented by the 253 least-significant bits of assetId.
  2. 2.
    encodedAssetAddr is defined as the number represented by the following bits concatenated together, read from most-significant to least-significant (i.e. in big-endian order):
    • 3 0 bits
    • the 3 most-significant bits of assetId
    • 88 bits that are left unspecified (currently they are ignored)
    • 2 bits representing assetType - 00 for ERC20, 01 for ERC721, 10 for ERC1155.
    • 160 bits representing assetAddr.

Note Encoding

We define the Note and EncodedNote structs as follows:
struct Note {
// an anonymous stealth address for the note's owner
CompressedStealthAddress owner;
// a nonce that must be a valid element of the BN254 Scalar field
uint256 nonce;
// the asset the note is for
Asset asset;
// the amount of value in `asset` the note "holds"
// this must be less than 2^252
uint256 value;
}
​
struct CompressedStealthAddress {
// the compressed encoding of the first component of the stealth address
uint256 h1;
// the compressed encoding of the second component of the stealth address
uint256 h2;
}
​
struct StealthAddress {
// the X coordinate of the first component of the stealth address
uint256 h1X;
// the Y coordinate of the first component of the stealth address
uint256 h1Y;
// the X coordinate of the second component of the stealth address
uint256 h2X;
// the Y coordinate of the second component of the stealth address
uint256 h2Y
}
​
struct EncodedNote {
StealthAddress owner;
// same as above
uint256 nonce;
// pull out from EncodedAsset
uint256 encodedAssetAddr;
// pull out from EncodedAsset
uint256 encodedAssetId;
// same as above
uint256 value;
}
Within Nocturne, all amounts and balances are forced by the contracts and circuits to be 252-bit integers. This ensures it's impossible to overflow the field.
The StealthAddress struct is a "flattened" form of a stealth address. If we recall that a stealth address is pair of Baby Jubjub curve elements
(H1,H2)∈G2(H_1, H_2) \in \mathbb{G}^2
, h1X, h1Y, h2X, and h2Y are the
XX
 and
YY
 coordinates of
H1H_1
 and
H2H_2
 respectively. The CompressedStealthAddress struct is the "compressed" form of a stealth address, where the two components
H1,H2H_1, H_2
 are represented using compressed point encoding (see above).
The encoding process for a Note is:
  1. 1.
    encode the asset
  2. 2.
    decompress the stealthAddress field
  3. 3.
    pull out the encodedAssetAddr and encodedAssetId fields.
Protocol Details - Previous
Signatures
Next - Protocol Details
Commitment Tree
Last modified 3mo ago