<unnamed>

Public Key

npub1ppn2nhlfdzkw9gw0ytljpef5dpyzsxzw8ffcyykamt32hw6pge0smhs2fw

Profile Code

nprofile1qqsqse4fml5k3t8z588j9lequ56xsjpgrp8r55uzztwa4c4thdq5vhcpz3mhxue69uhhyetvv9ujuerpd46hxtnfduqs6amnwvaz7tmwdaejumr0dsr39mma

Publishing to

relay.snort.social

relay.damus.io

nos.lol

Last Notes

2023-10-03 21:44:19 UTC

- reply

📅 Original date posted:2023-09-29
🗒️ Summary of this message: The author has implemented the MATT challenge protocol in Bitcoin Script and provides a detailed description and instructions on how to run the code. They propose using OP_CHECKCONTRACTVERIFY and OP_CAT opcodes to trace program execution and challenge computations. The next steps involve creating a generic framework for compiling high-level programs into MATT-compatible Bitcoin Scripts.
📝 Original message:
Hi, all!
I've been working on an implementation of the original MATT challenge
protocol[0], with a detailed description of how we go from a
"high-level arbitrary program" to something that can be verified
on-chain in Bitcoin Script.
You can find the write-up here, which also includes instructions of
how to run the code and inspect the transactions using a local block
explorer: https://github.com/halseth/mattlab/blob/main/docs/challenge.md
TLDR; Using the proposed opcode OP_CHECKCONTRACTVERIFY and OP_CAT, we
show to trace execution of the program `multiply` [1] and challenge
this computation in O(n logn) on-chain transactions:
func multiply(x int) int {
i := 0
while {
if i < 8 {
x = x + x
i = i + 1
} else {
break
}
}
return x
}
Next steps would be to make this a generic framework with tools to
automatically compile arbitrary high-level programs down to
MATT-compatible Bitcoin Scripts.
All feedback appreciated!
- Johan
[0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-November/021182.html
[1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-November/021205.html

2023-08-08 14:20:52 UTC

- reply

📅 Original date posted:2023-08-07
🗒️ Summary of this message: The sender thanks Salvatore for the update on taptree verification and offers suggestions on the proposal, including opcode parameter ordering and the deferred amount check.
📝 Original message:
Hi, Salvatore.
Thanks for the update! I like the fact that taptree verification now
can be done on both input and outputs, and having them be symmetrical
also makes the learning curve a bit easier.
I have implemented the updated opcodes in btcd (very rough
implementation)]1] as well as updated the example scripts for
simulating CTV[2] and Coinpools[3].
>From doing this I would again like to offer some suggestions on the proposal.
- For the opcode parameter ordering, it feels unnatural for the two
tweaks (data, taptree) to be separated by the internal key. A more
natural ordering of parameters IMO would be (of course this is all
subjective):
<data> <taptree> <internalkey> <index> <flags> OP_CCV.
If you disagree, I would love some rationale for the ordering you
chose! (looks like you also changed it again after your last post?).
- The deferred amount check seems a bit out of place, and insufficient
at least for the use cases I had in mind. They work well in a vault
setting, where you want to consolidate many outputs into a single new
one, and in 1-input-1-output settings where you want to preserve the
amount exactly. However, for coinpools, CTV with more than one output
and other interesting contracts where you want to split or combine
amounts it won't be powerful enough.
I'm wondering what other use cases you had in mind for the deferred
output amount check? Maybe I have missed something, but if not it
would perhaps be better to leave out the amount preservation check, or
go the extra mile and propose a more powerful amount introspection
machinery.
Cheers,
Johan
[1] - https://github.com/halseth/btcd/pull/1
[2] - https://github.com/halseth/tapsim/blob/8f4ac4d914fde0847c72cd22bdd45a1b7247cadf/examples/matt/ctv2/README.md
[3] - https://github.com/halseth/tapsim/blob/8f4ac4d914fde0847c72cd22bdd45a1b7247cadf/examples/matt/coinpool/README.md
On Sun, Jul 30, 2023 at 11:51 PM Salvatore Ingala via bitcoin-dev
<bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> Hi all,
>
> I have put together a first complete proposal for the core opcodes of
> MATT [1][2].
> The changes make the opcode functionally complete, and the
> implementation is revised and improved.
>
> The code is implemented in the following fork of the
> bitcoin-inquisition repo:
>
> https://github.com/Merkleize/bitcoin/tree/checkcontractverify
>
> Therefore, it also includes OP_CHECKTEMPLATEVERIFY, as in a
> previous early demo for vaults [3].
>
> Please check out the diff [4] if you are interested in the
> implementation details. It includes some basic functional tests for
> the main cases of the opcode.
>
> ## Changes vs the previous draft
>
> These are the changes compared to the initial incomplete proposal:
> - OP_CHECK{IN,OUT}CONTRACTVERIFY are replaced by a single opcode
> OP_CHECKCONTRACTVERIFY (CCV). An additional `flags` parameter allows
> to specify if the opcode operates on an input or an output.
> This also allows inspection of other inputs, that was not possible
> with the original opcodes.
> - For outputs, the default behavior is to have the following deferred
> checks mechanism for amounts: all the inputs that have a CCV towards
> the same output, have their input amounts summed, and that act as a
> lower bound for that output's amount.
> A flag can disable this behavior. [*]
> - A number of special values of the parameters were defined in order
> to optimize for common cases, and add some implicit introspection.
> - The order of parameters is modified (particularly, <data> is at the
> bottom of the arguments, as so is more natural when writing Scripts).
>
> ## Semantics
>
> The new OP_CHECKCONTRACTVERIFY takes 5 parameters from the stack:
>
> <data>, <index>, <pk>, <taptree>, <flags>
>
> The core logic of the opcode is as follows:
>
> "Check if the <index>-th input/output's scriptPubKey is a P2TR
> whose public key is obtained from <pk>, (optionally) tweaked with
> <data>, (optionally) tap-tweaked with <taptree>".
>
> The following are special values of the parameters:
>
> - if <pk> is empty, it is replaced with a fixed NUMS point. [**]
> - if <pk> is -1, it is replaced with the current input's taproot
> internal key.
> - if <index> is -1, it is replaced with the current input's index.
> - if <data> is empty, the data tweak is skipped.
> - if <taptree> is empty, the taptweak is skipped.
> - if <taptree> is -1, it is replaced with the current input's root
> of the taproot merkle tree.
>
> There are two defined flags:
> - CCV_FLAG_CHECK_INPUT = 1: if present, <index> refers to an input;
> otherwise, it refers to an output.
> - CCV_FLAG_IGNORE_OUTPUT_AMOUNT = 2: only defined when _CHECK_INPUT
> is absent, it disables the deferred checks logic for amounts.
>
> Finally, if both the flags CCV_FLAG_CHECK_INPUT and
> CCV_FLAG_IGNORE_OUTPUT_AMOUNT are absent:
> - Add the current input's amount to the <index>-th output's bucket.
>
> After the evaluation of all inputs, it is verified that each output's
> amount is greater than or equal to the total amount in the bucket
> if that output (validation of the deferred checks).
>
> ## Comment
>
> It is unclear if all the special values above will be useful in
> applications; however, as each special case requires very little added
> code, I tried to make the specs as flexible as possible at this time.
>
> With this new opcode, the full generality of MATT (including the fraud
> proofs) can be obtained with just two opcodes: OP_CHECKCONTRACTVERIFY
> and OP_CAT.
> However, additional opcodes (and additional introspection) would
> surely benefit some applications.
>
> I look forward to your comments, and to start drafting a BIP proposal.
>
> Best,
> Salvatore Ingala
>
>
> [*] - Credits go to James O'Beirne for this approach, taken from his
> OP_VAULT proposal. I cherry-picked the commit containing the
> Deferred Checks framework.
> [**] - The same NUMS point suggested in BIP-0341 was used.
>
>
> References:
>
> [1] - https://merkle.fun/
> [2] - https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-November/021182.html
> [3] - https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-April/021588.html
> [4] - https://github.com/bitcoin-inquisition/bitcoin/compare/24.0...Merkleize:bitcoin:checkcontractverify
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-09 13:01:30 UTC

- reply

