Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source
Source file sc_rollup_inbox_repr.ml
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565(*****************************************************************************)(* *)(* Open Source License *)(* Copyright (c) 2021 Nomadic Labs <contact@nomadic-labs.com> *)(* *)(* Permission is hereby granted, free of charge, to any person obtaining a *)(* copy of this software and associated documentation files (the "Software"),*)(* to deal in the Software without restriction, including without limitation *)(* the rights to use, copy, modify, merge, publish, distribute, sublicense, *)(* and/or sell copies of the Software, and to permit persons to whom the *)(* Software is furnished to do so, subject to the following conditions: *)(* *)(* The above copyright notice and this permission notice shall be included *)(* in all copies or substantial portions of the Software. *)(* *)(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*)(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, *)(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL *)(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*)(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING *)(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER *)(* DEALINGS IN THE SOFTWARE. *)(* *)(*****************************************************************************)(**
A Merkelized inbox represents a list of available messages. This
list is decomposed into sublist of messages, one for each Tezos
level greater than the level of the Last Cemented Commitment
(LCC).
This module is designed to:
1. give a constant-time access to the number of available messages
;
2. provide a space-efficient representation for proofs of inbox
inclusions (only for inboxes obtained at the end of block
validation) ;
3. offer an efficient function to add a new batch of messages in
the inbox at the current level.
To solve (1), we simply maintain the number of available messages
in a field.
To solve (2), we use a proof tree H which is implemented by a merkelized
skip list allowing for compact inclusion proofs
(See {!skip_list_repr.ml}).
To solve (3), we maintain a separate proof tree C witnessing the
contents of messages of the current level.
The protocol maintains the number of available messages, the
hashes of the head of H, and the root hash of C.
The rollup node needs to maintain a full representation for C and a
partial representation for H back to the level of the LCC.
*)typeerror+=Invalid_level_add_messagesofRaw_level_repr.ttypeerror+=Invalid_number_of_messages_to_consumeofint64let()=letopenData_encodinginregister_error_kind`Permanent~id:"sc_rollup_inbox.invalid_level_add_messages"~title:"Internal error: Trying to add an message to an inbox from the past"~description:"An inbox can only accept messages for its current level or for the next \
levels."(obj1(req"level"Raw_level_repr.encoding))(functionInvalid_level_add_messageslevel->Somelevel|_->None)(funlevel->Invalid_level_add_messageslevel);register_error_kind`Permanent~id:"sc_rollup_inbox.consume_n_messages"~title:"Internal error: Trying to consume a negative number of messages"~description:"Sc_rollup_inbox.consume_n_messages must be called with a non negative \
integer."(obj1(req"n"int64))(functionInvalid_number_of_messages_to_consumen->Somen|_->None)(funn->Invalid_number_of_messages_to_consumen)moduleSkip_list_parameters=structletbasis=2endmoduleSkip_list=Skip_list_repr.Make(Skip_list_parameters)typeproof_hash=Context.Proof.hashtypehistory_proof_hash=Context.Proof.hashtypehistory_proof=(proof_hash,history_proof_hash)Skip_list.cellletequal_history_proof=Skip_list.equalContext_hash.equalContext_hash.equallethistory_proof_encoding=Skip_list.encodingContext_hash.encodingContext_hash.encodingletpp_history_prooffmtcell=Format.fprintffmt{|
content = %a
index = %d
back_pointers = %a
|}Context_hash.pp(Skip_list.contentcell)(Skip_list.indexcell)(Format.pp_print_listContext_hash.pp)(Skip_list.back_pointerscell)(*
At a given level, an inbox is composed of metadata of type [t] and
[current_messages], a [tree] representing the messages of the current level
(held by the [Raw_context.t] in the protocol).
The metadata contains :
- [rollup] : the address of the rollup ;
- [level] : the inbox level ;
- [message_counter] : the number of messages in the [level]'s inbox ;
- [nb_available_messages] :
the number of messages that have not been consumed by a commitment cementing ;
- [current_messages_hash] : the root hash of [current_messages] ;
- [old_levels_messages] : a witness of the inbox history.
When new messages are appended to the current level inbox, the
metadata stored in the context may be related to an older level.
In that situation, an archival process is applied to the metadata.
This process saves the [current_messages_hash] in the
[old_levels_messages] and empties [current_messages]. If
there are intermediate levels between [inbox.level] and the current
level, this archival process is applied until we reach the current
level using an empty [current_messages]. See {!MakeHashingScheme.archive}
for details.
*)typet={rollup:Sc_rollup_repr.t;level:Raw_level_repr.t;nb_available_messages:int64;message_counter:Z.t;(* Lazy to avoid hashing O(n^2) time in [add_messages] *)current_messages_hash:unit->Context.Proof.hash;old_levels_messages:history_proof;}letequalinbox1inbox2=(* To be robust to addition of fields in [t]. *)let{rollup;level;nb_available_messages;message_counter;current_messages_hash;old_levels_messages;}=inbox1inSc_rollup_repr.Address.equalrollupinbox2.rollup&&Raw_level_repr.equallevelinbox2.level&&Compare.Int64.(equalnb_available_messagesinbox2.nb_available_messages)&&Z.equalmessage_counterinbox2.message_counter&&Context_hash.equal(current_messages_hash())(inbox2.current_messages_hash())&&equal_history_proofold_levels_messagesinbox2.old_levels_messagesletppfmtinbox=Format.fprintffmt{|
rollup = %a
level = %a
current messages hash = %a
nb_available_messages = %s
message_counter = %a
old_levels_messages = %a
|}Sc_rollup_repr.Address.ppinbox.rollupRaw_level_repr.ppinbox.levelContext_hash.pp(inbox.current_messages_hash())(Int64.to_stringinbox.nb_available_messages)Z.pp_printinbox.message_counterpp_history_proofinbox.old_levels_messagesletinbox_levelinbox=inbox.levelletold_levels_messages_encoding=Skip_list.encodingContext_hash.encodingContext_hash.encodingletencoding=Data_encoding.(conv(fun{rollup;message_counter;nb_available_messages;level;current_messages_hash;old_levels_messages;}->(rollup,message_counter,nb_available_messages,level,current_messages_hash(),old_levels_messages))(fun(rollup,message_counter,nb_available_messages,level,current_messages_hash,old_levels_messages)->{rollup;message_counter;nb_available_messages;level;current_messages_hash=(fun()->current_messages_hash);old_levels_messages;})(obj6(req"rollup"Sc_rollup_repr.encoding)(req"message_counter"n)(req"nb_available_messages"int64)(req"level"Raw_level_repr.encoding)(req"current_messages_hash"Context_hash.encoding)(req"old_levels_messages"old_levels_messages_encoding)))letnumber_of_available_messagesinbox=Z.of_int64inbox.nb_available_messagesletno_messages_hash=Context_hash.hash_bytes[Bytes.empty]letemptyrolluplevel={rollup;level;message_counter=Z.zero;nb_available_messages=0L;current_messages_hash=(fun()->no_messages_hash);old_levels_messages=Skip_list.genesisno_messages_hash;}letconsume_n_messagesn({nb_available_messages;_}asinbox):toptiontzresult=ifCompare.Int.(n<0)thenerror(Invalid_number_of_messages_to_consume(Int64.of_intn))elseifCompare.Int64.(Int64.of_intn>nb_available_messages)thenokNoneelseletnb_available_messages=Int64.(subnb_available_messages(of_intn))inok(Some{inboxwithnb_available_messages})letkey_of_message=Data_encoding.Binary.to_string_exnData_encoding.zmoduletypeMerkelizedOperations=sigtypetreetypemessages=treetypemessage=treetypehistoryvalhistory_encoding:historyData_encoding.tvalpp_history:Format.formatter->history->unitvalhistory_at_genesis:bound:int64->historyvaladd_messages:history->t->Raw_level_repr.t->stringlist->messages->(messages*history*t)tzresultLwt.tvaladd_messages_no_history:t->Raw_level_repr.t->stringlist->messages->(messages*t)tzresultLwt.tvalget_message:messages->Z.t->messageoptionLwt.tvalget_message_payload:messages->Z.t->stringoptionLwt.ttypeinclusion_proofvalpp_inclusion_proof:Format.formatter->inclusion_proof->unitvalnumber_of_proof_steps:inclusion_proof->intvalproduce_inclusion_proof:history->t->t->inclusion_proofoptionvalverify_inclusion_proof:inclusion_proof->t->t->boolendmoduletypeTREE=sigtypettypetreetypekey=stringlisttypevalue=bytesvalfind:tree->key->valueoptionLwt.tvalfind_tree:tree->key->treeoptionLwt.tvaladd:tree->key->value->treeLwt.tvalis_empty:tree->boolvalhash:tree->Context_hash.tendmoduleMakeHashingScheme(Tree:TREE):MerkelizedOperationswithtypetree=Tree.tree=structmoduleTree=Treetypetree=Tree.treetypemessages=treetypemessage=treeletadd_messageinboxpayloadmessages=letmessage_index=inbox.message_counterinletmessage_counter=Z.succinbox.message_counterinletkey=key_of_messagemessage_indexinletnb_available_messages=Int64.succinbox.nb_available_messagesinTree.(addmessages[key;"payload"](Bytes.of_stringpayload))>>=funmessages->letinbox={inboxwithmessage_counter;nb_available_messages}inLwt.return(messages,inbox)letget_messagemessagesmessage_index=letkey=key_of_messagemessage_indexinTree.(find_treemessages[key])letget_message_payloadmessagesmessage_index=letkey=key_of_messagemessage_indexinTree.(findmessages[key;"payload"])>|=Option.mapBytes.to_stringlethash_old_levels_messagescell=letcurrent_messages_hash=Skip_list.contentcellinletback_pointers_hashes=Skip_list.back_pointerscellinletopenContext_hashinList.mapto_bytes(current_messages_hash::back_pointers_hashes)|>hash_bytesmoduleInt64_map=Map.Make(Int64)typehistory={events:history_proofContext_hash.Map.t;sequence:Context_hash.tInt64_map.t;bound:int64;counter:int64;}lethistory_encoding=letopenData_encodinginletevents_encoding=Context_hash.Map.encodinghistory_proof_encodinginletsequence_encoding=conv(funm->Int64_map.bindingsm)(List.fold_left(funm(k,v)->Int64_map.addkvm)Int64_map.empty)(list(tup2int64Context_hash.encoding))inconv(fun{events;sequence;bound;counter}->(events,sequence,bound,counter))(fun(events,sequence,bound,counter)->{events;sequence;bound;counter})(obj4(req"events"events_encoding)(req"sequence"sequence_encoding)(req"bound"int64)(req"counter"int64))letpp_historyfmthistory=Context_hash.Map.bindingshistory.events|>funbindings->letpp_bindingfmt(hash,history_proof)=Format.fprintffmt"@[%a -> %a@]"Context_hash.pphashpp_history_proofhistory_proofinFormat.pp_print_listpp_bindingfmtbindingslethistory_at_genesis~bound={events=Context_hash.Map.empty;sequence=Int64_map.empty;bound;counter=0L;}(** [remember ptr cell history] extends [history] with a new
mapping from [ptr] to [cell]. If [history] is full, the
oldest mapping is removed. If the history bound is less
or equal to zero, then this function returns [history]
untouched. *)letrememberptrcellhistory=ifCompare.Int64.(history.bound<=0L)thenhistoryelseletevents=Context_hash.Map.addptrcellhistory.eventsinletcounter=Int64.succhistory.counterinlethistory={events;sequence=Int64_map.addhistory.counterptrhistory.sequence;bound=history.bound;counter;}inifInt64.(equalhistory.counterhistory.bound)thenmatchInt64_map.min_bindinghistory.sequencewith|None->history|Some(l,h)->letsequence=Int64_map.removelhistory.sequenceinletevents=Context_hash.Map.removeheventsin{counter=Int64.predhistory.counter;bound=history.bound;sequence;events;}elsehistoryletarchive_if_neededhistoryinboxtarget_level=letarchive_levelhistoryinbox=letprev_cell=inbox.old_levels_messagesinletprev_cell_ptr=hash_old_levels_messagesprev_cellinlethistory=rememberprev_cell_ptrprev_cellhistoryinletold_levels_messages=Skip_list.next~prev_cell~prev_cell_ptr(inbox.current_messages_hash())inletlevel=Raw_level_repr.succinbox.levelinletcurrent_messages_hash()=no_messages_hashinletinbox={rollup=inbox.rollup;nb_available_messages=inbox.nb_available_messages;old_levels_messages;level;current_messages_hash;message_counter=Z.zero;}in(history,inbox)inletrecaux(history,inbox)=ifRaw_level_repr.(inbox.level=target_level)then(history,inbox)elseaux(archive_levelhistoryinbox)inaux(history,inbox)letadd_messageshistoryinboxlevelpayloadsmessages=ifRaw_level_repr.(level<inbox.level)thenfail(Invalid_level_add_messageslevel)elselet(history,inbox)=archive_if_neededhistoryinboxlevelinList.fold_left_es(fun(messages,inbox)payload->add_messageinboxpayloadmessages>>=return)(messages,inbox)payloads>>=?fun(messages,inbox)->letcurrent_messages_hash()=ifTree.is_emptymessagesthenno_messages_hashelseTree.hashmessagesinreturn(messages,history,{inboxwithcurrent_messages_hash})letadd_messages_no_historyinboxlevelpayloadsmessages=lethistory=history_at_genesis~bound:0Linadd_messageshistoryinboxlevelpayloadsmessages>>=?fun(messages,_,inbox)->return(messages,inbox)(* An [inclusion_proof] is a path in the Merkelized skip list
showing that a given inbox history is a prefix of another one.
This path has a size logarithmic in the difference between the
levels of the two inboxes.
[Irmin.Proof.{tree_proof, stream_proof}] could not be reused here
because there is no obviously encoding of sequences in these data
structures with the same guarantee about the size of proofs. *)typeinclusion_proof=history_prooflistletpp_inclusion_prooffmtproof=Format.pp_print_listpp_history_prooffmtproofletnumber_of_proof_stepsproof=List.lengthproofletlift_ptr_pathhistoryptr_path=letrecauxaccu=function|[]->Some(List.revaccu)|x::xs->Option.bind(historyx)@@func->aux(c::accu)xsinaux[]ptr_pathletproduce_inclusion_proofhistoryinbox1inbox2=letcell_ptr=hash_old_levels_messagesinbox2.old_levels_messagesinlettarget_index=Skip_list.indexinbox1.old_levels_messagesinlethistory=remembercell_ptrinbox2.old_levels_messageshistoryinletderefptr=Context_hash.Map.find_optptrhistory.eventsinSkip_list.back_path~deref~cell_ptr~target_index|>Option.map(lift_ptr_pathderef)|>Option.joinletverify_inclusion_proofproofinbox1inbox2=letassoc=List.map(func->(hash_old_levels_messagesc,c))proofinletpath=List.splitassoc|>fstinletderef=letopenContext_hash.Mapinletmap=of_seq(List.to_seqassoc)infunptr->find_optptrmapinletcell_ptr=hash_old_levels_messagesinbox2.old_levels_messagesinlettarget_ptr=hash_old_levels_messagesinbox1.old_levels_messagesinSkip_list.valid_back_path~equal_ptr:Context_hash.equal~deref~cell_ptr~target_ptrpathendinclude(MakeHashingScheme(structincludeContext.Treetypet=Context.ttypetree=Context.treetypevalue=bytestypekey=stringlistend):MerkelizedOperationswithtypetree=Context.tree)