Bram Cohen [ARCHIVE]

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

Public Key

npub1ldcq03p2qe58u0xnlwa35wchjuhz49y6ueu5ghmtjetez9xstnvsmt8ur6

Profile Code

nprofile1qqs0kuq8cs4qv6r78nflhwc68vtewt32jjdwv72yta4ev4u3zng9ekga6u45m

Author Public Key

npub1ldcq03p2qe58u0xnlwa35wchjuhz49y6ueu5ghmtjetez9xstnvsmt8ur6

Show more details

Last Notes

2023-06-09 12:50:35

- reply

📅 Original date posted:2018-05-07
📝 Original message:
A technical point about SIGHASH_NOINPUT: It seems like a more general and
technically simpler to implement idea would be to have a boolean specifying
whether the inputs listed must be all of them (the way it works normally)
or a subset of everything. It feels like a similar boolean should be made
for outputs as well. Or maybe a single boolean should apply to both. In any
case, one could always use SIGHASH_SUBSET and not specify any inputs and
that would have the same effect as SIGHASH_NOINPUT.
On Mon, May 7, 2018 at 12:40 PM, Christian Decker via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Given the general enthusiasm, and lack of major criticism, for the
> `SIGHASH_NOINPUT` proposal, I'd like to formally ask the BBEs (benevolent
> BIP editors) to be assigned a BIP number. I have hacked together a
> simple implementation of the hashing implementation in Bitcoin Core [1]
> though I think it's unlikely to sail through review, and given the lack
> of ground-work on witness V1 scripts, I can't really test it now, and
> only the second commit is part of the implementation itself.
>
> One issue that was raised off list was that some fork coins have used
> sighash 0x40 as FORKID. This does not conflict with this proposal since
> the proposal only applies to segwit transactions, which the fork coins
> have explicitly disabled :-)
>
> I'm looking forward to discussing how to we can move forward to
> implementing this proposal, and how we can combine multiple proposals
> into the next soft-fork.
>
> Cheers,
> Christian
>
> [1] https://github.com/cdecker/bitcoin/tree/noinput
> _______________________________________________
> 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/lightning-dev/attachments/20180507/6a2c236a/attachment.html>

2023-06-07 23:16:53

- 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:12:07

- reply

📅 Original date posted:2022-07-26
📝 Original message:On Mon, Jul 25, 2022 at 8:21 PM Antoine Riard <antoine.riard at gmail.com>
wrote:
> What would be the canonical definition and examples of capabilities in the
> Bitcoin context ?
>
Payments into vaults which can only be accepted by that vault and are
guaranteed to be subject to the vault's restrictions (the vault has a
capability)
Oracles whose validity can be verified on chain (so transactions can depend
on what they say. The oracle has a capability)
Colored coins whose validity can be verified on chain (the colored coins
have a capability)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220726/f3d49255/attachment-0001.html>

2023-06-07 23:12:06

- reply

📅 Original date posted:2022-07-24
📝 Original message:On Wed, Jul 20, 2022 at 2:46 PM Antoine Riard via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Indeed this range has grown wild. Without aiming to be exhaustive (I'm
> certainly missing some interesting proposals lost in the abyss of
> bitcointalk.org), we can mention the following use-cases: multi-party
> stateful contracts [11], congestion trees [12], payment pools [13], "eltoo"
> layered commitments [14], programmable vaults [15], multi-events contracts
> [16], blockchain-as-oracle bets [17], spacechains [18], trustless
> collateral lending [19], ...
>
The big question you missed is whether capabilities are in scope for a
covenants proposal. In particular, vaults work a lot better when payments
to them are immediately locked up in the vault rather than it having to do
a step to accept them first.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220724/37c519d3/attachment.html>

2023-06-07 23:11:43

- 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

- 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

- 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

- 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

- 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:09:56

- reply

📅 Original date posted:2022-05-21
📝 Original message:On Thu, May 19, 2022 at 9:17 AM alicexbt via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> MEV could be one the issues associated with general covenants. There are
> some resources on https://mev.day if anyone interested to read more about
> it.
>
One of the top things to do about MEV is to make all transactions in a
block simultaneous, so for example if you have a price oracle it can be
limited to only reporting one price per block so although it can be
manipulated to either report a high or low price it can't simultaneously do
both. In Bitcoin ordering is strictly enforced but there's a loophole that
things which happen in the same transaction do happen simultaneously, so
future extensions could be made to only sign things they care about and are
okay with transactions getting aggregated just by smushing them together.
That of course requires a new signature opcode, because current signatures
always sign the whole transaction.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220521/f44e89f7/attachment.html>

2023-06-07 23:06:55

- reply

📅 Original date posted:2022-04-11
📝 Original message:On Mon, Apr 11, 2022 at 11:21 AM Olaoluwa Osuntokun <laolu32 at gmail.com>
wrote:
> Hi Bram,
>
> > The witnesses for transactions need to be put into Bitcoin transactions
> > even though the Bitcoin layer doesn't understand them
>
> Is this related to Ruben's comment about invalid state transitions
> (published in the base chain) leading to burned assets?
>
Yes, or at least the concern that a valid transaction could have its
required witness data not posted to the chain and be effectively bricked.
> In the past, I've
> considered using the existing annex field in taproot transactions to
> implement partial reveal of certain data. However, today bitcoind treats
> annex usage as non-standard, so those transactions may be harder to relay.
> IMO this is a great place to add minimal extra data, as it doesn't bleed
> over into
> the scripting layer (via OP_DROP usages) and since Bitcoin-level signatures
> also include this field in the sighash, the sigs serve to further
> authenticate this data.
>
That leads to a bit of a philosophical question: Is the annex reserved for
possible future Bitcoin script soft forks, or is it free to use for
whatever with confidence there won't be a future collision? But that might
not matter, because if the purpose is to force the extra witness
information to be published it has to be in something signed in the
transaction, and barring a check sig from stack that probably means it has
to be shoved into the transaction somewhere.
> > Taro issuance is limited to a single event rather than potentially
> > multiple events over time subject to special per-asset rules.
>
> There's a provision in the protocol that lets a party issuing assets to
> specify a special public key which is then tweaked with the genesis
> outpoint, similar to the way the asset IDs are generated. If this key is
> specified, then future issuance, if signed off by that key, will serve to
> associate assets of discrete IDs under a single identifier. This feature
> allows assets issued in multiple tranches to be fungible with one another.
>
Ah I see. That's still a fairly bespoke set of functionality instead of
allowing an arbitrary script to be used for the issuance (but that again
runs into Bitcoin script being fairly limited in its functionality).
>
> > but I am puzzled by the announcement saying Taro assets are 'analogous
> > with' colored coins. Taro assets are straightforwardly and unambiguously
> > colored coins and that isn't something to be ashamed of.
>
> We've shied away from using the "colored coins' terminology as at this
> point
> in the game it's pretty dated: new developers that joined in the last 3
> years or so have likely never heard of that term. Explaining the term also
> requires one to define "coin coloring", and what that actually means, etc,
> etc. IMO it's simpler to just use the familiar and widely used asset
> issuance/minting terminology.
>
People mostly haven't heard of colored coins in a while because everything
has been based on ERC-20 style tokens, which are truly horrid. Coloring is
a meaningful technical term which means something good, although
unfortunately the term 'colored' is a bit loaded in different ways around
the world so it's best to keep it in the technical docs.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220411/6e575c43/attachment.html>

2023-06-07 23:06:54

- reply

📅 Original date posted:2022-04-10
📝 Original message:From: Olaoluwa Osuntokun <laolu32 at gmail.com>
>
> > Furthermore, the Taro script is not enforced by Bitcoin, meaning those
> who
> > control the Bitcoin script can always choose to ignore the Taro script
> and
> > destroy the Taro assets as a result.
>
> This is correct, as a result in most contexts, an incentive exists for the
> holder of an asset to observe the Taro validation rules as otherwise, their
> assets are burnt in the process from the PoV of asset verifiers. In the
> single
> party case things are pretty straight forward, but more care needs to be
> taken
> in cases where one attempts to express partial application and permits
> anyone
> to spend a UTXO in question.
>
> By strongly binding all assets to Bitcoin UTXOs, we resolve issues related
> to
> double spending or duplicate assets, but needs to mind the fact that assets
> can
> be burnt if a user doesn't supply a valid witness. There're likely ways to
> get
> around this by lessening the binding to Bitcoin UTXO's, but then the system
> would need to be able to collect, retain and order all the set of possible
> spends, essentially requiring a parallel network. The core of the system as
> it
> stands today is pretty simple (which was an explicit design goal to avoid
> getting forever distracted by the large design space), with a minimal
> implementation being relatively compact given all the Bitcoin
> context/design
> re-use.
>
The TARO set of tradeoffs is fairly coherent but is subject to certain
limitations (modulo my understanding of it being off):
The witnesses for transactions need to be put into Bitcoin transactions
even though the Bitcoin layer doesn't understand them
There needs to be a constraint on Taro transactions which is understood by
the Bitcoin layer (which often/usually happens naturally because there's a
user signature but sometimes doesn't. It's a limitation)
Multiple Taro coins can't consolidate their value into a single output
because they only support a single linear history
Taro issuance is limited to a single event rather than potentially multiple
events over time subject to special per-asset rules.
This seems like a fairly logical approach (although my understanding of the
limitations/tradeoffs could be wrong, especially with regards to
consolidation). There's nothing wrong with a system having well documented
limitations, but I am puzzled by the announcement saying Taro assets are
'analogous with' colored coins. Taro assets are straightforwardly and
unambiguously colored coins and that isn't something to be ashamed of.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220410/df14d323/attachment.html>

2023-06-07 23:05:23

- 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:23

- reply

📅 Original date posted:2022-03-09
📝 Original message:On Mon, Mar 7, 2022 at 2:56 PM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
>
> > 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.
>
> Does this mean it basically gets recursive covenants?
> Or is a condition in this list of conditions written a more restrictive
> language which itself cannot return a list of conditions?
>
The conditions language is extremely restrictive but does allow for
recursive covenants through the route of specifying output
scriptpubkeys/puzzles, which Bitcoin already sort of in principle supports
except that Bitcoin script's ability to generate and parse transactions
isn't quite up to the task.
> > 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.
>
> How different is this from "jets" as proposed in Simplicity?
>
My vague impression is that Simplicity jets are meant to be for things like
Sha3 rather than shared library code. It might be that the way to use it
would be to implement CLVM opcodes be a bunch of Simplicity jets. Whether
that would be making the CLVM irrelevant or going through a pointless bit
of theatre to be based on Simplicity under the hood I don't know.
The compression hook is that in each block instead of there being a list of
puzzle reveals and solutions there's a generator written in CLVM which
outputs that list, and it can be passed the generators of old blocks from
which it can pull out code snippits.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220308/a6fdcea8/attachment-0001.html>

2023-06-07 23:05:22

- 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

- 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

- 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

- 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

- 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

- 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 23:03:08

- reply

📅 Original date posted:2022-02-01
📝 Original message:On Mon, Jan 31, 2022 at 4:08 PM Eric Voskuil <eric at voskuil.org> wrote:
>
>
> On Jan 31, 2022, at 15:15, Bram Cohen via bitcoin-dev <
> bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> Is it still verboten to acknowledge that RBF is normal behavior and
> disallowing it is the feature, and that feature is mostly there to appease
> some people's delusions that zeroconf is a thing? It seems a bit overdue to
> disrespect the RBF flag in the direction of always assuming it's on.
>
> What flag?
>
The opt-in RBF flag in transactions.
> There are two different common regimes which result in different
> incentivized behavior. One of them is that there's more than a block's
> backlog in the mempool in which case between two conflicting transactions
> the one with the higher fee rate should win. In the other case where there
> isn't a whole block's worth of transactions the one with higher total value
> should win.
>
> These are not distinct scenarios. The rational choice is the highest fee
> block-valid subgraph of the set of unconfirmed transactions, in both cases
> (within the limits of what is computationally feasible of course).
>
It's weird because which of two or more conflicting transactions should win
can oscillate back and forth depending on other stuff going on in the
mempool. There's already a bit of that with child pays but this is stranger
and has more oddball edge cases about which transactions to route.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220201/3f148e34/attachment-0001.html>

2023-06-07 23:03:06

- reply

📅 Original date posted:2022-01-31
📝 Original message:Gloria Zhao wrote:
>
> This post discusses limitations of current Bitcoin Core RBF policy and
> attempts to start a conversation about how we can improve it,
> summarizing some ideas that have been discussed. Please reply if you
> have any new input on issues to be solved and ideas for improvement!
>
Is it still verboten to acknowledge that RBF is normal behavior and
disallowing it is the feature, and that feature is mostly there to appease
some people's delusions that zeroconf is a thing? It seems a bit overdue to
disrespect the RBF flag in the direction of always assuming it's on.
> - **Incentive Compatibility**: Ensure that our RBF policy would not
> accept replacement transactions which would decrease fee profits
> of a miner. In general, if our mempool policy deviates from what is
> economically rational, it's likely that the transactions in our
> mempool will not match the ones in miners' mempools, making our
> fee estimation, compact block relay, and other mempool-dependent
> functions unreliable. Incentive-incompatible policy may also
> encourage transaction submission through routes other than the p2p
> network, harming censorship-resistance and privacy of Bitcoin payments.
>
There are two different common regimes which result in different
incentivized behavior. One of them is that there's more than a block's
backlog in the mempool in which case between two conflicting transactions
the one with the higher fee rate should win. In the other case where there
isn't a whole block's worth of transactions the one with higher total value
should win. It would be nice to have consolidated logic which handles both,
it seems the issue has to do with the slope of the supply/demand curve
which in the first case is gentle enough to keep the one transaction from
hitting the rate but in the second one is basically infinite.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220131/0d66162d/attachment.html>

2023-06-07 23:02:29

- reply

