<unnamed>

Public Key

npub1ldcq03p2qe58u0xnlwa35wchjuhz49y6ueu5ghmtjetez9xstnvsmt8ur6

Profile Code

nprofile1qqs0kuq8cs4qv6r78nflhwc68vtewt32jjdwv72yta4ev4u3zng9ekgpzemhxue69uhhyetvv9ujuurjd9kkzmpwdejhgcehkgj

Publishing to

relay.primal.net

Last Notes

2023-06-07 23:16:53 UTC

- reply

📅 Original date posted:2022-11-08
📝 Original message:On Tue, Nov 8, 2022 at 2:13 AM Salvatore Ingala via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> I have been working on some notes to describe an approach that uses
> covenants in order to enable general smart contracts in bitcoin. You can
> find them here:
>
> https://merkle.fun/
> <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>
>
Hash chained covenants in general all have about the same plateau of
functionality, which seems roughly reasonable to add to Bitcoin as it is
today but suffer from being limited and hence likely only a stepping stone
to greater functionality and unless whatever's put in now cleanly extends
to supporting more in the future it's likely to turn into a legacy
appendage which has to be supported. So my generic suggestion for this sort
of thing is that it should be proposed along with a plan for how it could
be extended to support full-blown covenants in the future.
Another probably unhelpful bit of feedback I have is that Bitcoin should
probably be taking verkle trees seriously because those can have
substantially lower size/cost/weight than merkle trees. That doesn't just
apply to this proposal, but to Bitcoin in general, which doesn't seem to
have any serious verkle tree proposals to date.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20221108/783dabea/attachment.html>

2023-06-07 23:11:43 UTC

- reply

📅 Original date posted:2022-07-11
📝 Original message:On Mon, Jul 11, 2022 at 2:53 PM Peter Todd <pete at petertodd.org> wrote:
>
> The only type of fee-smoothing scheme that is feasible is to smooth an
> entirely
> separate category of fees that are made mandatory. For example, you could
> achieve the economic impact of inflation by having a fixed value*time
> based fee
> that goes to timelocked anyone-can-spend outputs in the coinbase to push
> the
> fee forward to other miners.
>
I'm not sure what the implications would be of charging coins for moving
based on their value times how long since they last moved would be (I
*think* that's what you're suggesting). It isn't obviously bad, but feels
weird to me.
That said, a scheme which would work would be to have a fixed minimum fee
of satoshis/vbyte which is required to be repaid out by the miner into a
pool and they get back a fixed fraction of what was in that pool. The pool
could simply be a rolling coin which keeps the balance. That's still a bit
ugly but doesn't lessen block size significantly, is fairly coherent, and
is a soft fork. It's the best emergency measure I'm aware of.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220711/519eb7bd/attachment.html>

2023-06-07 23:11:39 UTC

- reply

📅 Original date posted:2022-07-11
📝 Original message:If transaction fees came in at an even rate over time all at the exact same
level then they work fine for security, acting similarly to fixed block
rewards. Unfortunately that isn't how it works in the real world. There's a
very well established day/night cycle with fees going to zero overnight and
even longer gaps on weekends and holidays. If in the future Bitcoin is
entirely dependent on fees for security (scheduled very strongly) and this
pattern keeps up (overwhelmingly likely) then this is going to become a
serious problem.
What's likely to happen is that at first there will simply be no or very
few blocks mined overnight. There are likely to be some, as miners at first
turn off their mining rigs completely overnight then adopt the more
sophisticated strategy of waiting until there are enough fees in the
mempool to warrant attempting to make a block and only then doing it.
Unfortunately the gaming doesn't end there. Eventually the miners with
lower costs of operation will figure out that they can collectively reorg
the last hour (or some time period) of the day overnight and this will be
profitable. That's likely to cause the miners with more expensive
operations to stop attempting mining the last hour of the day preemptively.
What happens after that I'm not sure. There are a small enough number of
miners with a quirky enough distribution of costs of operation and
profitability that the dynamic is heavily dependent on those specifics, but
the beginnings of a slippery slope to a mining cabal which reorgs everyone
else out of existence and eventually 51% attacks the whole thing have
begun. It even gets worse than that because once there's a cabal
aggressively reorging anyone else out when they make a block other miners
will shut down and rapidly lose the ability to quickly spin up again, so
the threshold needed for that 51% attack will keep going down.
In short, relying completely on transaction fees for security is likely to
be a disaster. What we can say from existing experience is that having
transaction fees be about 10% of rewards on average works well. It's enough
to incentivize collecting fees but not so much that it makes incentives get
all weird. 90% transaction fees is probably very bad. 50% works but runs
the risk of spikes getting too high.
There are a few possible approaches to fixes. One would be to drag most of
east asia eastward to a later time zone thus smoothing out the day/night
cycle but that's probably unrealistic. Another would be to hard fork in
fixed rewards in perpetuity, which is slightly less unrealistic but still
extremely problematic.
Much more actionable are measures which smooth out fees over time. Having
wallets opportunistically collect their dust during times of low
transaction fees would help and would save users on fees. Also making UX
which clarifies when things are likely to take a day or week but that it's
reliable would be a reasonable thing to do, but users unfortunately are
very averse to transactions taking a while.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220711/27bad65b/attachment.html>

2023-06-07 23:11:36 UTC

- reply

📅 Original date posted:2022-07-11
📝 Original message:On Mon, Jul 11, 2022 at 10:00 AM Peter Todd via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> If you actually do the numbers on this, you'll realize it takes absolutely
> catastrophic black swan events that make WW2 look like a minor conflict to
> make
> even insignificant inflation rate changes due to changes in lost coins.
>
That somewhat depends on what you mean by 'significant' and 'catastrophic'
but I believe the way the model goes is that if X% of coins are lost that
means that the value of all outstanding coins will go up by X%, and if the
rate of breakage goes from Y% annually to Y*Z% annually then the value of
all coins will go up by a factor of Z. This is of course an idealized model
in steady state, but gives some idea of scale.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220711/81d9948d/attachment-0001.html>

2023-06-07 23:11:15 UTC

- reply

📅 Original date posted:2022-07-07
📝 Original message:Part of the rules of my challenge is that the 'new' words need to be in the
same pool as the 'old' words, so any ordering is okay. Without that
requirement it's mathematically very straightforward.
On Thu, Jul 7, 2022 at 10:52 AM Pavol Rusnak <stick at satoshilabs.com> wrote:
> There is. Just encode the index of permutation used to scramble the
> otherwise sorted list. For 12 words you need to store 12! = ~32 bits so 3
> words should be enough.
>
> Repetitions make this more difficult, though.
>
> On Thu 7. 7. 2022 at 19:41, Bram Cohen via bitcoin-dev <
> bitcoin-dev at lists.linuxfoundation.org> wrote:
>
>> On Thu, Jul 7, 2022 at 7:43 AM Anton Shevchenko via bitcoin-dev <
>> bitcoin-dev at lists.linuxfoundation.org> wrote:
>>
>>> I made a python implementation for a different mnemonic encoding. The
>>> encoding requires user to remember words but not the order of those words.
>>> The code is open (MIT license) at https://github.com/sancoder/noomnem
>>
>>
>> Thanks Anton. There's an interesting mathematical question of whether
>> it's possible to make a code like this which always uses the BIP-39 words
>> for the same key as part of its encoding, basically adding a few words as
>> error correction in case the order is lost or confused. If the BIP-39
>> contains a duplicate you can add an extra word.
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
> --
> Best Regards / S pozdravom,
>
> Pavol "stick" Rusnak
> Co-Founder, SatoshiLabs
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220707/72c4a5e7/attachment.html>