📅 Original date posted:2020-11-23
📝 Original message:
Hi,
Posting an update to this thread, as we are inching closer to an
implementation in lnd that handles this scenario.
I put up a proposed PR today that attempts to solve this in a
backwards compatible manner:
https://github.com/lightningnetwork/lnd/pull/4795
The gist is that in every state we check that the "worst case fee
leak" is at most the channel reserve. The idea is that there should be
no incentive to perform the attack as described, as the cheating party
will gain at most the channel reserve, but at the same time lose its
channel reserve.
Since this makes small channels unusable at high fee rates (the leaked
fee would exceed the channel reserve for just a few, even a single
HTLC) we also clamp the maximum update_fee we'll send at 10 sat/b (a
configurable value). As an example a 1,000,000 sat channel with a 1%
channel reserve would have space for 6 HTLCs at this fee rate.
> Completely adhering to the bring-your-own-fee model for HTLC-txn sounds better as it splits more fairly fees burden between channel participants.
I totally agree that this sounds like the best solution! AFAICT this
would require a (simple) spec change, but would definitely be a big
win and a simple implementation change when we are doing BYOF on the
HTLC transactions anyway :)
- Johan
On Mon, Sep 14, 2020 at 1:30 AM Antoine Riard <antoine.riard at gmail.com> wrote:
>
> Hi Johan,
>
> > I would be open to patching the spec to disallow update_fee for anchor
> > channels, but maybe we can just add a warning and discourage it.
>
> My initial thinking was just to restrain it for the commitment-level only.
>
> Completely adhering to the bring-your-own-fee model for HTLC-txn sounds better as it splits more fairly fees burden between channel participants. The initiator won't have to pay for the remote's HTLC-txn, especially in periods of high-congestion. A participant shouldn't have to bear the cost of the counterparty choosing to go onchain, as it's mostly a client security parameter ("how many blocks it will take me to confirm ?") or an economic decision ("is this HTLC worthy to claim/expire ?").
>
> One could argue it's increasing the blockspace footprint as you will use one more pair of input-output but if you're paying the feerate that's lawful usage.
>
> Antoine
>
> Le ven. 11 sept. 2020 à 04:15, Johan Torås Halseth <johanth at gmail.com> a écrit :
>>
>> Hi,
>>
>> Very good observation, most definitely not a type of attack I forseen!
>>
>> Luckily, it was the plan to phase out update_fee all along, in favor
>> of only accepting the minimum relay fee (zero fee if/when package
>> relay is a reality). If I understand the scenario correctly, that
>> should mitigate this attack completely, as the attacker cannot impact
>> the intended miner fees on the HTLCs, and could only siphon off the
>> minimal miner fee if anything at all.
>>
>> I would be open to patching the spec to disallow update_fee for anchor
>> channels, but maybe we can just add a warning and discourage it.
>>
>> Johan
>>
>>
>> On Thu, Sep 10, 2020 at 8:13 PM Olaoluwa Osuntokun <laolu32 at gmail.com> wrote:
>> >
>> > Hi Antoine,
>> >
>> > Great findings!
>> >
>> > I think an even simpler mitigation is just for the non-initiator to _reject_
>> > update_fee proposals that are "unreasonable". The non-initiator can run a
>> > "fee leak calculation" to compute the worst-case leakage of fees in the
>> > revocation case. This can be done to day without any significant updates to
>> > implementations, and some implementations may already be doing this.
>> >
>> > One issue is that we don't have a way to do a "soft reject" of an update_fee
>> > as is. However, depending on the implementations, it may be possible to just
>> > reconnect and issue a co-op close if there're no HTLCs on the commitment
>> > transaction.
>> >
>> > As you mentioned by setting proper values for max allowed htlcs, max in
>> > flight, reserve, etc, nodes are able to quantify this fee leak risk ahead of
>> > time, and set reasonable parameters based on their security model. One issue
>> > is that these values are set in stone rn when the channel is opened, but
>> > future iterations of dynamic commitments may allow us to update them on the
>> > fly.
>> >
>> > In the mid-term, implementations can start to phase out usage of update_fee
>> > by setting a minimal commitment fee when the channel is first opened, then
>> > relying on CPFP to bump up the commitment and any HTLCs if needed. This
>> > discovery might very well hasten the demise of update_fee in the protocol
>> > all together as well. I don't think we need to depend entirely on a
>> > theoretical package relay Bitcoin p2p upgrade assuming implementations are
>> > willing to make an assumption that say 20 sat/byte or w/e has a good chance
>> > of widespread propagation into mempools.
>> >
>> > From the perspective of channel safety, and variations of attacks like
>> > "flood & loot", imo it's absolutely critical that nodes are able to update
>> > the fees on their second-level HTLC transactions. As this is where the real
>> > danger lies: if nodes aren't able to get 2nd level HTLCs in the chain in
>> > time, then the incoming HTLC expiry will expire, creating a race condition
>> > across both commitments which can potentially cascade.
>> >
>> > In lnd today, anchors is still behind a build flag, but we plan to enable
>> > it by default for our upcoming 0.12 release. The blockers on our end were to
>> > add support for towers, and add basic deadline aware bumping, both of which
>> > are currently on track. We'll now also look into setting clamps on the
>> > receiver end to just not accept unreasonable values for the fee rate of a
>> > commitment, as this ends up eating into the true HTLC values for both sides.
>> >
>> > -- Laolu
>> >
>> >
>> > On Thu, Sep 10, 2020 at 9:28 AM Antoine Riard <antoine.riard at gmail.com> wrote:
>> >>
>> >> Hi,
>> >>
>> >> In this post, I would like to expose a potential vulnerability introduced by the recent anchor output spec update related to the new usage of SIGHASH_SINGLE for HTLC transactions. This new malleability combined with the currently deployed mechanism of `update_fee` is likely harmful for funds safety.
>> >>
>> >> This has been previously shared with deployed implementations devs, as anchor channels are flagged as experimental it's better to discuss and solve this publicly. That said, if you're currently running experimental anchor channels with non-trusted parties on mainnet, you might prefer to close them.
>> >>
>> >> # SIGHASH_SINGLE and `update_fee` (skip it if you're familiar)
>> >>
>> >> First, let's get started by a quick reminder of the data set committed by signature digest algorithm of Segwit transactions (BIP 143):
>> >> * nVersion
>> >> * hashPrevouts
>> >> * hashSequence
>> >> * outpoint
>> >> * scriptCode of the input
>> >> * value of the output spent by this input
>> >> * nSequence of the input
>> >> * hashOutputs
>> >> * nLocktime
>> >> * sighash type of the signature
>> >>
>> >> Anchor output switched the sighash type from SIGHASH_ALL to SIGHASH_SINGLE | SIGHASH_ANYONECANPAY for HTLC signatures sent to your counterparty. Thus it can spend non-cooperatively its HTLC outputs on its commitment transactions. I.e when Alice broadcasts her commitment transaction, every Bob's signatures on Alice's HTLC-Success/Timeout transactions are now flagging the new sighash type.
>> >>
>> >> Thus `hashPrevouts`, `hashSequence` (ANYONECANPAY) and `hashOutputs` (SINGLE) aren't committed anymore. SINGLE only enforces commitment to the output scriptpubkey/amount at the same index that
>> >> the spending input. Alice is free to attach additional inputs/outputs to her HTLC transaction. This change is aiming to let a single-party bump the feerate of 2nd-stage HTLC transactions in case of mempool-congestion, without counterparty cooperation and thus make HTLC funds safer.
>> >>
>> >> The attached outputs are _not_ encumbered by a revokeable redeemscript for a potential punishment.
>> >>
>> >> That said, anchor ouput spec didn't change disable the current fee mechanism already covering HTLC transactions. Pre/post-anchor channels are negotiating a feerate through `update_fee` exchange, initiated by the channel funder. This `update_fee` can be rejected by the receiver if it's deemed unreasonable compared to your local fee estimator view, but as of today implementations are pretty liberal in their acceptance, admitting a divergence from a scale of 1 to no-bound at all.
>> >>
>> >> This negotiated feerate (`feerate_per_kw`) is used by channel participants to compute effective fees which have to be deduced either from the funder balance output for commitment transactions or from HTLC output value for HTLC transactions.
>> >>
>> >> # The Vulnerability : a Penalty Escape Vector
>> >>
>> >> By increasing the feerate thanks to `update_fee`, a malicious party can inflate fees committed on HTLC input/output pairs and redirect this inflated fee to a single-controlled output attached to these malleable pairs. This won't be punishable by an honest party in case of revoked state broadcast and thus enable to partially escape the penalty.
>> >>
>> >> As an example, Alice and Bob have a 100_000 sats channel. `feerate_per_kw` is 10000 sats.
>> >>
>> >> At state N, Alice balance is all on her side. She announces 10 outgoing HTLCs of value 7000 sats.
>> >>
>> >> As Commitment tx weight with 10 outputs is 2844 (post-anchor), the absolute fee committed is 28440 sats.
>> >>
>> >> As HTLC-timeout weight is 666 (post-anchor), the absolute fee committed is of 6660 sat, the HTLC tx output as counter-signed by Bob is of 340 sat. This absolute fee aims to pay the miner fee in case Alice needs to timeout HTLC onchain.
>> >>
>> >> Her remaining balance is 1560 sat, above both dust_limit_satoshi and the channel reserve as constrained by Bob (likely 1%).
>> >>
>> >> Alice waits for HTLCs to expire and advances state to N+1. Then she empties her balance minus reserve by sending a HTLC relayed by Bob either to a colluding channel on the rest of network or back to an onchain address thanks to a swap service.
>> >>
>> >> At state N+2, Alice finalizes HTLC-timeout of state N by capturing almost all of the absolute fee to a new P2WPKH output only controlled by her. She broadcasts the revoked commitment tx N and burns 28440 sats in commitment fee.
>> >>
>> >> Her balance of 1560 sats is punished by Bob's justice transaction.
>> >>
>> >> After confirmation and thus maturing of the CSV of 1 on her HTLC output Alice broadcasts her 10 HTLC-timeout sending back to her 6660 sat - 660 to pay a low-fee. Bob punishes the 10 HTLC-timeout outputs of 340 sats.
>> >>
>> >> Alice gain = 99_000 (swap spend) + 66_660 (HTLCs escape) - 1560 (commitment balance punishment) - 28440 (commitment fee) - 660*10 (HTLCs fees) - 340*10 (HTLCs output) = 125600 sats.
>> >>
>> >> Alice's gain is superior at channel value as it has been partially double-spend by bypassing the revocation punishment.
>> >>
>> >> # Limitations of Attacker Success
>> >>
>> >> A first limitation of attack success which can be point of is the fact that post-anchor HTLC outputs are CSV'ed by 1, which means in theory a honest party can punish this output before the malicious spend them with the revoked HTLC txn. In practice a malicious party can attach a branch of descendants to its anchor output and that way only allowing one more mempool victim's transaction on the revoked commitment. The victim must spend all outputs at once or otherwise they're going to obstrucate each other at mempool acceptance.
>> >>
>> >> Secondly, other limitations are the per-implementation channel policy `max_accepted_htlcs`, `max_htlc_value_in_flight`, `channel_reserve` and acceptance bound of `update_fee`. A quick look at default policies, even if they vary between deploy implementations, let it think there is room to escape a substantial part of channel value.
>> >>
>> >> Lastly, after the revoked commitment transaction is confirmed, both attacker and victim are in a feerate race to confirm either a justice transaction or a malicious HTLC-timeout. As fee estimator logic of the victim's implementation is a public piece of knowledge, it shouldn't be hard for the attacker to know the range of the first fee bid and override it by a bit to confirm it before the victim RBF at next block. Currently, not all implementations have RBF of justice transactions.
>> >>
>> >> As of today, if anchor output is deployed and given how LN implementations are managing fees/rebroadcast of onchain transactions, the chance of attack success sounds high in my opinion.
>> >>
>> >> # Countermeasures
>> >>
>> >> Channel policies could be tighter, like bounded further down `max_accepted_htlcs` or restraining acceptance of `update_fee`. For the latter, it's pretty hard as a) fee estimators diverge on mempool views b) an attacker can craft escape HTLC-txn in a period of high-fee and patiently waits a low-fee period to launch the exploitation.
>> >>
>> >> Justice transactions can adopt a scorched earth approach binding their feerate to the max to increase odds of winning the feerate race and thus deter attackers. But this sounds like introducing a griefing attack vector. Your counterparty can burn more of your lawful balance in fees than you'll punish its revoked balance.
>> >>
>> >> A workable option would be to patch current anchor spec to remove `feerate_per_kw` appliance on 2nd-stage transactions, maybe just committing a minimal relay fee.
>> >>
>> >> Thoughts of further countermeasures ?
>> >>
>> >> I think the vulnerability described is mostly right but please point any missing details.
>> >>
>> >> Cheers,
>> >>
>> >> Antoine
>> >> _______________________________________________
>> >> 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