📅 Original date posted:2022-01-21
📝 Original message:On Fri, Jan 21, 2022 at 9:32 AM Billy Tetrud <billy.tetrud at gmail.com> wrote:
> > Bitcoin doesn't have a strong single concept of a 'parent'
>
> I'm using the term "parent" loosely in context here to mean a relationship
> where an input has constraints applied to an output (or outputs).
>
Yes and I'm using it more specifically to mean a single parent because the
tricks for implementing capabilities I'm talking about don't work if you
don't have a way of talking about 'my parent' as an unambiguously defined
single UTXO.
>
> > verify the secure hash chain from its parent to itself so that it
> knows what the parent looked like
>
> I guess I just don't understand why you would want to do it this way.
>
The idea here is to optimize for adding as little to the UXTO model as
possible and doing everything with Bitcoin script additions. Some optional
mappings of inputs to outputs in a transaction seem to be necessary but
beyond that the current model can remain unchanged.
> If you send to an address that has such a reverse-looking script, you
> could brick funds that came from the wrong parent. With the reverse
> mechanism, the transaction creating the child, you can prevent this from
> happening by defining the transaction creating such a child as invalid
> unless the child matches the covenant in the parent.
>
If you want to pay to a singleton you don't do it by paying to some
scriptpubkey which represents that singleton, you pay to a scriptpubkey
which says 'I can be spent in any transaction which includes singleton X'
and it does the validation of that other UTXO being the current incarnation
of the singleton using the capabilities validation tricks I mentioned
before.
>
> > "you can only point back so far" leads to transactions becoming invalid,
> which is something we've always strictly avoided because it can result in
> huge problems during reorgs
>
> I'm surprised to hear you say that. I have tried to learn why valid
> transactions that can become invalid is seen as such a problem. I've been
> unsuccessful in finding much information about this. I tried to document
> the full extent of my understanding in my proposal here
> <https://github.com/fresheneesz/bip-efficient-bitcoin-vaults/blob/main/bbv/bip-beforeblockverify.md#reorg-safety> where
> I actually have a quote from you where you said you don't think this is a
> valid concern. Did something change your mind? Or did I misinterpret you?
> What am I missing from that section I linked to?
>
It can be made so that if it goes past the time when the backpointer works
then the transaction is still valid but its vbytes goes up because the
referenced string needs to be repeated on the chain.
I too am a bit on the fence about whether strict transaction
monotinicity is absolutely necessary. The most plausible violation of it to
add would be some kind of max height/age condition to go with the current
min height/age restrictions. What scares me about that isn't so much the
ability to replay reorgs getting messed up (those can be derailed by double
spends anyway) but that either an intentional DOS or just a spike in
transaction fees could cause a deadline to be passed and something to be
bricked for completely technical reasons having nothing to do with its
intended logic. The same type of functionality can be hacked by having an
allowed spend whose only condition is a min height/age so that if the time
has passed as long as someone isn't asleep at the wheel the transaction
will switch to a new state which disallows whatever it is that was supposed
to be disallowed at that time.
Since there isn't any compelling bit of functionality which needs to
violate monotinicity to be implemented I don't see any need to call for an
end to it as a principle. It certainly makes mempool logic a lot simpler
and more reliable.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220121/84c724d7/attachment.html>

2023-06-07 23:02:27

- reply

📅 Original date posted:2022-01-20
📝 Original message:On Tue, Jan 18, 2022 at 6:25 PM Billy Tetrud <billy.tetrud at gmail.com> wrote:
> > 'assert that my parent has a scriptpubkey of X'... That way you can, for
> example, have a UTXO which only allows itself to be absorbed by a
> transaction also involving a UTXO with a particular capability
>
> I'm not sure I fully follow. I usually think about covenants as having the
> reverse form, that a parent would assert "my children must have a script of
> the form XYZ". Are you saying you want to be able to specify that a UTXO
> can only be spent if the resulting outputs of that transaction all share
> the same script? I see this page
> <https://chialisp.com/docs/puzzles/singletons/> but i don't understand
> how those concepts relate to covenants.
>
Two concepts here. First of all Bitcoin doesn't have a strong single
concept of a 'parent', it just has transactions where all the parents lead
to all the children. For this sort of trickery to work more information
needs to be added to specify which of the inputs is the parent of each of
the outputs.
Second what in practice happens is that a coin can check what its own id
is, then verify the secure hash chain from its parent to itself so that it
knows what the parent looked like. For a Singleton it can then rely on the
fact that its ancestors enforced that they each only had one child to know
that it's the only descendant. In some sense this is like covenants which
point backwards in time although that information is already there in
principle because of the secure hash chain but hard to parse.
>
> > allow references to old blocks so code snippets can be pulled out of
> them
>
> Nodes currently aren't required to keep around the whole blockchain, but
> your proposal sounds like it would require them to. I think this could be
> pretty detrimental to future scalability. Monero, for example, has a
> situation where its UTXO set is the whole blockchain because you can't
> generally know what has been spent and what hasn't been. Allowing
> references to old blocks would pull in all this old block data into the
> UTXO set. So unless you're very careful about how or when you can reference
> old blocks, this could cause issues.
>
Don't full nodes by definition have to have the whole chain? This does make
pruned nodes difficult, but it could also have rules like you can only
point back so far.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220120/a3cb9768/attachment.html>

2023-06-07 23:02:26

- reply

📅 Original date posted:2022-01-18
📝 Original message:On Tue, Jan 18, 2022 at 7:10 AM Billy Tetrud <billy.tetrud at gmail.com> wrote:
> > Since scriptpubkeys/scriptsigs continue to run ephemerally at
> validation time full turing completeness is much less dangerous than people
> fear.
>
> The covenant proposals I've seen that might give bitcoin turing
> completeness require a turing complete process to be stepped such that each
> step is a transaction paid for with a usual fee. This fact I think makes
> the turing completeness a lot less scary. No single transaction would be
> turing complete, while a sequence of them could be. But importantly, each
> transaction has a strictly limited runtime and every script could continue
> to have a calculable number of maximum runtime steps.
>
This flows naturally out of the UTXO model. In ETH you don't know how much
transactions will cost in advance because things don't declare their state
up front, but with all dependencies declared up front execution can be made
completely deterministic.
> It would also probably be a good idea to add in a bunch of special
purpose opcodes for making coherent statements about transactions since in
Bitcoin they're a very complex and hard to parse format.
>
> What are some examples you're thinking of?
>
What's needed from a programming perspective is the ability to say 'assert
that my parent has a scriptpubkey of X'. That way you can, for example,
have a UTXO which only allows itself to be absorbed by a transaction also
involving a UTXO with a particular capability ('pay to singleton' is a term
for this) and that capability can be enforced by the scriptpubkey asserting
that either its parent is the originator of it or that its parent also has
the same type of scriptpubkey. This allows capabilities to be added without
gunking up on chain state with things other than UTXOs.
>
> > Once you start implementing complex general purpose functionality it
> tends to get very expensive very fast and is likely impractical unless
> there's a way to compress or at least de-duplicate snippets of code which
> are repeated on chain.
>
> I like this idea. If there was a way to dedupe scripts in some way, it
> could save a lot of bandwidth which would help bitcoin scale better. One
> thing we could do is have a specific set of pre-ordained script snippets
> that are given a shorthand that's stored in the software and explicitly
> shouldn't be transmitted long-hand. That would help for very standard
> widespread things. We could even add in a consensus rule where short-handed
> scripts pay for their expanded vbytes, not the vbytes of the compressed
> version. This would mean the incentives wouldn't be changed by this
> approach.
>
One approach is to allow references to old blocks so code snippets can be
pulled out of them. That avoids having to define the 'common sections' up
front. Charging for virtual vbytes unfortunately keeps smart functionality
very expensive and the point is to make it not so expensive.
> > For a payment to someone to come with a rider where they could accept it
> and think their system was working properly for a while until you exercised
> some kind of retroactive veto on new action or even clawback would
> obviously be unacceptable behavior.
>
> I definitely agree. A payment's covenant should be completely knowable to
> the recipient, and recipients shouldn't accept random covenants they
> haven't explicitly accepted on their own.
>
> > for payments to come with covenants but the recipient not even be able
> to parse them unless they're fully buying into that behavior is much more
> reasonable.
>
> The recipient not being able to parse them? Couldn't that result in
> exactly the situation above you said was not acceptable? The recipient must
> be able to know all the possibilities of the covenant or there might be
> some secret retroactive clawback in there waiting to bite them.
>
Not sure what you're saying. If the recipient can't parse a UTXO the
defined behavior should be that they assume it's bricked.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20220118/5d93153e/attachment-0001.html>

2023-06-07 23:01:45

- reply

📅 Original date posted:2021-12-31
📝 Original message:There are a few different approaches to adding covenants and capabilities
to the UTXO model with varying tradeoffs. It turns out that it can be done
while making very few but not quite zero compromises to practices Bitcoin
has been following so far.
First, the good news: Full support for both capabilities and covenants can
be added without changing the UTXO model whatsoever by adding some more
programmatic capabilities to the language and doing some programmatic
tricks. Since scriptpubkeys/scriptsigs continue to run ephemerally at
validation time full turing completeness is much less dangerous than people
fear. The main thing missing from what's expressed in transactions
themselves is a coherent notion of a single parent of each output instead
of the all-inputs-lead-to-all-outputs approach of transactions currently.
It would also probably be a good idea to add in a bunch of special purpose
opcodes for making coherent statements about transactions since in Bitcoin
they're a very complex and hard to parse format.
Now for the controversial stuff. Once you start implementing complex
general purpose functionality it tends to get very expensive very fast and
is likely impractical unless there's a way to compress or at least
de-duplicate snippets of code which are repeated on chain. Currently
Bitcoin has a strong policy that deciding which transactions to let into a
block for maximum fee is a strictly linear optimization problem and while
it's possible to keep things mostly that way making it completely strict is
unlikely to workable. About as close as you can get is to make it so that
each block can reference code snippets in previous blocks for
deduplication, so at least the optimization is linear for each block by
itself.
Having covenants and capabilities at all is controversial in and of itself.
With covenants the main issue is whether they're opt-in or opt-out. For a
payment to someone to come with a rider where they could accept it and
think their system was working properly for a while until you exercised
some kind of retroactive veto on new action or even clawback would
obviously be unacceptable behavior. But for payments to come with covenants
but the recipient not even be able to parse them unless they're fully
buying into that behavior is much more reasonable.
The main issue which people have raised with capabilities is that if you
were to have colored coins whose value was substantially greater than the
chain they were tokenized on then that could potentially create a business
model for attacking the underlying chain. While this is a real concern
tokenized assets have been out for a while now and have never come close to
causing this to happen, so maybe people aren't so worried about it now.
Given all the above caveats it turns out one weird trick is all you need to
support general purpose capabilities: for a UTXO to have a capability its
scriptpubkey asserts that its parent must either be the originator of that
capability or also conform to the same parent-asserting format. More
complex functionality such as supporting on-chain verifiable colored coins
can also be done but it follows the same pattern: Capabilities are
implemented as backwards pointing covenants.
If you'd like to see a fleshed out implementation of these ideas (albeit in
a slightly different model) there's quite a bit of stuff on chialisp.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20211231/dac00321/attachment.html>

2023-06-07 18:14:10

- reply

📅 Original date posted:2018-08-30
📝 Original message:This seems like a case where a distinction should be made between soft
forks which are likely to cause non-upgraded miners to get orphaned and
ones where they are. Of course in this case it's only 1/2016 of all blocks
so it doesn't really matter, but it's worth thinking about the principle.
In general soft forks are better when they don't cause orphaning on
non-upgraded miners.
The whole problem seems to be caused by the difference between the
timestamps at the end of a period and the block right after it. Soft
forking to force those to be 'close enough' together sounds like a solid
approach. Given that blocks are generally send around fairly quickly, and
that blocks more than two hours in the future are ignored, it seems
reasonable to not allow a backwards jump of that plus some safety
parameter. Let's say three hours. It also feels like a good idea to not
allow a jump of more than three hours forwards either, just on principle.
That should result in minimal code changes, and rarely any orphaning of
non-upgraded miners at all, and still only 1/2016 blocks when they do. And
no trace of a hard fork. It suffers from still allowing the attack a little
bit, but three hours out of every two weeks seems like no big deal.
On Sat, Aug 25, 2018 at 5:10 AM Johnson Lau via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> To determine the new difficulty, it is supposed to compare the timestamps
> of block (2016n - 1) with block (2016n - 2017). However, an off-by-one bug
> makes it compares with block (2016n - 2016) instead.
>
> A naive but perfect fix is to require every block (2016x) to have a
> timestamp not smaller than that of its parent block. However, a chain-split
> would happen even without any attack, unless super-majority of miners are
> enforcing the new rules. This also involves mandatory upgrade of pool
> software (cf. pool software upgrade is not mandatory for segwit). The best
> way is to do it with something like BIP34, which also requires new pool
> software.
>
> We could have a weaker version of this, to require the timestamp of block
> (2016x) not smaller than its parent block by t-seconds, with 0 <= t <=
> infinity. With a bigger t, the fix is less effective but also less likely
> to cause intentional/unintentional split. Status quo is t = infinity.
>
> Reducing the value of t is a softfork. The aim is to find a t which is
> small-enough-to-prohibit-time-wrap-attack but also
> big-enough-to-avoid-split. With t=86400 (one day), a time-wrap attacker may
> bring down the difficulty by about 1/14 = 7.1% per round. Unless new blocks
> were coming incredibly slow, the attacker needs to manipulate the MTP for
> at least 24 hours, or try to rewrite 24 hours of history. Such scale of 51%
> attack is already above the 100-block coinbase maturity safety theshold and
> we are facing a much bigger problem.
>
> With t=86400, a non-majority, opportunistic attacker may split the chain
> only if we have no new block for at least 24 - 2 = 22 hours (2-hours is the
> protocol limit for using a future timestamp) at the exact moment of
> retarget. That means no retarget is possible in the next 2016 blocks. Doing
> a time-wrap attack at this point is not quite interesting as the coin is
> probably already worthless. Again, this is a much bigger problem than the
> potential chain spilt. People will yell for a difficulty (and time wrap
> fix, maybe) hardfork to resuscitate the chain.
>
>
>
>
> > On 21 Aug 2018, at 4:14 AM, Gregory Maxwell via bitcoin-dev <
> bitcoin-dev at lists.linuxfoundation.org> wrote:
> >
> > Since 2012 (IIRC) we've known that Bitcoin's non-overlapping
> > difficulty calculation was vulnerable to gaming with inaccurate
> > timestamps to massively increase the rate of block production beyond
> > the system's intentional design. It can be fixed with a soft-fork that
> > further constraints block timestamps, and a couple of proposals have
> > been floated along these lines.
> >
> > I put a demonstration of timewarp early in the testnet3 chain to also
> > let people test mitigations against that. It pegs the difficulty way
> > down and then churned out blocks at the maximum rate that the median
> > time protocol rule allows.
> >
> > I, and I assume others, haven't put a big priority into fixing this
> > vulnerability because it requires a majority hashrate and could easily
> > be blocked if someone started using it.
> >
> > But there haven't been too many other network consensus rules going on
> > right now, and I believe at least several of the proposals suggested
> > are fully compatible with existing behaviour and only trigger in the
> > presence of exceptional circumstances-- e.g. a timewarp attack. So
> > the risk of deploying these mitigations would be minimal.
> >
> > Before I dust off my old fix and perhaps prematurely cause fixation on
> > a particular approach, I thought it would be useful to ask the list if
> > anyone else was aware of a favourite backwards compatible timewarp fix
> > proposal they wanted to point out.
> >
> > Cheers.
> > _______________________________________________
> > 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/20180830/579ee190/attachment-0001.html>

2023-06-07 18:13:55

- reply

📅 Original date posted:2018-08-03
📝 Original message:BLS signatures have the same aggregation feature as Schnorr signatures but
even better because the aggregation can be done non-interactively, at the
expense of being a bit slower. We just released a first draft (but fully
functional) library for doing BLS signatures based on a construction based
on musig. Feedback, discussion, and usage is very welcome.
https://github.com/Chia-Network/bls-signatures
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180803/64cf8b43/attachment.html>

2023-06-07 18:13:21

- reply