2023-06-07 23:11:14 UTC

- reply

📅 Original date posted:2022-07-07
📝 Original message:On Thu, Jul 7, 2022 at 7:43 AM Anton Shevchenko via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> I made a python implementation for a different mnemonic encoding. The
> encoding requires user to remember words but not the order of those words.
> The code is open (MIT license) at https://github.com/sancoder/noomnem
Thanks Anton. There's an interesting mathematical question of whether it's
possible to make a code like this which always uses the BIP-39 words for
the same key as part of its encoding, basically adding a few words as error
correction in case the order is lost or confused. If the BIP-39 contains a
duplicate you can add an extra word.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220707/557f4041/attachment.html>

2023-06-07 23:05:23 UTC

- reply

📅 Original date posted:2022-03-16
📝 Original message:On Wed, Mar 9, 2022 at 10:47 PM Anthony Towns <aj at erisian.com.au> wrote:
>
> To redo the singleton pattern in bitcoin's context, I think you'd have
> to pass in both the full tx you're spending (to be able to get the
> txid of its parent) and the full tx of its parent (to be able to get
> the scriptPubKey that your utxo spent) which seems klunky but at least
> possible (you'd be able to drop the witness data at least; without that
> every tx would be including the entire history of the singleton).
>
Yes that's the idea. Since the parent transaction is in the blockchain it
could be pulled in automatically without having to charge vbytes for it.
> If softfork is just doing a best effort for whatever opcodes it knows
> about, and otherwise succeeding, then it has to succeed, and your
> script/output has become anyone-can-spend.
>
That can be alleviated by when things call untrusted code they can wrap it
in a guard which can be the soft fork opcode itself.
>
> On the other hand, if you could tell the softfork op that you only wanted
> ops up-to-and-including the 118 softfork, then it could reject fakeopcode
> and fail the script, which I think gives the desirable behaviour.
>
A simple approach to versioning like that may be more expedient. Soft
forking in CLVM isn't implemented yet.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220315/ccdf755f/attachment.html>

2023-06-07 23:05:22 UTC

- reply

📅 Original date posted:2022-03-09
📝 Original message:On Mon, Mar 7, 2022 at 5:27 PM Anthony Towns <aj at erisian.com.au> wrote:
> One way to match the way bitcoin do things, you could have the "list of
> extra conditions" encoded explicitly in the transaction via the annex,
> and then check the extra conditions when the script is executed.
>
The conditions are already basically what's in transactions. I think the
only thing missing is the assertion about one's own id, which could be
added in by, in addition to passing the scriptpubkey the transaction it's
part of, also passing in the index of inputs which it itself is.
>
> > If you're doing everything from scratch it's cleaner to go with the coin
> > set model, but retrofitting onto existing Bitcoin it may be best to leave
> > the UTXO model intact and compensate by adding a bunch more opcodes which
> > are special to parsing Bitcoin transactions. The transaction format
> itself
> > can be mostly left alone but to enable some of the extra tricks (mostly
> > implementing capabilities) it's probably a good idea to make new
> > conventions for how a transaction can have advisory information which
> > specifies which of the inputs to a transaction is the parent of a
> specific
> > output and also info which is used for communication between the UTXOs
> in a
> > transaction.
>
> I think the parent/child coin relationship is only interesting when
> "unrelated" spends can assert that the child coin is being created -- ie
> things along the lines of the "transaction sponsorship" proposal. My
> feeling is that complicates the mempool a bit much, so is best left for
> later, if done at all.
>
The parent/child relationship is mostly about implementing capabilities.
There's this fundamental trick, sort of the ollie of UTXO programming,
where to make a coin have a capability you have a wrapper around an inner
puzzle for it where the wrapper asserts 'my parent must either be the
unique originator of this capability or also have this same wrapper' and it
enforces that by being given a reveal of its parent and told/asserting its
own id which it can derive from that parent. The main benefit of the coin
set approach over UTXO is that it reduces the amount of stuff to be
revealed and string mangling involved in the parentage check.
>
> (I think the hard part of managing the extra conditions is mostly
> in keeping it efficient to manage the mempool and construct the most
> profitable blocks/bundles, rather than where the data goes)
>
Not sure what you mean by this. Conditions map fairly closely with what's
in Bitcoin transactions and are designed so to be monotonic and so the
costs and fees are known up front. The only way two transactions can
conflict with each other is if they both try to spend the same coin.
> > They're radically different approaches and
> > it's hard to see how they mix. Everything in lisp is completely
> sandboxed,
> > and that functionality is important to a lot of things, and it's really
> > normal to be given a reveal of a scriptpubkey and be able to rely on your
> > parsing of it.
>
> The above prevents combining puzzles/solutions from multiple coin spends,
> but I don't think that's very attractive in bitcoin's context, the way
> it is for chia. I don't think it loses much else?
>
Making something lisp-based be a completely alternative script type would
also be my preferred approach.
> > A nice side benefit of sticking with the UTXO model is that the soft fork
> > hook can be that all unknown opcodes make the entire thing automatically
> > pass.
>
> I don't think that works well if you want to allow the spender (the
> puzzle solution) to be able to use opcodes introduced in a soft-fork
> (eg, for graftroot-like behaviour)?
>
This is already the approach to soft forking in Bitcoin script and I don't
see anything wrong with it. You shouldn't write scripts using previously
unrecognized opcodes until after they've been soft forked into having real
functionality, and if you do that and accidentally write an anyonecanspend
that's your own fault.
> Having third parties be able to link their spends to yours complicates
> mempool behaviour a fair bit (see the discussions on pinning wrt
> lightning txs -- and that's only with direct participants being able to
> link transactions).
Bitcoin already has that with spending of transaction outputs, and Chia's
mempool doesn't currently let transactions depend on other transactions in
the mempool. If you do have that sort of dependency, you should have to
smush both transactions together to make a single larger transaction and
make it have enough of a fee to replace the smaller one.
I'm pretty skeptical about having a database of large script snippets
> that will hopefully be reused in the future.
>
That database is just the list of old blocks which can be dredged up to
have code pulled out of them.
> In chia the "scriptPubKey" is the hash of a lisp program, and when you
> create a new coin, the "scriptPubKey" of the newly generated coin is
> also the output of a lisp program. So writing a quine gets you general
> recursive covenants in a pretty straight forward way, as I understand it.
>
Usually you don't quite write a quine because you can be passed in your own
code and assert your own id derived from it, but that's the basic idea. You
need to validate your own id anyway when you have a capability.
> Rather than a "transaction" containing "inputs/outputs", chia has spend
> bundles that spend and create coins; and spend bundles can be merged
> together, so that a block only has a single spend bundle. That spend
> bundle joins all the puzzles (the programs that, when hashed match
> the scriptPubKey) and solutions (scriptSigs) for the coins being spent
> together.
>
I often refer to spend bundles as 'transactions'. Hope that isn't too
confusing. They serve the same function in the mempool.
>
> I /think/ the compression hook would be to allow you to have the puzzles
> be (re)generated via another lisp program if that was more efficient
> than just listing them out.
It literally has a lisp program called the generator which returns the list
of puzzle reveals and transactions. The simplest version of that program is
to return a quoted list.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220308/14bf1b2c/attachment-0001.html>

2023-06-07 23:05:21 UTC

- reply

