Digital notarization is one of the most promising services o ered by modern blockchainbased solutions. We present a digital notary design with incremental security and cost reduced with respect to current solutions. A client of the service receives evidence in three steps. In the rst step, evidence is received almost immediately, but a lot of trust is required. In the second step, less trust is required, but evidence is received seconds later. Finally, in the third step evidence is received within minutes via a public blockchain.
The solution here described was commissioned to provide a customer in the nancial sector with evidence to corroborate its statement of the integrity, authenticity, and existence at a given time of its data. This is closely related to the problems known as secure timestamping and notarization. The commission was made with the very speci c requirement that it should make use of a privately run blockchain-based service anchored to a public blockchain, but at the same time still be capable of working without the private ledger, if it should cease to operate. We nd it interesting to discuss how this design challenge can be met, and what security guarantees it can o er.
Digital timestamping and blockchain have been linked from inception. The bitcoin
whitepaper [
Other blockchain-based timestamping solutions have been recently proposed. The authors
of [
As pointed out in [
The novel aspect of our solution is that a client of the service receives evidence in three steps. In the rst step, evidence is received almost immediately, but a lot of trust is required. In the second step, less trust is required, but evidence is received seconds later. Finally, in the third step evidence is received within minutes via a public blockchain. We achieve our results thanks to the interaction between two blockchains, one of which is public.
After some notation and preliminaries in Section 2, we give a semi-formal speci cation of the solution in Section 3. Sections 4 and 5 contain our security proofs. Section 6 contains a discussion about possible DOS attacks, while Section 7 hosts our conclusions. 2
Let time be measured in intervals [a; b) = ft 2 R j a t < bg, for any a < b 2 R. Let
A () be a digital signature algorithm using the private key of data owner A; if the owner can be determined unambiguously, we may sometimes omit A for clarity. We assume to be resistant to impersonation attacks: an attacker D cannot obtain D (m) from A (m). We also assume to be unforgeable. For example, ECDSA satis es both security properties under the usually-assumed hardness of the DLOG problem in (strong) elliptic curves.
Let k denote string concatenation. As a shorthand when dealing with containers of data with attached a signature of the contents, e.g. block headers, we will commonly employ expressions such as where T are the contents, the signature is computed as s = T k
(s); (T k 0) with 0 a string of zeroes of the same length as (T k 0), and nally the container s is composed by replacing 0 by (T k 0). The shorthand (s) is employed to indicate that the signature refers to the entire contents, without writing them explicitly at length.
Throughout this paper we denote with A(m) a public-key encryption of message m with
public key of actor A; with T f j g a Merkle tree of a list of items j; and with h (m) a
cryptographic hash function, in the sense of [
The seminal work on digital timestamping is due to Haber and Stornetta [
We present the following two algorithms to recall these important methods and establish a
common notation, though we do not make use of them directly in our solution.
Algorithm 1 (Trusted authority timestamping). In [
RFC 3161 is substantially the same scheme, but an additional hashing step is introduced: = h (d) k t k
A ( ) : = h (h (d) k t) k
A ( ) (1) (2) (3) These schemes place all trust in the hands of the authority A, but in practice trust is distributed among several stakeholders with successive timestamps.
By using hash trees, more sophisticated timestamping algorithms have been developed (see
e.g. [
Algorithm 2 (Tree-linked timestamping). At step k, de ne a time interval [tk 1; tk). The server A collects all requests k = f k;igi received in the time interval, and builds the Merkle tree T ( k). We denote its root with rk and we call it interval root.
The interval roots are linked together by the following rule, thus forming a chain of hashes fR`g0 ` k:
R0 = 0
R` = h (R` 1 k r`)
The values fR`g0 ` k are placed in a widely available repository. The server then returns to each requester a receipt with the time tk, along with the path in the Merkle tree from the requester's leaf up to the value Rk.
The authors of [
We now describe our solution. We do not require that blocks are created at xed-time intervals, but we require a time division in intervals. To be more precise, since each block hosts the time of its creation, we can consider time intervals using the index k (k 0), so that interval k corresponds to [tk 1; tk) for k 1 and interval 0 corresponds to time t < t0. 3.1
The service handles interactions among the following participants:
The clients of the service wish to provably record the existence of data d at a given time. C denotes an arbitrary client.
Some service nodes check proposed transactions for validity, provide evidence of record to clients, and maintain a blockchain, which we will call proxy blockchain. N and M denote nodes. At block creation time, one of the service nodes acts as committing node and thus prepares a block, which is submitted to the other service nodes for acceptance. One auxiliary node A commits further evidence to a public ledger L, used as a reference clock and trusted timestamping service, and monitors client transaction activity. A never acts as a service node.
The service relies on a trusted certi cate authority to provide the public key infrastructure
necessary to both identify the nodes with permission to participate in the service and provide the
ability to digitally sign documents. We assume that the proxy blockchain is at least permissioned
if not private, and that it is a robust ledger in the sense of [
The main function of our service is delivered by enabling a client C to prove existence of some data at commit time t, based on some evidence. We provide evidence in the form of digitally signed receipts and blockchain and C receives evidence with incremental trust, in three successive steps, as sketched below: 1. Evidence issued by the service node receiving data. 2. Evidence issued by the service node that create blocks in the proxy blockchain. 3. Evidence issued by the auxiliary node A and hosted by public blockchain L: A issues some evidence, which is partially stored in a public repository L, such as the bitcoin network. In the rst step, C receives a rst signed receipt. In the second step, C receives a second receipt and is able to access some evidence on the proxy blockchain. In the last step, C receives a nal receipt and is able to access some evidence on a public blockchain. We speak of incremental trust because the probability of C colluding with the other actors decreases signi cantly from one step to the next. 3.2
We now describe in detail the rst phases of our system. We assume that all clients are operating in time interval k.
Each client C, identi ed by a digital identity C , creates a self-signed statement to one of the nodes M for validation, which becomes in notation (1) =
C (d) k t k C k C ( ) This statement is analogous to a transaction in popular blockchain solutions, so we will call it transaction. M checks the signature in for validity and the claimed time t (i.e. t > tk 1). If the check is successful, M broadcasts to the other nodes and sends M ( ) back to C, which acts as the rst receipt. We call M the validator of transaction .
The next committing Node N then constructs a block by the following procedure. We assume that k blocks have already been created, with block k 1 being the last created1, meaning that all the following actions by N are implicitly related to time interval [tk 1; tk).
Let TC be the set of valid transactions originated by C and received2 by N (via validator nodes), ordered according to a prede ned rule3. Let T (TC ) be the Merkle tree of TC , and let RC be its root.
Let C be the set of all Clients that originated transactions received by N , which we call transacting Clients. Node N calculates the Merkle tree T fRC gC2C , whose root is called P. We refer to RC as the Client root and P as the block root.
We now de ne block Bk constructed by Node N . The block will contain a header, a list of summary transactions (one per transacting Client), and a phantom part.
The summary transaction for C contains a public encryption and is as follows: and sends it (4)
A( C ) k RC : 1Block 0 can be made with obvious modi cations. 2This set might be smaller than the set of all transactions issued by C 3For example, according to the order de ned by the integer representation of C (d).
The header Hk of Bk is, in notation (1),
Hk = h (Hk 1) k k k tk k P k N k N (Hk) ; where tk is stated by N as the creation time of Bk.
The phantom part is the list of all transactions referred by the summary transactions, that is [C2C TC . This transaction list is called phantom part because it is a part of the block which is visible only to the Nodes, and so invisible to the Clients.
Once N creates the block Bk, N issues a receipt C to each transacting Client C, which in notation (1) is written
C = TC k RC k C k N ( C ) ; where C is the shortest path in the Merkle tree from RC to P. 3.3
Let m be a xed number m 2. Every m blocks, node A interacts with the public blockchain. Let k0 be the last time interval in which this happened, and call anchorage block a block corresponding to one of these interactions. At the end of time interval k0 +m, another anchorage block is created, therefore A collects the ordered list of Merkle roots and block hashes of blocks k0 + 1; : : : ; k0 + m and uses these as 2m leaves of an auxiliary Merkle tree TA, TA = T
f Pk; h (Hk) gk0+1 k k0+m with root Rk0+m, referred to as the auxiliary root.
The data committed to the public ledger4 will be
pub data = A k k0 k m k Rk0+m : Finally, the auxiliary node issues an auxiliary receipt C to every client transacting in the intervals k0 + 1 k k0 + m. Each such Client will already be in possession of a set of receipts (6), which contains a set of blocks roots inside the paths C 's. This set of block roots is a subset of the leaves of the tree with root Rk0+m. Therefore, C will contain the shortest path C in TA required for C to recompute Rk0+m:
C = k0 + 1 k k0 + m k pub data k v k C k A C ; (9) where v is the address in the public blockchain of the transaction containing pub data. 4
The system that we have described in the previous section may appear unnecessarily complicated. After all, if there exists a \good" timestamping server, people could just use it and get its signature in return. But herein lies the problem, because for a timestamping server to be 4The commitment of these data to the public ledger may require more than one transaction, according to the public-blockchain transaction format. (5) (6) (7) (8) \good" it needs to be secure, reliable, approachable - in the sense that it is easy to communicate with it, both in bandwidth and in permissions - and cheap to use. While features like reliability, connectivity, and cost can be relatively easy to estimate, security remains much more di cult to evaluate. Indeed, we are not aware of any timestamping service on the Internet that presently satis es all these properties, especially security.
The only system that might provide reasonable security is a public blockchain, such as
the Bitcoin, and it would easily provide also approachability and reliability (in particular,
avoiding the risk of a single point of failure). However, at present, the cost of transactions
on a public blockchain is very high, making its direct use for storing proofs of documents
infeasible. Therefore, many competing solutions have been proposed, whose general aim is to
collect information on many documents - typically in hash form - and create paths of hashes
linking each document to the nal digest released on the public blockchain, e.g., Eternity Wall
[
Although our solution may appear similar, we aim at something more: we want to give our users incremental security. In the next sections we will describe our security claims and provide proofs. 4.1
The solution in Section 3 builds on the basic premise of digital notarization of a document. Each client correctly interacting with our previous system (in a correct implementation) may be seen as a notary making a statement of the existence of data d by adding their digital signature,
C (h (d) k t). We are not concerned with the kind of information carried by d. Indeed, the data may or may not be a document signed by parties entering a contract, and their handwritten signatures may have been added on a paper or digital copy; we here emphasize that the only digital statement of authenticity by digital signature is the Client's.
We assume throughout that the blockchain is a robust ledger in the sense of [
Let us consider the rst step of our incremental security, which is the rst interaction of a client C with our system. Let us call \Tom" someone who will come and will not believe in C's claims about the existence of its claimed documents at the claimed time. C hopes to be able to convince Tom by using our protocol.
At the start, C sends the signature of a document to the node network, encapsulated in the transaction (4), and a node M receives it. When M sends back to C the signature M ( ), M is actually giving C the rst evidence that C can show to Tom about its good faith. C is therefore immediately - say, in a few seconds - in possession of a receipt claiming the existence of its documents at the claimed time.
Whether Tom trusts this claim depends on whether Tom trusts M , speci cally. This is equivalent to trusting a single timestamping server and can be modeled simply as follows. Theorem 4.1. If M is trusted, then the data claimed by C existed at the claimed time and were known to C.
Proof. This comes from the unforgeability property of the signature C and can be achieved with a private blockchain. We require it to be private so that Tom knows all service nodes and can decide whether he trusts them.
Observe that we have not speci ed how consensus is reached in the proxy blockchain. It could be that a majority of nodes is needed, or that all nodes must con rm N 's proposed block, or some other more complex strategy. It does not matter, as long as Tom agrees that the consensus algorithm is trustworthy. What matters is that C has collected the new block header and that he has received a receipt C (6) from N . With this second evidence, Tom will agree on the following Theorem 4.2. If the new block has been generated with a trusted consensus algorithm, then (at least at time tk) the data claimed by C existed and were known to C.
Proof. All the service nodes that reached consensus have seen TC , so by signalling their agreement to the new block they agreed that the transactions from C were valid and, in particular, that the transactions were sent before the creation time tk of the block. Crucially, Tom has not seen the phantom part of the block, but he does not need it. Indeed, from Hk Tom can get tk and P. From C he gets TC and C , which shows the validity of the hash path. C could not have forged the hash path C due to the hash security properties.
An obvious question might arise when looking at the above proof: why keep a phantom part? This need arises from privacy reasons: we do not want any client C to see the transactions coming from another client C0. Of course, this goal could be reached with e.g. cryptography, but we take advantage of the use of a private blockchain to avoid more complicated features.
Thus C obtains within a short period of time some evidence on its documents that provides a much higher con dence for Tom: it is one thing to compromise or collude with a single participant M , and another to organize a collusion among the service nodes, including the miner N .
In the third and last step, if Tom does not trust the proxy blockchain, we will assume that he trusts the anchored public blockchain. Again, this trust means that, whatever consensus algorithm employed and whatever participants involved, the anchored public block was issued at a time prior to t.
Assuming that C has collected the new public block and the receipts C and C ( C refers to time interval k), Tom will then agree on the following.
Theorem 4.3. If a new public block has been generated in a public blockchain by a trusted consensus algorithm, then (at least at time t) the data claimed by C existed and were known to C.
Proof. The new public block contains a public transaction containing pub data. Since the public nodes have reached consensus and Tom trusts the public blockchain, he will trust that pub data existed before t. Indeed, from pub data Tom can get Rk0+m. From C he gets C , which shows the validity of the hash path from Rk0+m to PK . From C he gets C , which shows the validity of the hash path from PK to RC . From C he also extracts TC , which contains the transaction with the claimed data, and can check its validity by recomputing RC .
C could not have forged the hash paths C ; C or the tree root RC , without incurring in a hash collision.
Observe that in this last step Tom does not need to put any trust in the proxy blockchain, because he can verify by himself the related hash chains.
Obviously, in this third step of incremental trust Tom does feel very sure about C's claim, but C obtains all the needed third evidence only after the public block creation, which will probably last some minutes and its timestamping claim can only be up to t rather than its claimed t. 5
In Section 4 we showed how Tom can be convinced by C in di erent trust scenarios. To convince Tom, C needed some valid evidence from the system. But the system might decide not to release such evidence and try to obtain some advantage for itself. We will consider now attack scenarios where the system does not interact correctly with C. We will assume that all node services (including miners and auxiliary nodes) are malevolent.
The three scenarios we are considering are: \Fake Owner", \Ghost document: proxy version", \Ghost document: public version". In the \Ghost document" scenarios also the client C is malevolent.
Client C sends a transaction (4) at time t. The system does not acknowledge , and instead provides a colluding client D with evidence enough to claim that D knew data d at time t. Theorem 5.1. The Fake Owner attack fails.
Proof. First, the malevolent nodes need to create a fake transaction 0. We do not need to model what they will do next, because we claim it is impossible to create it. Indeed, 0 would have the form in notation (1) 0 =
D(d)jjtjj Djj D( 0) In particular, it would contain D(d). However, we assumed that our signature algorithm was resistant to impersonation attacks, and so this cannot happen.
After a new proxy block Hk is created at time tk - but before an anchorage block, i.e. k 6= m for any - C colludes with all service nodes and inserts a new transaction claiming that C knew data d0 at time t0 < tk.
This attack may work, because the nodes can decide to: discard block k and all existing successive blocks in their blockchain, recompute TC (to include 0) and all relevant information in Hk, recompute C (to include the new TC ), recompute all receipts for the other clients (and send them); recompute the headers of the successive blocks (to have valid hash pointers) and resend them to the clients.
The other clients might complain at seeing the change in past block headers, but they may be satis ed when they receive valid blocks and valid receipts. If this attack is performed rarely, the clients (and Tom) may be induced into believing that the block updates are due to some software problems rather than malice.
After a new proxy block Hk is created at time tk (an anchorage block, so k = m for some ) and the anchor has been created at time t0, C colludes with all service nodes and inserts a new transaction in Hk claiming that C knew data d0 at time t0 < tk.
Theorem 5.2. A ghost document in public version cannot be created.
Proof. Since the anchor has been created, pub data is in the public blockchain. To be able to claim knowledge of data d0, C needs a valid hash path pointing to the root corresponding to the new TC , so that he could use it to replace C . However, this path must end in Rk, which is immutable in the public blockchain, and so it is impossible to forge another path due to security properties of the hash function. 6
In the past section we do not investigate scenarios when malevolent actors of the system want to mount a DOS (Denial Of Service). We now examine this situation. There are three possible attackers: a validator node, the auxiliary node A and the PKI's CA.
Validator node If a malevolent node M receives a transaction from a client, M can decide to ignore it. In this case, C would notice that something went amiss and C would try to contact another node N . This kind of DOS is dangerous only if the client's communication with the system is limited to a group of colluding nodes.
A malevolent M could do worse than simply dropping : M could send the rst receipt M ( ) back to C and avoid broadcasting it to the other service nodes. In this way, C is tricked into thinking that M is behaving honestly. However, C is expecting to receive also the second receipt
C in a while. If this does not happen, C will know something is wrong and it will then interact with other nodes. On the other hand, if C receives C and has not been used to construct the relevant hashes, then again C will notice something is wrong.
Auxiliary node A cannot modify the Hk's to construct its Merkle tree (and thus compute a valid pub data), because A cannot sign impersonating one of the service nodes. However, A may avoid to insert some of the Hk's, e ectively removing from the auxiliary tree all the transactions received by the clients in the chosen intervals. This DOS attack by A is easily spotted by all nodes (and all clients) when the anchoring happens, because it will be impossible to reconclie the issued auxiliary receipts and the other receipts held by the clients.
Certi cation Authority We assume in our system that the CA is trusted, because if the CA were to issue certi cates to malicious peers, and if it failed to revoke them, the system would be vulnerable to a majority attack. However, it could be that the CA itself is ooded by packets sent by DOS attackers. In this scenario, it may impossible for the system participants to check the validity of new data coming into the system, depending on the public keys held by each participant. Yet, assuming that honest peers will not validate transactions without a certi cate revocation list being available, the validity of past transactions remains perfectly checkable by anyone having the relevant receipts (including Tom, if C gives them to him), since they are enough to validate the data inserted in the public blockchain. 7
We have shown a two-tiered system of independent blockchains for secure timestamping that o ers incremental levels of evidence to clients. We have examined under what assumptions the system may be deemed secure; in particular, we have seen that under the assumption of an honest certi cation authority, only denial of service attacks are feasible, and they are also immediately noticeable. The two-tiered system is designed to reduce the cost and increase e ciency of commitments to a slow and costly public blockchain, while at the same time still enabling clients to use their past evidence even if the intermediate blockchain solution were to cease being operational.
While we are satis ed with our nding, we notice that our results hold in a blockchain having an inde nite but supposedly robust consensus algorithm. It would be interesting to investigate how our system could be e ectively integrated in a blockchain enjoying a speci c consensus algorithm, such as proof-of-work or proof-of-stake.
Some partial results of this paper have been presented at the Euregio Blockchain Conference in 2018. The more advanced results presented here have been funded by the project MIUR PON \Distributed Ledgers for Secure Open Communities".