Contents

1. Basic Concepts

• Evaluation: Given a function $f$ and an input $x$, compute the function value $y$.
• Verification: Given a function $f$, an input $x$, and a function value $y$, verify whether $y = f(x)$.

Example 1:

Evaluation: Given a multiplicative group of order $n$ and an element $g$, find its inverse $y$.

Evaluation Method:

$$y = g^{-1} = g^{-1}g^{n} = g^{n - 1}$$

Computing $g^{n - 1}$ requires calculating $g^{2},g^{4},\ldots,g^{2^{i}}$ using exponentiation, needing at least $\log n$ multiplications.

Verification: Given a multiplicative group of order $n$ and an element $g$, verify that $y$ is its inverse.

Verification Method: Check if $g \cdot y = 1$, which requires only a single multiplication.

Hence, evaluation is at least $\log n$ times more complex than verification.

Example 2:

Evaluation: Given a cyclic elliptic curve group of order $n$ with generator $G$, and a public key $X$, find the private key $x$.

Evaluation Method: A brute-force search requires $2^{n}$ operations, with each step involving at least $\log x$ point doublings.

Verification: Given a cyclic elliptic curve group of order $n$ with generator $G$, and a public key $X$, verify that its private key is $x$.

Verification Method: Check if $xG = X$, which requires only $\log x$ point doublings.

Hence, evaluation is $2^{n}$ times more complex than verification.

Thus, verification generally has a much lower computational complexity than evaluation.

Similarly, in bilinear pairings, verifying whether a pairing equation holds, such as $e(A,B) = e(C,D)$, does not involve computing the individual pairing values but instead follows a verification approach to reduce computational cost.

2. Using Residue Verification Instead of Final Exponentiation

Two elements $x,y \in F$ are equivalent if and only if there exists some $c \in F^{*}$ such that $xc^{r} = y$:

$$y^{\frac{q^{k} - 1}{r}} = \left( x^{cr} \right)^{\frac{q^{k} - 1}{r}} = x^{\frac{q^{k} - 1}{r}}c^{q^{k} - 1} = x^{\frac{q^{k} - 1}{r}}.$$

Thus, by providing $c$ as an auxiliary input, we can directly verify $xc^{r} = y$ to reduce complexity.

Theorem 1: The product of pairings is equal to 1 if and only if the Miller loop product is an $r$-th residue:

$$\prod_{i}^{}e\left( P_{i},Q_{i} \right) = 1 \Leftrightarrow \exists c \in F_{q^{k}}^{*}:\prod_{i}^{}f_{r,Q}\left( P_{i} \right) = c^{r}.$$

Proof: Let $x = \prod_{i}^{}f_{r,Q}\left( P_{i} \right)$.

Completeness (If Direction):
Suppose

$$1 = \prod_{i}^{}e\left( P_{i},Q_{i} \right) = \left( \prod_{i}^{}e\left( P_{i},Q_{i} \right) \right)^{h} = x^{h}.$$

Since $r^{2} \nmid p^{k} - 1$ and $r \cdot h = q^{k} - 1$, we have $\gcd(r,h) = 1$ and $h' = h^{-1} \mod r$

Because $x^{hh'} = 1^{h'} = 1$ and $hh' = 1 + rs$, we obtain $x^{hh'} = x^{1 + rs} = 1$ 

Therefore, $c = x^{-s}$, implying $x = c^{r}$.

Soundness (Only If Direction):

Suppose $\prod_{i}^{}f_{r,Q}\left( P_{i} \right) = c^{r}$. Raising both sides to the power of $h$, we get $\prod_{i}^{}e\left( P_{i},Q_{i} \right) = c^{rh} = 1$.

By providing $c$ as an auxiliary input, we can replace final exponentiation with $r$-residue verification, reducing computational complexity.

Theorem 2: The Product of Pairings Equals 1 If and Only If the Miller Loop Product is a $\lambda/d$-th Residue

$$\prod_{i}^{}e\left( P_{i},Q_{i} \right) = 1 \Leftrightarrow \exists c \in F_{q^{k}}^{*}:\prod_{i}^{}f_{r,Q}\left( P_{i} \right) = c^{\lambda/d}.$$

Proof: If $\prod_{i}^{}e\left( Q_{i},P_{i} \right) = 1$, then according to Theorem 1, we have $\prod_{i}^{}f_{r,Q}\left( P_{i} \right) = c^{r}$, implying $ord(c) \mid r$.