📅 Original date posted:2022-03-16
📝 Original message:On Wed, Mar 9, 2022 at 6:30 AM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> I am pointing out that:
>
> * We want to save bytes by having multiple inputs of a transaction use the
> same single signature (i.e. sigagg).
>
> is not much different from:
>
> * We want to save bytes by having multiple inputs of a transaction use the
> same `scriptPubKey` template.
>
Fair point. In the past Bitcoin has been resistant to such things because
for example reusing pubkeys can save you from having to separately pay for
the reveals of all of them but letting people get credit for that
incentivizes key reuse which isn't such a great thing.
>
> > > For example you might have multiple HTLCs, with mostly the same code
> except for details like who the acceptor and offerrer are, exact hash, and
> timelock, and you could claim multiple HTLCs in a single tx and feed the
> details separately but the code for the HTLC is common to all of the HTLCs.
> > > You do not even need to come from the same protocol if multiple
> protocols use the same code for implementing HTLC.
> >
> > HTLCs, at least in Chia, have embarrassingly little code in them. Like,
> so little that there's almost nothing to compress.
>
> In Bitcoin at least an HTLC has, if you remove the `OP_PUSH`es, by my
> count, 13 bytes.
> If you have a bunch of HTLCs you want to claim, you can reduce your
> witness data by 13 bytes minus whatever number of bytes you need to
> indicate this.
> That amounts to about 3 vbytes per HTLC, which can be significant enough
> to be worth it (consider that Taproot moving away from encoded signatures
> saves only 9 weight units per signature, i.e. about 2 vbytes).
>
Oh I see. That's already extremely small overhead. When you start
optimizing at that level you wind up doing things like pulling all the
HTLCs into the same block to take the overhead of pulling in the template
only once.
>
> Do note that PTLCs remain more space-efficient though, so forget about
> HTLCs and just use PTLCs.
>
It makes a lot of sense to make a payment channel system using PTLCs and
eltoo right off the bat but then you wind up rewriting everything from
scratch.
> > > This does not apply to current Bitcoin since we no longer accept a
> SCRIPT from the spender, we now have a witness stack.
> >
> > My mental model of Bitcoin is to pretend that segwit was always there
> and the separation of different sections of data is a semantic quibble.
>
> This is not a semantic quibble --- `witness` contains only the equivalent
> of `OP_PUSH`es, while `scriptSig` can in theory contain non-`OP_PUSH`
> opcodes.
> xref. `1 RETURN`.
>
It's very normal when you're using lisp for snippets of code to be passed
in as data and then verified and executed. That's enabled by the extreme
adherence to no side effects.
> This makes me kinda wary of using such covenant features at all, and if
> stuff like `SIGHASH_ANYPREVOUT` or `OP_CHECKTEMPLATEVERIFY` are not added
> but must be reimplemented via a covenant feature, I would be saddened, as I
> now have to contend with the complexity of covenant features and carefully
> check that `SIGHASH_ANYPREVOUT`/`OP_CHECKTEMPLATEVERIFY` were implemented
> correctly.
>
Even the 'standard format' transaction which supports taproot and graftroot
is implemented in CLVM. The benefit of this approach is that new
functionality can be implemented and deployed immediately rather than
having to painstakingly go through a soft fork deployment for each thing.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220315/eeccf5c8/attachment-0001.html>

2023-06-07 23:05:19 UTC

- reply

📅 Original date posted:2022-03-19
📝 Original message:On Wed, Mar 16, 2022 at 7:54 AM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> My point is that in the past we were willing to discuss the complicated
> crypto math around cross-input sigagg in order to save bytes, so it seems
> to me that cross-input compression of puzzles/solutions at least merits a
> discussion, since it would require a lot less heavy crypto math, and *also*
> save bytes.
>
When using BLS signatures all that math is much simpler. You use a single
aggregated signature and always aggregate everything all the time.
I think there are two costs here:
>
> * Cost of bytes to transmit over the network.
> * Cost of CPU load.
>
There are three potential costs: CPU, bytes, and making outputs. In Chia
it's balanced so that the costs to a standard transaction in all three
buckets are roughly the same. In Bitcoin the three are implicitly tied to
each other by design which makes vbytes work okayish for Bitcoin Script as
it exists today.
> It seems to me that lisp-generating-lisp compression would reduce the cost
> of bytes transmitted, but increase the CPU load (first the metaprogram
> runs, and *then* the produced program runs).
>
Nah, CPU costs are dominated by signatures. Simple operations like applying
some parameters to a template don't add much.
> Not being a mathist, I have absolutely no idea, but: at least as I
> understood from the original mimblewimble.txt from Voldemort, BLS
> signatures had an additional assumption, which I *think* means
> "theoretically less secure than SECP256K1 Schnorr / ECDSA".
> Is my understanding correct?
> And if so, how theoretical would that be?
>
It includes some an extra cryptographic assumption but it's extremely
theoretical, having more to do with guessing what size of group provides
comparable security in number of bits than whether the whole approach is in
question. BLS12-381 is fairly conservative.
>
> PTLC signatures have the very nice property of being indistinguishable
> from non-PTLC signatures to anyone without the adaptor, and I think
> privacy-by-default should be what we encourage.
>
You do lose out on that when you aggregate.
> > I'm not sure that a "covenant language implementation" would necessarily
> > be "that" complicated. And if so, having a DSL for covenants could,
> > at least in theory, make for a much simpler implementation of
> > ANYPREVOUT/CTV/TLUV/EVICT/etc than doing it directly in C++, which
> > might mean those things are less likely to have "weird surprises" rather
> > than more.
>
> <rant>
> DSLs?
> Domain-specific languages?
>
Bitcoin Script is already a domain specific language, and the point of
adding in a lisp-family language would be to make it so that covenants and
capabilities can be implemented in the same language as is used for regular
coin scripting. The idea is to get off the treadmill of soft forking in
language features every time new functionality is wanted and make it
possible to implement all that on chain.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220319/9f946703/attachment.html>

2023-06-07 23:05:18 UTC

- reply

📅 Original date posted:2022-03-16
📝 Original message:On Thu, Mar 10, 2022 at 8:46 PM Anthony Towns <aj at erisian.com.au> wrote:
> Note that PTLCs aren't really Chia-friendly, both because chia doesn't
> have secp256k1 operations in the first place, but also because you can't
> do a scriptless-script because the information you need to extract
> is lost when signatures are non-interactively aggregated via BLS --
> so that adds an expensive extra ECC operation rather than reusing an
> op you're already paying for (scriptless script PTLCs) or just adding
> a cheap hash operation (HTLCs).
>
The CLVM currently supports BLS12-381 group 1 point operations which it
uses to support taproot which I think is enough to support PTLCs but
obviously isn't compatible with secp. In the future there will likely be a
soft fork to include a complete set of BLS12-381 operations mostly to
support ZK implementation.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220315/497a7250/attachment.html>

2023-06-07 23:05:17 UTC

- reply