📅 Original date posted:2018-06-18
📝 Original message:Not sure what you're saying here. The block rate can't be particularly
increased or decreased in the long run due to the work difficulty
adjustment getting you roughly back where you started no matter what.
Someone could DOS the system by producing empty blocks, sure, that's a
central attack of what can happen when someone does a 51% attack with no
special countermeasures other than everything that Bitcoin does at its
core. An attacker or group of attackers could conspire to reduce block
sizes in order to increase transaction fees, in fact they could do that
with a miner activated soft fork. That appears both doable and given past
things which have happened with transaction fees in the past potentially
lucrative, particularly as block rewards fall in the future. Please don't
tell the big mining pools about it.
On Mon, Jun 18, 2018 at 11:39 AM Артём Литвинович via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Dilution is a potential attack i randomly came up with in a Twitter
> arguement and couldn't find any references to or convincing arguments of it
> being implausible.
>
> Suppose a malicious actor were to acquire a majority of hash power, and
> proceed to use that hash power to produce valid, but empty blocks.
>
> As far as i understand it, this would effectively reduce the block rate by
> half or more and since nodes can't differentiate block relay and block
> production there would be nothing they can do to adjust difficulty or black
> list the attacker.
>
> At a rough estimate of $52 per TH equipment cost (Antminer pricing) and
> 12.5 BTC per 10 minutes power cost we are looking at an order of $2 billion
> of equipment and $0.4 billion a month of power costs (ignoring block
> reward) to maintain an attack - easily within means of even a minor
> government-scale actor.
>
> Is that a plausible scenario, or am i chasing a mirage? If it is
> plausible, what could be done to mitigate it?
>
>
> -Artem
> _______________________________________________
> 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/20180618/98b4fa44/attachment.html>

2023-06-07 18:12:57

- reply

📅 Original date posted:2018-06-09
📝 Original message:So are you saying that if fully validating nodes wish to prune they can
maintain the ability to validate old transactions by cacheing the number of
transactions in each previous block?
On Thu, Jun 7, 2018 at 3:20 PM, Peter Todd <pete at petertodd.org> wrote:
> On Thu, Jun 07, 2018 at 02:15:35PM -0700, Bram Cohen wrote:
> > Are you proposing a soft fork to include the number of transactions in a
> > block in the block headers to compensate for the broken Merkle format?
> That
> > sounds like a good idea.
> >
> > On Thu, Jun 7, 2018 at 10:13 AM, Peter Todd via bitcoin-dev <
> > bitcoin-dev at lists.linuxfoundation.org> wrote:
> >
> > > It's well known that the Bitcoin merkle tree algorithm fails to
> distinguish
> > > between inner nodes and 64 byte transactions, as both txs and inner
> nodes
> > > are
> > > hashed the same way. This potentially poses a problem for tx inclusion
> > > proofs,
> > > as a miner could (with ~60 bits of brute forcing) create a transaction
> that
> > > committed to a transaction that was not in fact in the blockchain.
> > >
> > > Since odd-numbered inner/leaf nodes are concatenated with themselves
> and
> > > hashed
> > > twice, the depth of all leaves (txs) in the tree is fixed.
> > >
> > > It occured to me that if the depth of the merkle tree is known, this
> > > vulnerability can be trivially avoided by simply comparing the length
> of
> > > the
> > > merkle path to that known depth. For pruned nodes, if the depth is
> saved
> > > prior
> > > to pruning the block contents itself, this would allow for completely
> safe
> > > verification of tx inclusion proofs, without a soft-fork; storing this
> ^^^^^^^^^^^^^^^^^^^
>
> Re-read my post: I specifically said you do not need a soft-fork to
> implement
> this. In fact, I think you can argue that this is an accidental feature,
> not a
> bug, as it further encourages the use of safe full verifiaction rather than
> unsafe lite clients.
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180608/8320bbb2/attachment.html>

2023-06-07 18:12:56

- reply

📅 Original date posted:2018-06-07
📝 Original message:Are you proposing a soft fork to include the number of transactions in a
block in the block headers to compensate for the broken Merkle format? That
sounds like a good idea.
On Thu, Jun 7, 2018 at 10:13 AM, Peter Todd via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> It's well known that the Bitcoin merkle tree algorithm fails to distinguish
> between inner nodes and 64 byte transactions, as both txs and inner nodes
> are
> hashed the same way. This potentially poses a problem for tx inclusion
> proofs,
> as a miner could (with ~60 bits of brute forcing) create a transaction that
> committed to a transaction that was not in fact in the blockchain.
>
> Since odd-numbered inner/leaf nodes are concatenated with themselves and
> hashed
> twice, the depth of all leaves (txs) in the tree is fixed.
>
> It occured to me that if the depth of the merkle tree is known, this
> vulnerability can be trivially avoided by simply comparing the length of
> the
> merkle path to that known depth. For pruned nodes, if the depth is saved
> prior
> to pruning the block contents itself, this would allow for completely safe
> verification of tx inclusion proofs, without a soft-fork; storing this
> data in
> the block header database would be a simple thing to do.
>
> Lite client verification without a trusted source of known-valid headers is
> dangerous anyway, so this protection makes for a fairly simple addition to
> any
> lite client protocol.
>
>
> # Brute Force Cost Assuming a Valid Tx
>
> Consider the following 64 byte transaction:
>
> tx = CTransaction([CTxIn(COutPoint(b'\xaa'*32,0xbbbbbbbb),
> nSequence=0xcccccccc)],[CTxOut(2**44-1,CScript([b'\
> xdd\xdd\xdd']))],nLockTime=2**31-1)
>
> If we serialize it, the last 32 bytes are:
>
> aaaaaaaaaa bbbbbbbb 00 cccccccc 01 ffffffffff0f0000 04 03dddddd
> ffffff7f
> ↳prevhash↲ ↳ n ↲ ↳ seq ↲ ↳ nValue ↲ ↳ pubk ↲ ↳lockt
> ↲
> ↳ sig_len ↳num_txouts ↳scriptPubKey_len
>
> Of those fields, we have free choice of the following bits:
>
> prevhash: 40 - prev tx fully brute-forcable, as tx can be created to match
> prev_n: 16 - can create a tx with up to about 2^16 outputs
> seq: 32 - fully brute-forcable in nVersion=1 txs
> nValue: 44 - assuming attacker has access to 175,921 BTC, worth ~1.3
> billion right now
> pubk: 32 - fully brute-forcable if willing to lose BTC spent; all
> scriptPubKeys are valid
> nLockTime: 31 - valid time-based nLockTime
> Total: 195 bits free choice → 61 bits need to be brute-forced
>
> Additionally, this can be improved slightly by a few more bits by checking
> for
> valid scriptSig/scriptPubKey combinations other than a zero-length
> scriptSig;
> the attacker can also avoid creating an unspendable output this way, and
> recover their funds by spending it in the same block with a third
> transaction.
> An obvious implementation making use of this would be to check that the
> high
> bits of prevout.n are zero first, prior to doing more costly checks.
>
> Finally, if inflation is not controlled - and thus nValue can be set
> freely -
> note how the brute force is trivial. There may very well exist
> crypto-currencies
> for which this brute-force is much easier than it is on Bitcoin!
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
> _______________________________________________
> 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/20180607/6531c188/attachment.html>

2023-06-07 18:12:28

- reply

📅 Original date posted:2018-05-23
📝 Original message:You compressed something which is truly natively a bitfield using regular
compression algorithms? That is expected to get horrible results. Much
better would be something which handles it natively, say doing run length
encoding on the number of repeated bits and compressing that using elias
omega encoding. That is suboptimal in a few ways but has the advantage of
working well both on things which are mostly zeros or mostly ones, and only
performs badly on truly random bits.
It isn't super clear how relevant this information is. The TXO bitfield is
fairly small to begin with, and to compress the data in real time would
require a special data structure which gets worse compression than straight
compressing the whole thing and has slower lookups than an uncompressed
version. Writing such a thing sounds like an interesting project though.
On Wed, May 23, 2018 at 4:48 PM, Jim Posen via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> I decided to look into the metrics around compression ratios of TXO
> bitfields, as proposed by Bram Cohen [1]. I'm specifically interested in
> the feasibility of committing to them with block headers. In combination
> with block commitments to TXOs themselves, this would enable UTXO
> inclusion/exclusion proofs for light clients.
>
> First, looking just at proofs of inclusion in the UTXO set, each block
> needs what Bram calls a "proof of position." Concretely, one such
> construction is a Merkle root over all of the block's newly created coins,
> including their output data (scriptPubKey + amount), the outpoint (txid +
> index), and an absolute index of the output in the entire blockchain. A
> Merkle branch in this tree constitutes a proof of position. Alternatively,
> the "position", rather than being an absolute index in the chain, could be
> a block hash plus an output index within the block.
>
> Let's say we use the absolute index in the chain as position. A TXO
> spentness bitfield can be constructed for the entire chain, which is added
> to when new coins are created and modified when they are spent. In order to
> compactly prove spentness in this bitfield to a client, one could chunk up
> the bitfield and construct a Merkle Mountain Range [2] over the chunks.
> Instead of building an MMR over outputs themselves, as proposed by Peter
> Todd [3], an MMR constructed over bitfield chunks grows far slower, by a
> large constant factor. Slower growth means faster updates.
>
> So there's the question of how much these bitfields can be compressed. We
> expect some decent level because patterns of spending coins are very
> non-random.
>
> The top graph in the attached figure shows the compression ratios possible
> on a TXO bitfield split into 4 KiB chunks, using gzip (level=9) and lz4.
> Data was collected at block height 523,303. You can see that the
> compression ratio is much lower for older chunks and is worse for more
> recent blocks. Over the entire history, gzip achieves 34.4%, lz4 54.8%,
> and bz2 37.6%. I'm kind of surprised that the ratios are not lower with
> off-the-shelf algorithms. And that gzip performs better than bz2 (it seems
> to be a factor of the chunk size?).
>
> Alternatively, we can look at bitfields stored separately by block, which
> is more compatible with constructions where an output's position is its
> block hash plus relative index. The per-block bitfield sizes are shown in
> the bottom graph. The compression ratios overall are 50% for gzip, 70% for
> lz4, and 61.5% for bz2.
>
> [1] https://lists.linuxfoundation.org/pipermail/
> bitcoin-dev/2017-March/013928.html
> [2] https://github.com/opentimestamps/opentimestamps-
> server/blob/master/doc/merkle-mountain-range.md
> [3] https://petertodd.org/2016/delayed-txo-commitments
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180523/4ae3fd4f/attachment-0001.html>

2023-06-07 18:12:04

- reply

