1# bLSAG ring signatures overview
  2*2022-07-20*
  3
  4> Note: I’m not a mathematician, I’m just an amateur on math. These notes are just an attempt to try to sort the notes that I took while learning abut bLSAG.
  5
  6<br>
  7bLSAG: Back's Linkable Spontaneous Anonymous Group signatures
  8
  9- signer ambiguity
 10- linkability
 11- unforgeability
 12
 13### Setup
 14Let $G$ be the generator of an EC group.
 15We use a hash function $\mathcal{H}_p$, which maps to curve points in EC, and a normal hash $\mathcal{H}_n$, which maps to $\mathbb{Z}_p$.
 16Signer's key pair: $k_{\pi}$, s.t. $K_{\pi} = k_{\pi} \cdot G \in \mathcal{R}$, with secret index $\pi$.
 17Set of Public Keys: $\mathcal{R} = \{ K_1, K_2, \ldots, K_n \}$
 18
 19```python
 20def new_key():
 21    k = F.random_element()
 22    K = g * k # g is the generator of the EC group
 23    return K
 24```
 25
 26### Signature
 271. compute key image: $\tilde{K} = k_{\pi} \mathcal{H_p} ( K_{\pi}) \in G$
 28    ```python
 29    key_image = k * hashToPoint(K)
 30    ```
 31
 322. Generate $\alpha \in^R \mathbb{Z}_p$, and $r_i \in^R \mathbb{Z}_p$, for $i \in \{1, 2, \ldots, n \}$, with $i \neq \pi$
 33    - $r_i$ is used for the fake responses
 34    ```python
 35        a = F.random_element()
 36        r = [None] * len(R)
 37        for i in range(0, len(R)):
 38            if i==pi:
 39                continue
 40
 41            r[i] = mod(F.random_element(), p)
 42    ```
 43
 443. Compute $c_{\pi + 1} = \mathcal{H}_n ( m, [\alpha G], [\alpha \mathcal{H}_p(K_{\pi})])$
 45
 46    ```python
 47    c[pi1] = hash(R, m, a * g, hashToPoint(R[pi]) * a, p)
 48    ```
 49
 504. for $i=\pi + 1, \pi +2, \ldots, n, 1, 2, \ldots, \pi -1$, calculate, replacing $n+1 \rightarrow 1$
 51    $$
 52    c_{i+1} = \mathcal{H}_n (m, [r_i G + c_i K_i], [r_i \mathcal{H}_p (K_i) + c_i \tilde{K}])
 53    $$
 54    - Notice that (from step 3 & 4):<br>
 55    $\alpha \mathcal{H}_p (K_{\pi}) = r_{\pi} \mathcal{H}_p (K_{\pi}) + c_{\pi} \cdot (\tilde{K})$,<br>
 56    where $\tilde{K}= k_{\pi} \mathcal{H_p} ( K_{\pi})$, so:<br>
 57    $\alpha \mathcal{H}_p (K_{\pi}) = r_{\pi} \mathcal{H}_p (K_{\pi}) + c_{\pi} \cdot (k_{\pi} \mathcal{H}_p(K_{\pi}))$<br>
 58    which is equal to,<br>
 59    $\alpha \cdot \mathcal{H}_p (K_{\pi}) = (r_{\pi} + c_{\pi} \cdot k_{\pi}) \cdot \mathcal{H}_p(K_{\pi})$<br>
 60    From where we can see: $\alpha = r_{\pi} + c_{\pi} \cdot k_{\pi}$<br>
 61    which we can rearrange to
 62    $r_{\pi} = \alpha - c_{\pi} \cdot k_{\pi}$.<br><br>
 63    
 64    ```python
 65    for j in range(0, len(R)-1):
 66        i = mod(pi1+j, len(R))
 67        i1 = mod(pi1+j +1, len(R))
 68
 69        c[i1] = hash(R, m, r[i] * g + c[i] * R[i],
 70                r[i] * hashToPoint(R[i]) + c[i] * key_image, p)
 71    ```
 72    
 736. Define $r_{\pi} = \alpha - c_{\pi} k_{\pi} \mod{p}$
 74
 75```python
 76r[pi] = mod(a - c[pi] * k, p)
 77```
 78
 79Signature: $\sigma(m) = (c_1, r_1, \ldots, r_n)$, with key image $\tilde{K}$ and ring $\mathcal{R}$.
 80- $len(\sigma(m)) = 1+n$
 81
 82```python
 83return [c[0], r]
 84```
 85
 86
 87<br><br><br>
 88
 89#### Step by step (simplified):
 90
 91<div style="overflow:auto;">
 92<div style="width: 60%; float:left; height: 360px; overflow-y:scroll;">
 93    
 94<img src="img/posts/ring-sig/step00.png" style="width:100%;" />
 95<img src="img/posts/ring-sig/step00.png" style="width:100%;" />
 96<img src="img/posts/ring-sig/step01.png" style="width:100%;" />
 97<img src="img/posts/ring-sig/step02.png" style="width:100%;" />
 98<img src="img/posts/ring-sig/step03.png" style="width:100%;" />
 99<img src="img/posts/ring-sig/step04.png" style="width:100%;" />
100<img src="img/posts/ring-sig/step05.png" style="width:100%;" />
101<img src="img/posts/ring-sig/step06.png" style="width:100%;" />
102    
103</div>
104
105
106<div style="width: 40%; float:right; margin-top:80px;">
107    
108    <ul>
109<li>Generate $r_i \in^R \mathbb{Z_p}$</li>
110<li>Compute $c_{i+1}$ from $r_i$</li>
111<li>Link $r_{\pi}$ with $c_{\pi}$</li>
112</ul>
113
114</div>
115</div>
116
117*You can scroll down the images through the step-by-step diagrams.*
118
119<br>
120
121It reminds in some way to the approach to close a box like the one in the picture:
122![](img/posts/ring-sig/box-closed.png)
123
124
125<br><br><br>
126### Verification
1271. check $p \tilde{K} \stackrel{?}{=} 0$
128    - to ensure that $\tilde{K} \in G$ (and not in a cofactor group of $G$)
1292. for $i = 1, 2, \ldots, n$, replacing $n+1 \rightarrow 1$
130    $$
131    c'_{i+1} = \mathcal{H}_n (m, [r_i G + c_i K_i], [r_i \mathcal{H}_p (K_i) + c_i \tilde{K}])
132    $$
1333. check $c_1 \stackrel{?}{=} c'_i$
134    ```python
135    c[0] = c1
136    for j in range(0, len(R)):
137        i = mod(j, len(R))
138        i1 = mod(j+1, len(R))
139        c[i1] = hash(R, m, r[i] * g + c[i] * R[i],
140                     r[i] * hashToPoint(R[i]) + c[i] * key_image, p)
141
142    assert c1 == c[0]
143    ```
144
145<br><br>
146
147## Links
148Toy implementation:
149
150- Sage: https://github.com/arnaucube/math/blob/master/ring-signatures.sage
151- Rust: https://github.com/arnaucube/ring-signatures-rs
152
153Resources:
154
155- *"Zero to Monero"* - https://web.getmonero.org/library/Zero-to-Monero-2-0-0.pdf
156(section *"3.4 Back’s Linkable Spontaneous Anonymous Group (bLSAG) signatures"*)
157
158
159
160
161
162
163
164
165