commit 8409ac89177e4218abbfa422cb9354c39d12ec32
parent 07db1165214920e669f1d50f62e54010474858a0
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date: Tue, 24 May 2022 21:49:01 +0200
mutator change
Diffstat:
1 file changed, 21 insertions(+), 27 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -1576,10 +1576,6 @@ BEGIN
<dd>
the variable-length extended query. Optional.
</dd>
- <dt>MUTATOR</dt>
- <dd>
- The 32-bit mutator for the result filter.
- </dd>
</dl>
</section>
<section anchor="result_filter">
@@ -1602,30 +1598,9 @@ BEGIN
it is possible that a desireable result is filtered by a result
filter because of a false-positive test.
</t>
- <t>
- To address this problem, R<sup>5</sup>N uses a <tt>MUTATOR</tt> value
- which allows block implemenations that use probabilistic data
- structures for result filters to additionally "randomize" the
- computation of a probabilistic data structure while remaining
- deterministic across peers. The 32-bit <tt>MUTATOR</tt>
- value is set by the peer initiating the GET request, and changed
- every time the GET request is repeated by the initiator. Peers
- forwarding GET requests <bcp14>MUST</bcp14> not change the
- mutator value included in the <tt>GetMessage</tt> as they might not
- be able to recalculate the result filter with a different <tt>MUTATOR</tt>
- value.
- </t>
- <t>
- By properly including the <tt>MUTATOR</tt> value in a probabilistic process, repeated
- requests have statistically independent probabilities of creating
- false-positives in a result filter. Thus, even if for one request
- a result filter may exclude a result as a false-positive
- match, subsequent requests are likely to not have the same
- false-positives.
- </t>
- <t>
+ <t>
How exactly a block result is added to a result filter
- (together with the <tt>MUTATOR</tt>) <bcp14>MUST</bcp14> be
+ <bcp14>MUST</bcp14> be
specified as part of the definition of a block type.
</t>
</section>
@@ -2208,6 +2183,25 @@ gnunet+tcp://12.3.4.5/ \
array. In particular, <tt>K</tt> is never transmitted.
</dd>
</dl>
+<t>
+ R<sup>5</sup>N HELLO blocks use a <tt>MUTATOR</tt> value
+ to additionally "randomize" the computation of the bloom filter while remaining
+ deterministic across peers. The 32-bit <tt>MUTATOR</tt>
+ value is set by the peer initiating the GET request, and changed
+ every time the GET request is repeated by the initiator. Peers
+ forwarding GET requests <bcp14>MUST</bcp14> not change the
+ mutator value included in the <tt>RESULT_FILTER</tt> as they might not
+ be able to recalculate the result filter with a different <tt>MUTATOR</tt>
+ value.
+ </t>
+ <t>
+ Consequently, repeated
+ requests have statistically independent probabilities of creating
+ false-positives in a result filter. Thus, even if for one request
+ a result filter may exclude a result as a false-positive
+ match, subsequent requests are likely to not have the same
+ false-positives.
+ </t>
<t>
To filter results of HELLO blocks using the Bloom filter, the
