Threshold Cryptoconditions Clarifications

[sappenin]

This issue was originally submitted by @nbougalis at https://github.com/interledger/rfcs/issues/209.

(Quoting from from @nbougalis)

The existing specification of THRESHOLD-SHA-256 can be somewhat confusing.

The standard should be amended to explicitly define that each sub-entry in an M-of-N threshold is given a hard-coded weight of exactly 1, and that for a valid fulfillment, the number of subfulfillments present will be exactly M. This means that the threshold can be derived by counting the subfulfillments present.

Additionally, althought implicit (since the condition generated from such a fulfillment won't match) the standard should, explicitly, specify that a fulfillment that contains (a) a number of subfulfillments other than exactly M; or (b) one where the number of subfullfilments and subconditions present is not exactly N is not valid.

Far from a simple optimization to save space, not including the count and requiring exactly M fulfillments has a valuable cryptographic purpose: to prevent malleability attacks. This is not mentioned anywhere. For completeness and as a precaution against an accidental future change that would compromise this critical property, we should add a paragraph or note that explains the rationale behind this.

To clarify, consider a 3-of-5 condition. Now, assume a fufillment for that condition is presented that contains 4 subfulfillments and 1 subcondition. Such a fulfillment, if it were to be valid against the condition, would contain one redundant signature. Removing any one at random and replacing it with its subcondition would result in a different but still valid fulfillment.

[sappenin]

I think the comment above from @nbougalis is a proper reading of the spec language as defined, but is this actually what we want? (Also tagging @adrianhopebailie and @justmoon for input)

In other words, there are two questions that are ambiguous to me:

1. Should a threshold condition/fulfillment allow "weighting"?
2. Can/Should a 2-of-2 ThresholdFulfillment verify/validate with a 1-of-2 ThresholdCondition?

For example, section 8.3.4 of the spec says,

subfulfillments: A SET OF fulfillments. The number of elements in this set is equal to the threshold therefore implementations use the length of this SET as the threshold value when deriving the fingerprint of this crypto-condition.

This aligns with what @nbougalis wrote above, but consider the following example:

Imagine I create a 1-of-2 ThresholdSha256Condition (i.e., Threshold = 1), and then I create a ThresholdSha256Fulfillment with 2 sub-fulfillments. In theory, the ThresholdSha256Fulfillment should verify with the 1-of-2 ThresholdSha256Condition because the number of fulfillments is 2, which is greater-than 1 (my notion of a "threshold" is that you must meet or exceed a threshold, so publishing 1 or 2 sub-fulfillments should fulfill the condition).

However, the Java implementation (and section 8.3.4 of the spec) seem to negate this idea. Anytime we create a ThresholdSha256Fulfillment with two sub-fulfillments, the threshold gets bumped to 2, which means the fulfillment does not verify with the 1-of-2 threshold condition.

Am I misunderstanding the meaning of "threshold" here? It seems like a fulfillment with 2 sub-fulfillments should verify a 1-of-2 Threshold condition.

[adrianhopebailie]

@nbougalis is correct that the spec could be clearer to be more explicit in how subconditions and subfulfillments are treated and weighted.

In theory, the ThresholdSha256Fulfillment should verify with the 1-of-2 ThresholdSha256Condition because the number of fulfillments is 2, which is greater-than 1 (my notion of a "threshold" is that you must meet or exceed a threshold, so publishing 1 or 2 sub-fulfillments should fulfill the condition).

Correct but this is an implementation optimization. The Java implementation could be updated to provide helpers where the threshold is provided (as opposed to being implied) and as a result the condition is derived correctly.

I think we should separate the implementation logic (flexible) from the encoding logic (deterministic) which is defined in the spec. The spec says that when decoding a fulfillment the number of subfulfillments is equal to the threshold but that doesn't impact how an implementation chooses to determine the threshold when constructing a fulfillment from its parts (subconditions and subfulfillments).

i.e. If the above-mentioned ThresholdSha256Fulfillment with 2 sub-fulfillments is to be encoded and sent over the wire then one of the subfulfillments must be encoded as a subcondition (not a subfulfillment) otherwise the system that decodes it will misinterpret it as a 2-of-2 instead of a 1-of-2.

[sappenin]

i.e. If the above-mentioned ThresholdSha256Fulfillment with 2 sub-fulfillments is to be encoded and sent over the wire then one of the subfulfillments must be encoded as a subcondition (not a subfulfillment) otherwise the system that decodes it will misinterpret it as a 2-of-2 instead of a 1-of

@adrianhopebailie Great context overall! I think your statement above (quoted) is the salient point -- that in actuality, a 1-of-2 ThresholdFulfillment with two sub-fulfillments doesn't really exist -- such a thing (with 2 sub-fulfillments) would actually be a 2-of-2 Threshold, per the spec.

[adrianhopebailie]

👍 - https://github.com/hyperledger/quilt/pull/94 is a great improvement on the implementation.

Let's keep this open though as I should update the spec per @nbougalis point in the OP