2023-06-09 12:56:46 UTC

- reply

📅 Original date posted:2019-10-24
📝 Original message:
Reviving this old thread now that the recently released RC for bitcoind
0.19 includes the above mentioned carve-out rule.
In an attempt to pave the way for more robust CPFP of on-chain contracts
(Lightning commitment transactions), the carve-out rule was added in
https://github.com/bitcoin/bitcoin/pull/15681. However, having worked on an
implementation of a new commitment format for utilizing the Bring Your Own
Fees strategy using CPFP, I’m wondering if the special case rule should
have been relaxed a bit, to avoid the need for adding a 1 CSV to all
outputs (in case of Lightning this means HTLC scripts would need to be
changed to add the CSV delay).
Instead, what about letting the rule be
The last transaction which is added to a package of dependent
transactions in the mempool must:
* Have no more than one unconfirmed parent.
This would of course allow adding a large transaction to each output of the
unconfirmed parent, which in effect would allow an attacker to exceed the
MAX_PACKAGE_VIRTUAL_SIZE limit in some cases. However, is this a problem
with the current mempool acceptance code in bitcoind? I would imagine
evicting transactions based on feerate when the max mempool size is met
handles this, but I’m asking since it seems like there has been several
changes to the acceptance code and eviction policy since the limit was
first introduced.
- Johan
On Wed, Feb 13, 2019 at 6:57 AM Rusty Russell <rusty at rustcorp.com.au> wrote:
> Matt Corallo <lf-lists at mattcorallo.com> writes:
> >>> Thus, even if you imagine a steady-state mempool growth, unless the
> >>> "near the top of the mempool" criteria is "near the top of the next
> >>> block" (which is obviously *not* incentive-compatible)
> >>
> >> I was defining "top of mempool" as "in the first 4 MSipa", ie. next
> >> block, and assumed you'd only allow RBF if the old package wasn't in the
> >> top and the replacement would be. That seems incentive compatible; more
> >> than the current scheme?
> >
> > My point was, because of block time variance, even that criteria doesn't
> hold up. If you assume a steady flow of new transactions and one or two
> blocks come in "late", suddenly "top 4MWeight" isn't likely to get
> confirmed until a few blocks come in "early". Given block variance within a
> 12 block window, this is a relatively likely scenario.
>
> [ Digging through old mail. ]
>
> Doesn't really matter. Lightning close algorithm would be:
>
> 1. Give bitcoind unileratal close.
> 2. Ask bitcoind what current expidited fee is (or survey your mempool).
> 3. Give bitcoind child "push" tx at that total feerate.
> 4. If next block doesn't contain unilateral close tx, goto 2.
>
> In this case, if you allow a simpified RBF where 'you can replace if
> 1. feerate is higher, 2. new tx is in first 4Msipa of mempool, 3. old tx
> isnt',
> it works.
>
> It allows someone 100k of free tx spam, sure. But it's simple.
>
> We could further restrict it by marking the unilateral close somehow to
> say "gonna be pushed" and further limiting the child tx weight (say,
> 5kSipa?) in that case.
>
> Cheers,
> Rusty.
> _______________________________________________
> 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/20191024/065e650f/attachment.html>

2023-06-09 12:56:46 UTC

- reply

