Jim Posen [ARCHIVE]

⚠️ This account is not associated with a real person. It's an archival account for mailing list messages.
🗓️ Active from 2017-12-11 to 2019-04-04
💬 Posted a total of 56 messages
📚 Participated in the following categories: bitcoin-dev, Lightning-dev
🔇 Please do not DM this user as it's used for archive purposes only.

Public Key

npub1ncnj8arudstdxzfhxk7k4nwgkrw3hyw8sgt0wqqmm5hh2c4knmgs2lqt2n

Profile Code

nprofile1qqsfufer737xc9knpymnt0t2ehytphgmj8rcy9hhqqda6tm4v2mfa5gprpmhxue69uhhyetvv9ujumn0wdmksetjv5hxxmmdqyt8wumn8ghj7un9d3shjtnwdaehgu3wvfskuequ6jcmp

Publishing to

relay.noswhere.com

relay.nostr.band

Author Public Key

npub1ncnj8arudstdxzfhxk7k4nwgkrw3hyw8sgt0wqqmm5hh2c4knmgs2lqt2n

Show more details

Last Notes

2023-06-09 12:52:18

- reply

📅 Original date posted:2018-11-08
📝 Original message:
Thanks for proposing this! I think it is absolutely one of the biggest
onboarding/usability challenges for many use cases.
My first thought is that like ZmnSCPxj mentioned, the person offering
liquidity can simply close the channel. So if I'm charging for liquidity,
I'd actually want to charge for the amount (in mSAT/BTC) times time. So
like 1 mSAT per satoshi of bandwidth per hour or something like that. I
don't think there's a perfect way of enforcing this at the protocol layer,
but maybe you could lock up the fees in channel reserve which decreases
over time and gets donated to miners on an early close?
Instead of a flat payment for liquidity, I've considered in the past a
model where you pre-pay on fees. So if I'm a large merchant and I expect to
be receiving lots of volume in payments, it is totally rational for you to
put up liquidity opening a channel to me because you will earn fees on
payments routed to me through that channel. So what I could do to convince
you is to say, "I expect if you open a 1 BTC channel to me, you will earn
at least 10 mSAT per minute in routing fees. And if you don't I'll cover
the difference." So every minute, I'll pay you 10 mSAT up front, then for
all HTLCs that come through the channel to me up to that limit, you'll
forward the fees onto me as reimbursement. I don't think this protocol is
any less vulnerable to attacks, but perhaps aligns incentives better?
My other concern with this sort of proposal is that it makes it easier to
perform HTLC withholding/loop attacks, which are executed by the receiving
end of a circuit. Currently on the network, there's a nice built-in
protection that it's not obvious how to convince victim to open a channel
to you. This is probably something that should get dealt with separately,
but part of me doubts that it'll be possible to create a liquidity market
without factoring in reputation.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20181107/44263e78/attachment.html>

2023-06-09 12:50:29

- reply

📅 Original date posted:2018-05-18
📝 Original message:
Yes Rusty, you are correct that an attacker still gets leverage on their
ability to destroy reputation unless the loss rates increase exponentially.
And I agree that would be a very steep increase, serving do decrease
circuit lengths dramatically. The reasoning for the linear increase in
reputation loss comes from viewing reputation loss as compensation for
time-value lost in locked HTLCs. In a sense, every node pays in reputation
for all of the time-value locked in HTLCs upstream from them in proportion
to the value assigned to it by the owners of the funds.
I'm not sure whether this would be an acceptable way of pricing payment
delays, though I do think it is important to make attackers pay for the
resources they are wasting on the network in some form.
On Fri, May 18, 2018 at 4:38 PM, ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> Good morning Rusty,
>
>
> > Also, you talked about reputation_loss_rate as being a private per-node
> >
> > thing, and being an explicit thing in the HTLC. I'm ignoring the
> >
> > former, and assuming the latter.
>
> Reputation (the score) is a private per-node thing, while the
> `reputation_loss_rate` is explicit in the HTLC.
>
> I am uncertain how that changes your analysis, though. In a line network
> like you showed, the reputation "bins" are Node1->Node2 and Node2->Node1
> and so on. It may be more useful to think of the reputation bins as
> assigned to half-chans than to nodes.
>
> So the initial Mallory3->Node18->Mallory2 gives high reputation to
> half-chans Node18->Mallory3 and Node18->Mallory2, then sacrifices the
> Node18->Mallory3 reputation to destroy the NodeN -> NodeN+1 and
> NodeN+1->NodeN reputations.
>
> Along that line, reputation lost is higher as N increases. Graphing
> reputation lost along that line, we form a triangle, and the area of the
> triangle is the total reputation destroyed. Only the length of one edge of
> the triangle is what is lost by the Node18->Mallory3 reputation score. So
> yes, it seems you are correct here.
>
> Regards,
> ZmnSCPxj
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180518/f341c9c4/attachment.html>

2023-06-09 12:50:28

- reply

📅 Original date posted:2018-05-15
📝 Original message:
>
> This can still be manipulated if Rusty1 opens a direct channel to Jim.
> Then Rusty1 can route payments Rusty1->Jim->Rusty2 that succeed quickly,
> then route payments Rusty1->ZmnSCPxj->Jim->Rusty2 that stall. Thus Rusty2
> can have the Jim->Rusty2 reputation boosted, while alternating with
> reputation losses that make ZmnSCPxj->Jim reputation go down. Since local
> reputation is used, ZmnSCPxj and Jim will not talk to each other about how
> Rusty2 seems to stall when not routing a payment from Rusty1. Rusty1 can
> now manipulate the reputation view of ZmnSCPxj and Jim of each other while
> keeping Rusty2 reputation somewhat high.
>
Yes, you are correct that in scenarios like this an attacker can pay to
degrade the reputation of one of its peers (or even nodes further away).
The key point is that doing so should be costly to the attacker because
they must pay the victim node to continue making itself vulnerable to
payment delays. But if the node is getting compensated, is that really an
attack then? This system is designed with the assumption that the best way
to defend an anonymous/decentralized network that allows sybils is by
pricing resource utilization appropriately. In a similar way, the Bitcoin
blockchain is "vulnerable" to spam attacks in the sense that attackers can
pay to fill up block space.
> As mentioned, the CLTV total leaks information on how far the payee is. I
> might decide to keep track of a reputation score, not of the local peers I
> have, but on the entire network. If the CLTV total at my outgoing is high,
> then if the outgoing HTLC takes a long time to respond, I will distribute a
> small reputation loss to a large number of nodes that are accessible from
> the outgoing channel; if the CLTV total at my outgoing is low, I will
> distribute a large reputation loss to a small number of nodes that are
> accessible from the outgoing channel. I now have the incentive to make
> this estimation even more accurate in the future.
>
One could do this today. I'd even argue that they are incentivized to
already as a protection against loop attacks/payment delays. But it's
likely a pretty ineffective strategy depending on the number of channels
that the possible downstream hops have open.
Please describe the below:
>
> 1. Behavior if payment succeeds after T time.
> 2. Behavior if payment fails after T time.
>
> It seems you only described "Behavior if payment succeeds after T time".
>
Ah, sorry if I didn't make that clear. The reputation is increased in the
case of successful payments by the fee collected. The reputation is
decreased on the downstream peer proportional to time T *regardless* of
whether the payment succeeds or fails. If a payment succeeds quickly, the
increase should outweigh the decrease, but if the payment succeeds after a
long time, the change in reputation may be net negative. If the payment
fails, the upstream peer's reputation does not change and the downstream
peer's reputation always decreases proportional to time T.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180515/755f6eaf/attachment-0001.html>

2023-06-09 12:50:27

- reply

