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

nprofile1qqsfufer737xc9knpymnt0t2ehytphgmj8rcy9hhqqda6tm4v2mfa5gpz3mhxue69uhhyetvv9ujuerpd46hxtnfduqs6amnwvaz7tmwdaejumr0dsg7e3h3

Publishing to

relay.damus.io

nos.lol

Author Public Key

npub1ncnj8arudstdxzfhxk7k4nwgkrw3hyw8sgt0wqqmm5hh2c4knmgs2lqt2n

Show more details

Last Notes

2023-06-09 14: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 14:50:41

- reply

📅 Original date posted:2018-05-08
📝 Original message:
Benjamin,
I don't agree that quantum resistance should be a blocker to deployment of
scriptless scripts on lightning because 1) it is a layer-2 solution and 2)
it already critically depends on the security of DL.
There are arguments against making certain protocol changes to the base
Bitcoin blockchain for the reason that they may not be quantum resistant.
The most notable is Confidential Transactions. There reason is that the
worst case attack is much worse: an attacker could print money freely and
without detection. In Bitcoin today, a DL break would compromise funds in
any addresses for which the pubkey has been revealed and it's not even
clear what to do about the remaining funds on chain. Compromising the
fundamental security of the blockchain is a valid cause for concern.
In the case of Lightning, the attack scenario on scriptless scripts is that
a peer is going to use a quantum computer to steal all live payments routed
through them from their senders before they get to the recipient. This
would be bad, but not catastrophic, and once it is recognized that the
attack is possible, insecure channels could be closed.
But furthermore, an attacker with a quantum computer could just steal the
multisig funding output directly instead of attacking scriptless scripts.
So additional protocol changes relying on the DL assumption don't bother me
in the least.
On Tue, May 8, 2018, 6:32 AM Benjamin Mord <ben at mord.io> wrote:
>
> Sorry, I do not wish to spam the list, but I need to correct a rather
> serious error in my last email. We must never call something
> "post-quantum", absent mathematical proof. (And good luck with that.) I
> apologise for my mistake in doing so myself.
>
> I should not even refer to lattice based cryptography as a post-quantum
> algorithm, I should at best call it a Shor's algorithm-resistant scheme. At
> least, it is not (yet) known how Shor's algorithm could be used to break
> it. Not in public circles, anyhow.
>
> A cursory glance at the history of cryptanalysis shows that primitives
> generally have finite life, which makes it odd that systems seldom use
> redundant primitives, and seldom provide for their rapid and safe swap. A
> system whose entire security rests on nothing but cryptography, ought to
> take particular care! The spectre of quantum computers may render the
> finite life of certain primitives more salient than others, but we must not
> suppose that, absent Shor's algorithm, there would be no need to plan for
> cryptographic failures. The question is not if, but when, Bitcoin and
> lightning will contend with broken primitives, whether due to classical or
> quantum cryptanalysis. Likely, both will come into play at various times,
> and one must plan accordingly.
>
> On Tue, May 8, 2018, 9:09 AM Benjamin Mord <ben at mord.io> wrote:
>
>>
>> That would be awesome. Do you have a reference?
>>
>> As pertains to the whole of asymmetric cryptography, I believe there are
>> not a variety of post quantum schemes, there is only one*: lattice-based
>> cryptography. (Which scares me, because it is not all that different from
>> the others.)
>>
>> (* Actually, in contexts where time can be used for asymmetry, as in
>> TESLA, we can then use hash functions to create something like asymmetric
>> signatures as well. But the functional context has to be compatible with
>> delayed verification.)
>>
>> (But I do not mean to focus exclusively on Schor's algorithm, the history
>> of even pre-quantum cryptanalysis shows that primitives tend to have finite
>> lifespan. Redundancy of any sort of good, even when not focused
>> specifically on quantum risks.)
>>
>> On Tue, May 8, 2018, 8:58 AM Greg Sanders <gsanders87 at gmail.com> wrote:
>>
>>> From what I understand talking to folks, the linear properties of these
>>> signature tricks are maintained under a number of post-quantum schemes.
>>>
>>> On Tue, May 8, 2018 at 8:44 AM, Benjamin Mord <ben at mord.family> wrote:
>>>
>>>>
>>>> If I'm not mistaken, the scriptless scripts concept (as currently
>>>> formulated) falls to Schor's algorithm, and at present there is no
>>>> alternative implementation of the concept to fall back on. Correct? Lest we
>>>> build a house of cards, I'd strongly urge everyone to not depend on
>>>> functional concepts whose underlying cryptographic primitives cannot be
>>>> swapped in an emergency.
>>>>
>>>> Sure, we use ecdsa for example (which is also vulnerable to Schor's
>>>> algorithm), but in contrast to scriptless scripts we have a variety of
>>>> backup primitives at our disposal that fulfill the same functional
>>>> objective.
>>>>
>>>> If scriptless scripts are found possible under lattice-based
>>>> cryptography for example, that would be something I suppose. The functional
>>>> concept of scriptless scripts is indeed very awesome - we just need to add
>>>> some cryptographic conservatism before we build on it.
>>>>
>>>>
>>>> _______________________________________________
>>>> 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/20180508/f3ebdf1a/attachment.html>

2023-06-09 14: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 14: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 14:50:25

- reply

📅 Original date posted:2018-05-09
📝 Original message:
One more point in terms of information leakage is that noise can be added
to the "this is the rate that you'll lose reputation at" field to help
obfuscate the number of upstream hops. I proposed setting it to "this is
the upstream rate that I'm losing reputation at" + downstream HTLC value,
but a node can decide to add noise. If they make it too low however,
there's a risk of insufficiently punishing bad nodes and if they make it
too high, there's a heightened risk that the payment fails because the
downstream reputation is insufficient along the route.
This is why I say it's kind of symmetric to the CLTV value: if the delta is
too low, there's risk of loss of funds, if the delta is too high, someone
might decide to fail the payment instead of taking the delay risk.
On Wed, May 9, 2018 at 10:23 AM, Jim Posen <jim.posen at gmail.com> wrote:
> Thanks for the thoughtful responses.
>
> > You missed the vital detail: that you must prove channel closure if you
> > can't unpeel the onion further. That *will* hit an unresponsive party
> > with a penalty.
>
> Ah, that is a good point. I still find the proposal overall worryingly
> complex in terms of communication overhead, time it takes to prove channel
> closure, all of your points in [1], [2], [3], etc. Furthermore, this
> mandates that immediate channel closure is the only allowed reaction to a
> party delaying an HTLC for a time period above a threshold -- the node
> reputation approach gives more discretion to the preceding hop.
> Deobfuscating the route may turn out to be the right option, but I think
> the reputation system has certain advantages over this.
>
> > The models we tried in Milan all created an incentive to fail payments,
> > which is a non-starter.
>
> Do you mind elaborating or summarizing the reasons? The way I'm analyzing
> it, even if there's a nominal spam fee paid to routing nodes that fail
> payments, as long as it's low enough (say 2-5% for arguments sake), the
> nodes still have more to gain by forwarding the payment and earning the
> full fee on a completed payment, and possibly the reputation boost
> associated with completing a payment if that system was in effect.
> Moreover, a node that constantly fails payments will be blacklisted by the
> sender eventually and stop receiving HTLCs from them at all. Overall, I
> don't think this is a profitable strategy. Furthermore, I think it works
> quite well in combination with the reputation system.
>
> > This seems like we'd need some serious evaluation to show that this
> > works, because the risks are very high.
>
> I agree that it needs to be evaluated. I may start working on some network
> simulations to test various DOS mitigation strategies.
>
> > I can destroy your node's reputation by routing crap through you; even
> > if it costs me marginaly more reputation than it does you, that just
> > means that the largest players can force failure upon smaller players,
> > centralizing the network. And I think trying to ensure that it costs me
> > more reputation than the sum of downstream reputation loss leaks too
> > much information
>
> I will add to ZmnSCPxj's response, which is mostly on point. The key here
> is that the only way to lose significant reputation is to delay a payment
> yourself or forward to a malicious downstream that delays -- neither of
> these can be forced by the sender alone. This amounts to a system where you
> are on the hook for any malicious behavior of your downstream peers, which
> is why you must keep a reputation score for each which they earn over time.
> This should keep all links in the network high quality and quickly
> disconnect off delaying nodes if the incentives are right.
>
> While I agree that a lot of reputation is leaked by aggregating the losses
> along the route, this serves exactly to prevent large nodes with high
> reputation from ruining links elsewhere. There are two things a node
> looking to cause reputation loss could do. 1) Identify a node (not itself)
> it thinks will delay a payment and send to them. This locks up funds on
> their behalf, but is actually good behavior because it identifies a faulty
> node and rightfully forces a loss in their reputation, eventually resulting
> in them being booted from the network. Everyone upstream loses some
> reputation for having connectivity to them, but less because of the loss
> aggregation along the route. 2) Delay a payment oneself and force upstream
> reputation loss. This is why I think it's important that the reputation
> loss aggregate so that the malicious party loses the most.
>
> As for the amount of information leaked, yes, it helps determine the
> number of upstream hops in a route. However, the CLTV values help determine
> the number of downstream hops in a route in exactly the same way. I see
> these as symmetric in a sense.
>
> To address ZmnSCPxj's point:
>
> > But it also looks more and more like a policy of "just
> `update_htlc_fail`" keeps our reputation high: indeed never accepting a
> forwarding attempt would ensure reputation.
> > However, earning via fees should help provide incentive against "Just
> `update_htlc_fail`" always. If the goal is "how do I earn money fastest"
> then there is some optimal threshhold > of risk-of-reputation-loss vs.
> fee-earnings-if-I-forward that is unlikely to be near the "Just fail it"
> spectrum, but somewhere in between. We hope.
>
> This is exactly the question that your local view of peer reputations
> helps solve: are the potential fees here worth the risk of forwarding this
> payment to this downstream? If their reputation is high, then you will want
> to forward because you think there's a low chance of you incurring
> reputation loss. If their reputation is low and the HTLC value is too high,
> you will fail it. So I disagree that "just `update_htlc_fail`" is an
> optimal strategy. Consider as well that all fees you earn on successful
> payments are profit to you as well as a reputation boost in the view of
> both of your peers. So in order to earn reputation, you have to forward
> payments. The key is not forwarding through malicious peers.
>
> -jimpo
>
> On Wed, May 9, 2018 at 12:31 AM, ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
>
>> Good morning Rusty, Jim, and list,
>>
>> > I can destroy your node's reputation by routing crap through you; even
>> >
>> > if it costs me marginaly more reputation than it does you, that just
>> >
>> > means that the largest players can force failure upon smaller players,
>> >
>> > centralizing the network.
>>
>> My understanding of the proposal was that reputation loss would occur
>> only if the reply (`update_htlc_fail` or `update_htlc_success`) is delayed;
>> this means that for you to force me to lose reputation, you need to somehow
>> make me delay my reply. In particular if you do simple things like give me
>> an invalid onion, or make me forward to a payee who does not know the
>> preimage, I do not lose reputation by replying very quickly with an
>> `update_htlc_fail`.
>>
>> Of course, a large player could force reputation loss by delaying reply
>> when they receive, and having patsy nodes route to them. So for instance
>> if it is Jim -> ZmnSCPxj -> Rusty, and Rusty activates the
>> Blockstream-takes-over-the-world Apocalypse program, the Rusty node
>> would then delay for a long time before replying, which makes my reputation
>> suffer. But it also makes Rusty reputation suffer even more and my
>> reaction would be that, the next time Jim hands me an HTLC that forwards to
>> Rusty, I would instead quickly `update_htlc_fail` back to Jim (which does
>> not lose me significant reputation due to my quick response) than risk
>> forwarding it to you, since you have a reputation for being slow and
>> unresponsive.
>>
>> Indeed, another aspect of Jim proposal is that it is extremely local: if
>> Jim has no channel to Rusty, then Jim has no opinion about Rusty, only
>> about ZmnSCPxj. However, ZmnSCPxj does have an opinion about Rusty, as
>> ZmnSCPxj has channel with Rusty. If I suffer too much reputation loss due
>> to Rusty, my opinion of Rusty drops even faster, and I decide to
>> `update_htlc_fail` in order to prevent Jim opinion of me from dropping too
>> much that Jim decides not to forward to me (if I have other channels with
>> more reasonable nodes).
>>
>> But it also looks more and more like a policy of "just
>> `update_htlc_fail`" keeps our reputation high: indeed never accepting a
>> forwarding attempt would ensure reputation.
>>
>> However, earning via fees should help provide incentive against "Just
>> `update_htlc_fail`" always. If the goal is "how do I earn money fastest"
>> then there is some optimal threshhold of risk-of-reputation-loss vs.
>> fee-earnings-if-I-forward that is unlikely to be near the "Just fail it"
>> spectrum, but somewhere in between. We hope.
>>
>> > And I think trying to ensure that it costs me
>> >
>> > more reputation than the sum of downstream reputation loss leaks too
>> >
>> > much information
>>
>> Yes, this is a major drawback of the proposal. The rate at which the
>> sender of the HTLC threatens me with reputation loss lets me estimate my
>> distance from the ultimate sender of the funds.
>>
>> Regards,
>> ZmnSCPxj
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180509/1894d9e0/attachment-0001.html>

