Tadge Dryja [ARCHIVE] on Nostr: š Original date posted:2016-08-08 š Original message: Blinded outsourcing of ...
š
Original date posted:2016-08-08
š Original message:
Blinded outsourcing of channel monitoring
The big risk in LN is that an attacking node can close a channel at an old,
invalidated state beneficial to the attacker, and the Bitcoin network will
accept these transactions. The node being attacked can defend by grabbing
both outputs, which will probably make such attacks quite rare. But, nodes
have to be online to detect this attack and defend against it, or risk
losing funds.
Outsourcing this vigilance can further defend against attacks by allowing
multiple parties to mount the defense. My initial thinking was that
minimizing the amount of data stored on the observer would be best, but I
don't think there's a way to make it O(log(n)) with the way Bitcoin works
today. (Sighash_noinput, some variants of MAST, etc could make that work
and we should keep that in mind, but that may be longer term)
So if it's going to be O(n), another way to make outsourcing better is to
anonimize / blind it. Of course if the observer actually sees an invalid
close and sends out a transaction moving the attacker's time-locked funds,
they will learn about how big the channel was, the txid, etc. But 99.999%
of the time, channels won't get closed at an invalid state, so the observer
doesn't actually do anything. Most of the time channels will be closed
cooperatively, but some times they'll be closed unilaterally because one
node is offline / unresponsive. We should keep privacy in either of those
cases.
States with in-flight HTLCs are another issue... if you want to keep the
data storage down, you can just not include them, and make a policy that
the sum of all the HTLCs should be less than either non-HTLC balance in the
channel. That way the attacker still loses money if they try to attack.
They potentially might not lose all of it though. You could make it
variable size and include HTLCs as well but that increases the data rate
significantly and probably hurts anonymity in various ways.
Without HTLCs, the script I have now specifies 2 pubkeys and requires 1 of
2 signatures- either from the timeout key or the revocable key. The goal
is that the observer is monitoring a channel, but even an uncooperative
close of that channel is undetectable, even after the output is spent and
the pubkeys are revealed in the p2wsh preimage. To meet this goal the two
pubkeys have to change completely with every new state, and also the
non-timelocked pubkey Hash output also needs to change each time.
A simple way to do it would be to have the two sides of the channel make up
new timeout and revocable pubkeys for each new state, but that's a lot of
data for them, and also an extra 66 bytes per state for the observer.
Instead, we can use the elkrem tree not just to revoke states, but also to
obscure the keys in each state.
To do this, the messages actually didn't change too much, but key
derivation changes a bit. At channel setup, A and B share "base points",
which are their public keys which will be used in the commitment script.
However these public keys are never used directly so I call them "points"
on the curve rather than pubkeys themselves. (Not sure what the best
convention is for that; I figure, call it a pubkey if you end up putting it
on the blockchain and making a signature with it; call it a point if it's
used otherwise, including to build a pubkey.)
When making a new state, instead of A sending B a revokable pubkey, A
instead sends two "elkrem points" specific to the state number. These
points are both deterministically derived from the same elkrem hash. For
example, if we're building state 9, A goes down the branches of their
elkrem tree to node #9, and gets a 32 byte hash. A appends ascii "t" for
the timeout point, and ascii "r" for the revocable point. A then uses
those two hashes as private scalars and multiplies by G, creating points on
the curve, or public keys. A sends those points to B as the "elkrem
points". B then adds elkrem point R to A's base point and elkrem point T
to B's own base point. The former results in A's revokable pubkey, the
latter in B's timeout pubkey for the script.
A sends elkrem points:
elkrem point R + B base point: Revokable Pubkey
elkrem point T + A base point: Timeout Pubkey
B's elkrem point R + B's refund point: Refund Pubkey hash
with these points, B signs & sends, A stores.
B sends elkrem points:
elkrem point R + A base point: Revokable Pubkey
elkrem point T + B base point: Timeout Pubkey
A's elkrem point R + A's refund point: Refund Pubkey hash
with these points, A signs & sends, B stores.
Before the state is revoked, the sender knows the scalar to generate the
elkrem points, so there's nothing hidden about the timeout and refund
pubkeys. Those just obscure the channel. The revokation pubkey is the
only one where nobody individually knows the private key for the pubkey
until the hashes are revealed.
Once the hashes are revealed and put into the tree, either party can
regenerate all the pubkeys at any previous state quickly. That's not
actually useful for the two nodes (why would you want to generate the
script of an old state?) but it's very useful for the outsourcing node.
They won't be able to recognize state n, but state 0 ... n-1 are
recognizable and can be stored efficiently.
The reason two different points are needed is that if you add the same
elkrem point to the two base points, the observer can subtract the base
points from the public key seen in the witness script.
A base point - timeout pubkey = elkrem
B base point - revokable pubkey = elkrem
if (A base point - timeout pubkey) == (B base point - revokable pubkey)
then that point must be the elkrem point, which would indicate that those
base points were used, allowing the observer to identify the channel.
Those are (I think) the only changes needed in the LN messages / protocol
itself. The design of the observer is not quite done but I have the basic
idea. It's kindof interesting, scalability-wise, because it will be
looking for a set of txids that's potentially much larger than the whole
blockchain! Basically when a node wants to give the observer an old state
to watch, it just gives a signature, a txid, and an elkrem hash. Only the
signature and txid need to be stored. Also you can drop part of the txid
at the risk of collisions, but the cost of collisions is pretty small
(mainly a few EC operations to build the pubkeys for the script), so 16 or
even 8 byte txids could work.
If the observer sees a transaction in a block which matches a txid they're
looking for, they do some sanity checks (e.g. does this tx have a p2wsh
output?) then re-create the script, by using the elkrem tree they have,
getting the state number from the tx itself (6 bytes, encoded in nLockTime
/ nSequence), generating the elkrem points, adding them to their stored
base points, hashing the script and seeing if the script matches. If it
does, , add the fixed output address, and figure out the output amount
based on the input amount. Then add the signature, which should match up
and result in a valid transaction.
This is preliminary and I wanted to send this mail about a week ago but I
kept finding ways the observer could figure out which channel it was
observing, and then devising ways to stop that.
The nice part about this way of doing it is that you can share the channel
state data with people you don't know or trust. Maybe they won't actually
watch over the channel for you, but maybe they might. If someone wanted to
be really nice, they could try to get *every* channel and observe it. All
you need is one or two nice people like that, and invalid closes become
nigh impossible.
I'll post a bit more once it's more finalized. If people see any problems
with this method please let me know!
-Tadge
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20160808/70c806f2/attachment.html>;
š Original message:
Blinded outsourcing of channel monitoring
The big risk in LN is that an attacking node can close a channel at an old,
invalidated state beneficial to the attacker, and the Bitcoin network will
accept these transactions. The node being attacked can defend by grabbing
both outputs, which will probably make such attacks quite rare. But, nodes
have to be online to detect this attack and defend against it, or risk
losing funds.
Outsourcing this vigilance can further defend against attacks by allowing
multiple parties to mount the defense. My initial thinking was that
minimizing the amount of data stored on the observer would be best, but I
don't think there's a way to make it O(log(n)) with the way Bitcoin works
today. (Sighash_noinput, some variants of MAST, etc could make that work
and we should keep that in mind, but that may be longer term)
So if it's going to be O(n), another way to make outsourcing better is to
anonimize / blind it. Of course if the observer actually sees an invalid
close and sends out a transaction moving the attacker's time-locked funds,
they will learn about how big the channel was, the txid, etc. But 99.999%
of the time, channels won't get closed at an invalid state, so the observer
doesn't actually do anything. Most of the time channels will be closed
cooperatively, but some times they'll be closed unilaterally because one
node is offline / unresponsive. We should keep privacy in either of those
cases.
States with in-flight HTLCs are another issue... if you want to keep the
data storage down, you can just not include them, and make a policy that
the sum of all the HTLCs should be less than either non-HTLC balance in the
channel. That way the attacker still loses money if they try to attack.
They potentially might not lose all of it though. You could make it
variable size and include HTLCs as well but that increases the data rate
significantly and probably hurts anonymity in various ways.
Without HTLCs, the script I have now specifies 2 pubkeys and requires 1 of
2 signatures- either from the timeout key or the revocable key. The goal
is that the observer is monitoring a channel, but even an uncooperative
close of that channel is undetectable, even after the output is spent and
the pubkeys are revealed in the p2wsh preimage. To meet this goal the two
pubkeys have to change completely with every new state, and also the
non-timelocked pubkey Hash output also needs to change each time.
A simple way to do it would be to have the two sides of the channel make up
new timeout and revocable pubkeys for each new state, but that's a lot of
data for them, and also an extra 66 bytes per state for the observer.
Instead, we can use the elkrem tree not just to revoke states, but also to
obscure the keys in each state.
To do this, the messages actually didn't change too much, but key
derivation changes a bit. At channel setup, A and B share "base points",
which are their public keys which will be used in the commitment script.
However these public keys are never used directly so I call them "points"
on the curve rather than pubkeys themselves. (Not sure what the best
convention is for that; I figure, call it a pubkey if you end up putting it
on the blockchain and making a signature with it; call it a point if it's
used otherwise, including to build a pubkey.)
When making a new state, instead of A sending B a revokable pubkey, A
instead sends two "elkrem points" specific to the state number. These
points are both deterministically derived from the same elkrem hash. For
example, if we're building state 9, A goes down the branches of their
elkrem tree to node #9, and gets a 32 byte hash. A appends ascii "t" for
the timeout point, and ascii "r" for the revocable point. A then uses
those two hashes as private scalars and multiplies by G, creating points on
the curve, or public keys. A sends those points to B as the "elkrem
points". B then adds elkrem point R to A's base point and elkrem point T
to B's own base point. The former results in A's revokable pubkey, the
latter in B's timeout pubkey for the script.
A sends elkrem points:
elkrem point R + B base point: Revokable Pubkey
elkrem point T + A base point: Timeout Pubkey
B's elkrem point R + B's refund point: Refund Pubkey hash
with these points, B signs & sends, A stores.
B sends elkrem points:
elkrem point R + A base point: Revokable Pubkey
elkrem point T + B base point: Timeout Pubkey
A's elkrem point R + A's refund point: Refund Pubkey hash
with these points, A signs & sends, B stores.
Before the state is revoked, the sender knows the scalar to generate the
elkrem points, so there's nothing hidden about the timeout and refund
pubkeys. Those just obscure the channel. The revokation pubkey is the
only one where nobody individually knows the private key for the pubkey
until the hashes are revealed.
Once the hashes are revealed and put into the tree, either party can
regenerate all the pubkeys at any previous state quickly. That's not
actually useful for the two nodes (why would you want to generate the
script of an old state?) but it's very useful for the outsourcing node.
They won't be able to recognize state n, but state 0 ... n-1 are
recognizable and can be stored efficiently.
The reason two different points are needed is that if you add the same
elkrem point to the two base points, the observer can subtract the base
points from the public key seen in the witness script.
A base point - timeout pubkey = elkrem
B base point - revokable pubkey = elkrem
if (A base point - timeout pubkey) == (B base point - revokable pubkey)
then that point must be the elkrem point, which would indicate that those
base points were used, allowing the observer to identify the channel.
Those are (I think) the only changes needed in the LN messages / protocol
itself. The design of the observer is not quite done but I have the basic
idea. It's kindof interesting, scalability-wise, because it will be
looking for a set of txids that's potentially much larger than the whole
blockchain! Basically when a node wants to give the observer an old state
to watch, it just gives a signature, a txid, and an elkrem hash. Only the
signature and txid need to be stored. Also you can drop part of the txid
at the risk of collisions, but the cost of collisions is pretty small
(mainly a few EC operations to build the pubkeys for the script), so 16 or
even 8 byte txids could work.
If the observer sees a transaction in a block which matches a txid they're
looking for, they do some sanity checks (e.g. does this tx have a p2wsh
output?) then re-create the script, by using the elkrem tree they have,
getting the state number from the tx itself (6 bytes, encoded in nLockTime
/ nSequence), generating the elkrem points, adding them to their stored
base points, hashing the script and seeing if the script matches. If it
does, , add the fixed output address, and figure out the output amount
based on the input amount. Then add the signature, which should match up
and result in a valid transaction.
This is preliminary and I wanted to send this mail about a week ago but I
kept finding ways the observer could figure out which channel it was
observing, and then devising ways to stop that.
The nice part about this way of doing it is that you can share the channel
state data with people you don't know or trust. Maybe they won't actually
watch over the channel for you, but maybe they might. If someone wanted to
be really nice, they could try to get *every* channel and observe it. All
you need is one or two nice people like that, and invalid closes become
nigh impossible.
I'll post a bit more once it's more finalized. If people see any problems
with this method please let me know!
-Tadge
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20160808/70c806f2/attachment.html>;