📅 Original date posted:2018-05-15
📝 Original message:
>
> You're forgetting the failure cases, where now I can profit.
>
> If I disconnect from another node, I now have a disincentive to tell
> others. At the moment we send an update disabling the channel (though
> we should give a few seconds for reconnect first, but whatever).
>
> Similarly, the rewards aren't proportional: being cheaper than other
> routes gets you all the traffic, but now you profit even if you can't
> service the payments. In fact, once a channel becomes hard to use (low
> capacity, transient disconnect, whatever), I *should* advertize it as
> cheaper route than anyone else: free money!
>
> I'm sure there are other ways to game it, but the underlying reason is
> clear: it misaligns user and node incentives.
If the system is sufficiently decentralized, managing to cheat everyone
> once is very profitable though.
>
I still don't agree with the conclusion.
What are the incentives currently for a node to advertise disabled
channels? Firstly, it reduces computational effort of performing an
unnecessary channel update. The main incentive though is that it is the
recommended spec compliant behavior, and makes the link appear more
reliable to the sender. I think this has to be analyzed as a repeated game,
where senders will prefer links that not only advertise lower fees, but
have a history of being reliable (or at least don't have a history of being
unreliable). So with a fee of 0 on failed payments, we think that there's
probably sufficient reason for nodes to advertise when channels are
disabled. I'll grant, obviously, that if that there is high fee on failed
payments that it would create incentive problems, but not if the
unconditional fee is low enough. Note also the unconditional fee is also
visible to senders, who will choose not to route through such links for
this exact reason. So your example of a node advertising cheap fees on
disabled links, it would only make sense to lower the success-conditional
fee, not the unconditional fee. Ultimately, I think this will reach an
equilibrium assuming senders have good route selection algorithms.
Now, that said, if this unconditional fee were the only (or even main)
protection against loop attacks, it would probably require them to be so
high as to create incentive problems. I am proposing the unconditional fee
as a spam fee to punish senders who just send a bunch of failing payments
in order to collect routing information, and put load on the network in the
process for no good reason. With this as the purpose, I think this
unconditional spam fee can be low enough to avoid the issues you raise.
One of my beliefs in structuring incentives it that it's far more
acceptable for senders to get cheated by nodes they route through than for
routers to be attacked. The reason is that senders collect a lot more
information in failure cases and can avoid repeated occurrences by
selecting routes differently. Routers, on the other hand, have far more
limited information and choices and their operation is critical to the
efficiency and decentralization of the system, so they should be protected
by the protocol to a greater degree.
> But I can make you look like a delaying node whenever I want. The only
> way to ensure that I lose more reputation than you do is to leak
> information about route length for *everyone*. And even then, it's just
> a matter of numbers. I can make successful payments to myself through
> the same peers (but not you!) to stay above their threshold so my
> reputation is intact.
>
> So it's basically a question of how expensive is it for me to throw you
> off the network? You have to tune that number carefully.
>
Remember, reputation is local to each node, so the only way you can raise
your reputation with me is by participating in successful circuits *with
me*. If you route successful payments on circuits with other peers, you may
raise your reputation with them, but will do nothing to convince me to send
more payments through you. So it is not true that you can make me look like
a delaying node whenever you want; after a few bad interactions, I will
stop routing through you until you participate in enough successful
payments *with me* as the downstream to earn back your reputation.
I agree this number needs to be tuned carefully, but ideally this (the
reputation rate loss) is something that can be tuned individually by
routers according to their risk tolerance and history of attacks on the
network. I think it's far preferable to have a number that can be tuned in
the face of DoS attacks than being caught with no protection whatsoever.
But we're busy trying to remove all the methods of deanonymizing the
> network, and you seem to be adding a new one, *and* providing an
> incentive to deanonymize.
>
> Yes, which is why we have mitigations in place (which are still probably
> insufficient). I really don't want to add another vector.
>
This gets to the heart of the tradeoff between network efficiency and
privacy. I admit that my proposal sacrifices on privacy, and I personally
find it acceptable given the added protection against DoS attacks, but I
understand the counterargument as well.
One additional thing to consider, though, is that if DoS attacks are
problematic and there is no protection, many nodes may stop routing
payments entirely. Onion routing through a network with very few possible
circuits certainly is less private than revealing additional circuit
information on a decentralized routing network.
> So now I'll try to deanonymize all payments so I can determine this.
> Those who do this best will be rewarded, and those who don't try will be
> knocked off the network, probably by those who can!
>
I'm not following, how are you deanonymizing payments? Having more
information about downstream hops can help one make better routing
decisions, but if the reputation system works properly, you should only
need to care about the reputation of the next hop.
> So I'd like to see a real design of the reputation system. If it's
> practical (which is a significant hurdle), we then need to carefully
> evaluate whether we're creating significant disincentives to
> neighbourliness.
>
I tried to mostly describe the design in the first email, but it's kind of
disorganized. I'll try to sketch it out here more succinctly.
Each node has a local configuration of its "reputation loss rate" per
channel in units of Hz. This configured rate is not explicitly advertised
to peers. Each update_add_htlc has an additional field the "reputation loss
rate" in units of satoshis per second, calculated as the reputation loss
rate of the upstream HTLC plus the local reputation loss rate times the
offered HTLC value. This value can be obfuscated somewhat by the origin of
the payment and at each hop with some amount of noise, subject to the
concerns raised in my discussion with ZmnSCPxj. When forwarding an HTLC,
the upstream hop measures the elapsed time between delivery of a commitment
signature on the add and receipt of the fail/update.
For each peer node, keep a reputation score in units of satoshis. For each
peer, when a payment completes where they are the upstream or downstream
hop, add the amount collected in fees to their reputation score. For each
payment where they are the downstream hop, subtract from their reputation
score the reputation loss rate on the offered HTLC times its elapsed time.
Reputation score is not explicitly shared between peered nodes, but can be
estimated to within differences in elapsed time measurements.
When you receive an HTLC to be forwarded to some downstream node, compare
their current reputation score with the offered reputation loss rate times
10 minutes times the CLTV on the HTLC. If their reputation is sufficient,
forward the HTLC and place a hold on their total reputation for that amount
(so that concurrently forwarded HTLCs can't exceed their reputation
"balance"). New, unknown, peers should get some initial reputation,
presumably greater for channels that one initiates vs channels one receives.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180515/35dedefc/attachment-0001.html>

2023-06-09 12:50:26

- reply

📅 Original date posted:2018-05-10
📝 Original message:
Hmm, I'm not quite following the situation. What do you mean by "directs
normal traffic"? Since the sender constructs the entire circuit, routing
nodes do not get any discretion over which nodes to forward a payment to,
only whether to forward or fail. What an attacker could do is perform a
loop attack and send a payment to another node that they control and delay
the payment on the receiving end. Note that the sending node loses no
reputation, only the receiving node. Since the hops being attacked are the
ones in the middle and they are faithfully enforcing the reputation
protocol, the receiving node's reputation should be penalized properly,
making it unlikely the attack will succeed in a second attempt.
On Thu, May 10, 2018 at 2:56 PM, Chris Gough <christopher.d.gough at gmail.com>
wrote:
> hello, I'm a curious lurker trying to follow this conversation:
>
> On Thu, 10 May 2018, 2:40 pm ZmnSCPxj via Lightning-dev, <
> lightning-dev at lists.linuxfoundation.org> wrote:
>
>>
>> The concern however is that the CLTV already partly leaks the distance
>> from the payee, whereas the reputation-loss-rate leaks distance from the
>> payer. It is often not interesting to know that some entity is getting
>> paid, but it probably far more interesting to know WHO paid WHO, so leaking
>> both distances simultaneously is more than twice as worse as leaking just
>> one distance.
>>
>
> Consider an asymetrically-resourced malevolent node that wants the ability
> to harm a specific small nodes without aquiring a bad reputation (and is
> willing to pay for it). In preparation, this bad boss node directs normal
> traffic to sacrificial nodes they control, while understating the
> reputation-risk (truthfully as it turns out, because they have out of band
> influence over the node). When the time comes, the sacrificial node
> inflicts delay on the victim node and they both suffer, while the boss
> keeps her nose clean.
>
> Is it the case that understating risk of legitimate traffic from boss node
> to sacrificial node effectively allows transfer of reputation to the
> sacrificial node in preparation for attack, while at the same time
> obscuring their association?
>
> Chris Gough
>
>>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180510/e6ddf135/attachment.html>

2023-06-09 12:50:03

