Looks great.  Just tested it with Armory and it works as expected

What's the current memory usage?  Is it increasing?  The longest I've seen it take is 5 minutes and that was a VM that was swapping.  And that should be improving soon...

I'll try to get this optimization in soon and see what comes of it.  But honestly, I don't know what to make of your situation.  Can you run it from the command line and tell me what the console output is?  Where is it frozen?  Any error messages?

Any of these can be made into an authentication data structure.  Each node, including non-leaf nodes may represent data, so you just append this node's data, to the hashes of the non-null children and hash that to get the current nodes value.  Then it's parent nodes do the same to agregate their children.

I haven't defined it rigorously, but it can be done.  One issue with a 256-way Patricia/radix tree is that each level will need the values of the other 255 children in order to verify each level.  Granted, it only matters at the top levels where there's a lot of branching, beyond levels 4 and 5 basically all other children pointers will be null.  But it goes along with why I'm hesitant to endorse a patricia tree: there might be a lot of data to transfer to very a node.

I was expecting that the hash of the TxOut script would be used so that all nodes are exactly 32-bytes.  You could argue that's exactly what most TxOut scripts already are:  hashes of longer data fields (such as using hash160s in place of public keys), but you have to make sure the search key is strictly bounded in size if you're using a trie of some sort.

@vuce
The structure of a trie has no dependence on insert order.  Given a set of data, there is only one trie that can hold it.  The same goes for Patricia tries (which are level-compressed tries).  And given that its query, insert and delete times are based strictly on key size (which will be bounded as above), there are no balance issues at all: it always takes exactly 32 "hops" to get from the root to the leaf you want, regardless of whether you are querying, inserting or deleting.  So given fixed key-length, all those operations are actually O(1).  

On the other hand, I was hoping for a structure that wasn't too complicated, and both RB trees and Patricia tries have complicated implementations (even though the concepts behind them are fairly simple).  But if we're going to have to go with something complicated, anyway (to limit worst-case speed and time performance), then I'd have to vote for Patricia trie or variant.  Not only is it O(1)... someone brought up the very good point that updates to the tree can mostly be parallelized.  That sounds like another good property of a tree that's going to have very high update rates...

I just gotta spend some time to figure out the space overhead for storing TxOuts.  If it's going to triple the overall disk space compared to other structures, it might be worth using one of the insert-order dependent trees.

What other data structures am I missing that could be considered?  I know B-trees would be a good choice if we are going with insert-order-dependent structure:  they are easy to keep balanced with fairly simple rules for balancing.

This is a topic I've been debating with folks on IRC the past couple days.  It's clear that most tree data strcutures have most of the properties we want.  Red-Black trees work great, but I don't like that the specific underlying structure (and thus root hash) depends on the specific order/history of insertions and deletions.  And assumes that every red-black implementation uses the rebalancing algorithm.  I have been given compelling reasons why this shouldn't be a problem, but I am personally not convinced yet.  Though I agree that it is probably an acceptable solution.

I'm voting for level-compressed trie structures (so, a variant of a patricia trees) which have no balance issues at all, are insert-order-independent, and O(1) query/insert/delete.  The problem is they can have a lot of storage overhead per tree element.  I haven't done the calculation to know for sure just how bad it is. 

Once I get out my next version of Armory, I will be diving into this a bit more, hopefully creating a proposal with much more specifics about tree structure, and the CONOPs (concept of operations) of the meta-chain.

Sorry, it's the blkchainagain branch.  I'll merge it into master when it becomes 0.80. 

In a month or two, I will be implementing a new wallet format -- with the intention of being compatible with the new wallet that the core bitcoin team will be switching to.  This means two things:

(1)  The deterministic algorithm will be changing.  Completely.  However, I have every intention of maintaining support for the old wallets (if possible... I think it is). 
(2)  The new wallet will be using a much shorter seed.  The current wallets require 512 bits of information to reconstruct your entire wallet.  The new wallets will only require 160 bits.

So this means that if you insist on memorzing your wallet seed: (1) it would be really hard to do it right now.  128 hex characters is a lot.  (2) It will get considerably easier with the new wallet format.

Sweet!

Armory 0.79.99.3 Downloads Page

