: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.

Superclasses (1)

Usage

Instances of :ModifiedMerklePatriciaTree can have the following properties:

PROPERTYTYPEDESCRIPTIONRANGE
From class :EthOnConcept
:simpleDefinition owl:AnnotationProperty This property relates an EthOn concept to a definition in Simple English, intended especially for non-technical users. owl:Thing
:suggestedStringRepresentation owl:AnnotationProperty This property relates an EthOn concept with a suggested string representation. It can be used to give the term a name, e.g. in program code. owl:Thing
From class owl:Thing
:AccountObjectProperty owl:ObjectProperty Groups all EthOn account object properties 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
: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
: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

Implementation

@prefix : <http://ethon.consensys.net/> .
@prefix dc: <http://purl.org/dc/elements/1.1/> .
@prefix ns: <http://www.w3.org/2003/06/sw-vocab-status/ns#> .
@prefix owl: <http://www.w3.org/2002/07/owl#> .
@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix sh: <http://www.w3.org/ns/shacl#> .
@prefix skos: <http://www.w3.org/2004/02/skos/core#> .
@prefix v0: <http://ethon.consensys.net/v0/> .
@prefix vann: <http://purl.org/vocab/vann/> .
@prefix void: <http://rdfs.org/ns/void#> .
@prefix xml: <http://www.w3.org/XML/1998/namespace> .
@prefix xsd: <http://www.w3.org/2001/XMLSchema#> .

: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> ;
    rdfs:subClassOf :EthOnConcept ;
    ns:term_status "unstable" .