📅 Original date posted:2020-02-03
📝 Original message:
> (I'm seeking a clever way that Bob can assign them and trivially tell
> which ID is assigned to which peer, but I can't figure it out, so I
> guess Bob keeps a mapping and restricts each peer to 256 live scids?).
Hi Rusty.
Here's a potential way for Alice and Bob to agree a set of 256 scids without any additional messages or changes to existing messages beyond a feature flag and a flag in open_channel, but comes with a computational cost.
Alice and Bob agree on a random integer `r`. This could be negotiated on `open_channel`, but we shouldn't need to send additional information because we already have a random integer we can use: the `temporary_channel_id`. This is not known to anybody besides Alice and Bob.
When a channel is locked, Bob computes n=256 scids, using something approximating `concat(n, trunc_bytes(sha256(ec_mult(2^n*r, Q)), 7))`, where `Q` is Alice's public key for the channel funding transaction.
The chance of scid collisions between channels is 2^56, which is probably no cause for concern.
Instead of keeping a map of 256 scids for each channel, Bob can use a cuckoo filter for efficiency. The filter can be used for a quick membership test and also as an associative map from scids to channels. It can also support scid deletion in the event of channel closure (at the cost of recomputing 256 ec_mults again).
So when Bob receives a new HTLC to forward, he tests it against his cuckoo filter and retreives a candidate set of possible channels to which it may refer. For each channel, he takes the most significant byte of the scid as `m` and performs `trunc_bytes(sha256(ec_mult(2^m*r, Q)), 7)` and tests the least-significant 7 bytes of the result against the scid.
Alice does not need to keep all of the scids she may use for invoices because they can be computed on the fly, but she will need to keep a copy of the `temporary_channel_id`.
In the reverse direction of Alice forwarding HTLCs to Bob, Bob's public key for the funding transaction is used instead.
Regards,
Mark Holden
m.a.holden [ARCHIVE] /
npub1ck…pxq6d
2023-06-09 12:58:31
in reply to nevent1q…jnma
Author Public Key
npub1ckky60snl9kapavqar0utymcyn7ngvmtqaxr7rpgch9ps6wx3wwqypxq6dPublished at
2023-06-09 12:58:31Event JSON
{
"id": "a98ecd3b5e374e0bd7a82422f4e15c971f4a44c325f3f7be6c79270332d2990d",
"pubkey": "c5ac4d3e13f96dd0f580e8dfc5937824fd34336b074c3f0c28c5ca1869c68b9c",
"created_at": 1686315511,
"kind": 1,
"tags": [
[
"e",
"3ed35742512a6038c8a47910d5915af4fefd8766015db6ab01e4ef19d4ac6fff",
"",
"root"
],
[
"e",
"815e56ad0606949b09cae99342de7cd2c03680264a9530f10ae786fc3f1b7328",
"",
"reply"
],
[
"p",
"4505072744a9d3e490af9262bfe38e6ee5338a77177b565b6b37730b63a7b861"
]
],
"content": "📅 Original date posted:2020-02-03\n📝 Original message:\n\u003e (I'm seeking a clever way that Bob can assign them and trivially tell\n\u003e which ID is assigned to which peer, but I can't figure it out, so I\n\u003e guess Bob keeps a mapping and restricts each peer to 256 live scids?).\n\nHi Rusty.\n\nHere's a potential way for Alice and Bob to agree a set of 256 scids without any additional messages or changes to existing messages beyond a feature flag and a flag in open_channel, but comes with a computational cost.\n\nAlice and Bob agree on a random integer `r`. This could be negotiated on `open_channel`, but we shouldn't need to send additional information because we already have a random integer we can use: the `temporary_channel_id`. This is not known to anybody besides Alice and Bob.\n\nWhen a channel is locked, Bob computes n=256 scids, using something approximating `concat(n, trunc_bytes(sha256(ec_mult(2^n*r, Q)), 7))`, where `Q` is Alice's public key for the channel funding transaction.\n\nThe chance of scid collisions between channels is 2^56, which is probably no cause for concern.\n\nInstead of keeping a map of 256 scids for each channel, Bob can use a cuckoo filter for efficiency. The filter can be used for a quick membership test and also as an associative map from scids to channels. It can also support scid deletion in the event of channel closure (at the cost of recomputing 256 ec_mults again).\n\nSo when Bob receives a new HTLC to forward, he tests it against his cuckoo filter and retreives a candidate set of possible channels to which it may refer. For each channel, he takes the most significant byte of the scid as `m` and performs `trunc_bytes(sha256(ec_mult(2^m*r, Q)), 7)` and tests the least-significant 7 bytes of the result against the scid.\n\nAlice does not need to keep all of the scids she may use for invoices because they can be computed on the fly, but she will need to keep a copy of the `temporary_channel_id`.\n\nIn the reverse direction of Alice forwarding HTLCs to Bob, Bob's public key for the funding transaction is used instead.\n\nRegards,\nMark Holden",
"sig": "07e92a853996e29dadab2c224ac211092114e5487a1daa47e8b99486a34d9aca00c2ff0abfee03cd5a4fb636f8511ab497ca65bae079de117522191d126af7a3"
}