Extract tree eval to separate file.

2 files changed, 543 insertions, 338 deletions

diff --git a/re/eval.py b/re/eval.py
new file mode 100644
index 0000000..db5a3b0
--- /dev/null
+++ b/re/eval.py
@@ -0,0 +1,473 @@
+from matplotlib import pyplot as plt
+import numpy as np
+from scipy.stats import bernoulli
+from tqdm.notebook import tqdm, trange
+from pyecsca.misc.utils import TaskExecutor
+
+
+errs = (0, 0.1, 0.2, 0.3, 0.4, 0.5)
+majs = (1, 3, 5, 7, 9, 11)
+
+nums = (4, 10, 20, 40, 60) 
+smpls = (1, 2, 3, 5, 10)
+
+def walk_symmetric(tree, err, majority, cfg):
+    current = tree.root
+    B = bernoulli(err)
+    queries = 0
+    while not current.is_leaf:
+        dmap_index = current.dmap_index
+        dmap_input = current.dmap_input
+        dmap = tree.maps[dmap_index]
+        true_response = dmap[cfg, dmap_input]
+        responses = []
+        response = None
+        for _ in range(majority):
+            responses.append(true_response ^ B.rvs())
+            if responses.count(True) > (majority // 2):
+                response = True
+                break
+            if responses.count(False) > (majority // 2):
+                response = False
+                break
+        response_map = {child.response: child for child in current.children}
+        current = response_map[response]
+        queries += len(responses)
+    return cfg in current.cfgs, len(current.cfgs), queries
+
+
+def _eval_symmetric(tree, cfg, errs, majs, num_tries):
+    correct_tries = np.zeros((len(errs), len(majs)))
+    precise_tries = np.zeros((len(errs), len(majs)))
+    amount_tries = np.zeros((len(errs), len(majs)))
+    query_tries = np.zeros((len(errs), len(majs)))
+    for i, err in enumerate(errs):
+        for j, majority in enumerate(majs):
+            for _ in range(num_tries):
+                correct, amount, queries = walk_symmetric(tree, err, majority, cfg)
+                correct_tries[i, j] += correct
+                precise_tries[i, j] += (amount == 1)
+                amount_tries[i, j] += amount
+                query_tries[i, j] += queries
+    return correct_tries, precise_tries, amount_tries, query_tries
+
+    
+def eval_tree_symmetric(cfgs, build_tree, num_trees, num_tries, num_cores):
+    correct_tries = np.zeros((len(errs), len(majs)))
+    precise_tries = np.zeros((len(errs), len(majs)))
+    amount_tries = np.zeros((len(errs), len(majs)))
+    query_tries = np.zeros((len(errs), len(majs)))
+
+    trees = []
+    with TaskExecutor(max_workers=num_cores) as pool:
+        for i in range(num_trees):
+            # Build the trees
+            pool.submit_task((i,), build_tree, cfgs)
+        for (i,), future in tqdm(pool.as_completed(), total=len(pool.tasks), desc="Building trees", smoothing=0):
+            trees.append(future.result())
+
+    with TaskExecutor(max_workers=num_cores) as pool:
+        for i, tree in enumerate(trees):
+            for cfg in cfgs:
+                # Now cfg is the "true" config
+                pool.submit_task((i, cfg), _eval_symmetric, tree, cfg, errs, majs, num_tries)
+        for (i, cfg), future in tqdm(pool.as_completed(), total=len(pool.tasks), desc="Computing", smoothing=0):
+            c_tries, p_tries, a_tries, q_tries = future.result()
+            correct_tries += c_tries
+            precise_tries += p_tries
+            amount_tries += a_tries
+            query_tries += q_tries
+    total = num_trees * num_tries * len(cfgs)
+
+    correct_rate = (correct_tries * 100) / total
+    precise_rate = (precise_tries * 100) / total
+    amount_rate = amount_tries / total
+    query_rate = query_tries / total
+    return correct_rate[...,::-1], precise_rate[...,::-1], amount_rate[...,::-1], query_rate[...,::-1]
+
+
+def walk_asymmetric(tree, err_0, err_1, majority, cfg):
+    current = tree.root
+    B0 = bernoulli(err_0)
+    B1 = bernoulli(err_1)
+    queries = 0
+    while not current.is_leaf:
+        dmap_index = current.dmap_index
+        dmap_input = current.dmap_input
+        dmap = tree.maps[dmap_index]
+        true_response = dmap[cfg, dmap_input]
+        responses = []
+        response = None
+        for _ in range(majority):
+            responses.append(true_response ^ (B1.rvs() if true_response else B0.rvs()))
+            if responses.count(True) > (majority // 2):
+                response = True
+                break
+            if responses.count(False) > (majority // 2):
+                response = False
+                break
+        response_map = {child.response: child for child in current.children}
+        current = response_map[response]
+        queries += len(responses)
+    return cfg in current.cfgs, len(current.cfgs), queries
+
+
+def _eval_asymmetric(tree, cfg, errs, majs, num_tries):
+    correct_tries = np.zeros((len(errs), len(errs), len(majs)))
+    precise_tries = np.zeros((len(errs), len(errs), len(majs)))
+    amount_tries =  np.zeros((len(errs), len(errs), len(majs)))
+    query_tries =   np.zeros((len(errs), len(errs), len(majs)))
+
+    for i, err_0 in enumerate(errs):
+        for j, err_1 in enumerate(errs):
+            for k, majority in enumerate(majs):
+                for _ in range(num_tries):
+                    correct, amount, queries = walk_asymmetric(tree, err_0, err_1, majority, cfg)
+                    correct_tries[i, j, k] += correct
+                    precise_tries[i, j, k] += (amount == 1)
+                    amount_tries[i, j, k] += amount
+                    query_tries[i, j, k] += queries
+    return correct_tries, precise_tries, amount_tries, query_tries
+
+
+def eval_tree_asymmetric(cfgs, build_tree, num_trees, num_tries, num_cores):
+    correct_tries = np.zeros((len(errs), len(errs), len(majs)))
+    precise_tries = np.zeros((len(errs), len(errs), len(majs)))
+    amount_tries =  np.zeros((len(errs), len(errs), len(majs)))
+    query_tries =   np.zeros((len(errs), len(errs), len(majs)))
+
+    trees = []
+    with TaskExecutor(max_workers=num_cores) as pool:
+        for i in range(num_trees):
+            # Build the trees
+            pool.submit_task((i,), build_tree, cfgs)
+        for (i,), future in tqdm(pool.as_completed(), total=len(pool.tasks), desc="Building trees", smoothing=0):
+            trees.append(future.result())
+
+    with TaskExecutor(max_workers=num_cores) as pool:
+        for i, tree in enumerate(trees):
+            for cfg in cfgs:
+                # Now cfg is the "true" config
+                pool.submit_task((i, cfg), _eval_asymmetric, tree, cfg, errs, majs, num_tries)
+        for (i, cfg), future in tqdm(pool.as_completed(), total=len(pool.tasks), desc="Computing", smoothing=0):
+            c_tries, p_tries, a_tries, q_tries = future.result()
+            correct_tries += c_tries
+            precise_tries += p_tries
+            amount_tries += a_tries
+            query_tries += q_tries
+    total = num_trees * num_tries * len(cfgs)
+
+    correct_rate = (correct_tries * 100) / total
+    precise_rate = (precise_tries * 100) / total
+    amount_rate = amount_tries / total
+    query_rate = query_tries / total
+    return correct_rate, precise_rate, amount_rate, query_rate
+
+
+def walk_binomial(tree, num, smpl, majority, cfg):
+    current = tree.root
+    B = binom(num, 0.5)
+    queries = 0
+    while not current.is_leaf:
+        dmap_index = current.dmap_index
+        dmap_input = current.dmap_input
+        dmap = tree.maps[dmap_index]
+        true_response = dmap[cfg, dmap_input]
+        responses = [true_response + B.rvs() - (num // 2) for _ in range(smpl)]
+        mean = np.mean(responses)
+        response_map = {child.response: child for child in current.children}
+        closest = min(response_map, key=lambda value: abs(value-mean))
+        current = response_map[closest]
+        queries += smpl
+    return cfg in current.cfgs, len(current.cfgs), queries
+
+
+def _eval_binomial(tree, cfg, nums, smpls, num_tries):
+    correct_tries = np.zeros((len(nums), len(smpls)))
+    precise_tries = np.zeros((len(nums), len(smpls)))
+    amount_tries =  np.zeros((len(nums), len(smpls)))
+    query_tries =   np.zeros((len(nums), len(smpls)))
+
+    for i, num in enumerate(nums):
+        for j, smpl in enumerate(smpls):
+            for _ in range(num_tries):
+                correct, amount, queries = walk_binomial(tree, num, smpl, cfg)
+                correct_tries[i, j] += correct
+                precise_tries[i, j] += (amount == 1)
+                amount_tries[i, j] += amount
+                query_tries[i, j] += queries
+    return correct_tries, precise_tries, amount_tries, query_tries
+
+
+def eval_tree_binomial(cfgs, build_tree, num_trees, num_tries, num_cores)
+    correct_tries = np.zeros((len(nums), len(smpls)))
+    precise_tries = np.zeros((len(nums), len(smpls)))
+    amount_tries =  np.zeros((len(nums), len(smpls)))
+    query_tries =   np.zeros((len(nums), len(smpls)))
+
+    trees = []
+    with TaskExecutor(max_workers=num_cores) as pool:
+        for i in range(num_trees):
+            # Build the trees
+            pool.submit_task((i,), build_tree, cfgs)
+        for (i,), future in tqdm(pool.as_completed(), total=len(pool.tasks), desc="Building trees", smoothing=0):
+            trees.append(future.result())
+
+    with TaskExecutor(max_workers=num_cores) as pool:
+        for i, tree in enumerate(trees):
+            for cfg in cfgs:
+                # Now cfg is the "true" config
+                pool.submit_task((i, cfg), _eval_binomial, tree, cfg, nums, smpls, num_tries)
+        for (i, cfg), future in tqdm(pool.as_completed(), total=len(pool.tasks), desc="Computing", smoothing=0):
+            c_tries, p_tries, a_tries, q_tries = future.result()
+            correct_tries += c_tries
+            precise_tries += p_tries
+            amount_tries += a_tries
+            query_tries += q_tries
+    total = num_trees * num_tries * len(cfgs)
+
+    correct_rate = (correct_tries * 100) / total
+    precise_rate = (precise_tries * 100) / total
+    amount_rate = amount_tries / total
+    query_rate = query_tries / total
+    return correct_rate, precise_rate, amount_rate, query_rate
+            
+
+def query_rate_symmetric(query_rate):
+    fig, ax = plt.subplots()
+    im = ax.imshow(query_rate.T, cmap="plasma")
+    cbar_ax = fig.add_axes((0.85, 0.15, 0.04, 0.69))
+    cbar = fig.colorbar(im, cax=cbar_ax)
+    cbar.ax.set_ylabel("Oracle query rate", rotation=-90, va="bottom")
+    
+    ax.set_xticks(np.arange(len(errs)), labels=errs)
+    ax.set_yticks(np.arange(len(majs)), labels=reversed(majs))
+    ax.set_xlabel("error probability")
+    ax.set_ylabel("majority vote")
+    for i in range(len(errs)):
+        for j in range(len(majs)):
+            text = ax.text(i, j, f"{query_rate[i, j]:.1f}",
+                           ha="center", va="center", color="white" if i - j <= 2 else "black")
+    return fig
+
+
+def success_rate_symmetric(correct_rate, baseline):
+    fig, ax = plt.subplots()
+    im = ax.imshow(correct_rate.T, vmin=0, cmap="viridis")
+    cbar_ax = fig.add_axes((0.85, 0.15, 0.04, 0.69))
+    cbar = fig.colorbar(im, cax=cbar_ax)
+    cbar.ax.set_ylabel("Success rate", rotation=-90, va="bottom")
+    cbar.ax.axhline(baseline, color="red", linestyle="--")
+    
+    ax.set_xticks(np.arange(len(errs)), labels=errs)
+    ax.set_yticks(np.arange(len(majs)), labels=reversed(majs))
+    ax.set_xlabel("error probability")
+    ax.set_ylabel("majority vote")
+    for i in range(len(errs)):
+        for j in range(len(majs)):
+            c_rate = correct_rate[i, j]
+            text = ax.text(i, j, f"{c_rate:.1f}%",
+                           ha="center", va="center", color="white" if c_rate < 80 else "black")
+    return fig
+
+
+def precise_rate_symmetric(precise_rate):
+    fig, ax = plt.subplots()
+    im = ax.imshow(precise_rate.T, vmin=0, cmap="viridis")
+    cbar_ax = fig.add_axes((0.85, 0.15, 0.04, 0.69))
+    cbar = fig.colorbar(im, cax=cbar_ax)
+    cbar.ax.set_ylabel("Precision", rotation=-90, va="bottom")
+    
+    ax.set_xticks(np.arange(len(errs)), labels=errs)
+    ax.set_yticks(np.arange(len(majs)), labels=reversed(majs))
+    ax.set_xlabel("error probability")
+    ax.set_ylabel("majority vote")
+    for i in range(len(errs)):
+        for j in range(len(majs)):
+            p_rate = precise_rate[i, j]
+            text = ax.text(i, j, f"{p_rate:.1f}%",
+                           ha="center", va="center", color="white" if p_rate < 80 else "black")
+    return fig
+
+
+def success_rate_vs_query_rate_symmetric(query_rate, correct_rate):
+    fig, ax = plt.subplots()
+    ax.grid()
+    for i, err in enumerate(errs):
+        qrs = query_rate[i, :]
+        crs = correct_rate[i, :]
+        ax.scatter(qrs, crs, label=f"error = {err}")
+    ax.set_xlabel("oracle queries")
+    ax.set_ylabel("success rate")
+    ax.legend()
+    return fig
+
+
+def success_rate_vs_majority_symmetric(correct_rate):
+    fig, ax = plt.subplots()
+    ax.grid()
+    for i, err in enumerate(errs):
+        crs = correct_rate[i, :]
+        ax.plot(list(reversed(majs)), crs, label=f"error = {err}")
+    ax.set_xlabel("majority vote")
+    ax.set_ylabel("success rate")
+    ax.set_xticks(majs)
+    ax.legend()
+    return fig
+
+
+def query_rate_asymmetric(query_rate_b):
+    fig, axs = plt.subplots(nrows=2, ncols=3, sharex="col", sharey="row")
+    vmin = np.min(query_rate_b)
+    vmax = np.max(query_rate_b)
+    
+    for row in range(2):
+        for col in range(3):
+            ax = axs[row, col]
+            level = row * 3 + col
+            im = ax.imshow(query_rate_b[::-1,:,level], cmap="plasma", vmin=vmin, vmax=vmax)
+            ax.set_xticks(np.arange(len(errs)), labels=errs)
+            ax.set_yticks(np.arange(len(errs)), labels=list(reversed(errs)))
+            for i in range(len(errs)):
+                for j in range(len(errs)):
+                    q = query_rate_b[i, len(errs) - j - 1, level]
+                    q_rate = f"{q:.0f}"
+                    text = ax.text(i, j, q_rate, ha="center", va="center", color="white" if q < (vmax - vmin)//2 else "black")
+            ax.set_xlabel("$e_1$")
+            ax.set_ylabel("$e_O$")
+            ax.set_title(majs[level])
+    fig.set_size_inches((10,6))
+    fig.tight_layout(h_pad=1.5, rect=(0, 0, 0.9, 1))
+    cbar_ax = fig.add_axes((0.9, 0.10, 0.02, 0.84))
+    cbar = fig.colorbar(im, cax=cbar_ax)
+    cbar.ax.set_ylabel("Oracle query rate", rotation=-90, va="bottom")
+    return fig
+
+
+def success_rate_asymmetric(correct_rate_b, baseline):
+    fig, axs = plt.subplots(nrows=2, ncols=3, sharex="col", sharey="row")
+    for row in range(2):
+        for col in range(3):
+            ax = axs[row, col]
+            level = row * 3 + col
+            im = ax.imshow(correct_rate_b[::-1,:,level], cmap="viridis", vmin=0, vmax=100)
+            ax.set_xticks(np.arange(len(errs)), labels=errs)
+            ax.set_yticks(np.arange(len(errs)), labels=list(reversed(errs)))
+            for i in range(len(errs)):
+                for j in range(len(errs)):
+                    c = correct_rate_b[i, len(errs) - j - 1, level]
+                    c_rate = f"{c:.0f}%"
+                    text = ax.text(i, j, c_rate, ha="center", va="center", color="white" if c < 50 else "black")
+            ax.set_xlabel("$e_1$")
+            ax.set_ylabel("$e_O$")
+            ax.set_title(majs[level])
+    fig.set_size_inches((10,6))
+    fig.tight_layout(h_pad=1.5, rect=(0, 0, 0.9, 1))
+    cbar_ax = fig.add_axes((0.9, 0.10, 0.02, 0.84))
+    cbar = fig.colorbar(im, cax=cbar_ax)
+    cbar.ax.set_ylabel("Success rate", rotation=-90, va="bottom")
+    cbar.ax.axhline(baseline, color="red", linestyle="--")
+    return fig
+
+
+def precise_rate_asymmetric(precise_rate_b):
+    fig, axs = plt.subplots(nrows=2, ncols=3, sharex="col", sharey="row")
+    for row in range(2):
+        for col in range(3):
+            ax = axs[row, col]
+            level = row * 3 + col
+            im = ax.imshow(precise_rate_b[::-1,:,level], cmap="viridis", vmin=0, vmax=100)
+            ax.set_xticks(np.arange(len(errs)), labels=errs)
+            ax.set_yticks(np.arange(len(errs)), labels=list(reversed(errs)))
+            for i in range(len(errs)):
+                for j in range(len(errs)):
+                    p = precise_rate_b[i, len(errs) - j - 1, level]
+                    p_rate = f"{p:.0f}%"
+                    text = ax.text(i, j, p_rate, ha="center", va="center", color="white" if p < 80 else "black")
+            ax.set_xlabel("$e_1$")
+            ax.set_ylabel("$e_O$")
+            ax.set_title(majs[level])
+    fig.set_size_inches((10,6))
+    fig.tight_layout(h_pad=1.5, rect=(0, 0, 0.9, 1))
+    cbar_ax = fig.add_axes((0.9, 0.10, 0.02, 0.84))
+    cbar = fig.colorbar(im, cax=cbar_ax)
+    cbar.ax.set_ylabel("Precision rate", rotation=-90, va="bottom")
+    return fig
+
+
+def success_rate_vs_majority_asymmetric(correct_rate_b):
+    fig, ax = plt.subplots()
+    ax.grid()
+    crs_accumulated = {}
+    for i, err_0 in enumerate(errs):
+        for j, err_1 in enumerate(errs):
+            crs = correct_rate_b[i, j, :]
+            total_err = round(err_0 + err_1, 1)
+            l = crs_accumulated.setdefault(total_err, [])
+            l.append(crs)
+    for total_err in crs_accumulated.keys():
+        crs = np.mean(crs_accumulated[total_err], axis=0)
+        ax.plot(majs, crs, label=f"total_error = {total_err}")
+    ax.set_xticks(majs)
+    ax.set_xlabel("majority")
+    ax.set_ylabel("success rate")
+    ax.legend(bbox_to_anchor=(1, 1.02))
+    fig.tight_layout()
+    return fig
+
+
+def query_rate_binomial(query_rate):
+    fig, ax = plt.subplots()
+    im = ax.imshow(query_rate.T, cmap="plasma")
+    cbar_ax = fig.add_axes((0.85, 0.15, 0.04, 0.69))
+    cbar = fig.colorbar(im, cax=cbar_ax)
+    cbar.ax.set_ylabel("Oracle query rate", rotation=-90, va="bottom")
+    
+    ax.set_xticks(np.arange(len(nums)), labels=nums)
+    ax.set_yticks(np.arange(len(smpls)), labels=reversed(smpls))
+    ax.set_xlabel("binom n")
+    ax.set_ylabel("samples")
+    for i in range(len(nums)):
+        for j in range(len(smpls)):
+            text = ax.text(i, j, f"{query_rate[i, j]:.1f}",
+                           ha="center", va="center", color="white" if i - j <= 2 else "black")
+    return fig
+
+
+def success_rate_binomial(correct_rate, baseline):
+    fig, ax = plt.subplots()
+    im = ax.imshow(correct_rate.T, vmin=0, cmap="viridis")
+    cbar_ax = fig.add_axes((0.85, 0.15, 0.04, 0.69))
+    cbar = fig.colorbar(im, cax=cbar_ax)
+    cbar.ax.set_ylabel("Success rate", rotation=-90, va="bottom")
+    cbar.ax.axhline(baseline, color="red", linestyle="--")
+    
+    ax.set_xticks(np.arange(len(nums)), labels=nums)
+    ax.set_yticks(np.arange(len(smpls)), labels=reversed(smpls))
+    ax.set_xlabel("binom n")
+    ax.set_ylabel("samples")
+    for i in range(len(nums)):
+        for j in range(len(smpls)):
+            c_rate = correct_rate[i, j]
+            text = ax.text(i, j, f"{c_rate:.1f}%",
+                           ha="center", va="center", color="white" if c_rate < 80 else "black")
+    return fig
+
+
+def precise_rate_binomial(precise_rate):
+    fig, ax = plt.subplots()
+    im = ax.imshow(precise_rate.T, vmin=0, cmap="viridis")
+    cbar_ax = fig.add_axes((0.85, 0.15, 0.04, 0.69))
+    cbar = fig.colorbar(im, cax=cbar_ax)
+    cbar.ax.set_ylabel("Precision", rotation=-90, va="bottom")
+    
+    ax.set_xticks(np.arange(len(nums)), labels=nums)
+    ax.set_yticks(np.arange(len(smpls)), labels=reversed(smpls))
+    ax.set_xlabel("binom n")
+    ax.set_ylabel("samples")
+    for i in range(len(nums)):
+        for j in range(len(smpls)):
+            p_rate = precise_rate[i, j]
+            text = ax.text(i, j, f"{p_rate:.1f}%",
+                           ha="center", va="center", color="white" if p_rate < 80 else "black")
+    return fig
diff --git a/re/rpa.ipynb b/re/rpa.ipynb
index 2a8783c..f0fa1d6 100644
--- a/re/rpa.ipynb
+++ b/re/rpa.ipynb
@@ -11,6 +11,8 @@
     " - [Exploration](#Exploration)\n",
     " - [Reverse-engineering](#Reverse-engineering)\n",
     "   - [Oracle simulation](#Oracle-simulation)\n",
+    "     - [Symmetric noise](#What-about-(symmetric)-noise?)\n",
+    "     - [Asymmetric noise](#What-about-(asymmetric)-noise?)\n",
     "   - [Method simulation](#Method-simulation)"
    ]
   },
@@ -53,7 +55,14 @@
     "from pyecsca.ec.context import DefaultContext, local\n",
     "from pyecsca.sca.re.rpa import MultipleContext, rpa_distinguish, RPA\n",
     "from pyecsca.sca.trace import Trace\n",
-    "from pyecsca.sca.trace.plot import plot_trace, plot_traces"
+    "from pyecsca.sca.trace.plot import plot_trace, plot_traces\n",
+    "\n",
+    "from eval import (eval_tree_symmetric, eval_tree_asymmetric,\n",
+    "                    success_rate_symmetric, success_rate_asymmetric,\n",
+    "                    query_rate_symmetric, query_rate_asymmetric,\n",
+    "                    precise_rate_symmetric, precise_rate_asymmetric,\n",
+    "                    success_rate_vs_majority_symmetric, success_rate_vs_majority_asymmetric,\n",
+    "                    success_rate_vs_query_rate_symmetric)"
    ]
   },
   {
@@ -97,7 +106,10 @@
     "g = Point(coords, X=gx, Y=gy, Z=Mod(1, p))\n",
     "\n",
     "curve = EllipticCurve(model, coords, p, infty, dict(a=a,b=b))\n",
-    "params = DomainParameters(curve, g, n, h)"
+    "params = DomainParameters(curve, g, n, h)\n",
+    "\n",
+    "# And P-256 for eval\n",
+    "p256 = get_params(\"secg\", \"secp256r1\", \"projective\")"
    ]
   },
   {
@@ -356,7 +368,6 @@
    },
    "outputs": [],
    "source": [
-    "p256 = get_params(\"secg\", \"secp256r1\", \"projective\")\n",
     "res = rpa_distinguish(params, multipliers, simulated_oracle)"
    ]
   },
@@ -365,7 +376,7 @@
    "id": "6361c477-5ddf-46ff-8918-864a453b676b",
    "metadata": {},
    "source": [
-    "Let's see if the result is correct."
+    "Let's see if the result is correct. You can replace the `simulated_oracle` above with `noisy_oracle(simulated_oracle, flip_proba=0.2)` or with `biased_oracle(simulated_oracle, flip_0=0.2, flip_1=0.1)` to see how the process and result changes with noise."
    ]
   },
   {
@@ -429,353 +440,171 @@
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "76b0f82c-64ac-4646-91b9-99f7962200d3",
+   "id": "04bd8191-1af8-4183-ac95-31b1e1c48e1b",
    "metadata": {},
    "outputs": [],
    "source": [
-    "errs = (0, 0.1, 0.2, 0.3, 0.4, 0.5)\n",
-    "majs = (1, 3, 5, 7, 9, 11)\n",
-    "num_tries = 100"
+    "def build_tree(cfgs):\n",
+    "    with silent():\n",
+    "        re = RPA(set(cfgs))\n",
+    "        re.build_tree(p256, tries=10)\n",
+    "        return re.tree\n",
+    "\n",
+    "correct_rate, precise_rate, amount_rate, query_rate = eval_tree_symmetric(set(multipliers), build_tree, num_trees=100, num_tries=100, num_cores=30)"
    ]
   },
   {
-   "cell_type": "code",
-   "execution_count": null,
-   "id": "4e9ca09b-9fe4-4c91-ac37-530892b1df48",
+   "cell_type": "markdown",
+   "id": "9bda1baa-359a-4f9b-889d-f64e055deff6",
    "metadata": {},
-   "outputs": [],
    "source": [
-    "correct_tries = np.zeros((len(errs), len(majs)))\n",
-    "precise_tries = np.zeros((len(errs), len(majs)))\n",
-    "query_tries = np.zeros((len(errs), len(majs)))\n",
-    "total_tries = 0"
+    "We can plot several heatmaps:\n",
+    " - One for the average number of queries to the oracle.\n",
+    " - One for the success rate of the reverse-engineering.\n",
+    " - One for the precision of the reverse-engineering."
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "265eb13a-6028-4fde-9c3f-cc23768ba63e",
+   "id": "7be15799-d042-43ae-b052-ef7b103e1cca",
    "metadata": {},
    "outputs": [],
    "source": [
-    "num_cores = 30\n",
-    "\n",
-    "def measure_mult(params, multipliers, simulated_oracle, i, mult, err, majority):\n",
-    "    correct = 0\n",
-    "    precise = 0\n",
-    "    calls = 0\n",
-    "    p = lru_cache(maxsize=2)(partial(simulated_oracle, simulate_mult_id=i))\n",
-    "    noisy = noisy_oracle(p, flip_proba=err)\n",
-    "    def oracle(scalar, affine_point):\n",
-    "        nonlocal calls\n",
-    "        calls += 1\n",
-    "        return noisy(scalar, affine_point)\n",
-    "    re = RPA(set(multipliers))\n",
-    "    re.build_tree(params, tries=10)\n",
-    "    for j in range(num_tries):\n",
-    "        res = re.run(oracle, majority=majority)\n",
-    "        if mult in res:\n",
-    "            correct += 1\n",
-    "        if len(res) == 1:\n",
-    "            precise += 1\n",
-    "    return correct, precise, calls\n",
-    "\n",
-    "with silent(), ProcessPoolExecutor(max_workers=num_cores) as pool:\n",
-    "    futures = []\n",
-    "    args = []\n",
-    "    for i, mult in enumerate(multipliers):\n",
-    "        for err in errs:\n",
-    "            for majority in majs:\n",
-    "                a = (params, multipliers, simulated_oracle, i, mult, err, majority)\n",
-    "                futures.append(pool.submit(measure_mult, *a))\n",
-    "                args.append(a)\n",
-    "    results = [None for _ in futures]\n",
-    "    for future in tqdm(as_completed(futures), total=len(futures), smoothing=0):\n",
-    "        j = futures.index(future)\n",
-    "        a = args[j]\n",
-    "        results[j] = future.result()"
+    "srs_fig = success_rate_symmetric(correct_rate, 100 / len(multipliers))"
    ]
   },
   {
-   "cell_type": "markdown",
-   "id": "4d283a04-decc-422f-b804-addd57a8a635",
+   "cell_type": "code",
+   "execution_count": null,
+   "id": "131f2bee-4c07-4449-a380-06082861d753",
    "metadata": {},
+   "outputs": [],
    "source": [
-    "Now we accumulate the results across the error rate and majority vote parameters."
+    "qrs_fig = query_rate_symmetric(query_rate)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "6cc0af93-8442-4ccf-958f-3502d2d76a34",
+   "id": "901bfdaa-5767-4c7b-92d5-9f82dd075ea6",
    "metadata": {},
    "outputs": [],
    "source": [
-    "for a, result in zip(args, results):\n",
-    "    i = errs.index(a[5])\n",
-    "    j = len(majs) - majs.index(a[6]) - 1\n",
-    "    correct_tries[i, j] += result[0]\n",
-    "    precise_tries[i, j] += result[1]\n",
-    "    query_tries[i, j] += result[2]\n",
-    "total_tries += num_tries\n",
-    "\n",
-    "correct_rate = (correct_tries * 100) / (total_tries * len(multipliers))\n",
-    "precise_rate = (precise_tries * 100) / (total_tries * len(multipliers))\n",
-    "query_rate = query_tries / (total_tries * len(multipliers))"
+    "prs_fig = precise_rate_symmetric(precise_rate)"
    ]
   },
   {
    "cell_type": "markdown",
-   "id": "8c747434-84bb-4acd-a994-45a4b4859a6e",
+   "id": "b8eeb49e-7734-4fda-bf28-ac39f6c8a626",
    "metadata": {},
    "source": [
-    "And save the results for later."
+    "Another way to look at these metrics is a scatter plot."
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "857f39ad-f6ba-4006-8da9-92f4318819e2",
+   "id": "d5176863-d6b6-4205-8a3a-4453b8177305",
    "metadata": {},
    "outputs": [],
    "source": [
-    "np.save(\"rpa_re_correct_rate\", correct_rate)\n",
-    "np.save(\"rpa_re_precise_rate\", precise_rate)\n",
-    "np.save(\"rpa_re_query_rate\", query_rate)"
-   ]
-  },
-  {
-   "cell_type": "markdown",
-   "id": "9bda1baa-359a-4f9b-889d-f64e055deff6",
-   "metadata": {},
-   "source": [
-    "We can plot several heatmaps:\n",
-    " - One for the average number of queries to the oracle.\n",
-    " - One for the success rate of the reverse-engineering.\n",
-    " - One for the precision of the reverse-engineering."
+    "srqrs_fig = success_rate_vs_query_rate_symmetric(query_rate, correct_rate)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "3caf3afd-e27e-4b6f-947b-cd8edb2d568d",
+   "id": "c2cfdca4-7e88-4138-b01f-696ecdcfd2bd",
    "metadata": {},
    "outputs": [],
    "source": [
-    "fig, ax = plt.subplots()\n",
-    "im = ax.imshow(query_rate.T, cmap=\"plasma\")\n",
-    "cbar_ax = fig.add_axes((0.85, 0.15, 0.04, 0.69))\n",
-    "cbar = fig.colorbar(im, cax=cbar_ax)\n",
-    "cbar.ax.set_ylabel(\"Oracle query rate\", rotation=-90, va=\"bottom\")\n",
-    "\n",
-    "ax.set_xticks(np.arange(len(errs)), labels=errs)\n",
-    "ax.set_yticks(np.arange(len(majs)), labels=reversed(majs))\n",
-    "ax.set_xlabel(\"error probability\")\n",
-    "ax.set_ylabel(\"majority vote\")\n",
-    "for i in range(len(errs)):\n",
-    "    for j in range(len(majs)):\n",
-    "        text = ax.text(i, j, f\"{query_rate[i, j]:.1f}\",\n",
-    "                       ha=\"center\", va=\"center\", color=\"w\" if i - j <= 2 else \"black\")\n",
-    "fig.savefig(\"rpa_re_query_rate.pdf\", bbox_inches=\"tight\")\n",
-    "plt.show()"
+    "srms_fig = success_rate_vs_majority_symmetric(correct_rate)"
    ]
   },
   {
-   "cell_type": "code",
-   "execution_count": null,
-   "id": "09c976dd-4940-40be-b7b2-6da73d672f24",
+   "cell_type": "markdown",
+   "id": "8c747434-84bb-4acd-a994-45a4b4859a6e",
    "metadata": {},
-   "outputs": [],
    "source": [
-    "fig, ax = plt.subplots()\n",
-    "im = ax.imshow(correct_rate.T, vmin=0, cmap=\"viridis\")\n",
-    "cbar_ax = fig.add_axes((0.85, 0.15, 0.04, 0.69))\n",
-    "cbar = fig.colorbar(im, cax=cbar_ax)\n",
-    "cbar.ax.set_ylabel(\"Success rate\", rotation=-90, va=\"bottom\")\n",
-    "cbar.ax.axhline(100 / len(multipliers), color=\"red\", linestyle=\"--\")\n",
-    "\n",
-    "ax.set_xticks(np.arange(len(errs)), labels=errs)\n",
-    "ax.set_yticks(np.arange(len(majs)), labels=reversed(majs))\n",
-    "ax.set_xlabel(\"error probability\")\n",
-    "ax.set_ylabel(\"majority vote\")\n",
-    "for i in range(len(errs)):\n",
-    "    for j in range(len(majs)):\n",
-    "        c_rate = correct_rate[i, j]\n",
-    "        text = ax.text(i, j, f\"{c_rate:.1f}%\",\n",
-    "                       ha=\"center\", va=\"center\", color=\"w\" if c_rate < 80 else \"black\")\n",
-    "fig.savefig(\"rpa_re_success_rate.pdf\", bbox_inches=\"tight\")\n",
-    "plt.show()"
+    "And save the results for later."
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "56114e99-e949-488f-85bb-f6bd2e221d39",
+   "id": "857f39ad-f6ba-4006-8da9-92f4318819e2",
    "metadata": {},
    "outputs": [],
    "source": [
-    "fig, ax = plt.subplots()\n",
-    "im = ax.imshow(precise_rate.T, vmin=0, cmap=\"viridis\")\n",
-    "cbar_ax = fig.add_axes((0.85, 0.15, 0.04, 0.69))\n",
-    "cbar = fig.colorbar(im, cax=cbar_ax)\n",
-    "cbar.ax.set_ylabel(\"Precision\", rotation=-90, va=\"bottom\")\n",
-    "\n",
-    "ax.set_xticks(np.arange(len(errs)), labels=errs)\n",
-    "ax.set_yticks(np.arange(len(majs)), labels=reversed(majs))\n",
-    "ax.set_xlabel(\"error probability\")\n",
-    "ax.set_ylabel(\"majority vote\")\n",
-    "for i in range(len(errs)):\n",
-    "    for j in range(len(majs)):\n",
-    "        p_rate = precise_rate[i, j]\n",
-    "        text = ax.text(i, j, f\"{p_rate:.1f}%\",\n",
-    "                       ha=\"center\", va=\"center\", color=\"w\" if p_rate < 80 else \"black\")\n",
-    "fig.savefig(\"rpa_re_precision.pdf\", bbox_inches=\"tight\")\n",
-    "plt.show()"
+    "np.save(\"rpa_re_correct_rate\", correct_rate)\n",
+    "np.save(\"rpa_re_precise_rate\", precise_rate)\n",
+    "np.save(\"rpa_re_query_rate\", query_rate)"
    ]
   },
   {
    "cell_type": "markdown",
-   "id": "b8eeb49e-7734-4fda-bf28-ac39f6c8a626",
+   "id": "e3981f44-ed3b-43f5-b4bd-e2d4b2ff95e8",
    "metadata": {},
    "source": [
-    "Another way to look at these metrics is a scatter plot."
+    "#### What about (asymmetric) noise?\n",
+    "The oracle may not only be noisy, but biased, this computation evaluates that case. Beware, for the same parameters this is about 6x slower because of the other dimension (two error probabilities instead of one)."
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "1e1b1769-6aa9-4b95-a7b7-dd5cfd501d27",
+   "id": "06268c58-63c9-4565-ba52-4414a9939581",
    "metadata": {},
    "outputs": [],
    "source": [
-    "fig, ax = plt.subplots()\n",
-    "ax.grid()\n",
-    "for i, err in enumerate(errs):\n",
-    "    qrs = query_rate[i, :]\n",
-    "    crs = correct_rate[i, :]\n",
-    "    ax.scatter(qrs, crs, label=f\"error = {err}\")\n",
-    "ax.set_xlabel(\"oracle queries\")\n",
-    "ax.set_ylabel(\"success rate\")\n",
-    "ax.legend()\n",
-    "fig.savefig(\"rpa_re_scatter.pdf\", bbox_inches=\"tight\")\n",
-    "plt.show()"
+    "def build_tree(cfgs):\n",
+    "    with silent():\n",
+    "        re = RPA(set(cfgs))\n",
+    "        re.build_tree(p256, tries=10)\n",
+    "        return re.tree\n",
+    "\n",
+    "correct_rate_b, precise_rate_b, amount_rate_b, query_rate_b = eval_tree_asymmetric(set(multipliers), build_tree, num_trees=100, num_tries=100, num_cores=30)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "921b1c7b-fd40-415e-b737-1a85e07a9ba5",
+   "id": "43a0055a-8d62-4f0a-be9f-e6ccb47b1d11",
    "metadata": {},
    "outputs": [],
    "source": [
-    "fig, ax = plt.subplots()\n",
-    "for i, err in enumerate(errs):\n",
-    "    crs = correct_rate[i, :]\n",
-    "    ax.plot(list(reversed(majs)), crs, label=f\"error = {err}\")\n",
-    "ax.set_xlabel(\"majority vote\")\n",
-    "ax.set_ylabel(\"success rate\")\n",
-    "ax.set_xticks(majs)\n",
-    "ax.legend()\n",
-    "fig.savefig(\"rpa_re_plot.pdf\", bbox_inches=\"tight\")\n",
-    "plt.show()"
-   ]
-  },
-  {
-   "cell_type": "markdown",
-   "id": "e3981f44-ed3b-43f5-b4bd-e2d4b2ff95e8",
-   "metadata": {},
-   "source": [
-    "#### What about (asymmetric) noise?"
+    "sra_fig = success_rate_asymmetric(correct_rate_b, 100 / len(multipliers))"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "40652fa3-39f9-47ad-9424-ee2fdaac78d3",
+   "id": "6b14a5eb-cfde-4e3e-a4f3-0d21dcca2dff",
    "metadata": {},
    "outputs": [],
    "source": [
-    "correct_tries_b = np.zeros((len(errs), len(errs), len(majs)))\n",
-    "precise_tries_b = np.zeros((len(errs), len(errs), len(majs)))\n",
-    "query_tries_b =   np.zeros((len(errs), len(errs), len(majs)))\n",
-    "total_tries_b = 0\n",
-    "\n",
-    "num_tries_b = 100"
+    "qra_fig = query_rate_asymmetric(query_rate_b)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "d6dce31a-1369-4556-8e01-4e19ad14d21e",
+   "id": "c5c7fe0e-88be-4d4e-a8fb-352ea85060f1",
    "metadata": {},
    "outputs": [],
    "source": [
-    "num_cores = 30\n",
-    "\n",
-    "def measure_mult(params, multipliers, simulated_oracle, i, mult, err_0, err_1, majority):\n",
-    "    correct = 0\n",
-    "    precise = 0\n",
-    "    calls = 0\n",
-    "    p = lru_cache(maxsize=2)(partial(simulated_oracle, simulate_mult_id=i))\n",
-    "    biased = biased_oracle(p, flip_0=err_0, flip_1=err_1)\n",
-    "    def oracle(scalar, affine_point):\n",
-    "        nonlocal calls\n",
-    "        calls += 1\n",
-    "        return biased(scalar, affine_point)\n",
-    "    re = RPA(set(multipliers))\n",
-    "    re.build_tree(params, tries=10)\n",
-    "    for j in range(num_tries_b):\n",
-    "        res = re.run(oracle, majority=majority)\n",
-    "        if mult in res:\n",
-    "            correct += 1\n",
-    "        if len(res) == 1:\n",
-    "            precise += 1\n",
-    "    return correct, precise, calls\n",
-    "\n",
-    "with silent(), ProcessPoolExecutor(max_workers=num_cores) as pool:\n",
-    "    futures = []\n",
-    "    args = []\n",
-    "    for i, mult in enumerate(multipliers):\n",
-    "        for err_0 in errs:\n",
-    "            for err_1 in errs:\n",
-    "                for majority in majs:\n",
-    "                    a = (params, multipliers, simulated_oracle, i, mult, err_0, err_1, majority)\n",
-    "                    futures.append(pool.submit(measure_mult, *a))\n",
-    "                    args.append(a)\n",
-    "    results = [None for _ in futures]\n",
-    "    for future in tqdm(as_completed(futures), total=len(futures), smoothing=0):\n",
-    "        j = futures.index(future)\n",
-    "        a = args[j]\n",
-    "        results[j] = future.result()"
-   ]
-  },
-  {
-   "cell_type": "markdown",
-   "id": "f4ddde62-18bb-46b2-a2e2-565cc21d654f",
-   "metadata": {},
-   "source": [
-    "Now we accumulate the results across the error rate and majority vote parameters."
+    "pra_fig = precise_rate_asymmetric(precise_rate_b)"
    ]
   },
   {
    "cell_type": "code",
    "execution_count": null,
-   "id": "20b9ac29-401f-4068-8b2a-4b2f14e14b28",
+   "id": "e4e999bf-bdd0-4b9f-86c6-1fdee773fd27",
    "metadata": {},
    "outputs": [],
    "source": [
-    "for a, result in zip(args, results):\n",
-    "    i = errs.index(a[5])\n",
-    "    j = errs.index(a[6])\n",
-    "    k = majs.index(a[7])\n",
-    "    correct_tries_b[i, j, k] += result[0]\n",
-    "    precise_tries_b[i, j, k] += result[1]\n",
-    "    query_tries_b[i, j, k] += result[2]\n",
-    "total_tries_b += num_tries_b\n",
-    "\n",
-    "correct_rate_b = (correct_tries_b * 100) / (total_tries_b * len(multipliers))\n",
-    "precise_rate_b = (precise_tries_b * 100) / (total_tries_b * len(multipliers))\n",
-    "query_rate_b = query_tries_b / (total_tries_b * len(multipliers))"
+    "srma_fig = success_rate_vs_majority_asymmetric(correct_rate_b)"
    ]
   },
   {
@@ -799,103 +628,6 @@
    ]
   },
   {
-   "cell_type": "code",
-   "execution_count": null,
-   "id": "5fd78523-0463-4932-ae64-42a444104d2c",
-   "metadata": {},
-   "outputs": [],
-   "source": [
-    "fig, axs = plt.subplots(nrows=2, ncols=3, sharex=\"col\", sharey=\"row\")\n",
-    "vmin = np.min(query_rate_b)\n",
-    "vmax = np.max(query_rate_b)\n",
-    "\n",
-    "for row in range(2):\n",
-    "    for col in range(3):\n",
-    "        ax = axs[row, col]\n",
-    "        level = row * 3 + col\n",
-    "        im = ax.imshow(query_rate_b[::-1,:,level], cmap=\"plasma\", vmin=vmin, vmax=vmax)\n",
-    "        ax.set_xticks(np.arange(len(errs)), labels=errs)\n",
-    "        ax.set_yticks(np.arange(len(errs)), labels=list(reversed(errs)))\n",
-    "        for i in range(len(errs)):\n",
-    "            for j in range(len(errs)):\n",
-    "                q_rate = f\"{query_rate_b[i, len(errs) - j - 1, level]:.0f}\"\n",
-    "                loc = f\"{errs[i]} {errs[j]}\"\n",
-    "                text = ax.text(i, j, q_rate, ha=\"center\", va=\"center\")\n",
-    "        ax.set_xlabel(\"$e_1$\")\n",
-    "        ax.set_ylabel(\"$e_O$\")\n",
-    "        ax.set_title(majs[level])\n",
-    "fig.set_size_inches((10,6))\n",
-    "fig.tight_layout(h_pad=1.5, rect=(0, 0, 0.9, 1))\n",
-    "cbar_ax = fig.add_axes((0.9, 0.10, 0.02, 0.84))\n",
-    "cbar = fig.colorbar(im, cax=cbar_ax)\n",
-    "cbar.ax.set_ylabel(\"Oracle query rate\", rotation=-90, va=\"bottom\")\n",
-    "fig.savefig(\"rpa_re_asymmetric_query_rate.pdf\")\n",
-    "plt.show()"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": null,
-   "id": "6b976938-f10d-439b-83b2-94d20d00ecbc",
-   "metadata": {},
-   "outputs": [],
-   "source": [
-    "fig, axs = plt.subplots(nrows=2, ncols=3, sharex=\"col\", sharey=\"row\")\n",
-    "for row in range(2):\n",
-    "    for col in range(3):\n",
-    "        ax = axs[row, col]\n",
-    "        level = row * 3 + col\n",
-    "        im = ax.imshow(correct_rate_b[::-1,:,level], cmap=\"viridis\", vmin=0, vmax=100)\n",
-    "        ax.set_xticks(np.arange(len(errs)), labels=errs)\n",
-    "        ax.set_yticks(np.arange(len(errs)), labels=list(reversed(errs)))\n",
-    "        for i in range(len(errs)):\n",
-    "            for j in range(len(errs)):\n",
-    "                c = correct_rate_b[i, len(errs) - j - 1, level]\n",
-    "                c_rate = f\"{c:.0f}%\"\n",
-    "                loc = f\"{errs[i]} {errs[j]}\"\n",
-    "                text = ax.text(i, j, c_rate, ha=\"center\", va=\"center\", color=\"w\" if c < 50 else \"black\")\n",
-    "        ax.set_xlabel(\"$e_1$\")\n",
-    "        ax.set_ylabel(\"$e_O$\")\n",
-    "        ax.set_title(majs[level])\n",
-    "fig.set_size_inches((10,6))\n",
-    "fig.tight_layout(h_pad=1.5, rect=(0, 0, 0.9, 1))\n",
-    "cbar_ax = fig.add_axes((0.9, 0.10, 0.02, 0.84))\n",
-    "cbar = fig.colorbar(im, cax=cbar_ax)\n",
-    "cbar.ax.set_ylabel(\"Success rate\", rotation=-90, va=\"bottom\")\n",
-    "cbar.ax.axhline(100 / len(multipliers), color=\"red\", linestyle=\"--\")\n",
-    "fig.savefig(\"rpa_re_asymmetric_success_rate.pdf\")\n",
-    "plt.show()"
-   ]
-  },
-  {
-   "cell_type": "code",
-   "execution_count": null,
-   "id": "868c4a7a-5c0f-4ee6-9a1a-2c251dfae34c",
-   "metadata": {},
-   "outputs": [],
-   "source": [
-    "fig, ax = plt.subplots()\n",
-    "ax.grid()\n",
-    "crs_accumulated = {}\n",
-    "for i, err_0 in enumerate(errs):\n",
-    "    for j, err_1 in enumerate(errs):\n",
-    "        crs = correct_rate_b[i, j, :]\n",
-    "        total_err = round(err_0 + err_1, 1)\n",
-    "        l = crs_accumulated.setdefault(total_err, [])\n",
-    "        l.append(crs)\n",
-    "        #ax.scatter(majs, crs, label=str(err_0 + err_1))\n",
-    "for total_err in crs_accumulated.keys():\n",
-    "    crs = np.mean(crs_accumulated[total_err], axis=0)\n",
-    "    ax.plot(majs, crs, label=f\"total_error = {total_err}\")\n",
-    "ax.set_xticks(majs)\n",
-    "ax.set_xlabel(\"majority\")\n",
-    "ax.set_ylabel(\"success rate\")\n",
-    "ax.legend(bbox_to_anchor=(1, 1.02))\n",
-    "fig.tight_layout()\n",
-    "plt.show()"
-   ]
-  },
-  {
    "cell_type": "markdown",
    "id": "62b0b8f2-8149-4abd-9aa7-a056b237ac6e",
    "metadata": {},