2023-06-09 14:50:24

- reply

📅 Original date posted:2018-05-09
📝 Original message:
Thanks for the thoughtful responses.
> You missed the vital detail: that you must prove channel closure if you
> can't unpeel the onion further. That *will* hit an unresponsive party
> with a penalty.
Ah, that is a good point. I still find the proposal overall worryingly
complex in terms of communication overhead, time it takes to prove channel
closure, all of your points in [1], [2], [3], etc. Furthermore, this
mandates that immediate channel closure is the only allowed reaction to a
party delaying an HTLC for a time period above a threshold -- the node
reputation approach gives more discretion to the preceding hop.
Deobfuscating the route may turn out to be the right option, but I think
the reputation system has certain advantages over this.
> The models we tried in Milan all created an incentive to fail payments,
> which is a non-starter.
Do you mind elaborating or summarizing the reasons? The way I'm analyzing
it, even if there's a nominal spam fee paid to routing nodes that fail
payments, as long as it's low enough (say 2-5% for arguments sake), the
nodes still have more to gain by forwarding the payment and earning the
full fee on a completed payment, and possibly the reputation boost
associated with completing a payment if that system was in effect.
Moreover, a node that constantly fails payments will be blacklisted by the
sender eventually and stop receiving HTLCs from them at all. Overall, I
don't think this is a profitable strategy. Furthermore, I think it works
quite well in combination with the reputation system.
> This seems like we'd need some serious evaluation to show that this
> works, because the risks are very high.
I agree that it needs to be evaluated. I may start working on some network
simulations to test various DOS mitigation strategies.
> I can destroy your node's reputation by routing crap through you; even
> if it costs me marginaly more reputation than it does you, that just
> means that the largest players can force failure upon smaller players,
> centralizing the network. And I think trying to ensure that it costs me
> more reputation than the sum of downstream reputation loss leaks too
> much information
I will add to ZmnSCPxj's response, which is mostly on point. The key here
is that the only way to lose significant reputation is to delay a payment
yourself or forward to a malicious downstream that delays -- neither of
these can be forced by the sender alone. This amounts to a system where you
are on the hook for any malicious behavior of your downstream peers, which
is why you must keep a reputation score for each which they earn over time.
This should keep all links in the network high quality and quickly
disconnect off delaying nodes if the incentives are right.
While I agree that a lot of reputation is leaked by aggregating the losses
along the route, this serves exactly to prevent large nodes with high
reputation from ruining links elsewhere. There are two things a node
looking to cause reputation loss could do. 1) Identify a node (not itself)
it thinks will delay a payment and send to them. This locks up funds on
their behalf, but is actually good behavior because it identifies a faulty
node and rightfully forces a loss in their reputation, eventually resulting
in them being booted from the network. Everyone upstream loses some
reputation for having connectivity to them, but less because of the loss
aggregation along the route. 2) Delay a payment oneself and force upstream
reputation loss. This is why I think it's important that the reputation
loss aggregate so that the malicious party loses the most.
As for the amount of information leaked, yes, it helps determine the number
of upstream hops in a route. However, the CLTV values help determine the
number of downstream hops in a route in exactly the same way. I see these
as symmetric in a sense.
To address ZmnSCPxj's point:
> But it also looks more and more like a policy of "just
`update_htlc_fail`" keeps our reputation high: indeed never accepting a
forwarding attempt would ensure reputation.
> However, earning via fees should help provide incentive against "Just
`update_htlc_fail`" always. If the goal is "how do I earn money fastest"
then there is some optimal threshhold > of risk-of-reputation-loss vs.
fee-earnings-if-I-forward that is unlikely to be near the "Just fail it"
spectrum, but somewhere in between. We hope.
This is exactly the question that your local view of peer reputations helps
solve: are the potential fees here worth the risk of forwarding this
payment to this downstream? If their reputation is high, then you will want
to forward because you think there's a low chance of you incurring
reputation loss. If their reputation is low and the HTLC value is too high,
you will fail it. So I disagree that "just `update_htlc_fail`" is an
optimal strategy. Consider as well that all fees you earn on successful
payments are profit to you as well as a reputation boost in the view of
both of your peers. So in order to earn reputation, you have to forward
payments. The key is not forwarding through malicious peers.
-jimpo
On Wed, May 9, 2018 at 12:31 AM, ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> Good morning Rusty, Jim, and list,
>
> > I can destroy your node's reputation by routing crap through you; even
> >
> > if it costs me marginaly more reputation than it does you, that just
> >
> > means that the largest players can force failure upon smaller players,
> >
> > centralizing the network.
>
> My understanding of the proposal was that reputation loss would occur only
> if the reply (`update_htlc_fail` or `update_htlc_success`) is delayed; this
> means that for you to force me to lose reputation, you need to somehow make
> me delay my reply. In particular if you do simple things like give me an
> invalid onion, or make me forward to a payee who does not know the
> preimage, I do not lose reputation by replying very quickly with an
> `update_htlc_fail`.
>
> Of course, a large player could force reputation loss by delaying reply
> when they receive, and having patsy nodes route to them. So for instance
> if it is Jim -> ZmnSCPxj -> Rusty, and Rusty activates the
> Blockstream-takes-over-the-world Apocalypse program, the Rusty node would
> then delay for a long time before replying, which makes my reputation
> suffer. But it also makes Rusty reputation suffer even more and my
> reaction would be that, the next time Jim hands me an HTLC that forwards to
> Rusty, I would instead quickly `update_htlc_fail` back to Jim (which does
> not lose me significant reputation due to my quick response) than risk
> forwarding it to you, since you have a reputation for being slow and
> unresponsive.
>
> Indeed, another aspect of Jim proposal is that it is extremely local: if
> Jim has no channel to Rusty, then Jim has no opinion about Rusty, only
> about ZmnSCPxj. However, ZmnSCPxj does have an opinion about Rusty, as
> ZmnSCPxj has channel with Rusty. If I suffer too much reputation loss due
> to Rusty, my opinion of Rusty drops even faster, and I decide to
> `update_htlc_fail` in order to prevent Jim opinion of me from dropping too
> much that Jim decides not to forward to me (if I have other channels with
> more reasonable nodes).
>
> But it also looks more and more like a policy of "just `update_htlc_fail`"
> keeps our reputation high: indeed never accepting a forwarding attempt
> would ensure reputation.
>
> However, earning via fees should help provide incentive against "Just
> `update_htlc_fail`" always. If the goal is "how do I earn money fastest"
> then there is some optimal threshhold of risk-of-reputation-loss vs.
> fee-earnings-if-I-forward that is unlikely to be near the "Just fail it"
> spectrum, but somewhere in between. We hope.
>
> > And I think trying to ensure that it costs me
> >
> > more reputation than the sum of downstream reputation loss leaks too
> >
> > much information
>
> Yes, this is a major drawback of the proposal. The rate at which the
> sender of the HTLC threatens me with reputation loss lets me estimate my
> distance from the ultimate sender of the funds.
>
> Regards,
> ZmnSCPxj
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180509/1cec1f17/attachment-0001.html>