📅 Original date posted:2019-10-25
📝 Original message:
It essentially changes the rule to always allow CPFP-ing the commitment as
long as there is an output available without any descendants. It changes
the commitment from "you always need at least, and exactly, one non-CSV
output per party. " to "you always need at least one non-CSV output per
party. "
I realize these limits are there for a reason though, but I'm wondering if
could relax them. Also now that jeremyrubin has expressed problems with the
current mempool limits.
On Thu, Oct 24, 2019 at 11:25 PM Matt Corallo <lf-lists at mattcorallo.com>
wrote:
> I may be missing something, but I'm not sure how this changes anything?
>
> If you have a commitment transaction, you always need at least, and
> exactly, one non-CSV output per party. The fact that there is a size
> limitation on the transaction that spends for carve-out purposes only
> effects how many other inputs/outputs you can add, but somehow I doubt
> its ever going to be a large enough number to matter.
>
> Matt
>
> On 10/24/19 1:49 PM, Johan Torås Halseth wrote:
> > Reviving this old thread now that the recently released RC for bitcoind
> > 0.19 includes the above mentioned carve-out rule.
> >
> > In an attempt to pave the way for more robust CPFP of on-chain contracts
> > (Lightning commitment transactions), the carve-out rule was added in
> > https://github.com/bitcoin/bitcoin/pull/15681. However, having worked on
> > an implementation of a new commitment format for utilizing the Bring
> > Your Own Fees strategy using CPFP, I’m wondering if the special case
> > rule should have been relaxed a bit, to avoid the need for adding a 1
> > CSV to all outputs (in case of Lightning this means HTLC scripts would
> > need to be changed to add the CSV delay).
> >
> > Instead, what about letting the rule be
> >
> > The last transaction which is added to a package of dependent
> > transactions in the mempool must:
> > * Have no more than one unconfirmed parent.
> >
> > This would of course allow adding a large transaction to each output of
> > the unconfirmed parent, which in effect would allow an attacker to
> > exceed the MAX_PACKAGE_VIRTUAL_SIZE limit in some cases. However, is
> > this a problem with the current mempool acceptance code in bitcoind? I
> > would imagine evicting transactions based on feerate when the max
> > mempool size is met handles this, but I’m asking since it seems like
> > there has been several changes to the acceptance code and eviction
> > policy since the limit was first introduced.
> >
> > - Johan
> >
> >
> > On Wed, Feb 13, 2019 at 6:57 AM Rusty Russell <rusty at rustcorp.com.au
> > <mailto:rusty at rustcorp.com.au>> wrote:
> >
> > Matt Corallo <lf-lists at mattcorallo.com
> > <mailto:lf-lists at mattcorallo.com>> writes:
> > >>> Thus, even if you imagine a steady-state mempool growth, unless
> the
> > >>> "near the top of the mempool" criteria is "near the top of the
> next
> > >>> block" (which is obviously *not* incentive-compatible)
> > >>
> > >> I was defining "top of mempool" as "in the first 4 MSipa", ie.
> next
> > >> block, and assumed you'd only allow RBF if the old package wasn't
> > in the
> > >> top and the replacement would be. That seems incentive
> > compatible; more
> > >> than the current scheme?
> > >
> > > My point was, because of block time variance, even that criteria
> > doesn't hold up. If you assume a steady flow of new transactions and
> > one or two blocks come in "late", suddenly "top 4MWeight" isn't
> > likely to get confirmed until a few blocks come in "early". Given
> > block variance within a 12 block window, this is a relatively likely
> > scenario.
> >
> > [ Digging through old mail. ]
> >
> > Doesn't really matter. Lightning close algorithm would be:
> >
> > 1. Give bitcoind unileratal close.
> > 2. Ask bitcoind what current expidited fee is (or survey your
> mempool).
> > 3. Give bitcoind child "push" tx at that total feerate.
> > 4. If next block doesn't contain unilateral close tx, goto 2.
> >
> > In this case, if you allow a simpified RBF where 'you can replace if
> > 1. feerate is higher, 2. new tx is in first 4Msipa of mempool, 3.
> > old tx isnt',
> > it works.
> >
> > It allows someone 100k of free tx spam, sure. But it's simple.
> >
> > We could further restrict it by marking the unilateral close somehow
> to
> > say "gonna be pushed" and further limiting the child tx weight (say,
> > 5kSipa?) in that case.
> >
> > Cheers,
> > Rusty.
> > _______________________________________________
> > Lightning-dev mailing list
> > Lightning-dev at lists.linuxfoundation.org
> > <mailto: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/20191025/58a3d7b8/attachment.html>

2023-06-09 12:54:46 UTC

- reply

📅 Original date posted:2019-04-03
📝 Original message:
Hi Pierre and list folks,
I haven't looked at the technical implications of implementing this in
detail, but I like the high-level direction this proposal is taking :)
I think it nicely ties together several concepts that have been proposed
earlier, and with the correct design could give the sender all the
flexibility needed to craft payments according to its own
reliability/privacy/fee tradeoff.
In an ideal world we would have:
- Multi-hop locks: hop decorrelation will be even more important when the
sender no longer controls the whole payment path.
- Packet switched routing: the sender can choose whether to route purely
packet switched (only knowing the destination, no need to keep any routing
table) or route purely onion-based (as today), or something in between. As
Christian mentions, this is similar to how TOR/TCP works, and I like the
flexibility this layering allows.
- Rendezvous routing: such a proposal would be nice to combine with
rendezvous routing. This way even the sender wouldn't necessarily know if
the "destination node" is just another trampoline. Maybe maybe this concern
shouldn't be on this layer though?
- Fees: (as today) the sender would set the fees it is willing to pay
between trampolines, and it could dynamically learn about fee levels needed
to reach different parts of the network. Today we know the fee needed to
reach the next hop, but here we could start out low (for the
trampoline-to-trampoline fee) and let different trampolines return
competing fee offers to get to the next hop.
As mentioned, I haven't thought about the technical implications of all
this, and it would certainly require a lot of work to get this actually
implemented.
Cheers,
Johan
On Wed, Apr 3, 2019 at 5:42 AM ZmnSCPxj via Lightning-dev <
lightning-dev at lists.linuxfoundation.org> wrote:
> Good morning Pierre and list,
>
> > There is another unrelated issue: because trampoline nodes don't know
> > anything about what happened before they received the onion, they may
> > unintentionnaly create overlapping routes. So we can't simply use the
> > payment_hash as we currently do, we would have to use something a bit
> > more elaborate.
>
> Just to be clear, the issue is for example with a network like:
>
>
> A ------- B -------- C
> / \
> / \
> / \
> / \
> D ------- E
>
> Then, A creates an inner trampoline onion "E->C", and an outer onion
> "A->B->E".
>
> E, on receiving the inner trampoline onion "E->C", finds that E->B
> direction is low capacity, so routes over the outer onion "E->D->B->C" with
> inner trampoline onion "C".
>
> This creates an overall route A->B->E->D->B->C.
>
> When the B->C HTLC is resolved, B can instead claim the A->B HTLC and just
> fail the D->B HTLC, thereby removing D and E from the route and claiming
> their fees, even though they participated in the route.
>
> > (maybe private keys?)
>
> Do you refer to the changing from "H"TLC to "P"TLC point-locked timelocked
> contracts?
> i.e. instead of payment hash / preimage, we use payment point / scalar.
>
> I think a few ideas would be improved by this.
>
> 1. Trampoline payments, as described above.
> 2. Offline vending machines
> - Instead of storing a fixed number of invoices from the always-online
> payment node, store a HD parent point and derive child points for payments.
> 3. Enables payment decorrelation.
>
> Perhaps we should consider switching to payment points/scalars sometime
> soon.
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> 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/20190403/24eb7d58/attachment.html>

2023-06-09 12:52:46 UTC

- reply

📅 Original date posted:2018-11-26
📝 Original message:
This shouldn't be problem, as the invoice will already indicate that the
node supports BaseAMP. If you have a reason to not reveal that you support
BAMP for certain invoices, you'll just not specify it in the invoice, and
act non-BAMPy when receiving payments to this payment hash.
Of course, this will also be opt-in for both sides and won't affect
existing nodes in any way.
Cheers,
Johan
On Wed, Nov 21, 2018 at 11:54 PM Rusty Russell <rusty at rustcorp.com.au>
wrote:
> Johan Torås Halseth <johanth at gmail.com> writes:
> > Seems like we can restrict the changes to BOLT11 by having the receiver
> > assume NAMP for incoming payments < invoice_amount. (with some timeout of
> > course, but that would need to be the case even when the sender is
> > signalling NAMP).
>
> This would effectively become a probe for Base AMP; if you get a partial
> payment error, it's because the recipient didn't support Base AMP.
>
> Seems cleaner to have a flag, both on BOLT11 and inside the onion. Then
> it's explicitly opt-in for both sides and doesn't affect existing nodes
> in any way.
>
> Cheers,
> Rusty.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20181126/67166a9b/attachment.html>

2023-06-09 12:52:40 UTC

- reply