📅 Original date posted:2022-03-09
📝 Original message:On Mon, Mar 7, 2022 at 7:06 PM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
>
> But cross-input signature aggregation is a nice-to-have we want for
> Bitcoin, and, to me, cross-input sigagg is not much different from
> cross-input puzzle/solution compression.
>
Cross-input signature aggregation has a lot of headaches unless you're
using BLS signatures, in which case you always aggregate everything all the
time because it can be done after the fact noninteractively. In that case
it makes sense to have a special aggregated signature which always comes
with a transaction or block. But it might be a bit much to bundle both lisp
and BLS support into one big glop.
>
> For example you might have multiple HTLCs, with mostly the same code
> except for details like who the acceptor and offerrer are, exact hash, and
> timelock, and you could claim multiple HTLCs in a single tx and feed the
> details separately but the code for the HTLC is common to all of the HTLCs.
> You do not even need to come from the same protocol if multiple protocols
> use the same code for implementing HTLC.
>
HTLCs, at least in Chia, have embarrassingly little code in them. Like, so
little that there's almost nothing to compress.
> This does not apply to current Bitcoin since we no longer accept a SCRIPT
> from the spender, we now have a witness stack.
>
My mental model of Bitcoin is to pretend that segwit was always there and
the separation of different sections of data is a semantic quibble.
> So this seems to be more like "do not write broken SCRIPTs"?
>
In general if people footgun that's their own fault. The resistance to
covenants and capabilities in the past has largely been around what would
happen if you had opt-out covenants which acted as riders and could monkey
around in later spends which were none of their business. But if they're
fully baked into the scriptpubkey then they're opted into by the recipient
and there aren't any weird surprises.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220308/5137151d/attachment-0001.html>

2023-06-07 23:05:14 UTC

- reply

📅 Original date posted:2022-03-07
📝 Original message:>
> After looking into it, I actually think chia lisp [1] gets pretty much all
> the major design decisions pretty much right. There are obviously a few
> changes needed given the differences in design between chia and bitcoin:
>
> - having secp256k1 signatures (and curve operations), instead of
> BLS12-381 ones
>
> - adding tx introspection instead of having bundle-oriented CREATE_COIN,
> and CREATE/ASSERT results [10]
>
Bitcoin uses the UTXO model as opposed to Chia's Coin Set model. While
these are close enough that it's often explained as Chia uses the UTXO
model but that isn't technically true. Relevant to the above comment is
that in the UTXO model transactions get passed to a scriptpubkey and it
either assert fails or it doesn't, while in the coin set model each puzzle
(scriptpubkey) gets run and either assert fails or returns a list of extra
conditions it has, possibly including timelocks and creating new coins,
paying fees, and other things.
If you're doing everything from scratch it's cleaner to go with the coin
set model, but retrofitting onto existing Bitcoin it may be best to leave
the UTXO model intact and compensate by adding a bunch more opcodes which
are special to parsing Bitcoin transactions. The transaction format itself
can be mostly left alone but to enable some of the extra tricks (mostly
implementing capabilities) it's probably a good idea to make new
conventions for how a transaction can have advisory information which
specifies which of the inputs to a transaction is the parent of a specific
output and also info which is used for communication between the UTXOs in a
transaction.
But one could also make lisp-generated UTXOs be based off transactions
which look completely trivial and have all their important information be
stored separately in a new vbytes area. That works but results in a bit of
a dual identity where some coins have both an old style id and a new style
id which gunks up what
>
> - serialization seems to be a bit verbose -- 100kB of serialized clvm
> code from a random block gzips to 60kB; optimising the serialization
> for small lists, and perhaps also for small literal numbers might be
> a feasible improvement; though it's not clear to me how frequently
> serialization size would be the limiting factor for cost versus
> execution time or memory usage.
>
A lot of this is because there's a hook for doing compression at the
consensus layer which isn't being used aggressively yet. That one has the
downside that the combined cost of transactions can add up very
nonlinearly, but when you have constantly repeated bits of large
boilerplate it gets close and there isn't much of an alternative. That said
even with that form of compression maxxed out it's likely that gzip could
still do some compression but that would be better done in the database and
in wire protocol formats rather than changing the format which is hashed at
the consensus layer.
> Pretty much all the opcodes in the first section are directly from chia
> lisp, while all the rest are to complete the "bitcoin" functionality.
> The last two are extensions that are more food for thought than a real
> proposal.
>
Are you thinking of this as a completely alternative script format or an
extension to bitcoin script? They're radically different approaches and
it's hard to see how they mix. Everything in lisp is completely sandboxed,
and that functionality is important to a lot of things, and it's really
normal to be given a reveal of a scriptpubkey and be able to rely on your
parsing of it.
> There's two ways to think about upgradability here; if someday we want
> to add new opcodes to the language -- perhaps something to validate zero
> knowledge proofs or calculate sha3 or use a different ECC curve, or some
> way to support cross-input signature aggregation, or perhaps it's just
> that some snippets are very widely used and we'd like to code them in
> C++ directly so they validate quicker and don't use up as much block
> weight. One approach is to just define a new version of the language
> via the tapleaf version, defining new opcodes however we like.
>
A nice side benefit of sticking with the UTXO model is that the soft fork
hook can be that all unknown opcodes make the entire thing automatically
pass.
>
> The other is to use the "softfork" opcode -- chia defines it as:
>
> (softfork cost code)
>
> though I think it would probably be better if it were
>
> (softfork cost version code)
>
Since softfork has to date never been used that second parameter is
technically completely ignored and could be anything at all. Most likely a
convention including some kind of version information will be created the
first time it's used. Also Chia shoves total cost into blocks at the
consensus layer out of an abundance of caution although that isn't
technically necessary.
[10] [9] The CREATE/ASSERT bundling stuff is interesting; and could be
> used to achieve functionality like the "transaction sponsorship"
> stuff. It doesn't magically solve the issues with maintaining the
> mempool and using that to speed up block acceptance, though, and
> the chia chain has apparently suffered from mempool-flooding attacks
> recently [11] so I don't think they've solved the broader problem,
>
Chia's approach to transaction fees is essentially identical to Bitcoin's
although a lot fewer things in the ecosystem support fees due to a lack of
having needed it yet. I don't think mempool issues have much to do with
choice of scriptpubkey language. which is mostly about adding in covenants
and capabilities.
That said, Ethereum does have trivial aggregation of unrelated
transactions, and the expense of almost everything else. There are a bunch
of ways automatic aggregation functionality could be added to coin set
mempools by giving them some understanding of the semantics of some
transactions, but that hasn't been implemented yet.
I previously posted some thoughts about this here:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-December/019722.html
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220306/4ed797aa/attachment-0001.html>

2023-06-07 17:59:52 UTC

- reply

📅 Original date posted:2017-04-10
📝 Original message:On Sun, Apr 9, 2017 at 11:44 AM, Erik Aronesty via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> Clearly a level-playing field is critical to keeping centralization from
> being a "defining feature" of Bitcoin over the long term. I've heard the
> term "level playing field" bandied about quite a bit. And it seems to me
> that the risk of state actor control and botnet attacks is less than
> state-actor manipulation of specialized manufacturing of "SHA-256 forever"
> hardware. Indeed, the reliance on a fairly simple hash seems less and
> less likely a "feature" and more of a baggage.
>
>
Whatever your hashing function the bottleneck for mining will be power.
Equihash and Cuckoo are serious attempts at making custom hardware have no
benefit over commodity hardware, but that's more about getting rid of
custom hardware manufacturers than it is about mining decentralization,
although arguably if successful it might let botnets back in, which would
improve decentralization. While those have been surprisingly successful at
resisting hardware so far, they might eventually fall as well, and if they
do they'll have even worse properties of centralizing around a mining
hardware manufacturer than sha256 does.
It would be much safer to go the other way, to a PoW function whose best
hardware implementation is particularly straightforward and well
understood. In that case it would be best to go with sha3. Sha3 also has
the benefit of using the sponge construction, which makes it particularly
resistant to asciboost-type attacks. It was picked out specifically because
its design from a security standpoint was particularly
confidence-inspiring, and in this case it actually makes a difference.
Arguably you could also go with blake2b, whose 1024 bit block size
completely obviates the asicboost concern entirely by cramming everything
into a single block. That also might have an even simpler design in
hardware than sha3, but a real expert would need to opine on that one.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170410/3ff44513/attachment.html>