2023-06-09 14:50:23

- reply

📅 Original date posted:2018-05-02
📝 Original message:
I have been thinking a lot lately about attacks on lightning routing nodes,
the worst of which is the so-called Loop Attack [1]. See the mailing list
thread for more details, but the basic idea is that a sender and receiver
collude to create a long circuit and refuse to settle or fail the HTLC at
the end until the last possible moment. The attack is particularly
insidious for a few reasons. Firstly, an attack on a multi-hop route gives
the attacker leverage, so that their funds locked in one channel cause
funds to be locked up in every channel on the route. Second, the onion
routing makes it difficult to attribute blame to a single node and defend
against a repeated attack.
First, I'll note that the case where a sender and recipient collude is a
more active variant on an attack that any node in a route can perform. Even
if a node does not initiate the payment, it can just accept offered HTLCs
in the route, not forward them, and wait until the offered HTLC almost
expires before failing. As noted above, the prior node in the route cannot
determine whether the attacking node is at fault or one downstream from it.
Even the sender may not be able to determine where in the route the payment
failed because of the issue where the obfuscated error reason is not MAC'ed
on every hop.
There are two directions of solutions I have heard: 1) protocol support for
decrypting the onion route if the HTLC is kept in-flight for too long 2)
requiring fees even if the payment fails as a cost to the attacker 3) some
sort of reputation system for nodes.
Option 1 I'm afraid may be quite complex. Say this mechanism kicks in and
all nodes in the circuit deobfuscate the route and are able to see the
delays at each hop. The outcome we hope for is that there is one node
clearly to blame and the prior hop in the route fails all channels with
them. However, the attacker can of course control multiple successive hops
in the route, one that looks innocent in front of one that looks guilty,
then keep the channel alive and try again. So then all nodes need to keep a
record of the full circuits and iteratively shift blame up the chain if bad
HTLCs keep going through those channels.
Option 2 is also problematic because it only protects against the case
where the sender is colluding with the receiver, and not where a routing
node is opportunistically delaying payments. This would, however, likely be
successful against nodes being annoying and sending tons of payments with
randomly generated payment hashes in order to "ping" a circuit.
Option 3 has become my preferred solution. The idea is that that for each
node that one has channels with, it only forwards payments through them if
they have a good history, otherwise it fails the payment. Notably, we
ignore whether the downstream hop is directly responsible for delaying a
payment or whether they are simply willing to forward to another node that
is intentionally delaying -- both should be considered bad behavior. In my
opinion, this type of solution fits best into the Lightning model of
independent, linked channels where each node has private contracts with its
direct peers. It also is the simplest in the context of onion routing
because if you are offered an HTLC to route, the only decision you can make
is whether to forward it or fail it based on the amount, previous hop, and
next hop. When I refer to "reputation" hereafter, I do not mean a global
reputation that is gossiped about -- just a local view of a peer's history.
For a Sybil-resistant reputation system, we can use money as a way of
measuring reputation. Fees collected through routing payments across
channels raise the reputation of the channel peer. You lose reputation by
accepting an HTLC and not failing or fulfilling it quickly, proportional to
the value of the HTLC and time to respond. What this essentially means is
that if an attacker wants people to send them HTLCs to delay, they pay a
certain amount in fees over time. So each node will track for each peer 1)
total fees collected from forwarding on routes where that peer is the prior
hop 2) total fees collect from forwarding on routes where that peer is the
next hop 3) total value times time of money locked in offered HTLCs on
channels to the peer. To track the third, as soon as an offered HTLC is
locked in by the peer, the node starts a timer. When the HTLC is settled or
failed or handled on-chain, the timer stops and the node registers the
total elapsed time multiplied by the value of the HTLC.
A very simple strategy would be to have two factors, R_inbound and
R_outbound and calculate reputation per peer as R_inbound * total inbound
fees + R_outbound * total outbound fees - total Bitcoin-seconds locked in
an HTLC. When forwarding a payment, you calculate the worst case reputation
loss, HTLC value * (CLTV - current block height) * 10 min / block, and fail
the payment if that value is greater than their current score. Effectively,
reputation scores are the maximum number of Bitcoin-seconds on could waste
in HTLCs as the downstream node in a channel. If you think, for example,
having 1 BTC for 1 hour is worth 1 satoshi, you might set R_inbound =
R_outbound = 10^8. Honest nodes should earn reputation passively by
forwarding payments and failing/fulfilling quickly, while an attacker would
lose reputation and have to pay fees to re-earn it. Furthermore, high
reputation nodes should be able to earn reputation faster since peers will
be willing to forward higher value HTLCs through them.
We want an additional property from this system though, which is that an
attacker be limited in their ability to disrupt network connectivity and
induce throttling on other channels. The above scheme has the problem that
for every unit of reputation the attacker loses, each upstream hop also
loses approximately the same amount -- they effectively get leverage on the
ability to reduce reputation. So instead, consider a modification: each hop
loses a quantity of reputation units equal to the *total* amount of
Bitcoin-seconds lost upstream. So say there's a payment A -> B -> C -> D,
where the CLTV decrements by 12 and the amount decrements by 10 satoshis at
each hop, with a terminal CLTV of 12 and a terminal amount of 100. So A
tells B "Here's an HTLC for 120 satoshis, CLTV is in 36 blocks, and you
will lose reputation at a rate of 120 satoshi-seconds per second of delay".
B calculates the maximum he could lose by forwarding to C as 120 * 36
blocks * 10 min / block. Assuming C has a high enough reputation score, B
will offer an HTLC of 110 satoshis, CLTV of 24 blocks, reputation rate of
120 + 110 = 230 satoshi-seconds per second. And finally C requires D to
stake reputation at a rate of 230 + 100 = 330 satoshi-seconds / second. The
effect is that if any node withholds the preimage, they lose an amount of
reputation equal to all of the reputation lost upstream combined, removing
any attack leverage.
This strategy has some downsides, namely in terms of centralization and
privacy. Telling the downstream node the rate at which they must stake
reputation may allow them to determine the number of upstream hops in the
circuit. To obfuscate this, the sender may require an addition reputation
stake, but takes a higher risk of the payment failing somewhere downstream.
The more obvious issue is centralization -- if payments are getting
throttled by reputation, there is even more of an incentive to route
through a small number of channels and decrease the length of payment
circuits. While this is a concern, the degree to while throttling happens
in controlled by the R parameters (the ratio at which fees contribute to
reputation). If R is high and reputation is abundant, then there will be
little throttling. But if a node finds itself under attack, it can raise
its R parameters and start throttling bad peers.
In summary, I think a simple local reputation mechanism of this form could
be implemented with only minor changes to the BOLT spec and could provide
decent resistance against DOS/loop attacks. Sorry for the excessively long
email.
[1] https://lists.linuxfoundation.org/pipermail/lightning-dev/2015-August/
000135.html
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180501/35997f70/attachment.html>

2023-06-09 14:50:04

- reply

📅 Original date posted:2018-04-15
📝 Original message:
I believe that anyone attempting a DOS by forcing on-chain settlement can
do it just as easily with asymmetric delays than with symmetric delays.
If my goal is to waste the time-value of your money in a channel, in a
world with symmetric delays, I could just publish the commitment
transaction and you would have to wait the full delay for access to your
funds. True. But with delays asymmetric as they are now, I can just as
easily refuse to participate in a mutual close, forcing you to close
on-chain. This is just as bad. In fact, I'd argue that it is worse, because
I lose less by doing this (in the sense that I as the attacker get
immediate access to my funds). So in my assessment, it is a very active
attack and symmetric delays are something of a mitigation. You are right
that the balance of funds in the channel becomes a factor too, but note
that there is the reserve balance, so I'm always losing access to some
funds for some time.
-jimpo
On Sun, Apr 15, 2018 at 6:35 AM, ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> Good morning Daniel,
>
>
> This makes a lot of sense to me as a way to correct the incentives for
> closing channels. I figure that honest nodes that have truly gone offline
> will not require (or be able to take advantage of) immediate access to
> their balance, such that this change shouldn't cause too much inconvenience.
>
> I was trying to think if this could open up a DOS vector - dishonest nodes
> performing unilateral closes even when mutual closes are possible just to
> lock up the other side's coins - but it seems like not much of a concern. I
> figure it's hard to pull off on a large scale.
>
>
>
> Now that you bring this up, I think, it is indeed a concern, and one we
> should not take lightly.
>
> As a purely selfish rational being, it matters not to me whether my
> commitment transaction will delay your output or not; all that matters is
> that it delays mine, and that is enough for me to prefer a bilateral close
> if possible. I think we do not need to change commitment transactions to
> be symmetrical then --- it is enough that the one holding the commitment
> transaction has its own outputs delayed.
>
> If I had a goal to disrupt rather than cooperate with the Lightning
> Network, and commitment transactions would also delay the side not holding
> the commitment transaction (i.e. "symmetrical delay" commitments), I would
> find it easier to disrupt cheaply if I could wait for a channel to be
> unbalanced in your favor (i.e. you own more money on it than I do), then
> lock up both our funds by doing a unilateral transaction. Since it is
> unbalanced in your favor, you end up losing more utility than I do.
> Indeed, in the situation where you are funding a new channel to me, I have
> 0 satoshi on the channel and can perform this attack costlessly.
>
> Now perhaps one may argue, in the case of asymmetric delays, that if I
> were evil, I could still disrupt the network by misbehaving and forcing the
> other side to push its commitment transaction. Indeed I could even just
> accept a channel and then always fail to forward any payment you try to
> make over it, performing a disruption costlessly too (as I have no money in
> this). But this attack is somewhat more passive than the above attack
> under a symmetrical delay commitment transaction scheme.
>
> Regards,
> ZmnSCPxj
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180415/f52b7c35/attachment.html>