📅 Original date posted:2018-11-13
📝 Original message:
Good evening Z and list,
I'm wondering, since these payments are no longer atomic, should we name it
accordingly?
Cheers,
Johan
On Tue, Nov 13, 2018 at 1:28 PM ZmnSCPxj via Lightning-dev <
lightning-dev at lists.linuxfoundation.org> wrote:
> Good morning list,
>
> I propose the below to support Base AMP.
>
> The below would allow arbitrary merges of paths, but not arbitrary
> splits. I am uncertain about the safety of arbitrary splits.
>
> ### The `multipath_merge_per_hop` type (`option_base_amp`)
>
> This indicates that payment has been split by the sender using Base AMP,
> and that the receiver should wait for the total intended payment before
> forwarding or claiming the payment.
> In case the receiving node is not the last node in the path, then
> succeeding hops MUST be the same across all splits.
>
> 1. type: 1 (`termination_per_hop`)
> 2. data:
> * [`8` : `short_channel_id`]
> * [`8` : `amt_to_forward`]
> * [`4` : `outgoing_cltv_value`]
> * [`8` : `intended_total_payment`]
> * [`4` : `zeros`]
>
> The contents of this hop will be the same across all paths of the Base AMP.
> The `payment_hash` of the incoming HTLCs will also be the same across all
> paths of the Base AMP.
>
> `intended_total_payment` is the total amount of money that this node
> should expect to receive in all incoming paths to the same `payment_hash`.
>
> This may be the last hop of a payment onion, in which case the `HMAC` for
> this hop will be `0` (the same rule as for `per_hop_type` 0).
>
> The receiver:
>
> * MUST impose a reasonable timeout for waiting to receive all component
> paths, and fail all incoming HTLC offers for the `payment_hash` if they
> have not totalled equal to `intended_total_payment`.
> * MUST NOT forward (if an intermediate node) or claim (if the final node)
> unless it has received a total greater or equal to `intended_total_payment`
> in all incoming HTLCs for the same `payment_hash`.
>
> The sender:
>
> * MUST use the same `payment_hash` for all paths of a single multipath
> payment.
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> 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/20181113/6342ecf1/attachment-0001.html>

2023-06-09 12:52:23 UTC

- reply

📅 Original date posted:2018-11-09
📝 Original message:
Neat! I think this is similar to what has been briefly discussed earlier
about hybrid packet-switched/circuit-switched payment routing.
B doesn't have to care about how the payment gets from C to D, but she
knows it must go through D, keeping privacy intact. This would be exactly
equivalent to how TOR works today I would think.
C must also make sure the detour route stays within the fee limit of course.
Cheers,
Johan
On Fri, Nov 9, 2018 at 7:02 AM ZmnSCPxj via Lightning-dev <
lightning-dev at lists.linuxfoundation.org> wrote:
> Good morning list,
>
> As was discussed directly in summit, we accept link-lvel payment splitting
> (scid is not binding), and provisionally accept rendez-vous routing.
>
> It strikes me, that even if your node has only a single channel to the
> next node (c-lightning), it is possible, to still perform link-level
> payment splitting/re-routing.
>
> For instance, consider this below graph:
>
> E<---D--->C<---B
> ^ /
> | /
> |L
> A
>
> In the above, B requests a route from B->C->D->E.
>
> However, C cannot send to D, since the channel direction is saturated in
> favor of D.
>
> Alternately, C can route to D via A instead. It holds the (encrypted)
> route from D to E. It can take that sub-route and treat it as a partial
> route-to-payee under rendez-vous routing, as long as node A supports
> rendez-vous routing.
>
> This can allow re-routing or payment splitting over multiple hops.
>
> Even though C does not know the number of remaining hops between D and the
> destination, its alternative is to earn nothing anyway as its only
> alternative is to fail the routing. At least with this, there is a chance
> it can succeed to send the payment to the final destination.
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> 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/20181109/813c32fc/attachment.html>

2023-06-09 12:51:31 UTC

- reply

📅 Original date posted:2018-09-20
📝 Original message:
I was thinking you could just make many requests to get the same
information, but if you always choose the same channel as long as its
capacity meets the requirement, then not much is learnt :)
On Thu, Sep 20, 2018 at 9:26 AM Christian Decker <decker.christian at gmail.com>
wrote:
> That might not be so desirable, since it leaks the current channel
> capacity to the user. Depending on how fine grained the amount in the
> invoice is and how the user can control it, he could do a binary search
> over capacities and very reliably tell how much capacity you have and
> track it over time. That is still the case for a single channel, but if
> you always chose the same channel it reduces how much info is leaked.
>
> Cheers,
> Christian
>
> Johan Torås Halseth <johanth at gmail.com> writes:
> > Any reason not to include _all_ (up to a limit) incoming channels with
> > sufficient capacity?
> >
> > Cheers,
> > Johan
> >
> > On Thu, Sep 20, 2018 at 4:12 AM Rusty Russell <rusty at blockstream.com>
> wrote:
> >
> >> Hi all,
> >>
> >> I'm considering a change to c-lightning, where `invoice` would
> >> automatically append an 'r' field for a channel which has sufficient
> >> *incoming* capacity for the amount (using a weighted probability across
> >> our peers).
> >>
> >> This isn't quite what 'r' was for, but it would be a useful
> >> hint for payment routing and also potentially for establishing an
> >> initial channel. This is an issue for the Blockstream Store which
> >> deliberately doesn't advertize an address any more to avoid
> >> centralization.
> >>
> >> Thoughts welcome!
> >> 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/20180920/114dfd18/attachment.html>

2023-06-09 12:51:30 UTC

- reply

📅 Original date posted:2018-09-20
📝 Original message:
Any reason not to include _all_ (up to a limit) incoming channels with
sufficient capacity?
Cheers,
Johan
On Thu, Sep 20, 2018 at 4:12 AM Rusty Russell <rusty at blockstream.com> wrote:
> Hi all,
>
> I'm considering a change to c-lightning, where `invoice` would
> automatically append an 'r' field for a channel which has sufficient
> *incoming* capacity for the amount (using a weighted probability across
> our peers).
>
> This isn't quite what 'r' was for, but it would be a useful
> hint for payment routing and also potentially for establishing an
> initial channel. This is an issue for the Blockstream Store which
> deliberately doesn't advertize an address any more to avoid
> centralization.
>
> Thoughts welcome!
> Rusty.
> _______________________________________________
> 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/20180920/83c90ab3/attachment.html>

2023-06-09 12:49:01 UTC

- reply