2023-06-07 17:59:52 UTC

- reply

📅 Original date posted:2017-04-10
📝 Original message:On Sun, Apr 9, 2017 at 11:44 AM, Erik Aronesty via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> Perhaps regular, high-consensus POW changes might even be *necessary* as a
> part of good maintenance of cryptocurrency in general. Killing the
> existing POW, and using an as-yet undefined, but deployment-bit ready POW
> field to flip-flop between the current and the "next one" every 8 years or
> or so, with a ramp down beginning in the 7th year.... A stub function that
> is guaranteed to fail unless a new consensus POW is selected within 7
> years.
>
That would force hard forks, cause huge governance problems on selecting
the new PoW algorithm, and probably cause even worse mining chip
manufacturer centralization because it would force miners to buy new chips
instead of sticking with the ones they've already got. They'll likely have
to keep buying new ones anyway as technology improves but it doesn't help
to force that process to go even faster.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170410/021b108b/attachment.html>

2023-06-07 17:59:39 UTC

- reply

📅 Original date posted:2017-04-07
📝 Original message:Expanding on this question a bit, it's optimized for parallel access, but
hard drive access isn't parallel and memory accesses are very fast, so
shouldn't the target of optimization be about cramming as much as possible
in memory and minimizing disk accesses?
On Fri, Apr 7, 2017 at 11:18 AM, Gregory Maxwell via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> On Thu, Apr 6, 2017 at 10:12 PM, Tomas via bitcoin-dev
> <bitcoin-dev at lists.linuxfoundation.org> wrote:
> >As this
> > solution, reversing the costs of outputs and inputs, seems to have
> > excellent performance characteristics (as shown in the test results),
> > updates to the protocol addressing the UTXO growth, might not be worth
> > considering *protocol improvements*
>
> I'm still lost on this-- AFAICT your proposals long term resource
> requirements are directly proportional to the amount of unspent output
> data, which grows over time at some fraction of the total transaction
> volume (plus the rate of spending which is more or less a constant).
>
> Can you help out my understanding here?
> _______________________________________________
> 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/20170407/6a7fb499/attachment-0001.html>

2023-06-07 17:59:17 UTC

- reply

📅 Original date posted:2017-04-05
📝 Original message:On Wed, Apr 5, 2017 at 7:31 PM, Peter Todd via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> While I'm in favour of blocking covert usage of ASICBOOST, there's every
> reason
> to block non-covert usage of it as well. In a low margin business like
> mining,
> the advatange it gives is enormous - quite possibly 10x your profit margin
> -
> and given that barrier free access to being able to purchase ASICs is
> already
> an archilles heal for Bitcoin there is every reason to eliminate this legal
> vulnerability. Additionally, it's a technical vulnerability as well: we
> want
> getting into the ASIC manufacturing and design business to have as low
> barriers
> to entry as is feasible, and the ASICBOOST exploit significantly increases
> the
> minimum capital requirements to do so.
>
Asicboost also has the problem that it isn't treating the hashing as a
black box, and thus has impacts on what gets mined. In particular it
creates an incentive to make blocks smaller. That's a very unwanted effect,
and anything like it should be engineered out on principle.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170405/bd9a7d92/attachment.html>

2023-06-07 17:58:05 UTC

- reply

📅 Original date posted:2017-03-29
📝 Original message:On Tue, Mar 28, 2017 at 9:59 AM, Wang Chun via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> The basic idea is, as many of us agree, hard fork is risky and should
> be well prepared. We need a long time to deploy it.
>
Much as it may be appealing to repeal the block size limit now with a grace
period until a replacement is needed in a repeal and replace strategy, it's
dubious to assume that an idea can be agreed upon later when it can't be
agreed upon now. Trying to put a time limit on it runs into the possibility
that you'll find that whatever reasons there were for not having general
agreement on a new setup before still apply, and running into the
embarrassing situation of winding up sticking with the status quo after
much sturm and drang.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170328/e04b8d19/attachment.html>

2023-06-07 17:56:36 UTC

- reply

📅 Original date posted:2017-02-28
📝 Original message:On Tue, Feb 28, 2017 at 8:43 AM, G. Andrew Stone <g.andrew.stone at gmail.com>
wrote:
>
> But since transactions' prevouts are not specified by [block height, tx
> index, output index] or by TXO index, I don't understand how an insertion
> ordered TXO tree can result in efficient lookups. Can you help me
> understand this?
>
You have to have a lookup table going from prevouts to txo index. Lookups
on that are relatively fast because looking up things in a hashtable is a
single cache miss, while looking up things in a tree is logarithmic cache
misses.
The purported benefit of using txout is that because recent things are
spent much more than old things, there's a lot of clustering of updates. If
you update two things near each other they share the top branches of
updates in the tree, resulting in less hashing and cache misses. But since
everything is log scale I suspect such benefits are small. My guess is
transaction ordering has much larger potential from compression because you
cram information about lots of things into a single leaf node because they
have very small diffs from each other. That said, those benefits are also
smaller than and accretive to the simple implementation tricks I already
implemented which cause things near each other in the tree to be near each
other in memory.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170228/aa032a07/attachment-0001.html>

2023-06-07 17:56:36 UTC

- reply

📅 Original date posted:2017-02-25
📝 Original message:On Fri, Feb 24, 2017 at 8:12 PM, Peter Todd <pete at petertodd.org> wrote:
>
> So to be clear, what you're proposing there is to use the insertion order
> as
> the index - once you go that far you've almost entirely re-invented my
> proposal!
>
I'm not 'proposing' this, I'm saying it could be done simply but I'm
skeptical of the utility. Probably the most compelling argument for it is
that the insertion indexed values are much smaller so they can be compacted
down a lot resulting in using less memory and more locality and fewer
hashes, but your implementation doesn't take advantage of that.
> Your merkle-set implementation is 1500 lines of densely written Python
The reference implementation which is included in those 1500 lines is less
than 300 lines and fairly straightforward. The non-reference implementation
always behaves semantically identically to the reference implementation, it
just does so faster and using less memory.
> with
> almost no comments,
The comments at the top explain both the proof format and the in-memory
data structures very precisely. The whole codebase was reviewed by a
coworker of mine and comments were added explaining the subtleties which
tripped him up.
> and less than a 100 lines of (also uncommented) tests.
Those tests get 98% code coverage and extensively hit not only the lines of
code but the semantic edge cases as well. The lines which aren't hit are
convenience functions and error conditions of the parsing code for when
it's passed bad data.
> By
> comparison, my Python MMR implementation is 300 lines of very readable
> Python
> with lots of comments, a 200 line explanation at the top, and 200 lines of
> (commented) tests. Yet no-one is taking the (still considerable) effort to
> understand and comment on my implementation. :)
>
Given that maaku's Merkle prefix trees were shelved because of performance
problems despite being written in C and operating in basically the same way
as your code and my reference code, it's clear that non-optimized Python
won't be touching the bitcoin codebase any time soon.
>
> Fact is, what you've written is really daunting to review, and given it's
> not
> in the final language anyway, it's unclear what basis to review it on
> anyway.
It should reviewed based on semantic correctness and performance.
Performance can only be accurately and convincingly determined by porting
to C and optimizing it, which mostly involves experimenting with different
values for the two passed in magic numbers.
> I
> suspect you'd get more feedback if the codebase was better commented, in a
> production language, and you have actual real-world benchmarks and
> performance
> figures.
>
Porting to C should be straightforward. Several people have already
expressed interest in doing so, and it's written in intentionally C-ish
Python, resulting in some rather odd idioms which is a bit part of why you
think it looks 'dense'. A lot of that weird offset math should be much more
readable in C because it's all structs and x.y notation can be used instead
of adding offsets.
> In particular, while at the top of merkle_set.py you have a list of
> advantages,
> and a bunch of TODO's, you don't explain *why* the code has any of these
> advantages. To figure that out, I'd have to read and understand 1500 lines
> of
> densely written Python. Without a human-readable pitch, not many people are
> going to do that, myself included.
>
It's all about cache coherence. When doing operations it pulls in a bunch
of things which are near each other in memory instead of jumping all over
the place. The improvements it gets should be much greater than the ones
gained from insertion ordering, although the two could be accretive.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170224/f104455e/attachment.html>