2023-06-09 14: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 14:50:03

- reply

📅 Original date posted:2018-04-13
📝 Original message:
> By extension, perhaps both sides should use the maximum delay either one
> asks for?
>
I'm not sure that is necessary. As long as both parties have to wait the
same amount of time regardless of whether they publish the commitment or
the other side does, that would resolve the issue.
> I don't think it's urgent, but please put it into the brainstorming part
> of the wiki so we don't lose track?[1]
>
I don't have access to add to the wiki. I'd write a section like:
# Symmetric CSV Delay
Change the script of the remote output of all commitment transactions to
require the full CSV delay. This acts as further incentive for both parties
to mutually close instead of waiting for the other side to unilaterally
close, and serves as punishment to misbehaving or unresponsive nodes that
force the other endpoint to go to chain.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180413/d373d903/attachment.html>

2023-06-09 14: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 14: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 14: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 14: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 20:17:24

- reply

📅 Original date posted:2019-04-04
📝 Original message:>
> Learning C++ is something within everyone's capability. Even people who do
> not
> wish to learn it can hire someone to perform review for them.
>
Anyone with enough knowledge of C++ to audit the entire the Bitcoin Core
codebase is more than capable of running it with assumeutxo disabled and
checking the hard-coded vale themself.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20190403/fa2a9a58/attachment.html>

2023-06-07 20:16:20

- reply

📅 Original date posted:2019-02-04
📝 Original message:Please see the thread "BIP 158 Flexibility and Filter Size" from 2018
regarding the decision to remove outpoints from the filter [1].
Thanks for bringing this up though, because more discussion is needed on
the client protocol given that clients cannot reliably determine the
integrity of a block filter in a bandwidth-efficient manner (due to the
inclusion of input scripts).
I see three possibilities:
1) Introduce a new P2P message to retrieve all prev-outputs for a given
block (essentially the undo data in Core), and verify the scripts against
the block by executing them. While this permits some forms of input script
malleability (and thus cannot discriminate between all valid and invalid
filters), it restricts what an attacker can do. This was proposed by Laolu
AFAIK, and I believe this is how btcd is proceeding.
2) Clients track multiple possible filter header chains and essentially
consider the union of their matches. So if any filter received for a
particular block header matches, the client downloads the block. The client
can ban a peer if they 1) ever return a filter omitting some data that is
observed in the downloaded block, 2) repeatedly serve filters that trigger
false positive block downloads where such a number of false positives is
statistically unlikely, or 3) repeatedly serves filters that are
significantly larger than the expected size (essentially padding the actual
filters with garbage to waste bandwidth). I have not done the analysis yet,
but we should be able to come up with some fairly simple banning heuristics
using Chernoff bounds. The main downside is that the client logic to track
multiple possible filter chains and filters per block is more complex and
bandwidth increases if connected to a malicious server. I first heard about
this idea from David Harding.
3) Rush straight to committing the filters into the chain (via witness
reserved value or coinbase OP_RETURN) and give up on the pre-softfork BIP
157 P2P mode.
I'm in favor of option #2 despite the downsides since it requires the
smallest number of changes and is supported by the BIP 157 P2P protocol as
currently written. (Though the recommended client protocol in the BIP needs
to be updated to account for this). Another benefit of it is that it
removes some synchronicity assumptions where a peer with the correct
filters keeps timing out and is assumed to be dishonest, while the
dishonest peer is assumed to be OK because it is responsive.
If anyone has other ideas, I'd love to hear them.
-jimpo
[1]
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016057.html
On Mon, Feb 4, 2019 at 10:53 AM Tamas Blummer via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> TLDR: a change to BIP158 would allow decision on which filter chain is
> correct at lower bandwith use
>
> Assume there is a BIP157 client that learned a filter header chain earlier
> and is now offered an alternate reality by a newly connected BIP157 server.
>
> The client notices the alternate reality by routinely asking for filter
> chain checkpoints after connecting to a new BIP157 server. A divergence at
> a checkpoint means that the server disagrees the client's history at or
> before the first diverging checkpoint. The client would then request the
> filter headers between the last matching and first divergent checkpoint,
> and quickly figure which block’s filter is the first that does not match
> previous assumption, and request that filter from the server.
>
> The client downloads the corresponding block, checks that its header fits
> the PoW secured best header chain, re-calculates merkle root of its
> transaction list to know that it is complete and queries the filter to see
> if every output script of every transaction is contained in there, if not
> the server is lying, the case is closed, the server disconnected.
>
> Having all output scripts in the filter does not however guarantee that
> the filter is correct since it might omit input scripts. Inputs scripts are
> not part of the downloaded block, but are in some blocks before that.
> Checking those are out of reach for lightweight client with tools given by
> the current BIP.
>
> A remedy here would be an other filter chain on created and spent
> outpoints as is implemented currently by Murmel. The outpoint filter chain
> must offer a match for every spent output of the block with the divergent
> filter, otherwise the interrogated server is lying since a PoW secured
> block can not spend coins out of nowhere. Doing this check would already
> force the client to download the outpoint filter history up-to the point of
> divergence. Then the client would have to download and PoW check every
> block that shows a match in outpoints until it figures that one of the
> spent outputs has a script that was not in the server’s filter, in which
> case the server is lying. If everything checks out then the previous
> assumption on filter history was incorrect and should be replaced by the
> history offered by the interrogated server.
>
> As you see the interrogation works with this added filter but is highly
> ineffective. A really light client should not be forced to download lots of
> blocks just to uncover a lying filter server. This would actually be an
> easy DoS on light BIP157 clients.
>
> A better solution is a change to BIP158 such that the only filter contains
> created scripts and spent outpoints. It appears to me that this would serve
> well both wallets and interrogation of filter servers well:
>
> Wallets would recognize payments to their addresses by the filter as
> output scripts are included, spends from the wallet would be recognized as
> a wallet already knows outpoints of its previously received coins, so it
> can query the filters for them.
>
> Interrogation of a filter server also simplifies, since the filter of the
> block can be checked entirely against the contents of the same block. The
> decision on filter correctness does not require more bandwith then download
> of a block at the mismatching checkpoint. The client could only be forced
> at max. to download 1/1000 th of the blockchain in addition to the filter
> header history.
>
> Therefore I suggest to change BIP158 to have a base filter, defined as:
>
> A basic filter MUST contain exactly the following items for each
> transaction in a block:
> • Spent outpoints
> • The scriptPubKey of each output, aside from all OP_RETURN output
> scripts.
>
> Tamas Blummer
> _______________________________________________
> 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/20190204/70fc17ef/attachment.html>

2023-06-07 20:13:29

- reply

📅 Original date posted:2018-07-05
📝 Original message:This is awesome, nice work!
On Mon, Jul 2, 2018 at 4:16 PM Roman Zeyde via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Hello all,
>
> I was working on this project for the last few months, so a user could run
> his own Electrum server, with required hardware resources not much beyond
> those of a full node (using ideas from ElectrumX [1], Electrum Personal
> Server [2] and bitcoincore-indexd [3]).
>
> The code and usage instructions can be found here:
> https://github.com/romanz/electrs
>
> The server indexes the entire Bitcoin blockchain, and the resulting index
> [4] enables fast queries for any given user wallet, allowing the user to
> keep real-time track of his balances and his transaction history using the
> Electrum wallet [5].
> Since it runs on the user's own machine, there is no need for the wallet
> to communicate with external Electrum servers, thus preserving the privacy
> of the user's addresses and balances.
>
> Features:
> * Supports latest Electrum protocol [6].
> * Maintains an index of transaction inputs and outputs, allowing fast
> balance queries
> * Fast synchronization of the Bitcoin blockchain (~2.5 hours for ~185GB @
> June 2018) on modest hardware [7]
> * Low CPU & memory usage (after initial indexing)
> * Low index storage overhead (~20%), relying on a local full node for
> transaction retrieval
> * Efficient mempool tracker allowing better fee estimation [8].
> * `-txindex` is not required for the Bitcoin node
> * Uses `rust-bitcoin` library [9] for efficient
> serialization/deserialization of Bitcoin transactions
> * Uses a single RocksDB [10] database, for better consistency and crash
> recovery
>
> Hope you'll find it useful :)
> Questions, suggestions and pull requests are welcome!
>
> [1] https://github.com/kyuupichan/electrumx
> [2] https://github.com/chris-belcher/electrum-personal-server
> [3] https://github.com/jonasschnelli/bitcoincore-indexd
> [4] https://github.com/romanz/electrs/blob/master/doc/schema.md
> [5] https://electrum.org
> [6] https://electrumx.readthedocs.io/en/latest/protocol.html
> [7] https://gist.github.com/romanz/cd9324474de0c2f121198afe3d063548
> [8]
> https://github.com/spesmilo/electrum/blob/59c1d03f018026ac301c4e74facfc64da8ae4708/RELEASE-NOTES#L34-L46
> )
> [9] https://github.com/rust-bitcoin/rust-bitcoin
> [10] https://github.com/spacejam/rust-rocksdb
> _______________________________________________
> 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/20180705/6c5cd00e/attachment.html>