📅 Original date posted:2018-02-08
📝 Original message:
Yeah, that is true, it would only give you the atomicity, not the decorrelation. I don’t see how you could get all the same properties using only one hash though. I guess the sender has no incentive to claim any of the payments before all of them have arrived, but you get no guarantee that partial payments cannot be made. Seems hard to do without introducing new primitives.
- Johan
On Thu, Feb 8, 2018 at 12:44, Jim Posen <jim.posen at gmail.com> wrote:
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 [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 [rusty at rustcorp.com.au] > wrote:
Olaoluwa Osuntokun < laolu32 at gmail.com [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 [Lightning-dev at lists.linuxfoundation.org]
https://lists.linuxfoundation. org/mailman/listinfo/ lightning-dev [https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev]
______________________________ _________________
Lightning-dev mailing list
Lightning-dev at lists. linuxfoundation.org [Lightning-dev at lists.linuxfoundation.org]
https://lists.linuxfoundation. org/mailman/listinfo/ lightning-dev [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/edbfbd41/attachment-0001.html>

2023-06-09 12:49:00 UTC

- reply

📅 Original date posted:2018-02-08
📝 Original message:
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180208/ec4e6b34/attachment.html>

2023-06-09 12:47:31 UTC

- reply

📅 Original date posted:2017-09-04
📝 Original message:
I haven’t looked too closely at your proposal, but the first thing that hit me (2 weeks ago, sorry for not answering right away), is that instead of the basic flood-the-network-about-channels algorithm that currently is being used, this makes each route discovery request behave more or less like flooding (ask everybody within your local topology)?
Also it will be interesting to see when the network starts developing, I suspect that if you keep every node within 3 hops in your local topology, you end up storing most of the network anyway. So I think the routing algorithms will be far easier to optimize and analyze after some real world data :)
That being said, interesting idea, I’m not dismissing it :D
On Tue, Aug 22, 2017 at 3:08, Billy Tetrud <billy.tetrud at gmail.com> wrote:
Hey Guys,
I'm testing this mailing list out for the first time, so I'm probably gonna be doing it wrong.
I want to talk about route discovery and route generation in the lightning network. It seems there's a couple types of things going on with routing: * Super basic flood-the-network style routing to get things up and running, as I believe is implicitly proposed here: https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md [https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md]
* More involved research projects that may not reach fruition any time soon. Eg this: http://bitfury.com/content/5-white-papers-research/whitepaper_flare_an_approach_to_routing_in_lightning_network_7_7_2016.pdf [http://bitfury.com/content/5-white-papers-research/whitepaper_flare_an_approach_to_routing_in_lightning_network_7_7_2016.pdf]
I'd like to discuss a near-term approach that can replace the basic flood-the-network style route discovery, but isn't so complicated that it needs a ton of study and work. This won't be the end-all solution to route discovery, but should take us a lot further than flood-the-network.
I propose a protocol where each node knows about its own local network topology, and to find a final route, a transaction originator queries a number of its connections for routes to the intended destination. By doing this, it means that nodes are *not* receiving or storing the entire network topology, which makes route discovery a lot less taxing on the network (in terms of bandwidth and storage space).
To go into more detail...
When a node joins the network: 1. it broadcasts its information to all its channels (pretty much as proposed here [https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md] ) announcing its relevant channel information 2. it requests local network topology information from all its channels for information about channels 1 hop beyond its direct connection (ie it will receive information about which addresses those channels are connected to, and their related fee info / etc) 3. it then requests topology information for channels 2 hops beyond, etc until it has filled its cache to its satisfaction (the user can choose some amount of megabytes as its limit of network topology data to store) 4. it also subscribes to topology changes for nodes at those distances (eg if a node has requested information from 3 hops away, it will receive info about any new channels or removed channels that fall within that distance)
When a node receives an announcement message from a node joining the network: 1. it will store that node's info in its cache 2. it will also forward that info to any node that's subscribed to topology changes that fall within the relevant distance
When a node wants to construct a route for a transaction: 1. It checks to see if it has a path to that node in its cache. If it does, it finds the cost of the cheapest path it has. 2. It asks all the channels on the edge of its cached local view for their cheapest path (however you want to define cheapest), specifying that it only care about paths with a maximum cost of the cheapest path it has already found in its cache. For example, if the node has nodes up to 3 hops away in its cache, it will *only* ask the nodes 3 hops away (it will not ask its direct connections, nor nodes 2 hops away, since it already has enough information to ignore them) 3. When it gets all its responses, it constructs a path
When a node receives a path request from a node: 1. It checks its cache for its cheapest cache-only path 2. It asks nodes on the edge of its cached local view for their cheapest path, specifying that it only cares about paths with a maximum cost of either its cheapest cache-only path or the max-cost specified by the requesting node minus the channel cost between it and the requesting node (whichever is cheaper). A node on the edge of its cached local view is *not* asked for route information if the cost to that node exceeds the max-cost this relay node would specify. 3. It reports the results that satisfy the max-cost requirements of the requesting node
And that's it. All the route information can be encrypted and signed so relaying nodes can't read the information inside, and so the requesting source node can verify which nodes sent that information.
This protocol should keep both node-announcement messages *and* route request messages highly localized.
Thoughts?
~BT
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20170904/66bc1247/attachment-0001.html>

2023-06-07 23:21:09 UTC

- reply

📅 Original date posted:2023-05-26
🗒️ Summary of this message: OP_CICV and OP_COCV, along with OP_CAT, enable interesting use cases such as CoinPools, allowing easy checking of input data and enforcing new commitments on output. Suggestions for further extension are proposed.
📝 Original message:Hi, Salvatore.
As a further exploration of this idea, I implemented a
proof-of-concept of OP_CICV and OP_COCV in btcd[1] that together with
OP_CAT enables a set of interesting use cases.
One such use case is, as mentioned earlier, CoinPools[2]. The opcodes
let you easily check the "dynamically committed data" of an input you
are spending, and enforce a new commitment on the output. The idea is
to have the set of participants in the pool, and their balances, be
the UTXOs committed data, and use this to validate the legitimacy of
a transaction, determining whether it permits a peer to exit with a
portion of the pooled funds.
Doing what you suggested above, having the input and output commit to
a merkle tree of participants and balances, we are able to quite
elegantly verify the coin pool exit clause. Here is a working example
of how that could look like: [3]. Obviously this lacks a lot before it
is a working CoinPool implementation, but it demonstrates how
OP_C[I/O]V introduces "memory" to Bitcoin script.
Having done this exercise, I have a few suggestions on how one could
further extend the proposal:
1. In the current proposal for OP_CHECKOUTPUTCONTRACTVERIFY, the
opcodes check whether the output key Q is key X tweaked with data D
and taproot T: Q == tweak(tweak(X,D), T).
OP_CHECKINPUTCONTRACTVERIFY on the other hand, works on the input
internal key, and does not care about the taptree on the input: P ==
tweak(X,D), where Q = tweak(P, T). In most cases this is probably good
enough, since you are already executing the current script and that
way know the spender has provided the correct taproot.
However, in the coin pool script mentioned above, I found that I
wanted to re-use the same taproot for the output (recursively). I
believe this would be a quite common use case. To solve this I
committed the taproot as part of the data itself: D' = hash(T+D),
which was then verified by OP_CICV. If you are aware of more efficient
alternatives, I am eager to hear them.
A simpler way IMO, would be to make OP_CICV and OP_COCV symmetrical:
Have OP_CICV take an optional taproot and do the same check as is done
for the output: Q == tweak(tweak(X,D), T).
2.To make fully functioning CoinPools, one would need functionality
similar to OP_MERKLESUB[4]: remove some data from the merkle tree, and
remove a key from the aggregated internal key.This suggestion may
surpass the intended scope of this proposal, and would likely
necessitate the availability of multiple EC operations to accommodate
various key schemes. If we had opcodes for adding and removing keys
from the internal key this would be even more powerful.
I look forward to hearing your thoughts on these suggestions and
further exploring the possibilities of the proposal!
Cheers,
Johan
[1] https://github.com/halseth/btcd/pull/1/commits/90a4065bdcd8029fe3325514a250490cba66fddd
[2] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-June/017964.html
[3] https://github.com/halseth/tapsim/tree/matt-demo/examples/matt/coinpool
[4] https://github.com/ariard/bips/blob/coinpool-bips/bip-merklesub.mediawiki
On Fri, May 5, 2023 at 11:18 PM Salvatore Ingala
<salvatore.ingala at gmail.com> wrote:
>
> On Thu, 4 May 2023 at 10:34, Johan Torås Halseth <johanth at gmail.com> wrote:
> >
> > It sounds like we can generalize the description of the construct to:
> > Access to (the hash of) embedded data of inputs and outputs, and the
> > enforcement of output keys and (static) taptrees. In other words, as
> > long as you can dynamically compute the output embedded data in
> > Script, you can enforce more or less anything (since you can make the
> > output script enforce presenting a witness "satisfying" the embedded
> > data).
> >
> > Does that sound about right?
>
> Yes. Fraud proofs allow us to extend beyond what Script can do (with the
> necessary tradeoffs), but there is plenty that can be done without them.
>
>
> > For instance, I believe you could simulate coin pools pretty easily:
> > Commit to the set of pubkeys and amounts owned by the participants in
> > the pool, and an output taptree where each participant has their own
> > spending path. Now, to exit the pool unilaterally, the participant
> > must present a proof that their pubkey+amount is committed to in the
> > input and an output where it is no longer committed.
>
> I don't think one would want to have a tapleaf for each participant:
> that would make you pay log n hashes just to reveal the tapleaf, and
> then you still need to pay log n hashes to access the embedded data.
>
> Instead, the "unilateral withdrawal Script" can be the same for all the
> participants. The witness would be the Merkle proof, plus perhaps some
> additional information to identify the leaf in the tree (depending on
> how the Merkle tree is implemented). In a complete Merkle tree for
> N = 2^n participants, the witness could contain the n hashes that allow
> to prove the value of the leaf, plus n bits to identify the path to the
> leaf (0/1 for 'left/right" child), since Script doesn't have enough
> opcodes to extract the bits from the leaf index.
>
> The data in the leaf can contain a commitment to all the information
> relevant for that participant (e.g.: their balance and pubkey, in a
> CoinPool construction).
>
> Then, the same witness can easily be reused to compute the new Merkle
> root after the data in the leaf is modified (for example, setting the
> amount to 0 for one participant).
>
>
> > A question that arises is how one would efficiently (in Script) prove
> > the inclusion/exclusion of the data in the commitment. One could
> > naively hash all the data twice during script execution (once for the
> > input, once for the output), but that is costly. It would be natural
> > to show merkle tree inclusion/exclusion in script, but perhaps there
> > are more efficient ways to prove it?
>
> A Merkle tree as described above commits to an entire vector that you
> can index positionally. That's quite versatile, and easier to handle
> than more complex constructions like accumulators with exclusion proofs.
>
> A Merkle proof for 2^7 = 128 participants requires about 8 hashes, so
> around 250 bytes in total of witness size; 2^10 = 1024 should bring that
> to the ballpark of 350 bytes.
>
> Best,
> Salvatore Ingala

2023-06-07 23:21:08 UTC

- reply

📅 Original date posted:2023-05-04
🗒️ Summary of this message: The construct allows access to embedded data of inputs and outputs, and enforcement of output keys and static taptrees. Merkle tree inclusion/exclusion in script could be used for efficient proof.
📝 Original message:Thank you for the example.
It sounds like we can generalize the description of the construct to:
Access to (the hash of) embedded data of inputs and outputs, and the
enforcement of output keys and (static) taptrees. In other words, as
long as you can dynamically compute the output embedded data in
Script, you can enforce more or less anything (since you can make the
output script enforce presenting a witness "satisfying" the embedded
data).
Does that sound about right?
For instance, I believe you could simulate coin pools pretty easily:
Commit to the set of pubkeys and amounts owned by the participants in
the pool, and an output taptree where each participant has their own
spending path. Now, to exit the pool unilaterally, the participant
must present a proof that their pubkey+amount is committed to in the
input and an output where it is no longer committed.
A question that arises is how one would efficiently (in Script) prove
the inclusion/exclusion of the data in the commitment. One could
naively hash all the data twice during script execution (once for the
input, once for the output), but that is costly. It would be natural
to show merkle tree inclusion/exclusion in script, but perhaps there
are more efficient ways to prove it?
- Johan
On Tue, May 2, 2023 at 12:44 AM Salvatore Ingala via bitcoin-dev
<bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> Hi all,
>
> I apologize for a couple of oversights in my last e-mail.
>
> The first is that m_B can't be committed as-is in the contract's
> embedded data, with the current semantics of OP_COCV, which
> only allows 32-byte values. A solution could be to store its
> hash SHA256(m_B), instead.
>
> (I didn't test the Scripts, so there could be other bugs − hopefully the
> general idea is clear, anyway)
>
> On Mon, 1 May 2023 at 15:11, Salvatore Ingala <salvatore.ingala at gmail.com> wrote:
>>
>> If the internal_pubkey is a musig-aggregated key of Alice and Bob,
>> the game can be settled entirely offline after the first transaction.
>> Simply, Bob communicates his move to Alice, Alice reveals her move to
>> Bob, and they can settle the bet. The game would be played without
>> any script being executed, therefore all transactions could look like
>> any other P2TR, with the only possible fingerprinting being due to the
>> input amounts.
>
>
> This is incomplete: Alice can't trust Bob by revealing her move, as
> he could then cheat on-chain and play a different move.
>
> The fix should be straightforward, after adding the requirement that the
> internal pubkey of [S1] is a musig2 of both players.
> After Bob reveals his move (say, Rock), Alice will only agree to continue
> the game off-chain if Bob pre-signs transactions for the state [S1] (where
> m_B = Paper, and m_B = Scissors) that send all the money to Alice.
> This guarantees that a cheating Bob is punished.
>
> Best,
> Salvatore Ingala
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

2023-06-07 23:20:59 UTC

- reply

📅 Original date posted:2023-04-28
🗒️ Summary of this message: A person is interested in a proposal for powerful capabilities using simple opcodes. They ask for an example of encoding a state transition in Bitcoin script for a simple game.
📝 Original message:Hi, Salvatore.
I find this proposal very interesting. Especially since you seemingly
can achieve such powerful capabilities by such simple opcodes.
I'm still trying to grok how this would look like on-chain (forget
about the off-chain part for now), if we were to play out such a
computation.
Let's say you have a simple game like "one player tic-tac-toe" with
only two tiles: [ _ | _ ]. The player wins if he can get two in a row
(pretty easy game tbh).
Could you give a complete example how you would encode one such state
transition (going from [ X, _ ] -> [ X, X ] for instance) in Bitcoin
script?
Feel free to choose a different game or program if you prefer :)
Thanks!
Johan
On Tue, Dec 13, 2022 at 2:08 PM Billy Tetrud via bitcoin-dev
<bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> Re Verkle trees, that's a very interesting construction that would be super useful as a tool for something like Utreexo. A potentially substantial downside is that it seems the cryptography used to get those nice properties of Verkle trees isn't quantum safe. While a lot of things in Bitcoin seems to be going down the path of quantum-unsafe (I'm looking at you, taproot), there are still a lot of people who think quantum safety is important in a lot of contexts.
>
> On Thu, Dec 1, 2022 at 5:52 AM Salvatore Ingala via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
>>
>> Hello Rijndael,
>>
>>
>>
>> On Wed, 30 Nov 2022 at 23:09, Rijndael <rot13maxi at protonmail.com> wrote:
>>>
>>> Hello Salvatore,
>>>
>>> I found my answer re-reading your original post:
>>> > During the arbitration phase (say at the i-th leaf node of M_T), any party can win the challenge by providing correct values for tr_i = (st_i, op_i, st_{i + 1}). Crucially, only one party is able to provide correct values, and Script can verify that indeed the state moves from st_i to st_{i + 1} by executing op_i. The challenge is over.
>>
>> You are correct, the computation step encoded in a leaf needs to be simple enough for Script to verify it.
>>
>> For the academic purpose of proving completeness (that is, any computation can be successfully "proved" by the availability of the corresponding fraud proof), one can imagine reducing the computation all the way down to a circuit, where each step (leaf) is as simple as what can be checked with {OP_NOT, OP_BOOLAND, OP_BOOLOR, OP_EQUAL}.
>>
>> In practice, you would want to utilize Script to its fullest, so for example you wouldn't compile a SHA256 computation to something else – you'd rather use OP_SHA256 directly.
>>
>>>
>>> That raises leads to a different question: Alice initially posts a commitment to an execution trace of `f(x) = y`, `x`, and `y`. Bob Disagrees with `y` so starts the challenge protocol. Is there a commitment to `f`? In other words, the dispute protocol (as I read it) finds the leftmost step in Alice and Bob's execution traces that differ, and then rewards the coins to the participant who's "after-value" is computed by the step's operation applied to the "before value". But if the participants each present valid steps but with different operations, who wins? In other words, Alice could present [64, DECREMENT, 63] and Bob could present [64, INCREMENT, 65]. Those steps don't match, but both are valid. Is there something to ensure that before the challenge protocol starts, that the execution trace that Alice posts is for the right computation and not a different computation that yields a favorable result for her (and for which she can generate a valid merkle tree)?
>>
>>
>> The function f is already hard-coded in the contract itself, by means of the tree of scripts − that already commits to the possible futures. Therefore, once you are at state S14, you know that you are verifying the 6th step of the computation; and the operation in the 6th step of the computation depends solely on f, not its inputs. In fact, you made me realize that I could drop op_i from the i-th leaf commitment, and just embed the information in the Script of that corresponding state.
>>
>> Note that the states S0 to S14 of the 256x game are not _all_ the possible states, but only the ones that occurred in that execution of the contract (corresponding to a path from the root to the leaf of the Merkle tree of the computation trace), and therefore the ones that materialized in a UTXO. Different choices made by the parties (by providing different data, and therefore choosing different branches) would lead to a different leaf, and therefore to different (but in a certain sense "symmetric") states.
>>
>> ========
>>
>> Since we are talking about the fact that f is committed to in the contract, I'll take the chance to extend on this a bit with a fun construction on top.
>> It is well-known in the academic literature of state channels that you can create contracts where even the function ("program", or "contract") is not decided when the channel is created.
>>
>> Since f is generic, we can choose f itself to be a universal Turing machine. That is, we can imagine a function f(code, data) that executes a program ("code") on the "data" given to it as input.
>> Since we can do fraud proofs on statements "f(code, data) == output", we could build contracts where the "code" itself is chosen later.
>>
>> For example, one could build a universal state channel, where parties can enter any contract among themselves (e.g.: start playing a chess game) entirely inside the channel. The state of this universal channel would contain all the states of the individual contracts that are currently open in the channel, and even starting/closing contracts can happen entirely off-chain.
>>
>> I believe these constructions are practical (the code of universal Turing machines is not really complicated), so it might be worth exploring further to figure out useful applications of this approach (supercharging lightning?).
>>
>> We should probably start by implementing testnet rock-paper-scissors in MATT, though :)
>>
>> Best,
>> Salvatore Ingala
>> _______________________________________________
>> 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

