Technical Field

The present invention relates to a proof system and method for structured documents, particularly for generating compact proofs regarding the content of web documents that can be used in smart contracts.

Background Art

It is known that“Smart Contracts” are a concept defined in 1997 by Nick Szabo (“Formalizing and securing relationships on public networks”, First Monday, vol. 2, 01 1997).

According to Szabo’ s definition“The basic idea of smart contracts is that many kinds of contractual clauses (such as liens, bonding, delineation of property rights, etc.) can be embedded in the hardware and software we deal with, in such a way as to make breach of contract expensive (if desired, sometimes prohibitively so) for the breacher”.

However, Szabo’ s inception remains a theoretical idea until the advent of Bitcoin.

It is known that Bitcoin is a decentralized system that implements digital cash, wherein a ledger (blockchain) tracking the ownership of the digital assets (tokens) at any time is maintained and validated by an arbitrary number of potentially unidentified and potentially egoistic actors. This distributed character makes the ledger, among other things, resistant to many forms of censorship.

Bitcoin, in addition to this, introduces tools that make its assets “programmable” through a scripting language.

However, even though Bitcoin introduces programmability, its scripting language is purposefully limited below Turing completeness.

In response to the limitations of Bitcoin script, in 2013 Ethereum, an alternative system, inheriting much of Bitcoin technical characteristics, is defined, implemented, and deployed. The biggest difference of Ethereum is that it features a Turing complete scripting language, with which it is possible to describe logic software agents of arbitrary complexity. These software agents, remarkably, can handle the digital assets tracked by the Ethereum blockchain, and can send and receive tokens (arrange change of tokens ownership), according to their programmed logic, and to the occurrence of certain conditions. These agents are called smart contracts, since they can be a medium to implement Szabo’s idea, with even stronger and more peculiar features.

It is further known the so-called “oracle problem”, that is the need of representing and automatically checking external information to a smart contract.

Different existing approaches are also known in order to interface/connect smart contract execution with environments external to the blockchain, both to access external information and to produce effects on the outside world.

One way to classify oracles is according to the data interaction pattern that they implement (A. M. Antonopoulos, Mastering Bitcoin: Unlocking Digital Crypto- Currencies, 1st ed. O’Reilly Media, Inc., 2014): immediate-read, publish- subscribe and request-response.

Immediate read oracles are lookup representations of datasets used typically only once by contracts. They can be implemented as contracts that provide a lookup method. They can also be updated over time.

Publish-subscribe oracles implement services that provide streams of evolving information, such as the price of gold, or the weather of a particular location. They can be implemented as contracts that emit events (i.e., publicly readable information, easily accessible also off-chain) that can be observed by other contracts, which in turn can react to the new information available. However, it is pointed out that, for a smart contract, the operation of periodically querying a service can be costly.

The request-response oracle pattern is the most complex, as it involves multi- step interactions among on-and off-chain elements. This kind of oracles allows smart contracts to access particular information that is accessible off-chain, e.g., through an internet API.

There are various ways to implement the request-response scheme. The off- chain element can be a human, an IoT sensor, a process running in the cloud, etc.

An example of request-response oracles is Oraclize, that is structured as a software agent that listens for data access requests generated by any smart contract. Requests contain information about the internet data sources to be accessed (e.g., a URL).

However, the usage of a single oracle, while it is cheap, places too much trust in a single non-trusted entity, which defeats the purpose of using a decentralized network.

Description of the invention

The main aim of the present invention is to provide a proof system and related method for structured documents which allow a different oracle data pattern, seeking the generality of request-response methods, without the complexity and trust requirements of an intermediary like Oraclize.

To do that, the proof system according to the invention defines a signature scheme that allows data providers to offer their information in a form suitable for the generation of proofs that can be fed to smart contracts.

Another object of the present invention is to provide a proof system and related method for structured documents that are general, transparent for the data providers, and with minimal cost for on-chain code execution.

Another object of the present invention is to provide a proof system and related method for structured documents that allow to remove the trust from a single oracle.

The above-mentioned objects are achieved by the present computer implemented method according to the features of claim 1.

The above-mentioned objects are also achieved by the present data processing proof system according to the features of claim 22.

