# Encodings

### 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](https://github.com/iden3/circomlib/blob/cff5ab6288b55ef23602221694a6a38a0239dcc0/circuits/pointbits.circom#L136) and circomlibjs's [`packPoint` and `unpackPoint` methods](https://github.com/iden3/circomlibjs/blob/4f094c5be05c1f0210924a3ab204d8fd8da69f49/src/babyjub.js#L97).

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:

```solidity
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&#x20;

We define an `Asset` by the following struct:

```solidity
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:

```solidity
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:

<pre class="language-solidity"><code class="lang-solidity">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;
}

<strong>struct StealthAddress {
</strong>  // 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;
}
</code></pre>

*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](https://nocturne-xyz.gitbook.io/nocturne/keys-and-key-derivation#addresses). 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](https://nocturne-xyz.gitbook.io/nocturne/keys-and-key-derivation#addresses), 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.&#x20;