2023-06-07 18:21:27 UTC

- reply

📅 Original date posted:2019-10-30
📝 Original message:On Mon, Oct 28, 2019 at 6:16 PM David A. Harding <dave at dtrt.org> wrote:
> A parent transaction near the limit of 100,000 vbytes could have almost
> 10,000 outputs paying OP_TRUE (10 vbytes per output). If the children
> were limited to 10,000 vbytes each (the current max carve-out size),
> that allows relaying 100 mega-vbytes or nearly 400 MB data size (larger
> than the default maximum mempool size in Bitcoin Core).
>
Thanks, Dave, I wasn't aware the limits would allow this many outputs. And
as your calculation shows, this opens up the potential for free relay of
large amounts of data.
We could start special casing to only allow this for "LN commitment-like"
transactions, but this would be application specific changes, and your
calculation shows that even with the BOLT2 numbers there still exists cases
with a large number of children.
We are moving forward with adding a 1 block delay to all outputs to utilize
the current carve-out rule, and the changes aren't that bad. See Joost's
post in "[PATCH] First draft of option_simplfied_commitment"
- Johan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20191030/bc2a90f3/attachment.html>

2023-06-07 18:12:15 UTC

- reply

📅 Original date posted:2018-05-23
📝 Original message:Thanks, Jimpo!
This is very encouraging, I think. I sorta assumed that separating the
elements into their own sub-filters would hurt the compression a lot more.
Can the compression ratio/false positive rate be tweaked with the
sub-filters in mind?
With the total size of the separated filters being no larger than the
combined filters, I see no benefit of combined filters? Committing to them
all in the headers would also save space, and we could ensure nodes are
serving all sub-filters.
- Johan
On Wed, May 23, 2018 at 9:38 AM, Jim Posen <jim.posen at gmail.com> 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.
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180523/7df6715a/attachment.html>