Brief Description of the Drawings

Other characteristics and advantages of the present invention will become better evident from the description of a preferred, but not exclusive embodiment of a proof system and related method for structured documents, illustrated by way of an indicative but non-limitating example in the accompanying Figures, in which:

Figure 1 is a general diagram showing the generation of an XML-Merkle tree with the computer-implemented method according to the invention;

Figures 2 and 3 shows examples of a generated XML-Merkle tree;

Figure 4 is a general diagram showing the generations of proofs using said XML-Merkle tree.

Fmbodiments of the Invention

With particular reference to Figure 1, globally indicated with reference M is a computer-implemented proof method for structured documents, particularly for generating compact proofs regarding the content of web documents that can be used in smart contracts.

The computer-implemented proof method M comprises at least the following main steps:

- receiving in input a structured document in the form of an XML tree, wherein said XML tree comprises a set of nodes, each node comprising a plurality of components (step 1);

- generating an XML-Merkle tree starting from said XML tree (step 2), comprising: determining a plurality of Merkle trees to individually represent each of said components of each of said node of the XML tree (step 21); for each node of the XML tree, determining a node hash by hashing the Merkle roots of said plurality of Merkle trees representing the components of the node (step 22);

- when requested, generating at least a proof related to information contained in said structured document using said XML-Merkle tree (step 3).

Particularly, the method M according to the invention allows to generate a compact representation in order to produce proofs of the presence of some information in a signed structured document. To do that, the method M defines a structure that integrates the information contained in an XML trees into a Merkle tree, enhancing the expressiveness of Merkle proofs while preserving a lightweight structure.

The method M can be applied to any structured document containing structured information. For example, HTML pages can be represented as XML trees in order to build an XML-Merkle tree.

It is pointed out that hashing all the information in a node would introduce a computationally complex search operation on-chain and would also move part of the proof computation on-chain. On the other hand, directly generating a Merkle tree with each node by hashing child text information in a bottom-up fashion would lose all the metatextual information.

Therefore, in order to avoid these drawbacks, the method M according to the invention uses Merkle trees to individually represent the three components of each XML node.

Each node of the XML tree comprises the following main components:

- a set of attributes (e.g., id, href), all optional except the field tag (e.g., <div>, <figure>);

- an optional text field (e.g., <div> optional text </div>);

- an optional list of child nodes (e.g., <div> <div> child div <div> </div>). The step 21 of determining a plurality of Merkle trees comprises computing a text Merkle tree starting from said text field in a node of the XML tree (step 211).

Therefore, the method according to the invention allows to to represent the text in a node as a text Merkle tree.

Particularly, said step 211 of computing a text Merkle tree comprises encoding each word of said text field in a node of the XML tree as a single leaf of said text Merkle tree.

This allows to obtain a good granularity for mapping the words into the text Merkle tree, providing at the same time a strong expressive power of the text Merkle tree.

According to a possible embodiment of the method M, the text Merkle tree is a binary Merkle tree. However, n-ary trees may also be used to build the text sub tree of each node.

Furthermore, the step 21 of determining a plurality of Merkle trees comprises computing an attribute Merkle tree starting from said set of attributes in a node of the XML tree (step 212).

Particularly, node attributes of the XML tree are a set of key- value pairs (e.g., id = dementi, color = red). The only exception is the HTML tag (e.g., div, figure, ...), which is used to define the name of the field. The HTML tag is always the first word in the node.

A common solution for representing node attributes is a hash table, but they are not a prime choice for storage in blockchain applications because of overhead costs.

According to the method M, the step 212 of computing an attribute Merkle tree comprises the use of a binary-tree representation, wherein the key- value pairs of the set of attributes are alphabetically ordered and each key- value pair is placed in a leaf of the attribute Merkle tree.

Particularly, the alphabetical ordering allows to remove ambiguities from a node and to represent it in a deterministic way, while containing the computational cost of generating the attribute Merkle tree and the evaluating proofs.

Furthermore, said step 21 of determining a plurality of Merkle trees comprises computing child node Merkle trees starting from said list of child nodes in a node of the XML tree and for each child node (step 213).

Therefore, each child node can be represented as another XML-Merkle tree and consequently hashed.