2023-06-07 20:12:44

- reply

📅 Original date posted:2018-06-05
📝 Original message:>
> I don't understand this comment. The bandwidth gains are not from
> address reuse, they are from the observed property that false
> positives are independent between two filters. I.e. clients that
> connect once a day will probably download 2-3 filters at most, if they
> had nothing relevant in the last ~144 blocks.
>
Your multi-layer digest proposal (https://bc-2.jp/bfd-profile.pdf) uses a
different type of filter which seems more like a compressed Bloom filter if
I understand it correctly. Appendix A shows how the FP rate increases with
the number of elements.
With the Golomb-Coded Sets, the filter size increases linearly in the
number of elements for a fixed FP rate. So currently we are targeting an
~1/2^20 rate (actually 1/784931 now), and filter sizes are ~20 bits * N for
N elements. With a 1-layer digest covering let's say 16 blocks, you could
drop the FP rate on the digest filters and the block filters each to ~10
bits per element, I think, to get the same FP rate for a given block by
your argument of independence. But the digest is only half the size of the
16 combined filters and there's a high probability of downloading the other
half anyway. So unless there is greater duplication of elements in the
digest filters, it's not clear to me that there are great bandwidth
savings. But maybe there are. Even so, I think we should just ship the
block filters and consider multi-layer digests later.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180605/1d6de3bd/attachment.html>

2023-06-07 20:12:44

- reply

📅 Original date posted:2018-06-04
📝 Original message:>
> I was wondering why this multi-layer multi-block filter proposal isn't
> getting any comment,
> is it because not asking all filters is leaking information?
>
It's an interesting idea, but it adds more complexity to the client and
could be added later on if clients adopt BIP 157 and complain about
bandwidth. It also derives all bandwidth gains from address reuse. So I'm
hesitant to make the complexity tradeoff for bandwidth savings due to a
behavior that is actively discouraged.
On another note, I've been thinking that block TXO commitments could
resolve the issue we are facing now with deciding between the prev script
approach and outpoint. The whole argument for outpoints is that there are
compact-ish (<1 MiB) proofs of filter validity, which is not currently
possible if the filters included prev output data. Such proofs would be
feasible if blocks headers (well, actually coinbase txs) had a commitment
to the Merkle root of all newly created outputs in the block.
This idea has been tossed around before in the context of fraud proofs and
TXO bitfields, and seems to unlock a whole bunch of other P2P commitments.
For example, if we wanted to do P2P commitments (BIP 157-style) to the
distribution of tx fees in a block, one could use block TXO commitments to
prove correctness of fees for non-segwit txs. It also enables block
validity proofs (assuming parent blocks are valid), which are not as
powerful as invalidity/fraud proofs, but interesting nonetheless.
This would require a new getdata type BLOCK_WITH_PREVOUTS or something. I
assume for most coinbase-tx-committed proposals, we'll also need a new
getcoinbases/coinbases that requests the coinbase tx and Merkle branch for
a range of headers as well. But with these additions, we could start
serving more block-derived data to light clients under the BIP 157
at-least-one-honest-peer assumption.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180604/ec43b862/attachment-0001.html>

2023-06-07 20:12:38

- reply

📅 Original date posted:2018-06-01
📝 Original message:To address the at-least-one-honest peer security assumption for light
clients, I think this is a rather good security model for light clients.
First it significantly reduces the chances that an attacker can eclipse a
client just by chance, and clients can implement measures like ensuring
connectivity to peers from different subnets. But even if, as you suggest,
a network attacker controls the target's local network, peers still can
have good security guarantees by requiring authenticated connections to
semi-trusted peers. A client can select a set of N servers that it believes
will not collude to attack it, and only sync filters if connected to a
threshold of them. So even if the network is malicious, the attacker cannot
forge the authenticated responses. The level of trust in these designated
parties again is quite low because only one has to be honest. This would
require something like BIP 150.
Even if clients are uncomfortable with whitelisting required peers, it
could have a policy of requiring a certain number of connections to peers
that have honestly served it filters in the past. This is sort of like
trust-on-first-use. This type of scheme, however, would require nodes to
advertise a pubkey per address, which BIP 150/151 does not support at
present.
All in all, I think this is an acceptable security model for light clients.
Without the ability to verify filter validity, a client would have to stop
syncing altogether in the presence of just one malicious peer, which is
unacceptable.
The other concern you raise, Greg, is using a filter for P2P communications
that we expect may be replaced in the future. You also raise the point that
full node wallets can use the smaller filters for rescans because the
filter validity is not in question. I'd perfectly fine with the idea of
defining two filter types in the BIP, one that is output script + outpoint
and the other output script + prev script. But I imagine some people would
object to the idea of full nodes storing two different filters that overlap
in contents. If we had to pick just one though, I'm strongly in support of
output script + outpoint so that BIP 157 can be deployed ASAP without a
consensus change. It's entirely possible we will learn even more about
optimal filter design through deployment and adoption.
On Fri, Jun 1, 2018 at 5:22 PM Gregory Maxwell <greg at xiph.org> wrote:
> On Sat, Jun 2, 2018 at 12:01 AM, Olaoluwa Osuntokun <laolu32 at gmail.com>
> wrote:
> >> A typical network attacker (e.g. someone on your lan or wifi segmet, or
> >> someone who has compromised or operates an upstream router) can be all
> of
> >> your peers.
> >
> > This is true, but it cannot make us accept any invalid filters unless the
> > attacker is also creating invalid blocks w/ valid PoW.
>
> I wish that were the true, but absent commitments that wouldn't be the
> case unless you were always downloading all the blocks-- since you
> wouldn't have any sign that there was something wrong with the
> filter-- and downloading all the blocks would moot using the filters
> in the first place. :)
>
> Or have I misunderstood you massively here?
>
> For segwit originally I had proposed adding additional commitments
> that would make it possible to efficiently prove invalidity of a
> block; but that got stripped because many people were of the view that
> the "assume you have at least one honest peer who saw that block and
> rejected it to tell you that the block was invalid" security
> assumption was of dubious value. Maybe it's more justifiable to make
> use of a dubious assumption for a P2P feature than for a consensus
> feature? Perhaps, I'd rather have both filter types from day one so
> that things not implementing the comparison techniques don't get the
> efficiency loss or the extra work to change filter types for a
> consensus one.
>
> [I think now that we're much closer to a design that would be worth
> making a consensus committed version of than we were a few months ago
> now, since we are effectively already on a second generation of the
> design with the various improvements lately]
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180601/b99c927d/attachment-0001.html>

2023-06-07 20: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 20:12:28

- reply

📅 Original date posted:2018-05-23
📝 Original message:I decided to look into the metrics around compression ratios of TXO
bitfields, as proposed by Bram Cohen [1]. I'm specifically interested in
the feasibility of committing to them with block headers. In combination
with block commitments to TXOs themselves, this would enable UTXO
inclusion/exclusion proofs for light clients.
First, looking just at proofs of inclusion in the UTXO set, each block
needs what Bram calls a "proof of position." Concretely, one such
construction is a Merkle root over all of the block's newly created coins,
including their output data (scriptPubKey + amount), the outpoint (txid +
index), and an absolute index of the output in the entire blockchain. A
Merkle branch in this tree constitutes a proof of position. Alternatively,
the "position", rather than being an absolute index in the chain, could be
a block hash plus an output index within the block.
Let's say we use the absolute index in the chain as position. A TXO
spentness bitfield can be constructed for the entire chain, which is added
to when new coins are created and modified when they are spent. In order to
compactly prove spentness in this bitfield to a client, one could chunk up
the bitfield and construct a Merkle Mountain Range [2] over the chunks.
Instead of building an MMR over outputs themselves, as proposed by Peter
Todd [3], an MMR constructed over bitfield chunks grows far slower, by a
large constant factor. Slower growth means faster updates.
So there's the question of how much these bitfields can be compressed. We
expect some decent level because patterns of spending coins are very
non-random.
The top graph in the attached figure shows the compression ratios possible
on a TXO bitfield split into 4 KiB chunks, using gzip (level=9) and lz4.
Data was collected at block height 523,303. You can see that the
compression ratio is much lower for older chunks and is worse for more
recent blocks. Over the entire history, gzip achieves 34.4%, lz4 54.8%, and
bz2 37.6%. I'm kind of surprised that the ratios are not lower with
off-the-shelf algorithms. And that gzip performs better than bz2 (it seems
to be a factor of the chunk size?).
Alternatively, we can look at bitfields stored separately by block, which
is more compatible with constructions where an output's position is its
block hash plus relative index. The per-block bitfield sizes are shown in
the bottom graph. The compression ratios overall are 50% for gzip, 70% for
lz4, and 61.5% for bz2.
[1]
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-March/013928.html
[2]
https://github.com/opentimestamps/opentimestamps-server/blob/master/doc/merkle-mountain-range.md
[3] https://petertodd.org/2016/delayed-txo-commitments
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180523/8e1272fd/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bitfield_sizes.svg
Type: image/svg+xml
Size: 1788184 bytes
Desc: not available
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180523/8e1272fd/attachment-0001.svg>

2023-06-07 20:12:17

- reply

📅 Original date posted:2018-05-28
📝 Original message:> Is there an application that requires watching for output scripts that
> doesn't also require watching for input scrips (or, less efficiently,
> input outpoints)?
>
Certain wallets may be able to use only the output script filter by using
output scripts to watch for confirmations on sent transactions, assuming
that application is the only one with access to the private keys. The
additional benefit of the input script/outpoint filter is to watch for
unexpected spends (coins getting stolen or spent from another wallet) or
transactions without a unique change or output address. I think this is a
reasonable implementation, and it would be nice to be able to download that
filter without any input elements.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180528/8fdc2ff6/attachment.html>