2023-06-07 18:12:14 UTC

- reply

📅 Original date posted:2018-05-22
📝 Original message:Maybe I didn't make it clear, but the distinction is that the current track
allocates
one service bit for each "filter type", where it has to be agreed upon up
front what
elements such a filter type contains.
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.
This would require a "getcftypes" message, of course.
- Johan
On Tue, May 22, 2018 at 3:16 AM, Olaoluwa Osuntokun <laolu32 at gmail.com>
wrote:
> > What if instead of trying to decide up front which subset of elements
> will
> > be most useful to include in the filters, and the size tradeoff, we let
> the
> > full-node decide which subsets of elements it serves filters for?
>
> This is already the case. The current "track" is to add new service bits
> (while we're in the uncommitted phase) to introduce new fitler types. Light
> clients can then filter out nodes before even connecting to them.
>
> -- Laolu
>
> On Mon, May 21, 2018 at 1:35 AM Johan Torås Halseth <johanth at gmail.com>
> wrote:
>
>> Hi all,
>>
>> Most light wallets will want to download the minimum amount of data
>> required to operate, which means they would ideally download the smallest
>> possible filters containing the subset of elements they need.
>>
>> What if instead of trying to decide up front which subset of elements
>> will be most useful to include in the filters, and the size tradeoff, we
>> let the full-node decide which subsets of elements it serves filters for?
>>
>> For instance, a full node would advertise that it could serve filters for
>> the subsets 110 (txid+script+outpoint), 100 (txid only), 011 (script+outpoint)
>> etc. A light client could then choose to download the minimal filter type
>> covering its needs.
>>
>> The obvious benefit of this would be minimal bandwidth usage for the
>> light client, but there are also some less obvious ones. We wouldn’t have
>> to decide up front what each filter type should contain, only the possible
>> elements a filter can contain (more can be added later without breaking
>> existing clients). This, I think, would let the most served filter types
>> grow organically, with full-node implementations coming with sane defaults
>> for served filter types (maybe even all possible types as long as the
>> number of elements is small), letting their operator add/remove types at
>> will.
>>
>> The main disadvantage of this as I see it, is that there’s an exponential
>> blowup in the number of possible filter types in the number of element
>> types. However, this would let us start out small with only the elements we
>> need, and in the worst case the node operators just choose to serve the
>> subsets corresponding to what now is called “regular” + “extended” filters
>> anyway, requiring no more resources.
>>
>> This would also give us some data on what is the most widely used filter
>> types, which could be useful in making the decision on what should be part
>> of filters to eventually commit to in blocks.
>>
>> - Johan
>> On Sat, May 19, 2018 at 5:12, Olaoluwa Osuntokun via bitcoin-dev <
>> bitcoin-dev at lists.linuxfoundation.org> wrote:
>>
>> On Thu, May 17, 2018 at 2:44 PM Jim Posen via bitcoin-dev <bitcoin-
>>
>>> 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.
>>>
>>
>> Yeah parallel filtering would be pretty nice. We've implemented a serial
>> filtering for btcwallet [1] for the use-case of rescanning after a seed
>> phrase import. Parallel filtering would help here, but also we don't yet
>> take advantage of batch querying for the filters themselves. This would
>> speed up the scanning by quite a bit.
>>
>> I really like the filtering model though, it really simplifies the code,
>> and we can leverage identical logic for btcd (which has RPCs to fetch the
>> filters) as well.
>>
>> [1]: https://github.com/Roasbeef/btcwallet/blob/master/chain/
>> neutrino.go#L180
>>
>> _______________________________________________ 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/20180522/cdeb1da6/attachment.html>

2023-06-07 18:12:13 UTC

- reply

📅 Original date posted:2018-05-21
📝 Original message:Hi all,
Most light wallets will want to download the minimum amount of data required to operate, which means they would ideally download the smallest possible filters containing the subset of elements they need.
What if instead of trying to decide up front which subset of elements will be most useful to include in the filters, and the size tradeoff, we let the full-node decide which subsets of elements it serves filters for?
For instance, a full node would advertise that it could serve filters for the subsets 110 (txid+script+outpoint), 100 (txid only), 011 ( script+outpoint) etc. A light client could then choose to download the minimal filter type covering its needs.
The obvious benefit of this would be minimal bandwidth usage for the light client, but there are also some less obvious ones. We wouldn’t have to decide up front what each filter type should contain, only the possible elements a filter can contain (more can be added later without breaking existing clients). This, I think, would let the most served filter types grow organically, with full-node implementations coming with sane defaults for served filter types (maybe even all possible types as long as the number of elements is small), letting their operator add/remove types at will.
The main disadvantage of this as I see it, is that there’s an exponential blowup in the number of possible filter types in the number of element types. However, this would let us start out small with only the elements we need, and in the worst case the node operators just choose to serve the subsets corresponding to what now is called “regular” + “extended” filters anyway, requiring no more resources.
This would also give us some data on what is the most widely used filter types, which could be useful in making the decision on what should be part of filters to eventually commit to in blocks.
- Johan On Sat, May 19, 2018 at 5:12, Olaoluwa Osuntokun via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
On Thu, May 17, 2018 at 2:44 PM Jim Posen via bitcoin-dev <bitcoin- 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.
Yeah parallel filtering would be pretty nice. We've implemented a serial filtering for btcwallet [1] for the use-case of rescanning after a seed phrase import. Parallel filtering would help here, but also we don't yet take advantage of batch querying for the filters themselves. This would speed up the scanning by quite a bit.
I really like the filtering model though, it really simplifies the code, and we can leverage identical logic for btcd (which has RPCs to fetch the filters) as well.
[1]: https://github.com/Roasbeef/btcwallet/blob/master/chain/neutrino.go#L180 [https://github.com/Roasbeef/btcwallet/blob/master/chain/neutrino.go#L180]
_______________________________________________ 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/20180521/d4626f97/attachment.html>