📅 Original date posted:2018-05-10
📝 Original message:I'm not sure about the best way to approach soft-forking (I've opined on it
before, and still find the details mind-numbing) but the end goal seems
fairly clearly to be an all of the above: Have aggregatable public keys
which support simple signatures, taproot with BIP 114 style taproot, and
Graftroot. And while you're at it, nuke OP_IF from orbit and make all the
unused opcodes be return success.
This all in principle could be done in one fell swoop with a single new
script type. That would be a whole lot of stuff to roll out at once, but at
least it wouldn't have so many painstaking intermediate soft forks to
administer.
On Thu, May 10, 2018 at 7:23 AM, Russell O'Connor via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Thanks for writing this up Anthony.
>
> Do you think that a CHECKSIGFROMSTACK proposal should be included within
> this discussion of signature soft-forks, or do you see it as an unrelated
> issue?
>
> CHECKSIGFROMSTACK enables some forms of (more) efficent MPC (See
> http://people.csail.mit.edu/ranjit/papers/scd.pdf), enables poor-man's
> covenants, and I believe the lightning folks are interested in it as well
> for some constant space storage scheme.
>
> On Thu, May 10, 2018 at 8:10 AM, Anthony Towns via bitcoin-dev <
> bitcoin-dev at lists.linuxfoundation.org> wrote:
>
>> Hello world,
>>
>> After the core dev meetup in March I wrote up some notes of where I
>> think things stand for signing stuff post-Schnorr. It was mostly for my
>> own benefit but maybe it's helpful for others too, so...
>>
>> They're just notes, so may assume a fair bit of background to be able to
>> understand the meaning of the bullet points. In particular, note that I'm
>> using "schnorr" just to describe the signature algorithm, and the terms
>> "key aggregation" to describe turning an n-of-n key multisig setup into
>> a single key setup, and "signature aggregation" to describe combining
>> signatures from many inputs/transactions together: those are often all
>> just called "schnorr signatures" in various places.
>>
>>
>> Anyway! I think it's fair to split the ideas around up as follows:
>>
>> 1) Schnorr CHECKSIG
>>
>> Benefits:
>> - opportunity to change signature encoding from DER to save a few
>> bytes per signature, and have fixed size signatures making tx size
>> calculations easier
>>
>> - enables n-of-n multisig key aggregation (a single pubkey and
>> signature gives n-of-n security; setup non-interactively via muSig,
>> or semi-interactively via proof of possession of private key;
>> interactive signature protocol)
>>
>> - enables m-of-n multisig key aggregation with interactive setup and
>> interactive signature protocol, and possibly substantial storage
>> requirements for participating signers
>>
>> - enables scriptless scripts and discreet log contracts via
>> key aggregation and interactive
>>
>> - enables payment decorrelation for lightning
>>
>> - enables batch validation of signatures, which substantially reduces
>> computational cost of signature verification, provided a single
>> "all sigs valid" or "some sig(s) invalid" output (rather than
>> "sig number 5 is invalid") is sufficient
>>
>> - better than ecdsa due to reducing signature malleability
>> (and possibly due to having a security proof that has had more
>> review?)
>>
>> Approaches:
>> - bump segwit version to replace P2WPKH
>> - replace an existing OP_NOP with OP_CHECKSCHNORRVERIFY
>> - hardfork to allowing existing addresses to be solved via Schnorr
>> sig
>> as alternative to ECDSA
>>
>> 2) Merkelized Abstract Syntax Trees
>>
>> Two main benefits for enabling MAST:
>> - logarithmic scaling for scripts with many alternative paths
>> - only reveals (approximate) number of alternative execution branches,
>> not what they may have been
>>
>> Approaches:
>> - replace an existing OP_NOP with OP_MERKLE_TREE_VERIFY, and treat an
>> item remaining on the alt stack at the end of script exeution as a
>> script and do tail-recursion into it (BIP 116, 117)
>> - bump the segwit version and introduce a "pay-to-merkelized-script"
>> address form (BIP 114)
>>
>> 3) Taproot
>>
>> Requirements:
>> - only feasible if Schnorr is available (required in order to make the
>> pubkey spend actually be a multisig spend)
>> - andytoshi has written up a security proof at
>> https://github.com/apoelstra/taproot
>>
>> Benefits:
>> - combines pay-to-pubkey and pay-to-script in a single address,
>> improving privacy
>> - allows choice of whether to use pubkey or script at spend time,
>> allowing for more efficient spends (via pubkey) without reducing
>> flexibility (via script)
>>
>> Approaches:
>> - bump segwit version and introduce a "pay-to-taproot" address form
>>
>> 4) Graftroot
>>
>> Requirements:
>> - only really feasible if Schnorr is implemented first, so that
>> multiple signers can be required via a single pubkey/signature
>> - people seem to want a security proof for this; not sure if that's
>> hard or straightforward
>>
>> Benefits:
>> - allows delegation of authorisation to spend an output already
>> on the blockchain
>> - constant scaling for scripts with many alternative paths
>> (better than MAST's logarithmic scaling)
>> - only reveals the possibility of alternative execution branches,
>> not what they may have been or if any actually existed
>>
>> Drawbacks:
>> - requires signing keys to be online when constructing scripts (cannot
>> do complicated pay to cold wallet without warming it up)
>> - requires storing signatures for scripts (if you were able to
>> reconstruct the sigs, you could just sign the tx directly and
>> wouldn't
>> use a script)
>> - cannot prove that alternative methods of spending are not
>> possible to anyone who doesn't exclusively hold (part of) the
>> output address private key
>> - adds an extra signature check on script spends
>>
>> Approaches:
>> - bump segwit version and introduce a "pay-to-graftroot" address form
>>
>> 5) Interactive Signature Aggregation
>>
>> Requirements:
>> - needs Schnorr
>>
>> Description:
>> - allows signers to interactively collaborate when constructing a
>> transaction to produce a single signature that covers multiple
>> inputs and/or OP_CHECKSIG invocations that are resolved by Schnorr
>> signatures
>>
>> Benefits:
>> - reduces computational cost of additional signatures (i think?)
>> - reduces witness storage needed for additional signatures to just the
>> sighash flag byte (or bytes, if it's expanded)
>> - transaction batching and coinjoins potentially become cheaper than
>> independent transactions, indirectly improving on-chain privacy
>>
>> Drawbacks:
>> - each soft-fork introduces a checkpoint, such that signatures that
>> are not validated by versions prior to the soft-fork cannot be
>> aggregated with signatures that are validated by versions prior to
>> the soft-fork (see [0] for discussion about avoiding that drawback)
>>
>> Approaches:
>> - crypto logic can be implemented either by Bellare-Neven or MuSig
>> - needs a new p2wpkh output format, so likely warrants a segwit
>> version bump
>> - may warrant allowing multiple aggregation buckets
>> - may warrant peer-to-peer changes and a new per-tx witness
>>
>> 6) Non-interactive half-signature aggregation within transaction
>>
>> Requirements:
>> - needs Schnorr
>> - needs a security proof before deployment
>>
>> Benefits:
>> - can halve the size of non-aggregatable signatures in a transaction
>> - in particular implies the size overhead of a graftroot script
>> is just 32B, the same as a taproot script
>>
>> Drawbacks:
>> - cannot be used with scriptless-script signatures
>>
>> Approaches:
>> - ideally best combined with interactive aggregate signatures, as it
>> has similar implementation requirements
>>
>> 7) New SIGHASH modes
>>
>> These will also need a new segwit version (for p2pk/p2pkh) and probably
>> need to be considered at the same time.
>>
>> 8) p2pk versus p2pkh
>>
>> Whether to stick with a pubkeyhash for the address or just have a
>> pubkey
>> needs to be decided for any new segwit version.
>>
>> 9) Other new opcodes
>>
>> Should additional opcodes in new segwit versions be reserved as OP_NOP
>> or
>> as OP_RETURN_VALID, or something else?
>>
>> Should any meaningful new opcodes be supported or re-enabled?
>>
>> 10) Hard-fork automatic upgrade of p2pkh to be spendable via segwit
>>
>> Making existing p2pk or p2pkh outputs spendable via Schnorr with
>> interactive signature aggregation would likely be a big win for people
>> with old UTXOs, without any decrease in security, especially if done
>> a significant time after those features were supported for new outputs.
>>
>> 11) Should addresses be hashes or scripts?
>>
>> maaku's arguments for general opcodes for MAST make me wonder a bit
>> if the "p2pkh" approach isn't better than the "p2wpkh" approach; ie
>> should we have script opcodes as the top level way to write addresses,
>> rather than picking the "best" form of address everyone should use,
>> and having people have to opt-out of that. probably already too late
>> to actually have that debate though.
>>
>> Anyway, I think what that adds up to is:
>>
>> - Everything other than MAST and maybe some misc new CHECKVERIFY opcodes
>> really needs to be done via new segwit versions
>>
>> - We can evaluate MAST in segwit v0 independently -- use the existing
>> BIPs to deploy MAST for v0; and re-evaluate entirely for v1 and later
>> segwit versions.
>>
>> - There is no point deploying any of this for non-segwit scripts
>>
>> - Having the taproot script be a MAST root probably makes sense. If so,
>> a separate OP_MERKLE_MEMBERSHIP_CHECK opcode still probably makes
>> sense at some point.
>>
>> So I think that adds up to:
>>
>> a) soft-fork for MAST in segwit v0 anytime if there's community/economic
>> support for it?
>>
>> b) soft-fork for OP_CHECK_SCHNORR_SIG_VERIFY in segwit v0 anytime
>>
>> c) soft-fork for segwit v1 providing Schnorr p2pk(h) addresses and
>> taproot+mast addresses in not too much time
>>
>> d) soft-fork for segwit v2 introducing further upgrades, particularly
>> graftroot
>>
>> e) soft-fork for segwit v2 to support interactive signature aggregation
>>
>> f) soft-fork for segwit v3 including non-interactive sig aggregation
>>
>> The rationale there is:
>>
>> (a) and (b) are self-contained and we could do them now. My feeling is
>> better to skip them and go straight to (c)
>>
>> (c) is the collection of stuff that would be a huge win, and seems
>> "easily" technically feasible. signature aggregation seems too
>> complicated to fit in here, and getting the other stuff done while we
>> finish thinking about sigagg seems completely worthwhile.
>>
>> (d) is a followon for (c), in case signature aggregation takes a
>> *really* long while. It could conceivably be done as a different
>> variation of segwit v1, really. It might turn out that there's no
>> urgency for graftroot and it should be delayed until non-interactive
>> sig aggregation is implementable.
>>
>> (e) and (f) are separated just because I worry that non-interactive
>> sig aggregation might not turn out to be possible; doing them as a
>> single upgrade would be preferrable.
>>
>> Cheers,
>> aj
>>
>> [0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018
>> -March/015838.html
>>
>> _______________________________________________
>> 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/20180510/4f7a41ed/attachment-0001.html>

2023-06-07 18:11:49

- reply

📅 Original date posted:2018-05-07
📝 Original message:A technical point about SIGHASH_NOINPUT: It seems like a more general and
technically simpler to implement idea would be to have a boolean specifying
whether the inputs listed must be all of them (the way it works normally)
or a subset of everything. It feels like a similar boolean should be made
for outputs as well. Or maybe a single boolean should apply to both. In any
case, one could always use SIGHASH_SUBSET and not specify any inputs and
that would have the same effect as SIGHASH_NOINPUT.
On Mon, May 7, 2018 at 12:40 PM, Christian Decker via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Given the general enthusiasm, and lack of major criticism, for the
> `SIGHASH_NOINPUT` proposal, I'd like to formally ask the BBEs (benevolent
> BIP editors) to be assigned a BIP number. I have hacked together a
> simple implementation of the hashing implementation in Bitcoin Core [1]
> though I think it's unlikely to sail through review, and given the lack
> of ground-work on witness V1 scripts, I can't really test it now, and
> only the second commit is part of the implementation itself.
>
> One issue that was raised off list was that some fork coins have used
> sighash 0x40 as FORKID. This does not conflict with this proposal since
> the proposal only applies to segwit transactions, which the fork coins
> have explicitly disabled :-)
>
> I'm looking forward to discussing how to we can move forward to
> implementing this proposal, and how we can combine multiple proposals
> into the next soft-fork.
>
> Cheers,
> Christian
>
> [1] https://github.com/cdecker/bitcoin/tree/noinput
> _______________________________________________
> 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/20180507/6a2c236a/attachment-0001.html>

2023-06-07 18:11:21

- reply

📅 Original date posted:2018-03-28
📝 Original message:On Mon, Mar 26, 2018 at 11:34 PM, Anthony Towns <aj at erisian.com.au> wrote:
> On Wed, Mar 21, 2018 at 05:47:01PM -0700, Bram Cohen via bitcoin-dev wrote:
> > [...] Most unused opcodes should be reclaimed as RETURN_VALID,
> > but there should still be one OP_NOP and there should be a 'real'
> RETURN_VALID,
> > which (a) is guaranteed to not be soft forked into something else in the
> > future, and (b) doesn't have any parsing weirdness.
>
> What's the reason for those? I could see an argument for RETURN_VALID, I
> guess:
>
> confA IF condB IF condC IF [pathA] RETURN_VALID ENDIF ENDIF ENDIF [pathB]
>
> is probably simpler and saves 3 bytes compared to:
>
> 1 condA IF condB IF condC IF [pathA] NOT ENDIF ENDIF ENDIF IF [pathB]
> ENDIF
>
> but that doesn't seem crazy compelling?
Mostly yes it's for that case and also for:
condA IF RETURN_VALID ENDIF condb IF RETURN_VALID ENDIF condc
Technically that can be done with fewer opcodes using OP_BOOLOR but maybe
in the future there will be some incentive for short circuit evaluation
But there's also the general principle that it's only one opcode and if
there are a lot of things which look like RETURN_VALID there should be one
thing which actually is RETURN_VALID
> I don't see a reason to just keep one OP_NOP though.
>
Mostly based on momentum because there are several of them there right now.
If noone else wants to defend it I won't either.
> > By far the most expedient option is (e) cause a RETURN_VALID at parse
> time.
> > There's even precedent for this sort of behavior in the other direction
> with
> > disabled opcodes causing failure at parse time even if they aren't being
> > executed.
>
> You're probably right. That still doesn't let you implement intercal's
> COMEFROM statement as a new opcode, of course. :)
>
That can be in the hardfork wishlist :-)
> > A lot can be said about all the options, but one thing I feel like
> snarking
> > about is that if you get rid of IFs using MAST, then it's highly unclear
> > whether OP_DEPTH should be nuked as well. My feeling is that it should
> and that
> > strict parsing should require that the bottom thing in the witness gets
> > referenced at some point.
>
> I guess when passing the script you could perhaps check if each witness
> item could have been replaced with OP_FALSE or OP_1 and still get the
> same result, and consider the transaction non-standard if so?
>
Essentially all opcodes including OP_PICK make clear at runtime how deep
they go and anything below the max depth can be safely eliminated (or used
as grounds for rejecting in strict mode). The big exception is OP_DEPTH
which totally mangles the assumptions. It's trivial to make scripts which
use OP_DEPTH which become invalid with things added below the stack then go
back to being valid again with more things added even though the individual
items are never even accessed.
>
> > Hacking in a multisig opcode isn't a horrible idea, but it is very stuck
> > specifically on m-of-n and doesn't support more complex formulas for how
> > signatures can be combined, which makes it feel hacky and weird.
>
> Hmm? The opcode I suggested works just as easily with arbitrary formulas,
> eg, "There must be at least 1 signer from pka{1,2,3}, and 3 signers all
> up, except each of pkb{1,2,3,4,5,6} only counts for half":
>
> 0 pkb6 pkb5 pkb4 pkb3 pkb2 pkb1 pka3 pka2 pka1 9 CHECK_AGGSIG_VERIFY
> (declare pubkeys)
> 0b111 CHECK_AGG_SIGNERS VERIFY
> (one of pka{1,2,3} must sign)
> 0b001 CHECK_AGG_SIGNERS
> 0b010 CHECK_AGG_SIGNERS ADD
> 0b100 CHECK_AGG_SIGNERS ADD
> DUP ADD
> (pka{1,2,3} count double)
> 0b000001000 CHECK_AGG_SIGNERS ADD
> 0b000010000 CHECK_AGG_SIGNERS ADD
> 0b000100000 CHECK_AGG_SIGNERS ADD
> 0b001000000 CHECK_AGG_SIGNERS ADD
> 0b010000000 CHECK_AGG_SIGNERS ADD
> 0b100000000 CHECK_AGG_SIGNERS ADD
> (pkb{1..6} count single)
> 6 EQUAL
> (summing to a total of 3 doubled)
>
> Not sure that saves it from being "hacky and weird" though...
>
That is very hacky and weird. Doing MAST on lots of possibilities is always
reasonably elegant, and it only gets problematic when the number of
possibilities is truly massive.
It's also the case that BLS can support complex key agreement schemes
without even giving away that it isn't a simple single signature. Just
saying.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180327/51bdea13/attachment.html>

2023-06-07 18:11:20

- reply

📅 Original date posted:2018-03-21
📝 Original message:Regarding the proposed segwit v2 with reclaiming most things as
RETURN_VALID, the net result for what's being proposed in the near future
for supporting aggregated signatures in the not-so-near future is to punt.
A number of strategies are possible for how to deal with new opcodes being
added later on, and the general strategy of making unused opcodes be
RETURN_VALID for now and figuring out how to handle it later works for all
of them. I think this is the right approach, but wanted to clarify that it
is in fact the approach being proposed.
That said, there are some subtleties to getting it right which the last
message doesn't really cover. Most unused opcodes should be reclaimed as
RETURN_VALID, but there should still be one OP_NOP and there should be a
'real' RETURN_VALID, which (a) is guaranteed to not be soft forked into
something else in the future, and (b) doesn't have any parsing weirdness.
The parsing weirdness of all the unclaimed opcodes is interesting. Because
everything in an IF clause needs to be parsed in order to find where the
ELSE is, you have a few options for dealing with an unknown opcode getting
parsed in an unexecuted section of code. They are (a) avoid the problem
completely by exterminating IF and MASTing (b) avoid the problem completely
by getting rid of IF and adding IFJUMP, IFNJUMP, and JUMP which specify a
number of bytes (this also allows for script merkleization) (c) require all
new opcodes have fixed length 1, even after they're soft forked, (d) do
almost like (c) but require that on new soft forks people hack their old
scripts to still parse properly by avoiding the OP_ELSE in inopportune
places (yuck!) (e) make it so that the unknown opcodes case a RETURN_VALID
even when they're parsed, regardless of whether they're being executed.
By far the most expedient option is (e) cause a RETURN_VALID at parse time.
There's even precedent for this sort of behavior in the other direction
with disabled opcodes causing failure at parse time even if they aren't
being executed.
A lot can be said about all the options, but one thing I feel like snarking
about is that if you get rid of IFs using MAST, then it's highly unclear
whether OP_DEPTH should be nuked as well. My feeling is that it should and
that strict parsing should require that the bottom thing in the witness
gets referenced at some point.
Hacking in a multisig opcode isn't a horrible idea, but it is very stuck
specifically on m-of-n and doesn't support more complex formulas for how
signatures can be combined, which makes it feel hacky and weird.
Also it may make sense to seriously consider BLS signatures, which have a
lot of practical benefits starting with them being noninteractively
aggregatable so you can always assume that they're aggregated instead of
requiring complex semantics to specify what's aggregated with what. My team
is working on an implementation which has several advantages over what's
currently in the published literature but it isn't quite ready for public
consumption yet. This should probably go on the pile of reasons why it's
premature to finalize a plan for aggregation at this point.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180321/c0b652a2/attachment.html>

2023-06-07 18:03:55

- reply

📅 Original date posted:2017-07-05
📝 Original message:On Tue, Jul 4, 2017 at 6:30 PM, shaolinfry via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Some people have criticized BIP9's blocktime based thresholds arguing they
> are confusing (the first retarget after threshold). It is also vulnerable
> to miners fiddling with timestamps in a way that could prevent or delay
> activation - for example by only advancing the block timestamp by 1 second
> you would never meet the threshold (although this would come a the penalty
> of hiking the difficulty dramatically).
>
> On the other hand, the exact date of a height based thresholds is hard to
> predict a long time in advance due to difficulty fluctuations. However,
> there is certainty at a given block height and it's easy to monitor.
>
You could get most of the best of both with a combination of the two: Have
the activation be a timestamp plus a certain number of blocks to come after
maybe about 100, which is more than enough to make sure all the games which
can be played with timestamps have passed but a small enough amount that it
doesn't add much uncertainty to wall clock time.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170704/029eec8d/attachment.html>

