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)$, the compressed encoding is the pair $(s, Y)$, where $s$ is a single bit representing the "sign" ($1$ means negative) of $X$, and a field element $x \in \mathbb{F}_p$ is considered "negative" if $x \gt \frac{p - 1}{2}$.

To decompress a pair $(s, Y)$, we do the following:

1. check that $s$ and $Y$ are well-formed.

2. compute $X^2 = \frac{1 - Y^2}{A - DY^2}$, where $A$ and $D$ are Baby Jubjub's curve parameters

3. check that the square root exists. If it doesn't, the pair does not represent a valid curve point.

4. if the square root is $0$, assert that $s$ is also $0$. Otherwise, the pair is an invalid encoding

5. otherwise, there will be two square roots - return the one whose "sign" matches $s$:

   1. compute one of them and call it $X$.

   2. compute the sign $s'$ of $X$ by comparing with $\frac{p-1}{2}$

   3. if $s' = s$, return $X$. Otherwise, return $p-X$.

We encode $(s, Y)$ pairs into a 255-bit value as the sign bit followed by the binary representation of $Y$, 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 $\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. encodedAssetId is the number represented by the 253 least-significant bits of assetId.

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 $(H_1, H_2) \in \mathbb{G}^2$, h1X, h1Y, h2X, and h2Y are the $X$ and $Y$ coordinates of $H_1$ and $H_2$ respectively. The CompressedStealthAddress struct is the "compressed" form of a stealth address, where the two components $H_1, H_2$ are represented using compressed point encoding (see above).

The encoding process for a Note is:

1. encode the asset

2. decompress the stealthAddress field

3. pull out the encodedAssetAddr and encodedAssetId fields.