- reply

📅 Original date posted:2018-04-12
📝 Original message:
As specified in BOLT 3, in the commitment transactions the to_local output
is time-locked with OP_CSV while the to_remote is a simple P2WPKH. The
to_local output must be time-locked in order to allow the other party to
come online and sweep funds from a published revoked commitment. In the
case of an honest unilateral close, however, this wastes the time-value of
capital locked in the channel for the publisher but not the other party.
This seems to create perverse incentives where a party that goes offline
and forces a unilateral close is not penalized and only the party that
broadcasts is. I see this as a problem in both normal operation and attack
scenarios. Consider cases where the peer is misbehaving and the node needs
to broadcast to chain. Concretely, consider a case where the other party
does not send an update_fail_htlc after it expires. A rational node might
decide to just become unresponsive instead of broadcasting the commitment
in the hopes that the other party publishes instead. Or if the value of the
HTLC is sufficient, it would want to claim the time-locked output ASAP in
which case the misbehaving peer is not punished and gets access to its
funds immediately.
I find it easier to analyze the game theory of these situations if the
to_remote output is also time-locked by the to_remote_delay. Making the
consequence of an on-chain settlement symmetric changes the game from
chicken [1] to a tragedy of the commons [2]. I'm curious how other people
think about this.
-jimpo
[1] https://en.wikipedia.org/wiki/Chicken_(game)
[2] https://en.wikipedia.org/wiki/Tragedy_of_the_commons
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180412/18ef498c/attachment.html>

2023-06-09 12:49:18

- reply

📅 Original date posted:2018-03-02
📝 Original message:
Regarding ping flooding, if it is problematic, the best solution is
probably including a small proof-of-work with the ping, similar to BIP 154.
However, the whole purpose of the ping in the first place is to be a
cheaper way to collect routing information than attempting to send a
payment, so I think adding a PoW starts to become counterproductive. Note
that the sender needs to expend a certain amount of computation just
creating the onion packet up front (on the order of a few ms, I believe),
so perhaps that is sufficient.
Also, if someone wanted to DoS the network, there are much better ways than
using this proposed ping mechanism. For example, someone can send payments
along any circuit with a randomly generated payment hash (for which the
preimage is unknown), and force a payment failure at the end of the route.
That is basically a way to ping that works now, but is more expensive for
everyone.
On Thu, Mar 1, 2018 at 4:16 PM, gb <kiwigb at yahoo.com> wrote:
> .... and any thoughts on protections against flood pinging?
>
> On Thu, 2018-03-01 at 09:45 -0500, Jim Posen wrote:
>
>
> > The main benefit is that this should make it quicker to send a
> > successful payment because latency is lower than sending an actual
> > payment and the sender could ping all possible routes in parallel,
> > whereas they can't send multiple payments in parallel. The main
> > downside I can think of is that, by the same token, it is faster and
> > cheaper for someone to extract information about channel capacities on
> > the network with a binary search.
> >
> >
> > -jimpo
> > _______________________________________________
> > Lightning-dev mailing list
> > Lightning-dev at lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180302/e1a8e668/attachment.html>

2023-06-09 12:49:17

- reply

📅 Original date posted:2018-03-01
📝 Original message:
My understanding is that the best strategy for choosing a route to send
funds over is to determine all possible routes, rank them by estimated fees
based on channel announcements and number of hops, then try them
successively until one works.
It seems inefficient to me to actually do a full HTLC commitment handshake
on each hop just to find out that the last hop in the route didn't have
sufficient remaining capacity in the first place. Depending on how many
people are using the network, I could also forsee situations where this
creates more payment failures because bandwidth is locked up in HTLCs that
are about to fail anyway.
One idea that would likely help is the ability to send a ping over an onion
route asking "does every hop have capacity to send X msat?" Every hop would
forward the onion request if the answer is yes, or immediately send the
response back up the circuit if the answer is no. This should reveal no
additional information about the channel capacities that the sender
couldn't determine by sending a test payment to themself (assuming they
could find a loop). Additionally, the hops could respond with the latest
fee rate in case channel updates are slow to propagate.
The main benefit is that this should make it quicker to send a successful
payment because latency is lower than sending an actual payment and the
sender could ping all possible routes in parallel, whereas they can't send
multiple payments in parallel. The main downside I can think of is that, by
the same token, it is faster and cheaper for someone to extract information
about channel capacities on the network with a binary search.
-jimpo
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180301/55533bfa/attachment.html>

2023-06-09 12:49:00

- reply

