Skip to content

Latest commit

 

History

History
264 lines (188 loc) · 17.5 KB

lip-0065.md

File metadata and controls

264 lines (188 loc) · 17.5 KB
LIP: 0065
Title: Introduce events and add events root to block headers
Author: Alessandro Ricottone <[email protected]>
        Mehmet Egemen Albayrak <[email protected]>
Discussions-To: https://research.lisk.com/t/introduce-events-and-add-events-root-to-block-headers/342
Status: Draft
Type: Standards Track
Created: 2022-05-03
Updated: 2023-01-10
Requires: 0039, 0055

Abstract

In this LIP, we introduce a mechanism to emit events from the application domain during the block processing. These events are included in a sparse Merkle tree, whose root, the event root, is added as a new property to block headers. Using the event root, it is possible to provide inclusion or non-inclusion proofs for events, proving whether an event was emitted during the block processing.

Copyright

This LIP is licensed under the Creative Commons Zero 1.0 Universal.

Motivation

Currently in the Lisk protocol, once a transaction has been included in a block, its effect is completely determined by the data inside of it. However, there are several cases in which this may not be the case anymore:

  • The result of advanced transactions might depend on the state at the moment of execution, e.g. the conversion rate at which a swap in a DEX is executed, and cannot be read only from the transaction data.
  • In the Lisk interoperability solution the effect of a cross-chain message that is part of a cross-chain update included in a block, does not necessarily depend only on its data: In some cases, the cross-chain message can be returned or its execution can fail.
  • After the implementation of LIP 0055, transactions can fail, i.e. their execution can trigger an error but the transaction is still included in the block.

Furthermore, some state transitions, like assigning the block reward to the block generator, are not induced by transactions but by the block header itself. In all these scenarios, the extra information about the execution of state transitions can be included in events, on-chain data emitted during the processing of a block. Front-end products can query the blockchain for the existence of a certain event and use the information contained to enrich the user experience.

Events do not need to be explicitly included in the block (like, e.g., transactions), but can be rather authenticated collectively in the block header. This authentication mechanism can be used to ensure that a specific event has been emitted during the block processing, e.g. it can prove a cross-chain payment has been processed successfully.

Rationale

Event Data Structure

Events follow a generic structure, storing the module and the event names along with a nested data property. Every module defines its events and the schemas used to serialize and deserialize the data property. The only restriction, which is globally imposed, is a maximum size of serialized events. This is to ensure that events can always be exchanged easily over the network.

Events have the following properties:

  • module: A string indicating the module that emits the event.
  • name: A string indicating the name of the event.
  • data: A byte value. This property contains extra information regarding the event. Each module defines the schemas used for serialization and deserialization.
  • topics: An array of byte values. The event is inserted in the sparse Merkle tree once for each entry in this array.
  • height: The height of the block in which the event was emitted. Together with the index, it uniquely identifies an event within a blockchain.
  • index: An integer counter (unique within a block) indicating how many events were emitted before the current one.

Event Tree

Events are emitted during application domain stages of the block processing and are inserted in a sparse Merkle tree as new leaf nodes. The leaf values are set to the hash of the serialized events. Leaf keys are given by the concatenation of a generic byte value and an index that identifies the position in which the event was emitted during the block processing. In particular, each event specifies an array of topics (similar to the 'indexed' keyword used in Solidity). The same event is inserted multiple times in the sparse Merkle tree, once for each entry in this array. By default, the indexed topics array contains the ID of the transaction that emitted the event or a constant placeholder for events emitted during the processing of the block header. However, events emitted during the processing of a cross-chain message contain the ID of the cross-chain message as default topic instead of the ID of the cross-chain update transaction that contained the cross-chain message.

This pattern allows efficient (non-)inclusion proofs for a variety of use cases, while at the same time leaving developers of custom modules the freedom to decide how to index custom events.

Event root

In this LIP we propose to add the root of the event sparse Merkle tree to the block header to allow checking inclusion and non-inclusion of events. The root of the sparse Merkle tree is 32-bytes, therefore resulting in a limited increase of the block-header size.

Default Event

We specify one default event which is emitted at the end of the transaction processing. This event is emitted within the application domain and has module name set to the name of the module to which the transaction belongs and a constant event type. The event data is a Boolean indicating the success of the transaction execution.

Error Handling and Events

If an error is encountered during the processing of a transaction, the transaction fails and the state is reverted to the state snapshot taken before the command execution as defined in LIP 0055. Similarly, all events that were emitted during the command execution should be reverted. Sometimes, however, it is useful to still persist some events even in this case. When emitting an event each module specifies if it should be reverted in case of an error.

