Immutable Ledger Design

---

Title: Immutable Ledger Design

Status: Proposed

Authors: - Alex Pozhylenkov alex.pozhylenkov@iohk.io

Created: 2024-08-19

---

Abstract

This document describes a specification of the immutable ledger for various purposes of project "Catalyst".

Motivation

Project "Catalyst" requires a solution for storing people votes and any other data, in a transparent, verifiable, scalable and immutable way.

Specification

Ledger structure

Ledger will be represented as a collection of distinct, unconnected chains, processed and run in parallel. The only common thing for all these chains will be a "tree" identifier, so these chains will serve and form an overall ledger state.

Obviously, given approach leads to data duplication, as each chain, will not know anything about others. And it also requires that the overall ledger state, could be deterministically defined at any point of time, considering potential transaction overlapping or duplication.

To achieve an immutability of data inside each chain Each particular chain, will be a common sequence of blocks. To achieve an immutability of data inside each chain, cryptographic hashing is applied. So each block from the chain reference to the hash of previous one. It is a widely used technic to prevent a modification of some data from previous blocks, without affecting structure of the current one.

The described approach allows to easily scale and increase throughput of the network on demand at any time, just by starting to process new chains.

Temporary chains

It's a common thing for blockchains to have a starting block (genesis), but it's unusual to have a final block for a chain. After which no any block could be produced.

And that's a main distinguish for this Immutable Ledger design, it has a final block.

So any chain will be bounded by some period of time. Which is well suited where it comes to process some temporary event e.g. voting.

Block structure

Block CDDL definition: block.cddl

block = [
    block-header,
    block-data,
    validator-signature,
]

block-header = [
    chain-id: ULID,
    height: int,
    timestamp: #6.1(uint .ge 1722470400), ; Epoch-based date/time
    prev-block-id: hash-bytes, ; hash of the previous block
    ?ledger-type: UUID,
    ?purpose-id: ULID / UUID,
    ?validator,
    ~metadata,
]

block-data = encoded-cbor

UUID = #6.37(bytes) ; UUID type
ULID = #6.32780(bytes) ; ULID type

kid = hash-bytes ; hash of the x509/c509 certificate

validator = (kid / [2* kid])
metadata = [ *any ]

validator-signature = (bytes / [2* bytes])

;# include hash

Header:

• chain-id - unique identifier of the chain.
• height - block's height. Also is used to identify the block type: genesis, regular, final (in more details described in validation section).
• timestamp - block's timestamp.
• prev-block-id - previous block hash.
• ledger-type - unique identifier of the ledger type. In general, this is the way to strictly bound and specify block-data of the ledger for the specific ledger-type. But such rules will be a part of the specific ledger type definition, and not specified by this document.
• purpose-id - unique identifier of the purpose. As it was stated before, each Ledger instance will have a strict time boundaries, so each of them will run for different purposes. This is the way to distinguish them.
• validator - identifier or identifiers of the entity who was produced and processed a block.
• metadata - fully optional field, to add some arbitrary metadata to the block.

Block:

• block-header - block header described above,
• block-data - an array of some CBOR encoded data
• validator-signature - a signature or signatures of the validator's.

Block validation rules

• chain-id MUST be the same as for the previous block (except for genesis).
• height MUST be incremented by 1 from the previous block height value (except for genesis and final block). Genesis block MUST have 0 value. Final block MUST hash be incremented by 1 from the previous block height and changed the sign to negative. E.g. previous block height is 9 and the Final block height is -10.

• Final block is the last one for the specific chain and any other block could not be referenced to the Final one.

• timestamp MUST be greater or equals than the timestamp of the previous block (except for genesis).

• prev-block-id MUST be a hash of the previous block bytes (except for genesis).

• ledger-type MUST be the same as for the previous block if present (except for genesis). MANDATORY field for Genesis and Final blocks.

• purpose-id MUST be the same as for the previous block if present (except for genesis). MANDATORY field for Genesis and Final blocks.
• validator MUST be the same as for the previous block if present (except for genesis). MANDATORY field for Genesis and Final blocks.
• prev-block-id's CBOR tag value and bstr size MUST be the same as for the previous block (except for genesis). Means that the hash function type and hash size itself must be the same.

• prev-block-id and validator-signature MUST use the same hash function, defined with the hash-bytes.

• prev-block-id for the Genesis block MUST be a hash of the genesis-to-prev-hash bytes.

• block-data MUST be a deterministically encoded CBOR.

Genesis to previous block hash CDDL definition: genesis-to-prev-hash.cddl

genesis-to-prev-hash = [
    chain-id: ULID,
    timestamp: #6.1(uint .ge 1722470400), ; Epoch-based date/time
    ledger-type: UUID,
    purpose-id: ULID / UUID,
    validator,
]

UUID = #6.37(bytes) ; UUID type
ULID = #6.32780(bytes) ; ULID type

validator = (kid / [2* kid])
kid = hash-bytes ; hash of the x509/c509 certificate

;# include hash

Signature rules

validator-signature MUST be a signature of the hashed block-header bytes and the block-data bytes (with the order the same as defined for block). Signed by the validator's keys defined in the corresponding certificates referenced by the validator. Signature algorithm is defined by the certificate. The format and size of this field MUST be totally the same as validator field:

• if validator is only one id => validator-signature contains only 1 signature;
• if validator is array => validator-signature contains an array with the same length;
• order of signatures from the validator-signature's array corresponds to the validators order of validator's array.

Rationale

Path to Active

Acceptance Criteria

Implementation Plan