📅 Original date posted:2018-02-08
📝 Original message:
If using two hashes to deliver the payment while still getting a proof, I'm
not sure what that provides above just sending regular lightning payments
over multiple routes with one hash. Firstly, if there is a second hash, it
would presumably be the same for all routes, making them linkable again,
which AMP tries to solve. And secondly, the receiver has no incentive to
claim any of the HTLCs before all of them are locked in, because in that
case they are releasing the transaction receipt before fully being paid.
On Thu, Feb 8, 2018 at 8:41 AM, Johan Torås Halseth <johanth at gmail.com>
wrote:
> An obvious way to make this compatible with proof-of-payment would be to
> require two hashes to claim the HTLC: the presage from the invoice payment
> hash (as today) + the new hash introduced here. This would give the sender
> a receipt after only one of the HTLCs was claimed. Would require changes to
> the scripts of course.
>
> With Schnorr/EC operations this could probably be made more elegant, as
> mentioned.
>
> - Johan
> On Wed, Feb 7, 2018 at 18:21, Rusty Russell <rusty at rustcorp.com.au> wrote:
>
> Olaoluwa Osuntokun <laolu32 at gmail.com> writes:
> > Hi Y'all,
> >
> > A common question I've seen concerning Lightning is: "I have five $2
> > channels, is it possible for me to *atomically* send $6 to fulfill a
> > payment?". The answer to this question is "yes", provided that the
> receiver
>
> This is awesome! I'm kicking myself for not proposing it :)
>
> Unfortunately, your proposal defines a way to make multipath donations,
> not multipath payments :(
>
> In other words, you've lost proof of payment, which IMHO is critical.
>
> Fortunately, this can be fairly trivially fixed when we go to scriptless
> scripts or other equivalent decorrelation mechanism, when I think this
> mechanism becomes extremely powerful.
>
> > - Potential fee savings for larger payments, contingent on there being a
> > super-linear component to routed fees. It's possible that with
> > modifications to the fee schedule, it's actually *cheaper* to send
> > payments over multiple flows rather than one giant flow.
>
> This is a stretch. I'd stick with the increased reliability/privacy
> arguments which are overwhelmingly compelling IMHO.
>
> If I have any important feedback on deeper reading (and after a sccond
> coffee), I'll send a separate email.
>
> Thanks!
> Rusty.
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180208/31041639/attachment.html>

2023-06-09 12:48:59

- reply

📅 Original date posted:2018-02-07
📝 Original message:
This is a really neat idea.
This is a question about non-interactive payments in general, but is there
any way to get a proof of payment? With regular invoices, knowledge of the
preimage serves as cryptographic proof that the payment was delivered.
On Feb 6, 2018 6:26 PM, "Conner Fromknecht" <conner at lightning.engineering>
wrote:
>
> Hi ZmnSCPxj and Laolu,
>
> > Indeed, the existence of per-hop fees (`fee_base_msat`) means,
> splitting the
> > payment over multiple flows will be, very likely, more expensive,
> compared to
> > using a single flow.
>
> As Laolu pointed out, we have yet to see how fees evolve on mainnet or
> what will
> emerge as a sane, default fee schedules. I agree that if the same
> proportional
> fee is used across all partial payments, then it could certainly be more
> expensive.
>
> However, it could also be the case that you were paying a needlessly high
> proportional fee to begin with, because paths of sufficient capacity to the
> destination were scarce. In an AMP world, there will be an abundance of
> channels
> that can route small, partial payments, which may itself drive down the
> competitive fee rate for smaller payments. Just a hypothesis, we shall see
> where
> supply meets demand!
>
> At the end of the day, the user can always fall back to regular payment if
> they
> expect to end up paying more fees using an AMP.
>
> > (If we want to support multiple routes converging to an intermediate
> node,
> > then continue routing to a different final node after routes have merged
> (i.e.
> > A->B->C->D, and A->E->C->D, with the payment being merged by C, who
> forwards
> > the combination to D), then we need to follow the current hop data
> format, but
> > I think supporting AMP at final payees is actually enough...
>
> I think this is an interesting idea, sounds maybe like a
> recursive/hierarchical
> AMP? The ability to merge the payments seems like it would result in a
> decent privacy
> leak, as I believe an intermediary would have enough evidence to prove
> that two
> payments were merged/correlated. Simple traffic analysis would also reveal
> a
> discrepancy in the number of incoming and outgoing packets, and possibly
> other
> observable differences in routing (some) AMPs vs regular payments.
>
> FWIW the current proposal allows the paths of partial payments to overlap,
> in such a scenario C would just forward the HTLCs independently. One could
> send
> them all along the same path if they desired! I'm assuming the intent here
> is to
> try and reduce total fees?
>
> Minor correction^2:
>
> > This should actually be (H(s_0 || s_1 || ...), s_i).
>
> This assumes the receiver knows the indexes of each share. Without this
> knowledge they would have to brute force all orderings to check the
> fingerprint.
>
> To maintain order invariance on the receiving end, I would propose sending
> (0, s_i) for the first n-1 partial payments, and then (n, s_i) on the
> final one.
> As in the description of the basic AMP scheme, the receiver maintains a
> persistent count of how many partial payments have been received for ID.
> If the
> receiver does not get the last payment last, the receiver just waits until
> all n
> have been received before deciding that its reconstructed value is BP.
>
> The receiver can verify they've received the correct BP and n by
> rederiving the
> partial preimages r_i = H(BP || i) and checking that there are n
> outstanding
> payments, one for each h_i = H(r_i). This also saves the receiving node n
> additional hash invocations.
>
> -Conner
>
> On Tue, Feb 6, 2018 at 4:04 PM Olaoluwa Osuntokun <laolu32 at gmail.com>
> wrote:
>
>> Hi ZmnSCPxj,
>>
>> > This is excellent work!
>>
>> Thanks!
>>
>> > I think, a `globalfeatures` odd bit could be used for this. As it is
>> > end-ot-end, `localfeatures` is not appropriate.
>>
>> Yep, it would need to be a global feature bit. In the case that we're
>> sending to a destination which isn't publicly advertised, then perhaps an
>> extension to BOLT-11 could be made to signal receiver support.
>>
>> > I believe, currently, fees have not this super-linear component
>>
>> Yep they don't. Arguably, we should also have a component that scales
>> according to the proposed CLTV value of the outgoing HTLC. At Scaling
>> Bitcoin Stanford, Aviv Zohar gave a talked titled "How to Charge
>> Lightning"
>> where the authors analyzed the possible evolution of fees on the network
>> (and also suggested adding this super-linear component to extend the
>> lifetime of channels). However, the talk itself focused on a very simple
>> "mega super duper hub" topology. Towards the end he alluded to a
>> forthcoming
>> paper that had more comprehensive analysis of more complex topologies. I
>> look forward to the publication of their finalized work.
>>
>> > Indeed, the existence of per-hop fees (`fee_base_msat`) means, splitting
>> > the payment over multiple flows will be, very likely, more expensive,
>> > compared to using a single flow.
>>
>> Well it's still to be seen how the fee structure on mainnet emerges once
>> the
>> network is still fully bootstrapped. AFAIK, most running on mainnet atm
>> are
>> using the default fee schedules for their respective implementations. For
>> example, the default fee_base_msat for lnd is 1000 msat (1 satoshi).
>>
>> > I believe the `realm` byte is intended for this.
>>
>> The realm byte is meant to signal "forward this to the dogecoin channel".
>> ATM, we just default to 0 as "Bitcoin". However, the byte itself only
>> really
>> need significance between the sender and the intermediate node. So there
>> isn't necessarily pressure to have a globally synchronized set of realm
>> bytes.
>>
>> > Thus, you can route over nodes that are unaware of AMP, and only provide
>> > an AMP realm byte to the destination node, who, is able to reconstruct
>> this
>> > your AMP data as per your algorithm.
>>
>> Yes, the intermediate nodes don't need to be aware of the end-to-end
>> protocol. For the final hop, there are actually 53 free bytes (before one
>> needs to signal the existence of EOBs):
>>
>> * 1 byte realm
>> * 8 bytes next addr (all zeroes to signal final dest)
>> * 32 bytes hmac (also all zeroes for the final dest)
>> * 12 bytes padding
>>
>> So any combo of these bytes can be used to signal more advanced protocols
>> to
>> the final destination.
>>
>>
>> A correction from the prior email description:
>>
>> > We can further modify our usage of the per-hop payloads to send
>> > (H(BP), s_i) to consume most of the EOB sent from sender to receiver.
>>
>> This should actually be (H(s_0 || s_1 || ...), s_i). So we still allow
>> them
>> to check this finger print to see if they have all the final shares, but
>> don't allow them to preemptively pull all the payments.
>>
>>
>> -- Laolu
>>
>>
>> On Mon, Feb 5, 2018 at 11:12 PM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
>>
>>> Good morning Laolu,
>>>
>>> This is excellent work!
>>>
>>> Some minor comments...
>>>
>>>
>>> (Atomic Multi-path Payments). It can be experimented with on Lightning
>>> *today* with the addition of a new feature bit to gate this new
>>> feature. The beauty of the scheme is that it requires no fundamental
>>> changes
>>> to the protocol as is now, as the negotiation is strictly *end-to-end*
>>> between sender and receiver.
>>>
>>>
>>> I think, a `globalfeatures` odd bit could be used for this. As it is
>>> end-ot-end, `localfeatures` is not appropriate.
>>>
>>> - Potential fee savings for larger payments, contingent on there being
>>> a
>>> super-linear component to routed fees. It's possible that with
>>> modifications to the fee schedule, it's actually *cheaper* to send
>>> payments over multiple flows rather than one giant flow.
>>>
>>>
>>> I believe, currently, fees have not this super-linear component.
>>> Indeed, the existence of per-hop fees (`fee_base_msat`) means, splitting
>>> the payment over multiple flows will be, very likely, more expensive,
>>> compared to using a single flow. Tiny roundoffs in computing the
>>> proportional fees (`fee_proportional_millionths`) may make smaller
>>> flows give a slight fee advantage, but I think the multiplication of
>>> per-hop fees will dominate.
>>>
>>>
>>> - Using smaller payments increases the set of possible paths a partial
>>> payment could have taken, which reduces the effectiveness of static
>>> analysis techniques involving channel capacities and the plaintext
>>> values being forwarded.
>>>
>>>
>>> Strongly agree!
>>>
>>>
>>> In order to include the three tuple within the per-hop payload for the
>>> final
>>> destination, we repurpose the _first_ byte of the un-used padding bytes
>>> in
>>> the payload to signal version 0x01 of the AMP protocol (note this is a
>>> PoC
>>> outline, we would need to standardize signalling of these 12 bytes to
>>> support other protocols).
>>>
>>>
>>> I believe the `realm` byte is intended for this. Intermediate nodes do
>>> not need to understand realm bytes that are understood by other nodes in
>>> the route, including the realm bytes understood by the final destination,
>>> as intermediate nodes cannot, indeed, read the hop data of other nodes.
>>> Thus, you can route over nodes that are unaware of AMP, and only provide an
>>> AMP realm byte to the destination node, who, is able to reconstruct this
>>> your AMP data as per your algorithm.
>>>
>>> Indeed, the `realm` byte controls the interpretation of the rest of the
>>> 65-byte packet. If you define, instead, a separate `realm` that is
>>> understood by the destination node, you can redefine the entire 64 bytes of
>>> the final hop data as you wish.
>>>
>>> If we support AMP only at final payees, we can completely redefine the
>>> 64 bytes in the final hop data for the new AMP `realm`, and not consume the
>>> next hop (which would reduce route length by 1).
>>>
>>> (If we want to support multiple routes converging to an intermediate
>>> node, then continue routing to a different final node after routes have
>>> merged (i.e. A->B->C->D, and A->E->C->D, with the payment being merged by
>>> C, who forwards the combination to D), then we need to follow the current
>>> hop data format, but I think supporting AMP at final payees is actually
>>> enough... AMP at intermediate nodes might not be used often enough by
>>> senders for it to matter, as taking advantage of that seems more complex
>>> than just asking your routing algo to provide you multiple routes to a
>>> destination, which you are probably already doing)
>>>
>>> ----
>>>
>>> Overall, good work I think.
>>>
>>> Regards,
>>> ZmnSCPxj
>>>
>> _______________________________________________
>> Lightning-dev mailing list
>> Lightning-dev at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>>
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180207/48a507f8/attachment-0001.html>

2023-06-09 12:48:51

- reply

📅 Original date posted:2018-02-07
📝 Original message:
I like Christian's proposal of adding a simple announcement cutoff
timestamp with the intention of designing something more sophisticated
given more time.
I prefer the approach of having an optional feature bit signalling that a
`set_gossip_timestamp` message must be sent immediately after `init`, as
Laolu suggested. This way it doesn't conflict with and other possible
handshake extensions.
On Feb 7, 2018 9:50 AM, "Fabrice Drouin" <fabrice.drouin at acinq.fr> wrote:
Hi,
Suppose you partition nodes into 3 generic roles:
- payers: they mostly send payments, are typically small and operated
by end users, and are offline quite a lot
- relayers: they mostly relay payments, and would be online most of
the time (if they're too unreliable other nodes will eventually close
their channels with them)
- payees: they mostly receive payments, how often they can be online
is directly link to their particular mode of operations (since you
need to be online to receive payments)
Of course most nodes would play more or less all roles. However,
mobile nodes would probably be mostly "payers", and they have specific
properties:
- if they don't relay payments they don't have to be announced. There
could be millions of mobile nodes that would have no impact on the
size of the routing table
- it does not impact the network when they're offline
- but they need an accurate routing table. This is very different from
nodes who mostly relay or accept payements
- they would be connected to a very small number of nodes
- they would typically be online for just a few hours every day, but
could be stopped/paused/restarted many times a day
Laolu wrote:
> So I think the primary distinction between y'alls proposals is that
> cdecker's proposal focuses on eventually synchronizing all the set of
> _updates_, while Fabrice's proposal cares *only* about the newly created
> channels. It only cares about new channels as the rationale is that if
once
> tries to route over a channel with a state channel update for it, then
> you'll get an error with the latest update encapsulated.
If you have one filter per day and they don't match (because your peer
has channels that you missed, or
have been closed and you were not aware of it) then you will receive
all channel announcements for
this particular day, and the associated updates
Laolu wrote:
> I think he's actually proposing just a general update horizon in which
> vertexes+edges with a lower time stamp just shouldn't be set at all. In
the
> case of an old zombie channel which was resurrected, it would eventually
be
> re-propagated as the node on either end of the channel should broadcast a
> fresh update along with the original chan ann.
Yes but it could take a long time. It may be worse on testnet since it
seems that nodes
don't change their fees very often. "Payer nodes" need a good routing
table (as opposed
to "relayers" which could work without one if they never initiate payments)
Laolu wrote:
> This seems to assume that both nodes have a strongly synchronized view of
> the network. Otherwise, they'll fall back to sending everything that went
on
> during the entire epoch regularly. It also doesn't address the zombie
churn
> issue as they may eventually send you very old channels you'll have to
deal
> with (or discard).
Yes I agree that for nodes which have connections to a lot of peers,
strongly synchronized routing tables is
harder to achieve since a small change may invalidate an entire
bucket. Real queryable filters would be much
better, but worst case scenario is we've sent an additionnal 30 Kb or
o of sync messages.
(A very naive filter would be sort + pack all short ids for example)
But we focus on nodes which are connected to a very small number of
peers, and in this particular
case it is not an unrealistic expectation.
We have built a prototype and on testnet it works fairly well. I also
found nodes which have no direct
channel betweem them but produce the same filters for 75% of the
buckets ("produce" here means
that I opened a simple gossip connection to them, got their routing
table and used it to generate filters).
Laolu wrote:
> How far back would this go? Weeks, months, years?
Since forever :)
One filter per day for all annoucements that are older than now - 1
week (modulo 144)
One filter per block for recent announcements
>
> FWIW this approach optimizes for just learning of new channels instead of
> learning of the freshest state you haven't yet seen.
I'd say it optimizes the case where you are connected to very few
peers, and are online a few times every day (?)
>
> -- Laolu
>
>
> On Mon, Feb 5, 2018 at 7:08 AM Fabrice Drouin <fabrice.drouin at acinq.fr>
> wrote:
>>
>> Hi,
>>
>> On 5 February 2018 at 14:02, Christian Decker
>> <decker.christian at gmail.com> wrote:
>> > Hi everyone
>> >
>> > The feature bit is even, meaning that it is required from the peer,
>> > since we extend the `init` message itself, and a peer that does not
>> > support this feature would be unable to parse any future extensions to
>> > the `init` message. Alternatively we could create a new
>> > `set_gossip_timestamp` message that is only sent if both endpoints
>> > support this proposal, but that could result in duplicate messages
being
>> > delivered between the `init` and the `set_gossip_timestamp` message and
>> > it'd require additional messages.
>>
>> We chose the other aproach and propose to use an optional feature
>>
>> > The reason I'm using timestamp and not the blockheight in the short
>> > channel ID is that we already use the timestamp for pruning. In the
>> > blockheight based timestamp we might ignore channels that were created,
>> > then not announced or forgotten, and then later came back and are now
>> > stable.
>>
>> Just to be clear, you propose to use the timestamp of the most recent
>> channel updates to filter
>> the associated channel announcements ?
>>
>> > I hope this rather simple proposal is sufficient to fix the short-term
>> > issues we are facing with the initial sync, while we wait for a real
>> > sync protocol. It is definitely not meant to allow perfect
>> > synchronization of the topology between peers, but then again I don't
>> > believe that is strictly necessary to make the routing successful.
>> >
>> > Please let me know what you think, and I'd love to discuss Pierre's
>> > proposal as well.
>> >
>> > Cheers,
>> > Christian
>>
>> Our idea is to group channel announcements by "buckets", create a
>> filter for each bucket, exchange and use them to filter out channel
>> announcements.
>>
>> We would add a new `use_channel_announcement_filters` optional feature
>> bit (7 for example), and a new `channel_announcement_filters` message.
>>
>> When a node that supports channel announcement filters receives an
>> `init` message with the `use_channel_announcement_filters` bit set, it
>> sends back its channel filters.
>>
>> When a node that supports channel announcement filters receives
>> a`channel_announcement_filters` message, it uses it to filter channel
>> announcements (and, implicitly ,channel updates) before sending them.
>>
>> The filters we have in mind are simple:
>> - Sort announcements by short channel id
>> - Compute a marker height, which is `144 * ((now - 7 * 144) / 144)`
>> (we round to multiples of 144 to make sync easier)
>> - Group channel announcements that were created before this marker by
>> groups of 144 blocks
>> - Group channel announcements that were created after this marker by
>> groups of 1 block
>> - For each group, sort and concatenate all channel announcements short
>> channel ids and hash the result (we could use sha256, or the first 16
>> bytes of the sha256 hash)
>>
>> The new `channel_announcement_filters` would then be a list of
>> (height, hash) pairs ordered by increasing heights.
>>
>> This implies that implementation can easily sort announcements by
>> short channel id, which should not be very difficult.
>> An additional step could be to send all short channel ids for all
>> groups for which the group hash did not match. Alternatively we could
>> use smarter filters
>>
>> The use case we have in mind is mobile nodes, or more generally nodes
>> which are often offline and need to resync very often.
>>
>> Cheers,
>> Fabrice
>> _______________________________________________
>> Lightning-dev mailing list
>> Lightning-dev at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
_______________________________________________
Lightning-dev mailing list
Lightning-dev at lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180207/cb4ed693/attachment-0001.html>