2023-06-07 17:56:34 UTC

- reply

📅 Original date posted:2017-02-24
📝 Original message:So your idea is to cluster entries by entry time because newer things are
more likely to leave and updating multiple things near each other is
cheaper?
That can be done with my tool. Instead of using hashes for the values being
stored, you use position entries. The first entry gets a value of all
zeros, the next one a one followed by all zeros, then the next two
correspond to the first two with the second bit flipped to one, then the
next four the first four with the third bit flipped to one, etc. It
probably performs a little bit better to do it two bits at a time instead
of one so that the entries are 00, 01, 10, 11, 0001, 0010, 0011, 0101,
0110, 0111, 1001, etc. If you were to really use this you'd probably want
to to add some optimizations to use the fact that the terminals fit in 64
bits instead of 256, but it mostly works unchanged, and gets whatever
benefits there are to this clustering plus the high performance
implementation tricks I've built which I keep complaining that nobody's
giving feedback on.
I'm not sold on this being a win: The empirical access patterns are
unknown, it requires an extra cache miss per lookup to find the entry
number, it may be that everything is optimized well enough without it for
there to be no meaningful gains, and it's a bunch of extra complexity. What
should be done is that a plain vanilla UTXO set solution is optimized as
well as it can be first, and then the insertion ordering trick is tried as
an optimization to see if it's an improvement. Without that baseline
there's no meaningful basis for comparison, and I'm quite confident that a
naive implementation which just allocates individual nodes will
underperform the thing I've come up with, even without adding optimizations
related to fitting in 64 bits.
On Thu, Feb 23, 2017 at 8:36 PM, Peter Todd <pete at petertodd.org> wrote:
> On Thu, Feb 23, 2017 at 07:32:43PM -0800, Bram Cohen wrote:
> > On Thu, Feb 23, 2017 at 7:15 PM, Peter Todd <pete at petertodd.org> wrote:
> >
> > >
> > > Glad we're on the same page with regard to what's possible in TXO
> > > commitments.
> > >
> > > Secondly, am I correct in saying your UTXO commitments scheme requires
> > > random
> > > access? While you describe it as a "merkle set", obviously to be
> merkelized
> > > it'll have to have an ordering of some kind. What do you propose that
> > > ordering
> > > to be?
> > >
> >
> > The ordering is by the bits in the hash. Technically it's a Patricia
> Trie.
> > I'm using 'merkle tree' to refer to basically anything with a hash root.
>
> The hash of what? The values in the set?
>
> > > Maybe more specifically, what exact values do you propose to be in the
> set?
> > >
> > >
> > That is unspecified in the implementation, it just takes a 256 bit value
> > which is presumably a hash of something. The intention is to nail down a
> > simple format and demonstrate good performance and leave those semantics
> to
> > a higher layer. The simplest thing would be to hash together the txid and
> > output number.
>
> Ok, so let's assume the values in the set are the unspent outpoints.
>
> Since we're ordering by the hash of the values in the set, outpoints will
> be
> distributed uniformly in the set, and thus the access pattern of data in
> the
> set is uniform.
>
> Now let's fast-forward 10 years. For the sake of argument, assume that for
> every 1 UTXO in the set that corresponds to funds in someone's wallet that
> are
> likely to be spent, there are 2^12 = 4096 UTXO's that have been permanently
> lost (and/or created in spam attacks) and thus will never be spent.
>
> Since lost UTXO's are *also* uniformly distributed, if I'm processing a new
> block that spends 2^12 = 4096 UTXO's, on average for each UTXO spent, I'll
> have to update log2(4096) = 12 more digests than I would have had those
> "dead"
> UTXO's not existed.
>
> Concretely, imagine our UTXO set had just 8 values in it, and we were
> updating
> two of them:
>
> #
> / \
> / \
> / \
> / \
> / \
> # #
> / \ / \
> / \ / \
> # . . #
> / \ / \ / \ / \
> . X . . . . X .
>
> To mark two coins as spent, we've had to update 5 inner nodes.
>
>
> Now let's look at what happens in an insertion-ordered TXO commitment
> scheme.
> For sake of argument, let's assume the best possible case, where every UTXO
> spent in that same block was recently created. Since the UTXO's are
> recently
> created, chances are almost every single one of those "dead" UTXO's will
> have
> been created in the past. Thus, since this is an insertion-ordered data
> structure, those UTXO's exist in an older part of the data structure that
> our
> new block doesn't need to modify at all.
>
> Concretely, again let's imagine a TXO commitment with 8 values in it, and
> two
> of them being spent:
>
> #
> / \
> / \
> / \
> / \
> / \
> . #
> / \ / \
> / \ / \
> . . . #
> / \ / \ / \ / \
> . . . . . . X X
>
> To mark two coins as spent, we've only had to update 3 inner nodes; while
> our
> tree is higher with those lost coins, those extra inner nodes are amortised
> across all the coins we have to update.
>
>
> The situation gets even better when we look at the *new* UTXO's that our
> block
> creates. Suppose our UTXO set has size n. To mark a single coin as spent,
> we
> have to update log2(n) inner nodes. We do get to amortise this a bit at
> the top
> levels in the tree, but even if we assume the amortisation is totally free,
> we're updating at least log2(n) - log2(m) inner nodes "under" the amortised
> nodes at the top of the tree for *each* new node.
>
> Meanwhile with an insertion-ordered TXO commitment, each new UTXO added to
> the
> data set goes in the same place - the end. So almost none of the existing
> data
> needs to be touched to add the new UTXOs. Equally, the hashing required
> for the
> new UTXO's can be done in an incremental fashion that's very L1/L2 cache
> friendly.
>
>
> tl;dr: Precisely because access patterns in TXO commitments are *not*
> uniform,
> I think we'll find that from a L1/L2/etc cache perspective alone, TXO
> commitments will result in better performance than UTXO commitments.
>
>
> Now it is true that Bitcoin's current design means we'll need a map of
> confirmed outpoints to TXO insertion order indexes. But it's not
> particularly
> hard to add that "metadata" to transactions on the P2P layer in the same
> way
> that segwit added witnesses to transactions without modifying how txids
> were
> calculated; if you only connect to peers who provide you with TXO index
> information in blocks and transactions, you don't need to keep that map
> yourself.
>
> Finally, note how this makes transactions *smaller* in many circumstances:
> it's
> just a 8-byte max index rather than a 40 byte outpoint.
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170224/63ab2731/attachment-0001.html>

2023-06-07 17:56:33 UTC

- reply