2023-06-07 20: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 20: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 20: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 20: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 20: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 20:11:45

- reply

📅 Original date posted:2018-05-01
📝 Original message:OK, I see what you are saying. You are effectively suggesting pipelining
the broadcasts of the update transactions. I think this introduces a
problem that a node in the circuit that withholds the preimage for too long
can force all upstream channels to be closed, at only the expense of their
one upstream channel being closed. I believe such an attack could
significantly disrupt the network.
Let me elaborate on the way I'm thinking about this:
So say I'm a routing node with an upstream HTLC with CLTV = X. I need to
ensure that if I learn the preimage, that I have time to broadcast and
confirm an HTLC-success transaction before height X. We'll call this number
of blocks D_success. So if I know the preimage, let's say X - D_success is
the latest height that I can safely broadcast the HTLC-success transaction,
assuming the settlement transaction is already final (ie. the update
transaction is confirmed and the CSV delay has passed). So now I also need
to know when to close the channel with the update transaction. I'll assume
it will take at most D_update blocks from the time I broadcast the update
transaction for it to be mined. So unless the downstream HTLC is already
failed, I should always close the upstream channel at height X - D_success
- CSV_update - D_update.
Now we'll look at the downstream HTLC with CLTV = Y. In order to minimize
the safe delta between the upstream and downstream CLTVs, I will want to
broadcast and confirm an HTLC-timeout transaction as soon after height Y as
possible. So assuming that the downstream settlement transaction is final
at height Y and it takes at most D_timeout blocks for the HTLC timeout
transaction to confirm once it is final assuming no double spends, then Y +
D_timeout is very latest I might learn the payment preimage from the
downstream channel on-chain. So I should be safe as long as X - D_success >
Y + D_timeout. This assumes that the update transaction for the downstream
channel is already mined and the CSV has passed. However, we know from
above that I had to close the upstream channel at time X - D_success -
CSV_update - D_update, which may very well be before Y. So if the
downstream hop waits until just before Y to publish the preimage, they can
force me to close my upstream channel. This applies transitively for
further upstream hops, assuming a large enough CSV value.
Granted, upstream hops can watch the blockchain for preimage reveals in
other closings transaction and perhaps fulfill off-chain if there is
sufficient time. This would not be possible with payment decorrelation
through scriptless scripts or the like.
Does that logic sound right to you?
On Tue, May 1, 2018 at 10:31 AM, Christian Decker <
decker.christian at gmail.com> wrote:
> Jim Posen <jim.posen at gmail.com> writes:
> > I'm still not following why this doesn't accumulate.
> >
> > In the example route, let's look at it from the point of view of C. C
> sees
> > the following regardless of whether D or E or someone behind E is the
> last
> > hop in the route:
> >
> > B -> HTLC(expire = X + delta) -> C -> HTLC(expire = X) -> D
> >
> > So D is not required to reveal the preimage before time X, and in the
> case
> > of an on-chain settle, C needs to be able to redeem the HTLC output
> through
> > the timeout clause before time X + delta. C can't redeem the HTLC (with
> > sufficient confirmations) at least until the settlement transaction is
> > confirmed. So it seems to me that regardless of the overall route and the
> > maximum CSV on it, the delta for the C hop has to be greater than the CSV
> > delay on the update transaction. And that this must be true at every hop
> > for the same reason.
>
> That'd be a purely reactionary behavior, i.e., chosing the delta in such
> a way that I can both settle the channel and have enough time to react
> to turn around and reveal the preimage. So with the assumptions we had
> before (CSV = 144 and CLTV delta = 144) you'd have an effective delta of
> 288 on each hop, yes. That's basically the case in which each channel
> reacts serially.
>
> You can trivially parallelize these closures by looking ahead and
> noticing that each hop really just cares about its own closure deadline,
> i.e., each node just cares to close 288 blocks before the CLTV expires,
> not that its delta w.r.t. to the downstream channel is that far in the
> future. So all we care about is that once we are due to give the
> upstream hop the preimage we've already closed the downstream channel
> and can now read the HTLC preimage from that channel.
>
> The CSV timeout isn't part of the delta on each hop, but we need to
> implement the deadline computation as:
>
> ```
> CLTV - CLTV delta - CSV
> ```
>
> instead of LN-penaltiy's
>
> ```
> CLTV - CLTV delta
> ```
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180501/91de4f67/attachment-0001.html>

2023-06-07 20:11:27

- reply

📅 Original date posted:2018-04-03
📝 Original message:Hey. This idea sounds quite interesting. It'd be helpful to see some more
numbers to evaluate it.
- How much bandwidth is consumed by redundant tx INVs currently? What is
this as a % of overall bandwidth usage?
- How would filtering txs through N=2 links affect network propagation?
This probably requires simulation to determine.
- Do you propose setting filters on inbound peers as well?
On Mon, Apr 2, 2018 at 3:18 PM, Gleb Naumenko via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Hi all,
> I have a couple of ideas regarding transaction relay protocol and wanted
> to share it with and probably get some feedback.
>
> I did some emulation and simulation and found out that around 90% of INV
> messages sent by public-IP nodes are idle (duplicate), obviously because
> each node creates 8 connections. I also realized that sending INV messages
> is a significant part of the overall bandwidth consumed by a public-IP
> node. At a larger scale, this will result in people not able to run a
> public-IP node.
>
> My idea is in some sense similar to BIP37 but applied to public-IP nodes.
> Here I want to emphasize that all the nodes will still receive *all* of the
> transactions. A new protocol should also keep the same zero-trust,
> robustness, decentralization guarantees and latency.
>
> Idea: while joining the network, a new node agrees on some filter with
> each of 8 nodes it connects to. So that NewNode <-> Node_A will be used to
> relay only a subset of transactions, NewNode <-> Node_B for another subset.
> This will significantly decrease the redundancy.
>
> To keep the guarantees, I would keep some redundancy (for example, each
> transaction INV is sent over 2 links).
>
> To make it robust to attacks, I have 2 extensions in my mind:
> 1. Set reconciliation (for a subset of transactions) with *other* nodes.
> Getting a bloom filter of a subset of the mempool transactions from Node_B
> may help to figure out whether Node_A is malicious, very slow, etc.
> 2. Rotating the filters every N minutes (N < 10)
>
> I can see some issues with latency here, but I believe this problem has a
> solution.
>
> Feedback is appreciated!
>
> If you want to look at a draft of the proposal — please let me know.
> If there were any similar ideas — please let me know.
>
> Best,
> Gleb
>
>
> _______________________________________________
> 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/20180403/89d5a284/attachment.html>

2023-06-07 20:11:23

- reply

