## Synopsis

The NOCUST system relies on cryptographic primitives such as hash functions and digital signatures. Further, it requires a specific encoding. The goal of this document is to describe the standards used and to serve as a reference for implementers.

### Motivation

Reference specification of the cryptographic functions used in the NOCUST system.

### Definitions

- $A_i$: Allotment of a leaf of an interval tree.

### Desired Properties

Deterministic signatures and checksums with hash functions

## Technical Specification

### Checksums

The NOCUST protocol requires to generate checksums over Tuples of variables. It will be used over the data structures defined in NSPEC005 (Active state, Transfers, Merkle tree nodes, etc..).

#### Encoding

Prior to the checksum a specific encoding MUST be required. The encoding depends on the type of the variable. The possible types are those defined in the solidity language, see the Solidity documentation. The encoding MUST correspond to the Non-standard Packed Mode defined by Solidity:

- The types shorter than 32 bytes are neither zero padded nor extended.
- Dynamic types are encoded in-place and without the length.
- Array elements are padded, but still encoded in-place.

**Example:**

Let's encode the following tuple composed of a `int16`

, a `bytes1`

, a `uint16`

, and a `string`

Solidity Type | Value | Bytes |
---|---|---|

`int16` |
-1 | 0xffff |

`bytes1` |
0x42 | 0x42 |

`uint16` |
3 | 0x0003 |

`string` |
"Hello, world!" | 0x48656c6c6f2c20776f726c6421 |

The encoded result would be: `0xffff42000348656c6c6f2c20776f726c6421`

For more details about Non-standard Packed encoding mode please refer to the solidity documentation.

#### Checksums

The function used MUST be `Keccak-256`

(SHA-3 variant) commonly used in Ethereum. The output from the previous encoding function is fed into the hash function to create the checksum.

We define the `checksum`

function taking as input a tuple of variables, and return the 32 bytes checksum:

```
function checksum(tuple: object) : Bytes32
```

Further, in the NOCUST specifications, we will detail the tuples interface to checksum using the Typescript syntax. To signal that a data structure is used for a checksum we extend it by the `Checksumable`

type. Note that in that case the order of the arguments in the interface matters for the resulting checksum.

Example:

```
// Define the interface
interface Account extends Checksumable {
owner: string
balance: Uint256
}
// Calculate the checksum of Bob Account
var accountChecksum = checksum({
owner: "Bob"
balance: new Uint256(1000)
})
```

### Signatures

Digital signatures are crucial when implementing a commit-chain like NOCUST. Prior to the signing/verification we MUST add a wrapper that requires to prepend to the message to sign the string `\x19Liquidity.Network Authorization:\n32`

and using the checksum function. A second wrapper MUST be applied; the standard wrapper for Ethereum signatures. It will prepend the message `\x19Ethereum Signed Message:\n32`

and Checksums.

```
function signatureWrapper(messageChecksum: Bytes32): Bytes32 {
return checksum("\x19Ethereum Signed Message:\n32" +
checksum("\x19Liquidity.Network Authorization:\n32" + messageChecksum)
)
}
```

Note that `\x19`

represent the End of Medium control character.

The signature scheme used is the standard secp256k1 curve with ECDSA (common scheme in Ethereum and available in Solidity). The signature consists of 3 parameters commonly known as `R`

(32 bytes), `S`

(32 bytes), `V`

(1 bytes). The `NOCUSTAuthorization`

data structure consists of `R`

, `S`

, `V`

parameters with a `checksum`

outputted from the `signatureWrapper`

and the signing address.

```
interface NOCUSTAuthorization {
checksum: Bytes32
address: Address
R: Bytes32
S: Bytes32
V: Bytes1
}
```

We define the verification and signing function as followed:

```
function sign(checksum: Bytes32): NOCUSTAuthorization
function verifySignature(signature: NOCUSTAuthorization) : Address
```

We will call the `RSV`

value the string concatenation of the hexadecimal values of `R`

, `S`

and `V`

in this order.

### Merkle trees

NOCUST makes extensive use of Merkle trees. We present here how Merkle trees are constructed.

Each node in the tree MUST be a result of the checksum of the following tuple:

```
interface MerkleTreeNode {
height: Uint32
leftChild: Bytes32
rightChild: Bytes32
}
```

The `height`

of a node is the number of edges from the node to a leaf. A leaf node will have a height of 0. `leftChild`

and `rightChild`

are the 2 underneath children. The Merkle tree is obtained by recursively calculating the intermediary nodes.

The Merkle proof that allows verifying the inclusion of a leaf at index `leafIndex`

and of checksum `leafChecksum`

within the tree is:

```
interface MerkleProof {
root: Bytes32
path: Bytes32[]
leafIndex: Uint64
leafChecksum: Bytes32
}
```

The algorithm to validate such proof is:

```
let nodeIndex = leafIndex
let node = leafChecksum
for (let i = 0; i < path.length; i++) {
let linkLeft = false
if (nodeIndex > 0) {
linkLeft = nodeIndex % 2 == 1
nodeIndex = Math.floor(nodeIndex / 2);
}
node = checksum({
i,
linkLeft ? path[i] : node,
linkLeft ? node : path[i],
})
}
assert(node === root)
```

The root checksum for an empty tree is `0x00000000000000000000000000000000`