2023-06-07 18:01:36

- reply

📅 Original date posted:2017-05-23
📝 Original message:On Mon, May 22, 2017 at 12:05 AM, Russell O'Connor via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> The SHA256 compression function takes two inputs:
>
> 1. A 256-bit value for the previous chunk in a chain, or an initial vector
> in the case of the first chunk.
> 2. A 512-bit chunk of data.
>
> sha256Compress : Word256 × Word512 -> Word256
>
> In total, the SHA256 compression function compresses 768-bits into
> 256-bits. The Merkle roots of two branches occupy 512 bits, and this
> leaves another 256-bits of space available for tags.
>
Ya know, when you're building a Merkle Trie that's exactly the primitive
you need.
In my own construction the assumption is that the values are already hashed
down to 256 bits when they're passed in, and the tags (which are currently
done by sacrificing bits instead of using tags, that needs to be fixed)
include three states for either side: empty, unary, or middle. Three of
those possibilities are unreachable (empty/empty, empty/unary, unary/empty)
so there are 6 possible tags needed. This approach essentially skips doing
the unary hashes, a further performance improvement. There doesn't appear
to be any downside in leveraging this trick as long as tags are cheap.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170522/1445b092/attachment-0001.html>

2023-06-07 18:00:30

- reply

📅 Original date posted:2017-04-19
📝 Original message:Repeatedly hashing to make it so that lossy implementations just fail
sounds like a great idea. Also relying on a single crypto primitive which
is as simple as possible is also a great idea, and specifically using
blake2b is conservative because not only is it simple but its block size is
larger than the amount of data being hashed so asicboost-style attacks
don't apply at all and the logic of multiple blocks doesn't have to be
built.
Memory hard functions are a valiant effort and are holding up better than
expected but the problem is that when they fail they fail catastrophically,
immediately going from running on completely commodity hardware to only
running on hardware from the one vendor who's pulled off the feat of making
it work. My guess is it's only a matter of time until that happens.
So the best PoW function we know of today, assuming that you're trying to
make mining hardware as commodity as possible, is to repeatedly hash using
blake2b ten or maybe a hundred times.
Mind you, I still think hard forking the PoW function is a very bad idea,
but if you were to do it, that would be the way to go.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170419/6dddcc73/attachment.html>

2023-06-07 17:59:52

- 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

- 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

- 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

- 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:56

- reply

📅 Original date posted:2017-04-03
📝 Original message:On Sun, Apr 2, 2017 at 1:43 PM, praxeology_guy via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> TL;DR: using spentness bits scales linearly... vs swapping digest leafs
> with empties can scale with logorithmically increasing storage
> requirements. So if you are using a 32 byte hash and spentness bits, you
> are pretty much limited to only being able to prune 8 to 12 layers. This
> corresponds to an MMR proof length of 512 to 768 bytes.
>
Yes the point of the txo bitfield is that the constant factors are so good
that it's entirely under control. Making the memory commitments smaller
requires that the proofs be kept up to date and increases CPU requirements
and proof size. It would be entirely reasonable to make an MMRs of the
bitfield or the insertion index data structure but they aren't needed
immediately if ever. For the insertion ordering structure it's reasonable
to require full nodes to cache the top bunch of layers to make the proofs
smaller, but a very expedient approximation of that is to make them simply
remember a root per block for all the insertions contained therein, and
have full nodes remember all of those.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170402/7d4e165b/attachment.html>

2023-06-07 17:58:56

- reply

📅 Original date posted:2017-04-01
📝 Original message:On Sat, Apr 1, 2017 at 6:58 PM, praxeology_guy <
praxeology_guy at protonmail.com> wrote:
> Bram Cohen,
>
> In R&D: First its appropriate to explore all interesting ideas, and help
> each other improve their ideas. Last, when there is a deadline that needs
> to be met, we compare various options and decide on which to go with.
>
> I'm on the First step still.
>
In that case you should read my txo bitfield proposal, instead of taking my
postings yesterday as a prompt to respond to something completely unrelated.
> If you really want to push me to saying it, I'm not a fan of the Patricia
> Tree for bitcoin txos. I think its too much work for everyone to do when
> other options are available. But I'm not trying to say that your design is
> bad or wont work... I'm just personally not interested in it at this time.
>
My bitfield proposal is different from the patricia trie stuff. Also your
objection about patricia tries being 'too much work' is nonsensical because
they're quite a bit simpler than MMRs.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170401/d4aaf777/attachment.html>

2023-06-07 17:58:55

- reply

📅 Original date posted:2017-04-01
📝 Original message:On Sat, Apr 1, 2017 at 6:10 PM, praxeology_guy via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> With using the MMR data structure for txo commitments, its preferable that
> wallets only keep information pertinent to their own spendable coins. In
> previous communication we talked about how wallets could maintain the
> changing MMR proof for their old coins. Yes wallets know which of their
> own coins are spent. But with MMR proofs wallets also need to know the
> spentness status of close relatives in the MMR tree... in order to
> construct a valid MMR proof that their own coin is not spent.
>
Did you read the post that I made about the TXO bitfield yesterday? That
gives what I believe is a much better way of handling this whole issue,
allowing wallets to keep track of nothing other than the proof of position
of their txo, which never changes.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170401/797fce51/attachment.html>

2023-06-07 17:58:40

- reply

📅 Original date posted:2017-03-31
📝 Original message:Looking forward in node scaling we can envision a future in which blocks
are required to come with proofs of their validity and nodes can be run
entirely in memory and never have to hit disk. Ideally we'd like for proofs
to be able to be stored in client wallets which plan to spend their utxos
later, or at least be able to have a full node make a single not terribly
expensive disk access to form the proof which can then be passed along to
other peers.
Such proofs will probably be significantly larger than the blocks they
prove (this is merkle root stuff, not zero knowledge stuff), but if we
accept that as a given then this should be doable, although the details of
how to do it aren't obvious.
This vision can be implemented simply and efficiently by playing some games
with the semantics of the term 'proof'. A proof is a thing which convinces
someone of something. What we've discussed in the past for such proofs
mostly has to do with maintaining a hash root of everything and having
proofs lead to that. This is an extrema of complexity of the proof and
simplicity of the checker, at the expense of forcing the root to be
maintained at all times and the proof to be reasonably fresh. Some tricks
can be applied to keep that problem under control, but there's an
alternative approach where the amount of data necessary to do validation is
much larger but still entirely reasonable to keep in memory, and the sizes
of proofs and their required freshness is much smaller.
In the previous discussion on Merkle sets I commented that insertion
ordering's main practical utility may be that it allows for compression. It
turns out that a constant factor of 256 makes a big difference. Since
there's only really one bit stored for each txo (stored or not) once you
have an insertion ordering you can simply store a bitfield of all txos so
far, which is entirely reasonable to hold in memory, and can be made even
more reasonable by compactifying down the older, mostly spent portions of
it (how best to compress a bitfield while maintaining random access is an
interesting problem but entirely doable).
This approach meets all the design goals, even allowing wallets to remember
their own 'proofs', which are just proofs of insertion ordering. Those
don't even change once the risk of reorgs has passed, so they can be stored
for years without being maintained.
Proofs of insertion ordering can be made by having a canonical way of
calculating a root of position commitments for each block, and nodes
calculate those roots when evaluating the block history and store them all
in memory. A proof of position is a path to one of those roots.
I've intentionally skipped over most of the details here, because it's
probably best to have a high level discussion of this as a general approach
before getting lost in the weeds.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170331/d7516c3d/attachment.html>

2023-06-07 17:58:35

- reply

📅 Original date posted:2017-03-31
📝 Original message:On Fri, Mar 31, 2017 at 1:29 PM, praxeology_guy via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> Change the fee policy to cause all fee/byte in a block to be reduced to
> the lowest included fee/byte. Change transactions to specify how/which
> outputs get what portions of [(TX_fee/TX_length - LIFB)*TX_length].
> Transactions of course could still offer the remainder to the miner if they
> don't want to modify some of the outputs and don't want to reveal their
> change output.
>
That would have the unfortunate effect of incentivizing miners to not
completely fill blocks, because low fee marginal transactions could cost
them money.
An alternate approach would be to incentivize miners to follow transaction
fees more by reducing mining rewards, which could be done by soft forking
in a requirement that a chunk of all mining rewards be sent to an
unspendable address.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170331/0fc61bb9/attachment.html>

2023-06-07 17:58:05

- 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:57:39

- reply

📅 Original date posted:2017-03-22
📝 Original message:Some questions:
Does this require information to be added to blocks, or can it work today
on the existing format?
Does this count number of transactions or their total length? The block
limit is in bytes rather than number of transactions, but transaction
number can be a reasonable proxy if you allow for some false negatives but
want a basic sanity check.
Does this allow for proofs of length in the positive direction,
demonstrating that a block is good, or does it only serve to show that
blocks are bad? Ideally we'd like an extension to SPV protocol so light
clients require proofs of blocks not being too big, given the credible
threat of there being an extremely large-scale attack on the network of
that form.
On Wed, Mar 22, 2017 at 1:47 AM, Luke Dashjr via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Despite the generalised case of fraud proofs being likely impossible, there
> have recently been regular active proposals of miners attacking with simply
> oversized blocks in an attempt to force a hardfork. This specific attack
> can
> be proven, and reliably so, since the proof cannot be broken without also
> breaking their attempted hardfork at the same time.
>
> While ideally all users ought to use their own full node for validation
> (even
> when using a light client for their wallet), many bitcoin holders still do
> not. As such, they are likely to need protection from these attacks, to
> ensure
> they remain on the Bitcoin blockchain.
>
> I've written up a draft BIP for fraud proofs and how light clients can
> detect
> blockchains that are simply invalid due to excess size and/or weight:
>
> https://github.com/luke-jr/bips/blob/bip-sizefp/bip-sizefp.mediawiki
>
> I believe this draft is probably ready for implementation already, but if
> anyone has any idea on how it might first be improved, please feel free to
> make suggestions.
>
> Luke
> _______________________________________________
> 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/20170322/d02f0db1/attachment.html>

2023-06-07 17:57:26

- reply

📅 Original date posted:2017-03-20
📝 Original message:It's possible to switch PoW algorithms with a soft fork rather than a hard
fork. You make it so that there are two different PoWs, the old one and the
new one, and each old-style block has to reference a new-style block and
contain the exact same transactions. The new work rule is that the weighted
geometric mean of the quality of the new-style block and the old-style
block has to exceed the work threshold, with the weighting starting almost
entirely on the old-style block and shifting gradually over to the
new-style block until in the end the amount of work to generate the
old-style block is completely trivial and doesn't matter any more.
The most interesting part of the whole thing is keeping it so that the new
work limit is consistently the limiting factor on mining difficulty rather
than the old one interfering. Getting that to work right is an interesting
problem which I'm not sure how to do off the top of my head but I believe
is manageable.
Using many PoWs is a bad idea, that generally gets the worst of everything
rather than the best. There are two ways to go with a PoW, either make it
as advantaged on custom hardware as possible, which means sha3, or make it
as difficult to ASIC as possible, which at this point means cuckoo since
there's already hardware for equihash.
On Sat, Mar 18, 2017 at 9:01 AM, John Hardy via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> I’m very worried about the state of miner centralisation in Bitcoin.
>
> I always felt the centralising effects of ASIC manufacturing would resolve
> themselves once the first mover advantage had been exhausted and the
> industry had the opportunity to mature.
>
> I had always assumed initial centralisation would be harmless since miners
> have no incentive to harm the network. This does not consider the risk of a
> single entity with sufficient power and either poor, malicious or coerced
> decision making. I now believe that such centralisation poses a huge risk
> to the security of Bitcoin and preemptive action needs to be taken to
> protect the network from malicious actions by any party able to exert
> influence over a substantial portion of SHA256 hardware.
>
> Inspired by UASF, I believe we should implement a Malicious miner Reactive
> Proof of Work Additions (MR POWA).
>
> This would be a hard fork activated in response to a malicious attempt by
> a hashpower majority to introduce a contentious hard fork.
>
> The activation would occur once a fork was detected violating protocol
> (likely oversize blocks) with a majority of hashpower. The threshold and
> duration for activation would need to be carefully considered.
>
> I don’t think we should eliminate SHA256 as a hashing method and change
> POW entirely. That would be throwing the baby out with the bathwater and
> hurt the non-malicious miners who have invested in hardware, making it
> harder to gain their support.
>
> Instead I believe we should introduce multiple new proofs of work that are
> already established and proven within existing altcoin implementations. As
> an example we could add Scrypt, Ethash and Equihash. Much of the code and
> mining infrastructure already exists. Diversification of hardware (a mix of
> CPU and memory intensive methods) would also be positive for
> decentralisation. Initial difficulty could simply be an estimated portion
> of existing infrastructure.
>
> This example would mean 4 proofs of work with 40 minute block target
> difficulty for each. There could also be a rule that two different proofs
> of work must find a block before a method can start hashing again. This
> means there would only be 50% of hardware hashing at a time, and a sudden
> gain or drop in hashpower from a particular method does not dramatically
> impact the functioning of the network between difficulty adjustments. This
> also adds protection from attacks by the malicious SHA256 hashpower which
> could even be required to wait until all other methods have found a block
> before being allowed to hash again.
>
> 50% hashing time would mean that the cost of electricity in relation to
> hardware would fall by 50%, reducing some of the centralising impact of
> subsidised or inexpensive electricity in some regions over others.
>
> Such a hard fork could also, counter-intuitively, introduce a block size
> increase since while we’re hard forking it makes sense to minimise the
> number of future hard forks where possible. It could also activate SegWit
> if it hasn’t already.
>
> The beauty of this method is that it creates a huge risk to any malicious
> actor trying to abuse their position. Ideally, MR POWA would just serve as
> a deterrent and never activate.
>
> If consensus were to form around a hard fork in the future nodes would be
> able to upgrade and MR POWA, while automatically activating on non-upgraded
> nodes, would be of no economic significance: a vestigial chain immediately
> abandoned with no miner incentive.
>
> I think this would be a great way to help prevent malicious use of
> hashpower to harm the network. This is the beauty of Bitcoin: for any road
> block that emerges the economic majority can always find a way around.
>
>
> _______________________________________________
> 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/20170320/2d622ba2/attachment.html>

2023-06-07 17:57:12

- reply

📅 Original date posted:2017-03-12
📝 Original message:Shouldn't there be a FAQ about this? All the blocksize increase proposals
going back to the Bitcoin Classic have the same problems and having
repeated proposals which move the details around a bit doesn't add anything
to the discussion.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170312/1882d23d/attachment.html>

2023-06-07 17:57:08

- reply

📅 Original date posted:2017-03-08
📝 Original message:On Tue, Mar 7, 2017 at 5:55 PM, bfd--- via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> Having a commitment to a "balance" of an "address" (I assume you mean
> P2SH/P2PKH script) is extremely expensive to create and validate, does
> not scale and is not a particularly useful thing for a client to use.
>
The benefit of this sort of infrequent utxo commitment is that it would
allow a new client to download just the contents of the utxo set and not
have to get the entire blockchain history, which is much larger.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170307/82d8eea0/attachment-0001.html>

2023-06-07 17:57:07

