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)$
, 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. 1.
check that
$s$
and
$Y$
are well-formed.
2. 2.
compute
$X^2 = \frac{1 - Y^2}{A - DY^2}$
, where
$A$
and
$D$
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
$0$
, assert that
$s$
is also
$0$
. Otherwise, the pair is an invalid encoding
5. 5.
otherwise, there will be two square roots - return the one whose "sign" matches
$s$
:
1. 1.
compute one of them and call it
$X$
.
2. 2.
compute the sign
$s'$
of
$X$
by comparing with
$\frac{p-1}{2}$
3. 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,
// 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
// 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
// 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;
}
// 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;
}
// 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 {
// same as above
uint256 nonce;
// pull out from EncodedAsset
// 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. 1.
encode the asset
2. 2.
decompress the stealthAddress field
3. 3.
pull out the encodedAssetAddr and encodedAssetId fields.