-- Fixed coinbase transactions in the ledger.  Completely.  Seriously.
-- Fixed zero-confirmation transactions not being added to unconfirmed balance
-- Fixed change-to-self being marked unconfirmed
-- Changed optimization settings on Windows builds (don't know if it makes a difference at all)

AND I noticed an opportunity for optimization that I thought I had implemented months ago -- perhaps I did so in another dev branch that got orphaned.  Or maybe there was a reason it didn't make it in...

I will probably make 0.79.99.3 into 0.80-alpha, then work on those optimizations, and saving data between loads.

Yeah, fairly accurate.  I'll re-summarize here because my view of my own proposal has evolved over discussions of the last few days, so I figured it was a good time to restate it, anyway


The first goal is blockchain pruning:  the amount of information needed to store the entire state of the network at any point in time is much less than the entire blockchain history.  You can basically just save the "outer surface" of the transaction map instead of the entire history and still do full validation.  

So I propose a structure that achieves this compression, and further organizes it accommodate a specific, common problem we want to solve anyway:  a new node gets on the network with its imported wallet and doesn't need the whole chain, but would like to get a complete history of it's own transactions in a verifiable manner.  I argue that with a more-straightforward "snapshot" tree, there's still room for deception by malicious peers, albeit not a whole lot.

Either way, I believe it's possible that new nodes can use a structure like this one to get up in running with full confidence in less than 50 MB of downloading, even in the far future.  And such a solution will be necessary, so let's hash it out now...

However, for lite-nodes to reliably use the new information, there must be some kind of enforcement that miners provide correct answers when updating the root node.  This could be done by hard-forking the network by changing the headers to require a valid root node, soft-forking by requiring a specific tx or coinbase script to contain a valid root, or as I propose: create a separate chain solely to allow mining power to "vote" on the correct snapshot root.  Such a solution would then be completely optional and transparent to anyone who doesn't know or care about it -- though I would expect most miners and developers would be anxious to leverage it.

As galambo brought up -- the alt-/meta-chain idea is a kind of "staging area" for this new piece of the protocol.  Once the community starts using it and becomes dependent on the information it provides, it could be integrated into the main chain (via hard- or soft-forking) as it would have super-majority support at that point.

I used memory-mapped files in version 0.60 to 0.77 of Armory.  Not only was it slow as dirt in Windows (though it worked brilliantly in Linux), it won't work on any 32-bit systems once the blockchain reaches 4GB+.  32-bit processes can't allocate enough virtual memory.  Hell, Win32 wouldn't take it at all even with 4 GB RAM, and a 1 GB blockchain (hence why Armory never worked in Win32).  Not only that, but mmap is OS-dependent.  If you want to use Map-Of-File-Views (the mmap equiv in Windows) you're going to deal with windows.h and LPWCSTRs.  

I'm so glad I got rid of that.  That's why I emulate it now, and it cleaned up my code a bit not having to branch base on OS.

I understand about the python wrappers.  You don't have to use the python, there's a pure C++ library underneath, though it's not obvious how to use it.  BlockUtilsTest.cpp has a lot of examples, but it's not intended for educational purposes:  it's really for me to do my unit-testing.

And in the end, I always approve of people digging in and implementing pieces of Bitcoin.  There's no better way to really undrestand it.

Nice!  Mind sharing a top-level overview of how you do it?  Data structures?   Do you know how much that is I/O limited?

The C++ utilities I wrote for Armory are almost that fast (but in linux only, have no idea why windows is so damned slow!).  I buffer blk000X.dat into RAM 50 MB at a time, and then pass around pointers to this data and scan it directly -- to avoid any extra copies.  It's a lot of pointers...

Okay!  Coinbase transactions have been fixed!    


I'm going to find the source of the zero-confirmation-but-not-unconfirmed bug, then probably consider releasing this 0.80-alpha.  I think beta will have to wait until I have something that won't take 4 minutes to load every time (first load is fine...)

EDIT:  I won't recompile all the versions yet, but since I already did the Linux-64bit version, so you can download it here if you want to try it... It's 0.79.99.2.

"Unconfirmed" should mean "less than 6 confirmations", not "1 or more".  However, I need to modify that to mean "less than 6" for regular tx, and "less than 120" for coinbase.  Spendable should be "1 or more" for regular transactions, "more than 120" for coinbase.

It sounds like what was displayed in this case was as expected (except for the "unconfirmed balance" at zero confirmations).  Is this correct?  The issue was actually time to first-confirmation of the network, not Armory itself.

As for the crashing, I'm going to try to insert a watching-only P2Pool-receiver address into a watching only wallet and investigate it myself...

Well that's where we are differing in opinion.  Majority peer-influence is cheap relative to majority mining power.  That's not to say it's an easy exploit, or that it would be in any way worth it.  But I see it as a source of uncertainty, and a channel waiting to be exploited in some way we haven't thought about.  I think the added complexity is well worth closing the "hole" completely.  Though not everyone feels it's actually a hole. 

I personally think it makes more sense, anyway -- you can still get a single TxOut with O(log(N)+log(M)) if you really want it -- but most of the time, it would be new nodes hopping on the network with imported wallets, and simply want to get their balance.  This tree structure takes that use case into account directly and doesn't leave a shred of uncertainty that they got the right answer.

Thanks Gladamas,

I have been checking the code and everything you said makes sense
(1) Good
(2) I just noticed I actually commented out the pickaxe code because of an issue exposing the correct information from the C++ code to the GUI.  I will work on doing that.
(3) I noticed some crashes with double-clicking on some types of transactions, so I put in a fix in 0.79.99.1.  Could you upgrade to the latest and tell me if it still crashes?
(4) That's what I would expect.  The C++ code is flagging it correctly (as unspendable), and thus won't return it in the "spendable" balance.  I just need to fix the ledger display it seems...

I will dig into the zero-confirmation issue a little bit more, today.  I have noticed it doesn't show zero-confirmation transactions in the balances, despite having them in the ledger.  I think I know where to look...

Thanks, that was really useful!

DiThi,

I see this from a different angle.  

(1) The tree-part of my proposal should be seen as an extension of yours.  I'm sure my idea was inspired from reading yours a long time ago.  The difference being that extra complexity is added to the tree structure to accommodate the most common use-case:  requesting address balances.  My tree structure guarantees that you can not only get any TxOut, but you can get all TxOuts for a given address/script and have no doubts that it's correct.

I believe this is a worthy trade-off, comared to your tree structure, as it removes a channel of uncertainty for the operator, and removes a channel for shenanigans from those who wish to deceive you.  And in the end, it's not actually that much more complicated.  It's simply more-tailored for the way that users need to access the network.

(2)  As echoed by others, I believe that a hard-forking blockchain change is going to only happen in the event of a crisis.  To do so requires more than democracy -- it will seriously impact the entire network in a detrimental way.  There are users who are still using version 0.3.X bitcoin clients not because they want to, but because it works, and they don't follow the forums or Bitcoin news or anything of the sort.  And the hard fork exposes them to all sorts of malicious behavior by others who would exploit their ignorance of current events and manipulate the abandoned chain that they are stuck on.

To maintain confidence in the system, a hard fork is going to need more than democracy -- it's going to need super-majority, probably 80-90% ... and gaining that level of consensus is pretty much impossible for new ideas that are not well-understood -- unless the idea has been in the wild, and in use for many months/years and is already used by 80%+ people.

The idea of using a second blockchain is actually a way of creating a "staging area" for such ideas on the main network (like galambo said) without actually risking exposing that network to any of the unforeseen issues that could arise.  It can be used to add such functionality to the network without actually changing the network.

In this way, the meta-chain can grow and develop as people start using it and understanding it.  People start building infrastructure on the availability of the information in that chain.  Once it has become ubiquitous enough and time-tested as a pillar of a part of the network, then you have 80%+ agreement amongst users without even having to ask for it.  At this point, a hard-fork is entirely feasible -- or at least orders of magnitude less disruptive.

You're right, it's not the only way, but I think it's about as good as it's going to get.

Ugh!  That's definitely not normal functioning.  What are your system specs?  1 GB of RAM?

It sounds like I better hold off on beta, and take the new blockchain stuff a bit further -- along with insta-loading between restarts.  Luckily, the changes I made are 95% of what I need to save an index to disk, or start saving this data into a DB engine.  I have been hesitant to pull a DB engine in, but it seems like now is the time.  (it will probably mean installing a new dependency on the offline system, though).

...

Thanks for being patient, guys.  This has turned out to be a more elusive problem than I originally thought it would be

Oh, yes I did!  Sorry I forgot to mention it.

Armory homedir:  "--datadir=Z:\newdir"
Satoshi homedir:  "--satoshi-datadir=Z:\newdir"

Okay, I have posted all four testing versions on the github download page.   I highlighted "four" because there are no longer different installers based on distro, only 32-bit vs 64-bit.  That's a lot easier for everyone...

Armory 0.79.99.1 Downloads Page

Please download them and check them out.  As far as I can tell, everything works as the previous versions have, but with the better blockchain utilities underneath.

One particular improvement I noticed, is that it doesn't have a problem "drinking from the firehose" anymore:  if the Satoshi client is still getting sync'd, Armory doesn't have a problem consuming all the new block data -- well maybe a little bit, but nothing like before.  I do need to add a warning or flag to identify that Bitcoin-qt is still sync'ing.

I have removed an warning in the GUI related to P2Pool, and made a minor bug/code change that might affect P2Pool display.  Still doesn't display coinbase transactions properly, but it looks like it at least won't try to spend them before 120 confirmations.  Can anyone verify that?

Also added "Help-->About".  Finally