- reply

📅 Original date posted:2017-03-07
📝 Original message:On Tue, Mar 7, 2017 at 1:28 PM, praxeology_guy via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
>
> merkle tree hashes:
> - array of "piece count" leaf hashes, hashing the balance pieces
> - array of "(child layer count + 1)/2" node hashes, hashing pairs of child
> hashes, or copying up if only one child
> - repeat ^ until the root hash is written
> ... except reverse the layer order. In other words, it should be breadth
> first.
>
A big yuck on that format. It should be something based on a patricia trie
to support incremental updates. Also if the things being stored are output
transaction + output number then those two can be hashed together to make a
consistent size identifier and be put into the merkle set format I
proposed, which is exactly the intended usage:
https://github.com/bramcohen/MerkleSet
- We could make BCP 4383 blocks, which would be 12 times per year, given
> block period was exactly 10 minutes. But since block period is not exactly
> 10 minutes, and file names generated with period 4283 are much less
> comprehensible than file names generated with period 5000... I propose
> 5000.
>
If it's of that order it should be synched up with the work difficulty
reset interval of 2016. If the format supports incremental updates it would
of course be possible to require them more frequently later.
> - Having a shorter BCP period would result in more frequent checks on UTXO
> set integrity, and permit new pruning nodes to start synching closer to the
> tip. But it may require nodes to keep more copies of the balances file to
> satisfy the same backup period, and require more background work of
> creating more balances files.
>
With a patricia based format it would be possible to make much more common
utxo commitments, possibly as often as every block only trailing by a few,
and the cost of updating wouldn't be onerous and reorgs could be handled by
simply undoing the last few transactions in the set and and then rolling
forward.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170307/79914478/attachment.html>

2023-06-07 17:56:51

- reply

📅 Original date posted:2017-03-31
📝 Original message:On Wed, Mar 1, 2017 at 2:31 PM, Peter Todd <pete at petertodd.org> wrote:
>
> A better way to present your work would have been to at least explain that
> at
> the top of the file, and perhaps even better, split the reference
> implementation and optimized implementation into two separate files. If
> you did
> this, you'd be more likely to get others to review your work.
>
I've now added explanation to the README, reorganized the files, and added
some comments:
https://github.com/bramcohen/MerkleSet
In fact, I'd suggest that for things like edge cases, you test edge cases in
> separate unit tests that explain what edge cases you're trying to catch.
>
The tests work by doing a lot of exercising on pseudorandom data, an
approach which does a good job of hitting all the lines of code and edge
cases and requiring very little updating as the implementation changes, at
the expense of it taking a while for tests to run. The advantage of very
custom unit tests is that they run almost instantly, at the cost of
requiring painstaking maintenance and missing more stuff. I've come to
favor this approach in my old age.
The proportion of code devoted to tests is more than it looks like at first
blush, because all the audit methods are just for testing.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170331/797a3461/attachment.html>

2023-06-07 17:56:50

- reply

📅 Original date posted:2017-02-28
📝 Original message:On Tue, Feb 28, 2017 at 3:24 PM, Pieter Wuille <pieter.wuille at gmail.com>
wrote:
>
> Yes, someone needs to have a lookup table from prevouts to TXO tree
> positions. But because an insertion-ordered TXO tree does not rebalance,
> that table can be maintained by wallets or service providers for just their
> own coins, instead of by every full node and miner individually for
> everyone's coins.
>
That falls apart if you want to support proofs of non-spend, which is the
point of the whole exercise
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170228/7a006446/attachment.html>

2023-06-07 17:56:36

- 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:36

- 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:34

- 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

- 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

- 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

- 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

- 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

- 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

- 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:56:27

- reply

📅 Original date posted:2017-02-23
📝 Original message:On Wed, Feb 22, 2017 at 5:26 PM, Peter Todd <pete at petertodd.org> wrote:
>
> A commitment scheme needs only have the property that it's not feasible to
> find
> two messages m1 and m2 that map to the same commitment; it is *not*
> required
> that it be difficult to find m given the commitment. Equally, it's not
> required
> that commitments always be the same size.
> So a perfectly reasonable thing to do is design your scheme such that the
> commitment to short messages is the message itself! This adds just a
> single bit
> of data to the minimum serialized size(1) of the commitment, and in
> situations
> where sub-digest-sized messages are common, may overall be a savings.
>
Yes I'm basically doing that but to make things be all the same size I'm
including the bit inline, sacrificing one bit of security. Actually I'm
sacrificing two bits of security, to allow for four values: terminal,
middle, empty, and invalid. Invalid is used internally when a value has yet
to be calculated lazily and in proofs to mean 'this is a middle node but
the children are not included'. One effect of this is that the root of a
set containing a single value is just that value with the two high order
bits of the first byte reset to the appropriate value.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170222/10b8cd50/attachment.html>

2023-06-07 17:56:26

- reply

📅 Original date posted:2017-02-21
📝 Original message:Here is a Merkle set data structure, whose format may be useful for utxo
commitments in Bitcoin blocks. It may also be useful for any other
distributed computation which wants an audit trail:
https://github.com/bramcohen/MerkleSet
This is a fairly straightforward Patricia Trie, with a simple format and a
simple reference implementation plus a performance optimized non-reference
implementation which is much more cache coherent. It will need to be ported
to C and be properly turned before the potential performance gains can be
realized though.
The clever things which affect the format spec are:
It uses blake2s as the internal hash function. This is the fastest hash
function to use on 512 bit inputs because blake2b uses a 1024 bit block
size. It might make sense to use a hypothetical variant of blake which is
optimized for 64 bits with a 512 bit block size, but that hasn't been
specified. Sha256 would take advantage of hardware acceleration, but that
isn't available everywhere.
Two bits of security are sacrificed to include metadata inline which halves
the CPU cost of hashing.
When one side of a node is empty and the other contains exactly two things
the secure hash of the child is adopted verbatim rather than rehashing it.
This roughly halves the amount of hashing done, and makes it more resistant
to malicious data, and cleans up some implementation details, at the cost
of some extra complexity.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170221/a52234ed/attachment.html>

2023-06-07 17:54:52

- 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

- 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

- 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>

2023-06-07 17:51:56

- reply

📅 Original date posted:2016-07-15
📝 Original message:On Sat, Jun 18, 2016 at 4:01 PM, Peter Todd <pete at petertodd.org> wrote:
>
>
Have you seen how BLAKE2 omits padding when the data to be hashed happens
> to be
> exactly one block in size? It's significantly faster than SHA256, and
> that's a
> standard part of the algorithm already.
>
That's very convenient! I didn't know it, but had 'look up how blake2 does
padding' in my list of stuff to do. I'm leaning heavily towards using
blake2b at this point, at least for internal hashing.
>
> > At the root there's a branch block. It consists of all nodes up to some
> > fixed depth - let's say 12 - with that depth set so that it roughly fits
> > within a single memory page. Branch blocks are arranged with the nodes in
> > fixed position defined by the prefix they correspond to, and the
> terminals
> > have outpointers to other blocks. Because they're all clustered
> together, a
> > lookup or update will only require a single
>
> A single....?
>
Okay, I've figured out the root cause of general confusion here. It's
mostly my fault.
There are a few different media on which data can be stored, with different
properties in terms of how long it takes to retrieve data from them, and
how much of a readahead they typically have. I was misreading the l2 cache
size as the main memory readahead amount, which is... probably wrong? The
readahead properties of memory aren't well documented and apparently vary a
lot. On SSDs it typically pulls down a kilobyte at once and they call them
pages, hence my use of that term above. But since my real point is that my
implementation should act as a silver bullet which can have acceptable
performance even on extremely bad devices, I'll give an analysis of how
well it works when everything is stored on a regular spinning hard drive.
Let's say you're storing 100 million items, which will fit within 10
gigabytes. If you set the block depths to about 10 bits they'll be about
32K, and if you set the size of leaf blocks to be about the same then
memory efficiency will be good because the leaf blocks will store twigs of
about 2^7 in size while having 2^10 space so they'll fit reasonably. Almost
everything will be three blocks from root, so updates will generally
require two disk seeks (plus one more for a write but those are generally
faster because they get batched.)
For latency numbers, I'm going off these:
https://gist.github.com/jboner/2841832
If the blockchain is very full of simple transactions and a disk seek takes
15 milliseconds, then going with the assumption that a block is about 600
seconds and the blockchain can handle 4 transactions per second and each of
them is 3 updates (one utxo spent plus two new ones created) that's 15 *
600 * 4 * 3 * 2 milliseconds per block, or about 200 seconds per block, so
if the uxto roots trail by a few blocks even a ludicrously underpowered
node could keep up.
On an SSD keeping up is completely trivial, the problem becomes one of how
quickly you can validate an entire blockchain history. There a read takes
about 0.15 milliseconds and you have to do 5 of them instead of 2 because
the natural memory block size is 4k, so it's about 1 millisecond per
update, or 600 * 4 * 3 total time for each block, which is about 7 seconds.
That's large enough that making the utxo root trail by two blocks is still
a good idea, but small enough that it isn't a big factor in the cost of
running a node. It's enough that validating a complete block history might
take a while though, and even validating just the last year would take a
few days. This is very conservative and it's assuming that *everything* is
kept on an SSD though. If the numbers work better and a few layers are kept
in regular memory validating a whole year of history might only take a few
hours.
Hopefully that all makes a fairly good case that raw merkle tree utxo root
trailing by a few blocks is a viable strategy. The data structures in the
MMR proposal are fairly complicated and the analysis of them talks in
somewhat vague terms about things being fast and slow. A similar analysis
of the MMR proposal specifying storage media and expectations of latency
numbers would clarify the reasoning a lot.
(By the way, sorry for the slow response - I got preempted by a bunch of
other work duties.)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20160715/1202d694/attachment.html>

2023-06-07 17:51:10

- reply

📅 Original date posted:2016-06-18
📝 Original message:On Wed, Jun 15, 2016 at 5:10 PM, Peter Todd <pete at petertodd.org> wrote:
> On Tue, Jun 14, 2016 at 05:14:23PM -0700, Bram Cohen via bitcoin-dev wrote:
>
> > The fundamental approach to handling the latency problem is to have the
> > utxo commitments trail a bit. Computing utxo commitments takes a certain
> > amount of time, too much to hold up block propagation but still hopefully
> > vastly less than the average amount of time between blocks. Trailing by a
> > single block is probably a bad idea because you sometimes get blocks back
> > to back, but you never get blocks back to back to back to back. Having
> the
> > utxo set be trailing by a fixed amount - five blocks is probably
> excessive
> > - would do a perfectly good job of keeping latency from every becoming an
> > issue. Smaller commitments for the utxos added and removed in each block
> > alone could be added without any significant performance penalty. That
> way
> > all blocks would have sufficient commitments for a completely up to date
> > proofs of inclusion and exclusion. This is not a controversial approach.
>
> Agreed - regardless of approach adding latency to commitment calculations
> of
> all kinds is something I think we all agree can work in principle, although
> obviously it should be a last resort technique when optimization fails.
>
An important point: Adding latency to utxo commitments does not imply
latency to proofs of inclusion and exclusion! If roots of what's added and
deleted in each block are added as well, then a proof of inclusion can be
done by having a proof of inclusion of the trailing utxo set followed by a
proof of exclusion from all the following deletion sets, or a proof of
inclusion in one of the single block addition sets followed by proofs of
exclusion from all the more recent deletion sets. Likewise a proof of
exclusion can be a proof of exclusion from the utxo set followed by proofs
of exclusion from all the more recent addition sets or a single proof of
inclusion in a recent deletion set.
This does make proofs larger (except in the case of recent deletions and
maybe recent additions) and adds complexity, so it shouldn't be done unless
necessary. But validation before block propagation needs to be extremely
fast, so for utxo roots this trick is probably both necessary and
sufficient.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20160617/1843b319/attachment-0001.html>

2023-06-07 17:51:08

- reply