The child nodes of a node are thus represented as a list of root hashes (the root of each child node XML-Merkle tree).

Preferably, nodes of the XML tree without child nodes are the first to be generated, while other nodes are afterward generated bottom- up.

The step 22 of determining a node hash according to the method M comprises, for each node of the XML tree, hashing the following roots:

- a node text Merkle root of said text Merkle tree (step 221);

- a node attribute Merkle root of said attribute Merkle tree (step 222);

- child node Merkle roots of each of said child node Merkle trees (step 223).

According to a preferred embodiment and in order to simplify the representation of the node, the method M condense the node attribute Merkle root and the node text Merkle root into a single hash.

Particularly, said step 22 of determining a node hash comprises, for each node of the XML tree:

- hashing the concatenation of the node attribute Merkle root and of the node text Merkle root into a single Attribute Text (AT) hash (step 224);

- hashing the Attribute Text (AT) hash with the child node Merkle roots to obtain said node hash (step 225).

Therefore, in the final representation each child node is represented as a hash of its content. The final structure of each node is the following:

- the AT hash;

- the child node Merkle roots (child nodes’ hashes).

In this representation, each node is a list of n+1 hashes, where the first hash is the AT hash, followed by the ordered n-child nodes’ hashes. The Merkle tree root of this representation is thus the hash of these n+1 hashes concatenated.

In the following it is disclosed an example in order to clarify the use of the computer-implemented method for obtaining the Merkle tree according to the invention.

Given a HTML code snipped:

<div id=’main’ class=’text box’>

<p> Hello world! <\p>

<\div>

The external node, the div, is converted into an attribute Markle tree with three elements: the two attributes (id and class ) and the tag (see Figure 2). Each attribute is hashed, the hashes are concatenated using a binary tree structure until the node attribute Merkle root is reached.

The tree root is the“AT hash”.

As previously discussed, the final node hash is generated concatenating the AT hash with the child node Merkle root of each children.

In the proposed example, the only child of the node div is the node p (the one containing the text“Hello world!”). Node p does not have any child, thus its representation is the AT hash generated using the attribute pair (“tag”,“p”) and the text“Hello world!”.

The node div is finally generated concatenating the AT hash (with its tag and attributes) and the node hash of the child p.

An example of the final representation for a generic node is shown in figure 3. Advantageously, the main step 3 of generating at least a proof comprises at least one of the following steps:

- generating audit proofs for proving that a record is in a given tree (step 31);

- generating text proofs for proving that a text is in a given tree (step 32);

- generating attribute proofs for proving that an attribute is in a given tree (step 33);

- generating parental proofs for verifying parent-child relationships within the XML-Merkle tree (step 34).

Audit proofs, text proofs, attribute proofs are also properties of the basic Merkle trees, while the parental proof is an additional property of the proposed XML- Merkle tree.

Audit proofs consist in reconstructing the root hash from a subset of hashes in the tree. Their implementation in XML-Merkle tree is slightly more complex than the one used for binary trees. This is due to the different technique used to build the tree.

Particularly, said step 31 of generating audit proofs comprises at least one of the following steps:

- verifying the presence in a node of an attribute Merkle root of an attribute Merkle tree or of a text Merkle root of a text Merkle tree (step 311);

- verifying the presence of a node in the XML-Merkle tree (step 312). Therefore, audit proofs can be used to verify (scenario I) the presence of a Merkle root of a sub-tree (text or attribute) in a node or (scenario II) the presence of a node in the XML-Merkle tree.

Particularly, said step 311 of verifying the presence in a node of an attribute Merkle root or a text Merkle root (scenario I) requires the following inputs: - the computed attribute Merkle root or text Merkle root to be verified;

- the Merkle roots of the other Merkle sub-trees;

- either node’s AT hash or other child node Merkle roots (child nodes’ hashes).

Furthermore, according to a possible embodiment, the step 311 comprises checking whether the AT hash can be obtained by hashing the attribute Merkle root and text Merkle root.

Alternatively, the step 311 comprises checking that the concatenation of the computed AT hash with the other child node Merkle roots gives the node hash of said XML-Merkle tree.

