[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] r1780: Updated the Pynchon spec to include the Byzantine server det (doc/trunk/pynchon-gate)
Author: rabbi
Date: 2007-04-24 08:47:49 -0400 (Tue, 24 Apr 2007)
New Revision: 1780
Modified:
doc/trunk/pynchon-gate/llncs.cls
doc/trunk/pynchon-gate/pynchon-spec.txt
Log:
Updated the Pynchon spec to include the Byzantine server detection scheme
I came up with. Asked some questions we need to answer.
Modified: doc/trunk/pynchon-gate/llncs.cls
===================================================================
--- doc/trunk/pynchon-gate/llncs.cls 2007-04-18 19:44:53 UTC (rev 1779)
+++ doc/trunk/pynchon-gate/llncs.cls 2007-04-24 12:47:49 UTC (rev 1780)
@@ -1,9 +1,26 @@
-% LLNCS DOCUMENT CLASS -- version 2.8
-% for LaTeX2e
+% LLNCS DOCUMENT CLASS -- version 2.14 (17-Aug-2004)
+% Springer Verlag LaTeX2e support for Lecture Notes in Computer Science
%
+%%
+%% \CharacterTable
+%% {Upper-case \A\B\C\D\E\F\G\H\I\J\K\L\M\N\O\P\Q\R\S\T\U\V\W\X\Y\Z
+%% Lower-case \a\b\c\d\e\f\g\h\i\j\k\l\m\n\o\p\q\r\s\t\u\v\w\x\y\z
+%% Digits \0\1\2\3\4\5\6\7\8\9
+%% Exclamation \! Double quote \" Hash (number) \#
+%% Dollar \$ Percent \% Ampersand \&
+%% Acute accent \' Left paren \( Right paren \)
+%% Asterisk \* Plus \+ Comma \,
+%% Minus \- Point \. Solidus \/
+%% Colon \: Semicolon \; Less than \<
+%% Equals \= Greater than \> Question mark \?
+%% Commercial at \@ Left bracket \[ Backslash \\
+%% Right bracket \] Circumflex \^ Underscore \_
+%% Grave accent \` Left brace \{ Vertical bar \|
+%% Right brace \} Tilde \~}
+%%
\NeedsTeXFormat{LaTeX2e}[1995/12/01]
-\ProvidesClass{llncs}[2000/05/16 v2.8
-^^JLaTeX document class for Lecture Notes in Computer Science]
+\ProvidesClass{llncs}[2004/08/17 v2.14
+^^J LaTeX document class for Lecture Notes in Computer Science]
% Options
\let\if@envcntreset\iffalse
\DeclareOption{envcountreset}{\let\if@envcntreset\iftrue}
@@ -21,6 +38,11 @@
\let\if@openbib\iffalse
\DeclareOption{openbib}{\let\if@openbib\iftrue}
+% languages
+\let\switcht@@therlang\relax
+\def\ds@deutsch{\def\switcht@@therlang{\switcht@deutsch}}
+\def\ds@francais{\def\switcht@@therlang{\switcht@francais}}
+
\DeclareOption*{\PassOptionsToClass{\CurrentOption}{article}}
\ProcessOptions
@@ -30,6 +52,145 @@
\setlength{\textwidth}{12.2cm}
\setlength{\textheight}{19.3cm}
+\renewcommand\@pnumwidth{2em}
+\renewcommand\@tocrmarg{3.5em}
+%
+\def\@dottedtocline#1#2#3#4#5{%
+ \ifnum #1>\c@tocdepth \else
+ \vskip \z@ \@plus.2\p@
+ {\leftskip #2\relax \rightskip \@tocrmarg \advance\rightskip by 0pt plus 2cm
+ \parfillskip -\rightskip \pretolerance=10000
+ \parindent #2\relax\@afterindenttrue
+ \interlinepenalty\@M
+ \leavevmode
+ \@tempdima #3\relax
+ \advance\leftskip \@tempdima \null\nobreak\hskip -\leftskip
+ {#4}\nobreak
+ \leaders\hbox{$\m@th
+ \mkern \@dotsep mu\hbox{.}\mkern \@dotsep
+ mu$}\hfill
+ \nobreak
+ \hb@xt@\@pnumwidth{\hfil\normalfont \normalcolor #5}%
+ \par}%
+ \fi}
+%
+\def\switcht@albion{%
+\def\abstractname{Abstract.}
+\def\ackname{Acknowledgement.}
+\def\andname{and}
+\def\lastandname{\unskip, and}
+\def\appendixname{Appendix}
+\def\chaptername{Chapter}
+\def\claimname{Claim}
+\def\conjecturename{Conjecture}
+\def\contentsname{Table of Contents}
+\def\corollaryname{Corollary}
+\def\definitionname{Definition}
+\def\examplename{Example}
+\def\exercisename{Exercise}
+\def\figurename{Fig.}
+\def\keywordname{{\bf Key words:}}
+\def\indexname{Index}
+\def\lemmaname{Lemma}
+\def\contriblistname{List of Contributors}
+\def\listfigurename{List of Figures}
+\def\listtablename{List of Tables}
+\def\mailname{{\it Correspondence to\/}:}
+\def\noteaddname{Note added in proof}
+\def\notename{Note}
+\def\partname{Part}
+\def\problemname{Problem}
+\def\proofname{Proof}
+\def\propertyname{Property}
+\def\propositionname{Proposition}
+\def\questionname{Question}
+\def\remarkname{Remark}
+\def\seename{see}
+\def\solutionname{Solution}
+\def\subclassname{{\it Subject Classifications\/}:}
+\def\tablename{Table}
+\def\theoremname{Theorem}}
+\switcht@albion
+% Names of theorem like environments are already defined
+% but must be translated if another language is chosen
+%
+% French section
+\def\switcht@francais{%\typeout{On parle francais.}%
+ \def\abstractname{R\'esum\'e.}%
+ \def\ackname{Remerciements.}%
+ \def\andname{et}%
+ \def\lastandname{ et}%
+ \def\appendixname{Appendice}
+ \def\chaptername{Chapitre}%
+ \def\claimname{Pr\'etention}%
+ \def\conjecturename{Hypoth\`ese}%
+ \def\contentsname{Table des mati\`eres}%
+ \def\corollaryname{Corollaire}%
+ \def\definitionname{D\'efinition}%
+ \def\examplename{Exemple}%
+ \def\exercisename{Exercice}%
+ \def\figurename{Fig.}%
+ \def\keywordname{{\bf Mots-cl\'e:}}
+ \def\indexname{Index}
+ \def\lemmaname{Lemme}%
+ \def\contriblistname{Liste des contributeurs}
+ \def\listfigurename{Liste des figures}%
+ \def\listtablename{Liste des tables}%
+ \def\mailname{{\it Correspondence to\/}:}
+ \def\noteaddname{Note ajout\'ee \`a l'\'epreuve}%
+ \def\notename{Remarque}%
+ \def\partname{Partie}%
+ \def\problemname{Probl\`eme}%
+ \def\proofname{Preuve}%
+ \def\propertyname{Caract\'eristique}%
+%\def\propositionname{Proposition}%
+ \def\questionname{Question}%
+ \def\remarkname{Remarque}%
+ \def\seename{voir}
+ \def\solutionname{Solution}%
+ \def\subclassname{{\it Subject Classifications\/}:}
+ \def\tablename{Tableau}%
+ \def\theoremname{Th\'eor\`eme}%
+}
+%
+% German section
+\def\switcht@deutsch{%\typeout{Man spricht deutsch.}%
+ \def\abstractname{Zusammenfassung.}%
+ \def\ackname{Danksagung.}%
+ \def\andname{und}%
+ \def\lastandname{ und}%
+ \def\appendixname{Anhang}%
+ \def\chaptername{Kapitel}%
+ \def\claimname{Behauptung}%
+ \def\conjecturename{Hypothese}%
+ \def\contentsname{Inhaltsverzeichnis}%
+ \def\corollaryname{Korollar}%
+%\def\definitionname{Definition}%
+ \def\examplename{Beispiel}%
+ \def\exercisename{\"Ubung}%
+ \def\figurename{Abb.}%
+ \def\keywordname{{\bf Schl\"usselw\"orter:}}
+ \def\indexname{Index}
+%\def\lemmaname{Lemma}%
+ \def\contriblistname{Mitarbeiter}
+ \def\listfigurename{Abbildungsverzeichnis}%
+ \def\listtablename{Tabellenverzeichnis}%
+ \def\mailname{{\it Correspondence to\/}:}
+ \def\noteaddname{Nachtrag}%
+ \def\notename{Anmerkung}%
+ \def\partname{Teil}%
+%\def\problemname{Problem}%
+ \def\proofname{Beweis}%
+ \def\propertyname{Eigenschaft}%
+%\def\propositionname{Proposition}%
+ \def\questionname{Frage}%
+ \def\remarkname{Anmerkung}%
+ \def\seename{siehe}
+ \def\solutionname{L\"osung}%
+ \def\subclassname{{\it Subject Classifications\/}:}
+ \def\tablename{Tabelle}%
+%\def\theoremname{Theorem}%
+}
% Ragged bottom for the actual page
\def\thisbottomragged{\def\@textbottom{\vskip\z@ plus.0001fil
@@ -398,8 +559,9 @@
\def\l@chapter#1#2{\addpenalty{-\@highpenalty}
\vskip 1.0em plus 1pt \@tempdima 1.5em \begingroup
- \parindent \z@ \rightskip \@pnumwidth
- \parfillskip -\@pnumwidth
+ \parindent \z@ \rightskip \@tocrmarg
+ \advance\rightskip by 0pt plus 2cm
+ \parfillskip -\rightskip \pretolerance=10000
\leavevmode \advance\leftskip\@tempdima \hskip -\leftskip
{\large\bfseries\boldmath#1}\ifx0#2\hfil\null
\else
@@ -415,7 +577,8 @@
\@tempdima \z@
\begingroup
\parindent \z@ \rightskip \@tocrmarg
- \parfillskip -\@tocrmarg
+ \advance\rightskip by 0pt plus 2cm
+ \parfillskip -\rightskip \pretolerance=10000
\leavevmode \advance\leftskip\@tempdima \hskip -\leftskip
#1\nobreak
\leaders\hbox{$\m@th \mkern \@dotsep mu.\mkern
@@ -423,6 +586,16 @@
\nobreak\hbox to\@pnumwidth{\hss #2}\par
\penalty\@highpenalty \endgroup}
+\def\l@author#1#2{\addpenalty{\@highpenalty}
+ \@tempdima=15\p@ %\z@
+ \begingroup
+ \parindent \z@ \rightskip \@tocrmarg
+ \advance\rightskip by 0pt plus 2cm
+ \pretolerance=10000
+ \leavevmode \advance\leftskip\@tempdima %\hskip -\leftskip
+ \textit{#1}\par
+ \penalty\@highpenalty \endgroup}
+
\setcounter{tocdepth}{0}
\newdimen\tocchpnum
\newdimen\tocsecnum
@@ -650,8 +823,6 @@
\newcounter{@inst}
\newcounter{@auth}
\newcounter{auco}
-\def\andname{and}
-\def\lastandname{\unskip, and}
\newdimen\instindent
\newbox\authrun
\newtoks\authorrunning
@@ -679,8 +850,9 @@
\noindent$^{\the@inst}$\enspace\ignorespaces}%
\setbox0=\vbox{\def\thanks##1{}\@institute}%
\ifnum\c@@inst=1\relax
+ \gdef\fnnstart{0}%
\else
- \setcounter{footnote}{\c@@inst}%
+ \xdef\fnnstart{\c@@inst}%
\setcounter{@inst}{1}%
\noindent$^{\the@inst}$\enspace
\fi
@@ -696,12 +868,18 @@
\def\inst#1{\unskip$^{#1}$}
\def\fnmsep{\unskip$^,$}
\def\email#1{{\tt#1}}
-\AtBeginDocument{\@ifundefined{url}{\def\url#1{#1}}{}}
+\AtBeginDocument{\@ifundefined{url}{\def\url#1{#1}}{}%
+\@ifpackageloaded{babel}{%
+\@ifundefined{extrasenglish}{}{\addto\extrasenglish{\switcht@albion}}%
+\@ifundefined{extrasfrenchb}{}{\addto\extrasfrenchb{\switcht@francais}}%
+\@ifundefined{extrasgerman}{}{\addto\extrasgerman{\switcht@deutsch}}%
+}{\switcht@@therlang}%
+}
\def\homedir{\~{ }}
\def\subtitle#1{\gdef\@subtitle{#1}}
\clearheadinfo
-
+%
\renewcommand\maketitle{\newpage
\refstepcounter{chapter}%
\stepcounter{section}%
@@ -756,9 +934,8 @@
\protected@xdef\scratch{\the\tocauthor}%
\protected@xdef\toc@uthor{\scratch}%
\fi
- \addtocontents{toc}{{\protect\raggedright\protect\leftskip15\p@
- \protect\rightskip\@tocrmarg
- \protect\itshape\toc@uthor\protect\endgraf}}%
+ \addtocontents{toc}{\noexpand\protect\noexpand\authcount{\the\c@auco}}%
+ \addcontentsline{toc}{author}{\toc@uthor}%
\if@runhead
\if!\the\authorrunning!
\value{@inst}=\value{@auth}%
@@ -778,7 +955,7 @@
\markboth{\@author}{\@title}%
\fi
\endgroup
- \setcounter{footnote}{0}%
+ \setcounter{footnote}{\fnnstart}%
\clearheadinfo}
%
\def\@maketitle{\newpage
@@ -795,6 +972,7 @@
\unskip,
\fi}%
\begin{center}%
+ \let\newline\\
{\Large \bfseries\boldmath
\pretolerance=10000
\@title \par}\vskip .8cm
@@ -978,10 +1156,6 @@
\rightmargin\leftmargin}\item[\hskip\labelsep
\bfseries\abstractname]}
{\endlist}
-\renewcommand{\abstractname}{Abstract.}
-\renewcommand{\contentsname}{Table of Contents}
-\renewcommand{\figurename}{Fig.}
-\renewcommand{\tablename}{Table}
\newdimen\headlineindent % dimension for space between
\headlineindent=1.166cm % number and text of headings.
@@ -1013,4 +1187,4 @@
\setlength\tabcolsep{1.4\p@}
\endinput
-
+%end of file llncs.cls
Modified: doc/trunk/pynchon-gate/pynchon-spec.txt
===================================================================
--- doc/trunk/pynchon-gate/pynchon-spec.txt 2007-04-18 19:44:53 UTC (rev 1779)
+++ doc/trunk/pynchon-gate/pynchon-spec.txt 2007-04-24 12:47:49 UTC (rev 1780)
@@ -1,8 +1,9 @@
$Id$
Pynchon Gate Protocol Draft Specification
- (Spec draft by Nick Mathewson;
- original design by Bram Cohen and Len Sassaman)
+ (Spec draft by Nick Mathewson with
+ contributions from Len Sassaman;
+ original design by Bram Cohen and Len Sassaman)
@@ -505,6 +506,8 @@
[XXXX Say something about TLS sessions.]
+ [XXXX Do we want to do away with SHORT_PIR_REQUESTS?]
+
The PIR message format is as follows:
TYPE [1 octet]
@@ -562,9 +565,10 @@
1. The first message MUST be sent by the client, and must be a VERSION
message listing all the protocol versions that the client
- understands. (Currently, the only known version is 0.) The server
- MUST reply with a VERSION message choosing a single one of those
- versions, or with an ERROR message (code 'BAD_VERSION').
+ understands. (Currently, the only known version is 0.XXXXX)
+ The server MUST reply with a VERSION message choosing a single
+ one of those versions, or with an ERROR message (code
+ 'BAD_VERSION').
Once the client receives the VERSION message from the server, it
then sends one or more messages to the server. The server replies
@@ -648,22 +652,33 @@
4.2. Retrieving a bucket
To download a specific bucket B from cycle CYC of nymserver NYMID, clients
- should behave as follows:
+ should behave as follows: XXXX
1. Connect to K chosen distributors and negotiate protocol versions, if
not already connected.
- 2. Generate K-1 random seeds SEED[1..K-1].
- 3. Let MASK = SEED[1] XOR SEED[2] ... XOR SEED[K-1]
+ 2. Generate 2 sets of K-1 random seeds ALPHA_SEED[1..K-1],
+ ETA_SEED[1..K-1].
+ 3. Let MASK = ALPHA_SEED[1] XOR ALPHA_SEED[2] ... XOR ALPHA_SEED[K-1]
4. Flip the B'th bit of MASK.
- 5. Permute the chosen distributors into a randomly selected order.
+ 5. Generate ETA_MASK as a random string of bitlength idential to
+ MASK.
+ 6. Permute the chosen distributors into a randomly selected order.
Send the first K-1 distributors SHORT_PIR_REQUEST messages, each
- with a different one of the K-1 elements of SEED
+ with a different one of the K-1 elements of both ALPHA_SEED and
+ ETA_SEED, randomizing the which set's element is chosen to be sent
+ first..
- Send the last distributor a LONG_PIR_REQUEST message with MASK.
+ Send the last distributor a LONG_PIR_REQUEST message with MASK for
+ both sets, randomizing which set's MASK is sent first.
- 6. Compute the XOR of the responses. This is the value of the bucket.
+ 7. Cache the values of each element of ETA_SET and the corresponding
+ distributor to which it was sent.
+ 8. Compute the XOR of the ALPHA_SET responses. This is the value of
+ the bucket. If this fails, see the section on Byzantine server
+ detection (Section 4.4).
+
4.3. Retrieving a cycle's worth of messages.
To download _all_ of its messages for a given cycle CYC of nymserver
@@ -704,13 +719,40 @@
8. Unpack the messages in the bucket.
- If a client retrieves a bucket with an in-correct hash, it must have
- received an incorrect PIR response from at least one distributer. The
- client then re-downloads the offending bucket, as follows:
+// If a client retrieves a bucket with an in-correct hash, it must have
+// received an incorrect PIR response from at least one distributer. The
+// client then re-downloads the offending bucket, as follows:
{XXXX how exactly do we reattempt a bucket? Is it better to try a
completely different set of servers? Or to try replacing a just a
couple of the distributors in the current PIR set?}
+ {XXXX Do the Byzantine detection, and correct for it. However, I think
+ that round is a wash, and you should either punt to the next one,
+ or re-download with a new set of servers, minus the Byzantine ones.
+ Thoughts? --LS.}
+
+4.4. Byzantine server detection.
+
+ {XXXX We need to introduce the validator in the architecture section.}
+
+ If a client retrieves a bucket with an incorrect hash, it must have
+ received an incorrect PIR response from at least one distributor. The
+ client can then attempt to identify which distributor or distributors
+ provided the incorrect response as follows:
+
+ 1. Connect to the validator.
+ 2. Submit ETA_SEED[1..K-1] and ETA_MASK.
+ 3. Compare the results from the validator with the previously cached
+ distributor responses for the elements of ETA_SET. If mis-matched,
+ flag the offending distributor(s) as having returned invalid
+ responses.
+ [XXXX 4. Add the Byzantine distributor to a list of servers never to
+ use? After some number of repeat offenses? Should we send it random
+ junk instead of an ALPHA_SET? What about notification to the system
+ as a whole? --LS.]
+
+ [What about performance issues on the validator? --LS.]
+
5. Account administration
{XXXX Write me. Clients need a way to set preferences, create accounts,
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/