Better ArithmeticCircuit struct and json

[namnc]

We may have redundant info now so we may want to streamline the output.

Below is Bristol format we can extend it: https://nigelsmart.github.io/MPC-Circuits/

[namnc]

We may also want the gates to have some topological order (e.g. a gate id i > j will only use inputs from gates with id at most j).

[namnc]

I made this python script to convert our json circuit to a sort of arithmetic bristol format during EthTaipei hackathon: https://gist.github.com/namnc/1351994aacb25054ee4696c52ad0802e

This can be used with Kevin's MP-SPDZ loader here: https://gist.github.com/mhchia/79a26963664accbafebb27cf19b8e562#file-circuit_arith-py

It basically parses the json and build a tree with multiple roots and generate id from the leaves in a topological order.

[namnc]

I will proceed with marking main component inputs and outputs.

[namnc]

@voltrevo here ser!

[namnc]

Latest script to migrate to rs https://github.com/namnc/circom-mp-spdz/blob/main/arithc_to_bristol.py

[namnc]

Requirement: https://hackmd.io/Iuu9yge4ShKBjawAcmFjvw?view#12-Arithmetic-circuit-to-bristol-fashion-circuit

[voltrevo]

Below is Bristol format we can extend it

I think extending the format is necessary to address the following problems:

• Bristol format specifies the number of input and output wires, but not which wires they are
• There is no concept of a constant in Bristol format

Currently if you have a circuit like c = a + b + 1 it would look something like this:

2 5              # num_gates, num_wires
3 1 1            # 3 inputs
1 1              # 1 output

2 1 0 1 3 AAdd
2 1 3 2 4 AAdd

To use that circuit, you have to know somehow that the third input is actually a constant with value 1 that needs to be supplied. You also have to know that the inputs a and b correspond to wires 0 and 1 and output c corresponds to wire 4.

I realize that in https://hackmd.io/Iuu9yge4ShKBjawAcmFjvw?view#12-Arithmetic-circuit-to-bristol-fashion-circuit these issues are addressed by circuit_info.json, but that seems like a poor solution. This information is part of the circuit - why leave the main circuit file incomplete and reliant on another small file? How about this instead?

2 5 2 1          # num_gates, num_wires, num_inputs, num_outputs

"a" "b"
"c"

2 1 0 1 3 AAdd
1 1 1 2 Constant
2 1 3 2 4 AAdd

Above:

• the inclusion of 2 extra numbers on the first line marks that the new format is being used, which adds a line for inputs and a line for outputs
• constants are handled with a constant operation, taking an input as a value (instead of a wire index) and assigning that value to its output wire
• the lowest wire ids are the inputs and the highest wire ids are the outputs

Alternatively, I feel we could just make an entirely new format that would be even better:

! super duper circuit format

# comments are allowed, not just my annotations

inputs {
    "a" 0
    "b" 1
}

outputs {
    "c" 4
}

program {
    # must be topologically sorted
    3 = Add(0, 1)
    2 = Constant(1)
    4 = Add(3, 2)
}

# naturally allows for extensions by adding more blocks

# eg
# mpc {
#     "alice" {
#         inputs "a"
#     }
#     "bob" {
#         inputs "b"
#         outputs "c"
#     }
# }

Or just a json format:

{
    "inputs": ["a", "b"],
    "outputs": ["c"],
    "program": [
        ["Add", 0, 1, 3],
        ["Constant", 1, 2],
        ["Add", 3, 2, 4]
    ]
}

I'm confused. Maybe I'm missing something. Am I missing something?

In the contexts where Bristol has been used elsewhere, surely it also suffers from these issues? How are these issues addressed in those contexts, and why would they not have been addressed by updating the format?

[namnc]

I think the concept of "constant" has not been present in the Bristol format before. Indeed we need to have a separate file to indicate which wire is a constant and what value.

In your solution you in fact seems to introduce a new gate "Constant" that sets a public value to a wire. I think we can make your proposal the new format of our circuit output (json).

But in the end, the program is not for human but for machine to read. So whatever semantic we add might be only useful when we visualize the circuit so human can read it.

[brech1]

I think it is ok for the Bristol format file not to have any information about the constants since these are just a different type of input. The circuit file purpose is to describe the circuit structure.

But primarily I think we should abstain from modifying the Bristol format, or if we have to ideally we should still be able to compile to it, and then our own format.

[brech1]

I think we're on a different stage now than when this issue was created, the ArithmeticCircuit struct has no duplicated data, and it has been build towards better processing efficiency. With this structure we should be able to compile to whatever output we want, as a post-processing step.