I have a question about the security of the deterministic wallet algorithm of Armory. Is it possible to deduce the private key(s) of other addresses in the same wallet in the following situation?
1. Knowing private key of one of the addresses in a wallet
2. Knowing private keys of many addresses in a wallet
3. Knowing private key of one of the addresses in a wallet, and having the watch-only wallet
4. Knowing private keys of many addresses in a wallet, and having the watch-only wallet
For example, Alice shares a watch-only copy of her wallet with Bob, and she also needs to share private keys of some addresses with Bob. Could Bob deduce the the private keys of other addresses in Alice's wallet?
Each wallet is based on base public-private keypair, and a single chaincode. With PublicKey(n) and the chaincode, you can calculate PublicKey(n+1). Thus you can compute all PublicKey(i) where i>n. Therefore, a watching-only wallet consists of just PublicKey(0) and the chaincode. The same goes for PrivateKeys. If you have PrivateKey(n) and the chaincode (which is the same code for both public and private chains), you can compute PrivateKey(n+1). Thus, the full wallet is just PrivateKey(0) and the chaincode. It seems that your (1) and (2) above assume the person does not have the chaincode to your wallet, (3) and (4) assumes they do. I would be hesitant to assume they don't have the chaincode because it is always on your computer unencrypted, so it's vulnerable. Or in some cases you may have given away your watching-only wallet. Either way, here's a more direct answer: (1) No other private keys are compromised (2) No other private keys are compromised (3) All PrivateKeys(i>n) are compromised. Previous keys are not. (4) All PrivateKeys(i>min(n)) are compromised, where min(n) is the lowest of the many keys. This will pretty much be the same with the new wallet format, too. |
|
|
|
I didn't mention it anywhere, but here is my absolute top 4 priorities: (1) New blockchain mgmt tools : Armory is going to stop working soon without it! Also, it will enable WinXP-32bit support and should reduce system requirements even further! BETA! (2) The new blockchain tools will also make it easier to save indexing info between loads to avoid the full scan and long load times. I liked the full scan because it added a statelessness to Armory that guaranteed everything would work if you just restart, and I didn't need to do anything... but the blockchain is getting too big to keep that solution. (3) Coin control: this actually won't be terribly hard: the Armory codebase is already set up to handle it, I just need to make a GUI for it and test it. This wasn't going to be a top priority, but I've reached a critical threshold of requests  (4) New wallet format -- will include ability to import Satoshi 0.6.0+ wallets and will use the same algorithm as the Bitcoin-Qt devs are going to implement in an upcoming release. It will not only be faster, it will support arbitrary-dimensional wallets: you can have all your wallets created from a single seed, or create subwallets, etc. This is 1/3 done but had to quit because I didn't want to hold up the beta release... Then... I will have to make a decision about whether to tackle independent networking or multi-signature transactions. I'm tempted to do multi-sig, because, while Armory remains a tool for advanced users, advanced users can handle the Bitcoin-Qt dependency (but they don't have to be happy about it). However, one of my original goals was to pioneer multi-sig interfaces, and it is something severely lacking from the community... I'm happy to receive feedback about this. I think multi-sig will come before networking independence, so that everyone has everything! Then, with network-independence, I can stop adding new features and focus on interface design and the standard-usermode. Possibly even a lightweight mode. |
|
|
|
|
Anyone have any comments about 0.77? Given the lack of response to it, I suspect either no one is using it, or there are no complaints. Either way, it's about time to release it, because I'm positive there are some users out there suffering (or stopped using) due to the table-sorting bug.
|
|
|
|
|
Oh, I apologize. I started reading the thread and it looked like the same proposals I've seen before where both parties just compute the DHSS value with private*public and use that as the public key -- requiring one person to have both private keys to be able to spend it. One party reveals their private key to allow the other party to redeem it.
Your technique is definitely an improvement. And you're right about the anonymity: standard multi-sig transactions (BIP 16) reveal both original addresses when the coins are redeemed.
|
|
|
|
FYI, this topic has been discussed in a few different contexts, such as in this thread. Obviously, multi-signature transactions are built into the network, so this kind of ECDSA magic is unnecessary, at least for simple 2-of-2 transactions. Also, the 2-of-2 using ECDSA as you described requires one party to compromise their own private key to allow the other party to claim the entire encumbered amount. There's no way to, say, split the money that is locked in the 2-of-2 transaction without one party trusting another. Also, I don't like the idea of having wallets where some private keys are supposed to be revealed, while it's an epic fail for other keys to be revealed. It works for Casascius physical Bitcoins, but I have personally decided it's not a good idea for general usage. On top of that, I believe that being able to split the encumbered money is important: I am firm believer that both parties need a "risk deposit." That the initial 2-of-2 fund is seeded with, say, 20% of the transaction value from both parties (can do more or less depending on how much the parties don't trust each other). At the end of the transaction, if everything went as planned, both parties get their risk deposit back -- Alice puts in 1.2X and Bob puts in 0.2X; at the end of the exchange, they both sign a tx sending 0.2X to Alice, 1.2X to Bob. But if it doesn't go smoothly, then both parties lose their deposit and the tx money. Therefore, there is every incentive for both parties to resolve the transaction agreeably. This avoids: (1) Lazy Alice: Alice receives the goods but then is too lazy to sign the transaction completing the transfer to Bob (or in your case, sending the private key to Bob). She might do this maliciously if she is disatisfied with the product, and if she has no risk deposit, it costs her nothing to screw over Bob. (2) Prankster Bob: Bob advertises that he has products to sell with no intention of selling anything. Alice puts 100 BTC into a 2-of-2 tx, and then Bob disappears leaving the money stranded. Or Bob comes back and offers to split the money with her, since she'll get nothing back if she doesn't agree. Etc. With a risk deposit, Bob has to put his own money into the tx to demonstrate that he is serious about the transaction. And using special hash codes, it's possible for both Alice and Bob to inject the money "simultaneously" so that neither party risks putting money in before the other. (3) The risk deposit could serve as a pre-paid fee for third-party arbitration, if a third-party was included on the transaction. A common agreement might be that third-party Charles, might arbitrate any transaction that has at least 10% risk deposit from both parties. Charles takes that 20% as its fee only if arbitration is needed. Gavin doesn't like the idea of coins being lost, and thinks there should be a MAD option (mutually assured destruction), to allow the coins to be recycled if things go awry. I'm still not entirely convinced that's necessary, but it's not a bad idea. I guess we never actually resolved "the best way" to do this... |
|
|
|
The server for thin clients (see my post above) would have to be scaled to deal with this problem, I agree.
My impression is processors can do 1,000's of ECDSA-DHSS per second today. I bet if you cared enough about this to dedicate processing to it, available processing power would keep up with total transactions.
As long as miners can keep up with regular transactions, Wikileaks should be able to deploy a server that can keep up as well.
But my point was, that the usefulness of this solution is limited to isolated cases (which are still useful cases). Sure you can do 1,000 ECDSA ops per second, but if there are 1,000 addresses in your wallet and any of them could be used in an address-extension like this, you're at 100% CPU just to check 1 tx per second. And we know 1 tx per second is nothing compared to the desired adoptance of Bitcoin. The math doesn't have to add up exactly (who has 1,000 addresses in their wallet?) but the point is it's entirely possible for network volume to overwhelm even powerful computers, which puts the whole idea on shaky grounds. I actually really like the idea for wikileaks, political dissidents, or internet gambling, if they use a single public address and dedicate systems to it... but outside of that very niche market, I don't see it working. |
|
|
|
I think the idea is awesome and elegant and completely in the spirit of Bitcoin. But it's not scalable  Not true. Miners would not have to change to implement this. This is independent of the current implementation in that the regular client does not have to change if this is implemented by some clients. Those clients willing to do the checking could implement this no problem. I didn't say it would have to be done by miners. I implied that doing ECDSA-DHSS calculations on 1+ million transactions per hour is not feasible. There's not 1 million tx/hour right now, but with any degree of success in the Bitcoin world, even having a single address which you know might be used for this kind of address extension will cause you to have to do at least 1 million ECDSA ops per hour. That's a lot of electricity, just to find out if someone sent you money. And that's only for one address. Now you have to do one ECDSA-DHSS calculation for every address in your wallet on every tx, at least the ones that you suspect might be used for this kind of key extension. For an organization like wikileaks which could post a single address once and dedicate a server to searching for incoming transactions, it makes sense. But I don't see it working for regular users in the future... |
|
|
|
This was originally proposed by ByteCoin, and then I tried to expand on it in a super-complicated way that would reduce the how much of the blockchain would have to be searched for such transactions. In the end, I think the idea ultimately works, but only if Bitcoin doesn't catch on... it's just way too costly when simple blockchain verification will be difficult to execute, much less additional ECDSA ops on each tx to look for a multitude of potential receiving addresses. I think the idea is awesome and elegant and completely in the spirit of Bitcoin. But it's not scalable By the way, the concept of a*(b*G) == b*(a*G) is also known as "Diffie-Hellman Shared Secret". It is frequently used for key exchange: you use each others' public keys to derive a shared secret which you then use as, say, an AES key for encrypting further communications. There's actually a lot of cool and creative things you can do with DHSS, like creating pseudo-multi-signature addresses. |
|
|
|
So I'm running the latest git, but it still says .76. Shouldn't it be .77? It's also always sitting at 98% CPU and being really unresponsive It looks like you have a check to google.com to see if the network is up. Problem is, all my connections on this test system are proxied through Tor and sometimes google blocks Tor exit nodes so I get a socket timeout from line 729 of ArmoryQt.py in setupNetworking Side note: The blockchain loaded in 90 seconds. Outside of a VM (on the host) it loads in about 60. To run from git, you need to switch to the "tablesortingfix" branch. I will merge the code into master once I'm ready to "release" it. And yes, I know it's slowing down. The acceleration of blockchain size has me scrambling to get some major things updated sooner rather than later. Unfortunately, I'm just not there yet. :-/ Oh okay. I'll switch branches and test it out. As for "google.com", I also check microsoft.com ... I don't suppose that helps? I figured that was a reliable way to determine if you have a connection to the outside world, but I guess it isn't. Recommendations?
Is there any use case for having internet but no connection to bitcoind? If not, how about this pseudo-code: if bitcoind_available():
if bitcoind_rpc('getconnectioncount'):
echo 'online mode'
else:
echo 'Satoshi found, but it has no connections. Falling back to offline mode.'
else:
echo 'offline mode'
I think this would work and should be easy enough to implement. Interesting idea. You're right there is no use cases I'm aware of for using Satoshi client if it's not connected to any peers. However, I've never accessed bitcoind via RPC, I didn't even know there was a way to query the number of connections. I assumed that if google/MS was ping-able, then the Satoshi client is at least capable of having peers. It seems that that assumption is not the case. I don't suppose that connectioncount is something I can query peer-to-peer? Doesn't seem like it, but I also don't want to have to open another network connection just for this purpose... |
|
|
|
I actually meant "weighted majority" of CPUs -- I recognize that not all CPUs can use compatible instruction sets. However, a majority of users are using CPUs that have a common instruction set. I was under the impression that multiple instruction sets are generally supported on each CPU, hence "SSE", "SSE2", "3DNOW", etc. Given that I've seen large lists like that on CPU spec pages/boxes before, I suspect it's the case...
MMX, SSE, 3DNow!, etc are not instruction sets in their own right, but rather extensions of the standard IA-32 instruction set (this is the common instruction set for x86-32 CPUs). Any code which is compiled to use these extensions will not work on any CPU with an instruction set that doesn't include these extensions. As I understand, it is possible (in assembly) to write two versions of a function (one using the extended instructions and one using the just the standard instruction set) and have the program select which version to use by querying the CPU at runtime, but that's far beyond my level of expertise. Note that this is only possible because these extended instruction sets simply add new instructions without replacing or changing the standard instructions. Either way, I removed the -march option and it seems to work. The documentation suggests that gcc will decide for me what to compile, which is not march=native. Maybe I still have no idea what I'm talking about, but I'm going with what works. So far the python2.6-i386 works after the change. Please try the others and let me know.
Are you sure it works, though? On all IA-32 systems? Unless you're absolutely positive the default is safe, -march=i386 is the only way to be sure. Compiling for any other architecture is very likely to result in a binary that is guaranteed to crash on certain systems. No, I'm not sure it works on all systems. But I never had a complaint when using march=native, which should be the least-compitible compilation option. The fact that the gcc documentation says that leaving out the -march= option will pick some default of the year is probably exactly what I want. I think it picks i386 for 32-bit systems and k8 for 64-bit? I'm not totally sure. But it's better than what I had before without having to fill an evening learning about architectures and compilers. I will take your advice and look into what I should be using. But as I said, the documentation suggests that not specifying the option usually causes it to pick a versatile one, and likely to be appropriate for the popular CPUs of the time that the gcc version was released. Are you recommending i386 for all systems, or just the 32-bit systems? |
|
|
|
So I'm running the latest git, but it still says .76. Shouldn't it be .77? It's also always sitting at 98% CPU and being really unresponsive It looks like you have a check to google.com to see if the network is up. Problem is, all my connections on this test system are proxied through Tor and sometimes google blocks Tor exit nodes so I get a socket timeout from line 729 of ArmoryQt.py in setupNetworking Side note: The blockchain loaded in 90 seconds. Outside of a VM (on the host) it loads in about 60. To run from git, you need to switch to the "tablesortingfix" branch. I will merge the code into master once I'm ready to "release" it. And yes, I know it's slowing down. The acceleration of blockchain size has me scrambling to get some major things updated sooner rather than later. Unfortunately, I'm just not there yet. :-/ As for "google.com", I also check microsoft.com ... I don't suppose that helps? I figured that was a reliable way to determine if you have a connection to the outside world, but I guess it isn't. Recommendations? |
|
|
|
I see there is no -march=generic option, which is unfortunate because I figured there would be an instruction set that is supported by a majority of CPUs.
If you think for a moment about what a CPU is and how it works, you'll realise what you're suggesting makes absolutely no sense. Every CPU has a single instruction set, and cannot use any other. IA-32 (i386) is a subset of all the various instruction sets used in x86-32 CPUs, and that's about a close as you're ever going to get to one instruction set being supported by a majority of CPUs. The instruction sets of other CPUs such as PowerPC, ARM, et al, are all totally incompatible with each other and with IA-32, so there's absolutely no way to compile code so that it works on all of them. It looks like, just not using the -march option at all is what I want, and -mtune=generic.
Actually, that may be what broke it in the first place. Specifying the target architecture is mandatory for the above reason. If you don't, the compiler will use the system default, which may not always be what you want. You must always specify what architecture you're compiling for if you want it to work on systems other than your own. I strongly recommend that you use -march=i386 -mtune=generic to avoid any future surprises. -mtune doesn't actually have anything to do with what instruction set your target architecture uses - instead it just optimises your code for things like the cache size of a particular CPU and so on. Setting it to the wrong CPU (even a CPU that doesn't use the same instruction set as the one you're compiling for) won't ever break anything, but it can have a detrimental effect on your code's performance. Always set it to "generic" unless you have a specific CPU in mind. Does this also mean that I can use "-march=i386 -m32" to compile the 32-bit binaries on my 64-bit system? It would be nice to be able to cross-compile, but I never bothered to figure out how, and have a separate VM for each .deb file...
I've never cross-compiled either, but yes, that should work. Let me know how it goes. I actually meant "weighted majority" of CPUs -- I recognize that not all CPUs can use compatible instruction sets. However, a majority of users are using CPUs that have a common instruction set. I was under the impression that multiple instruction sets are generally supported on each CPU, hence "SSE", "SSE2", "3DNOW", etc. Given that I've seen large lists like that on CPU spec pages/boxes before, I suspect it's the case... Either way, I removed the -march option and it seems to work. The documentation suggests that gcc will decide for me what to compile, which is not march=native. Maybe I still have no idea what I'm talking about, but I'm going with what works. So far the python2.6-i386 works after the change. Please try the others and let me know. |
|
|
|
Um, you guys do realise that i686 is actually a 36-bit architecture and is guaranteed not to work on a 32-bit system (or a VM that emulates one), right? 32-bit binaries should be compiled for i386 only. That's the standard architecture for IA-32 systems; the i[456]86 architectures are CPU-specific and should generally not be used without a good reason.
Makefiles and compiling issues are not my strongest skillset. Perhaps you can help me/us figure out what the problem might be...? I'm about to revert the crypto++ updates made in 0.76 to see if that resolves the issue. That will cause anyone using gcc 4.7+ to no longer be able to compile it, but I suppose I can maintain a gcc4.7 branch that follows the master with only the changes needed. So, any recommendations? It's not my strong suit either, I just have enough experience with Linux programs whose installation instructions consist entirely of "Run make and fix compilation errors" to have some idea of what I'm doing in that area. First of all, don't use -march=native when compiling binaries for general distribution! I don't know about Ubuntu, but most "32-bit" distros these days actually use the P6 architecture instead of i386, which has the advantage of allowing you to use up to 64GB of RAM with a supposedly 32-bit CPU, but the disadvantage that code compiled for such a system will flat out not work on a true 32-bit system. You should be using -march=i386 for IA-32 and -march=k8 (er, I think...) for AMD64 (as well as -mtune=generic, though omitting it won't cause any errors, but may (or may not) have an effect on performance). That should at least fix the "Illegal instruction" issue, which is almost certainly caused by accidentally compiling for a CPU-specific architecture. Okay, I just started reading up on it, and I see what's going on. Doesn't explain why it used to work then suddenly stopped working, but it sounds like was lucky that it ever worked! Also explains why reverting the changes didn't help. I see there is no -march=generic option, which is unfortunate because I figured there would be an instruction set that is supported by a majority of CPUs. It looks like, just not using the -march option at all is what I want, and -mtune=generic. Does this also mean that I can use "-march=i386 -m32" to compile the 32-bit binaries on my 64-bit system? It would be nice to be able to cross-compile, but I never bothered to figure out how, and have a separate VM for each .deb file... |
|
|
|
Um, you guys do realise that i686 is actually a 36-bit architecture and is guaranteed not to work on a 32-bit system (or a VM that emulates one), right? 32-bit binaries should be compiled for i386 only. That's the standard architecture for IA-32 systems; the i[456]86 architectures are CPU-specific and should generally not be used without a good reason.
Makefiles and compiling issues are not my strongest skillset. Perhaps you can help me/us figure out what the problem might be...? I'm about to revert the crypto++ updates made in 0.76 to see if that resolves the issue. That will cause anyone using gcc 4.7+ to no longer be able to compile it, but I suppose I can maintain a gcc4.7 branch that follows the master with only the changes needed. So, any recommendations? |
|
|
|
just got a little closer: Makefile of cryptopp has "-march=native" compiler option so that gcc will generate code for you local platform. Depending on what machine you're on, you might easily generate non-i[3456]86-compatible code.
I'm about to test... with "-march=i686", but other problems pop up.
didn't work (illegal instruction) I then tried with -march=i586 and after solving some other issues, like "forcing" to link against python2.6 (target system has python 2.6, build system 2.7). It now works, no more "illegal instruction" when creating a wallet. What didn't work well? The new binary installer that I posted? Or compiling for i586/i686? I think the new .deb file I posted should work on other 32-bit linux systems, and if it doesn't, I really don't understand what's going on. I'm super curious why the 32-bit-binaries-compiled-on-my-VM used to work but now they don't...? There was a very minor change made to the crypto++ library to make it work with the latest gcc, but that was just adding "this->" references to some calls. Perhaps the behavior actually changed... I'll have to revert the crypto++ library and see if my VM can compile working code again... |
|
|
|
I just recompiled the 32-bit version on one of my physical machines running Ubuntu 32-bit (luckily, I have a lot of them!). I don't have one for 12.04-32bit, but I guess I can make it happen if necessary. Or maybe someone can help me figure out how I should be compiling crypto++ to avoid this problem. The 'march=i?86" options sound kind of promising except I don't want to battle the crypto++ library too much... it's not my library, I don't want to mess with it... Anyways, here's the updated armory_0.77_python2.6_i386.deb. I tested it on my offline system and it worked. Hopefully it will work for others, too. |
|
|
|
I'm experiencing the "Illegal instruction" problem on my first-gen asus eeepc.
It seems to be an invalid instruction in the binary (I used the dependency bundle).
Ran an strace and it seems to be in the random number generator somewhere (I can't see an actual stacktrace, how do I dump one).
So I guess one of the dependency libs might've been compiled for a different CPU.
Ideas anyone?
Actually, I just ran into this the other day, too. I don't know why it used to work and now it doesn't. I have been compiling the binaries on Ubuntu VMs and it seems that the 32-bit systems are creating bad binaries. Perhaps the CPU type of a 32-bit VM is "different"? Anyone have any problems with the 64-bit packages? I'll investigate this a little more thoroughly. For now, I'll just compile it on a physical 10.04 32-bit system I have. At least, the python2.6 package can be done there... |
|
|
|
Nevermind, I found the trick: delete the user folder and reimport the armory wallet I'm not sure why that worked. I would think that issue is that the Satoshi client already added the tx to its own memory pool, and "broadcast it" once, and then won't broadcast it again. And any tx conflicting with that one will be rejected. Thus, you would need to clear the Satoshi-client memory pool in order to execute any more transactions with that wallet (at least any tx using any inputs used by the first tx). I would expect that maybe the tx you finally sent used different inputs, or maybe you restarted the Satoshi client which might purge the memory pool of tx that aren't relevant to its own wallet (I don't know if it actually does that though...) |
|
|
|
etotheipi, can you please explain to me how is the address sweeping done? Does it only sweep funds that are found on the address at the time of sweeping or is it possible to auto-sweep funds any time new funds arrive, a la MtGox? If it doesn't auto-sweep, it would be a cool feature. I'm kinda tired of using the vanilla client wallet and would like to add all my addresses to an Armory wallet and have it auto-sweep the funds once they arrive. Stop using my first wallet isn't something I can stop doing because of automatic payments I get to lots of addresses in there and having an Armory wallet that auto-swept those payments would be a peace of mind  Addresses are only swept once. No information about the addresses is kept anywhere. I determined that in most cases, if there's a swath of addresses you want to maintain in this way, you'll just make a new dedicated Armory wallet, and import/migrate the addresses there. I'm sure an auto-sweep function would be useful in some circumstances, but that's very low priority compared to some of the other current issues -- like when Armory stops working due to blockchain file splitting at 2GB Unfortunately, I won't get to implementing the new wallet format until after beta, so it could be 2+ months before I can support importing/migrating Satoshi 0.6.0+ wallets. Only if the wallet was created pre-0.6.0 can any of the addresses be migrated or swept using Armory (it's because Armory doesn't know how to handle compressed public keys). i.e. you won't even be able to use Armory for newer addresses anyway, so the lack of auto-sweep is not a critical deficiency. |
|
|
|
|
Show Posts