📅 Original date posted:2017-02-24
📝 Original message:On Thu, Feb 23, 2017 at 6:58 PM, Peter Todd <pete at petertodd.org> wrote:
>
> So to be clear, do you agree or disagree with me that you *can* extract a
> compact proof from a MMR that a given output is unspent?
>
After wading through your logic on how updates are done, I agree that that
can be done, but apples to apples compact proofs can also be done in a utxo
commitment, and proofs of the validity of updates can be done in a utxo
commitment, so there isn't any performance advantage to all that extra
complexity.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170223/a93584fd/attachment.html>

2023-06-07 17:56:33 UTC

- reply

📅 Original date posted:2017-02-24
📝 Original message:On Thu, Feb 23, 2017 at 7:15 PM, Peter Todd <pete at petertodd.org> wrote:
>
> Glad we're on the same page with regard to what's possible in TXO
> commitments.
>
> Secondly, am I correct in saying your UTXO commitments scheme requires
> random
> access? While you describe it as a "merkle set", obviously to be merkelized
> it'll have to have an ordering of some kind. What do you propose that
> ordering
> to be?
>
The ordering is by the bits in the hash. Technically it's a Patricia Trie.
I'm using 'merkle tree' to refer to basically anything with a hash root.
> Maybe more specifically, what exact values do you propose to be in the set?
>
>
That is unspecified in the implementation, it just takes a 256 bit value
which is presumably a hash of something. The intention is to nail down a
simple format and demonstrate good performance and leave those semantics to
a higher layer. The simplest thing would be to hash together the txid and
output number.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170223/ebb642c9/attachment.html>

2023-06-07 17:56:32 UTC

- reply

📅 Original date posted:2017-02-24
📝 Original message:On Thu, Feb 23, 2017 at 5:09 PM, Peter Todd <pete at petertodd.org> wrote:
> I think you've misunderstood what TXO commitments are. From my article:
>
> "A merkle tree committing to the state of all transaction outputs, both
> spent
> and unspent, can provide a method of compactly proving the current state
> of an
> output."
> -https://petertodd.org/2016/delayed-txo-commitments#txo-commitments:
>
The proposal on that page is of a tree which does require random access
updates, it just positions entries in the order they happened to be added
instead of sorting by their hash. Once you start updating it to indicate
spent status all the exact same issues of TXO size and cache coherence on
updates show up again, but now you're using a more complex bespoke data
structure instead of a basic fundamental one.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170223/e1b6fe16/attachment.html>

2023-06-07 17:56:32 UTC

- reply

📅 Original date posted:2017-02-23
📝 Original message:On Thu, Feb 23, 2017 at 3:51 PM, Peter Todd <pete at petertodd.org> wrote:
> On Thu, Feb 23, 2017 at 03:13:43PM -0800, Bram Cohen wrote:
> >
> > I can't speak to MMRs (they look a bit redundant with the actual
> blockchain
> > history to my eye) but circling back to utxo commitments, the benefits
> are
>
> In what way do you see MMRs as redundant?
>
You can readily prove something is in the TXO or STXO set using the actual
blockchain, and the proofs will be nice and compact because even light
nodes are expected to already have all the historical headers.
What you can't do with MMRs or the blockchain is make a compact proof that
something is still in the utxo set, which is the whole point of utxo
commitments.
It's totally reasonable for full nodes to independently update and
recalculate the utxo set as part of their validation process. The same
can't be done for a balanced version of the txo set because it's too big.
Relying on proofs as a crutch for using the full txo set would badly
exacerbate the already extant problem of miners doing spv mining, and
increase the bandwidth a full validating node had to use by a multiple.
This whole conversation is badly sidetracked. If people have comments on my
merkle set I'd like to engage further with them, but mmrs need to be argued
independently on their own merits before being used as a counterpoint to
utxo commitments.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170223/c2fc2e57/attachment-0001.html>

2023-06-07 17:56:31 UTC

- reply

📅 Original date posted:2017-02-23
📝 Original message:On Thu, Feb 23, 2017 at 9:53 AM, Chris Priest via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> What problem does this try to solve, and what does it have to do with
> bitcoin?
>
I can't speak to MMRs (they look a bit redundant with the actual blockchain
history to my eye) but circling back to utxo commitments, the benefits are
that it enables actual proofs of non-fraud: You can prove the validity of a
block based on just the previous block (and maybe some previous headers
because of mining rewards) and can prove to a light node that a utxo hasn't
been spent yet.
A major factor in the way of getting utxo commitments in blocks is
performance. The txo set is of course vastly larger and more unwieldy. If
you make the utxo commitments trail by a small fixed number of blocks
(between 2 and 5) their latency problems shouldn't be a big deal as long as
the overall performance is good enough. My thesis is that with appropriate
format and implementation tricks it's possible to get performance good
enough to no longer be a gating factor to deployment.
Disappointingly there hasn't been any feedback about my implementation,
just discussion about merkle sets generally.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170223/5dbd72da/attachment.html>

2023-06-07 17:56:30 UTC

- reply

📅 Original date posted:2017-02-23
📝 Original message:On Wed, Feb 22, 2017 at 5:15 PM, Peter Todd via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> With that, notice how proving the soundness of the proofs becomes trivial:
> if
> validation is deterministic, it is obviously impossible to construct two
> different proofs that prove contradictory statements, because a proof is
> simply
> part of the data structure itself. Contradiction would imply that the two
> proofs are different, but that's easily rejected by simply checking the
> hash of
> the data.
>
My code works this way. Proofs are serialization of a subset of the tree,
and to validate a proof you ask a single function whether a particular
value is included in that tree subset, and it answers yes or no, so
obviously it's impossible for a single value to both validate and not
validate. The proof code was quite terrifying before I made this change
(which I did on your suggestion), and it's much cleaner and simpler now. It
also in principle supports compact proofs of multiple inclusions and
exclusions in the same serialization of a subset of the tree because the
upper branches won't have to be repeated. I haven't written code for
generating those, but the validation code will happily accept them.
I'm not sure what you mean by MMRs though. Are you talking about MMRs where
each mountain is a set of diffs to the old things and are periodically
consolidated? Or do later mountains refer to internals of earlier ones? Or
do they have 'maybe' values which mean that the earlier mountain should be
referred to? Are these patricia tries or something flatter and more fixed
depth?
My code doesn't keep track of tree size, by the way. It would be trivial to
add that functionality to the library, and including it in the hashing
creates complexity and doesn't seem to have any benefit over sending that
data in a side channel.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170222/4a48d1ae/attachment-0001.html>

2023-06-07 17:54:52 UTC

- reply

📅 Original date posted:2016-12-10
📝 Original message:On Mon, Dec 5, 2016 at 7:27 AM, t. khan via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> Put another way: let’s stop thinking about what the max block size should
> be and start thinking about how full we want the average block to be
> regardless of size. Over the last year, we’ve had averages of 75% or
> higher, so aiming for 75% full seems reasonable, hence naming this concept
> ‘Block75’.
>
That's effectively making the blocksize limit completely uncapped and only
preventing spikes, and even in the case of spikes it doesn't differentiate
between 'real' traffic and low value spam attacks. It suffers from the same
fundamental problems as bitcoin unlimited: There are in the end no
transaction fees, and inevitably some miners will want to impose some cap
on block size for practical purposes, resulting in a fork.
Difficulty adjustment works because there's a clear goal of having a
certain rate of making new blocks. Without a target to attempt automatic
adjustment makes no sense.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20161210/01c100f5/attachment.html>

2023-06-07 17:54:50 UTC

- reply