Furthermore, said step 312 of verifying the presence of a node in the XML- Merkle tree (scenario II) comprises checking whether or not the node hash (root) of said XML-Merkle tree previously signed matches the root of a reconstructed validation tree.

Particularly, the construction of said validation tree requires the following inputs:

- node’s hash to be verified;

- an array of arrays of Merkle proof element, wherein each sub-array is relative to the next parent nodes child nodes; (The array contains the AT hash and n-1 child nodes’ hashes, where n is the number of child nodes)

- an index array, listing at which index each child is in relation to its parent;

- the root of the XML-Merkle tree.

Furthermore, the step 312 of verifying the presence of a node in the XML- Merkle tree (scenario II) comprises:

- for each sub-array, computing the parent node hash by concatenating and hashing the first i nodes’ hashes, followed by the hash of the checked node, followed by the remaining n-i child nodes’ hashes;

- recursively applying said computing until the root of the reconstructed validation tree is obtained;

- comparing the obtained root with the root of the original XML-Merkle tree and

- if the obtained root of the reconstructed validation tree matches the root of said XML-Merkle tree previously signed, generating said audit proof. The step 32 of generating text proofs comprises hashing the text to be verified to obtain a leaf value (step 321) and calculating an audit proof related to said leaf value (step 322).

The audit proof is the list of missing node hashes required to compute all of the nodes between the leaf and the tree root. When the proof is required, it is enough to check if the root hash computed from the audit path matches the established Merkle root. If true, the leaf, and thus the given text, exists in the tree.

The step 33 of generating attribute proofs comprises separately computing the hashing of the attribute name and of the attribute value of an attribute to be verified and concatenating the two hashes in a single value (step 331), hashing said single value to obtain a leaf value (step 332) and calculating an audit proof related to said leaf value (step 333).

Like for text proofs, a proof of the existence of an attribute can be produced by checking if the root hash computed from the audit path matches the established Merkle root.

With reference to parental proofs, these proofs are used to verify parent-child relationships within the XML-Merkle tree and they are very convenient for verifying particular properties of a node.

In particular, parental proofs are especially useful to demonstrate key relationships between siblings which are necessary for some use-cases, for example to prove that two adjacent elements contain relevant information.

As an example, in a scenario where we want to prove the outcome of a soccer match associated to a bet, the information is structured so that two adjacent elements contain respectively the team name and its score. The easiest way to match a team name and score is to demonstrate that a team name is in a certain field and that there is a score in the adjacent field.

Advantageously, said step 34 of generating parental proofs needs the following inputs:

- the child node hash for which it is necessary to demonstrate that it is the child of some node;

- the child node index in the sibling set;

- the parent node hash for which it is necessary to demonstrate that it is the parent of some node;

- the child nodes siblings.

Furthermore, the step 34 of generating parental proofs comprises the following steps:

- concatenating the siblings according to their index: the siblings with an index lower than the childs index, followed by the child nodes hash, followed by the remaining siblings (step 341);

- checking whether or not the generated hash corresponds to the parent hash and, it corresponds, generating the parental proof (step 342).

It is worth noting that proving that a node A is child of a node B, and then performing an audit proof of node B implicitly performs an audit proof of node A. However, the opposite is not true. It cannot be asserted whether the parent node B is in the tree via an audit proof of node A.

In a similar way, to prove a sibling relationship between two nodes, it is sufficient to prove that both nodes are children of the same parent node. This can be extended with the use of indexes to prove ordinal relationships between siblings.

According to the invention, a data processing proof system is provided comprising means for carrying out the steps of the computer-implemented method disclosed above.

Particularly, the proof system according to a preferred embodiment comprises at least the following components:

- a tree/proof generator;

- an on-chain verifier.

According to a possible solution, the tree/proof generator could be implemented in python, while the on-chain verifier could be implemented using Solidity. Furthermore, according to the invention, it is provided a computer program comprising instructions which, when the program is executed by a computer, cause the computer to carry out the steps of the method disclosed above.

Furthermore, a smart contract according to the invention comprises the computer-implemented method disclosed above for checking at least a proof related to information contained in a structured document.

Example: temperature prediction.

As a possible example, it is here below disclosed a temperature prediction scenario. In this scenario it is determined whether or not a certain temperature will be reached on a given day.

