We are exploring methods to enhance arithmetic operations using various types of adders, such as the Carry-Save Adder, Brent-Kung Adder, and others. Similarly, we are investigating optimization techniques for multiplication operations.
Thank you in advance!
Hello @pradeep508
Addition and multiplication operations are done using the TFHE-rs backend. If you want to experiment with different implementations then you need to update the backend. For example, you can change the addition function here.
Hi @ayoub
we are getting build error
error: failed to run custom build command for concrete-cpu v1.75.0 (/home/user/Desktop/concrete-main/backends/concrete-cpu/implementation)
Have you followed the provided instructions to build the Compiler here? More logs would also be helpful in identifying what’s failing.
building is not going propely. getting errors at every step.
FAILED: tools/concretelang/concrete-protocol/CMakeFiles/concrete-protocol.dir/concrete-protocol.capnp.c++.o
/home/user/Desktop/concrete/compilers/concrete-compiler/compiler/build/tools/concretelang/concrete-protocol/concrete-protocol.capnp.c++:44:62: error: extra ‘;’ [-Werror=pedantic]
44 | CAPNP_DEFINE_ENUM(KeyType_e9c66eb80e60b9ea, e9c66eb80e60b9ea);
installed rust not taken into account while building
Can you please provide the steps? how to build with necessary prerequisites.
thanks in advance
Which compiler versions are you using? For Rust, I guess it’s maybe your PATH which isn’t setup properly.
gcc 13.1, ubuntu 20.4,
test directory /home/user/concrete/frontends/concrete-python/tests
INSECURE_KEY_CACHE_LOCATION=/home/user/.cache/concrete-python/pytest
============================= test session starts ==============================
platform linux – Python 3.10.10, pytest-7.2.2, pluggy-1.5.0 – /home/user/concrete/frontends/concrete-python/.venv/bin/python
cachedir: .pytest_cache
Using --randomly-seed=186165987
rootdir: /home/user/concrete/frontends/concrete-python, configfile: pytest.ini
plugins: cov-4.0.0, anyio-4.8.0, xdist-3.2.1, randomly-3.15.0
gw0 I / gw1 I / gw2 I / gw3 I
[gw0] linux Python 3.10.10 cwd: /home/user/concrete/frontends/concrete-python
[gw1] linux Python 3.10.10 cwd: /home/user/concrete/frontends/concrete-python
[gw2] linux Python 3.10.10 cwd: /home/user/concrete/frontends/concrete-python
[gw3] linux Python 3.10.10 cwd: /home/user/concrete/frontends/concrete-python
[gw0] Python 3.10.10 (main, Mar 21 2023, 18:45:11) [GCC 11.2.0]
[gw1] Python 3.10.10 (main, Mar 21 2023, 18:45:11) [GCC 11.2.0]
[gw2] Python 3.10.10 (main, Mar 21 2023, 18:45:11) [GCC 11.2.0]
[gw3] Python 3.10.10 (main, Mar 21 2023, 18:45:11) [GCC 11.2.0]
gw0 [2837] / gw1 [2837] / gw2 [2837] / gw3 [2837]
scheduling tests via LoadScheduling
tests/internal/test_utils.py::test_unreachable
tests/execution/test_tfhers.py::test_tfhers_one_tfhers_one_native_complete_circuit_tfhers_keygen[x + y]
tests/execution/test_round_bit_pattern.py::test_round_bit_pattern[True-x ** 2-5-2]
[gw0] PASSED tests/internal/test_utils.py::test_unreachable
tests/execution/test_if_then_else.py::test_if_then_else[-condition_description87-when_true_description87-when_false_description87-3]
tests/internal/test_utils.py::test_assert_that
[gw0] PASSED tests/internal/test_utils.py::test_assert_that
tests/execution/test_composition_compression.py::test_composable_with_input_compression
[gw2] node down: Not properly terminated
[gw2] FAILED tests/execution/test_round_bit_pattern.py::test_round_bit_pattern[True-x ** 2-5-2]
replacing crashed worker gw2
[gw4] linux Python 3.10.10 cwd: /home/user/concrete/frontends/concrete-python
[gw0] node down: Not properly terminated
[gw0] FAILED tests/execution/test_composition_compression.py::test_composable_with_input_compression
replacing crashed worker gw0
[gw5] linux Python 3.10.10 cwd: /home/user/concrete/frontends/concrete-python
[gw3] node down: Not properly terminated
[gw3] FAILED tests/execution/test_if_then_else.py::test_if_then_else[-condition_description87-when_true_description87-when_false_description87-3]
replacing crashed worker gw3
[gw6] linux Python 3.10.10 cwd: /home/user/concrete/frontends/concrete-python
[gw1] node down: Not properly terminated
[gw1] FAILED tests/execution/test_tfhers.py::test_tfhers_one_tfhers_one_native_complete_circuit_tfhers_keygen[x + y]
replacing crashed worker gw1
[gw7] linux Python 3.10.10 cwd: /home/user/concrete/frontends/concrete-python
[gw5] Python 3.10.10 (main, Mar 21 2023, 18:45:11) [GCC 11.2.0]
[gw4] Python 3.10.10 (main, Mar 21 2023, 18:45:11) [GCC 11.2.0]
[gw6] Python 3.10.10 (main, Mar 21 2023, 18:45:11) [GCC 11.2.0]
[gw7] Python 3.10.10 (main, Mar 21 2023, 18:45:11) [GCC 11.2.0]
tests/execution/test_comparison.py::test_comparison[operation13-1-2-True-False-lhs_shape13-rhs_shape13-None]
tests/execution/test_minimum_maximum.py::test_minimum_maximum[operation196-4-4-False-True-lhs_shape196-rhs_shape196-chunked]
tests/execution/test_min_max.py::test_min_max[min-2-True-shape13-axis13-False-one-tlu-promoted]
tests/mlir/test_converter.py::test_converter_convert_multi_precision[-parameters7-configuration_overrides7-\n\nmodule {\n func.func @“”(%arg0: !FHE.eint<7>) → (!FHE.eint<8>, !FHE.eint<7>) {\n %c2_i3 = arith.constant 2 : i3\n %c12_i8 = arith.constant 12 : i8\n %0 = “FHE.sub_eint_int”(%arg0, %c12_i8) : (!FHE.eint<7>, i8) → !FHE.eint<7>\n %c64_i8 = arith.constant 64 : i8\n %1 = “FHE.mul_eint_int”(%0, %c64_i8) : (!FHE.eint<7>, i8) → !FHE.eint<7>\n %2 = “FHE.reinterpret_precision”(%1) : (!FHE.eint<7>) → !FHE.eint<1>\n %cst = arith.constant dense<[144, 169]> : tensor<2xi64>\n %3 = “FHE.apply_lookup_table”(%2, %cst) : (!FHE.eint<1>, tensor<2xi64>) → !FHE.eint<8>\n %c100_i8 = arith.constant 100 : i8\n %4 = “FHE.add_eint_int”(%arg0, %c100_i8) : (!FHE.eint<7>, i8) → !FHE.eint<7>\n return %3, %4 : !FHE.eint<8>, !FHE.eint<7>\n }\n}\n\n ]
[gw5] node down: Not properly terminated
[gw5] FAILED tests/execution/test_minimum_maximum.py::test_minimum_maximum[operation196-4-4-False-True-lhs_shape196-rhs_shape196-chunked]
replacing crashed worker gw5
[gw8] linux Python 3.10.10 cwd: /home/user/concrete/frontends/concrete-python
[gw4] node down: Not properly terminated
[gw4] FAILED tests/execution/test_comparison.py::test_comparison[operation13-1-2-True-False-lhs_shape13-rhs_shape13-None]
replacing crashed worker gw4
[gw9] linux Python 3.10.10 cwd: /home/user/concrete/frontends/concrete-python
[gw6] node down: Not properly terminated
INTERNALERROR> Traceback (most recent call last):
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/execnet/gateway_base.py”, line 1190, in _send
INTERNALERROR> message.to_io(self._io)
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/execnet/gateway_base.py”, line 577, in to_io
INTERNALERROR> io.write(header + self.data)
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/execnet/gateway_base.py”, line 543, in write
INTERNALERROR> self._write(data)
INTERNALERROR> BrokenPipeError: [Errno 32] Broken pipe
INTERNALERROR>
INTERNALERROR> The above exception was the direct cause of the following exception:
INTERNALERROR>
INTERNALERROR> Traceback (most recent call last):
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/_pytest/main.py”, line 270, in wrap_session
INTERNALERROR> session.exitstatus = doit(config, session) or 0
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/_pytest/main.py”, line 324, in _main
INTERNALERROR> config.hook.pytest_runtestloop(session=session)
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/pluggy/_hooks.py”, line 513, in call
INTERNALERROR> return self._hookexec(self.name, self._hookimpls.copy(), kwargs, firstresult)
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/pluggy/_manager.py”, line 120, in _hookexec
INTERNALERROR> return self._inner_hookexec(hook_name, methods, kwargs, firstresult)
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/pluggy/_callers.py”, line 182, in _multicall
INTERNALERROR> return outcome.get_result()
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/pluggy/_result.py”, line 100, in get_result
INTERNALERROR> raise exc.with_traceback(exc.traceback)
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/pluggy/_callers.py”, line 103, in _multicall
INTERNALERROR> res = hook_impl.function(*args)
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/xdist/dsession.py”, line 117, in pytest_runtestloop
INTERNALERROR> self.loop_once()
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/xdist/dsession.py”, line 140, in loop_once
INTERNALERROR> call(**kwargs)
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/xdist/dsession.py”, line 204, in worker_errordown
INTERNALERROR> crashitem = self.sched.remove_node(node)
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/xdist/scheduler/load.py”, line 218, in remove_node
INTERNALERROR> self.check_schedule(node)
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/xdist/scheduler/load.py”, line 191, in check_schedule
INTERNALERROR> self._send_tests(node, min(num_send, maxschedchunk))
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/xdist/scheduler/load.py”, line 290, in _send_tests
INTERNALERROR> node.send_runtest_some(tests_per_node)
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/xdist/workermanage.py”, line 298, in send_runtest_some
INTERNALERROR> self.sendcommand(“runtests”, indices=indices)
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/xdist/workermanage.py”, line 317, in sendcommand
INTERNALERROR> self.channel.send((name, kwargs))
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/execnet/gateway_base.py”, line 912, in send
INTERNALERROR> self.gateway._send(Message.CHANNEL_DATA, self.id, dumps_internal(item))
INTERNALERROR> File “/home/user/concrete/frontends/concrete-python/.venv/lib/python3.10/site-packages/execnet/gateway_base.py”, line 1195, in _send
INTERNALERROR> raise OSError(“cannot send (already closed?)”) from e
INTERNALERROR> OSError: cannot send (already closed?)
========================= 6 failed, 2 passed in 15.47s =========================
We are planning to modify addition and multiplication operations at the software level (e.g., a = 3, b = 2; performing basic arithmetic operations like addition,mutliplication), not LWE-based addition and multiplication operations.
do you mean like simulating encrypted computation? If that’s the case, then why don’t you use the simulation feature of Concrete?
we are panning to replace normal adder(a+b with other adders) with Carry-Save Adder, Brent-Kung Adder, and others.
Currently, most operations are implemented in our backend using TFHE-rs. So the MLIR code will be calling an external lib (the backend). If you look at the generated MLIR, you will find those calls. If the API looks fine to you, and you don’t want to implement those adders in MLIR, then you should modify the backend code with your own implem.
Can you help me. where can i modify code to include approximation in addition operation. I will try to reduce number of gates required for addition.
we are unable to find the addtion opreation equivalent circuit representation using fhe gates
I’m not sure to understand what you mean here
In Fully Homomorphic Encryption (FHE), performing an addition operation like 2 + 3 requires converting it into a circuit representation using basic logic gates such as AND, OR, and XOR. Since FHE operates on encrypted data, standard arithmetic operations cannot be applied directly. Instead, integer addition must be expressed as a Boolean circuit that can be evaluated homomorphically. This involves representing each bit of the input numbers in binary and then implementing a bitwise addition process using half-adders and full-adders. These adders are built using XOR gates for sum computation and AND/OR gates for carry propagation. The FHE system then evaluates this circuit using encrypted inputs, ensuring that the addition is performed securely without decrypting the values. Our goal is to identify and modify this circuit representation in the Concrete library to explore alternative, more efficient adder designs, such as Brent-Kung or Kogge-Stone adders, which optimize carry propagation for faster computation in encrypted form.
Aha now I get it. In Concrete, we use TFHE which already works on integers, so we don’t have to break arithmetic operations into boolean circuits. Addition of two ciphertexts is actually a single gate.
I thought initially that you were looking at CRT encoding which involves multiple ciphertexts to represent an integer with large bitwidth, my bad.
Can you share intermediate representation of addition
and multiplication operation conversion file, mlir to llvm or mlir to tfhers conversion file
You could generate all that using our tools:
show_mlir=True in concrete-python during compilation.concretecompiler binary to output the IR using the representation of your choice (e.g. concretecompiler --action=dump-llvm-ir ...)MLIR in FHE dialect:
module {
func.func @mul(%arg0: !FHE.eint<6>, %arg1: i4) -> !FHE.eint<6> {
%0 = "FHE.mul_eint_int"(%arg0, %arg1) : (!FHE.eint<6>, i4) -> !FHE.eint<6>
return %0 : !FHE.eint<6>
}
}
MLIR in TFHE dialect:
module {
func.func @mul(%arg0: !TFHE.glwe<sk?> {TFHE.OId = 0 : i32}, %arg1: i4) -> !TFHE.glwe<sk?> {
%0 = arith.extsi %arg1 : i4 to i64
%1 = "TFHE.mul_glwe_int"(%arg0, %0) {TFHE.OId = 1 : i32} : (!TFHE.glwe<sk?>, i64) -> !TFHE.glwe<sk?>
return %1 : !TFHE.glwe<sk?>
}
}
MLIR in LLVM-IR:
; ModuleID = '-'
source_filename = "-"
declare ptr @malloc(i64)
declare void @free(ptr)
declare ptr @concrete_checked_malloc(i64)
declare void @memref_mul_cleartext_lwe_ciphertext_u64(ptr, ptr, i64, i64, i64, ptr, ptr, i64, i64, i64, i64)
declare void @_dfr_stop(i64)
declare void @_dfr_start(i64, ptr)
define { ptr, ptr, i64, [1 x i64], [1 x i64] } @mul(ptr %0, ptr %1, i64 %2, i64 %3, i64 %4, i4 %5, ptr %6) {
%8 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } undef, ptr %0, 0
%9 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %8, ptr %1, 1
%10 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %9, i64 %2, 2
%11 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %10, i64 %3, 3, 0
%12 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %11, i64 %4, 4, 0
call void @_dfr_start(i64 1, ptr %6)
%13 = sext i4 %5 to i64
%14 = call ptr @concrete_checked_malloc(i64 add (i64 ptrtoint (ptr getelementptr (i64, ptr null, i32 610) to i64), i64 64))
%15 = ptrtoint ptr %14 to i64
%16 = add i64 %15, 63
%17 = urem i64 %16, 64
%18 = sub i64 %16, %17
%19 = inttoptr i64 %18 to ptr
%20 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } undef, ptr %14, 0
%21 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %20, ptr %19, 1
%22 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %21, i64 0, 2
%23 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %22, i64 610, 3, 0
%24 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %23, i64 1, 4, 0
call void @memref_mul_cleartext_lwe_ciphertext_u64(ptr %14, ptr %19, i64 0, i64 610, i64 1, ptr %0, ptr %1, i64 %2, i64 %3, i64 %4, i64 %13)
call void @_dfr_stop(i64 1)
ret { ptr, ptr, i64, [1 x i64], [1 x i64] } %24
}
MLIR in FHE dialect:
module {
func.func @add(%arg0: !FHE.eint<4>, %arg1: !FHE.eint<4>) -> !FHE.eint<4> {
%0 = "FHE.add_eint"(%arg0, %arg1) : (!FHE.eint<4>, !FHE.eint<4>) -> !FHE.eint<4>
return %0 : !FHE.eint<4>
}
}
MLIR in TFHE dialect:
module {
func.func @add(%arg0: !TFHE.glwe<sk?> {TFHE.OId = 0 : i32}, %arg1: !TFHE.glwe<sk?> {TFHE.OId = 1 : i32}) -> !TFHE.glwe<sk?> {
%0 = "TFHE.add_glwe"(%arg0, %arg1) {TFHE.OId = 2 : i32} : (!TFHE.glwe<sk?>, !TFHE.glwe<sk?>) -> !TFHE.glwe<sk?>
return %0 : !TFHE.glwe<sk?>
}
}
MLIR in LLVM-IR:
; ModuleID = '-'
source_filename = "-"
declare ptr @malloc(i64)
declare void @free(ptr)
declare ptr @concrete_checked_malloc(i64)
declare void @memref_add_lwe_ciphertexts_u64(ptr, ptr, i64, i64, i64, ptr, ptr, i64, i64, i64, ptr, ptr, i64, i64, i64)
declare void @_dfr_stop(i64)
declare void @_dfr_start(i64, ptr)
define { ptr, ptr, i64, [1 x i64], [1 x i64] } @add(ptr %0, ptr %1, i64 %2, i64 %3, i64 %4, ptr %5, ptr %6, i64 %7, i64 %8, i64 %9, ptr %10) {
%12 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } undef, ptr %0, 0
%13 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %12, ptr %1, 1
%14 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %13, i64 %2, 2
%15 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %14, i64 %3, 3, 0
%16 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %15, i64 %4, 4, 0
%17 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } undef, ptr %5, 0
%18 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %17, ptr %6, 1
%19 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %18, i64 %7, 2
%20 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %19, i64 %8, 3, 0
%21 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %20, i64 %9, 4, 0
call void @_dfr_start(i64 1, ptr %10)
%22 = call ptr @concrete_checked_malloc(i64 add (i64 ptrtoint (ptr getelementptr (i64, ptr null, i32 513) to i64), i64 64))
%23 = ptrtoint ptr %22 to i64
%24 = add i64 %23, 63
%25 = urem i64 %24, 64
%26 = sub i64 %24, %25
%27 = inttoptr i64 %26 to ptr
%28 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } undef, ptr %22, 0
%29 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %28, ptr %27, 1
%30 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %29, i64 0, 2
%31 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %30, i64 513, 3, 0
%32 = insertvalue { ptr, ptr, i64, [1 x i64], [1 x i64] } %31, i64 1, 4, 0
call void @memref_add_lwe_ciphertexts_u64(ptr %22, ptr %27, i64 0, i64 513, i64 1, ptr %0, ptr %1, i64 %2, i64 %3, i64 %4, ptr %5, ptr %6, i64 %7, i64 %8, i64 %9)
call void @_dfr_stop(i64 1)
ret { ptr, ptr, i64, [1 x i64], [1 x i64] } %32
}