📅 Original date posted:2018-03-27
📝 Original message:Based on some ideas that were thrown around in this thread (
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-December/015385.html),
I have been working on a P2P extension that will allow faster header sync
mechanisms. The one-sentence summary is that by encoding headers more
efficiently (eg. omitting prev_hash) and downloading evenly spaced
checkpoints throughout history (say every 1,000th) from all peers first, we
could speed up header sync, which would be a huge improvement for light
clients. Here is a draft of the BIP:
https://github.com/jimpo/bips/blob/headers-sync/headersv2.mediawiki. The
full text is below as well.
I'd love to hear any feedback people have.
----------------------------------------------------------
== Abstract ==
This BIP describes a P2P network extension enabling faster, more
reliable methods for syncing the block header chain. New P2P messages
are proposed as more efficient replacements for
<code>getheaders</code> and <code>headers</code> during initial block
download. The proposed header download protocol reduces bandwidth
usage by ~40%-50% and supports downloading headers ranges from
multiple peers in parallel, which is not possible with the current
mechanism. This also enables sync strategies with better resistance to
denial-of-service attacks.
== Motivation ==
Since 2015, optimized Bitcoin clients fetch all block headers before
blocks themselves in order to avoid downloading ones that are not part
of the most work chain. The protocol currently in use for fetching
headers leaves room for further optimization, specifically by
compressing header data and downloading more headers
simulaneously<ref>https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-December/015385.html</ref>.
Any savings here should have a large impact given that both full nodes
and light clients must sync the header chain as a first step, and that
the time to validate and index the headers is negligible compared to
the time spent downloading them from the network. Furthermore, some
current implementations of headers syncing rely on preconfigured
checkpoints to discourage attackers attempting to fill up a victim's
disk space with low-work headers. The proposed messages enable sync
strategies that are resilient against these types of attacks. The P2P
messages are designed to be flexible, supporting multiple header sync
strategies and leaving room for future innovations, while also
compact.
== Definitions ==
''double-SHA256'' is a hash algorithm defined by two invocations of
SHA-256: <code>double-SHA256(x) = SHA256(SHA256(x))</code>.
== Specification ==
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119.
=== New Structures ===
==== Compressed Headers ====
Bitcoin headers are serialized by default in 80 bytes as follows:
{| class="wikitable"
! Field Name
! Data Type
! Byte Size
! Description
|-
| version
| int32_t
| 4
| Block version information
|-
| prev_block
| uint256
| 32
| The hash of the previous block
|-
| merkle_root
| uint256
| 32
| The root hash of the transaction Merkle tree
|-
| timestamp
| uint32_t
| 4
| A Unix timestamp of the block creation time, as reported by the miner
|-
| bits
| uint32_t
| 4
| The calculated difficulty target for this block
|-
| nonce
| uint32_t
| 4
| A nonce that is set such that the header's hash matches the difficulty target
|}
When deserializing a correctly-formed sequence of block headers
encoded in this way, it can be noted that:
* The prev_block field should always match the double-SHA256 hash of
the previous header, making it redundant
* According to Bitcoin consensus rules, the bits field only changes
every 2016 blocks
* The version often matches that of a recent ancestor block
* The timestamp is often a small delta from the preceding header's timestamp
To take advantage of these possible savings, this document defines a
variable-sized ''compressed encoding'' of block headers that occur in
a range. Note that no savings are possible when serializing a single
header; it should only be used for vectors of sequential headers. The
full headers are reconstructed using data from previous headers in the
range. The serialization begins with an ''encoding indicator'', which
is a bitfield specifying how each field is serialized. The bits of the
indicator have the following semantics:
{| class="wikitable"
! Bit Index
! Reconstruction
! Description
|-
| 0
| <code>prev_block[i] = DSHA256(header[i-1])</code>
| The prev_block field is ommitted and assigned to the double-SHA256
hash of the previous uncompressed header.
|-
| 1
| <code>nbits[i] = nbits[i-1]</code>
| The nbits field is omitted and matches that of the previous header.
|-
| 2
| <code>timestamp[i] = timestamp[i-1] + value</code>
| The timestamp is replaced by a 2-byte signed short int, representing
an offset from the previous block's timestamp
|-
| 3
|
| Interpreted along with bits 4 & 5.
|-
| 4
|
| Interpreted along with bits 3 & 5.
|-
| 5
| <code>version[i] = version[i - ((bit[3] << 2) + (bit[4] << 1) +
bit[5])]</code>
| Bits 3, 4, and 5 are first interpreted as a 3-bit offset, with bit
index 3 as the most significant and bit index 5 as the least
significant. If the offset is non-zero, the version field is omitted
and assigned to the version of the block at the offset number of
blocks prior.
|-
| 6
|
| Reserved.
|-
| 7
|
| Reserved. May be used in a future encoding version to signal another
indicator byte.
|}
The compressed header format is versioned by a 256-bit unsigned
integer. This document defines version 0.
==== VarInt ====
''VarInt'' is a variable-length unsigned integer encoding that
supports a greater range of numbers than the standard ''CompactSize''.
This encoding was introduced at the database layer in Bitcoin
Core<ref>https://github.com/bitcoin/bitcoin/commit/4d6144f97faf9d2a6c89f41d7d2360f21f0b71e2</ref>
in 2012, but is new to the Bitcoin P2P layer.
This definition is per the code comments in Bitcoin Core written by
Pieter Wuille:
<pre>
Variable-length integers: bytes are a MSB base-128 encoding of the number.
The high bit in each byte signifies whether another digit follows. To make
the encoding is one-to-one, one is subtracted from all but the last digit.
Thus, the byte sequence a[] with length len, where all but the last byte
has bit 128 set, encodes the number:
(a[len-1] & 0x7F) + sum(i=1..len-1, 128^i*((a[len-i-1] & 0x7F)+1))
Properties:
* Very small (0-127: 1 byte, 128-16511: 2 bytes, 16512-2113663: 3 bytes)
* Every integer has exactly one encoding
* Encoding does not depend on size of original integer type
* No redundancy: every (infinite) byte sequence corresponds to a list
of encoded integers.
0: [0x00] 256: [0x81 0x00]
1: [0x01] 16383: [0xFE 0x7F]
127: [0x7F] 16384: [0xFF 0x00]
128: [0x80 0x00] 16511: [0x80 0xFF 0x7F]
255: [0x80 0x7F] 65535: [0x82 0xFD 0x7F]
2^32: [0x8E 0xFE 0xFE 0xFF 0x00]
</pre>
==== Checkpoints ====
A ''checkpoint'' is defined for a block as a tuple of its hash and the
chain work:
{| class="wikitable"
! Field Name
! Data Type
! Byte Size
! Description
|-
| block_hash
| uint256
| 32
| The hash of the block
|-
| chain_work
| VarInt
| Variable(1-20)
| A delta between the total work in the chain at the checkpoint block
and a previous checkpoint, determined by context
|}
=== Service Bit ===
This BIP allocates a new service bit:
{| class="wikitable"
|-
| NODE_HEADERS_V2
| <code>1 << ?</code>
| If enabled, the node MUST respond to <code>getcheckpts</code> and
<code>getheaders2</code> queries
|}
=== New Messages ===
==== getcheckpts ====
<code>getcheckpts</code> is used to request block headers at a
specified distance from each other which serve as checkpoints during
parallel header download. The message contains the following fields:
{| class="wikitable"
! Field Name
! Data Type
! Byte Size
! Description
|-
| block_locator
| uint256[]
| Variable
| A vector of block hashes in descending order by height used to
identify the header chain of the requesting node
|-
| interval
| uint32_t
| 4
| The distance in block height between requested block hashes
|}
# Nodes SHOULD NOT send <code>getcheckpts</code> unless the peer has
set the <code>NODE_HEADERS_V2</code> service bit
# The hashes in <code>block_locator</code> MUST be in descending order
by block height
# The block locator SHOULD be generated as it is in
<code>getheaders</code> requests
# The receiving node MUST respond to valid requests with a
<code>checkpts</code> response where the interval is the same as in
the request and the first checkpoint hash matches the first common
block hash in the block locator
==== checkpts ====
<code>checkpts</code> is sent in response to <code>getcheckpts</code>,
listing block hashes at the specified interval. The message contains
the following fields:
{| class="wikitable"
! Field Name
! Data Type
! Byte Size
! Description
|-
| start_height
| uint32_t
| 4
| The height of the first block in the active chain matching the
request's block locator
|-
| end_height
| uint32_t
| 4
| The height of the last block in the active chain
|-
| start_checkpoint
| Checkpoint
| 48
| The checkpoint structure for the block in the active chain at height
start_height
|-
| end_checkpoint
| Checkpoint
| 48
| The checkpoint structure for the block in the active chain at height
end_height
|-
| interval
| uint32_t
| 4
| The distance in block height between checkpoints
|-
| checkpoints_length
| CompactSize
| Variable(1-5)
| The number of checkpoints to follow
|-
| checkpoints
| Checkpoint[]
| checkoints_length * Variable(33-52)
| The checkpoints as specified below
|}
# The interval SHOULD match the field in the <code>getcheckpts</code> request
# The start_checkpoint SHOULD correspond to the first block hash in
the locator from the <code>getcheckpts</code> request that is part of
the active chain
# The end_checkpoint SHOULD correspond to the tip of the node's active chain
# The start_height MOST be set to the block height of the start_checkpoint
# The end_height MOST be set to the block height of the end_checkpoint
# If the interval is zero, the checkpoints vector MUST be empty
# If the interval is non-zero, checkpoints MUST correspond to blocks
on the active chain between the start_checkpoint and the
end_checkpoint (exclusive), where the difference in block height
between each entry and the previous one is equal to the interval
# The checkpoints_length MUST be less than or equal to 2,000
# The node SHOULD include as many checkpoints on its active chain as
are available, up to the limit of 2,000
# The chain_work field in the first checkpoint MUST be the total work
in the chain ending at that block
# The chain_work field in each subsequent checkpoint MUST be the
difference in chain work between that block and the previous
checkpoint
# The chain_work field in each checkpoint MUST be a properly-encoded
VarInt, not exceeding 20 bytes
==== getheaders2 ====
<code>getheaders2</code> is used to request compressed headers for a
range of blocks. The message contains the following fields:
{| class="wikitable"
! Field Name
! Data Type
! Byte Size
! Description
|-
| max_version
| uint8_t
| 1
| The maximum supported encoding version of the headers
|-
| flags
| uint8_t
| 1
| A bitfield of message encoding flags
|-
| start_height
| uint32_t
| 4
| The height of the first block header in the requested range
|-
| end_hash
| uint256
| 32
| The hash of the last block header in the requested range
|}
# Nodes SHOULD NOT send <code>getheaders2</code> unless the peer has
set the <code>NODE_HEADERS_V2</code> service bit
# The height of the block with hash end_hash MUST be greater than or
equal to start_height, and the difference MUST be strictly less than
3,000
# The end_hash SHOULD match one in a previously received
<code>checkpts</code> message, otherwise the receiving node MAY
disconnect
# The 0th bit (least significant order) of the flags field MAY be set
to request the coinbase transaction and merkle branch for the block at
height start_height
==== headers2 ====
<code>headers2</code> is sent in response to <code>getheaders2</code>,
listing the compressed headers in the requested range. The message
contains the following fields:
{| class="wikitable"
! Field Name
! Data Type
! Byte Size
! Description
|-
| version
| uint8_t
| 1
| The encoding version of the headers
|-
| flags
| uint8_t
| 1
| A bitfield of message encoding flags
|-
| start_height
| uint32_t
| 4
| The height of the first block header returned
|-
| headers_length
| CompactSize
| 1-3
| The number of block headers to follow
|-
| headers
| CompressedHeader[]
| Variable
| The compressed block headers
|-
| start_block_coinbase_tx
| CTransaction
| Variable
| The coinbase transaction in the block at start_height
|-
| start_block_coinbase_branch
| uint256[]
| Variable
| A merkle branch linking the coinbase transaction in the block at
start_height to its header
|}
# The version MUST be less than or equal to the max_version field of
the <code>getheaders2</code> request
# Any bits set in the flags field of the <code>getheaders2</code>
request MAY be set in the response field
# Any bits not set in the flags field of the <code>getheaders2</code>
request MUST NOT be set in the response field
# The first header MUST be encoded with a 0-byte indicator (ie. the
header is uncompressed)
# start_height MUST be set to the block height of the first header
# The hash of the last block SHOULD equal the end_hash of the
<code>getheaders2</code> request, ''even if the block is no longer
part of the active chain''
# The length of the headers vector MUST be less than or equal to 3,000
# The headers MUST be sequential in order of height, with each header
a successor of the previous one
# Each header SHOULD be optimally compressed
# The start_block_coinbase_tx should be the serialized coinbase
transaction in the block corresponding to the first header
# The start_block_coinbase_branch should be a vector of
right-hand-side hashes in the merkle branch linking the coinbase
transaction to the first header, in order from bottom of the tree to
top
# If the 0th bit (least significant order) of the flags field is
unset, the start_block_coinbase_tx and start_block_coinbase_branch
fields MUST be omitted
=== Sync Strategies ===
The general header sync protocol for clients now is to first request
checkpoints from all peers with <code>getcheckpts</code>, then decide
which peers to fetch ranges of headers from and download them with
<code>getheaders2</code>.
==== Forward Sequential Syncing ====
Similar to the current sync protocol, a client may choose one peer to
download headers from, then fetch them in forward sequential order.
Once this peer is out of headers, the client performs the same routine
with any peers offering more headers.
With this strategy, the client is able to fully validate the block
headers in order and abort if the peer serves an invalid one. On the
other hand, the peer may be able to serve a longer, lower-work chain
than the global active chain, wasting the client's time, memory, and
storage space.
==== Parallel Header Download ====
In order to increase the throughput of header downloads, a node may
download multiple header ranges in parallel from all peers serving the
same checkpoints, then validate them in sequential order.
==== Random Sampling Proof-of-Work ====
Similar the FlyClient<ref>https://www.youtube.com/watch?time_continue=8400&v=BPNs9EVxWrA</ref>
header download protocol, clients can select the peer claiming the
greatest total work chain and use random sampling to efficiently
determine if the peer is likely to be reporting its chain work
honestly.
The client treats the checkpoint message as a commitment to chain work
of intermediate ranges of headers, the client then randomly samples
ranges of headers weighted by total work to determine whether the
total chain work is valid before downloading all headers. To defend
against malicious peers attempting to reuse earlier headers later in
the chain to fake greater total work, the client should check the
block height in the coinbase transaction for all headers after the BIP
34 activation height. If the peer is found to be dishonest, they can
be banned before the client downloads too many headers, otherwise the
client chooses this as the primary sync peer for forward sequential
sync or parallel download.
== Rationale ==
* '''Why include the coinbase transaction in the headers messages?'''
The primary reason is that after BIP
34<ref>https://github.com/bitcoin/bips/blob/master/bip-0034.mediawiki</ref>
activation at block height 227,835, coinbase transactions constitute
cryptographic commitments to a block's height in the chain, which
mitigates certain attacks during header sync. Furthermore, the
<code>getheaders2</code> message can be used as a simple way of
requesting a coinbase transaction for a single header, which may be
independently useful.
* '''Why not omit nBits entirely?''' The compression is designed to
permit full decompression of all headers in a <code>headers2</code>
message ''without'' requiring any other chain context. This is
desirable so that proofs of work may be validated for arbitrary header
ranges. While nBits can be computed knowing previous headers, this
requires block headers that may not be sent in the same message.
== Compatibility ==
This is backwards compatible, as it defines new P2P messages which are
available if a service bit is signaled. There are no changes to
consensus rules.
== Acknowledgements ==
Thanks to Gregory Maxwell for suggestions on the compressed header
encoding and the DOS-resistant sync strategies. Thanks to Suhas
Daftuar for helpful discussions.
Credit for the VarInt encoding goes to Pieter Wuille.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180327/65c9ed79/attachment-0001.html>