Discarded Alternatives

We analyzed three options for authenticating events:

  • Regular Merkle trees
  • Sparse Merkle trees
  • Bloom filters

Regular Merkle Trees

Regular Merkle trees are used to authenticate lists, and the order of the elements in the list matters in calculating the Merkle root. In the Lisk protocol, they are already used to authenticate transactions in the block header via the transactionRoot.

We discarded regular Merkle trees because they do not provide the same flexibility of sparse Merkle trees in terms of non-inclusion proofs.

Bloom Filters

Bloom filters are a probabilistic data structure that can efficiently check for the existence of a certain element in a set. Here efficiently means that no proof is necessary, as it is in the Merkle trees case, and a Verifier can check inclusion directly just by holding the filter value.

Bloom filters have no false negatives, meaning that if an element is not part of the set, it is indicated with certainty in the Bloom filter value. However, they do have a non-zero probability of false positives, where it is possible that the filter value mistakenly indicates inclusion of an element that is not part of the set. This false positive rate increases with the set size.

Another disadvantage is that Bloom filters are in general larger than Merkle roots (for instance, in Ethereum the event Bloom filter has a size of 256 bytes).

To summarize, we chose sparse Merkle trees because:

  • They offer non-inclusion proofs.
  • The root is small in size.
  • An inclusion proof indicates the existence of an event with certainty.

Specification

Constants

Name Type Value Description
MAX_EVENT_SIZE_BYTES integer 16*1024 Maximum size in bytes of a serialized event.
MIN_MODULE_NAME_LENGTH integer 1 Minimum length of a module name.
MAX_MODULE_NAME_LENGTH integer 32 Maximum length of a module name.
MIN_EVENT_NAME_LENGTH integer 1 Minimum length of an event name.
MAX_EVENT_NAME_LENGTH integer 32 Maximum length of an event name.
EMPTY_HASH bytes sha256(b"") Hash of empty bytes.
EVENT_TOPIC_INIT_GENESIS_STATE bytes 0x00 Default topic for events emitted during genesis state initialization.
EVENT_TOPIC_FINALIZE_GENESIS_STATE bytes 0x01 Default topic for events emitted during genesis state finalization.
EVENT_TOPIC_BEFORE_TRANSACTIONS bytes 0x02 Default topic for events emitted before transactions execution.
EVENT_TOPIC_AFTER_TRANSACTIONS bytes 0x03 Default topic for events emitted after transactions execution.
EVENT_NAME_DEFAULT string commandExecutionResult Name of default event emitted at the end of transaction execution.
EVENT_INDEX_LENGTH_BITS integer TBD Length in bits of the index used to calculate events tree leaf keys.
MAX_EVENTS_PER_BLOCK integer 2^EVENT_INDEX_LENGTH_BITS Max number of events emitted per block.
TOPIC_HASH_LENGTH_BYTES integer TBD Output length in bytes of the hash function used to calculate events tree leaf keys.
TOPIC_INDEX_LENGTH_BITS integer 2 Length in bits of the topic index used to calculate events tree leaf keys.
MAX_TOPICS_PER_EVENT integer 2^TOPIC_INDEX_LENGTH_BITS Max number of topics per event.
TOTAL_INDEX_LENGTH_BYTES integer (EVENT_INDEX_LENGTH_BITS+TOPIC_INDEX_LENGTH_BITS)/8 Length in bytes of the concatenation of the event index and the topic index.

Event ID

The event ID is defined as the hash of the serialize event.

def eventID(event: Event) -> bytes:
    return sha256(encode(eventSchema, event))

Event Data Structure

Events are serialized and deserialized using the following JSON schema.

eventSchema = {
    "type": "object",
    "required": ["module", "name", "data", "topics", "height", "index"],
    "properties": {
        "module": {
            "dataType": "string",
            "minLength": MIN_MODULE_NAME_LENGTH,
            "maxLength": MAX_MODULE_NAME_LENGTH,
            "fieldNumber": 1
        },
        "name": {
            "dataType": "string",
            "minLength": MIN_EVENT_NAME_LENGTH,
            "maxLength": MAX_EVENT_NAME_LENGTH,
            "fieldNumber": 2
        },
        "data": {
            "dataType": "bytes",
            "fieldNumber": 3
        },
        "topics": {
            "type": "array",
            "fieldNumber": 4,
            "items": {
                "dataType": "bytes"
            }
        },
        "height": {
            "dataType": "uint32",
            "fieldNumber": 5
        },
        "index": {
            "dataType": "uint32",
            "fieldNumber": 6
        }
    }
}