To determine the temperature, a popular weather aggregator is used which reports the temperature for all major cities in Italy.

In order to instantiate this contract, the following specific information are needed:

1. a public key associated with the publisher;

2. the date by which the temperature should be reached;

3. the name of the city where the temperature is being monitored;

4. the temperature threshold to be reached.

Furthermore, it is needed an easy way to find the temperature for a given city in the page.

Here below it is showed a snippet of the portion of the page showing the temperature for a few cities. The snippet shows the weather for the cities of Rome, Turin and Trento.

1 <div class = " odd2 row" >

2 <div class = "col -xs -5 col -sm -8" >

3 <a href = "http://meteo. corriere. it/italia/lazio/roma/" title

meteo Roma”>Roma </a>

4 </ div >

5 <div class = "col -xs -3 col -sm -2 ">

6 <div class = " localital8 118 - pioggia_30 "/> 7 <7 div >

8 <div class = "col -xs -4 col -sm -2 ">5</ div >

9 </div >

10 <div class = " oddl row" >

11 <div class = "col -xs -5 col -sm -8" >

12 <a href = "http://meteo. corriere. it/italia/piemonte/torino/"

title = " meteo Torino ">Torino </a>

13 div >

14 <div class = "col -xs -3 col -sm -2 ">

15 <div class = " localital8 118 - nuvoloso_70 "/>

16 <7 div >

17 <div class = "col -xs -4 col -sm -2”>1 <7 div >

18 </div >

19 <div class = " odd2 row" >

20 <div class = "col -xs -5 col -sm -8" >

21 <a href = " http ://meteo.corriere. it/italia/trentino-alto- adige/trento/”title= "meteo Trento" >Trento </a>

22 <7 div >

23 <div class = "col -xs -3 col -sm -2 ">

24 <div class = " localital8 118 - molto_nuvoloso "/>

25 <7 div >

26 <div class = "col -xs -4 col -sm -2 " >3 <7 div >

27 <7 div >

It is possible to see a pattern, where each field with tag a has the title meteo CITY where CITY is the name of a city, and the last sibling of this field's parent contains the temperature in its text section.

As a result, what constitutes a proper proof for this scenario is:

1. initializing the contract with the name of the city where the temperature is to be monitored and the target temperature; 2. proving that there is a field tagged as a with the title attribute as described above (attribute proofs, followed by an audit proof);

3. proving that there is a field tagged as div with text X, where X is the temperature at retrieval (attribute and text proofs followed by an audit proof). Note that at this point the contract logic compares the value of X with the threshold defined upon initialization;

4. proving the sibling relationship between these two fields by providing a parent field with these two nodes as children, one as the first child of the first child, the other as the last child. This can be achieved by using parental proofs with fixed indices for the position of each child;

5. a final audit proof for the parent field, proving this subtree is in the page. This requires to perform a total of 10 proofs for proving purposes. Some contract logic is required when comparing values to thresholds.

The contract is initialized with a public key, two timestamps that indicate a time frame for the threshold to be reached, the threshold to be reached, a boolean value indicating whether the threshold is to be approached from below or above the target, and the amount to stake. Even though the contract allows for two different types of approaches to the value, due to the way the proof is done computational costs are identical for both cases.

The taker has to wait for the target to be passed before building the proof, and if this never occurs, they lose by default after the twenty-four hours grace period.

If the target is met or passed, the taker has to acquire the signed and timestamped Merkle root and verify it locally by rebuilding the tree. If the roots correspond, the taker can build the proofs.

The proofs are then sent in order to the contract, and again the contract reaches the state where the taker is deemed successful in their proof. The taker may now redeem the jackpot.

It is therefore proved that the method and system according to the invention allow to obtain a different oracle data pattern, seeking the generality of request- response methods, without the complexity and trust requirements of an intermediary like Oraclize. Particularly, the proof system and method according to the invention define a signature scheme that allows data providers to offer their information in a form suitable for the generation of proofs that can be fed to smart contracts.

Furthermore, the system and method according to the present invention are general, transparent for the data providers, and with minimal cost for on-chain code execution.

Furthermore, the proof system and related method according to the invention allow to remove the trust from a single oracle.