:ModifiedMerklePatriciaTree

owl:Thing
- :ModifiedMerklePatriciaTree

URI

http://ethon.consensys.net/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:

PROPERTY	TYPE	DESCRIPTION	RANGE
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" .