http://ethon.consensys.net/ModifiedMerklePatriciaTree
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.
Instances of :ModifiedMerklePatriciaTree can have the following properties:
| PROPERTY | TYPE | DESCRIPTION | RANGE |
|---|---|---|---|
| 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 |
| :conformsTo | owl:ObjectProperty | Relates an Ethereum concept to the Ethereum protocol variant it conforms to. | 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 |
| :DASE_RULE | owl:AnnotationProperty | 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 |
| :from | owl:ObjectProperty | Relates a message to the account it originates from. | 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 |
| :hasReceiptsTrie | owl:FunctionalProperty | Relates a block to the trie that contains the block's receipt data. | owl:Thing |
| :hasTransition | owl:ObjectProperty | Relates a state to a transition (i.e. a message) that creates a new state. | owl:Thing |
| :knowsOfUncle | owl:ObjectProperty | Relates a block to a known uncle. | 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 |
| swrla:isRuleEnabled | owl:AnnotationProperty | owl:Thing | |
@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> ;
rdfs:subClassOf :EthOnConcept ;
ns:term_status "unstable" .