Bob McElrath [ARCHIVE] / is on Nostr

⚠️ This account is not associated with a real person. It's an archival account for mailing list messages.
🗓️ Active from 2014-08-10 to 2021-12-15
💬 Posted a total of 28 messages
📚 Participated in the following categories: Bitcoin-development, bitcoin-dev, Bitcoin Advent Calendar
🔇 Please do not DM this user as it's used for archive purposes only.

Last Notes

2023-06-09 14:53:15

- reply

📅 Original date posted:2018-12-02
📝 Original message:
I've long thought about using SIGHASH_SINGLE, then either party can add inputs
to cover whatever fee they want on channel close and it doesn't have to be
pre-planned at setup.
For Lightning I think you'd want to cross-sign, e.g. Alice signs her input
and Bob's output, while Bob signs his input and Alice's output. This would
demotivate the two parties from picking apart the transaction and broadcasting
one of the two SIGHASH_SINGLE's in a Lightning transaction.
Matt Corallo via bitcoin-dev [bitcoin-dev at lists.linuxfoundation.org] wrote:
> (cross-posted to both lists to make lightning-dev folks aware, please take
> lightning-dev off CC when responding).
>
> As I'm sure everyone is aware, Lightning (and other similar systems) work by
> exchanging pre-signed transactions for future broadcast. Of course in many
> cases this requires either (a) predicting what the feerate required for
> timely confirmation will be at some (or, really, any) point in the future,
> or (b) utilizing CPFP and dependent transaction relay to allow parties to
> broadcast low-feerate transactions with children created at broadcast-time
> to increase the effective feerate. Ideally transactions could be constructed
> to allow for after-the-fact addition of inputs to increase fee without CPFP
> but it is not always possible to do so.
>
> Option (a) is rather obviously intractible, and implementation complexity
> has led to channel failures in lightning in practice (as both sides must
> agree on a reasonable-in-the-future feerate). Option (b) is a much more
> natural choice (assuming some form of as-yet-unimplemented package relay on
> the P2P network) but is made difficult due to complexity around RBF/CPFP
> anti-DoS rules.
>
> For example, if we take a simplified lightning design with pre-signed
> commitment transaction A with one 0-value anyone-can-spend output available
> for use as a CPFP output, a counterparty can prevent confirmation
> of/significantly increase the fee cost of confirming A by chaining a
> large-but-only-moderate-feerate transaction off of this anyone-can-spend
> output. This transaction, B, will have a large absolute fee while making the
> package (A, B) have a low-ish feerate, placing it solidly at the bottom of
> the mempool but without significant risk of it getting evicted during memory
> limiting. This large absolute fee forces a counterparty which wishes to have
> the commitment transaction confirm to increase on this absolute fee in order
> to meet RBF rules.
>
> For this reason (and many other similar attacks utilizing the package size
> limits), in discussing the security model around CPFP, we've generally
> considered it too-difficulty-to-prevent third parties which are able to
> spend an output of a transaction from delaying its confirmation, at least
> until/unless the prevailing feerates decline and some of the mempool backlog
> gets confirmed.
>
> You'll note, however, that this attack doesn't have to be permanent to work
> - Lightning's (and other contracting/payment channel systems') security
> model assumes the ability to get such commitment transactions confirmed in a
> timely manner, as otherwise HTLCs may time out and counterparties can claim
> the timeout-refund before we can claim the HTLC using the hash-preimage.
>
> To partially-address the CPFP security model considerations, a next step
> might involve tweaking Lightning's commitment transaction to have two
> small-value outputs which are immediately spendable, one by each channel
> participant, allowing them to chain children off without allowng unrelated
> third-parties to chain children. Obviously this does not address the
> specific attack so we need a small tweak to the anti-DoS CPFP rules in
> Bitcoin Core/BIP 125:
>
> The last transaction which is added to a package of dependent transactions
> in the mempool must:
> * Have no more than one unconfirmed parent,
> * Be of size no greater than 1K in virtual size.
> (for implementation sanity, this would effectively reduce all mempool
> package size limits by 1 1K-virtual-size transaction, and the last would be
> "allowed to violate the limits" as long as it meets the above criteria).
>
> For contracting applications like lightning, this means that as long as the
> transaction we wish to confirm (in this case the commitment transaction)
> * Has only two immediately-spendable (ie non-CSV) outputs,
> * where each immediately-spendable output is only spendable by one
> counterparty,
> * and is no larger than MAX_PACKAGE_VIRTUAL_SIZE - 1001 Vsize,
> each counterparty will always be able to independantly CPFP the transaction
> in question. ie because if the "malicious" (ie transaction-delaying) party
> bradcasts A with a child, it can never meet the "last transaction" carve-out
> as its transaction cannot both meet the package limit and have only one
> unconfirmed ancestor. Thus, the non-delaying counterparty can always
> independently add its own CPFP transaction, increasing the (A, Tx2) package
> feerate and confirming A without having to concern themselves with the (A,
> Tx1) package.
>
> As an alternative proposal, at various points there have been discussions
> around solving the "RBF-pinning" problem by allowing transactors to mark
> their transactions as "likely-to-be-RBF'ed", which could enable a relay
> policy where children of such transactions would be rejected unless the
> resulting package would be "near the top of the mempool". This would
> theoretically imply such attacks are not possible to pull off consistently,
> as any "transaction-delaying" channel participant will have to place the
> package containing A at an effective feerate which makes confirmation to
> occur soon with some likelihood. It is, however, possible to pull off this
> attack with low probability in case of feerate spikes right after broadcast.
>
> Note that this clearly relies on some form of package relay, which comes
> with its own challenges, but I'll start a separate thread on that.
>
> See-also: lightning-dev thread about the changes to lightning spec required
> to incorporate this: https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-November/001643.html
>
> Matt
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
> !DSPAM:5c014daf168271726154759!
--
Cheers, Bob McElrath
"For every complex problem, there is a solution that is simple, neat, and wrong."
-- H. L. Mencken

2023-06-08 01:01:21

- reply