📅 Original date posted:2016-06-17
📝 Original message:On Thu, Jun 16, 2016 at 9:34 PM, Peter Todd <pete at petertodd.org> wrote:
> So above you said that in merbinner trees each node "hash[es] in a record
> of
> its depth" That's actually incorrect: each node commits to the prefix that
> all
> keys below that level start with, not just the depth.
I considered a similar trick at the implementation rather than the
definition level: A node doesn't have to store the prefix which is implicit
in its position. That would create a fair number of headaches though,
because I'm using fixed size stuff in important ways, and it could at most
save about 10% of memory, so it goes into the 'maybe later' bucket.
>
> This means that in merbinner trees, cases where multiple keys share parts
> of
> the same prefix are handled efficiently, without introducing extra levels
> unnecessarily; there's no need for the ONLY0/1 nodes as the children of an
> inner node will always be on different sides.
>
> When keys are randomly distributed, this isn't a big deal; OTOH against
> attackers who are choosing keys, e.g. by grinding hashes, merbinner trees
> always have maximum depths in proportion to log2(n) of the actual number of
> items in the tree. Grinding is particularly annoying to deal with due to
> the
> birthday attack: creating a ground prefix 64 bits long only takes 32 bits
> worth
> of work.
>
Yes an attacker can force the tree to be deeper in places, but it's
mitigated in several ways: (1) The way I'm using memory it won't cause a
whole new block to be allocated, it will just force log(attack strength) -
log(n) nodes to be used (2) logarithmic growth being what it is that isn't
such a big amount (3) With the special casing of TERMBOTH an attacker needs
three things with the same prefix to pull off an attack rather than two,
which is quite a bit harder to pull off.
That said, it wouldn't be all that hard to change how the hashing function
works to do a single hash for a whole series of ONLY in a row instead of a
new one at every level, which would make the attacker only able to force
extra memory usage instead of extra CPU, but this is a slightly annoying
thing to write to stop a fairly lame attack, so I'm at least not doing it
for my initial implementation. I could likely be convinced that it's worth
doing before an actual release though. There's another implementation trick
to do the same thing for memory usage, which is much more in the 'do later'
category because it doesn't involve changing the format and hence it can be
put off.
> In particular, case #2 handles your leaf node optimizations generically,
> without special cases and additional complexity. It'd also be a better way
> to
> do the ONLY0/1 cases, as if the "nothing on this side" symbol is a single
> byte,
> each additional colliding level would simply extend the commitment without
> hashing. In short, you'd have nearly the same level of optimization even
> if at
> the cryptography level your tree consists of only leaves, inner nodes, and
> nil.
>
I'm taking pains to make all the hashing be of fixed-size things, so that a
non-padding variant of a secure hashing algorithm can be used. The chains
of ONLY thing above would force a special exception to that, which can be
done but is annoying. Making things smaller than a single block (64 bytes)
won't speed up hashing time, and making things a single byte longer than
that doubles it.
> Another advantage of variable sized commitments is that it can help make
> clear
> to users when it's possible to brute force the message behind the
> commitment.
> For instance, digest from a hashed four byte integer can be trivially
> reversed
> by just trying all combinations. Equally, if that integer is concatenated
> with
> a 32 byte digest that the attacker knows, the value of the integer can be
> brute
> forced.
>
I'm hashing all strings before inserting to get them to be a fixed size and
avoid a few different attacks. In Bitcoin most of the strings added are
longer than that so it's a form of compression. A custom hash function
could be used which 'hashes' very short strings by repeating them verbatim
could be used, but seems like not such a hot idea. I'm making extensive use
of things being fixed size everywhere, which improves performance in a lot
of ways.
> > > Technically even a patricia trie utxo commitment can have sub-1 cache
> > > > misses per update if some of the updates in a single block are close
> to
> > > > each other in memory. I think I can get practical Bitcoin updates
> down
> > > to a
> > > > little bit less than one l2 cache miss per update, but not a lot
> less.
> > >
> > > I'm very confused as to why you think that's possible. When you say
> > > "practical
> > > Bitcoin updates", what exactly is the data structure you're proposing
> to
> > > update? How is it indexed?
>
I'll re-answer this because I did a terrible job before. The entire data
structure consists of nodes which contain a metadata byte (TERM0, ONLY1,
etc.) followed by fixes size secure hashes, and (in some cases) pointers to
where the children are. The secure hashes in parent nodes are found by
hashing their children verbatim (or the stored string in the case of a
TERM). This is very conventional. All of the cleverness is in where in
memory these nodes are stored so that tracing down the tree causes very few
cache misses.
(The alternate approach is to have each node store its own hash rather than
that be stored by the parent. That approach means that when you're
recalculating you have to look up siblings which doubles the number of
cache misses. Not such a hot idea.)
At the root there's a branch block. It consists of all nodes up to some
fixed depth - let's say 12 - with that depth set so that it roughly fits
within a single memory page. Branch blocks are arranged with the nodes in
fixed position defined by the prefix they correspond to, and the terminals
have outpointers to other blocks. Because they're all clustered together, a
lookup or update will only require a single
Below the root block are other branch blocks. Each of them has a fixed 12
bit prefix it is responsible for. When doing a lookup a second cache miss
will be hit for levels 13-24, because those are all clustered in the same
branch block.
Below the second level of root block (at Bitcoin utxo set scale - this
varies based on how much is stored) there are leaf blocks. A leaf block
consists of nodes with outpointers to its own children which must be within
the same leaf block. All entry points into a leaf block are from the same
branch block, and the leaf block has no out pointers to other blocks. When
a leaf block overflows the entry point into it which overflowed is moved
into the active leaf for that branch, and if that's full a new one is
allocated. There's some subtlety to exactly how this is done, but I've
gotten everything down to simple expedient tricks with straightforward
implementations. The thing which matters for now is that there's only a
single cache miss for each leaf node, because they also fit in a page.
So at Bitcoin scale there will probably only be 3 cache misses for a
lookup, and that's a worst case scenario. The first one is probably always
warm, bringing it down to 2, and if you do a bunch in sorted order they'll
probably hit the same second level branches repeatedly bringing it down to
1, and might even average less than that if there are enough that the leaf
block has multiple things being accessed.
(These same tricks can be applied to merbinner tree implementation as well,
although that would be a bit less parsimonious with memory, by a small
constant factor.)
> Anyway hashing is pretty slow. The very fast BLAKE2 is about 3 cycles/byte
> (SHA256 is about 15 cycles/byte) so hashing that same data would take
> around
> 200 cycles, and probably quite a bit more in practice due to overheads
> from our
> short message lengths; fetching a cache line from DRAM only takes about
> 1,000
> cycles. I'd guess that once other overheads are taken into account, even
> if you
> could eliminate L2/L3 cache-misses it wouldn't be much of an improvement.
>
Those numbers actually back up my claims about performance. If you're doing
a single update and recalculating the root afterwards, then the amount of
rehashing to be done is about 30 levels deep times 64 bytes per thing
hashed times 15 cycles per byte then it's about 28,800 cycles of hashing.
If you have a naive radix tree implementation which hits a cache miss at
every level then that's 30,000 cycles, which is about half the performance
time, certainly worth optimizing. If instead of sha256 you use blake2
(Which sounds like a very good idea!) then hashing for an update will be
about 5760 cycles and performance will be completely dominated by cache
misses. If a more cache coherent implementation is used, then the cost of
cache misses will be 3000 cycles, which will be a non-factor with sha256
and a significant but not dominating one with blake2.
It's reasonable to interpret those numbers as saying that blake2 and cache
coherent implementation are both clearly worth it (probably necessary for
real adoption) and that an amortized binary radix tree is tempting but not
worth it.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20160617/88e3169a/attachment.html>

2023-06-07 17:51:07

- reply