The maximum size of a serialized event is MAX_EVENT_SIZE_BYTES.

module, name, and data

The module property corresponds to the module to which the event belongs. Each event has a name and JSON schema used to serialize and deserialize the data property. The name is a string of length at most MAX_EVENT_NAME_LENGTH. The value EVENT_NAME_DEFAULT is reserved for the default event and cannot be assigned.

Both module and name must be alphanumeric strings (lower and upper case characters allowed).

topics

The event topics is an array of unique byte values whose length ranges between 1 and MAX_TOPICS_PER_EVENT.

By default, the first topic is set to:

  • the transaction ID, for events emitted during the transaction processing stages,
  • the cross-chain message ID, for events emitted during the cross-chain message processing stages,
  • the constant EVENT_TOPIC_INIT_GENESIS_STATE, for events emitted during the 'genesis state initialization' stage,
  • the constant EVENT_TOPIC_FINALIZE_GENESIS_STATE, for events emitted during the 'genesis state finalization' stage,
  • the constant EVENT_TOPIC_BEFORE_TRANSACTIONS, for events emitted during the 'before transactions execution' stage,
  • or the constant EVENT_TOPIC_AFTER_TRANSACTIONS, for events emitted during the 'after transactions execution' stage.

An event emitted during transaction processing cannot have any of these default values in the topics array.

height

The event height is an integer set to the height of the block in which the event was emitted.

index

The event index is an integer between 0 and MAX_EVENTS_PER_BLOCK - 1, set to the number of events that were previously emitted in the same block. As a consequence, during the execution of a single block, at most MAX_EVENTS_PER_BLOCK events can be emitted.

Error Handling and Events

For events emitted during the command execution, modules specify whether the event is reverted or not in case of error (i.e., whether it is included in the events tree or not). In all other application domain stages errors cannot occur in a valid block (thus, also state changes are never reverted) so that it is not necessary to specify if the event is revertible.

Events Tree

Events are inserted into the events tree once for each entry in the event topics array. The leaf key is the concatenation of the hash of the element in the topics array, the event index converted to a binary string of length EVENT_INDEX_LENGTH_BITS and concatenated with the topic index of TOPIC_INDEX_LENGTH_BITS bits (corresponding to the entry in the topics array), for a total of TOTAL_INDEX_LENGTH_BYTES bytes. The leaf value is the SHA-256 hash of the serialization of the event properties using the eventSchema given above.

In summary, for each event one key-value pair is added to the events tree for each entry topic in the associated topics array, where:

  • key = sha256(topic)[:TOPIC_HASH_LENGTH_BYTES] + ((event index << TOPIC_INDEX_LENGTH_BITS) + topic index).to_bytes(TOTAL_INDEX_LENGTH_BYTES, byteorder="big")
  • value = sha256(encode(eventSchema, event)).

Event Root

In this LIP we introduce a new block header property, eventRoot. The events root at a certain height h, eventRoot(h), is the root of the sparse Merkle tree computed from all key-value pairs of all events emitted from the block at height h (the events tree). A block header without any events has only one empty node in the events tree therefore the event root equals the EMPTY_HASH.

Default Event

Each module defines a default event indicating the result of a transaction processing, with the following properties:

  • module: The name of the module of the command executed by the transaction.
  • name: The constant EVENT_NAME_DEFAULT.
  • topics: An array containing only the transaction ID.
  • data: A Boolean value set to true if the transaction was processed successfully, false otherwise. The event data JSON schema is given below.
defaultEventDataSchema = {
    "type": "object",
    "required": ["success"],
    "properties": {
        "success": {
            "dataType": "bool",
            "fieldNumber": 1
        }
    }
}

This event is emitted automatically for every transaction after the "after command execution" block processing stage.

Emitting Events

We define the following notation to emit events during the block processing.

  • emitEvent(module: str, name: str, data: object, topics: list[bytes]): emit an event and add it to the events tree as explained above. The event index and the relevant default topic are added automatically. The data property is serialized according to the schema corresponding to the given name.
  • emitPersistentEvent(module: str, name: str, data: object, topics: list[bytes]): emit an event and add it to the events tree as explained above. The event index and the relevant default topic are added automatically. The data property is serialized according to the schema corresponding to the given name. If the event is emitted during the command execution stage, it is not removed from the events tree if the command execution fails. Otherwise, it works exactly as emitEvent.

Backwards Compatibility

This LIP, and in general the new block header proposed in LIP 0055, results in a hard fork as nodes following the proposed protocol will reject blocks according to the previous protocol, and nodes following the previous protocol will reject blocks according to the proposed protocol.