This sort of a developer is dangerous to have developing Bitcoin's internal structures. I think it's better they stay away.
Which sort of developer? The one who revels in complexity, as though complexity breeds integrity? This guy is surely already busy on his first implementation of Bitcoin, in assembly language. He'll be done by 2017, assuming the architecture he's developing for is still popular enough that people will be able to run it. Or do you mean the one who walks away? And this benefits bitcoin because the fewer clients, the better? No, the developer you described clearly has no patience to test his code so that it works properly. We're better off without such developers. I'm not sure what you guys are talking about. If you disagree with meta-chain at all, then state it as such. Otherwise, this discussion is about two different mechanisms to achieve the same end result. My core argument is the the trie-based solution is much less complex overall, easier to implement and get right, and has numerous other benefits -- such as dead-simple rollbacks and the whole thing is parallelizable (different threads/CPUs/servers can maintain different sub-branches of a patricia tree, and report their results can easily be accumulated at the end -- this is not possible with BSTs). If you want to contribute to this discussion, then please do. |
|
|
|
By recommending a binary tree, or rather, a Merkle tree in the form most resembling a binary tree, I am suggesting that from block to block, the miner has the option of either just updating the tree (in a well-defined deterministic manner but leaving it unbalanced) or updating and rebalancing the tree such that all of the leaf nodes are the same distance (or distance-1) from the root, again in a well-defined deterministic manner.
I am not suggesting leaving the implementation up to the STL or any other form of library.
I don't believe Patricia trees are "simpler" when measured in the amount of human learning and neurons one must dedicate to understanding the concept. That doesn't mean I think it's too hard to learn, but rather, I doubt the cost (measured in terms of complexity of the specification) is worth the benefit.
If you tell a developer, "Now you've got to learn what a Patricia tree is", and then "Now that you've implemented it, you've got to simulate numerous cases of rollbacks to test and feel good that your implementation works backwards as well as forward" you have just made many more developers say "to hell with it, I'll develop something else".
... not to mention implementing a chain reorg strategy consisting of "now talk to your peers and start asking them for now-orphaned blocks (hopefully they have them still) so you can roll your tree back intact" rather than starting with a copy of the tree at or before the point in time of the split and rolling it forward.
Either way, the developer has to get into the implementation details of the data structure. They have to understand it. And really, neither structure is particularly complicated. Perhaps some devs are more familiar with BSTs. But to say that a miner "has the option" to rebalance -- that doesn't make sense. Any rebalancing operation on a BST will change the root hash. It must be determined from the start exactly when and how rebalance ops will happen. Or else everyone gets different answers. And as for the comment about "simulating numerous cases of rollbacks" -- This case is dramatically simpler with a patricia tree structure -- you just add and remove elements from the tree using standard insert & delete operations. It doesn't get much simpler than that (besides maybe keeping around the last few blocks worth of deleted TxOuts, which is probably a few kB). On the other hand, you may be talking about gigabytes of data to store "backups" or "snapshots" of the BST, just in order to accommodate the possibility of a rollback. And how many copies do you need to store? You can keep the last state of the tree, but what if there's a 2-block reorg? Well, now you need two copies. To handle arbitrary-sized rollbacks, you could really be thrashing your hard-drive, and in such a way that everything has changed while you were attempting to swap gigabytes of data around. |
|
|
|
Yes, it's possible to BSTs, but it's a lot of work. And it's not simple. To design this data structure around BSTs requires every implementer of the meta-chain to use this specific BST algorithm. There is no such ambiguity with Trie structures -- you could look them up in any textbook.
It's true that every implementer will need to use the same algorithm, otherwise the root hashes will be incompatible. And of course you can't just use a standard library map because those do not support computing hashes! But there are plenty of ambiguities involved in using tries. Here's an earlier quote from you where you mentioned an optimization using skip strings: In the Patricia/Hybrid Tree case, there are purely branch nodes and leaf nodes, though the branch nodes may have "skip strings". So a leaf node's hash value is just the root hash of the subtree. And a branch node's value is the hash of the concatenated skip string and its non-null child node values.
Surely if you use skip strings, that will change the root hash, so everyone would have to agree on the particular algorithm to use? Let's make several implementations, and evaluate which one is the best. "Skip strings" are part of the standard Patricia tree implementation. It just may be called something different in different texts. Either you use a Trie, Patricia tree, a De la Brandais tree, or a Hybrid tree. Once the correct one is agreed upon, the ambiguities in implementation shrink to basically nothing. It becomes a question of how to traverse and aggregate tree data for Bitcoin purposes, not how to implement the data structure. That's something that will have to be done for any data structure that is used. On the other hand, a red-black tree that is optimized differently, and thus produce different root hash, will still be called a red-black tree. To describe to someone what that optimization is, well, requires a description of the algorithm (and probably code samples). I know it's possible, I'm just pointing out the difficulties that could arise out of different people unknowingly producing different tree structures. Most likely, under bizarre conditions with complicated rebalance operations, and it would be remarkably frustrating to debug. I'm pointing all this out so that you can't say no progress is being made! Until someone from the 'trie' camp catches up, the simplest solution is a BST since some code for this already exists.
I do appreciate that you are doing this. I wish I had time for it. Perhaps your C++ implementation is sufficient for porting to other languages, so that such a uniform implementation can be achieved. Clearly, I'm still opposed to it for other reasons (like necessitating backups/snapshots for re-orgs), but you can still accomplish what is needed. And I hope that we can hit all the snags and start figuring them out sooner than later. The claim "This just won't be possible using BST's, though." is plain false. It confuses the data structure and algorithm with their implementation. This gotta be some sort of miscommunication, or maybe the author had too much fun at a party yesterday.
Perhaps you misunderstood me. I was saying it won't be possible for everyone to agree on the root hash unless they use the exact same implementation. Standard implementations (such as STL map<>) are standardized only in run-time, not underlying structure. Thus, a widespread "experiment" using BSTs won't be simple without a uniform implementation across all languages, etc. This may be a lot of work. However, if it was tries, I consider it quite simple that anyone can download any [correct] trie implementation from anywhere, and know that they can get the same answer. Because the structure is guaranteed. |
|
|
|
I know it's been a while since this topic has been visited, but I'd like to make a proposal here:
Rather than settle on the "best" way to implement this tree, how about settle on the "simplest", so that way the community can catch the bug and start cranking their brains on the best way to implement this tree with the right balance of features and complexity when the time comes to consider making it part of the protocol standard.
By "simplest", I mean implemented as follows:
1. A simple binary tree that starts out balanced, but maintaining the balancing from block to block is optional. A miner has the choice to rebalance the tree for the next block, but doesn't have to. The lack of a requirement to keep the tree balanced is meant as an effort to discourage mining empty blocks because a miner doesn't want the CPU burden or any delay associated with rebuilding the whole tree with each incoming transaction.
2. No ability to roll back. Rolling back must be accomplished either by rebuilding the tree from scratch, or by starting with a known good backup and rolling it forward. Backups are systematically deleted such that the backup burden grows O(log n) relative to the total block height. More specifically, the backup of any given block's tree should have a lifetime of 2^n blocks where n is the number of contiguous zero bits at the end of the block height. Block 0x7890's tree backup should last sixteen blocks because 0x7890 ends in four zero bits. The backup for the tree of block 0x10000 should last 0x10000 blocks.
Now, why would I suggest a methodology that clearly avoids taking advantage of features that would make a "better mousetrap" so to speak? Here are the most prominent reasons:
1. At some point, the Bitcoin community may come to a consensus that we should redefine a valid Bitcoin block to incorporate the root hash of a valid meta-tree rather than having it be optional coinbase clutter. Until then, this is merely an optional performance-enhancing and usability-enhancing feature without any hard commitment to a standard. We should help people understand the base case for what it is, and then move on to derivative cases that do the job better.
2. There is serious value in simplicity. The more things are needlessly complex, the higher the barrier to entry for new developers of bitcoin software. We are at a point where we need more developers on board than we need the disk space saved by what would be (for the current block height and all block heights for the foreseeable future) about 20 backups of the meta tree on each user's disk. Besides being much more difficult for the average developer to understand, requiring a tree that must do a moonwalk during a rare edge case which is very difficult for a developer to reproduce and test makes for an exploitable danger that implementations may fail to do the right thing when the right thing is needed the most.
3. The Bitcoin community could use the lessons learned in a basic "proof of concept" implementation of this without being committed to any specific methodology for optimizing it. This will help the community at large understand which use cases evolve from the availability of the tree, and then come to an intelligent consensus as to what features and attributes of a meta tree are the most valuable and which bargains of complexity versus power are worth making.
I generally approve of the idea of prototyping the meta-chain CONOPs, and let people/devs start thrashing out how to use it, how to improve it etc. However, if you're arguing for simplicity, then you must use the Trie/Patricia/De la Brandais tree. There is no need for snapshotting/backups. Put the data in. If a block has to be rolled back, remove them from the tree. For a given snapshot in time, all Trie-based implementations will agree. It's part of their design. This just won't be possible using BST's, though. It's not a matter of preference, it's a matter of standardization. If you use BST, you might be inclined to use STL map<a,b> in C++, or similar implementation in Java, etc. But the map<> data structure will be designed/optimized different for each architecture, compiler, and OS. There's no guarantee that a BST in Linux using gcc 4.3 will even match the BST implementation in Linux gcc 4.8 -- they might've changed the BST implementation under-the-hood, optimizing the rebalancing operations differently. And you'd never know, because underlying tree structure is not specified in the C++ standard for map<>. Only the expected run times of insert/delete/query/etc. So, miners won't be able to agree on the root hash unless they all build the BST exactly the same way, so they must agree on the BST algorithm to use. Who's writing that implementation? Will they create an implementation of the exact same algorithm in C, Java, C++, haskell, etc? This is why I keep pushing Trie-based algorithms -- any implementation of the Trie (or whatever variant is agreed upon) will work. A trie that is implemented in C++ by someone in China can be used to produce the same root hash as a Java implementation written by some kid in his basement in Idaho (assuming the implementations are correct). Yes, it's possible to BSTs, but it's a lot of work. And it's not simple. To design this data structure around BSTs requires every implementer of the meta-chain to use this specific BST algorithm. There is no such ambiguity with Trie structures -- you could look them up in any textbook. So, I agree that we should do this. It needs to be done and I think something like this is ultimately the future of BTC (especially lite nodes). If only I could get all my other priorities in Armory finished, then I would be focusing on this. |
|
|
|
reinstalled after deletion but now Armory just stuck on splash screen. win 7. 0.7.1 satoshi.
blockchain up to date.
wtf!? I'm surprised it doesn't at least open the main window... Can you check the C:\Users\<username>\Roaming\Armory\armorylog.txt file for me? Skip right to the end and look for error messages. Or email it to me (it's the same thing you get if you were to go to "File->Export Log File" from the main window.
Bug confirmedAfter inducing a one-hour blockchain load time, I got the same problem as OpenYourEyes... and additionally get to see all the errors from the C++ code that don't normally make it into the log file (redirecting it would be a PITA). Errors complaining about new blocks being orphans... I guess my work is cut out for me today! At least I can reproduce it! |
|
|
|
I can add that there is definitely some kind of race condition when it comes to Armory reading the blockchain database while the Satoshi client writes to it. I have several times seen Armory crash in that situation. It typically happens when the Satoshi client is catching up, and I start Armory while this is happening. Then suddenly Armory crashes. But it is rare, I cannot reproduce it on demand, and I was stupid enough not to save info about the crash (not that it seemed particularly informative, I think it was just a segfault with no info about where in the code it happened).
Definitely, Armory doesn't like "drinking from the firehose" if Bitcoin-Qt is still updating (and 0.84.1 will detect this condition and produce a warning). I'm about to run off for an hour, so I put a one-hour sleep command after my load-blockchain call in my code, to try to guarantee there is a new block by the time it "finishes" scanning. I haven't had time to hunt down the code path, but at least if I can reproduce what OpenYourEyes was seeing, that's a great start. so i just downloaded 0.84. upon launch i get this error: the specified module could not be found. LoadLibrary (pythondll) failed.
also something about python27.dll error
Bizarre. Can you try manually deleting "C:\Program Files (x86)\Armory" and then reinstall? Of course, I just had my first crash of Armory in Windows, after it was running for about a day! Gah, everything looks so good, then starts falling apart! that won't erase any wallet data will it? i migrated in a satoshi wallet. Wallets are stored in C:\Users\<username>\AppData\Roaming\Armory. You can manually back them up to another directory to be sure. But it's intentionally kept separate so that you can install/upgrade/uninstall without affecting the wallets. |
|
|
|
I can add that there is definitely some kind of race condition when it comes to Armory reading the blockchain database while the Satoshi client writes to it. I have several times seen Armory crash in that situation. It typically happens when the Satoshi client is catching up, and I start Armory while this is happening. Then suddenly Armory crashes. But it is rare, I cannot reproduce it on demand, and I was stupid enough not to save info about the crash (not that it seemed particularly informative, I think it was just a segfault with no info about where in the code it happened).
Definitely, Armory doesn't like "drinking from the firehose" if Bitcoin-Qt is still updating (and 0.84.1 will detect this condition and produce a warning). I'm about to run off for an hour, so I put a one-hour sleep command after my load-blockchain call in my code, to try to guarantee there is a new block by the time it "finishes" scanning. I haven't had time to hunt down the code path, but at least if I can reproduce what OpenYourEyes was seeing, that's a great start. so i just downloaded 0.84. upon launch i get this error: the specified module could not be found. LoadLibrary (pythondll) failed.
also something about python27.dll error
Bizarre. Can you try manually deleting "C:\Program Files (x86)\Armory" and then reinstall? Of course, I just had my first crash of Armory in Windows, after it was running for about a day! Gah, everything looks so good, then starts falling apart! |
|
|
|
Btw what happens when bitcoind receives a new block in the middle of armory's scanning at startup?
Nothing. Armory will continue scanning the blkxxxx.dat files as they were before the new block was received, and Armory will still consider the end of the previous block to be the end of the file. Once Armory is done scanning, it will find the new block on the first "heartbeat" (every 1s) and update itself accordingly. In the past hour or so, I've been trying to pin down the bug I mentioned previously, opening and closing armory in between deaths (5-10 minutes interval) in Kingdom Rush game. I've observed conclusively that armory does not re-sync afterwards when a new block is received by bitcoind in the middle of the scan at startup. If it were truly skipping that block, then the first block it would receive after the scan would be two higher than the top block, and appear to be an orphan. This would be an excellent explanation for what OpenYourEyes is seeing when running Armory. It doesn't explain why I've never run into it, though... I'll do some tracing on my own to see if can find a faulty code path. I'm afraid it might be an OS-specific bug -- as I've started Armory, literally, more than 100 times in the last week and never witnessed this. Or maybe I just never noticed (or my system scans the blockchain too fast for it to ever happen to me!) |
|
|
|
Btw what happens when bitcoind receives a new block in the middle of armory's scanning at startup?
Nothing. Armory will continue scanning the blkxxxx.dat files as they were before the new block was received, and Armory will still consider the end of the previous block to be the end of the file. Once Armory is done scanning, it will find the new block on the first "heartbeat" (every 1s) and update itself accordingly. |
|
|
|
By the way, if you don't mind re-downloading the blockchain in Bitcoin-Qt, I would appreciate you trying that.
I'll certainly do that, it probably won't be for a few days though as it takes close to two days to download the blockchain on my laptop. Could it be an issue of me no leaving enough time between starting bitcoind and then armory? I normally start bitcoind, wait 20-30 seconds and then start armory. Just started up armory and again it was stuck on not having the correct block number. with the same repative error messages present in log that you pointed out), so I restarted armory and it's working fine. 2012-11-03 22:17 (INFO) -- ArmoryQt.py:2339 - New Block! : 206103
2012-11-03 22:17 (INFO) -- ArmoryQt.py:2339 - New Block! : 206103
2012-11-03 22:17 (ERROR) -- armoryengine.py:9143 - ***Connection to Satoshi client LOST! Attempting to reconnect...
2012-11-03 22:17 (INFO) -- ArmoryQt.py:2339 - New Block! : 206103
2012-11-03 22:17 (INFO) -- ArmoryQt.py:2339 - New Block! : 206103
It might be best to start bitcoin, wait until you stop downloading blocks, then start armory. If you need to download a few hours worth of blocks, waiting 30 seconds is definitely not enough. Especially if the blockchain normally takes days to download. Red Emerald, if you look at those info lines, you'll notice that all the block numbers are the same. That means that something truly wacky is going on with his system: it is detecting new blocks in the blkxxxx.dat files, but concludes that none of them extend the main chain (hence, Armory believes that block 206103 is always the top block even after reading newer blocks). That's not a download issue, that's a real WTF issue. One I haven't seen before... |
|
|
|
I guess it's a testament to the fragility of multi-threaded programming (or my own implementation of it).
I am amazed what you can do with multithreading in Python. Python is a fantastic language, but multithreading is definitely not one of its strengths, with stuff like the "global interpreter lock" etc coming in the way. I am impressed! "Multi-threading" is actually fairly easy to use in Python (doing it "correctly" is another story). The problem with the GIL is more related to computational efficiency: if I have two compute-heavy tasks, the GIL is not actually helping me parallelize them, and in fact may complicate and slow things down. However, parallelizing computation is not the goal here: it's to make sure there is CPU devoted to managing the GUI while the block data mgr is doing its thing. In this sense , Python threading is actually quite good (separating the user context from the compute context). Overall, I've had a very good experience with Python multi-threading, but a rough experience with the general concept of converting a complicated single-threaded app into a multi-threaded, server-client type of application (the BlockDataManager is the server, the GUI is the client). I'm so glad it's done now... |
|
|
|
I use Armory from git, which branch should I be testing?
Use the "threading" branch. Although, I have been committing some updates directly to the threading so you are probably going to get a few more features than the others testing the installers I released (but hopefully no extra bugs!) I just build the threading branch under Mac OS X Mountain Lion. It is the first version of Armory that builds completely without any modification to the Makefile. It is very nice that it starts right away! I have only tried it very lightly (moved a few BTC between wallets), but so far it looks good! Great work, Mr. -1  After some complaining/suggestions from Red Emerald, I was able to add a OS-detection branch to the Makefile that applies the necessary mods for Mac. Unfortunately, I haven't yet figured out how to distribute for OSX, but at least it's easier to build manually. And I must say that I'm thrilled that it's working for everyone: including the OSX users! It's amazing how discouraged I was a month ago when everything was falling apart and seg faulting. But then I found that one bug that was throwing everything out of sync, and now it seems pretty darned stable. I guess it's a testament to the fragility of multi-threaded programming (or my own implementation of it). So, only a couple more subtle features before 0.84.1. This will probably be one of those "official" releases that ends up being followed the next week by a bug-fix release. That bug-fix release will be 0.85-beta. I have decreed it be time for beta! Any last requests? (small suggestions only, please... I'm not going to do anything crazy before beta). I think one of the first things after beta will be the new, universal wallet format. It will support compressed public keys (and thus, importing Satoshi wallets), hierarchical deterministic wallets, sub-wallets, linked wallets (for multi-sig and split-keys), much faster, merging wallets, and external comment/script store. It will be a slow upgrade, but will open up a lot of opportunities to expand what Armory is capable of (like multi-sig!). |
|
|
|
I use Armory from git, which branch should I be testing?
Use the "threading" branch. Although, I have been committing some updates directly to the threading so you are probably going to get a few more features than the others testing the installers I released (but hopefully no extra bugs!) |
|
|
|
0.84 will have a way to tell Armory to use online mode even if you don't detect internet. yaaaay! I have a slow, intermittent connection at home, anymore, and would have to boot Armory 3-10 times before it'd recognize the connection. Oh, please test it for me (the 0.84 downloads from above). Run with " --skip-online-check". |
|
|
|
(and yes, I know that Armory asks for the chain to be synced before being opened, but I figured I'd try it this way and see how/if it could handle it.  ) I had thought about adding a way to detect if Bitcoin-Qt itself is not synchronized... I just hadn't considered it worth the effort, yet. But maybe it is, especially now that I'm in "polish" mode and that's a common situation for users to get themselves confused. |
|
|
|
BUMP! Seriously, has no one tried the new version!? I'm anxious to find out if it works for everyone else as well as it's working for me! (which is pretty good) Also, if there are any other small/aesthetic things you'd like to see, please let me know. I just added a "busy" icon that spins while the blockchain is scanning, and added some checkboxes to filter addresses on the wallet window ("Hide Change Addresses", "Hide Unused", and "Hide Empty Addresses"). That seems to be a popular request these days... I also tweaked the menus so it's a little easier to find the "Import" and "Sweep" functions (mainly just directions for what to do). Lastly, a caveat about the aesthetics of the new version on Windows: apparently there is a Qt (PyQt?) bug in Windows such that the QTabWidget -- as used on the main window to separate "Dashboard" from "Transactions" -- does not follow the color scheme for the rest of the application. In fact, the bug is stupid enough that I can't even manually set the background color without causing all sorts of other problems. I don't know what the solution is, but I'm afraid I'll have to leave the dashboard as that ugly white for now  (Windows only) |
|
|
|
Testing call for Armory version 0.84-alpha-almost-beta!
I ironed out enough bugs that I think it's ready for other people to try it. Unfortunately, Armory now has so many features, that it's overwhelming to even try to test every condition myself. So, sometimes it seems like stupid things slip by me, but I have no other way. I really need people to just install and use it, and report when abnormal behavior occurs! I have 64-bit builds available: Windows 64-bit Installer Debian/Ubuntu 64-bit .deb PackageThis update has full multi-threading support, allowing you to do wallet management and generate addresses, etc, while the blockchain is being scanned. It even handles bizarre situations like when you initiate a key import, and then try to restore a paper backup before the import rescan is done. It got really complicated, but I think I ironed out the bulk of the details, and not many more to go! While people help me test, I'll work on getting some kind of progress bar or animation for display while the blockchain is scanning. Although, even without it, this is a pretty dramatic improvement! And if it does work, please let me know that too. I usually only hear bug reports, but it's good to know if people have good experiences with it, too The screenshots are essentially the same as before... but I think it actually works, now 
|
|
|
|
|
Not sure it matters anymore, but I did program an ECDSA calculator into Armory, under "Tools->EC Calculator". You can multiply scalars mod N (where N is the modulus of the secp256k1 curve), point-addition, and scalar-point multiplication. It works for doing shared keys like you talk about it your thread on 2-factor physical coins: you can start Armory in offline mode, create a new wallet, create two addresses, copy&paste the private and public keys, then plug them into the calculator using scalar-point multiplication and verify that A*B' == A'*B. Then calculate A*B and A*B*G to see that you get what you expect.
|
|
|
|
There are idiots out there that still disables UAC on WinVI or Win7 computers. The UAC actually is good security feature, with UAC disabled the malware can more easily Goatse the computer and data.
Can Armory be rewritten in proper programming language like C/C++ ? This will help a lot avoiding such stupid behavior like py2exe does. TorChat had similar problems with permissions in past.
Sorry, part of the reason Armory exists and is [generally] robust is because of the fluidity of python. The flexibility of passing data around, catching errors, accommodating corner cases, and networking... gives at least a 100% boost to development speed. And keeps me sane. FYI, all the Blockchain utilities are written in C++. 10,000 lines of C++. But you couldn't pay me any amount of money to convert the 15k-20k lines of python to C++... |
|
|
|
Shouldn't armory be writing the log to the User Data folder, not the Program Files folder? On Windows7 Program Files need administrator access.
I do write my log file to the user AppData directory, but py2exe has a mind of its own (the program that converts python scripts into Windows executables). It injects its own logging system into the exe, and if there are errors in the app, it writes them to the same dir as the .exe. I don't actually use that log file for anything, and don't need it, but I haven't figured out how to disable it without disabling other stuff I want to keep. And until now, I guess most users were priveleged users that could create the .exe.log file without problem... |
|
|
|
|
Show Posts
