Anthony Towns [ARCHIVE] on Nostr: 📅 Original date posted:2015-07-25 📝 Original message: On Fri, Jul 24, 2015 at ...
📅 Original date posted:2015-07-25
📝 Original message:
On Fri, Jul 24, 2015 at 03:38:28PM -0700, Joseph Poon wrote:
> If we're presuming everyone uses OP_CSV in the long-term, you can
> overload nLockTime with values below current unixtime as a
> filter/counter. It should be enough bits of entropy no matter the size
> (even in the billions of transactions in a single channel) Since both
> parties are signing the nLockTime value, it's safe to use that as an
> identifier in the Commitment Transaction.
Oh, that's clever! You can use the range between 500M and $NOW, which
gives you 937,798,763 values at the time of writing, so about a billion
updates per channel. If that wasn't enough, you could divide your actual
n by 10, 100, 1000 etc, and just have to search through an additional 10,
100, 1000 hashes to work out which value to use when claiming cheating.
On Fri, Jul 24, 2015 at 04:24:49PM -0700, Joseph Poon wrote:
> Ah sorry, that only solves the Commitment Transactions, not the HTLC
> outputs. It's also not possible to use the pubkeys as identifiers, as
> Rusty said, P2SH would be used.
>
> While it's possible to only check only recent blocks before the
> Commitment Transaction for the search space (e.g. 3 days worth), since
> you know when the Commitment Transaction was broadcast, the search space
> limitation sort of breaks down if you permit long-dated HTLCs.
I don't think it matters how long the HTLC was; maybe they're way old
and all expired, but were payments to you. Say the current channel is:
12 -> Cheater
88 -> You
and the old transaction that Cheater just pushed to the blockchain was:
55 -> Cheater
3 -> You
10 -> You & R1 | Cheater & Timeout1
20 -> You & R2 | Cheater & Timeout2
12 -> You & R3 | Cheater & Timeout3
To get at least your 88 owed, you need all but the last transaction, so
you need to be able to workout #R1 and #R2 and Timeout1 and Timeout2, no
matter how long ago they were.
> For now, I think a reasonable stop-gap solution would be to have some
> small storage of prior commitment transactions. For every commitment,
> and each HTLC output, store the timeout and the original Commitment
> Transaction height when the HTLC was first made.
I don't think you want to multiply each HTLC output by every commitment
it's stored in -- if the TIMEOUT is on the order of a day, and the
channel is updated just once a second that's a x86,400 blowout in
storage, so almost 5 orders of magnitude.
But if everytime you see a new HTLC output (ie, R4, Timeout4), you could
store those values and use the nLockTime trick to store the height of
your HTLC storage. Then you just have to search back down from R4 to
find the other HTLCs in the txn, ie R3, R2 and R1, which is just a
matter of pulling out the values R, Timeout, dropping them into payment
script templates, and checking if they match.
You could also store your commitment count to still limit the searching
you have to do there. If you make the rule:
- nLockTime will increment everytime we introduce a new HTLC
- nLockTime will increment everytime there's been N commitment updates
since the last time nLockTime incremented
and you store:
- 47b commitment index
- 1b am I being paid?
- 80b R
- 16b timeout
each time. If it's a new HTLC you store the info for that, if it's just
a commitment bump, you store the active HTLC that's furthest from the
top of the stack, or all 0s. That's 18 bytes per HTLC or n commitments.
If you spend a year doing 100 new HTLC/s that's 57GB for HTLCs and
if you set n to be 100k hashes to search through (so half a minute's
work on Rusty's laptop), and assume 1000 commitments/s in a worst case
distribution, that's just an extra 5MB.
You might have to increment by ~0.25 each time instead to last a year
without nLockTime surpassing current Unix time; I don't think that causes
much problem though -- you have maybe 4x as many commitment hashes to
check, and up to an extra 3 HTLCs to check and skip. Reduce n by 4 to
compensate, and that's an extra 20MB instead of 5MB.
~60GB after a year is about 30*12 = 360 GB-months of data, which is
about $12 on Amazon S3. That seems reasonably plausible, even at scale,
doesn't it?
(If you need an extra 4B per HTLC to avoid relying on OP_CTV/OP_CSV;
that's ~23% more space; so say $15 over the course of a year)
> That should be enough
> information to work with (you can work backwards if you know which
> Commitment Transaction the HTLC was first created) and amounts to 48
> bits (6 bytes) of storage per HTLC output per fully expired Commitment
> Transaction. I generally dislike OP_RETURN as a solution, but it's
> possible.
Hmm, I'm not sure OP_RETURN actually works well enough for avoiding
local storage of HTLC specs -- more than one OP_RETURN is non-standard :(
(Of course the scripts behind the P2SH hashes are non-standard too)
> Thanks for bringing this up, I haven't really properly considered this!
Glad it's novel :)
On Fri, Jul 24, 2015 at 05:38:25PM -0700, Joseph Poon wrote:
> Oh, I forgot it's necessary to store the hash of the R value. That'll
> make it much bigger. 26-bytes or so.
> Also, if OP_RETURN is viewed as acceptable, then you should be able to
> fit 3 outputs per OP_RETURN metadata output.
Yeah; 80 bytes works much better than 40 bytes.
> 32-bits is used for the Commitment Transaction. For even the most
> high-volume node, 10 commitments per second results in 300 million
> Commitment Transactions. This identifies in which Commitment Transaction
> the HTLC was created. By knowing the Commitment Transaction, you'll know
> the revocation preimage, so after the revocation information has been
> exchanged, you only need to know which Commitment Transaction the HTLC
> was originally formed, since the revocation information was originally
> *generated* using a merkle tree derived from the Commitment Transaction
> as an index.
I don't think this is useful if you've got OP_CTV and OP_CSV? If your
script is:
Pay: (Alice & R & DELAY) | (Bob & TIMEOUT) | (Bob & REVOCATION)
then the REVOCATION has to be updated with each commitment update, or
else Bob would be able to claim it immediately after the next commitment
update. So you only need to know the txn's commitment id, which you
work out from nLockTime anyway.
Otherwise, Alice, Bob, and DELAY are channel parameters; leaving just
R and TIMEOUT which fit in 22 bytes. So you can fit ~3.6 R&TIMEOUTs in
a single OP_RETURN (so 3.6 in 1, 7.2 in 2, exactly 40 in 11).
I'm not sure how the key management works for when you don't have OP_CTV
or OP_CSV. I guess if the the key set used for HTLC #N is calculable given
any secret M>N (but not M<=N), and you always reveal secret MIN(current
active HTLC ids), then you just need to record the HTLC's index. You
could again allow for a small search though; you only have to calculate
the public key and hash the transaction against the calculated keys so
searching should still be somewhat cheap. So yeah, I think that makes
sense?
BTW, 10 commitments per second (per channel) doesn't sound /that/ high
volume :) Pay per megabyte for an end user at 100Mb/s is already
around that at least at peak times, eg.
Cheers,
aj
📝 Original message:
On Fri, Jul 24, 2015 at 03:38:28PM -0700, Joseph Poon wrote:
> If we're presuming everyone uses OP_CSV in the long-term, you can
> overload nLockTime with values below current unixtime as a
> filter/counter. It should be enough bits of entropy no matter the size
> (even in the billions of transactions in a single channel) Since both
> parties are signing the nLockTime value, it's safe to use that as an
> identifier in the Commitment Transaction.
Oh, that's clever! You can use the range between 500M and $NOW, which
gives you 937,798,763 values at the time of writing, so about a billion
updates per channel. If that wasn't enough, you could divide your actual
n by 10, 100, 1000 etc, and just have to search through an additional 10,
100, 1000 hashes to work out which value to use when claiming cheating.
On Fri, Jul 24, 2015 at 04:24:49PM -0700, Joseph Poon wrote:
> Ah sorry, that only solves the Commitment Transactions, not the HTLC
> outputs. It's also not possible to use the pubkeys as identifiers, as
> Rusty said, P2SH would be used.
>
> While it's possible to only check only recent blocks before the
> Commitment Transaction for the search space (e.g. 3 days worth), since
> you know when the Commitment Transaction was broadcast, the search space
> limitation sort of breaks down if you permit long-dated HTLCs.
I don't think it matters how long the HTLC was; maybe they're way old
and all expired, but were payments to you. Say the current channel is:
12 -> Cheater
88 -> You
and the old transaction that Cheater just pushed to the blockchain was:
55 -> Cheater
3 -> You
10 -> You & R1 | Cheater & Timeout1
20 -> You & R2 | Cheater & Timeout2
12 -> You & R3 | Cheater & Timeout3
To get at least your 88 owed, you need all but the last transaction, so
you need to be able to workout #R1 and #R2 and Timeout1 and Timeout2, no
matter how long ago they were.
> For now, I think a reasonable stop-gap solution would be to have some
> small storage of prior commitment transactions. For every commitment,
> and each HTLC output, store the timeout and the original Commitment
> Transaction height when the HTLC was first made.
I don't think you want to multiply each HTLC output by every commitment
it's stored in -- if the TIMEOUT is on the order of a day, and the
channel is updated just once a second that's a x86,400 blowout in
storage, so almost 5 orders of magnitude.
But if everytime you see a new HTLC output (ie, R4, Timeout4), you could
store those values and use the nLockTime trick to store the height of
your HTLC storage. Then you just have to search back down from R4 to
find the other HTLCs in the txn, ie R3, R2 and R1, which is just a
matter of pulling out the values R, Timeout, dropping them into payment
script templates, and checking if they match.
You could also store your commitment count to still limit the searching
you have to do there. If you make the rule:
- nLockTime will increment everytime we introduce a new HTLC
- nLockTime will increment everytime there's been N commitment updates
since the last time nLockTime incremented
and you store:
- 47b commitment index
- 1b am I being paid?
- 80b R
- 16b timeout
each time. If it's a new HTLC you store the info for that, if it's just
a commitment bump, you store the active HTLC that's furthest from the
top of the stack, or all 0s. That's 18 bytes per HTLC or n commitments.
If you spend a year doing 100 new HTLC/s that's 57GB for HTLCs and
if you set n to be 100k hashes to search through (so half a minute's
work on Rusty's laptop), and assume 1000 commitments/s in a worst case
distribution, that's just an extra 5MB.
You might have to increment by ~0.25 each time instead to last a year
without nLockTime surpassing current Unix time; I don't think that causes
much problem though -- you have maybe 4x as many commitment hashes to
check, and up to an extra 3 HTLCs to check and skip. Reduce n by 4 to
compensate, and that's an extra 20MB instead of 5MB.
~60GB after a year is about 30*12 = 360 GB-months of data, which is
about $12 on Amazon S3. That seems reasonably plausible, even at scale,
doesn't it?
(If you need an extra 4B per HTLC to avoid relying on OP_CTV/OP_CSV;
that's ~23% more space; so say $15 over the course of a year)
> That should be enough
> information to work with (you can work backwards if you know which
> Commitment Transaction the HTLC was first created) and amounts to 48
> bits (6 bytes) of storage per HTLC output per fully expired Commitment
> Transaction. I generally dislike OP_RETURN as a solution, but it's
> possible.
Hmm, I'm not sure OP_RETURN actually works well enough for avoiding
local storage of HTLC specs -- more than one OP_RETURN is non-standard :(
(Of course the scripts behind the P2SH hashes are non-standard too)
> Thanks for bringing this up, I haven't really properly considered this!
Glad it's novel :)
On Fri, Jul 24, 2015 at 05:38:25PM -0700, Joseph Poon wrote:
> Oh, I forgot it's necessary to store the hash of the R value. That'll
> make it much bigger. 26-bytes or so.
> Also, if OP_RETURN is viewed as acceptable, then you should be able to
> fit 3 outputs per OP_RETURN metadata output.
Yeah; 80 bytes works much better than 40 bytes.
> 32-bits is used for the Commitment Transaction. For even the most
> high-volume node, 10 commitments per second results in 300 million
> Commitment Transactions. This identifies in which Commitment Transaction
> the HTLC was created. By knowing the Commitment Transaction, you'll know
> the revocation preimage, so after the revocation information has been
> exchanged, you only need to know which Commitment Transaction the HTLC
> was originally formed, since the revocation information was originally
> *generated* using a merkle tree derived from the Commitment Transaction
> as an index.
I don't think this is useful if you've got OP_CTV and OP_CSV? If your
script is:
Pay: (Alice & R & DELAY) | (Bob & TIMEOUT) | (Bob & REVOCATION)
then the REVOCATION has to be updated with each commitment update, or
else Bob would be able to claim it immediately after the next commitment
update. So you only need to know the txn's commitment id, which you
work out from nLockTime anyway.
Otherwise, Alice, Bob, and DELAY are channel parameters; leaving just
R and TIMEOUT which fit in 22 bytes. So you can fit ~3.6 R&TIMEOUTs in
a single OP_RETURN (so 3.6 in 1, 7.2 in 2, exactly 40 in 11).
I'm not sure how the key management works for when you don't have OP_CTV
or OP_CSV. I guess if the the key set used for HTLC #N is calculable given
any secret M>N (but not M<=N), and you always reveal secret MIN(current
active HTLC ids), then you just need to record the HTLC's index. You
could again allow for a small search though; you only have to calculate
the public key and hash the transaction against the calculated keys so
searching should still be somewhat cheap. So yeah, I think that makes
sense?
BTW, 10 commitments per second (per channel) doesn't sound /that/ high
volume :) Pay per megabyte for an end user at 100Mb/s is already
around that at least at peak times, eg.
Cheers,
aj