By definition, $\frac{m}{d} \nmid h$ and $\frac{m}{d}$ is not divisible by any divisor of $h$, leading to $\gcd\left( \frac{m}{d},ord(c) \right) = 1$.

Thus, there exists an integer $m'$ such that:

$$\frac{m}{d} \cdot m' = 1 \mod ord(c)$$

This means that for some $c$, we obtain:

$$\left( c^{m'} \right)^{(m/d)} = c$$

Thus, the Miller Loop can always be reduced to a $\lambda/d$-th residue.

Conversely, raising both sides to the power of $h$, we get:

$$\prod_{i}^{}f_{r,Q_{i}}\left( P_{i} \right)^{h} = \left( c^{\frac{m}{d}} \right)^{rh} = 1 = \prod_{i = 0}^{n}e\left( Q_{i},P_{i} \right)$$

Therefore, by providing an auxiliary input $c$, we can replace the final exponentiation with $\lambda/d$-th residue verification, significantly reducing computational complexity.

Lemma 1 Suppose $a$ and $u$ satisfy $a^{r} = u$. If $\prod_{i = 0}^{n}e\left( Q_{i},P_{i} \right) \neq 1$, then there does not exist $c \in F_{q}^{*}$ such that:

$$\prod_{i = 0}^{n}f_{r},Q_{i}\left( P_{i} \right) \cdot u = c^{r}$$

Proof: When $\prod_{i = 0}^{n}e\left( Q_{i},P_{i} \right) \neq 1$, we have:

$$\prod_{i = 0}^{n}f_{r},Q_{i}\left( P_{i} \right) = w^{i} \cdot s^{r}$$

where $s \in F_{q}^{*}$, $i \neq 0$, and $w$ is an $r$-th root of unity in $F_{q}^{*}$.

Conversely, if there exists $c \in F_{q}^{*}$ such that:

$$w^{i} \cdot s^{r} \cdot u = c^{r}$$

then:

$$w^{i} = \left( \frac{c}{s \cdot a} \right)^{r}$$

By the definition of $r$-th roots of unity, we know:

$$\left( w^{i} \right)^{r} = 1$$

which implies:

$$\left( \frac{c}{s \cdot a} \right)^{r} = 1$$

Thus, the order of $\frac{c}{s \cdot a}$ is $r^{2}$, contradicting the assumption that $r^{2} \nmid q^{k} - 1$.

Lemma 2: Let $b$ be a non-$d$-th residue. Then, there exists an $a$ such that: - $a$ is a non-$d$-th residue but an $r$-th residue. - $a \cdot b$ is a $d$-th residue.

Proof: Let $h = d^{s} \cdot f$, where $d \nmid f$. Choose $a$ such that $ord(a) = d^{s}$.

Since $r$ is a prime and $\gcd\left( d^{s},r \right) = 1$, it follows that $a$ is an $r$-th residue.

To prove that $a$ is a non-$d$-th residue, assume the contrary:

If there exists $b$ such that $b^{d} = a$, then given that $ord(a) = d^{s}$, this would imply:

$$ord(b) = d^{s + 1}$$

which contradicts $d^{s + 1} \nmid h$, implying $d^{s + 1} \nmid q^{k} + 1$.

Since $b$ is a non-$d$-th residue, we have:

$$b^{\left( q^{k} - 1 \right)/d} = w^{i}$$

for some $i \neq 0$ and $\left( w^{i} \right)^{d} = 1$. Moreover, $a$ is also a non-$d$-th residue, meaning all $a^{i}$ (for $i \in \lbrack 1,d - 1\rbrack$) are non-$d$-th residue.

By evaluating $\left( a^{i} \right)^{\left( q^{k} - 1 \right)/d}$, which forms a permutation over $i \in \lbrack 1,d - 1\rbrack$, there exists some $j$ such that:

$$\left( a^{j} \right)^{\left( q^{k} - 1 \right)/d} = w^{-i}$$

making $a^{j}$ a $d$-th residue.

Theorem 3: The Product of Pairings Equals 1 If and Only If the Miller Loop Output is a $d^{i}$-th Root of Unity and $\lambda$-th Residue Verification Holds

$$\prod_{i}^{}e\left( P_{i},Q_{i} \right) = 1 \Leftrightarrow \exists c,u \in F_{q^{k}}^{*}:\prod_{i}^{}f_{r,Q}\left( P_{i} \right) = c^{\lambda}u \land u^{d^{i}} = 1$$

Proof: We need to prove that there exists $x$ if and only if there exist $c,u$ such that:

$$x^{r} = c^{d}u,\quad u^{d^{i}} = 1$$

Given that $\gcd(d,rm) = 1$, there exists:

$$v = u^{(rm)^{-1} \mod d^{i}}$$

such that:

$$v^{rm} = u$$

Let $m' = m^{-1} \mod \left( q^{k} - 1 \right)$. Rewriting the equation:

$$x^{rm'} = \left( c^{d}v \right)^{rmm'}$$

Let $y = x^{m'}$, then $x = y^{m}$.

We need to show that $y$ exists if and only if there exist $c,v$ such that:

$$y = c^{d}v,\quad v^{d^{i}} = 1$$

• If $c,v$ exist, then $y$ exists.
• $y$ can be computed using the Tonelli-Shanks algorithm.
• Given $x$, we compute $c$ and $v$ from $x^{m'}$, then set $u = v^{rm}$.

Conversely, given $c,u$, we set:

$$x = \left( c^{d}u^{(rm)^{-1} \mod d^{i}} \right)^{m}$$

Thus, the theorem holds.

3. Verifying Line Coefficients Instead of Computing Lines

Instead of computing the line equation from points $T$ and $Q$, we provide the line coefficients $(\lambda,\mu)$ and verify that the line $y = \lambda x + \mu$ passes through $T$ and $Q$. This enables efficient computation of the line value at $P$.

Tangent Line Verification and Evaluation:

Given a point $T = \left( x_{1},y_{1} \right) \in E\left( F_{q^{k}} \right)$, evaluate its tangent line at $P \in E\left( F_{q} \right)$ using line coefficients $(\lambda,\mu)$.

1. Verify that $(\lambda,\mu)$ defines the tangent line passing through $T$:
   Verify $y_{1} - \lambda x_{1} = 0$ and $2\lambda y_{1} = 3x_{1}^{2}$.
2. Compute $\lambda^{2}$.
3. Compute $x_{3} = \lambda^{2} - 2x_{1}$, $y_{3} = - \mu - \lambda x_{3}$.
4. Compute ${line}_{T,Q}(P) = 1 + \lambda x'_{P} - y'_{P}\mu\omega^{3}$.

Intersection Line Verification and Evaluation:

Given points $T = \left( x_{1},y_{1} \right),Q = \left( x_{2},y_{2} \right) \in E\left( F_{q^{k}} \right)$, evaluate their intersection line at $P \in E\left( F_{q} \right)$ using coefficients $(\lambda,\mu)$.

1. Verify that $(\lambda,\mu)$ defines the line passing through $T$ and $Q$:
   Verify $y_{1} - \lambda x_{1} - \mu = 0$ and $y_{2} + \lambda x_{2} - \mu = 0$.
2. Compute $\lambda^{2}$.
3. Compute $x_{3} = \lambda^{2} - x_{1} - x_{2}$, $y_{3} = - \mu - \lambda x_{3}$.
4. Compute ${line}_{T,Q}(P) = 1 + \lambda x'_{P} - y'_{P}\mu\omega^{3}$.

Thus, by providing the coefficients $(\lambda,\mu)$, we can verify that the line passes through $T$ and $Q$ without computing it from them, reducing complexity.

4. Algorithm Overview

Define a line determined by $(\lambda,\mu) \in F_{q}^{2/k}$ with the following functions:

• line.is_tangent(T): Verifies if the line is the tangent at $T$.
• line.is_line(T, Q): Verifies if the line passes through $T$ and $Q$.
• line.evaluate(P): Evaluates the line at $P$.
• line.double(T): Performs point doubling, returning $2T$.
• line.add(T, Q): Performs point addition, returning $T + Q$.

The final algorithm of Miller Loop is optimized as follows:

from BitVM2: Bridging Bitcoin to Second Layers

Heading 1

Heading 2

Heading 3

Bold text

Heading 4

Heading 5

Heading 6

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur.

Block quote

Ordered list

1. Item 1
2. Item 2
3. Item 3

Unordered list

• Item A
• Item B
• Item C

Text link

Emphasis

^Superscript

_Subscript