📅 Original date posted:2016-06-16
📝 Original message:On Wed, Jun 15, 2016 at 8:26 PM, Peter Todd <pete at petertodd.org> wrote:
> >
> > What do you mean by TXO commitments? If you mean that it only records
> > insertions rather than deletions, then that can do many of the same
> proofs
> > but has no way of proving that something is currently in the UTXO set,
> > which is functionality I'd like to provide.
>
> I think you need to re-read my original post on TXO commitments,
> specifically
> where I say:
>
> # TXO Commitments
>
> A merkle tree committing to the state of __all transaction outputs,
> both spent
> and unspent__, we can provide a method of compactly proving the
> current state of
> an output.
>
>
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-May/012715.html
Okay, clearly my assumptions about the parts of that post I didn't read
carefully were way off. I'll have to look through it carefully to be able
to make coherent apples to apples comparisons.
> I'm worried that once there's real transaction fees everyone might stop
> > consolidating dust and the set of unspent transactions might grow without
> > bound as well, but that's a topic for another day.
>
> Ok, but then if you're concerned about that risk, why introduce a data
> structure - the STXO set - that's _guaranteed_ to grow without bound?
>
I'm not proposing STXO set commitments either. My point was that there
should be incentives for collecting dust. That has nothing to do with this
thread though and should be discussed separately (also I don't feel like
discussing it because I don't have a good proposal).
> > What I'm making is a patricia trie. Its byte level definition is very
> > similar to the one in your MMR codebase.
>
> Which codebase exactly? I have both a insertion-ordered list (MMR) and a
> key:value mapping (referred to as a "merbinner tree" in the codebase) in
> the
> proofchains codebase. They're very different data structures.
>
I'm talking about your merbinner trees. I read through that part of your
codebase carefully and got the impression that the MMR tree section used it
as a building block.
> > The main differences to your patricia trie are the non-padding sha256 and
> > that each level doesn't hash in a record of its depth and the usage of
> > ONLY0 and ONLY1.
>
> I'm rather confused, as the above sounds nothing like what I've
> implemented,
> which only has leaf nodes, inner nodes, and the special empty node
> singleton,
> for both the MMR and merbinner trees.
>
It's quite a bit like merbinner trees. I've basically taken the leaf nodes
and smushed them into the inner nodes above them, thus saving a hashing
operation and some memory. They're both binary radix trees.
> Technically even a patricia trie utxo commitment can have sub-1 cache
> > misses per update if some of the updates in a single block are close to
> > each other in memory. I think I can get practical Bitcoin updates down
> to a
> > little bit less than one l2 cache miss per update, but not a lot less.
>
> I'm very confused as to why you think that's possible. When you say
> "practical
> Bitcoin updates", what exactly is the data structure you're proposing to
> update? How is it indexed?
My calculations are: a Bitcoin block contains about 2000 updates. The l2
cache is about 256 kilobytes, and if an update is about 32 bytes times two
for the parents, grandparents, etc. then an l2 cache can contain about 4000
values. If the current utxo size is about 2000 * 4000 = 8,000,000 in size
then about half the pages which contain a transaction will contain a second
one. I think the utxo set is currently about an order of magnitude greater
than that, so the number of such collisions will be fairly mall, hence my
'less than one but not a lot less' comment.
As for how it's indexed, at a crypto definition level it's just a binary
radix tree. In terms of how it's indexed in memory, that involves some
optimizations to avoid cache misses. Memory is allocated into blocks of
about the size of an 12 cache (or maybe an l1 cache, it will require some
testing and optimization). Blocks are either branch blocks, which keep
everything in fixed positions, or leaf blocks, which contain fixed size
entries for nodes plus indexes within the same leaf block of their
children. Branch blocks can have many children which can be either branch
blocks or leaf blocks, but typically are either all branch blocks or all
leaf blocks. Branch blocks always have exactly one parent. Leaf blocks
always have all their inputs come from a single branch block, but there can
be multiple ones of those. When a branch block overflows it first tries to
put stuff into the last leaf block it used, and if there's no more room it
allocates a new one. It's fairly common for branches to have just a few
leaf children, but they also could have a lot, depending on whether the
base 2 log of the number of things currently in the set modulo the number
levels in a branch is a small number.
Usually when an update is done it consists of first checking the
appropriate output of the root block (it's jumped to directly to avoid
unnecessary memory lookups. If there's nothing there the algorithm will
walk back until it finds something.) That leads directly to (usually)
another branch whose output is jumped to directly again. At Bitcoin utxo
set sizes that will usually lead to a leaf block, which is then walked down
manually to find the actual terminal node, which is then updated, and the
parent, grandparent, etc. is then marked invalid until something which was
already marked invalid is hit, and it exits. Calculation of hash values is
done lazily.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20160616/e266893c/attachment.html>

2023-06-07 17:51:06

- reply

📅 Original date posted:2016-06-15
📝 Original message:On Wed, Jun 15, 2016 at 5:10 PM, Peter Todd <pete at petertodd.org> wrote:
> On Tue, Jun 14, 2016 at 05:14:23PM -0700, Bram Cohen via bitcoin-dev wrote:
> >
> > Peter proposes that there should be both UTXO and STXO commitments, and
>
> No, that's incorrect - I'm only proposing TXO commitments, not UTXO nor
> STXO
> commitments.
>
What do you mean by TXO commitments? If you mean that it only records
insertions rather than deletions, then that can do many of the same proofs
but has no way of proving that something is currently in the UTXO set,
which is functionality I'd like to provide.
When I say 'merkle tree' what I mean is a patricia trie. What I assume is
meant by a merkle mountain range is a series of patricia tries of
decreasing size each of which is an addition to the previous one, and
they're periodically consolidated into larger tries so the old ones can go
away. This data structure has the nice property that it's both in sorted
order and has less than one cache miss per operation because the
consolidation operations can be batched and done linearly. There are a
number of different things you could be describing if I misunderstood.
> I'm not proposing STXO commitments precisely because the set of _spent_
> transactions grows without bound.
I'm worried that once there's real transaction fees everyone might stop
consolidating dust and the set of unspent transactions might grow without
bound as well, but that's a topic for another day.
> > Now I'm going to go out on a limb. My thesis is that usage of a mountain
> > range is unnecessary, and that a merkle tree in the raw can be made
> > serviceable by sprinkling magic pixie dust on the performance problem.
>
> It'd help if you specified exactly what type of merkle tree you're talking
> about here; remember that the certificate transparency RFC appears to have
> reinvented merkle mountain ranges, and they call them "merkle trees".
> Bitcoin
> meanwhile uses a so-called "merkle tree" that's broken, and Zcash uses a
> partially filled fixed-sized perfect tree.
>
What I'm making is a patricia trie. Its byte level definition is very
similar to the one in your MMR codebase.
Each level of the tree has a single metadata byte and followed by two
hashes. The hashes are truncated by one byte and the hash function is a
non-padding variant of sha256 (right now it's just using regular sha256,
but that's a nice optimization which allows everything to fit in a single
block).
The possible metadata values are: TERM0, TERM1, TERMBOTH, ONLY0, ONLY1,
MIDDLE. They mean:
TERM0, TERM1: There is a single thing in the tree on the specified side.
The thing hashed on that side is that thing verbatim. The other side has
more than one thing and the hash of it is the root of everything below.
TERMBOTH: There are exactly two things below and they're included inline.
Note that two things is a special case, if there are more you sometimes
have ONLY0 or ONLY1.
ONLY0, ONLY1: There are more than two things below and they're all on the
same side. This makes proofs of inclusion and exclusion simpler, and makes
some implementation details easier, for example there's always something at
every level with perfect memory positioning. It doesn't cause much extra
memory usage because of the TERMBOTH exception for exactly two things.
MIDDLE: There two or more things on both sides.
There's also a SINGLETON special case for a tree which contains only one
thing, and an EMPTY special value for tree which doesn't contain anything.
The main differences to your patricia trie are the non-padding sha256 and
that each level doesn't hash in a record of its depth and the usage of
ONLY0 and ONLY1.
>
> > There are two causes of performance problems for merkle trees: hashing
> > operations and memory cache misses. For hashing functions, the difference
> > between a mountain range and a straight merkle tree is roughly that in a
> > mountain range there's one operation for each new update times the number
> > of times that thing will get merged into larger hills. If there are fewer
> > levels of hills the number of operations is less but the expense of proof
> > of inclusion will be larger. For raw merkle trees the number of
> operations
> > per thing added is the log base 2 of the number of levels in the tree,
> > minus the log base 2 of the number of things added at once since you can
> do
> > lazy evaluation. For practical Bitcoin there are (very roughly) a million
> > things stored, or 20 levels, and there are (even more roughly) about a
> > thousand things stored per block, so each thing forces about 20 - 10 = 10
> > operations. If you follow the fairly reasonable guideline of mountain
> range
> > hills go up by factors of four, you instead have 20/2 = 10 operations per
> > thing added amortized. Depending on details this comparison can go either
> > way but it's roughly a wash and the complexity of a mountain range is
> > clearly not worth it at least from the point of view of CPU costs.
>
> I'm having a hard time understanding this paragraph; could you explain
> what you
> think is happening when things are "merged into larger hills"?
>
I'm talking about the recalculation of mountain tips, assuming we're on the
same page about what 'MMR' means.
> As UTXO/STXO/TXO sets are all enormously larger than L1/L2 cache, it's
> impossible to get CPU cache misses below one for update operations. The
> closest
> thing to an exception is MMR's, which due to their insertion-ordering could
> have good cache locality for appends, in the sense that the mountain tips
> required to recalculate the MMR tip digest will already be in cache from
> the
> previous append. But that's not sufficient, as you also need to modify old
> TXO's further back in the tree to mark them as spent - that data is going
> to be
> far larger than L1/L2 cache.
>
This makes me think we're talking about subtly different things for MMRs.
The ones I described above have sub-1 cache miss per update due to the
amortized merging together of old mountains.
Technically even a patricia trie utxo commitment can have sub-1 cache
misses per update if some of the updates in a single block are close to
each other in memory. I think I can get practical Bitcoin updates down to a
little bit less than one l2 cache miss per update, but not a lot less.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20160615/62646c88/attachment-0001.html>

2023-06-07 17:51:05

- reply

📅 Original date posted:2016-06-14
📝 Original message:This is in response to Peter Todd's proposal for Merkle Mountain Range
commitments in blocks:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-May/012715.html
I'm in strong agreement that there's a compelling need to put UTXO
commitments in blocks, and that the big barrier to getting it done is
performance, particularly latency. But I have strong disagreements (or
perhaps the right word is skepticism) about the details.
Peter proposes that there should be both UTXO and STXO commitments, and
they should be based on Merkle Mountain Ranges based on Patricia Tries. My
first big disagreement is about the need for STXO commitments. I think
they're unnecessary and a performance problem. The STXO set is much larger
than the utxo set and requires much more memory and horespower to maintain.
Most if not all of its functionality can in practice be done using the utxo
set. Almost anything accepting proofs of inclusion and exclusion will have
a complete history of block headers, so to prove inclusion in the stxo set
you can use a utxo proof of inclusion in the past and a proof of exclusion
for the most recent block. In the case of a txo which has never been
included at all, it's generally possible to show that an ancestor of the
txo in question was at one point included but that an incompatible
descendant of it (or the ancestor itself) is part of the current utxo set.
Generating these sorts of proofs efficiently can for some applications
require a complete STXO set, but that can done with a non-merkle set,
getting the vastly better performance of an ordinary non-cryptographic
hashtable.
The fundamental approach to handling the latency problem is to have the
utxo commitments trail a bit. Computing utxo commitments takes a certain
amount of time, too much to hold up block propagation but still hopefully
vastly less than the average amount of time between blocks. Trailing by a
single block is probably a bad idea because you sometimes get blocks back
to back, but you never get blocks back to back to back to back. Having the
utxo set be trailing by a fixed amount - five blocks is probably excessive
- would do a perfectly good job of keeping latency from every becoming an
issue. Smaller commitments for the utxos added and removed in each block
alone could be added without any significant performance penalty. That way
all blocks would have sufficient commitments for a completely up to date
proofs of inclusion and exclusion. This is not a controversial approach.
Now I'm going to go out on a limb. My thesis is that usage of a mountain
range is unnecessary, and that a merkle tree in the raw can be made
serviceable by sprinkling magic pixie dust on the performance problem.
There are two causes of performance problems for merkle trees: hashing
operations and memory cache misses. For hashing functions, the difference
between a mountain range and a straight merkle tree is roughly that in a
mountain range there's one operation for each new update times the number
of times that thing will get merged into larger hills. If there are fewer
levels of hills the number of operations is less but the expense of proof
of inclusion will be larger. For raw merkle trees the number of operations
per thing added is the log base 2 of the number of levels in the tree,
minus the log base 2 of the number of things added at once since you can do
lazy evaluation. For practical Bitcoin there are (very roughly) a million
things stored, or 20 levels, and there are (even more roughly) about a
thousand things stored per block, so each thing forces about 20 - 10 = 10
operations. If you follow the fairly reasonable guideline of mountain range
hills go up by factors of four, you instead have 20/2 = 10 operations per
thing added amortized. Depending on details this comparison can go either
way but it's roughly a wash and the complexity of a mountain range is
clearly not worth it at least from the point of view of CPU costs.
But CPU costs aren't the main performance problem in merkle trees. The
biggest issues is cache misses, specifically l1 and l2 cache misses. These
tend to take a long time to do, resulting in the CPU spending most of its
time sitting around doing nothing. A naive tree implementation is pretty
much the worst thing you can possibly build from a cache miss standpoint,
and its performance will be completely unacceptable. Mountain ranges do a
fabulous job of fixing this problem, because all their updates are merges
so the metrics are more like cache misses per block instead of cache misses
per transaction.
The magic pixie dust I mentioned earlier involves a bunch of subtle
implementation details to keep cache coherence down which should get the
number of cache misses per transaction down under one, at which point it
probably isn't a bottleneck any more. There is an implementation in the
works here:
https://github.com/bramcohen/MerkleSet
This implementation isn't finished yet! I'm almost there, and I'm
definitely feeling time pressure now. I've spent quite a lot of time on
this, mostly because of a bunch of technical reworkings which proved
necessary. This is the last time I ever write a database for kicks. But
this implementation is good on all important dimensions, including:
Lazy root calculation
Few l1 and l2 cache misses
Small proofs of inclusion/exclusion
Reasonably simple implementation
Reasonably efficient in memory
Reasonable defense against malicious insertion attacks
There is a bit of a false dichotomy with the mountain range approach.
Mountain ranges need underlying merkle trees, and mine are semantically
nearly identically to Peter's. This is not a coincidence - I adopted
patricia tries at his suggestion. There are a bunch of small changes which
allow a more efficient implementation. I believe that my underlying merkle
tree is unambiguously superior in every way, but the question of whether a
mountain range is worth it is one which can only be answered empirically,
and that requires a bunch of implementation work to be done, starting with
me finishing my merkle tree implementation and then somebody porting it to
C and optimizing it. The Python version has details which are ridiculous
and only make sense once it gets ported, and even under the best of
conditions Python performance is not strongly indicative of C performance.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20160614/a1bc30c1/attachment.html>

2023-06-07 17:44:19

- reply

📅 Original date posted:2015-11-06
📝 Original message:(My apologies for a 'drive-by' posting. I'm not subscribed to this mailing
list but this post may be of interest here. If you'd like to make sure I
see a response send it to me directly. This post was originally posted to
the web at
https://medium.com/@bramcohen/how-wallets-can-handle-transaction-fees-ff5d020d14fb
)
Since transaction fees are a good thing (see
https://medium.com/@bramcohen/bitcoin-s-ironic-crisis-32226a85e39f ), that
brings up the question: How should wallets handle them? This essay is an
expansion of my talk at the bitcoin scaling conference (see
https://www.youtube.com/watch?v=iKDC2DpzNbw&t=13m17s and
https://scalingbitcoin.org/montreal2015/presentations/Day1/11-bram_wallet_fees.pdf
).
Ground Rules
To answer this question we first need to lay down some ground rules of what
we’re trying to solve. We’ll focus on trying to solve the problem for
consumer wallets only. We’ll be ignoring microchannels, which dramatically
reduce the number of transactions used but still have to put some on the
blockchain. We’ll also be assuming that full replace by fee is in effect
(see
https://medium.com/@bramcohen/the-inevitable-demise-of-unconfirmed-bitcoin-transactions-8b5f66a44a35
)
because the best solution uses that fairly aggressively.
What should transaction fees be?
Before figuring out how wallets should calculate transaction fees, we first
need to know what transaction fees should be. The obvious solution to that
question is straightforward: It should be determined by supply and demand.
The price is set at the point where the supply and demand curves meet. But
supply and demand curves, while mostly accurate, are a little too simple of
a model to use, because they don’t take into account time. In the real
world, the supply of space for transactions is extremely noisy, because
more becomes available (and has to be immediately consumed or it’s lost
forever) every time a block is minted, and block minting is an
intentionally random process, that randomness being essential for
consensus. Demand is random and cyclical. Random because each transaction
is generated individually so the total amount is noisy (although that
averages out to be somewhat smooth at scale) and has both daily and weekly
cycles, with more transactions done during the day than at night.
What all these result in is that there should be a reward for patience. If
you want or need to get your transaction in quicker you should have to pay
on average a higher fee, and if you’re willing to wait longer it should on
average cost less. Inevitably this will result in transactions taking on
average longer than one block to go through, but it doesn’t require it of
everyone. Those who wish to offer high fees to be sure of getting into the
very next block are free to do so, but if everyone were to do that the
system would fall apart.
What should the wallet user interface be?
Ideally transaction fees would be handled in a way which didn’t require
changes to a wallet’s user interface at all. Unfortunately that isn’t
possible. At a minimum it’s necessary to have a maximum fee which the user
is willing to spend in order to make a transaction go through, which of
course means that some transactions will fail because they aren’t willing
to pay enough, which is the whole point of having transaction fees in the
first place.
Because transaction fees should be lower for people willing to wait longer,
there should be some kind of patience parameter as well. The simplest form
of this is an amount of time which the wallet will spend trying to make the
transaction go through before giving up (Technically it may make sense to
specify block height instead of wall clock time, but that’s close enough to
not change anything meaningful). This results in fairly understandable
concepts of a transaction being ‘pending’ and ‘failed’ which happen at
predictable times.
Transactions eventually getting into a ‘failed’ state instead of going into
permanent limbo is an important part of the wallet fee user experience.
Unfortunately right now the only way to make sure that a transaction is
permanently failed is to spend its input on something else, but that
requires spending a transaction fee on the canceling transaction, which of
course would be just as big as the fee you weren’t willing to spend to make
the real transaction go through in the first place.
What’s needed is a protocol extension so a transaction can make it
impossible for it to be committed once a certain block height has been
reached. The current lack of such an extension is somewhat intentional
because there are significant potential problems with transactions going
bad because a block reorganization happened and some previously accepted
transactions can’t ever be recommitted because their max block height got
surpassed. To combat this, when a transaction with a max block height gets
committed near its cutoff it’s necessary to wait a longer than usual number
of blocks to be sure that it’s safe (I’m intentionally not giving specific
numbers here, some developers have suggested extremely conservative
values). This waiting is annoying but should only apply in the edge case of
failed transactions and is straightforward to implement. The really big
problem is that given the way Bitcoin works today it’s very hard to add
this sort of extension. If any backwards-incompatible change to Bitcoin is
done, it would be a very good idea to use that opportunity to improve
Bitcoin’s extension mechanisms in general and this one in particular.
What information to use
The most obvious piece of information to use for setting transaction fees
is past transaction fees from the last few blocks. This has a number of
problems. If the fee rate goes high, it can get stuck there and take a
while to come down, if ever, even though the equilibrium price should be
lower. A telltale sign of this is high fee blocks which aren’t full, but
it’s trivial for miners to get around that by padding their blocks with
self-paying transactions. To some extent this sort of monopoly pricing is
inherent, but normally it would require a cabal of most miners to pull it
off, because any one miner can make more money in the short term by
accepting every transaction they can instead of restricting the supply of
available transaction space. If transaction fees are sticky, a large but
still minority miner can make money for themselves even in the short term
by artificially pumping fees in one of their blocks because fees will
probably still be high by the time of their next block.
Past fees also create problems for SPV clients, who have to trust the full
nodes they connect to to report past fees accurately. That could be
mitigated by making an extension to the block format to, for example,
report what the minimum fee per bytes paid in this block is in the headers.
It isn’t clear exactly what that extension should do though. Maybe you want
to know the minimum, or the median, or the 25th percentile, or all of the
above. It’s also possible for miners to game the system by making a bunch
of full nodes which only report blocks which are a few back when fees have
recently dropped. There are already some incentives to do that sort of bad
behavior, and it can be mitigated by having SPV clients connect to more
full nodes than they currently do and always go with the max work, but SPV
clients don’t currently do that properly, and it’s unfortunate to create
more incentives for bad behavior.
Another potential source of information for transaction fees is currently
pending transactions in the network. This has a whole lot of problems. It’s
extremely noisy, much more so than regular transaction fees, because (a)
sometimes a backlog of transactions builds up if no blocks happen to have
happened in a while (b) sometimes there aren’t many transactions if a bunch
of blocks went through quickly, and (c) in the future full nodes can and
should have a policy of only forwarding transactions which are likely to
get accepted sometime soon given the other transactions in their pools.
Mempool is also trivially gameable, in exactly the same way as the last few
blocks are gameable, but worse: A miner who wishes to increase fees can run
a whole lot of full nodes and report much higher fees than are really
happening. Unlike with fee reporting in blocks, there’s no way for SPV
clients to audit this properly, even with a protocol extension, and it’s
possible for full nodes to lie in a much more precise and targetted manner.
Creating such a strong incentive for such a trivial and potentially
lucrative attack seems like a very bad idea.
A wallet’s best information to use when setting price are the things which
can be absolutely verified locally: The amount it’s hand to pay in the
past, the current time, how much it’s willing to pay by when. All of these
have unambiguous meanings, precise mathematical values, and no way for
anybody else to game them. A wallet can start at a minimum value, and every
time a new block is minted which doesn’t accept its transaction increase
its fee a little, until finally reaching its maximum value at the very end.
Full nodes can then follow the behavior of storing and forwarding along
several blocks’s worth of transactions, ten times sounds reasonable,
ignoring transactions which pay less per byte than the ones they have
stored, and further requiring that a new block be minted between times when
a single transaction gets replaced by fee. That policy both has the
property of being extremely denial-of-service resistant and minimizing the
damage to zeroconf. (Zeroconf is a bad idea, but if something is a good
idea to do for other reasons reducing the pain to those stuck with zeroconf
is a nice bonus.)
An actual formula
At long last, here is the formula I advocate using:
Pick a starting point which is de minimis for your first transaction or 1/2
(or less, configurable) your last fee paid if you’ve sent coin before
Let B = max number of blocks from start before giving up, S = starting fee,
M = max fee
For each new block at height H from the start, post a new transaction with
fee e^(lg(S) + (lg(M) — lg(S)) * H/B)
To avoid artifacts when multiple wallets use the same magic numbers, do
this before the first block: pick V uniformly in [0, 1], let S = e^(lg(S) +
(lg(M) — lg(S)) * (V/(V+B)))
The very first time you send coin it makes sense to give it a longer time
to do the transaction because it’s starting from a very low value and you
don’t want to way overshoot the amount necessary. But if you start from the
standard absolute minimum fee in Bitcoin and put the maximum time at
several hours it will increase by less than 10% per block, so exponential
growth is on your side.
It might be reasonable to, for example, start at a value which is a
discount to the minimum paid in the last block if that value is less than
what you would start with otherwise and if there’s a protocol extension to
put that information in the block headers. Such possibilities should be
studied and discussed more, but the formula I gave above should be the
default starting point if you simply want something which works and is
conservative and reliable.
Sidebar: Handling utxo combining
Whenever a wallet makes a payment, it needs to decide how to structure the
inputs and outputs of the new transaction. Generally the output consists of
two utxos, one of them going to the recipient and one of them going back
into the original wallet. Which input or inputs to use is less clear.
Usually an attempt is made to optimize for anonymity, or at least leaking
as little information as possible, and there’s usually a comment in the
code saying what amounts to ‘I can’t clearly justify any particular
strategy here but this is what I’m doing’.
When there are real transaction fees, one might consider trying to optimize
utxo combining for fees. The strategy used turns out to matter surprisingly
little for fees in the long run. For every separate utxo in your wallet,
you’ll eventually have to pay the fee to combine it with something else,
and the amount of increase in fee will be the same regardless of whether
you do it in the current transaction or a later transaction. It does make
sense to include more inputs in earlier versions of a payment though,
because the fees at that time are lower, and drop them in later versions
once the fees have gone up, in the hopes that the utxo consolidation can be
done for cheaper in some later transaction. It may also make sense to do
completely separate purely consolidation transactions with no external
output during off-peak times. That puts more bytes on the blockchain
because of the unnecessary intermediary value it generates though, so there
needs to be a significant difference in fees between peak and off-peak
times for it to make sense. Both of those techniques have significant and
unclear privacy implications and should be studied more.
There are also signing tricks which could potentially save significant
amounts of bytes on the blockchain, thus lowering fees. The most elegant
would be to create a new extension so that when there are multiple inputs
to a transaction which all use Schnorr the signature can be a single
combination signature instead of separate signatures for each of them. This
has very little downside and I’m strongly in favor of it being done.
A simpler, less elegant trick which saves more bytes would be to allow
multiple inputs to the same transaction which use the same key to only
result in a single signature. This lowers privacy, because it gives away
the association between utxos before they’re consolidated, but if used
properly would only push back that reveal a little bit. The danger is that
wallets would instead use it improperly and use the same key all the time,
which would always save as many bytes as possible but be a privacy disaster.
A trick which is a just plain bad idea, although it would save even more
bytes, would be not count the bytes of the reveal of a p2sh script to count
if that exact same script has ever been used before. This is clearly a bad
idea, because it directly encourages extremely privacy-averse behavior, and
because it necessitates a data structure of all p2sh scripts which have
ever been done before for validation, which is quite large and costly to
maintain.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20151106/f9ea4b51/attachment-0001.html>