ZmnSCPxj [ARCHIVE] on Nostr: 📅 Original date posted:2023-06-28 🗒️ Summary of this message: A mathematical ...
📅 Original date posted:2023-06-28
🗒️ Summary of this message: A mathematical demonstration shows how blinding factors can be computed to ensure privacy in a routing network with trampoline nodes.
📝 Original message:
Good morning list,
Here is a simple mathematical demonstration of a particular way to compute blinding factors such that:
* All non-Trampoline intermediate nodes only need to know one blinding factor.
* The receiver only needs to know one blinding factor.
* Trampoline nodes can provide the nodes on the sub-routes they decide the blinding factors without the non-Trampoline intermediate nodes knowing they are on a trampoline and not a "direct" source-to-dest route.
First, let us start with:
* The ultimate receiver has a secret `r`.
* The ultimate receiver gives the ultimate sender the point `R`, such that `R = r * G`.
Now, suppose the ultimate sender is directly channeled with the ultimate receiver.
The ultimate sender chooses a fresh random scalar `e`, the "error" blinding factor that reaches the ultimate receiver.
It then constructs an onion with `e` decryptable by the ultimate receiver.
Together with that onion, the ultimate sender offers a PTLC with the point `e * G + R`.
The ultimate receiver can claim that PTLC by revealing `e + r`, as it learns `e` from the onion, and knows `r` and the contract is to give `r` in exchange for payment.
That is the simplest case.
--
Now let us suppose that the ultimate receiver needs to got through an intermediate node, Carol.
The ultimate sender still needs to choose a final error scalar, `e`, by random.
However, it also needs to generate two scalars, `c` and `d`, such that `c + d = e`.
This can be done by selecting a random `d` and computing `c = e - d` (by algebra).
By algebra, `d = e - c`.
The ultimate sender then encrypts the onion:
* `e` encrypted to the ultimate receiver.
* The above ciphertext, and `d` encrypted to intermediate node Carol.
The ultimate sender then sends the PTLC with point `c * G + R` to Carol.
Each intermediate non-Trampoline node --- such as Carol --- then gets the input point, adds its per-hop blinding factor times `G`, and uses the result as the output point to the next hop.
So Carol receives `c * G + R`.
Carol then adds `d * G` (which is the `d` error it got from the onion).
Carol then sends a PTLC (with one less onion hop layer as well) with the point `c * G + R + d * G`.
Note that `e = c + d`, so we can re-arrange the PTLC sent by Carol to the ultimate sender as `(c + d) * G + R`.
This is equal to `e * G + R`, the exact same as in the case where the ultimate sender is directly channeled with ultimate receiver.
The ultimate receiver therefore cannot know whether it received from Carol, or from a further node, as in both the direct case and the indirect case, the ultimate receiver sees `e * G + R`.
When the ultimate receiver releases `e + r`, Carol can compute `c + r` by taking `e + r - d`, and since `c = e - d`, `e + r - d = e - d + r = c + r`.
It can then claim the incoming `c * G + R` with scalar `c + r`.
Carol does not know `c`, it only knows `d`, and thus it cannot compute `r`.
--
Now let us instead suppose that Carol is a Trampoline node, and that the ultimate sender does not provide a detailed route from Carol to the next Trampoline hop.
In this next example, the ultimate receiver is actually the final Trampoline hop after Carol, but Carol does not know this fact (and should not be able to learn this fact).
The ultimate sender learns `R`, then selects a random `e`.
It then selects `c` and `d` such that `c + d = e`, using the same technique as above (i.e. random-pick `d` and compute `c = e - d`).
Now the ultimate sender computes a Trampoline-level onion, with the following:
* `e` encrypted to the ultimate receiver.
* the above ciphertext, `d`, and the next Trampoline hop (i.e. the node ID of ultimate receiver), encrypted to Carol.
The ultimate sender then sends a PTLC with the above onion, with point `c * G + R`, to Carol.
Carol then decrypts the onion, and gets `d`.
It then has to search for a route from Carol to the ultimate receiver (the next Trampoline hop).
Let us suppose that Carol finds a route Carol -> Alice -> ultimate receiver.
Carol now needs to make `c * G + d * G + R` reach the ultimate receiver.
It can do that by selecting two scalars, `a` and `b`, such that `a + b = d`.
It knows `d`, and can random-pick` b` and then compute `a = d - b`.
Carol then creates the onion:
* It copies the ciphertext from ultimate sender: `e` encrypted to the ultimate receiver.
* The above ciphertext, and `b`, encrypted to Alice.
Carol then sends the PTLC with point `c * G + R + a * G` to Alice.
Alice decrypts the onion and learns `b`.
Forwarding, it gives the PTLC with point `c * G + R + a * G + b * G` to the next hop, the ultimate receiver.
Now, `a + b = d` therefore `a * G + b * G = d * G`.
And `c + d = e`, therefore `c * G + d * G = e * G`.
Thus:
c * G + R + a * G + b * G
= c * G + a * G + b * G + R; commutative property
= c * G + (a + b) * G + R; associative property
= c * G + d * G + R; d = a + b by construction
= (c + d) * G + R; associative property
= e * G + R; e = c + d by construction
Thus, again, the ultimate receiver gets the same `e * G + R` and cannot differentiate whether it was reached via a Trampoline, via a non-Trampoline intermediate, or directly.
Similarly, on claiming, every intermediate (Trampoline and non-Trampoline) node has enough data to claim its incoming PTLC.
And only the ultimate sender knows `c`, which allows it to recover the `r`.
Regards,
ZmnSCPxj
🗒️ Summary of this message: A mathematical demonstration shows how blinding factors can be computed to ensure privacy in a routing network with trampoline nodes.
📝 Original message:
Good morning list,
Here is a simple mathematical demonstration of a particular way to compute blinding factors such that:
* All non-Trampoline intermediate nodes only need to know one blinding factor.
* The receiver only needs to know one blinding factor.
* Trampoline nodes can provide the nodes on the sub-routes they decide the blinding factors without the non-Trampoline intermediate nodes knowing they are on a trampoline and not a "direct" source-to-dest route.
First, let us start with:
* The ultimate receiver has a secret `r`.
* The ultimate receiver gives the ultimate sender the point `R`, such that `R = r * G`.
Now, suppose the ultimate sender is directly channeled with the ultimate receiver.
The ultimate sender chooses a fresh random scalar `e`, the "error" blinding factor that reaches the ultimate receiver.
It then constructs an onion with `e` decryptable by the ultimate receiver.
Together with that onion, the ultimate sender offers a PTLC with the point `e * G + R`.
The ultimate receiver can claim that PTLC by revealing `e + r`, as it learns `e` from the onion, and knows `r` and the contract is to give `r` in exchange for payment.
That is the simplest case.
--
Now let us suppose that the ultimate receiver needs to got through an intermediate node, Carol.
The ultimate sender still needs to choose a final error scalar, `e`, by random.
However, it also needs to generate two scalars, `c` and `d`, such that `c + d = e`.
This can be done by selecting a random `d` and computing `c = e - d` (by algebra).
By algebra, `d = e - c`.
The ultimate sender then encrypts the onion:
* `e` encrypted to the ultimate receiver.
* The above ciphertext, and `d` encrypted to intermediate node Carol.
The ultimate sender then sends the PTLC with point `c * G + R` to Carol.
Each intermediate non-Trampoline node --- such as Carol --- then gets the input point, adds its per-hop blinding factor times `G`, and uses the result as the output point to the next hop.
So Carol receives `c * G + R`.
Carol then adds `d * G` (which is the `d` error it got from the onion).
Carol then sends a PTLC (with one less onion hop layer as well) with the point `c * G + R + d * G`.
Note that `e = c + d`, so we can re-arrange the PTLC sent by Carol to the ultimate sender as `(c + d) * G + R`.
This is equal to `e * G + R`, the exact same as in the case where the ultimate sender is directly channeled with ultimate receiver.
The ultimate receiver therefore cannot know whether it received from Carol, or from a further node, as in both the direct case and the indirect case, the ultimate receiver sees `e * G + R`.
When the ultimate receiver releases `e + r`, Carol can compute `c + r` by taking `e + r - d`, and since `c = e - d`, `e + r - d = e - d + r = c + r`.
It can then claim the incoming `c * G + R` with scalar `c + r`.
Carol does not know `c`, it only knows `d`, and thus it cannot compute `r`.
--
Now let us instead suppose that Carol is a Trampoline node, and that the ultimate sender does not provide a detailed route from Carol to the next Trampoline hop.
In this next example, the ultimate receiver is actually the final Trampoline hop after Carol, but Carol does not know this fact (and should not be able to learn this fact).
The ultimate sender learns `R`, then selects a random `e`.
It then selects `c` and `d` such that `c + d = e`, using the same technique as above (i.e. random-pick `d` and compute `c = e - d`).
Now the ultimate sender computes a Trampoline-level onion, with the following:
* `e` encrypted to the ultimate receiver.
* the above ciphertext, `d`, and the next Trampoline hop (i.e. the node ID of ultimate receiver), encrypted to Carol.
The ultimate sender then sends a PTLC with the above onion, with point `c * G + R`, to Carol.
Carol then decrypts the onion, and gets `d`.
It then has to search for a route from Carol to the ultimate receiver (the next Trampoline hop).
Let us suppose that Carol finds a route Carol -> Alice -> ultimate receiver.
Carol now needs to make `c * G + d * G + R` reach the ultimate receiver.
It can do that by selecting two scalars, `a` and `b`, such that `a + b = d`.
It knows `d`, and can random-pick` b` and then compute `a = d - b`.
Carol then creates the onion:
* It copies the ciphertext from ultimate sender: `e` encrypted to the ultimate receiver.
* The above ciphertext, and `b`, encrypted to Alice.
Carol then sends the PTLC with point `c * G + R + a * G` to Alice.
Alice decrypts the onion and learns `b`.
Forwarding, it gives the PTLC with point `c * G + R + a * G + b * G` to the next hop, the ultimate receiver.
Now, `a + b = d` therefore `a * G + b * G = d * G`.
And `c + d = e`, therefore `c * G + d * G = e * G`.
Thus:
c * G + R + a * G + b * G
= c * G + a * G + b * G + R; commutative property
= c * G + (a + b) * G + R; associative property
= c * G + d * G + R; d = a + b by construction
= (c + d) * G + R; associative property
= e * G + R; e = c + d by construction
Thus, again, the ultimate receiver gets the same `e * G + R` and cannot differentiate whether it was reached via a Trampoline, via a non-Trampoline intermediate, or directly.
Similarly, on claiming, every intermediate (Trampoline and non-Trampoline) node has enough data to claim its incoming PTLC.
And only the ultimate sender knows `c`, which allows it to recover the `r`.
Regards,
ZmnSCPxj