commit cc73546624d723535ac90fe2e293a7e08b2c1fc6
parent da66ae0aca4a31437228c9382da78bd6058b1128
Author: Elias Summermatter <elias.summermatter@seccom.ch>
Date: Wed, 16 Jun 2021 01:46:31 +0200
Fixed some more stuff in the IBF
Diffstat:
1 file changed, 49 insertions(+), 159 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
@@ -2537,155 +2537,25 @@ peers set +---------+ +---------+ +---------+
===>: Always answer needed.
]]></artwork>
</figure>
+ <!-- CORRECT -->
<t>
- A possible implementation of the check in pseudocode could look as follows:
+ In the message control flow its important to ensure that no duplicated message are received
+ (Except inquiries where collisions are possible) and only messages are received which are compliant
+ with the flow in <xref target="security_generic_functions_mfc_chain" format="default" />.
+ To link messages the SHA-512 element hashes that are part of all messages except in the
+ <em><xref target="messages_inquiry" format="title" /></em> message can be used.
+ To link an <em><xref target="messages_inquiry" format="title" /></em> message to an
+ <em><xref target="messages_offer" format="title" /></em> message
+ the SHA-512 hash from the offer has to be salted and converted to the IBF-Key (as described in
+ <xref target="ibf_format_id_generation_pseudo_code" format="default" />) this then can
+ be matched against the received <em><xref target="messages_inquiry" format="title" /></em> message.
</t>
- <figure anchor="security_generic_functions_mfc_code">
- <artwork name="" type="" align="left" alt=""><![CDATA[
-# ValidStates:
-# The following message states are used to track the message flow.
-# - NOT_INITIALIZED: Fresh initialized value
-# - SENT: Element has been sent
-# - EXPECTED: Element is expected
-# - RECEIVED: Element is received
-
-# Function to initialize new store
-# Output:
-# Returns empty store
-FUNCTION initialize_store()
- RETURN {}
-FUNCTION END
-
-# Function to initialize a store element
-# Output:
-# Returns an empty element for the store
-FUNCTION initialize_element()
- RETURN {
- INQUIRY: NOT_INITIALIZED,
- OFFER: NOT_INITIALIZED,
- DEMAND: NOT_INITIALIZED,
- ELEMENT: NOT_INITIALIZED
- }
-FUNCTION END
-
-# Function called every time a new message is transmitted to other peer
-# Input:
-# store: Store created by the initialize_store() function
-# mt: The message that was sent type e.g. INQUIRY or DEMAND
-# hash: The hash of the element which is sent
-# Output:
-# Returns TRUE if the message flow was followed, otherwise FALSE
-FUNCTION send(store, mt, hash)
-
- IF NOT hash IS IN store
- store_element = initialize_element()
- ELSE
- store_element = store.get(hash)
- END IF
-
- CASE based ON mt
- CASE INQUIRY
- IF store_element.INQUIRY == NOT_INITIALIZED
- store_element.INQUIRY = SENT
- ELSE
- RETURN FALSE
- END IF
- CASE OFFER
- IF store_element.OFFER == NOT_INITIALIZED
- store_element.OFFER = SENT
- store_element.DEMAND = EXPECTED
- ELSE
- RETURN FALSE
- END IF
- CASE DEMAND
- IF store_element.DEMAND == NOT_INITIALIZED AND
- (store_element.INQUIRY == SENT OR
- store_element.INQUIRY == NOT_INITIALIZED)
- store_element.DEMAND = SENT
- store_element.ELEMENT = EXPECTED
- ELSE
- RETURN FALSE
- END IF
- CASE ELEMENT
- IF store_element.ELEMENT == NOT_INITIALIZED AND
- store_element.OFFER == SENT
- store_element.ELEMENT = SENT
- ELSE
- RETURN FALSE
- END IF
- DEFAULT
- RETURN FALSE
- CASE END
- ADD OR UPDATE KEY hash IN store WITH store_element
- RETURN TRUE
-FUNCTION END
-
-# Function called every time a new message is received from the other peer
-# Input:
-# store: Store created by the initialize_store() function
-# mt: The message that was received type e.g. INQUIRY or DEMAND
-# hash: The hash of the element which is received
-# Output:
-# Returns TRUE if the message flow was followed, otherwise FALSE
-FUNCTION receive (store, mt, hash)
- IF NOT hash IS IN store
- store_element = initialize_element()
- ELSE
- store_element = store.get(hash)
- END IF
-
- CASE based on mt
- CASE INQUIRY
- IF store_element.INQUIRY == NOT_INITIALIZED
- store_element.INQUIRY = RECEIVED
- ELSE
- RETURN FALSE
- END IF
- CASE OFFER
- IF store_element.OFFER == NOT_INITIALIZED
- store_element.OFFER = RECEIVED
- ELSE
- RETURN FALSE
- END IF
- CASE DEMAND
- IF store_element.DEMAND == EXPECTED AND
- store_element.OFFER == SENT
- store_element.DEMAND = RECEIVED
- ELSE
- RETURN FALSE
- END IF
- CASE ELEMENT
- IF store_element.ELEMENT == EXPECTED AND
- store_element.DEMAND == SENT
- store_element.ELEMENT = RECEIVED
- ELSE
- RETURN FALSE
- END IF
- DEFAULT
- RETURN FALSE
- CASE END
- ADD OR UPDATE KEY hash IN store WITH store_element
- RETURN TRUE
-FUNCTION END
-
-# Function called when the union operation is finished to ensure that all demands have
-# been fulfilled
-# Input:
-# store: Store created by the initialize_store() function
-# Output:
-# Returns TRUE if all demands have been fulfilled otherwise FALSE
-FUNCTION check_if_synchronisation_is_complete(store):
- FOR element in store.getAll()
- IF element.ELEMENT == EXPECTED OR
- element.DEMAND == EXPECTED
- RETURN FALSE
- IF END
- FOR END
- RETURN TRUE
-FUNCTION END
-
- ]]></artwork>
- </figure>
+ <t>
+ In the end of the set reconciliation operation after receiving and sending the
+ <em><xref target="messages_done" format="title" /></em> message it should be checked
+ that all demands have been satisfied and all elements have been received.
+ </t>
+ <!-- CORRECT -->
<t>
This is based on <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>, section 5.3 (Message Control Flow).
</t>
@@ -2873,6 +2743,21 @@ END FUNCTION
abort the protocol if its resource limits are likely to be
exceeded, or if the size is implausible for the given operation.
</t>
+ <!-- CORRECT -->
+ <!-- BUGTRACKER -->
+ <t>
+ It needs to be checked that that the offset (message field "OFFSET")
+ for every received <em><xref target="messages_ibf" format="title" /></em> message
+ is strictly monotonic increasing and is a multiple of the MAX_BUCKETS_PER_MESSAGE
+ defined in the <xref target="constants" format="title" /> section otherwise the
+ connection MUST be aborted.
+ </t>
+ <t>
+ An other sanity check is to ensure that the "OFFSET" message field never
+ is a higher than the "IBF SIZE" field in the <em><xref target="messages_ibf" format="title" /></em>
+ message.
+ </t>
+ <!-- CORRECT -->
</dd>
<dt><xref target="messages_ibf_last" format="title" /></dt>
<dd>
@@ -2882,19 +2767,24 @@ END FUNCTION
should conclude the transmission of the IBF and a change to the <strong>Active Decoding</strong>
phase should be ensured.
</t>
+ <!-- CORRECT -->
+ <!-- BUGTRACKER -->
+ <t>
+ To verify that all IBFs have been received a simple validation can be made
+ the number of buckets in the <em><xref target="messages_ibf_last" format="title" /></em> message
+ added to the value in the message OFFSET field should always be equal to the "IBF SIZE".
+ </t>
+ <t>
+ Further plausibility checks can be made. One is to ensure that after each active/passive
+ switch the IBF can never more than double in size. An other plausibility check is
+ is that an IBF probably never will be bigger than the byzantine upperbound multiplied by two.
+ The third plausibility check is to take successfully decoded IBF keys (received offers and demands)
+ into account and validating the size of the received IBF with the in <xref target="performance_formula_ibf_parameters_code" format="default" />
+ described function get_next_ibf_size(). If any of these three checks fail the operation
+ must be aborted.
+ </t>
+ <!-- CORRECT -->
</dd>
- <!-- FIXME: we can also receive an IBF_LAST in this state,
- here additional sanity checks, like that we have received
- all of the other fragments/parts of the IBF first and
- that the parameters are thus consistent apply. @Christian So we would have
- to transmit the number of IBF slices that will be transmitted first
- to do this check right? Empfangen in mononer rheienfolge und prüfen das
- es der letzte war. Sizes immer gleich?
- Grösse plausible check:
- - initiale bzyantine Upper bound verküpfen auf setsize differenz
- - Wiederholt das ding kann sich nur verdoppeln
- - Genau prüffen durch offer/demands
- -->
</dl>
</section>
