Comment on page

# Encodings

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

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.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`

.

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.

Last modified 3mo ago