Clairvoyance.tex

% !TEX root = GovChain.tex


Using the hiding property of a hash function, we might argue that the government might also guarantee for the immutability of their secret data that they do not want to publish. More precisely, assume that the government has a list $d_1,d_2,\ldots ,d_k$ of documents they wish to keep secret, but want to assure the general public that the documents themselves will not be changed not manipulated. For this, the government could simply create the Merkle tree $MT(d_1,\ldots ,d_k)$ that contains the hash values $h(d_1),\ldots ,h(d_k)$ as its leaves, and publish this tree as the safety certificate. If at a later date there is a dispute regarding some issue pertaining to document $d_i$ (e.g. in case that $d_i$ is a contract under question), a judicial body might require the government agency to make this particular document public, and show its membership in the Merkle tree $MT(d_1,\ldots ,d_k)$. In case that the document was manipulated in the meantime, this can now be detected, as the leave hash will not match the path to the root of the tree. Note that this still allows the documents different from $d_i$ to remain secret.

One problem with this solution is that since the documents $d_1,\ldots ,d_k$ are not made public, a malicious government agent might publish two versions of the document: one that suits him and does not reflect signs of foul play, and another that holds the actual true. For example, suppose that the government does not disclose tax certificates of particular entities, but includes these in the Merkle tree. Assume also that a certificate for an entity $X$ was issued stating that the taxes are not in order, and was included in a Merkle tree. An authorized government agent is then bribed to also issue a certificate that the taxes are in order, together with the proof of the inclusion in a Merkle tree (note that this can even be the same tree containing the first certificate). If $X$ is at a later date asked to prove the status of their taxes, they would just provide the certificate showing the taxes to be in order, together with the proof of the inclusion in the corresponding Merkle tree. Since we have no way to detect that the other certificate is also in the tree (due to the data being secret), we can not detect foul play in this case. A similar sort of embezzlement can be executed with contracts stating how much public funds were used to execute a particular activity, or spent on a particular service.

This can be addressed at the Merkle tree construction level, demanding some behaviour from the government and adding a simple verifying procedure to the guarding entities, as follows. Allow the government to input hashes of undisclosed documents in the Merkle tree leafs, but for each secret document, the government must input a public document containing (a) the hash value of the corresponding secret document and (b) some reasonable description thereof. Let us refer to these documents as \textit{affidavits}. In simple terms, an affidavit of the example above must read \textit{``A secret document with hash value $\langle \mbox{hash}\rangle$ has been inserted into this tree. Description: Tax situation of entity X. $\langle\mbox{timestamp}\rangle$, $\langle\mbox{signature}\rangle$''}. 

In order to avoid any ambiguities, we suggest that each affidavit corresponds to exactly one secret document in the same Merkle tree, and that they should be treated as regular public documents. The guarding entities facing such a tree must perform an additional verification: For each hash whose document they cannot access, there must be a affidavit in the same tree containing that hash value, and a description. There is a delicate degree of liberty on what a reasonable description should look like. We suggest that such a description contains the maximum amount of public information, in order to be used later as a proof. For instance, it should allow to trace two contradictory documents (a guarding entity may allow users to search affidavits by description). Should the government give unrelated or incomplete descriptions, this would become evident when a court orders to reveal the underlying document. 

Adding this to previous considerations, Merkle trees could also include elements of the form $(z:a)$ where $z$ is the hash of an undisclosed document (indicated in the body of the publicly available affidavit), and $a$ is the hash value of the affidavit itself.
%
%$$
%\begin{array}{ll}
%\mbox{\it New: } &\{x_1,x_2,\dots,x_n\},\\
%\mbox{\it Updates: }& \{(y_1:y_1'), (y_2:y_2'),\dots, (y_m:y_m')\},\\
%\mbox{\it Undisclosed: }& \{z_1,z_2,\dots,z_k\}\\
%\mbox{\it Affidavits: }& \{a_1,a_2,\dots,a_k\}\\
%\end{array}
%$$
%

%Upon publication of a Merkle root by the government, fully responsible verifiers should download all corresponding data, compute the hash value of each new document, check that each affidavit contains a hash value, and that updates link to a non-updated version of a document. After doing this, they assemble a Merkle tree with all computed data: (i) hashes of new documents, (ii) hashes of updated documents (possibly linking to the hash of the previous version, as discussed in \ref{sec:updates}) and (iii) hash values stated in affidavits. Note that affidavits are treated as regular disclosable documents, whose hash value is therefore included in (i). To finish, this entity verifies that the Merkle root of this tree matches the last published Merkle root in the established blockchain. There are some relatively straightforward details in these verifications which we omit here. 


%\domagoj{add some potential solutions}