📅 Original date posted:2021-12-15
📝 Original message:You basically described Braidpool:
https://github.com/pool2win/braidpool
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-August/019371.html
We're working on this actively and will have some updates soon. Additional
contributors are most welcome.
To your points below:
1. Increased payout regularity does not lower the viable size of mining pools,
because smaller mining pools using this mechanism still have higher variance.
2. The on-chain footprint is *higher* due to the increased payout regularity.
For a talk a while back I computed that if you want to have a 1% annual variance
on your profits, you need a pool that is about 20% of the network. The only way
to get this is with smaller, faster blocks or "shares".
https://www.youtube.com/watch?v=91WKy7RYHD4
There is a discussion forum at:
https://matrix.to/#/#braidpool:matrix.org
and a mailing list:
https://sourceforge.net/p/braidpool/mailman/
All of the existing discussion has been happening privately unfortunately but
I'll try to start using Matrix. ;-)
We've been discussing alternatives for both fee-rate and hashrate derivatives
lately. I'm not opposed to using CTV for some of the things in braidpool, if it
makes sense. Payment pools and unilateral channel openings may be interesting in
this context.
P.S. if anyone wants me to write up a blurb of exactly *why* a construction
without shares cannot be used for hashrate derivatives I can do that, just ask.
It comes down to maximum likelihood estimators for the Poisson distribution...
Billy Tetrud [billy.tetrud at gmail.com] wrote:
> Looks like an interesting proposal, but it doesn't seem to quite match the
> goals you mentioned. As you do mention, this mining pool coordination doesn't
> get rid of the need for mining pools in the first place. So it doesn't satisfy
> item 1 on your goal list afaict.
>
> The primary benefits over what we have today that I can see are:
> 1. increased payout regularity, which lowers the viable size of mining pools,
> and
> 2. Lower on chain footprint through combining pay outs from multiple pools.
>
> Am I missing some?
>
> These are interesting benefits, but it would be nice if your post was clearer
> on that, since the goals list is not the same as the list of potential benefits
> of this kind of design.
>
> As far as enabling solo mining, what if this concept were used off chain? Have
> a public network of solo miners who publish "weak blocks" to that network, and
> the next 100 (or 1000 etc) nice miners pay you out as long as you're also being
> nice by following the protocol? All the nice optimizations you mentioned about
> eg combined taproot payouts would apply i think. The only goals this wouldn't
> satisfy are 3 and 5 since an extra network is needed, but to be fair, your
> proposal requires pools which all need their own extra network anyways.
>
> The missing piece here would be an ordering of weak blocks to make the window
> possible. Or at least a way to determine what blocks should definitely be part
> of a particular block's pay out. I could see this being done by a separate
> ephemeral blockchain (which starts fresh after each Bitcoin block) that keeps
> track of which weak blocks have been submitted, potentially using the pow
> already in each block to secure it. Granted that piece is a bit half baked, but
> it seems quite solvable. Wdyt?
>
> One thing that jumped out at me as not safe is throwing block rewards into a
> channel and being able to spend them immediately. There's a reason block
> rewards aren't spendable for a while, and channels don't solve that problem, do
> they? Why not simply reduce the on chain wait time for spending block rewards
> at that point? Seems like the consequences would be the same.
>
> On Tue, Dec 14, 2021, 16:12 Bob McElrath via bitcoin-dev <
> bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> You are hand waving. Attempting to redefine terms to justify your argument
> is
> intellectually dishonest. Bitcoin pools have *always* been about variance
> reduction. Your window function fundamentally CANNOT be used to hedge
> hashrate.
> Various suggestions below introduce dangerous new games that might be
> played by
> miners.
>
> The fact is that the half-baked design you posted is less than useless, and
> doesn't do anything that anyone wants.
>
> You are trying to justify CTV by making it be all things to all people.
> "When
> all you have is a hammer, every problem looks like a nail". Instead I
> humbly
> suggest that you pick ONE problem for which CTV is demonstrably the right
> and
> best solution, instead of snowing us with a ton of half-baked things that
> *could* be done, and often don't even require CTV, and some (like this one)
> fundamentally don't work. I do like some of your ideas, but if you had to
> pick
> just one "use case", which would it be?
>
> Jeremy [jlrubin at mit.edu] wrote:
> > Bitcoin didn't invent the concept of pooling: https://en.wikipedia.org/
> wiki/
> > Pooling_(resource_management). This is a Bitcoin Mining Pool, although it
> may
> > not be your favorite kind, which is fixated on specific properties of
> computing
> > contributions before finding a block. Pooling is just a general technique
> for
> > aggregating resources to accomplish something. If you have another name
> like
> > pooling that is in common use for this type of activity I would be more
> than
> > happy to adopt it.
> >
> > This sort of pool can hedge not only against fee rates but also against
> > increases in hashrate since your historical rate 'carries' into the
> future as a
> > function of the window. Further, windows and reward functions can be
> defined in
> > a myriad of ways that could, e.g., pay less to blocks found in more rapid
> > succession, contributing to the smoothing functionality.
> >
> > With respect to sub-block pooling, as described in the article, this sort
> of
> > design also helps with micro-pools being able to split resources
> > non-custodially in every block as a part of the higher order DCFMP. The
> point
> > is not, as noted, to enable solo mining an S9, but to decrease the size
> of the
> > minimum viable pool. It's also possible to add, without much validation
> or
> > data, some 'uncle block' type mechanism in an incentive compatible way
> (e.g.,
> > add 10 pow-heavy headers on the last block for cost 48 bytes header + 32
> bytes
> > payout key) such that there's an incentive to include the heaviest ones
> you've
> > seen, not just your own, that are worth further study and consideration
> > (particularly because it's non-consensus, only for opt-in participation
> in the
> > pool).
> >
> > With respect to space usage, it seems you wholly reject the viability of
> a
> > payment pool mechanism to cut-through chain space. Is this a critique
> that
> > holds for all Payment Pools, or just in the context of mining? Is there a
> > particular reason why you think it infeasible that "strongly online"
> > counterparties would be able to coordinate more efficiently? Is it
> preferable
> > for miners, the nexus of decentralization for Bitcoin, to prefer to use
> > custodial services for pooling (which may require KYC/AM) over bearing a
> cost
> > of some extra potential chainload?
> >
> > Lastly, with respect to complexity, the proposal is actually incredibly
> simple
> > when you take it in a broader context. Non Interactive Channels and
> Payment
> > Pools are useful by themselves, so are the operations to merge them and
> swap
> > balance across them. Therefore most of the complexity in this proposal is
> > relying on tools we'll likely see in everyday use in any case, DCFMP or
> no.
> >
> > Jeremy
> >
> --
> Cheers, Bob McElrath
>
> "For every complex problem, there is a solution that is simple, neat, and
> wrong."
> -- H. L. Mencken
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
> !DSPAM:61ba2512470948607217095!
--
Cheers, Bob McElrath
"For every complex problem, there is a solution that is simple, neat, and wrong."
-- H. L. Mencken

2023-06-07 20:23:45

- reply