📅 Original date posted:2016-12-11
📝 Original message:On Sun, Dec 11, 2016 at 1:40 PM, t. khan via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> Block75 is not exponential scaling. It's true the max theoretical increase
> in the first year would be 7x, but the next year would be a max of 2x, and
> the next could only increase by 50% and so on.
>
With those limits there's very little reason to not simply have a fixed
schedule. Blocks are likely to all be full in the future anyway, with a
real fee market, and the idea that miners will be held back on block sizes
for worry about propagation delay is a myth, and even if it were true it
would favor collective pooling a lot, which would be a very bad thing.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20161211/ea9bb129/attachment.html>

2023-06-07 17:54:48 UTC

- reply

📅 Original date posted:2016-12-10
📝 Original message:Miners individually have an incentive to include every transaction they can
when they mine a block, but they also sometimes have an incentive to
collectively cooperate to reduce throughput to make more money as a group.
Under schemes where limits can be adjusted both possibilities must be taken
into account.
On Sat, Dec 10, 2016 at 4:40 PM, James Hilliard via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Miners in general are naturally incentivized to always mine max size
> blocks to maximize transaction fees simply because there is very
> little marginal cost to including extra transactions(there will always
> be a transaction backlog of some sort available to mine since demand
> for block space is effectively unbounded as fees approach 0 and they
> can even mine their own transactions without any fees). This proposal
> would almost certainly cause runaway block size growth and encourage
> much more miner centralization.
>
> On Sat, Dec 10, 2016 at 6:26 PM, t. khan via bitcoin-dev
> <bitcoin-dev at lists.linuxfoundation.org> wrote:
> > Miners 'gaming' the Block75 system -
> > There is no financial incentive for miners to attempt to game the Block75
> > system. Even if it were attempted and assuming the goal was to create
> bigger
> > blocks, the maximum possible increase would be 25% over the previous
> block
> > size. And, that size would only last for two weeks before readjusting
> down.
> > It would cost them more in transaction fees to stuff the network than
> they
> > could ever make up. To game the system, they'd have to game it forever
> with
> > no possibility of profit.
> >
> > Blocks would get too big -
> > Eventually, blocks would get too big, but only if bandwidth stopped
> > increasing and the cost of disk space stopped decreasing. Otherwise, the
> > incremental adjustments made by Block75 (especially in combination with
> > SegWit) wouldn't break anyone's connection or result in significantly
> more
> > orphaned blocks.
> >
> > The frequent and small adjustments made by Block75 have the added
> benefit of
> > being more easily adapted to, both psychologically and technologically,
> with
> > regards to miners/node operators.
> >
> > -t.k
> >
> > On Sat, Dec 10, 2016 at 5:44 AM, s7r via bitcoin-dev
> > <bitcoin-dev at lists.linuxfoundation.org> wrote:
> >>
> >> t. khan via bitcoin-dev wrote:
> >> > BIP Proposal - Managing Bitcoin’s block size the same way we do
> >> > difficulty (aka Block75)
> >> >
> >> > The every two-week adjustment of difficulty has proven to be a
> >> > reasonably effective and predictable way of managing how quickly
> blocks
> >> > are mined. Bitcoin needs a reasonably effective and predictable way of
> >> > managing the maximum block size.
> >> >
> >> > It’s clear at this point that human beings should not be involved in
> the
> >> > determination of max block size, just as they’re not involved in
> >> > deciding the difficulty.
> >> >
> >> > Instead of setting an arbitrary max block size (1MB, 2MB, 8MB, etc.)
> or
> >> > passing the decision to miners/pool operators, the max block size
> should
> >> > be adjusted every two weeks (2016 blocks) using a system similar to
> how
> >> > difficulty is calculated.
> >> >
> >> > Put another way: let’s stop thinking about what the max block size
> >> > should be and start thinking about how full we want the average block
> to
> >> > be regardless of size. Over the last year, we’ve had averages of 75%
> or
> >> > higher, so aiming for 75% full seems reasonable, hence naming this
> >> > concept ‘Block75’.
> >> >
> >> > The target capacity over 2016 blocks would be 75%. If the last 2016
> >> > blocks are more than 75% full, add the difference to the max block
> size.
> >> > Like this:
> >> >
> >> > MAX_BLOCK_BASE_SIZE = 1000000
> >> > TARGET_CAPACITY = 750000
> >> > AVERAGE_OVER_CAP = average block size of last 2016 blocks minus
> >> > TARGET_CAPACITY
> >> >
> >> > To check if a block is valid, ≤ (MAX_BLOCK_BASE_SIZE +
> AVERAGE_OVER_CAP)
> >> >
> >> > For example, if the last 2016 blocks are 85% full (average block is
> 850
> >> > KB), add 10% to the max block size. The new max block size would be
> >> > 1,100 KB until the next 2016 blocks are mined, then reset and
> >> > recalculate. The 1,000,000 byte limit that exists currently would
> >> > remain, but would effectively be the minimum max block size.
> >> >
> >> > Another two weeks goes by, the last 2016 blocks are again 85% full,
> but
> >> > now that means they average 935 KB out of the 1,100 KB max block size.
> >> > This is 93.5% of the 1,000,000 byte limit, so 18.5% would be added to
> >> > that to make the new max block size of 1,185 KB.
> >> >
> >> > Another two weeks passes. This time, the average block is 1,050 KB.
> The
> >> > new max block size is calculated to 1,300 KB (as blocks were 105%
> full,
> >> > minus the 75% capacity target, so 30% added to max block size).
> >> >
> >> > Repeat every 2016 blocks, forever.
> >> >
> >> > If Block75 had been applied at the difficulty adjustment on November
> >> > 18th, the max block size would have been 1,080KB, as the average block
> >> > during that period was 83% full, so 8% is added to the 1,000KB limit.
> >> > The current size, after the December 2nd adjustment would be 1,150K.
> >> >
> >> > Block75 would allow the max block size to grow (or shrink) in response
> >> > to transaction volume, and does so predictably, reasonably quickly,
> and
> >> > in a method that prevents wild swings in block size or transaction
> fees.
> >> > It attempts to keep blocks at 75% total capacity over each two week
> >> > period, the same way difficulty tries to keep blocks mined every ten
> >> > minutes. It also keeps blocks as small as possible.
> >> >
> >> > Thoughts?
> >> >
> >> > -t.k.
> >> >
> >>
> >> I like the idea. It is good wrt growing the max. block size
> >> automatically without human action, but the main problem (or question)
> >> is not how to grow this number, it is what number can the network
> >> handle, considering both miners and users. While disk space requirements
> >> might not be a big problem, block propagation time is. The time required
> >> for a block to propagate in the network (or at least to all the miners)
> >> is directly dependent of its size. If blocks take too much time to
> >> propagate in the network, the orphan rate will increase in unpredictable
> >> ways. For example if the internet speed in China is worse than in
> >> Europe, and miners in China have more than 50% of the hashing power,
> >> blocks mined by European miners might get orphaned.
> >>
> >> The system as described can also be gamed, by filling the network with
> >> transactions. Miners have the monetary interest to include as many
> >> transactions as possible in a block in order to collect the fees.
> >> Regardless how you think about it, there has to be a maximum block size
> >> that the network will allow as a consensus rule. Increasing it
> >> dynamically based on transaction volume will reach a point where the
> >> number got big enough that it broke things. Bitcoin, because its
> >> fundamental design, can scale by using offchain solutions.
> >>
> >>
> >> _______________________________________________
> >> 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
> >
> _______________________________________________
> 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/20161210/d2b72e8b/attachment-0001.html>