Introduce explicit model for the "circuit definition"

[sbellem]

NOTE: This issue is Work In Progress.

Quoting the Internet Draft (Introduction, second paragraph):

The validation function for these compound signatures takes as input the fingerprint of the circuit, called the condition, the circuit definition and minimum required logic gates with their inputs, called the fulfillment, and a message.

            CircuitDefinition
            -----------------
           /                 \
          /                + inputs
         /                     \
    Condition              Fulfillment

Problem

Both the Condtion and Fulfillment are represented by classes, but the circuit definition is somewhat implicit, hidden within the Fulfillment model/class. This is somewhat problematic or cumbersome for applications to construct Fulfillment instances. That is, given a Condition instance (URI or binary form). even though one may have all the necessary secret information (inputs), one is lacking the circuit definition (topology), which is "hidden" behind the fingerprint of the Condition instance.

Proposed Solution

In order to address this problem, this issue wishes to introduce an additional class, say CircuitDefinition, which would act as the bridge between the Condition and Fulfillment classes. When composing a Condition, one would first instantiate a CircuitDefinition object, from which a Condition instance could be generated, from which the different encodings can be generated (binary, URI, and JSON). Using the same CircuitDefinition instance, one could feed it inputs, such that a Fulfillment instance could then be generated.

In this way, applications would have a direct, clear, and clean way to communicate the circuit definition that is required by those who are constructing a Fulfillment instance.

Modeling a Crypo-Conditions Circuit Definition in Python

This is an "open question".

networkx

Since a boolean circuit can be viewed as a directed acyclic graph, one approach could be to use the Networkx library.

NOTE: The model will need to account for the fact that given inputs will belong to specific Conditions (edges, or vertices, within the graph). This shouldn't be a problem though, as long as the edges/vertices have attributes that identify the Conditions. Since Conditions are uniquely identified via their URI, or binary forms, they can be used as an "indexing" mechanism.

pyeda

Have yet to look into it. docs: http://pyeda.readthedocs.io/en/latest/

Truth Tables

/cc @trentmc

[diminator]

I think you can distinguish a bit more precise:

• circuit topology: how things are wired up (electronic circuit schematic)
• circuit instantiation: the actual values/attributes for each component in the circuit (electronic circuit sizing)
• circuit fingerprint: condition = the compressed representation (electronic behavioral model, with limited verification capabilities: ie. check condition URI)
• circuit simulation: fulfillment = circuit topology + circuit instantiation+ inputs

[ttmc]

Maybe something like:

x = ed25519("insert public key for x here")
y = ed25519("insert public key for y here")
a = ed25519("insert public key for a here")
b = ed25519("insert public key for b here")
c = ed25519("insert public key for c here")
condition = (x or y) and (2 of {a, b, c})

Note: (x or y) is the same as (1 of {x, y})

and (u and v) is the same as (2 of {u, v})

It could also allow for intermediate variable definitions, e.g.

v1 = x or y
v2 = 2 of {a, b, c}
condition = v1 and v2

See https://docs.bigchaindb.com/projects/server/en/master/data-models/conditions.html

[sappenin]

This is a great issue - the problem outlined above has consumed quite a bit of my thought time lately. Unfortunately, while I don't have a concrete solution, I do have some thoughts that I hope relate.

First, this "circuit definition" problem appears to only manifest in the context of Threshold conditions. For example, given a preimage or prefix condition (specifically, a prefix condition without a threshold sub-condition), it's not so difficult to construct the "circuit definition" because those circuit definitions are quite simple and easily inferable from the spec. Ditto for Ed25519 and RSA Conditions - the circuitry is defined by each encryption algorithm.

IMHO, it's only with a threshold condition that inferring/knowing the "circuit definition" becomes a problem.

Second, there is an additional problem with Threshold Conditions. Setting aside the concept of "sub" conditions and fulfillments for a moment, the spec only provides room for two entities (Conditions + Fulfillments), but there seems to actually be a third entity that only appears when Threshold conditions are involved (I'm open to the idea that what I'm about to outline is the circuit definition problem, but I think it's subtly different):

To illustrate this missing entity problem:

1. Suppose I want to create a 1-of-2 ThresholdCondition where each subcondition is itself a Threshold condition (what's inside of each subcondition is not important for this thought excercise) and each subcondition is actually generated by two different parties (Alice and Bob).
2. To create the ThresholdCondition, I first need Alice and Bob to assemble their subfulfillments and give them to me. Let's call those subFulfillment1 and subFulfillment2.
3. Next, I create the main ThresholdFulfillment (aka, MainThresholdFulfillment) using subFulfillment1 and subFulfillment2 (and subCondition1 + subCondition2).
4. From the MainFulfillment, I generate a condition with a threshold of 1. Let's call this MainThresholdCondition.
5. Next, assume Alice wants to fulfill MainThresholdCondition. She will need to create a fulfillment that is not MainThresholdFulfillment because she doesn't have enough information to construct MainThresholdFulfillment (and she only needs 1 of the 2 anyway). So, Alice creates a new ThresholdFulfillment using her subfulfillment1. Let's call this new object SatisfyingThresholdFulfillment. Since this fulfillment contains 1 of the 2 fulfillments necessary to satisfy MainThresholdCondition, everything works.

Given the above example, you can see there are actually 3 objects at play, whereas the spec only seems to leave room for two objects:

1. MainThresholdFulfillment: Defines the original requirements of the contract that will need to be satisfied. Contains two private-keys, essentially, and is the original source of truth.

2. MainThresholdCondition: Defines the requirements that need to be satisfied. From the dictionary, "a state of affairs that must exist or be brought about before something else is possible or permitted."

3. SatisfyingThresholdulfillment(s): One or more fulfillments that would meet the requirements of MainThresholdCondition.

I'm curious if the above is merely a restatement of the circuit definition problem, or if there's actually an additional entity that needs to be defined in the spec when it comes to Threshold conditions. Currently, there are only (Condition + Fulfillment), but I feel like there should actually be a third concept, and "circuit definition" idea doesn't really seem to fix this problem - it's not that I need to know how the circuit works, it's that there's a difference between the schematic (MainFulfillment), the machine (MainCondition), and the "Key" (SatisfyingFulfillment).

[sbellem]

Thanks for the feedback @sappenin! I'll get back to you asap! Sorry for the delays!