📅 Original date posted:2020-04-05
📝 Original message:Note that this attack requires collaboration with the current UTXO owner.
Generally if there's some form of address/payment request, the current holder is
trying to transfer the UXTO to some other (non-statechain) entity, and he knows
the target of the transfer, and participates in the protocol to authorize it.
The current holder must obtain the target pubkey for the transfer out-of-band
with respect to the SE, or the SE can MITM that.
It's a stated security assumption that the sender or receiver do not collude
with the SE. If either do, then your attack is generally possible and all bets
are off. So what you've described is simply the SE colluding with the receiver.
The receiver will *already* receive the UTXO, so the receiver here is assisting
the SE in stealing his (the receiver's) funds, or the SE has done a MITM on the
transfer. Various improvements including blind signing, a SE-federation, etc
are valuable to consider to mitigate this. But the SE must be prevented, one way
or another, from "buying the UTXO". The SE cannot be allowed to be both operator
of the SE and a customer of it, as this clearly violates the no-receiver
collusion principle.
"Adding a new user key" doesn't change the situation. There's already a user key
involved, and the user has already acquiesced to the transfer. Acquiescing with
two keys doesn't change anything.
As far as proving and tracing the fraud, this is where "single use seals" come
in. Each SE transfer can involve an "opening" of a seal, followed by a "close"
when it is transferred, creating a linear history of ownership. If the SE
obtains the full private key x, one way or another, the spend of that UTXO will
fall outside this seal-based history, and proof of fraud will be evident. It
won't be possible to determine *which* of the old owners collaborated with the
SE, but it gives clear proof that the SE is not to be trusted. A customer might
demand that a seal-based system be in use as an independent entity from the SE,
to audit the honesty of the SE. The seal system does not require any of the keys
required for transfer. See https://mainstay.xyz as a potential implementation.
There are lots of reasons this might required as an AML solution for some
businesses anyway.
Nadav Kohen via bitcoin-dev [bitcoin-dev at lists.linuxfoundation.org] wrote:
> Hey all,
>
> So my main concern with the proposal as written is that the Statechain Entity
> (SE) can untraceably scam its users with the following attack:
>
> 1) Buy the utxo (have it transferred to a key it knows), this first step can be
> skipped if the utxo was created by the SE.
> 2) Transfer the UTXO to someone else, let it be for however long
> 3) When it wishes to steal the UTXO, the SE now knows its own shard s_n and it
> knows the full private key, x, from when it owned the UTXO (and had both
> shards), and so it can compute x/s_n = the current users shard. It can then
> sign for the current user, and forge a state transition to a key it owns before
> spending the UTXO on chain.
>
> The main problem here is that the user who had their funds stolen cannot prove
> to anyone that this has happened since the attack compromises their key.
> That said, I think this problem is easily fixed by adding a new user key to the
> protocol with which they must sign in order for the transfer to be considered
> valid on the state chain. This way, if the SE wishes to steal the funds (which
> they still can), at least it is traceable/provable that this SE is not
> trustworthy as there is no evidence of a valid transfer for the funds that have
> been stolen.
>
> Best,
> Nadav
>
> On Thu, Apr 2, 2020 at 7:22 PM Tom Trevethan via bitcoin-dev <
> bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> Thanks for all of the input and comments - I do now think that the
> decrementing nSequence relative locktime backup system with kick-off
> transaction is the way to go, including a fee penalty via CPFP to
> disincentivise DoS, as suggested.
> I have started a more detailed document specifying the proposed protocol in
> more detail: https://github.com/commerceblock/mercury/blob/master/
> statechains.md which includes improvements to the transfer mechanism (and
> an explanation of how this can be used to transfer/novate positions in
> DLCs). Always happy to get more feedback or PRs.
>
> Tom
>
> On Tue, Mar 31, 2020 at 12:41 PM Tom Trevethan <tom at commerceblock.com>
> wrote:
>
> Hi David,
>
> Just for clarity, I left nChain over 2 years ago (having worked there
> since 2016). While there, I (along with other researchers) were given
> free rein to work on any ideas we wanted to. I had been interested in
> the scaling of Bitcoin off-chain, and this was one of several things I
> spent time on (including things like sidechains, pegs and threshold
> signatures). This patent application came out of an idea I had to
> transfer ownership of UTXOs off-chain that has some similarities to the
> statechains proposal, which has shown there is interest and demand for
> this type of system.
>
> Although I think the existence of this application is something to be
> mindful of, there are several important things to note:
>
> 1. Although there are similarities, the current ideas are significantly
> different to those in the application.
> 2. The key transfer protocol as described in the application is not
> secure (for several reasons, including as discussed above, by Albert
> and Bob etc.) - and a different mechanism is required.
> 3. Decrementing timelocks (as suggested in the application) are prior
> art (Decker-Wattenhofer 2015), and in any case any implementation will
> most likely use an 'invalidation tree' relative locktime backup
> mechanism for open-ended UTXOs.
> 4. The patent application has not been granted (it was made in May
> 2017) and the international search report rejected it on the grounds of
> prior art.
>
> Tom
>
> On Tue, Mar 31, 2020 at 11:36 AM David A. Harding <dave at dtrt.org>
> wrote:
>
> On Wed, Mar 25, 2020 at 01:52:10PM +0000, Tom Trevethan via
> bitcoin-dev wrote:
> > Hi all,
> >
> > We are starting to work on an implementation of the statechains
> concept (
> > https://medium.com/@RubenSomsen/
> statechains-non-custodial-off-chain-bitcoin-transfer-1ae4845a4a39),
> >
> > [...]
> > There are two main modifications we are looking at:
> > [...]
> >
> > 2. Replacing the 2-of-2 multisig output (paying to statechain
> entity SE key
> > and transitory key) with a single P2(W)PKH output where the
> public key
> > shared between the SE and the current owner. The SE and the
> current owner
> > can then sign with a 2-of-2 ECDSA MPC.
>
> Dr. Trevethan,
>
> Would you be able to explain how your proposal to use statechains
> with
> 2P-ECDSA relates to your patent assigned to nChain Holdings for
> "Secure
> off-chain blockchain transactions"?[1]
>
> [1] https://patents.google.com/patent/US20200074464A1
>
> Here are some excerpts from the application that caught my
> attention in
> the context of statechains in general and your proposal to this
> list in
> particular:
>
> > an exchange platform that is trusted to implement and operate the
> > transaction protocol, without requiring an on-chain transaction.
> The
> > off-chain transactions enable one computer system to generate
> multiple
> > transactions that are recordable to a blockchain in different
> > circumstances
> >
> > [...]
> >
> > at least some of the off-chain transactions are valid for
> recording on
> > the blockchain even in the event of a catastrophic failure of the
> > exchange (e.g., exchange going permanently off-line or loosing
> key
> > shares).
> >
> > [...]
> >
> > there may be provided a computer readable storage medium
> including a
> > two-party elliptic curve digital signature algorithm (two-party
> ECDSA)
> > script comprising computer executable instructions which, when
> > executed, configure a processor to perform functions of a
> two-party
> > elliptic curve digital signature algorithm described herein.
> >
> > [...]
> >
> > In this instance the malicious actor would then also have to
> collude
> > with a previous owner of the funds to recreate the full key.
> Because
> > an attack requires either the simultaneous theft of both exchange
> and
> > depositor keys or collusion with previous legitimate owners of
> funds,
> > the opportunities for a malicious attacker to compromise the
> exchange
> > platform are limited.
>
> Thank you,
>
> -Dave
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
> !DSPAM:5e87670a231323960034969!
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
> !DSPAM:5e87670a231323960034969!
--
Cheers, Bob McElrath
"For every complex problem, there is a solution that is simple, neat, and wrong."
-- H. L. Mencken
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 181 bytes
Desc: Digital signature
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20200405/6199c0fd/attachment.sig>

2023-06-07 20:23:39

- reply