2023-06-07 18:17:27

- reply

📅 Original date posted:2019-04-03
📝 Original message:Big Concept ACK. I think this would be one of the biggest usability
improvements for Bitcoin and I see no security issues with the assumevalid
approach. I also agree that it's important to start work on this even
before the ultimate, perfect accumulator has been designed/tested and the
commitment scheme can always be upgraded later on. assumeutxo syncing
actually seems pretty orthogonal to the accumulator research.
I have a few questions
- So any nodes that do an initial sync will stop at the assumeutxo height,
serialize a snapshot of the chain state and store it? How many nodes are
expected to do this? Any idea how long this takes? Should it be enabled by
default?
- Would pruned nodes still download all historic blocks to double-check the
snapshot or only full nodes that intend to serve block data?
- How long are old snapshots retained? Presumably during a new release
nodes should keep at least a version back. Without P2P signalling of which
snapshots are available, they maybe have to keep all old snapshots or even
download old ones.
and comments
- The snapshot should probably be chunked up to minimize the amount of
bandwidth/IO/memory a malicious node could waste before you realize. Also,
it would make parallel downloading easier.
On Tue, Apr 2, 2019 at 4:43 PM James O'Beirne via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Hi,
>
> I'd like to discuss assumeutxo, which is an appealing and simple
> optimization in the spirit of assumevalid[0].
>
> # Motivation
>
> To start a fully validating bitcoin client from scratch, that client
> currently
> needs to perform an initial block download. To the surprise of no one, IBD
> takes a linear amount time based on the length of the chain's history. For
> clients running on modest hardware under limited bandwidth constraints,
> say a mobile device, completing IBD takes a considerable amount of time
> and thus poses serious usability challenges.
>
> As a result, having fully validating clients run on such hardware is rare
> and
> basically unrealistic. Clients with even moderate resource constraints
> are encouraged to rely on the SPV trust model. Though we have promising
> improvements to existing SPV modes pending deployment[1], it's worth
> thinking about a mechanism that would allow such clients to use trust
> models closer to full validation.
>
> The subject of this mail is a proposal for a complementary alternative to
> SPV
> modes, and which is in the spirit of an existing default, `assumevalid`.
> It may
> help modest clients transact under a security model that closely resembles
> full validation within minutes instead of hours or days.
>
> # assumeutxo
>
> The basic idea is to allow nodes to initialize using a serialized version
> of the
> UTXO set rendered by another node at some predetermined height. The
> initializing node syncs the headers chain from the network, then obtains
> and
> loads one of these UTXO snapshots (i.e. a serialized version of the UTXO
> set
> bundled with the block header indicating its "base" and some other
> metadata).
>
> Based upon the snapshot, the node is able to quickly reconstruct its
> chainstate,
> and compares a hash of the resulting UTXO set to a preordained hash
> hard-coded
> in the software a la assumevalid. This all takes ~23 minutes, not
> accounting for
> download of the 3.2GB snapshot[2].
>
> The node then syncs to the network tip and afterwards begins a simultaneous
> background validation (i.e., a conventional IBD) up to the base height of
> the
> snapshot in order to achieve full validation. Crucially, even while the
> background validation is happening the node can validate incoming blocks
> and
> transact with the benefit of the full (assumed-valid) UTXO set.
>
> Snapshots could be obtained from multiple separate peers in the same
> manner as
> block download, but I haven't put much thought into this. In concept it
> doesn't
> matter too much where the snapshots come from since their validity is
> determined via content hash.
>
> # Security
>
> Obviously there are some security implications due consideration. While
> this
> proposal is in the spirit of assumevalid, practical attacks may become
> easier.
> Under assumevalid, a user can be tricked into transacting under a false
> history
> if an attacker convinces them to start bitcoind with a malicious
> `-assumevalid`
> parameter, sybils their node, and then feeds them a bogus chain
> encompassing
> all of the hard-coded checkpoints[3].
>
> The same attack is made easier in assumeutxo because, unlike in
> assumevalid,
> the attacker need not construct a valid PoW chain to get the victim's node
> into
> a false state; they simply need to get the user to accept a bad
> `-assumeutxo`
> parameter and then supply them an easily made UTXO snapshot containing,
> say, a
> false coin assignment.
>
> For this reason, I recommend that if we were to implement assumeutxo, we
> not
> allow its specification via commandline argument[4].
>
> Beyond this risk, I can't think of material differences in security
> relative to
> assumevalid, though I appeal to the list for help with this.
>
> # More fully validating clients
>
> A particularly exciting use-case for assumeutxo is the possibility of
> mobile
> devices functioning as fully validating nodes with access to the complete
> UTXO
> set (as an alternative to SPV models). The total resource burden needed to
> start a node
> from scratch based on a snapshot is, at time of writing, a ~(3.2GB
> + blocks_to_tip * 4MB) download and a few minutes of processing time,
> which sounds
> manageable for many mobile devices currently in use.
>
> A mobile user could initialize an assumed-valid bitcoin node within an
> hour,
> transact immediately, and complete a pruned full validation of their
> assumed-valid chain over the next few days, perhaps only doing the
> background
> IBD when their device has access to suitable high-bandwidth connections.
>
> If we end up implementing an accumulator-based UTXO scaling design[5][6]
> down
> the road, it's easy to imagine an analogous process that would allow very
> fast
> startup using an accumulator of a few kilobytes in lieu of a multi-GB
> snapshot.
>
> ---
>
> I've created a related issue at our Github repository here:
> https://github.com/bitcoin/bitcoin/issues/15605
>
> and have submitted a draft implementation of snapshot usage via RPC here:
> https://github.com/bitcoin/bitcoin/pull/15606
>
> I'd like to discuss here whether this is a good fit for Bitcoin
> conceptually. Concrete
> plans for deployment steps should be discussed in the Github issue, and
> after all
> that my implementation may be reviewed as a sketch of the specific software
> changes necessary.
>
> Regards,
> James
>
>
> [0]:
> https://bitcoincore.org/en/2017/03/08/release-0.14.0/#assumed-valid-blocks
> [1]: https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki
> [2]: as tested at height 569895, on a 12 core Intel Xeon Silver 4116 CPU @
> 2.10GHz
> [3]:
> https://github.com/bitcoin/bitcoin/blob/84d0fdc/src/chainparams.cpp#L145-L161
> [4]: Marco Falke is due credit for this point
> [5]: utreexo: https://www.youtube.com/watch?v=edRun-6ubCc
> [6]: Boneh, Bunz, Fisch on accumulators: https://eprint.iacr.org/2018/1188
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20190403/49377fdf/attachment.html>

