--- Log opened Tue Nov 02 00:00:21 2021
01:25 < devrandom> <kcalvinalvin> "https://github.com/mit-dci/utcd..." <- so it seems that what I need is an RPC wrapper for `GenerateUData`, where I pass in a set of UTXOs and I get back the batch proof and the current tip
01:52 < kcalvinalvin> devrandom: Yes. And the peer receiving the proof would validate with https://github.com/mit-dci/utcd/blob/9b19805dfd801d56aa5af0d0b6a67034d6cc3988/blockchain/utreexoviewpoint.go#L528-L539
01:53 < kcalvinalvin> Do note that the verifier would also need to have the chain synced to the tip
01:55 < devrandom> BTW, in my use case, the verifier gets the accumulator root from a trusted source (in particular, a set of oracles - each signing the root)
01:55 < devrandom> it's very lightweight (e.g. a hardware wallet)
01:56 < devrandom> so it doesn't need to sync up the accumulator itself
01:57 < devrandom> so I would also need an RPC to get the accumulator roots as of a certain height.  this is for the oracles, so they can sign and publish those
01:58 < kcalvinalvin> You could just save all the roots for every height
01:58 < kcalvinalvin> https://github.com/mit-dci/utcd/blob/master/chaincfg/mainnetroots.go
01:58 < devrandom> :+1:
01:59 < kcalvinalvin> It was pretty compact to have roots every 1000 blocks
01:59 < kcalvinalvin> It took too long to put every single root inside the binary
01:59 < kcalvinalvin> But just having it in memory is no problem
01:59 < kcalvinalvin> Or on disk, it's tiny
02:00 < kcalvinalvin> https://github.com/mit-dci/utcd/blob/master/chaincfg/testnetroots.go - this is the roots for testnet
02:00 < devrandom> nice
02:03 < devrandom> I suppose running `GenerateUData` for a historical block is pretty difficult.  but it seems OK to have gaps in the proofs supplied to the verifier for our use case, if blocks come in so fast that we don't react in time for a block
02:04 < devrandom> our codebase is in Rust, so will have to reimplement some of the data structures in Rust for the verifier
02:04 < kcalvinalvin> devrandom: Yeah 'GenerateUData' only supports proving from tip. You'd have to dig around pre-generated proofs for historic blocks
02:05 < kcalvinalvin> https://github.com/mit-dci/rustreexo
02:05 < kcalvinalvin> I ditched the rust library in favor of making the go node more robust. But if there's need, I can look at it again
02:05 < kcalvinalvin> (the rust lib doesn't work at the moment)
02:06 < devrandom> kcalvinalvin: that won't work either, because the pre-generated proofs are for UTXOs that are being spent in a block, but we need proofs for UTXOs that continue to be active.  we are continuously proving to the verifier that a set of UTXOs is still alive.
02:09 < devrandom> kcalvinalvin: if you have code that may be useful, I would be happy to take a look
02:20 < kcalvinalvin> devrandom: Yeah so you'd also create proof for all the new UTXOs created in a block
02:20 < kcalvinalvin> And that'd work
02:40 < devrandom> <kcalvinalvin> "devrandom: Yeah so you'd also..." <- I don't think I understand.  our verifier needs to be shown that a UTXO that was created at some point in the past (perhaps many blocks ago) is still active at the current tip.  so it doesn't care about any other UTXOs that may have been created in a block.
02:42 < devrandom> sorry about any confusion - our use case is very different from the original Utreexo use case - our verifier only cares about a small subset of UTXOs, and continues caring about them over time.  this is different from the CSN in the normal Utreexo vision that cares about the global set of UTXOs and how blocks modify this global set.
02:47 < _aj_> devrandom: that's not that different? caring about a small subset of utxos (and knowing they're unspent) is something every wallet wants to do
02:48 < _aj_> devrandom: standard utreexo behaviour (as i understand it) is to (a) update the root hash as blocks come in -- that's the consensus part; and (b) update the proofs for any utxos you care about so you can do wallet operations (which is also your use case, i think). bridge nodes go further and update proofs for _all_ utxos, but the idea is that's a relatively rare thing to do
02:49 < _aj_> (again: aiui, correct me if i'm wrong)
02:59 < devrandom> _aj_: I agree that our use case is very similar to the wallet use case, including the need to update wallet UTXO proofs if you are not running a bridge node.  but that doesn't seem to be discussed at all in the original paper.  so just want to attract attention that both a CSN and a wallet can be "verifiers", but we are focused on the latter, which has somewhat different requirements which might not have been considered in detail yet.
03:16 < _aj_> devrandom: aiui the idea is that if you're not a bridge node, you won't receive the current [header, tx, tx, tx...] data when a new block comes in, but instead [header, [tx+proof], [tx+proof], [tx+proof], ...] and those proofs will let you easily update any existing utxo proofs for the new block. bridge nodes do the [header, tx,..] -> [header, tx+proof,..] conversion
04:33 < kcalvinalvin> _aj_: > [header, [tx+proof], [tx+proof], [tx+proof], ...]
04:33 < kcalvinalvin> Should note that while this would work, we don't do this because you can batch the proofs and compact the proof. So you receive [header, tx, tx, tx...][proof] as a non-bridge node
04:35 < kcalvinalvin> > header, tx,..] -> [header, tx+proof,..] conversion
04:35 < kcalvinalvin> Same here, you don't generate a proof per tx but rather for the entire block. so [header, tx,...] -> [header, tx,...][proof]
04:38 < _aj_> kcalvinalvin: right, but you can generate the per-tx proofs from the per-block proof and vice-versa, no? so it's "just" an encoding difference?
04:38 < devrandom> sounds like you two are saying that the block proof can be used to update a wallet UTXO proof.  that's interesting.  it's not in the paper, right?
04:40 < _aj_> devrandom: isn't it the bit about "efficient storage and processing of subsets of the forest" ?
04:50 < devrandom> I guess I don't quite see how that's done.  so let's say I have a proof of a single UTXO - it's basically a path from root to leaf.  and let's say that a UTXO is deleted elsewhere in the tree.  the deleted UTXO is replaced ("swapped"?) with another UTXOs.  but the deletion proof doesn't include the replacement UTXO, so I don't see how I would know what the new hashes along the path to the deleted node are.
04:51 < devrandom> s/UTXOs/UTXO/
04:52 < devrandom> ^ aj
04:54 < devrandom> _aj_:  hmm... I guess the question above applies to a CSN in general.  so I'll take a look how it's implemented in the code, I must be missing something
04:54 < _aj_> devrandom: sorry, i don't know the details. i don't think you can delete a node without knowing the path to its leaf though, so i think you're just missing where that path is?
04:55 < _aj_> (or you can't replace a leaf without knowing what the replacement is, etc)
09:23 < adiabat> I'm still not 100% sure what devrandom's wallet needs, but I'll try to clarify a bit -
09:27 < adiabat> You *could* have CSNs with wallets that keep proofs for their own UTXOs (the ones they own) and when they send out transactions that they've signed, those transactions are already proven
09:27 < adiabat> without the need for a bridge node to do anything
09:28 < adiabat> That model is attractive in the sense that as more and more wallets / nodes are CSNs, bridge nodes are less and less needed
09:28 < adiabat> *but* the current plan is not to do that.  There's 2 reasons
09:30 < adiabat> one is that you're going to need bridge nodes for the forseeable future, and those bridge nodes won't have any idea which utxos are tracked by utreexo wallets
09:30 < adiabat> so having wallets not bother, and just send out transactions they sign to regular old bitcoin nodes, which will gossip the tx around
09:31 < adiabat> and eventually will get to a bridge node and get proofs tacked on... that works fine.
09:31 < adiabat> The other concern is that if you implement wallet proof tracking in the straightforward / simple way, it can really hurt privacy
09:32 < adiabat> the CSNs will each have different subsets of the full forest that they're storing, and not just because they have different amounts of ram to cache it
09:33 < adiabat> but because they own different leaves.  This is probably ery detectable by nodes connected to them by seeing what proof they request
09:33 < adiabat> (that is, once we have nodes request proofs -- right now we just send the full proof for everything, which is very inefficient)
09:34 < adiabat> so it's probably tricky to get it to work in a safe way that doesn't let people figure out what utxos you own by what proofs you request
09:34 < adiabat> you'd have to have the proof separately, and mark it as like "I know these hashes, but request them anyway because I don't want anyone to know that I know them"
09:35 < adiabat> so curently it's not doing "update the proofs for any utxos you care about so you can do wallet operations"
09:36 < adiabat> seems possible, would be cool, but a bit of a minefield so avoiding for now as not really needed
09:37 < adiabat> OK other clarifications ---
09:37 < adiabat> "so let's say I have a proof of a single UTXO - it's basically a path from root to leaf.  and let's say that a UTXO is deleted elsewhere in the tree. the deleted UTXO is replaced ("swapped"?) with another UTXOs."
09:38 < adiabat> ^^^ yup, all this is correct
09:38 < adiabat> "but the deletion proof doesn't include the replacement UTXO" 
09:40 < adiabat> ^^^ actually, it does!  Not as a separate thing, but it's built in.  Here's how:
09:41 < adiabat> with the example of deleting 1 leaf (multiple leaves are more complex, but you can see how if you can get it to work with 1, worst case you can just repeat that a bunch of times for multiple leaves)
09:41 < adiabat> pre-deletion, there are either an odd number of leaves, or an even number of leaves
09:42 < adiabat> the deletion proof contains the sibling of the leaf being deleted
09:43 < adiabat> if there are an odd number of leaves, there will be a single leaf all by itself in its own tree.  That isolated hash can be brought in to take the place of the deleted leaf
09:43 < adiabat> and all hashes up to the root can be recomputed
09:44 < adiabat> if there are an even number of leaves pre-deletion, the lowest hash in the proof *becomes* the isolated hash
09:45 < devrandom> so the order of the leaves can change - I missed that.  I guess that's necessary for performance, otherwise you'd have to shift leaves too much
09:46 < adiabat> Yes, right now leaves move around a bit.  I'm working on a somewhat different design where they move around less
09:46 < adiabat> since the moving around actually hurts as it tends to increase the size of proofs
09:47 < devrandom> adiabat: but does the proof include this isolated hash?  I thought that the proof includes the siblings of the node pre-deletion, so would not refer to the thing that was swapped in
09:47 < adiabat> because new utxos get mixed in with old ones.  We want old UTXOs to have big proofs and new utxos to have small proofs, since new utxos are spent so much more often
09:48 < adiabat> The isolated hash doesn't need a proof; it counts as a root (it's the only root that's also a leaf) and CSNs will always store it
09:48 < devrandom> but I should read the code more carefully, I think I made some unwarranted assumptions
09:48 < devrandom> oh, right
09:48 < adiabat> yeah it's a bit weird but code wise it all works out
09:49 < adiabat> the code is... too complex, I'm trying to make it simpler.  When you're proving and deleting multiple things at once, there's a lot of shortcuts to not hash as much 
09:50 < adiabat> but the code is ugly / complex.  eg all of https://github.com/mit-dci/utreexo/blob/master/accumulator/transform.go
09:50 < devrandom> OK,  I think I get the theory.  I'll run some of the unit tests and stare at the printouts to have a more intuitive feel for how the nodes move
09:51 < adiabat> Sure.  Maybe don't worry to much about the specific moving algo, as hopefully it will change to something a bit simpler soon
09:51 < adiabat> whatever change though will have the same interfaces and shouldn't affect how CSNs / bridge node code works
09:52 < devrandom> OK, thank you
09:53 < adiabat> 👍
10:04 < devrandom> hmm.... so I'm trying to visualize by running the `TestForestFixed` unit test, and changing `numadds = 16` and `numdels = 1`.  i.e. a single perfect tree to start with, and then the first node is deleted.
10:05 < devrandom> strangely, I'm seeing the entire row 0 reshuffled - I didn't expect that
10:06 < devrandom> adiabat: ^
10:07 < devrandom> rows 0 goes from:
10:07 < devrandom> 00:0000 01:0001 02:0002 03:0003 04:0004 05:0005 06:0006 07:0007 08:0008 09:0009 10:000a 11:000b 12:000c 13:000d 14:000e 15:000f 
10:07 < devrandom> to:
10:07 < devrandom> 00:0008 01:0009 02:000a 03:000b 04:000c 05:000d 06:000e 07:000f 08:0004 09:0005 10:0006 11:0007 12:0002 13:0003 14:0001 15:0000 
10:18 < adiabat> yup, that is the worst case scenario for this algo
10:18 < adiabat> it goes from having 1 root to having 4 roots
10:18 < adiabat> at the start, the only thing the CSN knows is root 30
10:19 < adiabat> proof for 00 is 01, 17, 25, 29
10:19 < adiabat> so those become the new roots of the new trees
10:19 < adiabat> they're in the wrong order though, with the smallest on the left and biggest on the right, so everything has to move around
10:20 < adiabat> 8,9,a,b,c,d,e,f was all under 29 so that all moves to the left, and so on with the smaller trees
10:21 < adiabat> if you had 16 leaves and deleted position 15, its more of the best case scenario, in that nothing moves and the proof becomes the new set of roots with no change
10:22 < adiabat> also the worst case scenario is rare compared to best case; since we add UTXOs left to right, we usually don't have to delete stuff all the way on the left
10:23 < devrandom> ah, right, will try with something not on the edge
10:34 < devrandom> adiabat: strangely, the printout for the edge case I tried above (numadds = 16, numdels = 1) shows still a perfect tree rather than a forest after the delete.  is that no as expected?
10:36 < devrandom> (perhaps the diagonal nodes are garbage but they still show in the printout?)
10:37 < adiabat> yeah I think the print function will continue past the end.  So even if numLeaves is 15 it will print 16, and the last one is junk data.
10:38 < adiabat> same on disk, it leaves stuff there instead of shrinking the file or overwriting with 0s since nothing should read there
10:42 < devrandom> yeah, it prints an extra in each row when you go from 16 to 15
10:43 < devrandom> but that's fine
12:56 -!- ksedgwic [~ksedgwicm@2001:470:69fc:105::ce1] has joined #utreexo
13:22 < dergoegge> i watched the assume utxo thingy on the youtube live stream and there was something pretty cool mentioned: using utreexo to sync up the background chainstate for assumeutxo. 
13:22 < dergoegge> i feel like that could be a really great first step to get some parts of utreexo into bitcoin core.
13:22 < dergoegge> if we use the caching technique that calvin tested out recently where the mainnet proofs are only like ~10GB, then for the above to work a node could download all the proofs before doing IBD (similar to the download of the actual assumeutxo snapshot)
13:22 < dergoegge> lets say you activate assumeutxo at height 700000, then you download the proofs up to block 699999 and validate the background chainstate using utreexo with as many cores as you want to.
13:22 < dergoegge> i guess we would need a function to convert the assumeutxo snapshot to the accumulator roots to compare that everything matches up, but that should be possible somehow.
13:22 < dergoegge> we dont need any new p2p code for this and bug-to-bug compat is also less of a concern with the conversion function.
14:12 -!- michaelfolkson [~michaelfo@138.68.143.20] has joined #utreexo
17:04 < adiabat> Another possiblity which seems possible is converting from utreexo to a regular db after IBD
17:05 < adiabat> that seems easy enough: ask a birdge node for all the leaf data and put it in your db
--- Log closed Wed Nov 03 00:00:22 2021