📅 Original date posted:2020-03-27
📝 Original message:Big picture, it seems to me this idea is workable and very interesting. I see
three likely enhancements that will be necessary or desirable:
1. Atomic swap of multiple UTXOs, and binary decomposition of value in lots
2. Key exchange ("addresses") to facilitate a secure comms path from
sender -> receiver
3. (Optional) single-use seals to close old state
(1) It's unlikely that a party sending a UTXO to another party will have a UTXO
of exactly the right size that's needed, already locked into the statechain. If
he has to create the UTXO first and then lock it into the statechain, the
statechain solution is no better than an on-chain send. And once the receiver
has the UTXO, it's unlikely that he will want to send exactly that same amount
to another receiver later. This isn't a problem in Lightning where amounts can
be arbitrarily updated. As a consequence, I think Lightning is more valuable for
small-value payments, and statechains will be more valuable for larger values.
The natural solution is to decompose your outputs in a binary decomposition,
having e.g. UTXOs with 1048576 satoshis, another with 2097152 satoshis, and so
on. Then when I want to send, I select the appropriate UTXOs as a binary
decomposition of the value I want to send, with a "lot size" of 1048576
satoshis, or the dust limit. The notion of "lots" like this is common in
traditional markets...many stocks are bought and sold in lots of 100, and forex
is traded in lots of $100,000. Users of a statechain therefore need log(V)
available UTXOs locked into the statechain, where V is their value in BTC.
Having fixed lot sizes like this also makes coinjoin-type uses more viable. The
statechain could also assist in dividing a UTXO into two utxos of the next lot
size down, so that I have the right UTXOs to hit the value I want to send.
This means that the statechain now has to *atomically* swap multiple UTXOs. In
principle, it should be possible for a statechain to circumvent the
Pagnia-Gärtner theorem[1] as it is a trusted third party, but guaranteed output
delivery will still be a problem. If a statechain can do this, it is also
capable of performing such swaps across two blockchains, creating the
execution/clearing element (but not order book) for a DEX. This same mechanism
can also be used to pay the SE for its service through a different UTXO than the
one being transferred.
Second (2), the steps in Tom's protocol presuppose a secure communications path
from the sender's wallet to the receiver's. This is probably not practical for a
myriad of reasons, but this data can be relayed through the SE if it is
encrypted for the target. This implies a new kind of "address" or "payment
request" that identifies the IP of the SE in use, pubkey of the
sender/recipient, and amount. If sender and receiver have each other's pubkeys
through another channel, as addresses/lightning payment requests are used today,
they can perform a Diffie-Hellman round mediated by the SE to establish a secure
communications path for the rounds of the protocol. Piggybacking on the
Lightning p2p network might be another option.
Third (3), a logical enhancement would be to use some kind of single-use seal,
which is "opened" when the UTXO is created or transferred, and "closed" when it
is transferred again. Thus a receiver can ensure that the sender is the holder
of current state and not some old state. It's a good idea from Peter Todd, and
Tom's Mainstay[2] may be a way to do it. The SE itself can maintain a rolling
single-use seal Merkle root, periodically timestamped into Bitcoin for faster
time resolution than Bitcoin, if you trust the SE but not your counterparty
(which is the trust assumption present in the first place). Getting Bitcoin
itself to reject backout transactions from closed seals is another problem...but
having a single-use seal implementation involved is a start.
.. [1] https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.7863
.. [2] https://mainstay.xyz
Tom Trevethan via bitcoin-dev [bitcoin-dev at lists.linuxfoundation.org] wrote:
> Hi all,
>
> We are starting to work on an implementation of the statechains concept (https:
> //medium.com/@RubenSomsen/
> statechains-non-custodial-off-chain-bitcoin-transfer-1ae4845a4a39), with
> particular interest in using the protocol enable the change of ownership
> (novation) of an individual position in an active discreet log contract (DLC)
> without an on-chain transaction, and without needing the cooperation of the
> counterparty. The protocol as outlined by Ruben requires features not currently
> available in Bitcoin (like SIGHASH_NOINPUT), and it is uncertain when (or even
> if) this will be added. So we are looking at variants that would work with
> current Bitcoin functionality, and it would be good to get some feedback on
> them.
>
> There are two main modifications we are looking at:
> 1. Instead of an eltoo-based backup/refund transaction (enabling the current
> owner to claim the UTXO in case the statechain entity disappears) we propose
> using a decrementing nLocktime for backup transactions as the output changes
> hands. Here, the first owner gets a backup transaction with an nLocktime at
> some future height (h0), then the next owner gets a backup transaction with
> nLocktime (h0-c) where c is a confirmation window. This approach has the
> downside of limiting the lifetime of the UTXO, but it also doesn't require the
> current owner to be always online.
>
> 2. Replacing the 2-of-2 multisig output (paying to statechain entity SE key and
> transitory key) with a single P2(W)PKH output where the public key shared
> between the SE and the current owner. The SE and the current owner can then
> sign with a 2-of-2 ECDSA MPC. This enables each owner to generate their own
> private key share, and the SE changes their key share at each change of
> ownership (with the shared public key remaining the same). This works as
> follows (.G is EC point multiplication, * is scalar multiplication):
>
> KeyGen:
>
> a. Owner 1 generates private key share o1 then calculates the corresponding
> public key of the share O1 and sends it to the SE: O1 = o1.G
> b. The SE then generates a private key: s1 (the SE private key share),
> calculates the corresponding public key and sends it to Owner 1: S1 = s1.G
> c. Both SE and Owner 1 then multiply the public keys they receive by their own
> private key shares to obtain the same shared public key P (which corresponds to
> a shared private key of p = o1*s1): P = o1.(s1.G) = s1.(o1.G)
> d. Owner 1 creates a funding transaction (Tx0) to pay an amount A to the
> address corresponding to P (but doesn't sign it).
> e. Once Owner 1 and SE cooperatively sign the first backup transaction, Owner 1
> then signs and broadcasts the deposit transaction Tx0.
>
> Transfer from Owner 1 to Owner 2:
>
> a. Owner 2 generates two private keys: o2 (the new owner UTXO private key
> share) and b2 (the new owner refund private key).
> b. The SE generates a temporary blinding nonce x and calculates the value x*s1
> and sends this securely to Owner 2.
> c. Owner 2 then multiplies this received value by the modular inverse of o2
> (o2_inv) and then sends this value (x*s1*o2_inv), to Owner 1.
> d. Owner 1 then multiplies this received value by the key share o1 and sends
> the resulting value (x*s1*o2_inv*o1) to the SE.
> e. The SE then multiplies this received value by the modular inverse of the
> temporary nonce (x_inv) to obtain x*s1*o2_inv*o1*x_inv. This cancels the
> blinding nonce x to give s1*o2_inv*o1. This value, when multiplied by the new
> owner key share o2 equals the original shared private key s1*o1.
> f. The SE then sets this value equal to s2 = s1*o2_inv*o1 and deletes s1. s2
> and o2 are now the key shares of `P` and can be used to colaboritively sign
> (with 2P ECDSA). So long as the SE delets s1, the old owner key share (o1) is
> of no use in deriving or co-signing with the full shared private key, and is
> invalidated.
> g. The shared public key P remains unchanged, but the corresponding private key
> (which no individual party ever has knowledge of or can derive) can only be
> determined from the key shares of the SE and Owner 2 (i.e. P = s2*o2.G).
> h. Owner 2 then calculates their backup public key (B2 = b2.G) and sends it to
> the SE.
> i. The SE creates a backup transaction (Tx2) that pays the output of Tx0 to the
> address corresponding to B2 , with `nLockTime` set to a block height h0 - c0,
> where c0, is a confirmation time sufficient to guarantee that Tx2 can be
> confirmed in the blockchain before Tx1 (therefore making Tx1 invalid).
> j. Owner 2 and the SE then cooperate to sign Tx2 with shared key (P) using the
> 2P ECDSA protocol, which Owner 2 then saves.
>
> The principle of the logic of the key transfer is that the two separate key
> shares are updated, but the full shared private key (which no-one knows)
> remains the same. The new owner chooses a new secret value for their private
> key share, and this (along with the private key share of the previous owner) is
> utilized by the SE to update their share. The use of the nonce (x) prevents any
> of the participants from determining any information about each others secret
> keys. In this way Owner 2 cannot determine s1 from x*s1, Owner 1 cannot
> determine s1 or o2 from x*s1*o2_inv and the SE cannot determine o1 or o2 from
> x*s1*o2_inv*o1.
>
> This transfer protocol can be repeated to transfer the ownership to new owners.
> Each time the SE key share sX is updated, the previous key shares become
> invalid and are of no use even if the current key share is subsequently
> revealed. The SE still needs to be trusted to delete the old key share, but
> this protocol removes the risk the the SE can be hacked by a previous owner to
> steal the funds.
>
> Any comments on the above would be greatly appreciated.
>
> Tom
> !DSPAM:5e7b7203210751402398759!
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
> !DSPAM:5e7b7203210751402398759!
--
Cheers, Bob McElrath
"For every complex problem, there is a solution that is simple, neat, and wrong."
-- H. L. Mencken
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 181 bytes
Desc: Digital signature
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20200327/72079e39/attachment-0001.sig>

2023-06-07 20:23:38

- reply

📅 Original date posted:2020-03-26
📝 Original message:Very good point, but I think this is easy to fix.
It's not actually necessary that the quantity in (b) involve the SE's secret key
s1. It can be purely the blinding factor. This quantity gets relayed through the
SE anyway, after a round trip through owner 2, where the SE removes the blinding
nonce. The SE needs to determine the ratio of the two private keys o1*o2_inv.
There's no reason for the SE to send anything about s1 other than the public
keys S1=s1.G and S2=s2.G, keeping the secret keys s1 and s2 hidden behind ECDLP
and not sharing quantities involving them in Z_p.
Thus:
b. (SE) x -> (2)
c. (2) o2_inv*x -> (1)
d. (1) o1*(o2_inv*x) -> (SE)
e. (SE) s2 = x_inv*(o1*o2_inv*x)*s1 = o1*o2_inv*s1
s2.G -> (2)
f. (2) o2.s2.G = o1.s1.G = P
Now we could have had a different problem, in step (e) if the SE sends owner 2
the quantity o1*o2_inv*s1, a self-sending owner can determine a similar quantity
to what you described (x1+x2)*s1: (o1*o2_inv + o2*o3_inv)*s1 and we're back to
an Irwin-Hall distribution.
It's not necessary to send a quantity involving s1 in steps (b-e). Owner 2
already has his private key o2 and the SE has his new private key
s2=o1*o2_inv*s1. Since P=o1.s1.G=o2.s2.G we're set up for o2 to transfer the
funds, but it's necessary to prove to (2) that his o2 does in fact control the
UTXO. This can be done by sending (2) the public key S2=s2.G which he can
multiply by o2 to get P=o2.s2.G and verify that the SE does have the correct
private key corresponding to his o2 for the public key P recorded on-chain.
Thus in the self-send situation, the owner no longer has any algebraic relations
he can use as you describe.
Algebraic relations remain in step (d) that a self-sending owner could use, but
they all involve his own private keys, which he knows anyway. He has only one
relation from the previous owner and all subsequent relations do not involve
that owner. However if a pair of entities send funds back and forth, each owner
could collect a sum as you describe, if the counterparty (2) re-uses keys:
o2_inv*(x1 + x2)
The SE has similar relations in step (e) if there's key reuse. Therefore it's
important that on each transfer, you generate a new key and do not re-use keys.
A responsible SE could detect a key-reuse situation by e.g. recording old
pubkeys P1, P2 even though he deleted s1 and s2, and inform the user of the
key-reuse error and abort.
Do you think that works?
P.S. SGX is not "trust minimization", it's "trust transfer" -- specifically to
the keys managing the SGX. If we thought processor manufacturers were better at
key management than the rest of us, we should just hand them the task. I don't
think that's the case, and I don't think anyone else does either. An SGX
attestation as an optional add-on I think is a worthwhile enhancement, as long
as it's not on the critical path of the protocol.
Albert via bitcoin-dev [bitcoin-dev at lists.linuxfoundation.org] wrote:
> Hi,
>
> Great to see some work in this direction, here's some thoughts on your keygen
> scheme:
>
> In the scenario where Owner1=Owner2, that is, one of the owners sends some
> coins to itself, that owner would get to know both x1*s1 and x2*s2=
> x2*s1*o2_inv*o1, and, because he already knows o1 and o2, that implies
> knowledge of both x1*s1 and x2*s1 where x1 and x2 are random numbers sampled
> from an uniform distribution. Once the owner has these two numbers, he can just
> sum these together to obtain s1*(x1+x2).
> Now, because of the central limit theorem, the distribution of x1+x2 should
> approximate a normal one, concretely an Irwin–Hall distribution, with that
> approximation getting better when more numbers are collected through iterations
> of the protocol. Once you've collected enough numbers to approximate a normal
> well enough (looking at Irwin Hall distribution graphs^[1] you can observe that
> with less than 10 samples the distribution is already pretty similar to a
> normal one), it should be possible to drastically reduce the search space and
> apply brute force to guess the value of \sum x and, consequently, s1.
>
> Practically, it's possible that the search space is still too large for
> brute-force to be fruitful, so this attack might not work, but it shows that
> there is information leakage in every protocol iteration.
>
> On another note, if you are not already aware of, something which might be
> worth looking into is the possibility of further trust-minimising the SE role
> by forcing it's code to be run inside an AWS oracle or a hardware isolated
> processor such as SGX.
>
> Albert
>
> [1] https://en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution
>
> On Wed, Mar 25, 2020, at 9:52 PM, Tom Trevethan via bitcoin-dev wrote:
>
> Hi all,
>
> We are starting to work on an implementation of the statechains concept (
> https://medium.com/@RubenSomsen/
> statechains-non-custodial-off-chain-bitcoin-transfer-1ae4845a4a39), with
> particular interest in using the protocol enable the change of ownership
> (novation) of an individual position in an active discreet log contract
> (DLC) without an on-chain transaction, and without needing the cooperation
> of the counterparty. The protocol as outlined by Ruben requires features
> not currently available in Bitcoin (like SIGHASH_NOINPUT), and it is
> uncertain when (or even if) this will be added. So we are looking at
> variants that would work with current Bitcoin functionality, and it would
> be good to get some feedback on them.
>
> There are two main modifications we are looking at:
> 1. Instead of an eltoo-based backup/refund transaction (enabling the
> current owner to claim the UTXO in case the statechain entity disappears)
> we propose using a decrementing nLocktime for backup transactions as the
> output changes hands. Here, the first owner gets a backup transaction with
> an nLocktime at some future height (h0), then the next owner gets a backup
> transaction with nLocktime (h0-c) where c is a confirmation window. This
> approach has the downside of limiting the lifetime of the UTXO, but it also
> doesn't require the current owner to be always online.
>
> 2. Replacing the 2-of-2 multisig output (paying to statechain entity SE key
> and transitory key) with a single P2(W)PKH output where the public key
> shared between the SE and the current owner. The SE and the current owner
> can then sign with a 2-of-2 ECDSA MPC. This enables each owner to generate
> their own private key share, and the SE changes their key share at each
> change of ownership (with the shared public key remaining the same). This
> works as follows (.G is EC point multiplication, * is scalar
> multiplication):
>
> KeyGen:
>
> a. Owner 1 generates private key share o1 then calculates the corresponding
> public key of the share O1 and sends it to the SE: O1 = o1.G
> b. The SE then generates a private key: s1 (the SE private key share),
> calculates the corresponding public key and sends it to Owner 1: S1 = s1.G
> c. Both SE and Owner 1 then multiply the public keys they receive by their
> own private key shares to obtain the same shared public key P (which
> corresponds to a shared private key of p = o1*s1): P = o1.(s1.G) = s1.
> (o1.G)
> d. Owner 1 creates a funding transaction (Tx0) to pay an amount A to the
> address corresponding to P (but doesn't sign it).
> e. Once Owner 1 and SE cooperatively sign the first backup transaction,
> Owner 1 then signs and broadcasts the deposit transaction Tx0.
>
> Transfer from Owner 1 to Owner 2:
>
> a. Owner 2 generates two private keys: o2 (the new owner UTXO private key
> share) and b2 (the new owner refund private key).
> b. The SE generates a temporary blinding nonce x and calculates the value
> x*s1 and sends this securely to Owner 2.
> c. Owner 2 then multiplies this received value by the modular inverse of o2
> (o2_inv) and then sends this value (x*s1*o2_inv), to Owner 1.
> d. Owner 1 then multiplies this received value by the key share o1 and
> sends the resulting value (x*s1*o2_inv*o1) to the SE.
> e. The SE then multiplies this received value by the modular inverse of the
> temporary nonce (x_inv) to obtain x*s1*o2_inv*o1*x_inv. This cancels the
> blinding nonce x to give s1*o2_inv*o1. This value, when multiplied by the
> new owner key share o2 equals the original shared private key s1*o1.
> f. The SE then sets this value equal to s2 = s1*o2_inv*o1 and deletes s1.
> s2 and o2 are now the key shares of `P` and can be used to colaboritively
> sign (with 2P ECDSA). So long as the SE delets s1, the old owner key share
> (o1) is of no use in deriving or co-signing with the full shared private
> key, and is invalidated.
> g. The shared public key P remains unchanged, but the corresponding private
> key (which no individual party ever has knowledge of or can derive) can
> only be determined from the key shares of the SE and Owner 2 (i.e. P =
> s2*o2.G).
> h. Owner 2 then calculates their backup public key (B2 = b2.G) and sends it
> to the SE.
> i. The SE creates a backup transaction (Tx2) that pays the output of Tx0 to
> the address corresponding to B2 , with `nLockTime` set to a block height h0
> - c0, where c0, is a confirmation time sufficient to guarantee that Tx2 can
> be confirmed in the blockchain before Tx1 (therefore making Tx1 invalid).
> j. Owner 2 and the SE then cooperate to sign Tx2 with shared key (P) using
> the 2P ECDSA protocol, which Owner 2 then saves.
>
> The principle of the logic of the key transfer is that the two separate key
> shares are updated, but the full shared private key (which no-one knows)
> remains the same. The new owner chooses a new secret value for their
> private key share, and this (along with the private key share of the
> previous owner) is utilized by the SE to update their share. The use of the
> nonce (x) prevents any of the participants from determining any information
> about each others secret keys. In this way Owner 2 cannot determine s1 from
> x*s1, Owner 1 cannot determine s1 or o2 from x*s1*o2_inv and the SE cannot
> determine o1 or o2 from x*s1*o2_inv*o1.
>
> This transfer protocol can be repeated to transfer the ownership to new
> owners. Each time the SE key share sX is updated, the previous key shares
> become invalid and are of no use even if the current key share is
> subsequently revealed. The SE still needs to be trusted to delete the old
> key share, but this protocol removes the risk the the SE can be hacked by a
> previous owner to steal the funds.
>
> Any comments on the above would be greatly appreciated.
>
> Tom
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
>
> !DSPAM:5e7c2da240641930319229!
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
> !DSPAM:5e7c2da240641930319229!
--
Cheers, Bob McElrath
"For every complex problem, there is a solution that is simple, neat, and wrong."
-- H. L. Mencken

2023-06-07 20:22:41

- reply

📅 Original date posted:2020-02-01
📝 Original message:We propose that OP_CHECKTEMPLATEVERIFY should behave more like CHECKSIG,
including a flags byte that specify what is hashed. This unifies the ways a
SigHash is computed, differing only in the final checksig which is omitted in
favor of chacking the hash directly. Having two paths to create a signature hash
introduces extra complexity, especially as concerns potential future SIGHASH
flag upgrades.
CTV omits inputs as part of its semantics, so CTV-type functionality using
CHECKSIG is also achievable if some form of NOINPUT flag is also deployed. With
NOINPUT alone, a standard CHECKSIG can be used to implement a covenant -- though
it uses an unnecessarily large number of bytes just to check a 32-byte hash.
Therefore, any pitfalls CTV intends to evade can be evaded by using a CHECKSIG,
if NOINPUT is deployed in some form, adding new flexibility. Beyond what's
possible with NOINPUT/ANYPREVOUT, CTV additionally commits to:
»·······1. Number of inputs
»·······2. Number of outputs
»·······3. Index of input
The justification given for committing to the number of inputs and outputs is
that "it makes CTV hashes easier to compute with script", however doing so would
require OP_CAT. It's noted that both of these are actually redundant
commitments. Since the constexpr requirement was removed, if OP_CAT were
enabled, this commitment to the input index could be evaded by computing the CTV
hash within the script, modifying the input index using data taken from the
witness. Therefore committing to the input index is a sender-specified-policy
choice, and not an anti-footgun measure for the redeemer. As such, it's
appropriate to consider committing to the input index using a flag instead.
I believe the above may be possible *without* a new opcode and simply with a
sighash flag. That is, consider a flag SIGHASH_NOSIG which behaves as follows:
The stack is expected to contain <hash> <flags>, where the hash to be checked is
<hash> and is in the place where you'd normally put a pubkey. The byte <flags>
is the second thing on the stack. This is intended to be an empty "signature"
with the flags byte appended (which must contain SIGHASH_NOSIG to succeed).
There are probably reasons this might not work as a flag that I haven't
discovered yet. Alternatively CTV might be considered to be an alternative type
of CHECKSIG operator and might be renamed to CHECKSIGHASH, appending flag bytes
to the hash to be checked.
The flags discussed above, NOINPUT, NOSIG, INPUTINDEX are all really
sender-policy choices, while SIGHASH flags are redeemer-choice as they usually
occur in the witness. There's really no way currently for an output to specify
that the redeemer must use a particular set of flags. One way to achieve this is
to put the CHECKSIG(HASH) including its flags into the redeemScript -- which is
functionally what CTV does (or a CHECKSIG in a redeemScript using NOINPUT).
This is committed to in outputs and therefore specifies sender policies, however
the redeemScript is specified by the receiver. Perhaps an anti-footgun measure
would be to require that certain SIGHASH flags like these MUST be committed to
in the output, by the sender.
CSV (CHECKSEQUENCEVERIFY) is an example that redemption policies are committed
to in the output by the sender via the sequence_no field, and then checked with
an opcode OP_CSV to enable relative timelocks. It's probably possible to add new
flags to the sequence_no field, and check the new semantics with CSV instead of
an entiely new opcode.
As user policy choices, NOINPUT might be considered "MAY" conditions. A user MAY
use NOINPUT on an output, but let's not require it. Covenants on the other
hand, are a MUST condition. The CTV proposal imposes "MUST" conditions on the
existence of the covenant itself, as well as the number of inputs and outputs,
to prevent txid malleability so that such transactions can be used in offline
protocols. Txid non-malleability can be achieved by enforcing that the output
must be spent using SIGHASH_ALL instead of committing to the number of inputs
separately with a new opcode. The MUST condition also helps with sighash caching
for batch validation.
INPUTINDEX is required in a CTV/CHECKSIGHASH world because of the half-spend
problem. Normally outputs are spent uniquely as long as different addresses are
used on the outputs. A transaction with the same address appearing twice would
also have a half-spend problem. Anyone signing the first output and giving that
PSBT to another person can allow them to spend the second input. Therefore one
might even want INPUTINDEX for non-covenant transactions, though making a tx
with the same address twice seems like a silly idea to me.
Therefore, assuming a CSV-type mechanism can be devised using sequence_no, CTV
is equivalent to a flag in sequence_no that is logically
MUST|ALL|NOSIG|INPUTINDEX and a redeemScript of <hash> <flags>.
Lightning-like use cases might put sequence_no flags that are logically
MAY|ALL|NOINPUT.
The other mechanism for sender policy is scriptPubKey, which is heavily
restricted by isStandard, but might be another place to specify flags like the
above.
Thoughts?
Does this idea address any of the NOINPUT footguns? (which I'm not up on)
Is there a reason this cannot be done with sequence_no and OP_CSV?
Is there a reason that a separate opcode (CTV) is different/better than this
approach?
--
Cheers, Bob McElrath
"For every complex problem, there is a solution that is simple, neat, and wrong."
-- H. L. Mencken

2023-06-07 20:15:21

- reply

📅 Original date posted:2018-11-27
📝 Original message:I have been working on an experimental wallet that implements Bitcoin
Covenants/Vaults following a blog post I wrote about 2 years ago, using
"Pay-to-Timelock Signed Transaction" (P2TST). (Also mentioned recently by
kanzure in a talk somewheres...) The idea is that you deposit to an address for
which you don't know the private key. Instead you construct a second
transaction sending that to a timelocked staging address for which you DO have
the privkey (it also has an IF/ELSE condition with a second spending condition
for use in case of theft attempt). In order to do this you either have to
delete the privkey of the deposit address (a difficult proposition to know it's
actually been deleted), but instead one can construct a signature directly using
a RNG, and use the SIGHASH to compute the corresponding pubkey via ECDSA
recover, from which you compute the corresponding address. In this way your
wallet is a set of P2TST transactions and a corresponding privkey, with a (set
of) emergency keys.
This interacts with NOINPUT in the following way: if the input to the
transaction commits to the pubkey in any way, you have a circular dependency on
the pubkey that could only be satisfied by breaking a hash function. This
occurs with standard sighash's which commit to the txid, which in turn commit to
the address, which commits to the pubkey, so this construction of
covenants/vaults requires NOINPUT.
AFAICT sipa's proposal is compatible with the above vaulted construction by
using SIGHASH_NOINPUT | SIGHASH_SCRIPTMASK to remove the
scriptPubKey/redeemScript from the sighash. Putting the
scriptPubKey/redeemScript in the sighash introduces the same circular
dependency, but SIGHASH_SCRIPTMASK removes it.
One would probably want to provide the fee from a separate wallet so as to be
able to account for fluctuating fee pressures when the unvaulting occurs a long
time after vaulting. Thus you'd want to use SIGHASH_SINGLE so that a fee-wallet
can add fees (or for composability of P2TSTs), and SIGHASH_NOFEE as well.
P.S. Also very excited to combine the above idea with Taproot/Graftroot/g'Root.
--
Cheers, Bob McElrath
"For every complex problem, there is a solution that is simple, neat, and wrong."
-- H. L. Mencken

2023-06-07 19:50:26

- reply

📅 Original date posted:2016-05-11
📝 Original message:I like this idea, but let's run some numbers...
bfd--- via bitcoin-dev [bitcoin-dev at lists.linuxfoundation.org] wrote:
> A Bloom Filter Digest is deterministically created of every block
Bloom filters completely obfuscate the required size of the filter for a desired
false-positive rate. But, an optimal filter is linear in the number of elements
it contains for fixed false-positive rate, and logarithmic in the false-positive
rate. (This comment applies to a RLL encoded Bloom filter Greg mentioned, but
that's not the only way) That is for N elements and false positive rate
\epsilon:
filter size = - N \log_2 \epsilon
Given that the data that would be put into this particular filter is *already*
hashed, it makes more sense and is faster to use a Cuckoo[1] filter, choosing a
fixed false-positive rate, given expected wallet sizes. For Bloom filters,
multiply the above formula by 1.44.
To prevent light clients from downloading more blocks than necessary, the
false-positive rate should be roughly less than 1/(block height). If we take
the false positive rate to be 1e-6 for today's block height ~ 410000, this is
about 20 bits per element. So for todays block's, this is a 30kb filter, for a
3% increase in block size, if blocks commit to the filter. Thus the required
size of the filter commitment is roughly:
filter size = N \log_2 H
where H is the block height. If bitcoin had these filters from the beginning, a
light client today would have to download about 12MB of data in filters. My
personal SPV wallet is using 31MB currently. It's not clear this is a bandwidth
win, though it's definitely a win for computing load on full nodes.
[1] https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
--
Cheers, Bob McElrath
"For every complex problem, there is a solution that is simple, neat, and wrong."
-- H. L. Mencken
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20160511/90715bc8/attachment.sig>

2023-06-07 19:49:33

- reply

📅 Original date posted:2016-03-09
📝 Original message:Dave Hudson [dave at hashingit.com] wrote:
> A damping-based design would seem like the obvious choice (I can think of a
> few variations on a theme here, but most are found in the realms of control
> theory somewhere). The problem, though, is working working out a timeframe
> over which to run the derivative calculations.
>From a measurement theory perspective this is straightforward. Each block is a
measurement, and error propagation can be performed to derive an error on the
derivatives.
The statistical theory of Bitcoin's block timing is known as a Poisson Point
Process: https://en.wikipedia.org/wiki/Poisson_point_process or temporal point
process. If you google those plus "estimation" you'll find a metric shit-ton of
literature on how to handle this.
> The problem is the measurement of the hashrate, which is pretty inaccurate at
> best because even 2016 events isn't really enough (with a completely constant
> hash rate running indefinitely we'd see difficulty swings of up to +/- 5% even
> with the current algorithm). In order to meaningfully react to a major loss
> of hashing we'd still need to be considering a window of probably 2 weeks.
You don't want to assume it's constant in order to get a better measurement.
The assumption is clearly false. But, errors can be calculated, and retargeting
can take errors into account, because no matter what we'll always be dealing
with a finite sample.
Personally I don't think difficulty target variations are such a big deal, if
the algorithm targets that over any long time interval, the average block time
is 10 min. Bitcoin's current algorithm fails here, with increasing hashrate (as
we have), it issues coins faster than its assumed schedule.
--
Cheers, Bob McElrath
"For every complex problem, there is a solution that is simple, neat, and wrong."
-- H. L. Mencken

2023-06-07 19:49:32

- reply

📅 Original date posted:2016-03-08
📝 Original message:Dave Hudson via bitcoin-dev [bitcoin-dev at lists.linuxfoundation.org] wrote:
> I think the biggest question here would be how would the difficulty
> retargeting be changed? Without seeing the algorithm proposal it's difficult
> to assess the impact that it would have, but my intuition is that this is
> likely to be problematic.
I have no comment on whether this will be *needed* but there's a simple
algorithm that I haven't seen any coin adopt, that I think needs to be: the
critically damped harmonic oscillator:
http://mathworld.wolfram.com/CriticallyDampedSimpleHarmonicMotion.html
In dynamical systems one does a derivative expansion. Here we want to find the
first and second derivatives (in time) of the hashrate. These can be determined
by a method of finite differences, or fancier algorithms which use a quadratic
or quartic polynomial approximation. Two derivatives are generally all that is
needed, and the resulting dynamical system is a damped harmonic oscillator.
A damped harmonic oscillator is basically how your car's shock absorbers work.
The relevant differential equation has two parameters: the oscillation frequency
and damping factor. The maximum oscillation frequency is the block rate. Any
oscillation faster than the block rate cannot be measured by block times. The
damping rate is an exponential decay and for critical damping is twice the
oscillation frequency.
So, this is a zero parameter, optimal damping solution for a varying hashrate.
This is inherently a numeric approximation solution to a differential equation,
so questions of approximations for the hashrate enter, but that's all. Weak
block proposals will be able to get better approximations to the hashrate.
If solving this problem is deemed desirable, I can put some time into this, or
direct others as to how to go about it.
--
Cheers, Bob McElrath
"For every complex problem, there is a solution that is simple, neat, and wrong."
-- H. L. Mencken

2023-06-07 19:47:15

- reply

📅 Original date posted:2015-12-30
📝 Original message:Jonathan Toomim [j at toom.im] wrote:
>
> The generalized softfork method has the advantage of being merge-mined
That's an over-generalization. There are two kinds of soft-forks WRT mining,
those which:
1. involve new validation rules by data-hiding from non-upgraded modes
(e.g. extension blocks, generalized softfork)
2. involve NO new validation logic (e.g. P2SH)
Miners which are not validating transactions *should* be deprived of revenue,
because their role is transaction validation, not simply brute forcing sha256d.
So I'm very strongly against this "generalized softfork" idea -- I also don't
see how upgraded nodes and non-upgraded nodes can possibly end up with the same
UTXO set.
> > Once a chain is seen to be 6 or more blocks ahead of my chain tip, we should
> > enter "zombie mode" and refuse to mine or relay
>
> I like this method. However, it does have the problem of being voluntary. If
> nodes don't upgrade to a version that has the latent zombie gene long before a
> fork, then it does nothing.
Which is why it should be put into core long before forks. ;-)
--
Cheers, Bob McElrath
"For every complex problem, there is a solution that is simple, neat, and wrong."
-- H. L. Mencken

2023-06-07 19:47:14

- reply

📅 Original date posted:2015-12-30
📝 Original message:joe2015--- via bitcoin-dev [bitcoin-dev at lists.linuxfoundation.org] wrote:
> That's the whole point. After a conventional hardfork everyone
> needs to upgrade, but there is no way to force users to upgrade. A
> user who is simply unaware of the fork, or disagrees with the fork,
> uses the old client and the currency splits.
>
> Under this proposal old clients effectively enter "zombie" mode,
> forcing users to upgrade.
This is a very complex way to enter zombie mode.
A simpler way is to track valid PoW chains by examining only the header, that
are rejected for other reasons.
Once a chain is seen to be 6 or more blocks ahead of my chain tip, we should
enter "zombie mode" and refuse to mine or relay, and alert the operator, because
we don't know what we're doing and we're out of date. This way doesn't require
any modifications to block structure at all.
--
Cheers, Bob McElrath
"For every complex problem, there is a solution that is simple, neat, and wrong."
-- H. L. Mencken

2023-06-07 19:46:55

- reply

📅 Original date posted:2015-12-19
📝 Original message:Peter Todd via bitcoin-dev [bitcoin-dev at lists.linuxfoundation.org] wrote:
> One of the issues raised by the pools present was block withholding
> attacks, which they said are a real issue for them. In particular, pools
> are receiving legitimate threats by bad actors threatening to use block
> withholding attacks against them.
The only possible other bad actors are other miners. So who are the "bad actor"
miners? It's a short list of candidates.
> P2Pool is often brought up as a replacement for pools, but it itself is still
> relatively vulnerable to block withholding, and in any case has many other
> vulnerabilities and technical issues that has prevented widespread adoption of
> P2Pool.
I've been trying to understand this source of "vulnerabilities and technical
issues" with p2pool and have received a lot of contradictory information. Can
someone in the know summarize what the problems with p2pool are?
The economic situation where miners can be deprived of profit due to the lack of
synchronicity in block updates is a physics problem due to the size of the Earth
and will never be removed. This is a design flaw in Bitcoin. Therefore a
different, more comprehensive solution is called for.
My solution to this is somewhat longer term and needs more simulation but
fundamentally removes the source of contention and fixes the design flaw, while
remaining as close "in spirit" to bitcoin as possible:
https://scalingbitcoin.org/hongkong2015/presentations/DAY2/2_breaking_the_chain_1_mcelrath.pdf
Not only does block withholding simply not work to deny other miners income due
to the absence of orphans, but I explicitly added a dis-incentive against
withholding blocks in terms of the "cohort difficulty". Other graph-theoretic
quantities are in general possible in the reward function to better align the
incentives of miners with the correct operation of the system. Also by lowering
the target difficulty and increasing the block (bead) rate, one lowers the
variance of miner income.
Part of the reason I ask is that there has been some interest in testing my
ideas in p2pool itself (or a new similar share pool), but I'm failing to
understand the source of all the complaints about p2pool.
--
Cheers, Bob McElrath
"For every complex problem, there is a solution that is simple, neat, and wrong."
-- H. L. Mencken

2023-06-07 19:44:21

- reply

📅 Original date posted:2015-11-09
📝 Original message:I would expect that since a block contains mostly hashes and crypto signatures,
it would be almost totally incompressible. I just calculated compression ratios:
zlib -15% (file is LARGER)
gzip 28%
bzip2 25%
So zlib compression is right out. How much is ~25% bandwidth savings worth to
people? This seems not worth it to me. :-/
Peter Tschipper via bitcoin-dev [bitcoin-dev at lists.linuxfoundation.org] wrote:
> This is my first time through this process so please bear with me.
>
> I opened a PR #6973 this morning for Zlib Block Compression for block
> relay and at the request of @sipa this should have a BIP associated
> with it. The idea is simple, to compress the datastream before
> sending, initially for blocks only but it could theoretically be done
> for transactions as well. Initial results show an average of 20% block
> compression and taking 90 milliseconds for a full block (on a very slow
> laptop) to compress. The savings will be mostly in terms of less
> bandwidth used, but I would expect there to be a small performance gain
> during the transmission of the blocks particularly where network latency
> is higher.
>
> I think the BIP title, if accepted should be the more generic, "Support
> for Datastream Compression" rather than the PR title of "Zlib
> Compression for block relay" since it could also be used for
> transactions as well at a later time.
>
> Thanks for your time...
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
> !DSPAM:5640ff47206804314022622!
--
Cheers, Bob McElrath
"For every complex problem, there is a solution that is simple, neat, and wrong."
-- H. L. Mencken

2023-06-07 19:43:29

- reply

📅 Original date posted:2015-10-14
📝 Original message:So it seems to me that all I need to do is figure out who the current leader is,
and DDoS him off the network to shut Bitcoin-NG down.
This is a significant advantage to bitcoin's ex-post-facto blocks: no one knows
where the next one will come from. The only way to shut the network down is to
shut all nodes down.
Emin Gün Sirer via bitcoin-dev [bitcoin-dev at lists.linuxfoundation.org] wrote:
> Hi everyone,
>
> We just released the whitepaper describing Bitcoin-NG, a new technique for
> addressing some of the scalability challenges faced by Bitcoin. Surprisingly,
> Bitcoin-NG can simultaneously increase throughput while reducing latency, and
> do so without impacting Bitcoin's open architecture or changing its trust
> model. This post illustrates the core technique:
> http://hackingdistributed.com/2015/10/14/bitcoin-ng/
> while the whitepaper has all the nitty gritty details:
> http://arxiv.org/abs/1510.02037
>
> Fitting NG on top of the current Bitcoin blockchain is future work that we
> think is quite possible. NG is compatible with both Bitcoin as is, as well as
> Blockstream-like sidechains, and we currently are not planning to compete
> commercially with either technology -- we see NG as being complementary to both
> efforts. This is pure science, published and shared with the community to
> advance the state of blockchains and to help them reach throughputs and
> latencies required of cutting edge fintech applications. Perhaps it can be
> adopted, or perhaps it can provide the spark of inspiration for someone else to
> come up with even better solutions.
>
> We would be delighted to hear your feedback.
> - Ittay Eyal and E. Gün Sirer.
>
> !DSPAM:561e98cd301391127216946!
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
> !DSPAM:561e98cd301391127216946!
--
Cheers, Bob McElrath
"For every complex problem, there is a solution that is simple, neat, and wrong."
-- H. L. Mencken