2023-06-07 18:12:29

- reply

📅 Original date posted:2018-05-29
📝 Original message:This is a really cool finding, thanks Pieter!
I did some more analysis on selecting a good P value to reduce total data
downloaded considering both filters themselves and blocks in the case of
false positive matches, using data from mainnet. The quantity it minimizes
is:
filter_size(N, B) + block_size * false_positive_probability(C, N, B)
N is the number of filter elements per block
B is the Golomb-Rice coding parameter
C is the number of filter elements watched by the client
The main result is that:
For C = 10, B = 13 is optimal
For C = 100, B = 16 is optimal
For C = 1,000, B = 20 is optimal
For C = 10,000, B = 23 is optimal
So any value of B in the range 16 to 20 seems reasonable, with M = 1.4971 *
2^B for optimal compression, as Pieter derived. The selection of the
parameter depends on the target number of elements that a client may watch.
I attached some of the results, and would be happy to share the CSV and raw
notebook if people are interested.
On Fri, May 25, 2018 at 2:14 PM Gregory Maxwell via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> On Fri, May 25, 2018 at 6:42 PM, Gregory Maxwell <greg at xiph.org> wrote:
> > configuration is roughly right, then M=1569861 and rice parameter 19
> > should be used.
>
> That should have been M=784931 B=19 ... paste error.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180529/1a5d37e0/attachment-0002.html>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180529/1a5d37e0/attachment-0003.html>

