Concurrent writings in verifiable persistent data structures
A method for storing a persistent data structure a sequence of data blocks comprises receiving a new one of the data blocks for appending to a last one of the data blocks. Said new data block containing corresponding data and a corresponding appending requirement selected among a set of pre-defined appending requirements including a first appending requirement providing that a content and an ordering of all the data blocks match a corresponding first indication received with the appending requirement, and a further appending requirement providing that a content and an ordering of all the data blocks of a further sequence are at least an initial portion of the sequence matching a corresponding further indication received with the appending requirement, said further sequence identified by a corresponding context and appending said new data block to said last data block conditioned on a fulfillment of said corresponding appending requirement.
1 . A method for storing a persistent data structure comprising a sequence of data blocks, the method comprising, under the control of a computing system:
at the computing system, receiving a new one of the data blocks to be appended to a last one of the data blocks in the sequence, said new data block containing corresponding data and a corresponding appending requirement selected among a set of pre-defined appending requirements comprising:
a first one of the appending requirements providing that a content and an ordering of all the data blocks of the sequence of data blocks match a corresponding first indication received with the appending requirement, and
a further one of the appending requirements providing that a content and an ordering of all the data blocks of a further sequence are at least an initial portion of the sequence matches a corresponding further indication received with the appending requirement, said further sequence identified by a corresponding context,
at the computing system, appending said new data block to said last data block conditioned to a fulfillment of said appending requirement contained in the new data block, and
at the computing system, storing an indication of the context,
wherein each data block in the sequence is associated with a corresponding block,
hash that is a hash value of said data block, and with a corresponding link hash that is a hash value based on the block hash of said data block and on the link hash of a previous data block, in the sequence of data blocks, and that is adjacent to said data block wherein:
said first one of the appending requirements provides that the link hash of the last data block matches a link hash comprised in said first indication; and
said further one of the appending requirements provides that the link hash of a last data block of the current further sequence matches a link hash comprised in said further indication.
2 . The method of claim 1 , wherein said set of predefined appending requirements further comprises:
a still further one of the appending requirements providing that a content of the last data block matches a corresponding still further indication received with the appending requirement.
3 . The method of claim 2 , wherein said still further one of the appending requirements provides that the block hash of the last data block matches a block hash comprised in said still further indication.
4 . The method of claim 1 , wherein said new data block further contains a context update request providing for an updating of the context to a new context indicative of an extension of the further sequence.
5 . The method of claim 4 , wherein the context identifying the further sequence corresponds to a lastly appended data block among data blocks of the sequence containing a corresponding context update request.
6 . The method of claim 1 , wherein said further sequence comprises all the data blocks of the sequence.
7 . The method of claim 1 , further comprising, at the computing system:
receiving a set of new ones of the data blocks to be appended;
appending at least a selected one of the new ones of the data blocks of the received set to the last one of the data blocks in the sequence conditioned to the appending requirements contained in said received set of new ones of the data blocks.
8 . The method of claim 7 , wherein said at least a selected one of the data blocks of the received set comprises a plurality of selected data blocks, the method further comprising appending the selected data blocks to the last one of the data blocks in the sequence by ordering the selected data blocks according to the appending requirements contained in the selected data blocks.
9 . The method of claim 1 , wherein said set of pre-defined appending requirements further comprises an additional one of the appending requirements that is always fulfilled.
10 . A computer program product comprising one or more tangible, non-transitory readable storage media having program instructions collectively stored on the one or more tangible, non-transitory readable storage media, the program instructions readable by a computing system to cause the computing system to perform the method of claim 1 .
11 . A computing system comprising a circuitry for performing each step of the method according to claim 1 .