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

  • AiA_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 kk leafs L1,L2,...,LkL_1, L_2, ..., L_k where each leaf is assigned an exclusive allotment AiA_i and the total allotment Atot=n=1kAnA_{tot} = \sum_{n=1}^{k}{A_n}. Each leaf is assigned the interval Ii=[n=0i1An,n=0iAn] I_i = [\sum_{n=0}^{i-1}{A_n}, \sum_{n=0}^{i}{A_n}]

With A0=0A_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 AtotA_{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

Other Implementations

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

History

All content herein is licensed under GPL License.

results matching ""

    No results matching ""