2023-06-07 18:12:16

- reply

📅 Original date posted:2018-05-24
📝 Original message:Greg, I've attached a graph including the input scripts.
In the top graph, we can see how the input script filter compares to the
input outpoint filter. It is definitely smaller as a result of address
reuse. The bottom graph shows the ratio over time of combining the input
prev script and output script filters vs keeping them separate. In more
recent blocks, it appears that there are decreasing savings.
On Wed, May 23, 2018 at 6:04 PM Conner Fromknecht
<conner at lightning.engineering> wrote:
> Hi all,
>
> Jimpo, thanks for looking into those stats! I had always imagined that
> there
> would be a more significant savings in having all filters in one bundle, as
> opposed to separate. These results are interesting, to say the least, and
> definitely offer us some flexibility in options for filter sharding.
>
> So far, the bulk of this discussion has centered around bandwidth. I am
> concerned, however, that splitting up the filters is at odds with the
> other
> goal of the proposal in offering improved privacy.
>
> Allowing clients to choose individual filter sets trivially exposes the
> type of
> data that client is interested in. This alone might be enough to
> fingerprint the
> function of a peer and reduce anonymity set justifying their potential
> behavior.
>
> Furthermore, if a match is encountered, and block requested, full nodes
> have
> more targeted insight into what caused a particular match. They could
> infer that
> the client received funds in a particular block, e.g., if they are only
> requesting
> output scripts.
>
> This is above and beyond the additional complexity of now syncing,
> validating,
> and managing five or six distinct header/filter-header/filter/block chains.
>
> I agree that saving on bandwidth is an important goal, but bandwidth and
> privacy
> are always seemingly at odds. Strictly comparing the bandwidth
> requirements of
> a system that heavily weighs privacy to existing ones, e.g. BIP39, that
> don't is a
> losing battle IMO.
>
> I'm not fundamentally opposed to splitting the filters, I certainly see the
> arguments for flexibility. However, I also want to ensure we are
> considering the
> second order effects that fall out of optimizing for one metric when
> others exist.
>
> Cheers,
> Conner
> On Wed, May 23, 2018 at 10:29 Gregory Maxwell via bitcoin-dev <
> bitcoin-dev at lists.linuxfoundation.org> wrote:
>
>> Any chance you could add a graph of input-scripts (instead of input
>> outpoints)?
>>
>> On Wed, May 23, 2018 at 7:38 AM, Jim Posen via bitcoin-dev
>> <bitcoin-dev at lists.linuxfoundation.org> wrote:
>> > So I checked filter sizes (as a proportion of block size) for each of
>> the
>> > sub-filters. The graph is attached.
>> >
>> > As interpretation, the first ~120,000 blocks are so small that the
>> > Golomb-Rice coding can't compress the filters that well, which is why
>> the
>> > filter sizes are so high proportional to the block size. Except for the
>> > input filter, because the coinbase input is skipped, so many of them
>> have 0
>> > elements. But after block 120,000 or so, the filter compression
>> converges
>> > pretty quickly to near the optimal value. The encouraging thing here is
>> that
>> > if you look at the ratio of the combined size of the separated filters
>> vs
>> > the size of a filter containing all of them (currently known as the
>> basic
>> > filter), they are pretty much the same size. The mean of the ratio
>> between
>> > them after block 150,000 is 99.4%. So basically, not much compression
>> > efficiently is lost by separating the basic filter into sub-filters.
>> >
>> > On Tue, May 22, 2018 at 5:42 PM, Jim Posen <jim.posen at gmail.com> wrote:
>> >>>
>> >>> My suggestion was to advertise a bitfield for each filter type the
>> node
>> >>> serves,
>> >>> where the bitfield indicates what elements are part of the filters.
>> This
>> >>> essentially
>> >>> removes the notion of decided filter types and instead leaves the
>> >>> decision to
>> >>> full-nodes.
>> >>
>> >>
>> >> I think it makes more sense to construct entirely separate filters for
>> the
>> >> different types of elements and allow clients to download only the
>> ones they
>> >> care about. If there are enough elements per filter, the compression
>> ratio
>> >> shouldn't be much worse by splitting them up. This prevents the
>> exponential
>> >> blowup in the number of filters that you mention, Johan, and it works
>> nicely
>> >> with service bits for advertising different filter types independently.
>> >>
>> >> So if we created three separate filter types, one for output scripts,
>> one
>> >> for input outpoints, and one for TXIDs, each signaled with a separate
>> >> service bit, are people good with that? Or do you think there
>> shouldn't be a
>> >> TXID filter at all, Matt? I didn't include the option of a prev output
>> >> script filter or rolling that into the block output script filter
>> because it
>> >> changes the security model (cannot be proven to be correct/incorrect
>> >> succinctly).
>> >>
>> >> Then there's the question of whether to separate or combine the
>> headers.
>> >> I'd lean towards keeping them separate because it's simpler that way.
>> >
>> >
>> >
>> > _______________________________________________
>> > bitcoin-dev mailing list
>> > bitcoin-dev at lists.linuxfoundation.org
>> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>> >
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180523/fe5608eb/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: filter_sizes.svg
Type: image/svg+xml
Size: 2833873 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180523/fe5608eb/attachment-0001.svg>

2023-06-07 18:12:14

- reply

📅 Original date posted:2018-05-22
📝 Original message:>
> My suggestion was to advertise a bitfield for each filter type the node
> serves,
> where the bitfield indicates what elements are part of the filters. This
> essentially
> removes the notion of decided filter types and instead leaves the decision
> to
> full-nodes.
>
I think it makes more sense to construct entirely separate filters for the
different types of elements and allow clients to download only the ones
they care about. If there are enough elements per filter, the compression
ratio shouldn't be much worse by splitting them up. This prevents the
exponential blowup in the number of filters that you mention, Johan, and it
works nicely with service bits for advertising different filter types
independently.
So if we created three separate filter types, one for output scripts, one
for input outpoints, and one for TXIDs, each signaled with a separate
service bit, are people good with that? Or do you think there shouldn't be
a TXID filter at all, Matt? I didn't include the option of a prev output
script filter or rolling that into the block output script filter because
it changes the security model (cannot be proven to be correct/incorrect
succinctly).
Then there's the question of whether to separate or combine the headers.
I'd lean towards keeping them separate because it's simpler that way.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180522/328a953f/attachment-0001.html>

2023-06-07 18:12:14

- reply

📅 Original date posted:2018-05-23
📝 Original message:So I checked filter sizes (as a proportion of block size) for each of the
sub-filters. The graph is attached.
As interpretation, the first ~120,000 blocks are so small that the
Golomb-Rice coding can't compress the filters that well, which is why the
filter sizes are so high proportional to the block size. Except for the
input filter, because the coinbase input is skipped, so many of them have 0
elements. But after block 120,000 or so, the filter compression converges
pretty quickly to near the optimal value. The encouraging thing here is
that if you look at the ratio of the combined size of the separated filters
vs the size of a filter containing all of them (currently known as the
basic filter), they are pretty much the same size. The mean of the ratio
between them after block 150,000 is 99.4%. So basically, not much
compression efficiently is lost by separating the basic filter into
sub-filters.
On Tue, May 22, 2018 at 5:42 PM, Jim Posen <jim.posen at gmail.com> wrote:
> My suggestion was to advertise a bitfield for each filter type the node
>> serves,
>> where the bitfield indicates what elements are part of the filters. This
>> essentially
>> removes the notion of decided filter types and instead leaves the
>> decision to
>> full-nodes.
>>
>
> I think it makes more sense to construct entirely separate filters for the
> different types of elements and allow clients to download only the ones
> they care about. If there are enough elements per filter, the compression
> ratio shouldn't be much worse by splitting them up. This prevents the
> exponential blowup in the number of filters that you mention, Johan, and it
> works nicely with service bits for advertising different filter types
> independently.
>
> So if we created three separate filter types, one for output scripts, one
> for input outpoints, and one for TXIDs, each signaled with a separate
> service bit, are people good with that? Or do you think there shouldn't be
> a TXID filter at all, Matt? I didn't include the option of a prev output
> script filter or rolling that into the block output script filter because
> it changes the security model (cannot be proven to be correct/incorrect
> succinctly).
>
> Then there's the question of whether to separate or combine the headers.
> I'd lean towards keeping them separate because it's simpler that way.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180523/5a74bcf7/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: filter_sizes.svg
Type: image/svg+xml
Size: 2066101 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180523/5a74bcf7/attachment-0001.svg>

