:ModifiedMerklePatriciaTree


Label

Merkle Patricia Tree

Description

Merkle Patricia trees provide a cryptographically authenticated data structure that can be used to store all (key, value) bindings, although for the scope of this paper we are restricting keys and values to strings (to remove this restriction, just use any serialization format for other data types). They are fully deterministic, meaning that a Patricia tree with the same (key,value) bindings is guaranteed to be exactly the same down to the last byte and therefore have the same root hash, provide the holy grail of O(log(n)) efficiency for inserts, lookups and deletes, and are much easier to understand and code than more complex comparison-based alternatives like red-black trees.

Usage

Instances of :ModifiedMerklePatriciaTree can have the following properties:

PROPERTYTYPEDESCRIPTIONRANGE
From class owl:Thing
:AccountDataProperty owl:DatatypeProperty Groups all data properties that are specific to an account. owl:Thing
:AccountObjectProperty owl:ObjectProperty Groups all EthOn account object properties owl:Thing
:BlockDataProperty owl:DatatypeProperty Groups all data properties that are specific to a block. These properties are usually functional because a block can only be associated with a single instance of them. owl:Thing
:BlockObjectProperty owl:ObjectProperty Groups all EthOn block object properties owl:Thing
:EthOnAnnotationProperty owl:AnnotationProperty Superclass of all EthOn specific annotation properties. owl:Thing
:EthOnDataProperty owl:DatatypeProperty Groups all data properties specific to EthOn. owl:Thing
:EthOnObjectProperty owl:ObjectProperty Groups all EthOn object properties owl:Thing
:MessageDataProperty owl:DatatypeProperty Groups all EthOn message data properties. owl:Thing
:MessageObjectProperty owl:ObjectProperty Groups all EthOn message object properties. owl:Thing
:NetworkDataProperty owl:DatatypeProperty Groups all EthOn network data properties. owl:Thing
:NetworkObjectProperty owl:ObjectProperty Groups all EthOn network object properties. owl:Thing
:StateDataProperty owl:DatatypeProperty -- owl:Thing
:StateObjectProperty owl:ObjectProperty Groups all EthOn state object properties. owl:Thing
:createsPostMsgState owl:FunctionalProperty Relates a message to the global state of the system after all the message has been executed. owl:Thing
:hasAccountStorage owl:FunctionalProperty Relates an account to the Merkle Patricia tree that encodes its storage contents at a certain account state. This property is Functional because an account state can have only one instance of account storage and inverse functional because an account storage can have only one associated account state. :AccountStorage
:hasTransition owl:ObjectProperty Relates a state to a transition (i.e. a message) that creates a new state. owl:Thing
:partOf owl:ObjectProperty This is a general relation to express part of relationships. The classic study of parts and wholes, mereology, has three axioms: 1. the part-of relation is Transitive - "parts of parts are parts of the whole" - If A is part of B and B is part of C, then A is part of C Reflexive - "Everything is part of itself" - A is part of A Antisymmetric - "Nothing is a part of its parts" - if A is part of B and A != B then B is not part of A. owl:Thing
:simpleDefinition owl:AnnotationProperty This property relates an EthOn class to a definition in Simple English, intended especially for non-technical users. owl:Thing
:suggestedStringRepresentation owl:AnnotationProperty This property relates an EthOn class with a suggested string representation. It can be used to give the term a name, e.g. in program code. owl:Thing

Implementation

@prefix : <http://ethon.consensys.net/> .
@prefix ns: <http://www.w3.org/2003/06/sw-vocab-status/ns#> .
@prefix owl: <http://www.w3.org/2002/07/owl#> .
@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .

:ModifiedMerklePatriciaTree a owl:Class ;
    rdfs:label "Merkle Patricia Tree"@en ;
    :suggestedStringRepresentation "ModifiedMerklePatriciaTree"@en ;
    rdfs:comment "Merkle Patricia trees provide a cryptographically authenticated data structure that can be used to store all (key, value) bindings, although for the scope of this paper we are restricting keys and values to strings (to remove this restriction, just use any serialization format for other data types). They are fully deterministic, meaning that a Patricia tree with the same (key,value) bindings is guaranteed to be exactly the same down to the last byte and therefore have the same root hash, provide the holy grail of O(log(n)) efficiency for inserts, lookups and deletes, and are much easier to understand and code than more complex comparison-based alternatives like red-black trees."@en ;
    rdfs:seeAlso <https://github.com/ethereum/wiki/wiki/Patricia-Tree> ;
    ns:term_status "unstable" .