67 lines
4.4 KiB
HTML
67 lines
4.4 KiB
HTML
<!DOCTYPE html>
|
||
<html lang="en">
|
||
<head>
|
||
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
|
||
<style>
|
||
body {
|
||
max-width: 30em;
|
||
margin-left: 2em;
|
||
}
|
||
p.center {
|
||
text-align:center;
|
||
}
|
||
</style>
|
||
<link rel="shortcut icon" href="../rho.ico">
|
||
<title>Verifiable log backed map</title>
|
||
</head>
|
||
<body>
|
||
<p><a href="./index.html"> To Home page</a> </p>
|
||
<h1>Verifiable log backed map</h1>
|
||
|
||
<p>The point and purpose of the Verifiable Log Backed Map is to provide a mapping from identiers, such as phone numbers, email addresses, etc, to public keys, which mapping has to be the same for everyone – so that if you see your public key is such and such, you know that those you converse with also see your public key is such and such.</p>
|
||
|
||
<p>For this to be actually useful, needs to drive a blogging and messaging system with capabilities analogous to facebook, wordpress, or twitter, and each entity in the system needs to have a wallet analogous to a blockchain wallet. Not all wallets should be associated with entities that can be easily found on the network, but entities that can be easily found on the network should have wallets</p>
|
||
|
||
<p>A Verifiable Log Backed map is a Verifiable Map backed by a Verifiable Log that describes an ordered set of operations that result in predictable mutations to the map.</p>
|
||
|
||
<h2>Clients of a verifiable log can:</h2><ol>
|
||
<li>Efficiently verify that a specific entry is included in the log.</li>
|
||
<li>Efficiently detect splitview attacks.</li>
|
||
<li>Efficiently verify the appendonly property of the log.</li>
|
||
<li>Enumerate all entries held in the log.</li>
|
||
</ol>
|
||
<p>The verifiable log as described is equivalent to that described in <a href="https://tools.ietf.org/html/rfc6962">RFC6962</a>.</p>
|
||
|
||
<h2>Verifiable Maps</h2>
|
||
<p>A verifiable map is a map from a set of keys to a corresponding set of values. Conceptually we map all 2<sup>256</sup> hash values to 256 bit values plus null, except that we take advantage of the fact that the tree is sparse, that most values map to null. Periodically the map will publish a signed tree head which includes a root hash of all 2<sup>256</sup> entries.</p>
|
||
<p>We implement this as a <a href="https://github.com/ethereum/wiki/wiki/Patricia-Tree">Merkle-patricia dac</a>.</p>
|
||
|
||
<p>Clients of the map can:</p>
|
||
<ol><li>Efficiently retrieve the value (or indication of nonpresence)for a key, and verify that this is included (or not present) in the map at a point in time.</li>
|
||
<li>Efficiently detect splitview attacks.</li>
|
||
<li>Enumerate all key/value pairs held in the map.</li></ol>
|
||
<p>This verifiable map as described is equivalent to the Sparse Merkle Tree described in Revocation Transparency.</p>
|
||
|
||
<h2>Verifiable LogBacked Map</H2>
|
||
<P>is a Verifiable Map backed by a Verifiable Log that describes an
|
||
ordered set of operations that result in predictable mutations to the map.</p>
|
||
|
||
<p>The following table summarizes properties of the data structures laid out above. “Efficiently” means that a client can and should perform this validation themselves. “Full audit” means that to validate correctly, a client would need to download the entire dataset, and is something that in
|
||
practices we expect a small number of dedicated auditors to perform, rather than being done by each client.
|
||
<table rules="all" frame="box">
|
||
<tr><th> </th><th>Verifiable Log</th><th>Verifiable Map</th><th>Verifiable LogBacked Map</th></tr>
|
||
<tr><th>Prove inclusion of value</th><td>Yes, efficiently</td><td>Yes, efficiently</td><td>Yes, efficiently</td></tr>
|
||
<tr><th>Prove noninclusion of value </th><td>Impractical </td><td>Yes, efficiently </td><td>Yes, efficiently</td></tr>
|
||
<tr><th>Retrieve provable value for key </th><td>Impractical </td><td>Yes, efficiently </td><td>Yes, efficiently</td></tr>
|
||
<tr><th>Retrieve provable current value for key </th><td>Impractical </td><td>No </td><td>Yes, efficiently</td></tr>
|
||
<tr><th>Prove appendonly </th><td>Yes, efficiently </td><td>No </td><td>Yes, efficiently, although full audit is required to verify complete correct
|
||
operation.</td></tr>
|
||
<tr><th>Enumerate all entries </th><td>Yes, by full audit </td><td>Yes, by full audit</td><td> Yes, by full audit</td></tr>
|
||
<tr><th>Prove correct operation </th><td>Yes, efficiently </td><td>No </td><td>Yes, by full audit</td></tr>
|
||
<tr><th>Enable detection of splitview </th><td>Yes, efficiently </td><td>Yes, efficiently </td><td>Yes, efficiently</td></tr>
|
||
</table>
|
||
<p> </p>
|
||
|
||
</body>
|
||
</html>
|