2023-06-07 18:12:12

- reply

📅 Original date posted:2018-05-17
📝 Original message:>
> I think lite clients cross checking is something which very likely
> will never be implemented by anyone, and probably not stay working
> (due to under-usage) if it is implemented. This thought is driven by
> three things (1) the bandwidth overhead of performing the check, (2)
> thinking about the network-interacting-state-machine complexity of it,
> and by the multitude of sanity checks that lite clients already don't
> implement (e.g. when a lite client noticed a split tip it could ask
> peers for the respective blocks and check at least the stateless
> checks, but none has ever done that), and...
>
In my opinion, it's overly pessimistic to design the protocol in an
insecure way because some light clients historically have taken shortcuts.
If the protocol can provide clients the option of getting additional
security, it should.
On the general topic, Peter makes a good point that in many cases filtering
by txid of spending transaction may be preferable to filtering by outpoint
spend, which has the nice benefit that there are obviously fewer txs in a
block than txins. This wouldn't work for malleable transactions though.
I'm open to the idea of splitting the basic filter into three separate
filters based on data type, but there are some bandwidth concerns. First,
the GCS encoding gets better compression with a greater number of elements,
though as I recall in my analysis, that starts to tail off at ~1000
elements per filter with P=20, in which case it's not as much of a concern
given current block sizes. The other is that clients need to download
and/or store the filter header chain for each filter type, which are 32
bytes each per block. So if a client is expected to download all three
filter types anyway, or even two of three, it's less efficient in these
terms. It would be possible though to split the filters themselves, but
still have the basic filter header cover all three filters. This would mean
that full nodes could not support just a subset of the basic filters --
they'd have to compute all of them to compute the filter header.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180517/c25d9cf4/attachment.html>

2023-06-07 18:12:12

- reply

📅 Original date posted:2018-05-17
📝 Original message:>
> It isn't a question of 'some lite clients' -- I am aware of no
> implementation of these kinds of measures in any cryptocurrency ever.
>
Doesn't mean there can't or shouldn't be a first. :-)
> The same kind of comparison to the block could have been done with
> BIP37 filtering, but no one has implemented that. (similarly, the
> whitepaper suggests doing that for all network rules when a
> disagreement has been seen, though that isn't practical for all
> network rules it could be done for many of them-- but again no
> implementation or AFAIK any interest in implementing that)
Correct me if I'm wrong, but I don't think it's true that the same could be
done for BIP 37. With BIP 37, one would have to download every partial
block from every peer to determine if there is a difference between them.
With BIP 157, you only download a 32 byte filter header from every peer
(because filters are deterministic), and using that commitment can
determine whether there's a conflict requiring further interrogation. The
difference in overhead makes checking for conflicts with BIP 157 practical,
whereas it's not as practical with BIP 37.
> Sure, but at what cost? And "additional" while nice doesn't
> necessarily translate into a meaningful increase in delivered security
> for any particular application.
>
> I think we might be speaking too generally here.
>
Sure. The security model that BIP 157 now allows is that a light client with*
at least one honest peer serving filters* can get the correct information
about the chain. No, this does not prevent against total eclipse attacks,
but I think it's a much stronger security guarantee than requiring all
peers or even a majority of peers to be honest. In a decentralized network
that stores money, I think there's a big difference between those security
models.
> But in exchange the filters for a given FP rate would be probably
> about half the current size (actual measurements would be needed
> because the figure depends on much scriptpubkey reuse there is, it
> probably could be anywhere between 1/3 and 2/3rd).
>
This does not seem right. Let's assume txids are removed because they are
not relevant to this particular point. The difference as I understand it is
whether to include in the filter serialized outpoints for inputs or
serialized prev scriptPubkeys for inputs. When hashed these are the same
size, and there's an equal number of them (one per input in a block). So
the only savings comes from deduping the prev scriptPubkeys with each other
and with the scriptPubkeys in the block's outputs. So it comes down
entirely to how much address reuse there is on the chain.
> Monitoring inputs by scriptPubkey vs input-txid also has a massive
> advantage for parallel filtering: You can usually known your pubkeys
> well in advance, but if you have to change what you're watching block
> N+1 for based on the txids that paid you in N you can't filter them
> in parallel.
>
Yes, I'll grant that this is a benefit of your suggestion.
> I think Peter missed Matt's point that you can monitor for a specific
> transaction's confirmation by monitoring for any of the outpoints that
> transaction contains. Because the txid commits to the outpoints there
> shouldn't be any case where the txid is knowable but (an) outpoint is
> not. Removal of the txid and monitoring for any one of the outputs
> should be a strict reduction in the false positive rate for a given
> filter size (the filter will contain strictly fewer elements and the
> client will match for the same (or usually, fewer) number).
>
> I _think_ dropping txids as matt suggests is an obvious win that costs
> nothing. Replacing inputs with scripts as I suggested has some
> trade-offs.
>
I may have interpreted this differently. So wallets need a way to know when
the transactions they send get confirmed (for obvious usability reasons and
so for automatic fee-bumping). One way is to match the spent outpoints
against the filter, which I think of as the standard. Another would be to
match the txid of the spending transaction against the first, which only
works if the transaction is not malleable. Another would be to match the
change output script against the first, assuming the wallet does not reuse
change addresses and that the spending transaction does in fact have a
change output.
Now lets say these pieces of data, txids, output scripts, and spent
outpoints are in three separate filters that a wallet can download
separately or choose not to download. The spent outpoint method is the most
reliable and has no caviats. It also allows for theft detection as Peter
notes, which is a very nice property indeed. If the wallet uses the txid
matching though, the txid filter would be smaller because there are fewer
txids per block than inputs. So there could be some bandwidth savings to
that approach. The change output watching is probably the nicest in some
ways because the client needs the output filter anyway. If the transaction
has no change output with a unique script, the client could watch for any
of the other outputs on the spending tx, but may get more false positives
depending on the degree of address reuse.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180517/01b8298f/attachment-0001.html>

2023-06-07 18:11:58

- reply

📅 Original date posted:2018-05-17
📝 Original message:>
> This brings us another theoretical problem: someone could spend our
> OP_TRUE with a low-fee non-RBF tx, and we'd not be able to use it to
> CPFP the tx. It'd be hard to do, but possible. I think the network
> benefits from using OP_TRUE (anyone can clean, and size, vs some
> only-known-to-me pubkey) outweighs the risk, but it'd be nice if OP_TRUE
> P2WSH spends were always considered RBF.
>
I believe OP_CSV with a relative locktime of 0 could be used to enforce RBF
on the spending tx?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180517/da8223c0/attachment-0001.html>

2023-06-07 18:11:39

- reply

📅 Original date posted:2018-04-13
📝 Original message:Why not add the outpoints owned by the wallet to the filter and watch for
those instead of elements in the input script or witness data?
On Fri, Apr 13, 2018 at 12:12 PM, Jonas Schnelli via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Hi Andreas
>
> Thanks for bringing this up and this seems indeed to be suboptimal.
>
> > I wonder if Bitcoin Core would be willing to extend the BIP37 matching
> > rules such that data elements in the witness are also matched against?
>
> Bitcoin Core is not an identity that can be „willing to extend“ (or
> reject) a feature.
> Someone needs to come up with a proposal (pull request).
>
> Maybe an extension for BIP37 would make sense (*meh*).
> Just inserting the witness data into the bloom filter seems to be an easy
> solution (CBloomFilter::IsRelevantAndUpdate())
>
> /jonas
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180413/cedc5780/attachment.html>