wumpus changed the topic of #bitcoin-wizards to: This channel is is for discussing theoretical ideas with regard to cryptocurrencies, not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja
maraoz has joined #bitcoin-wizards
trippysalmon has quit [Ping timeout: 250 seconds]
c-cex-yuriy has joined #bitcoin-wizards
c0rw|awa_ is now known as c0rw1n
prosodyC has joined #bitcoin-wizards
joesmoe has quit [Ping timeout: 244 seconds]
c0rw1n is now known as c0rw|zZz
joesmoe has joined #bitcoin-wizards
trippysalmon has joined #bitcoin-wizards
trippysalmon has quit [Ping timeout: 250 seconds]
orik has quit [Quit: My Mac has gone to sleep. ZZZzzz…]
x3066b896 has quit [Ping timeout: 240 seconds]
bramc has joined #bitcoin-wizards
<bramc>
Hey everybody
<bramc>
maaku, are you online?
<maaku>
yes?
<bramc>
Hey maaku, I've spent some more time thinking about patricia trees, and have some implementation questions/suggestions
<phantomcircuit>
bramc, please brain dump :P
<bramc>
The first is, how about leaving some extra space allocated in the leaves of the tree? That way when new stuff is added you don't have to do much reallocation, and you can in principle make the whole thing one flat sorted chunk of memory, which should be quite efficient compared to doing lots of memory allocation
<maaku>
bramc: sure but there's no need to hash that data, or transmit empty bytes over the network, so it's an implementation issue
<maaku>
(although I wonder why a leaf would grow, most applications e.g. UTXO shrink over time)
dEBRUYNE_ has quit [Ping timeout: 246 seconds]
<bramc>
The second one is more vague. Your implementation seems to be base-256. Why not do binary, and cluster depth 8, thus making it an implementation issue rather than changing the format? There's also some interactions between that and the implementation suggestion I just made which I need to spend more time thinking about.
<bramc>
the utxo set grows and shrinks over time, if it remains about stable you never need to sweep through doing a realloc, so all the better.
orik has joined #bitcoin-wizards
trippysalmon has joined #bitcoin-wizards
<bramc>
clumping together layers of the tree seems like a good idea because it reduces memory lookups, which are likely to dominate performance
<bramc>
That gets into the question of what the size of near cache is on modern CPUs, which I don't actually know. It may be that base 256 is smaller than ideal.
<bramc>
All of these things are implementation questions. For the moment I'm assuming that the canonical data structure is a patricia root of the utxo set at the last block plus a patricia root of the delta made by just the current block.
antgreen has joined #bitcoin-wizards
<bramc>
The further batching of updates I brought up the other day I'm feeling lukewarm on, mostly because it's possible that most of the benefits to be had from it can be achieved via implementation tricks.
trippysalmon has quit [Ping timeout: 250 seconds]
<bramc>
maaku, hopefully that isn't too much dump at once. I can discuss things one at a time
<maaku>
bramc: my implementation is binary
<maaku>
there are other base-256 implementations out there, are you looking at the righ tone?
<bramc>
maaku, I probably just misunderstood something you said about radix 256. Are you clumping things together to lower the number of memory lookups to walk the tree?
<maaku>
bramc: no, leveldb is handling that (although the current implementation is memory only)
<maaku>
but the insertion keys are ordered on disk (property of leveldb)
<bramc>
maaku, Oh it's my strong suspicion that a custom data structure could thrash leveldb's performance
<bramc>
Is leveldb's setup documented somewhere? I wouldn't want to reinvent its internal data structures if it's already doing it 'right'
<maaku>
In what way? The suggested implementation right now (again, the only existing one is memory-only) would be to have a separate leveldb entry for each node (leaf or inner), and the 'key' is the path to the node
<maaku>
so each node update is is one key/value update, plus O(log N) key/value updates as you propogate upwards
<maaku>
key/value update == database operation
<bramc>
I'm assuming that leveldb doesn't have maintenance of a patricia root integrated into its functionality. There could be a significant constant factor improvement by doing that right
<maaku>
I'm open to suggestions on how that can be done better.
<bramc>
Frequently time is dominated by memory lookups. Obviously the number of hashes to maintain the patricia root can't be changed, but if things are laid out properly then the number of memory lookups will be log(n)/8 instead of log(n)
<bramc>
Does leveldb provide key/value functionality, and you hack a tree on top of that?
<bramc>
leveldb also isn't using the fact that hashes are fixed length
trippysalmon has joined #bitcoin-wizards
<bramc>
And it doesn't have support for batch inserts and reads either
trippysalmon has quit [Ping timeout: 250 seconds]
<bramc>
Maybe the thing for me to do is finish my thoughts and hack together a protoype. If I do it will be in Python and slow but easy to port to C.
<CodeShark>
why do people like to use python so much for prototyping? I mean, I understand it's a fairly regular language with pretty clear syntax...but anything you build will have to be eventually ported if you want to build anything decent :p
<CodeShark>
I guess it's ok for apps that don't require much performance nor tight systems integration
<bramc>
maaku, Does your implementation store intermediate nodes of the patricia tree as truncated bitfields?
<belcher>
CodeShark eventually the prototype becomes the main program
<belcher>
before you know it you're stuck with python
<bramc>
CodeShark It's great when you're trying to get something up and running and are still experimenting. If you write in a simple style it's easy to port later, and you'll get to that point much quicker for not having had to deal with C in the interim.
<gmaxwell>
see also p2pool. :(
<CodeShark>
bramc: regarding leveldb, it is probably a good idea to not depend on any particular storage engine
<bramc>
At my day job we've ported a decent size codebase from python to C. It isn't any different than the sorts of software engineering discipline you need to keep a legacy codebase from looking like bloated spaghetti
<CodeShark>
wasn't part of the reason C++ was created to avoid having to do this kind of thing? :)
JackH has quit [Ping timeout: 256 seconds]
Newyorkadam has joined #bitcoin-wizards
trippysalmon has joined #bitcoin-wizards
<bramc>
CodeShark True about the code dependency. Thankfully patricia trees are a very well defined format with hardly any weird edge cases unless there are bugs.
Tiraspol has quit [Ping timeout: 256 seconds]
Tiraspol has joined #bitcoin-wizards
Tiraspol has quit [Changing host]
Tiraspol has joined #bitcoin-wizards
<bramc>
Anything I write will be structured as a somewhat general purpose key/value store with the added features of maintained patricia root, batch updates and reads, defense against an attacker shoving everything into one section of the tree, and background maintenance
<bramc>
That's actually a fairly long list of features. Yes I have ideas for all of them.
rusty has joined #bitcoin-wizards
<bramc>
Hey rusty, I was just babbling about the stuff we were discussing via email
<rusty>
bramc: I better grab more coffee then :)
<bramc>
Actually it won't be a key/value store, it will be a secure hash store
<bramc>
aka a set :-)
Newyorkadam has quit [Ping timeout: 272 seconds]
<CodeShark>
bramc: are you looking to write a storage engine optimized for this?
<bramc>
CodeShark Yes that's the idea
trippysalmon has quit [Ping timeout: 250 seconds]
Newyorkadam has joined #bitcoin-wizards
<CodeShark>
it sounds like it could be a pretty useful thing to have generally :)
<CodeShark>
UTXO stuff just being one application
<bramc>
Yeah I'll need to keep the feature set under control to avoid going down the rabbit hole with it though. It's a more-that-a-weekend project to begin with.
<bramc>
Basic API should include batch insert, batch read, and get patricia root. Later there should be batch get paths to patricia root.
csggggg8 has quit [Ping timeout: 265 seconds]
<bramc>
And, uh, whatever else is involved in fixed storage size nodes
<bramc>
I'll probably break semantic boundaries a bit and make it not support items above a megabyte or so, because those can't be in the blockchain.
trippysalmon has joined #bitcoin-wizards
<bramc>
Maybe that restriction will be my contribution to the implicit semantics of bitcoin :-)
<CodeShark>
hah
<CodeShark>
what about support for pruning?
<bramc>
Oh, right, there's batch delete as well
<CodeShark>
I'm thinking also partial trees
<bramc>
And calls for 'do background maintenance stuff now'
<bramc>
Not sure what you mean by that
<CodeShark>
nodes that don't necessarily store the entire utxo
<CodeShark>
updates would require specifying the complete branch
<bramc>
That falls under the general category of 'Not part of MVP'
<CodeShark>
heh, ok :)
trippysalmon has quit [Ping timeout: 250 seconds]
<bramc>
I'm coming up with lots of implementation details, some of which I alluded to earlier, all of which it's probably a lot easier for me to explain by way of implementation.
Guest3928 has quit [Quit: :)]
mr_burdell has joined #bitcoin-wizards
csggggg8 has joined #bitcoin-wizards
<bramc>
But the basics of the API are: 'do batch insert/delete', 'batch read', 'get root', and 'do background maintenance stuff'
<CodeShark>
merging trees could be treated as a batch insert, I suppose
<bramc>
Yes I'm assuming that merging trees is just merging in a small tree and is a regular batch insert
<bramc>
Or a bunch of smaller batch inserts. Should work fine as long as the items being inserted are all grouped into sorted order
<CodeShark>
right
licnep has joined #bitcoin-wizards
AaronvanW has quit [Ping timeout: 246 seconds]
<bramc>
I'll be a little lazy about defense against an attacker intentionally clustering inserts in the first version. That can be done well, but I'll just do it okay, the amount which comes with letting maintenance operations be done in the background.
<CodeShark>
you mean stuff like using HMAC(key, nonce) instead of just key?
<gmaxwell>
Other concerns are that you must be able to efficiently undo state ... and also efficiently support fetching against an old version if you are to support hotstarting off a copy of this data fetched over the network.
<gmaxwell>
bramc: if the data is keyed on transaction hashes, then clustering is protected by the difficulty of partial preimage attacks on the hash.
<CodeShark>
partial preimage attacks can be made even more difficult :)
<CodeShark>
but perhaps it's not necessary
<bramc>
gmaxwell, That offers some degree of protection, but annoying attacks are still possible
trippysalmon has joined #bitcoin-wizards
<bramc>
gmaxwell, Interesting point about rolling back. The obvious approach is to allow indefinite rollbacks, and make it so that roll forwards of pre-stored things don't waste. That doesn't prune though
<gmaxwell>
bramc: not sure about that. at least when we anaylized this before we found the amount of unbalancing you could cause was basically negligible.
<bramc>
gmaxwell, I'm happy to pretend the attacks don't work for now :-)
<CodeShark>
as long as all attackers unbalance in uniformly distributed random directions we're totally fine ;)
<bramc>
gmaxwell, My inclination for rolling back is to assume that it will be handled as forward operations - to switch what branch you're on you remove the blocks you're rolling back and insert the new ones, all as forwards operations
<gmaxwell>
yea, the reorg cases isn't that big a deal as it can be handled basically as bitcoin core currently does, and thats okay.
<gmaxwell>
Though the download case seems much harder to handle efficiently.
roconnor has joined #bitcoin-wizards
deego has left #bitcoin-wizards ["ty"]
<CodeShark>
not sure I follow, gmaxwell - are you talking about receiving the stuff out of order?
<bramc>
gmaxwell, The hope is that the data structure is so efficient that verifying the patricia tree root for every block on download is no big deal
snthsnth has quit [Ping timeout: 264 seconds]
trippysalmon has quit [Ping timeout: 250 seconds]
<CodeShark>
oh, you mean being able to validate the deltas
belcher has quit [Quit: Leaving]
<gmaxwell>
I mean, you've not got this verified root thing, and you'd like to startup some kind of client using only 'SPV history security'. So that would involve you downloading the current state, checking it against the root, and continuing forward. (probably not quite current, actually, but say 300 blocks back)
<gmaxwell>
Great. now ... you're downloading this multiple gigabyte dataset, you'd probably like to fetch it concurrently from multiple peers.. and it's likely going to take you more than 10 minutes to download.
<gmaxwell>
So the network is going to keep moving.
<CodeShark>
how big is the UTXO right now?
<gmaxwell>
so what, you expect your peers to do an enormously expensive reorg back to where you want to fetch from... and then stay stuck there until you're done? Or ... well what? there are lots of ways to address this, but all seem to be awful expensive for the servers.
<gmaxwell>
CodeShark: roughly a gigabyte on disk. About 4 when 'uncompressed' into the in memory data structures.
<gmaxwell>
(encoding on disk is way over optimized. :) )
<CodeShark>
hmm, yeah...it's quite likely a new block is mined before you're done downloading that :)
<rusty>
s/txs/txouts/
<CodeShark>
could we perhaps have separate subbranches for each of block mod some number?
orik has quit [Ping timeout: 272 seconds]
<gmaxwell>
CodeShark: perhaps, but to just copy is awful resource costly.
<CodeShark>
if you go back just a few blocks on initial download you can make it highly unlikely that it gets reorged out...and then it's just a matter of applying the remaining deltas. And after sync you can always go backwards into the history to validate it to increase your security
Giszmo has joined #bitcoin-wizards
<gmaxwell>
CodeShark: in terms of security model, it's much better to take a pretty good leap back there. The reason is that doing a day or two of sync is no big deal. (if you're so slow that this is a problem you have no hope of keeping up).. and it really changes the security assumptions.
trippysalmon has joined #bitcoin-wizards
<gmaxwell>
Since at 100 block reorgs or so is where all bitcoin's incentive/security properties start falling apart. (basically the gap between SPV and full security closes for 'sufficiently large' reorgs)
<CodeShark>
100 because of maturity?
<CodeShark>
or some other reason?
<bramc>
gmaxwell, I'm not sure what your complaint is. The utxo commitment is just a new field in blocks. It adds nothing to the load of nodes serving data to a new node.
<gmaxwell>
bramc: I'm talking about a specific way of using the commitment.
<CodeShark>
bramc: I think we're talking about a different sync model
<gmaxwell>
CodeShark: yea, because of maturity.
<CodeShark>
where we sync to utxo directly
<bramc>
gmaxwell, I understand your point about massive reorgs. For now I'm gonna punt.
<CodeShark>
in this sync model, you just download block headers and utxo
<bramc>
Oh right. hmm
<bramc>
If you wish to start a new download which is pruned to a particular point, then you do need to download the utxo tree of a particular node in the past
trippysalmon has quit [Ping timeout: 250 seconds]
<bramc>
There's an inherent tradeoff of whether you want to actually keep around all the old utxo roots or not.
<CodeShark>
you go k blocks in the past, download the utxo from that point and ignore more recent stuff until you've got it, then you apply a delta for each block since, then you can optionally go backwards from that block to increase security
<CodeShark>
gmaxwell suggests k should be >= 100
<bramc>
It helps to have standardized points people work off of, like every 1000 blocks or so there's one which you're willing to serve utxo tree info for directly, and it's the same intervals for all peers.
snthsnth has joined #bitcoin-wizards
csggggg8 has quit [Ping timeout: 256 seconds]
<CodeShark>
yes, that could even be efficiently sharded
trippysalmon has joined #bitcoin-wizards
<gmaxwell>
sure, Agreed, but ... gonna keep a full copy of the last one of those? high overhead!
csggggg8 has joined #bitcoin-wizards
<maaku>
<bramc> maaku, Does your implementation store intermediate nodes of the patricia tree as truncated bitfields?
<maaku>
yes.
<bramc>
maaku, Ah in that case memory lookups can be dramatically improved using a custom data structure
<bramc>
It's a little silly having a tree on top of a key/value store on top of a tree
trippysalmon has quit [Ping timeout: 250 seconds]
<gmaxwell>
ideally avoiding the (n log(n)) log (n log(n)) overheads.
<maaku>
bramc: I'm not sure what you mean by "tree on top of a key/value store on top of a tree"
<maaku>
it's the same tree
csggggg8 has quit [Ping timeout: 256 seconds]
<bramc>
maaku, Sort of. If you're optimizing for memory lookups you lay things out a bit differently.
<maaku>
I don't want to rain on anyone's parade, but it's not obvious to me that anything more than a small constaint is gained by a custom db / custom data structure
<CodeShark>
he's talking about what happens if you use something like leveldb as your storage engine
<gmaxwell>
maaku: small constants like ... 2?
<maaku>
gmaxwell: or smaller
<gmaxwell>
IMO halving costs in a normative datastructure is not insignificant. In particular you don't want to flub the normative part so that an efficient representation isn't possible.
<maaku>
indexed key/value stores like leveldb are balanced trees internally
<maaku>
and leveldb does have the batch update & snapshotting modes required
<CodeShark>
I'd also rather let someone else handle the low-level storage optimization stuff...but if bramc wants to do it, I'm all for it ;)
<maaku>
gmaxwell: the patricia trie spec I coded up is independent of data store. it's just the specificaiton for hashing nodes, and the ultraprune-like efficient network/disk format
<maaku>
but how the tree is actually stored and indexed is not constrained
<CodeShark>
maaku: I'm also a fan of using abstract models for this...but I think bramc actually enjoys this kind of work ;)
<gmaxwell>
maaku: and leveldb's performance is already seemingly problematic for bitcoin core. (and drove ripple to go create its own thing)
<maaku>
CodeShark: sure, but at the end of the day a significant performance boost would be required to justify maintaining a new db + the review work that would be required (this is consensus code!)
trippysalmon has joined #bitcoin-wizards
<maaku>
vs. using leveldb (alredy part of consensus, and externally maintained)
<gmaxwell>
maaku: yes sure and maybe it's not initially deployed that way. But see my comment above about normative data structures.
<gmaxwell>
maaku: and already problematic without additional overheads.
<maaku>
gmaxwell: I'm not sure I understand your above statement
<maaku>
I think we are talking about the name normative data structure, just different storage methodologies
<maaku>
this was, for example, the primary reason why I went from radix-256 (Alan's proposal) to radix-2 -- you can store a radix-2 as radix-256 by serializing 8 levels together on disk, but not vice versa
<maaku>
anyway bramc I hope we can work together on defining a patricia trie spec for root calculation / hash structure and network relay format irregardless of storage methodology
<maaku>
there's no reason the canonical representation for hashing purposes, or the compact encoding for p2p purposes need to be complicated by storage concerns
trippysalmon has quit [Ping timeout: 250 seconds]
<bramc>
maaku, My intention right now is to make a set data structure which can spit out patricia tree roots. I can easily make the output conform to whatever your spec uses
<maaku>
ok cool.
<bramc>
maaku, Yes that radix-2 vs. radix-256 thing is one of the things I was babbling about before.
<maaku>
my primary concern is seeing if there are further optimizations of the patricia trie structure (reducing hash compressions rounds, reducing proof sizes, etc.)
<bramc>
You can batch up operations. That saves you some calculation.
<bramc>
I don't think there's much of anything you can do to the patricia format though. It's pretty basic. We both like the idea of making the big root be a block behind, but that doesn't change it's format any
<bramc>
For a delta you need a way to represent deletion, of course.
<gmaxwell>
maaku: "there's no reason" -- ... if the hashing structure is one that inhibits an efficient storage implimentation that would be a very good reason. Perhaps in reality no such concern exists, but I don't think we know that without at least trying to design efficient storage... even if we don't use it.
dstadulis has joined #bitcoin-wizards
roxtrongo has joined #bitcoin-wizards
roxtrong_ has joined #bitcoin-wizards
<maaku>
sure ok. well the first place to start is requirements. my own assumptions are that the two metrics to minimize are: (1) network serialization size of proofs, (2) number of compression rounds for validation of a proof
<maaku>
and in a somewhat more distant third (doesn't take precidence over the other two), (3) fewest constraints on implementation
<bramc>
maaku, That's totally dominated by it being radix-2. There isn't much to be added short of making things be deltas off periodic checkpoints, which I'll want to revisit later but first things first.
<gmaxwell>
Hm. I don't understand the rational for (2). One off proof checking would be pretty rare, and the cost of the proof will be dominated by network bandwidth.
roxtrongo has quit [Ping timeout: 264 seconds]
trippysalmon has joined #bitcoin-wizards
neha has quit [Quit: ...sleep]
snthsnth has quit [Ping timeout: 246 seconds]
<bramc>
When you're sending paths to root in bulk a nontrivial amount of bandwidth can be saved by trimming duplicates.
sparetire_ has quit [Quit: sparetire_]
<CodeShark>
just send a partial tree
<gmaxwell>
bramc: sure, the filtered block stuff in bitcoin core does this.
<gmaxwell>
(for block membership proofs)
<maaku>
gmaxwell: SPV mode
<maaku>
hardware wallets
<maaku>
etc.
<gmaxwell>
maaku: right, but consider! you're talking about multiple kilobytes of proof per txin. 2x the hashing will be negligible to dealing with all that extra data in almost all applications.
adam3us1 has quit [Quit: Leaving.]
<rusty>
bramc: the only interesting case is where you have to provide two neighbor nodes for purposes of non-existence proof.
<maaku>
gmaxwell: yeah sure, for an actual computer. I don't want to overconstraint hardware or power requirements though
trippysalmon has quit [Ping timeout: 250 seconds]
<maaku>
oh, also I've only considered solutions that have the possibility for stateless updates (not the best term... being able to calculate the new root using only the delta)
<gmaxwell>
rusty: depending on the commitment structure a prefix tree may not need to adjcent branches to show non-existance.
<gmaxwell>
e.g. if the immediate node above shows the span internally.
<CodeShark>
that would almost always be the case
<gmaxwell>
CodeShark: not sure? I vaguely recall that property was not very compatible with stateless updates.
<gmaxwell>
but I could be wrong.
<maaku>
CodeShark: it's not the case for the structure I developed
<CodeShark>
ok
<gmaxwell>
but if you really did expect to be mostly doing non-existance proofs, there are commitment structures that are more efficient on average, at least.
<maaku>
so yeah, that's an area of research I would appreciate work on -- what's the minimal tradeoffs for adding that capability?
<rusty>
gmaxwell: true, I was thinking simple bit-based patricia trie. But yes, proving a different leaf with same prefix as node N proves that N isn't there.
<rusty>
gmaxwell: with a delta scheme, you may end up frequently proving "it was in base, but not in any delta", right?
<maaku>
gmaxwell: what you're suggesting could be summarized as min-max commitments in the inerior nodes, correct?
<gmaxwell>
maaku: Yes.
<gmaxwell>
It might be useful to make a directory of query types, tie them to applications.. and then we can speak about how efficient different structures are for different offered query loads.
<maaku>
i think that could be stateless so long as the min-max hashes aren't themselves pruned, but you're trading off compression rounds
<CodeShark>
good idea, gmaxwell
<maaku>
yeah it really depends on applications. e.g. for UTXO committments I would expect mostly existence proofs. non-existence proofs are chiefly for fraud proofs (I think?), which you need to support but are presumably rare
<maaku>
but there are other applications...
<maaku>
for an address [sic] index you'd expect more frequent non-existence proofs
<maaku>
Also on the topic of commitments, if anyone wants to contribute something Really Usefull, we definately are in need of an infinite-regress merkle mountain range C library
<CodeShark>
I started working on one in C++
<CodeShark>
what do you mean by infinite-regress?
<maaku>
In MMR as defined by petertodd, you use a regular merkle tree for bagging the peaks. In infinite-regress you use an MMR for the peaks
trippysalmon has joined #bitcoin-wizards
<maaku>
(and then MMR for the peaks of the peaks, MMR again for the peaks of the peaks of the peaks, ... until you have just one hash left)
<CodeShark>
ah, so a nested MMR
<maaku>
yeah
<maaku>
only really provides benefit when log N is large, but for things like STXO sets or block headers that grow forever, that minor optimization gives noticable benefit
<CodeShark>
why is that really useful?
<maaku>
rusty did some compact SPV proof analysis last year, and infinite/nested MMR was *much* better than the competition (something like 2x? I'd have to grep the logs)
<CodeShark>
so only a constant factor?
<CodeShark>
I guess it does make a difference when log N is large...but presumably log N still grows more slowly than moore's law and nielsen's law (hopefully) :)
<maaku>
no that was sloppy of me; with the data sets we were using (meant to be representative of the bitcoin block chain circa 12mo ago) it was of that order
bedeho_ has joined #bitcoin-wizards
<CodeShark>
I'm also concerned about complexity of implementations
<maaku>
CodeShark: as am I; rusty had some other designs that were (imho) hacky e.g. fixed size batching with parameters determined by experiment
<maaku>
nested MMR has the benefit of beating them *and* being a relatively straight forward algorithm
trippysalmon has quit [Ping timeout: 250 seconds]
<maaku>
hence the need for a write-once, use-everywhere C library
K1NGREX has quit [Remote host closed the connection]
<CodeShark>
if I understand correctly, the main benefit to MMR is shorter proofs for more recent txos...or is there something else to it?
<maaku>
shorter proofs to the right-side of the tree
<CodeShark>
yes...but don't you lose key indexing?
<maaku>
it's a purposefully unbalanced data structure, for use cases where access patterns are typically unbalanced
<CodeShark>
or do you need to re "unbalance" it on insertions?
<CodeShark>
i.e. if you have to perform a lot of insertions in the middle of the structure it doesn't seem particularly efficient
<CodeShark>
it's efficient when inserting always on the right
<maaku>
CodeShark: it is only easy to add to the right
rusty has quit [Ping timeout: 255 seconds]
<CodeShark>
right - but then the leaves are always sorted by order of insertion
<gmaxwell>
very efficient. but updating elsewhere isn't worse than updating in a search tree.
<CodeShark>
and you need a separate index
<gmaxwell>
but indeed you do, though that can be a non-normative datastructure for many purposes.
hod0r has quit [Read error: Connection reset by peer]
<maaku>
gmaxwell: hrm. I think you might need access to the full dataset to insert elsewhere than the right-side
hod0r has joined #bitcoin-wizards
<gmaxwell>
insert requires rebalacing but _update_ is as cheap as lookup.
<CodeShark>
only if you have the full structure
<CodeShark>
or?
<gmaxwell>
No.
<maaku>
gmaxwell: right, correct
<gmaxwell>
so e.g. when PT is talking about STXO he assumes you show membership and use the same proof also to update to mark the output spent.
<CodeShark>
ok, right
<maaku>
insert/delete requires N/2, update is log N (avg)
neha has joined #bitcoin-wizards
<gmaxwell>
I suspect there is a way to without much cost support a 'lumpy' mmr that can be cheaply insert/remove but with an unbalancing cost.
<CodeShark>
perhaps I'm missing something but I'm not entirely convinced of the benefits...and it seems to be substantially more complex than patricia trees
<gmaxwell>
it's just you cannot use incrementally optimal self-balancing structures without having to have random access to all the data. :(
<gmaxwell>
CodeShark: its substantially less complex in fact.
<CodeShark>
howso?
trippysalmon has joined #bitcoin-wizards
<CodeShark>
you mean for the verifier? or the prover?
<gmaxwell>
it's just an insertion ordered tree. whoppie. .. with a little bit of special handling on insertion to deal with the unbalanced leading edge. For everyone.
<gmaxwell>
but it makes for different cost tradeoffs.
<CodeShark>
insertions on the right are less complex - I'll give you that :p
<CodeShark>
just about all other operations are more complex
<gmaxwell>
someone shows membership to you.. thats simpler. certantly not more complex.. it's exactly like checking membership of a transaction in a block.
<gmaxwell>
fradulent spends, you have blocks commit to the indexes their inputs are at, and then you just show whats actually at that index.
<CodeShark>
for very specific use cases I can see it having some benefits...but it seems extremely limiting in that once you go outside those narrow use cases it seems ugly. patricia trees seem to be decent for all cases
<gmaxwell>
CodeShark: I am skeptical. I initially thought that and then found when I went through it I was wrong on every count.
trippysalmon has quit [Ping timeout: 250 seconds]
<gmaxwell>
All the cases I came up with the proofs ended up smaller, almost half the size. The software not more complex to describe. And the one thing I really thought it would do poorly is handle pruning and then sipa simulated it on the bitcoin history and found it pruned about as well.
<maaku>
CodeShark: MMR to me seems strictly more useful on average that patricia tries ... but there are some cases (e.g. utxo) where patricia tries work better
<CodeShark>
so you maintain a separate index of the leaves?
<maaku>
CodeShark: can you expand on the use case you are imagining, for which you would require the index?
<CodeShark>
query for a specific txo
<gmaxwell>
[OT] is there some metapackage in debian for "no really, I actually want to write software on this host"? having to install automake / libtool etc one at a time is obnoxious, I'm surprised they're not in build-essential
<maaku>
CodeShark: the assumption with the MMR based proposals is that is pushed off onto the wallet
<CodeShark>
maaku: yes, understood...but that assumption (while not necessarily a bad idea) seems limiting
<CodeShark>
i.e. you might want to outsource proving
<gmaxwell>
it doesn't need to be pushed off to the wallet, but it can be. Or to a third party index provider.
trippysalmon has joined #bitcoin-wizards
<CodeShark>
it also seems like it would complicate sharding or other such things
<CodeShark>
dunno - a factor of 2 doesn't fully convince me
<CodeShark>
longer individual proofs - but seems more complex for full synching
<CodeShark>
err, less complex
<CodeShark>
using patricia trees
<CodeShark>
gives us far more flexibility architecturally
<gmaxwell>
I think thats mistaken.
<bramc>
Don't proofs of not there in patricia just boil down to showing two neighboring leaves?
<CodeShark>
yes, bramc
trippysalmon has quit [Ping timeout: 250 seconds]
<gmaxwell>
CodeShark: in working through this before, I started in your position and then came to the conclusion that for each of the query classes I could enumerate the STXO style approach was more flexable. And it allowed some very powerful offloading that I couldn't see how to do otherwise.
<gmaxwell>
e.g. designs where no host in the world had the full state and it worked fine.
roxtrong_ has quit [Remote host closed the connection]
<gmaxwell>
I'm not asking you to take my word for it, just have an open mind.
<CodeShark>
I need to see it to believe it
<gmaxwell>
Uncertanty around pruning was the main concern I had with it after working it all through.
<bramc>
gmaxwell, What use case are you thinking of for mmr?
<CodeShark>
can you elaborate on that, gmaxwell?
<gmaxwell>
Also, careful that you don't confuse goals with mechenisms. Like... _why_ do you want a non-existance proof? To show a block is fradulent? But that doesn't actually need a non-existance proof, the block can just instead specify which indexes its spending.
<gmaxwell>
CodeShark: STXO design doesn't ever 'remove' entries, it just updates them to mark them as spent (e.g. replaces them with a constant value spent token.) So you can prune the tree. This sounds inherently less efficient, but it turns out that "log X" is essential no worse than some constant, in the physical universe... so the fact that the tree is a bit bigger hardly matters.
<CodeShark>
STXO vs UTXO seems like a separate issue of patricia tree vs. MMR tree
neha has quit [Quit: ...sleep]
<gmaxwell>
MMR doesn't make sense with utxo because the common operations there are random insertions and removals which are not efficient for MMR.
<CodeShark>
yes, I get that - in fact, I've even implemented it
<CodeShark>
but you could still have STXO with a patricia tree
<gmaxwell>
STXO the common operations are appending (ultra efficient, works proofless) and a lookup+update.
<gmaxwell>
you could. but the operations STXO does are exactly those which are ultraefficient for MMR.
<CodeShark>
and you need a separate index for arbitrary structure queries
TheSeven has quit [Disconnected by services]
<gmaxwell>
But who is you?
<gmaxwell>
A full node needs no such index.
[7] has joined #bitcoin-wizards
<gmaxwell>
A miner needs no such index.
<CodeShark>
a prover needs the index
<CodeShark>
unless it's the sender
<gmaxwell>
A wallet does, but only for the coins that it can spend.
<CodeShark>
the only use case where the prover doesn't need the index is when the prover is the sender - but that seems rather restrictive
<gmaxwell>
and then you can relay the offsets along with the transactions.
<CodeShark>
I'm thinking about, i.e., synching two instances of the same wallet
<gmaxwell>
and you can even ask a third party to provide them. So you have many options: have a index yourself. Okay. Then you can relay along the offsets on any tx you see so indexless nodes can find them.
<gmaxwell>
Or you can have a partial index, with an arbritary sharding of your choice.. including "coins I can spend"
trippysalmon has joined #bitcoin-wizards
<bramc>
I still don't understand what stxo/mmr is being considered for
<CodeShark>
also, what happens when the recipient is not online at the time the transaction is sent? does the sender outsource delivery?
<gmaxwell>
CodeShark: no different than bitcoin?
<CodeShark>
so all these proofs would be relayed continuously all the time?
<gmaxwell>
(I mean if there is no one storing recent blocks at all then you have an issue there-- but the point is that you can choose any degree in between what bitcoin has not and everyone is stateless)
<CodeShark>
I suppose with something like lightning we can really begin to talk about outsourcing delivery
<CodeShark>
but with the current flood model it doesn't seem to make much sense
<gmaxwell>
CodeShark: I don't agree? I mean you can keep recent blocks (like with pruning we won't go below 288 in bitcoin core) and then after that if you've been offline a wallet has to go find an archive node to tell them about transactions of theirs.
<gmaxwell>
and by archive I don't mean complete,... I mean perhaps it just needs one with 2016 blocks back.. or it knows it gave out keys hashing to X,Y,Z lately so needs archives specializing in those keyspaces.
<gmaxwell>
Or it's a foobar-script wallet and talks to an archive that indexes only scriptpubkeys of that particular kind, and so on.
<gmaxwell>
the indexing is non-normative with STXO+MMR so you're not fixed on a single commited way of making indexes.
<gmaxwell>
maybe you have shared nodes that index every Nth block and you go gather from them when you sync back up. ::shrugs::
<CodeShark>
dunno - introducing substantial asymmetry for the sake of at most a halving of proof sizes that can be delivered directly to recipients (i.e. via lightning) doesn't sound very appealing...but I'll continue to keep an open mind :)
<gmaxwell>
well it's not just halving the proof size, it also renders it independant of the indexing structure.
smk has quit [Quit: Page closed]
<CodeShark>
where would that be beneficial?
<bramc>
oh, stxo = spent transaction outputs
<CodeShark>
yes
<gmaxwell>
well I just described. you can have every system in the world be almost completely stateless. (just a small near constant amount of state, plus recent history for reorgs) ... plus then whatever information that is 'interesting' to them via whatever scheme you'd like to dream up, now or in the future.
<bramc>
what's the benefit of mmr over patricia for stxo?
<CodeShark>
that's what we're discussing, bramc
rabidus has joined #bitcoin-wizards
Burrito has quit [Quit: Leaving]
<bramc>
Yeah I'm not following. Is it that the mmr has less update costs?
<gmaxwell>
20:47 < gmaxwell> STXO the common operations are appending (ultra efficient, works proofless) and a lookup+update.
<gmaxwell>
20:47 < gmaxwell> you could. but the operations STXO does are exactly those which are ultraefficient for MMR.
<CodeShark>
the main benefit seems to be that as long as we're only performing append operations we only need to store the root hash
<CodeShark>
and each object appended requires only a short proof
<gmaxwell>
if you have the leading edge of the mmr already then each append is proofless.
<bramc>
Is there any way to prove something isn't there in mmr?
<gmaxwell>
bramc: At least in the context of block fraud you can eliminate the need for non-membership proofs by requiring any claim of membership at least provide the offset (which is free).
<bramc>
gmaxwell, I'm not sure what you just said
<bramc>
I understand that patricia is taking on significant costs for the sake of keeping everything sorted
jinglebellz has quit [Remote host closed the connection]
<gmaxwell>
Sorting is overkill. Consider: you're sorting on meaningless hashes. "How doees this make sense" :P
jinglebellz has joined #bitcoin-wizards
<CodeShark>
but then you need to sort anyhow for indexing
<bramc>
Well there's a reason to keep the utxo set sorted
jinglebellz has quit [Remote host closed the connection]
<gmaxwell>
We'd like to show non-membership to prove a block or transaction is fradulent... right? so just have the block or transaction give the 32bit or 64bit or whatever index for the position of the thing they claim is a member in the insertion ordered comitted list.
<gmaxwell>
Proof of non-membership is simply showing whats actually at that offset.
<gmaxwell>
Doublespent, meaningless, never have existed in the first place.
<gmaxwell>
You make every input claim what offset it consumes. The thing its consuming is either there .. or it's not (because it was spent, or because it was never there in the first place)
<bramc>
Ah, now I understand what the requirement is
<MRL-Relay>
[tacotime] well... but you do need the data structure to be stable on insertion/deletion
<bramc>
Yes for stxo mmr makes a lot more sense because of the lack of sorting requirement because you don't need to prove stuff isn't there.
<gmaxwell>
You never delete. And you only append not insert.
<gmaxwell>
To spend a coin you update it and replace it with a fixed constant spent flag.
<MRL-Relay>
[tacotime] What about reorganizations?
<gmaxwell>
[tacotime]: for any of these schemes reorgs are handled by external magic (rollback logs)
<MRL-Relay>
[tacotime] oh, i see.
<gmaxwell>
e.g. what bitcoin does for the UTXO set.
<MRL-Relay>
[tacotime] yeah, that's how btcd always handled reorgs too. but i figured that for something like that you'd have to the reverse of all changes, so you'd have to keep a log of all altered paths in the tree for each block i guess.
<gmaxwell>
really it's just a log of any destroyed data, plus the updates themselves is sufficient.
<CodeShark>
how would you do initial sync of a full validator node using mmr+stxo?
<CodeShark>
(without having to download the entire blockchain)
<gmaxwell>
with full security? well the only option for that is downloading all the blocks so you mean with SPV security?
<CodeShark>
let's not call it SPV security :p
<CodeShark>
let's say recent history security - i.e. the last 1000 blocks
<CodeShark>
+ PoW
<gmaxwell>
Sure. you get the root for t-1000 and then start fetching blocks along with their update proofs from nodes that have those full blocks.
<CodeShark>
ok, so then the key insight is that we're actually committing to the position of each output in each block
<CodeShark>
explicitly
<gmaxwell>
yes.
<CodeShark>
why didn't you start off with that? :)
<gmaxwell>
Assumed background knoweldge. Sorry.
<gmaxwell>
now to be fair, I'm somewhat selling you a sweet song here. There are complications. Stateless nodes like I described are dependant on needing membership proofs for all inputs. Thats less bandwidth efficient than sending a whole utxo set at some point.
<gmaxwell>
you could instead just fetch the whole pruned state too, however.
<gmaxwell>
though since the number of entries is all history instead of utxo it will be somewhat larger. (not as much as you think, because of pruning)
<gmaxwell>
but in the worst case it's much larger.
<gmaxwell>
e.g. if the network manages to spend every other output though all the history just to screw with you.
<gmaxwell>
I CAN FINALLY GO HOME!
* gmaxwell
vanishes
<CodeShark>
lol
snthsnth has joined #bitcoin-wizards
<bramc>
I think for my MVP I'm going to make it a set of hashes and not store the things they're hashes of
dstadulis has quit [Quit: ZZZzzz…]
<gmaxwell>
anyways, once you work through the overheads enough to see how what I was just describing is not all roses, the next set of ideas is the dual structure where you have a fixed size utxo of recent history and then evict things from it into an STXO history.. and indeed, at that point you end up with something that is more complex than a plain huge patrticia tree.
<CodeShark>
we could also commit to backreferences using a patricia tree to allow for stateless validation...but specifying paths requires a bit more than just an offset
<gmaxwell>
but you get savings in two ways-- you keep short lifetime outputs out of the STXO logN ... and you get really small proofs for them too.
<bramc>
gmaxwell, That's similar to my proposal to having big patricia trees which only get updated at set times and working off a delta from it
<gmaxwell>
bramc: I hadn't made that connection before you'd mentioned your thing just because the motivations were different.
<gmaxwell>
(e.g. I just never considered the IO cost implications of the split scheme)
<gmaxwell>
since stxo is insertion ordered it doesn't have any huge mandatory IO cost implications by itself. One of the selling points of that class of schemes.