and the root checksum for a set with a single element is the checksum of its only leaf.

### Interval trees

Interval trees are Merkle trees with additional interval data on each node. Each leaf is assigned an interval (typically, in NOCUST the interval correspond to the balance allotment).

Given an ordered set of $k$ leafs $L_1, L_2, ..., L_k$ where each leaf is assigned an exclusive allotment $A_i$ and the total allotment $A_{tot} = \sum_{n=1}^{k}{A_n}$. Each leaf is assigned the interval $I_i = [\sum_{n=0}^{i-1}{A_n}, \sum_{n=0}^{i}{A_n}]$

With $A_0 = 0$.

In the remainder of the section we will call the lower bound of this interval the `left`

value and the upper bound of this interval the `right`

value.

Each node in the tree is the result of the checksum of the following model:

```
interface IntervalTreeNode extends Checksumable {
height: Uint32
left: Uint256
innerNode: Bytes32
right: Uint256
}
```

The `height`

of a node is the number of edges from the node to a leaf. A leaf node will have a height of 0.
`left`

is equal to the lower bound of the interval and `right`

is equal to the upper one.

`innerNode`

is the checksum of the following model:

```
interface IntervalTreeNodeInnerNode extends Checksumable {
leftChild: Bytes32
middle: Uint256
rightChild: Bytes32
}
```

Where `leftChild`

and `rightChild`

are the 2 underneath children of the node and the `middle`

is the value between the 2 children intervals.

Finally, if the node is a leaf we take the checksum of the following model instead of `IntervalTreenode`

.

```
interface IntervalTreeLeafNode extends Checksumable {
left: Uint256
leafChecksum: Bytes32
right: Uint256
}
```

`leafChecksum`

is the checksum of the of the leaf data (Account or transfer).

The root checksum for an empty tree is `0x00000000000000000000000000000000`

and the root checksum for a tree with a single element is the checksum of its only leaf.

**Example:**

For the `left`

, `right`

, and `middle`

values.

```
Root
/ \
A B
/ \ / \
C D E F
Account balance: 5 6 1 3
Account offset: 0 5 11 12
Interval: 0;5 5;11 11;12 12;15
```

node/value | `left` |
`right` |
`middle` |
---|---|---|---|

Root | 0 | 15 | 11 |

A | 0 | 11 | 5 |

B | 11 | 15 | 12 |

C | 0 | 5 | N/A |

D | 5 | 11 | N/A |

E | 11 | 12 | N/A |

F | 12 | 15 | N/A |

The proof guaranteeing the exclusive allotment and the leaf inclusion to the set is:

```
interface ProofOfExclusiveAllotement {
root: Bytes32 // Expected root
path: Bytes32[] // Left or right child along the path
pathValues: Uint256[] // Missing left or right value along the path
left: Uint256 // Left value of the leaf
right: Uint256 // Right value of the leaf
leafIndex: Uint64
leafChecksum: Bytes32
totalAllotement: // Sum of all allotements
}
```

`leafIndex`

MUST be the index of the leaf in the interval tree.

`totalAllotement`

is $A_{tot}$

The algorithm to validate such proof:

```
let node = leafChecksum
let left_i = left
let right_i = right
for (let height = 0; j < length(path); j++) {
const linkLeft = leafIndex % 2 === 1
leafIndex = Math.floor(leafIndex / 2)
node = checksum({
height,
linkLeft ? pathValues[height] : left_j,
checksum({
linkLeft ? path[height] : node, // left child
linkLeft ? left_j : right_j, // middle value
linkLeft ? node : path[height] // right child
}),
linkLeft ? right_j : pathValues[height]
})
left_j = linkLeft ? pathValues[height] : left_j
right_j = linkLeft ? right_j : pathValues[height]
assert(right_j >= left_j)
}
assert(totalAllotement === right_j - left_j)
assert(node === root)
```

At each level in the tree the verifier MUST check that the interval does not intersect. Therefore, `right_j >= left_j`

. `totalAllotement`

MUST be equal to `right_j - left_j`

. Finally, The root and the calculated root MUST match.

## Example Implementation

- Implementation of the checksum function in the operator implementation: https://github.com/liquidity-network/nocust-server/blob/master/operator_api/operator_api/crypto.py#L113
- Implementation of the
`NOCUSTAuthorization`

function in the Python operator server: https://github.com/liquidity-network/nocust-server/blob/master/operator_api/operator_api/crypto.py#L50 - Implementation of the
`NOCUSTAuthorization`

message wrapper in a JS client: https://github.com/liquidity-network/nocust-client-library/blob/release-2.1.2/lib/util.ts#L97-L98 - NOCUST smart -contract Signature verification: https://github.com/liquidity-network/nocust-contracts-solidity/blob/master/contracts/BimodalLib.sol#L401
- Python server Merkle tree implementation: https://github.com/liquidity-network/nocust-server/blob/master/operator_api/operator_api/merkle_tree.py
- Solidity contract Merkle proof verification: https://github.com/liquidity-network/nocust-contracts-solidity/blob/master/contracts/MerkleVerifier.sol

## Other Implementations

Checksum function in web3 JS: https://github.com/ethereum/web3.js/blob/2.x/packages/web3-utils/src/SoliditySha3.js

## History

## Copyright

All content herein is licensed under GPL License.