commit 25550ba0ab49062169204d0377bd6d9d5335bc7f
parent 00d3ceab5301c2fe24c3af64d9b89b25a6d4634a
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date: Sun, 29 Oct 2023 00:01:49 +0900
update
Diffstat:
8 files changed, 67 insertions(+), 49 deletions(-)
diff --git a/IETF118/R5NRoutExample-0.pdf b/IETF118/R5NRoutExample-0.pdf
Binary files differ.
diff --git a/IETF118/R5NRoutExample-1.pdf b/IETF118/R5NRoutExample-1.pdf
Binary files differ.
diff --git a/IETF118/R5NRoutExample-2.pdf b/IETF118/R5NRoutExample-2.pdf
Binary files differ.
diff --git a/IETF118/R5NRoutExample-3.pdf b/IETF118/R5NRoutExample-3.pdf
Binary files differ.
diff --git a/IETF118/R5NRoutExample-4.pdf b/IETF118/R5NRoutExample-4.pdf
Binary files differ.
diff --git a/IETF118/R5NRoutExample-5.pdf b/IETF118/R5NRoutExample-5.pdf
Binary files differ.
diff --git a/IETF118/R5NRoutExample.drawio b/IETF118/R5NRoutExample.drawio
@@ -1 +1 @@
-<mxfile host="Electron" modified="2023-08-31T13:27:30.160Z" agent="5.0 (Macintosh; Intel Mac OS X 13_2_1) AppleWebKit/537.36 (KHTML, like Gecko) draw.io/14.6.13 Chrome/89.0.4389.128 Electron/12.0.7 Safari/537.36" etag="9do6tgLn_h-PaXXZZ0ZA" version="14.6.13" type="device"><diagram id="tL_J0fyiPHFeeB-L7Xh7" name="Page-1">7VtRc6M2EP41foxHIBD4MYlzuZncdTKXa6/31JGNbNMCckFO7P76SiAFkMAhDjGJL36xWSQh9ttvd7WSR/Ay3l6neL36SgMSjWwQbEdwOrJtywKIfwnJrpD4EylYpmEgG5WCu/A/IoVASjdhQLJaQ0ZpxMJ1XTinSULmrCbDaUof6s0WNKo/dY2XxBDczXFkSn+EAVtJKXKd8sZnEi5X6tEWmhR3Yqxay1fJVjigDxURvBrBy5RSVvyKt5ckEtpTiin6fWq5K2eWsZ2aq5pRShLWZYTp1XL1/dr74d8A+NtP/4/P87/OzizbGDelmyQgohMYwQuashVd0gRHXyhdc6HFhX8TxnYSPbxhlItWLI7kXbIN2Z+V3z/lUOL3dFu92KmLhKU70QWMXXX5U40gLspu+ZXqV8ydBAaopU6U3ugmnZN9ipDWhtMlYXvaoUcoOQkIjQmfD++Xkgiz8L4+DyytcfnYroSH/5AIPQct30BLvPydvExowr8uXgfAApkOED4HwIzrm50L4nLBPMJZFs6V+FMYqQkNgLM9KM7FuPc42sgnAf4xsY8i7hgF5A+rkJG7Nc5f/YH75jqgOFsX3nIRboVhXCy4bi9pRNN8IIgcD/lerviU/kMqd6DlQO78eA+asIp8kX8eobknKSPb/eCYypQdXOUyZdBw1PVD6YJ9KVpVnK+S9a5+21S/ZZkO+ETU7zt19dtoYPVbk6N6udKzvV6gOr6fg+/Bz0GDaNYJE81zvLqf84cmGhounehKM4BglWhg7LtPcC2/uiVpyJVE0sEI6HQkYIvNHIeAjknAE040IKpHOtcdmoDeO8vnK2HvzUQ6tyPRBl25uU0Z/clGOuhrKeXQGT1qSDROV/0IaOoHQy+oGkLKkfycdYiXe3M+zu/o4yZD+jj7vVWn3mI064q0MyTSfpM7Pdm00dIKJC4c2J1OzGTihKOZA+vq95yhs3ZoqHrQNfLBhSjpkaverO9dFfAe3JnlHDVwgc4YD7A90hUwf1DAgBmATng5ZWsbJGjwwqG5QWXqPgk0P1OlgnJe1nOc17sgUEf+uM2IVxB1GxBVss40k0+4pSF/kXLHTctoHN1SiteUvUpjMQeaaANBbaBCD8ZAudU9vvYLlhxmKjSyUcQkH0fipIiiJPp3I85ecLAhAMV+ailCS/H9jW4YydXLeR7OWUgTNRyfXjFi0dIwd0HwcM6jAZ6R6JZmYd4ZTmeUMRrzHqrBeRQuxQ1GNR+UrfBaDBZvl+JwzXiGubGOF9xoV3n0YVgOeea4pociLk9TQZOHuig2j183R/O8MajvbsCJN55Aw0/ZDVb9ePyn/w0ms8A9xQxzye3v382XPOAADTTXQpoFlkaizE3cOMvyNOGcN7Cd9da0xXyCCMfCSpJZts5vgen5d9FFZCIp/74hu2IMYAkdFs+dpaWVdjNeDjzTjLFmRdKBV01OirC05jnXodhsMcw8DoMgaovA9ZSqkx3ugbl9AafV/f2GBdxjjaxqmLo3688uzXrwNORRKZmTrB+zfNIxHmiWQXGz2Kf9Ze2tJXq32JvXkK8d194cM2Hu1RyKzYwP8AXYWkpkNzgba9IUBV8N/KZsvVfwrQ/wtURaMd8bHHz7lQMBKBOPXxx8jfhuw67bkbE3z1f1nQR8YK8itwa+NTT40Nzz/homYYx7yS8dc2H1hXJMuCgWT9nEhgWo9S1vFfF19tNFuXXlDJfsVDnWpS+AFwBDgBsXwFOvcQEsqwAvsoqWQyVbzQpU4a4pHDStiF+tcueYC4/riM4+gNPORGt7TlbDntNxgYOeAdwNDkgchXk1Q/z7qIXX4D7MwpkC8xCum56k1UYWEdnKeutFpQJcll4bD2Bb0K+WdMfAe2I7n1/oJzyfXw+rnDK1vNpxbj6Dg06ZFmrZW0feC25/2zMtB0GOU162tEwIIY0VXcvLtlanRnqhsKW8zM0O7yrN1qJB1j5hW4ve6gBVSdhixF5r147J6G84CWjMk6+gnyDdVJt868S1ZtgidhNxAUBX559eQLNC40Oxgr/aGMBJ+UF1m/PRYSRBWpJh62zriSTGphECe+fl6P8r8o9BKrPuqYVJuxdqKZvom1r6vjPAE6tx39meegi8JOYoTR36D6HjkAa1GNHzWYKc2kBQrWD6ZolW+3XcF1k9vyz/Ml40L/95D6/+Bw==</diagram></mxfile>
-\ No newline at end of file
+<mxfile host="Electron" modified="2023-10-28T14:32:03.568Z" agent="5.0 (Macintosh; Intel Mac OS X 13_2_1) AppleWebKit/537.36 (KHTML, like Gecko) draw.io/14.6.13 Chrome/89.0.4389.128 Electron/12.0.7 Safari/537.36" etag="QwHVmxX8AlCfQby0nb5K" version="14.6.13" type="device"><diagram id="tL_J0fyiPHFeeB-L7Xh7" name="Page-1">7V1bl6I4EP41/dgekkAIj9OX6T5nLttnZnZn52kPSlS20biI3fb++g03IRcRUUB77RclQAj1famqVKrsK3Q7Wz+E7mL6hXk0uIKGt75Cd1cQAsu2+Ufc8pa2OI6RNkxC38suKhq++//SrDG/bOV7dClcGDEWRP5CbByx+ZyOIqHNDUP2Kl42ZoH41IU7oUrD95EbqK0/fS+aZq3YMosTj9SfTPNHA+ykZ2ZufnX2Ksup67HXUhO6v0K3IWNR+m22vqVBLL1cMOl9H7eczUa2jN7yseYjCuk8qtPD3f1k+uPB/kk+GejrL/LH4+iv62sAlX5Dtpp7NL7JuEI3LIymbMLmbvCZsQVvBLzxbxpFbxl67ipivGkazYLsLF370Z+l77+yruLvd+vywVt+MI/Ct/gWY2Dlh7/yHuKD4rbkKL9vGblh9CHGnTeMAne59Ed580c/yAekSiqXJluFI1olnoyDbjihUcV1OL2OegK9MhweKJtRPmx+QUgDN/JfRLa5GWknm+sKFPmXDMh9QCUKqPHIvmeHczbnHzft4JwCWAPps8QZnhbOab8vbrDKnmTwPxX7IOD6M4b8depH9PvCTWTxylW4CKi7XKRKdeyvY2LcjLlsb1nAwqQjhE0bEzsRfMieaekMAibiOpLfweZRqX2c/FVB80LDiK4rhZmdtXLNmtkWMz9+LTQ1yZqmJR2dtx1d/FAVPwCqnn4n4iemKH6IexY/cM5My5WMW196Dp+nnsP9IV3XbzEwErEmu8BOjp5o6HMh0VDHgOzFyvAbB8Fv1oQfnBT8pqJnwTs2cwiLetay+taz9kXP7jvRrLNcN1g6f/LdOjSISA5N3/4kVvUcaFP8nkvJeKQTPx4ROjySmLEhidno223XmI7T1md9a7M8OrdTnTknpc7guYVBTsBwkZpImyeFNNFpznfrIQJpJW6hnjWqo/oNrRqufsVvIlH8ttm3g252queMsp6r1HKnY5jISamrfNjiivbsPT0oBWgx6XtiqAFyVcZzT2VomfWNNiz2DyXVCfzwsXZq5K2as6aEr6XBN2+rPbmyJzwxn79ZEf+XzJ4p8yZ97+yugjpqR47UEZI6SgWjdJRwcPPaB/ilqr28gjiIMrN1FW9v5xMU/7OKN4w52Mgw0t2doglP4s9vbBXRRLx8dvujyGfzvDs+vLTH9EqF/PHc9kfcBrhDGjyxpZ/cjO6GLIrYjN+RX/Ah8CfxiYhJmmc5dRdxZ7P1JM4IGAxdPoMGYz6TponNidysy2vTUvUStbgvY+j00k26ldWuIcfOwCISFeyBgRStBTWsBpY5cA5XXGj2+NsznUytx/HUnUwAWLz+2CxRBYf2pLeWFKlrsNkKhG3a+gnZgeHQy18j6pPYcKjpUTUzWlptXwvHAzU7JGQAiQltAE3bxJyOoh/hgIENLBsS2+KLHRs3U/vILncDHYjEp4DyIGzDassm6BmHOmVcEZ9ogXMDjKEY1nBsZ5fDpNsM642QHP6BUfqDAlM2C759GWgCOHBwqVuJ55AMEHCKv04ZiLplYFnngfZ03u6QWl2SNcsiqjDvx2ctqWSt1ZC1trSs2+ThdEXMbsMbLRrj/ZIbmxGz0p+sl/dxdGJajmjfgejtyWdRQ55akhcpu4ct89SEitN+WdY1W9YdtJqARFnWIc2CosU1nXZqITWN5c6NXN7y9PsP9R0b5HIjdRtEImDBkZxt8YnrZaITP/ALoLlYq1QsWpKhYncW02U+XC6Sk9kDoRFr4JB/PtO3tDsDAJHZyWCGYanjWoTmZIgkggrMymxAmYZZk5sxfMQFG/uVCvVnvucF21bQolFRQaoGuv6GjpTyQ7R01fBVDlwdbQGM1FSQY1Pp4f5/T6Udaq6CXduTpCUqAc3mVGtU0g9YpdKdz32k+Yguj6P2doZTG3LVS0+mkbf3wLfd5LK2ELO26rI1ez7d8s1UY6dHpUOaEncBPwZb2kiBGrsFHA348gryeODrdvyOCj64gC8tr/KZb/cO/s4F2IGGwEhckAv4EEoT39LkdHaMPWrdCbhgn1tuCXzQIfj6yEvLHqABzlPrN1pfWNXgS8HgDdC9gW+17e+d6cxvAXzTEsFHGme/Y/Db9vcu4G+cfVnta8plurX5SC2Y+eLP/ZmrvnCDsIKpxms/M44Jb5rFT1nNFAbkUXN+VcBW0Ra8SgRZlDa8s5tKe+ByWH1suMhwFV7FYfU7WxtWz/YW6jsDeAt9tsebgMgKrFsF6ELtrSV9mmq86YKbWs0vJbHr4oTd4oZsBbdPrkdngZ/skcQ/r7NlWhsv/tIf5mBWT3W9FdEYkS0UGQd0nW353jRLHd5VzSWnbluUeKaOPAQOEcYbklRuFFdKvF5ZV19pv/Jyw5btSe38L2uLqupofxirBqVNmu1MfOmaaH0RCMt1vk0TYQhyBkVyFrHFdIMNTzvKIjdVffnNnXtsxj1brzVVqdtiPgKHZYtJRnSkrVcZEitehTSpRmrK3lzQNauReiuPkIPxTbMUgdQRbo/YWorpgjm9Umyfwt7WSUZ65Zi024eaqlLlR06cbjmmqcBrg2Q1bGqRkY0JEoiWJU1vryHnBw0ypg+j35bsg27oRyRXUCncqp2IbUs+pczjtumnhq3KtjvP3NUY6z2iGvonqzGTnrRrDapWyK4vCppS/HujEfcuQpQW4GbXGlB1Hy9E2KdmSfaSZPzqlyVJHXWcXg9acumb1aA1N6BH9tIq9fZxf0+2N29OWhgrhR21dZkhFJ5gsaypxYWxvthBJbRgXNFRDKm2iPv9rIQrJXviK2HOOLEOSiz0tJr+bgCU3E8MuiV27jGcDuXq10q1Trle18UIVFbeNV2mIDmk07GPiGAnhGvJyLdYEHoYVff6cdDeKC0rUZHSjWPocgSpY29Xs6t/ofQOSve4cVOiIEAiBRvHt3vbxtHvPat+5AONR/u2f3mMftuxhtfQVsEov+dZMznq/hrZjiymCnluzXtwpLAL1OSrEEulNJBpcbQUNqzGAlMCfGXZieNHAXENw94WJ9YHBImaEALvyGSHuwkBdAVMLTJCl8veWkSmp0SBvbC6JApo6cQPi/8nll5e/Fs2dP8f</diagram></mxfile>
+\ No newline at end of file
diff --git a/IETF118/r5n.tex b/IETF118/r5n.tex
@@ -17,14 +17,26 @@
\maketitle
% \section{The R5N DHT In a Nutshell}
+
+\begin{frame}{The R5N DHT I-D}
+ \url{https://datatracker.ietf.org/doc/draft-schanzen-r5n/}\\R5N is a DHT with the following distinguishing properties:
+ \begin{itemize}
+ \item \textbf{Open access}.
+ \item Works in \textbf{restricted-route environments}.
+ \item Supports \textbf{route path recording}.
+ \item In-band \textbf{request (and response) validation}.
+ \item \textbf{Result filtering}.
+ \end{itemize}
+\end{frame}
+
\begin{frame}{Open, peer-to-peer routing}
\begin{itemize}
- \item Problem: Access control leads to centralization.
- \item Solution: Unlike RELOAD (RFC 6940), we want ad-hoc permissionless participation.
- \item RELOAD: ``RELOAD's security model is based on each node having one or more
+ \item Access control requires authentication (and trust) and leads to centralization.
+ \item RELOAD (RFC 6940): ``RELOAD's security model is based on each node having one or more
public key certificates. In general, these certificates will be
assigned by a central server, which also assigns Node-IDs, although
self-signed certificates can be used in closed networks.''
+ \item (Popular) DHTs today require classic Kademlia-style ad-hoc permissionless participation (e.g. IPFS).
\end{itemize}
\end{frame}
@@ -35,7 +47,7 @@ Restricted-Route Networks'' by Evans et al.:
\begin{itemize}
\item ``Restricted-route topology'' refers to a connected underlay topology which prohibits (restricts) direct
connections between some of the nodes.
- \item Common DHT routing algorithms show diminished performance or even arrant failure when operating over a restricted-route underlay.
+ \item Common DHT routing algorithms (e.g. Kademlia) show diminished performance or even arrant failure when operating over a restricted-route underlay.
\item A common solution is to restrict participation in the DHT to peers that are not encumbered by NAT or firewalls.
\item However, this solution limits load-distribution for P2P applications and does not work at all for
physical networks or friend-to-friend networks.
@@ -43,80 +55,86 @@ connections between some of the nodes.
\end{itemize}
\end{frame}
-\begin{frame}{Support for in restricted-route environments}
+\begin{frame}{Support for restricted-route environments}
\begin{itemize}
\item Some peers, which from the distance metric (XOR) may be close, may not be reachable (e.g. firewall).
- \item This leads to multiple (local) minima wrt where data may be stored/can be retrieved.
+ \item This leads to multiple (local) minima with respect to where data may be stored/can be retrieved.
\item Solution: Randomized routing before XOR-metric-based routing. "Escape" local minimum sink.
\item When we have a small world topology, such a random walk will cause us to land in a random spot in the network and we will find a random local minimum.
\end{itemize}
\end{frame}
-\begin{frame}{Route recording}
- \begin{itemize}
- \item Problem: Peer which is very close in routing space. You should be connected, but you cannot connect (e.g. firewall).
- \item Solution: TODO
- \end{itemize}
-\end{frame}
-
-
-\begin{frame}{In-band response validation}
- \begin{itemize}
- \item Problem: ?
- \item Solution: Pluggable, extensible \textit{block types}.
- \item Validated by each hop.
- \end{itemize}
-\end{frame}
-
-\begin{frame}{Result filtering}
- \begin{itemize}
- \item Problem: Already known information.
- \item Solution: \textit{Result Bloom filter}.
- \end{itemize}
-\end{frame}
-
-\begin{frame}{Routing loop prevention}
- \begin{itemize}
- \item Problem: Routing loops
- \item Solution: \textit{Peer Bloom filter}.
- \end{itemize}
-\end{frame}
-
\begin{frame}{Example: PUTting some data}
\begin{center}
- \includegraphics[width=0.7\textwidth]{R5NRoutExample-0.pdf}
+ \includegraphics[height=0.9\textheight]{R5NRoutExample-0.pdf}
\end{center}
\end{frame}
-\begin{frame}{XOR distances}
+\begin{frame}{Example: PUTting some data}
\begin{center}
- \includegraphics[width=0.7\textwidth]{R5NRoutExample-1.pdf}
+ \includegraphics[height=0.9\textheight]{R5NRoutExample-1.pdf}
\end{center}
\end{frame}
-\begin{frame}{XOR distances}
+\begin{frame}{XOR-distance metric routing only}
\begin{center}
- \includegraphics[width=0.7\textwidth]{R5NRoutExample-2.pdf}
+ \includegraphics[height=0.9\textheight]{R5NRoutExample-2.pdf}
\end{center}
\end{frame}
-\begin{frame}{XOR distance route}
+\begin{frame}{Randomized route I}
\begin{center}
- \includegraphics[width=0.7\textwidth]{R5NRoutExample-3.pdf}
+ \includegraphics[height=0.9\textheight]{R5NRoutExample-3.pdf}
\end{center}
\end{frame}
-\begin{frame}{Randomized route}
+\begin{frame}{Randomized route II}
\begin{center}
- \includegraphics[width=0.7\textwidth]{R5NRoutExample-4.pdf}
+ \includegraphics[height=0.9\textheight]{R5NRoutExample-4.pdf}
\end{center}
\end{frame}
-\begin{frame}{XOR distance route}
+\begin{frame}{Randomized route III}
\begin{center}
- \includegraphics[width=0.7\textwidth]{R5NRoutExample-5.pdf}
+ \includegraphics[height=0.9\textheight]{R5NRoutExample-5.pdf}
\end{center}
\end{frame}
+\begin{frame}{Route recording}
+ Consider the following problem:
+ \begin{itemize}
+ \item Another peer is very close to our own in the routing space.
+ \item We should be directly connected, but cannot (e.g. firewall).
+ \item Solution: TODO
+ \end{itemize}
+\end{frame}
+
+
+\begin{frame}{In-band response validation}
+ DHT values can be corrupted or invalid. R5N addresses this with pluggable, extensible block types:
+ \begin{itemize}
+ \item Given a key and a block type, it is possible to verify the integrity of the value.
+ \item The verification should be possible for all hops on path, improving caching performance.
+ \item A verification could include cryptographic signatures over the data or more sophisticated approaches (see GNS, RFC-to-be 9498)
+ \end{itemize}
+\end{frame}
+
+\begin{frame}{Result filtering}
+ R5N supports filtering results for no longer interesting values:
+ \begin{itemize}
+ \item Allows us to "pause" queries and resume later w/o having to process all results again.
+ \item Reduces traffic by aborting result forwarding early.
+ \item Realized using a \textit{Bloom filter}.
+ \end{itemize}
+\end{frame}
+
+\begin{frame}{Routing loop prevention}
+ \begin{itemize}
+ \item Routing loops are a common issue in DHT routing algorithms.
+ \item R5N uses a \textit{Bloom filter} in request/response messages to prevent/identify routing loops.
+ \end{itemize}
+\end{frame}
+
+
\begin{frame}
\begin{center}
The R5N DHT\\