2023-06-07 20:08:40

- reply

📅 Original date posted:2017-12-11
📝 Original message:On Mon, Dec 11, 2017 at 1:04 PM, Gregory Maxwell <greg at xiph.org> wrote:
> On Mon, Dec 11, 2017 at 8:40 PM, Jim Posen via bitcoin-dev
> <bitcoin-dev at lists.linuxfoundation.org> wrote:
> > Firstly, I don't like the idea of making the net header encoding
> dependent
> > on the specific header validation rules that Bitcoin uses (eg. the fact
> that
> > difficulty is only recalculated every 2016 blocks). This would be
> coupling
>
> In the last proposal I recall writing up, there was a one byte flag on
> each header to indicate what was included.
>
>
Is there a link somewhere to that proposal? The only thing I could find was
your forwarded email
<https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014904.html>
on
this thread.
> Nbits _never_ needs to be sent even with other consensus rules because
> its more or less necessarily a strict function of the prior headers.
> This still holds in every clone of Bitcoin I'm aware of; sending it
> with the first header in a group probably makes sense so it can be
> checked independently.
>
> > with insufficient benefit.
>
> another >18% reduction in size beyond the removal of prev. is not
> insubstantial by any means. I don't think it should lightly be
> ignored.
>
>
Omitting nBits entirely seems reasonable, I wrote up a possible
implementation here
<https://github.com/bitcoin/bitcoin/compare/master...jimpo:compact-headers-difficulty>.
The downside is that it is more complex because it leaks into the
validation code. The extra 4 byte savings is certainly nice though.
> Prev omission itself is not, sadly, magically compatible: I am quite
> confident that if there is a bitcoin hardfork it would recover the
> nbits/4-guarenteed always-zero bits of prev to use as extra nonce for
> miners. This has been proposed many times, implemented at least once,
> and the current requirement for mining infrastructure to reach inside
> the coinbase txn to increment a nonce has been a reliable source of
> failures. So I think we'd want to have the encoding able to encode
> leading prev bits.
>
> Many altcoins also change the header structures. If the better thing
> is altcoin incompatible, we should still do it. Doing otherwise would
> competitively hobble Bitcoin especially considering the frequent
> recklessly incompetent moves made by various altcoins and the near
> total lack of useful novel development we've seen come out of the
> clones.
>
> Probably the most important change in a new header message wouldn't be
> the encoding, but it would be changing the fetching mechanism so that
> header sets could be pulled in parallel, etc.
>
> I would rather not change the serialization of existing messages,
> nodes are going to have to support speaking both messages for a long
> time, and I think we already want a different protocol flow for
> headers fetching in any case.
>
Can you elaborate on how parallel header fetching might work? getheaders
requests could probably already be pipelined, where the node requests the
next 2,000 headers before processing the current batch (though would make
sense to check that they are all above min difficulty first).
I'm open to more ideas on how to optimize the header download or design the
serialization format to be more flexible, but I'm concerned that we forgo a
40-45% bandwidth savings on the current protocol for a long time because
something better might be possible later on or there might be a hard fork
that at some point requires another upgrade. I do recognize that supporting
multiple serialization formats simultaneously adds code complexity, but in
this case the change seems simple enough to me that the tradeoff is worth
it.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20171211/995788a9/attachment-0001.html>

2023-06-07 20:08:39

- reply

📅 Original date posted:2017-12-11
📝 Original message:I want to resurrect this thread from August/September because it seems like
a significant improvement for light clients at very little cost. From the
mailing list, it seems like this got stalled in determining how many more
bytes could be save in addition to the prev_block.
The ideas I've gathered from Greg Maxwell's forwarded email are:
1. Omit nBits altogether and have the receiving node determine it from
chain context.
2. Include nBits only on headers with a height that is a multiple of 2016
since it does not change in between.
3. Compress nTime to two bytes by using the bounds on allowed values from
the consensus rules.
I propose just moving ahead with only the exclusion of the prev_block, as
IMO the other savings are not worth the added complexity.
Firstly, I don't like the idea of making the net header encoding dependent
on the specific header validation rules that Bitcoin uses (eg. the fact
that difficulty is only recalculated every 2016 blocks). This would be
coupling together the two layers, breaking net compatibility for some alts,
and possibly making consensus rule changes even more difficult for a
savings with insufficient benefit. So if you buy that argument, I'm not in
favor of #2 or #3.
Option 1 is still viable, though it has some downsides. The implementation
leaks into the validation code, whereas calculating prev_block can occur
just at the net layer (see implementation below). Also, nodes would now be
*required* to sync the header chain from the genesis block, whereas they
had the option of starting from some checkpoint before.
So switching gears, I'd like to ask what the best way to actually implement
this change is. Solutions I can think of are:
1. New headers command name like "cmpctheaders" or "headersv2".
2. Change serialization of existing headers message in a new protocol
version.
3. Change serialization of existing headers message with new service bit.
I wrote up some proof-of-concept implementations in Core a) just omitting
prev_block
<https://github.com/bitcoin/bitcoin/compare/master...jimpo:compact-headers>
and b) omitting nBits as well
<https://github.com/bitcoin/bitcoin/compare/master...jimpo:compact-headers-difficulty>.
If people think a) is reasonable, I'll write up a BIP.
> Hi everyone, the Bitcoin headers are probably the most condensed and
> important piece of data in the world, their demand is expected to grow.
> When sending a stream of continuous block headers, a common case in IBD and
> in disconnected clients, I think there is a possible optimization of the
> transmitted data: The headers after the first could avoid transmitting the
> previous hash cause the receiver could compute it by double hashing the
> previous header (an operation he needs to do anyway to verify PoW). In a
> long stream, for example 2016 headers, the savings in bandwidth are about
> 32/80 ~= 40% without compressed headers 2016*80=161280 bytes with
> compressed headers 80+2015*48=96800 bytes What do you think? In
> OpenTimestamps calendars we are going to use this compression to give
> lite-client a reasonable secure proofs (a full node give higher security
> but isn't feasible in all situations, for example for in-browser
> verification) To speed up sync of a new client Electrum starts with the
> download of a file <https://headers.electrum.org/blockchain_headers>
> ~36MB containing the first 477637 headers. For this kind of clients could
> be useful a common http API with fixed position chunks to leverage http
> caching. For example /headers/2016/0 returns the headers from the genesis
> to the 2015 header included while /headers/2016/1 gives the headers from
> the 2016th to the 4031. Other endpoints could have chunks of 20160 blocks
> or 201600 such that with about 10 http requests a client could fast sync
> the headers
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20171211/86e7642f/attachment.html>