Actually link you posted has a good illustration: http://www.cs.sunysb.edu/~skiena/combinatorica/animations/search.html

Suppose what we are looking for is in the first pentagon. DFS will arrive there faster because it won't go to other pentagons before it scans the first one.


Yes.  But if you just link to one block header, it's still much better than nothing because it is hard to fake just one block header.


As far as I understand it downloads whole blocks because there is no way to download only headers, however it discards block contents unless it looks for wallet transactions.


No, ultraprune is a full verifying node implementation, it is just more efficient.


They trust that server protects them against double-spends. Also, they pull blockchain info from server instead of downloading it directly on Bitcoin network.


There is no need to store everything locally.

It is in fact theoretically possible to implement a full, verifying, mining node when you have only 32 bytes of local storage

But that's a fairly complex topic...

1. ArmoryX overhaul (50 BTC): ArmoryX is a proof-of-concept colored coin wallet. Basically, it is the only one in existence (if you do not count bitpaint) and the only one which implements p2ptrade. However, the problem is that it is based on an outdated version of Armory. And I have very little interest to maintain it.

So, what's required: merge ArmoryX with changes in later versions of Armory. I'm not sure what is possible/feasible, but at very least we need support for bitcoind 0.8 blockchain format.

Required skills: C++, Python.

Bounty: 50 BTC is a total budget for overhaul, maintenance and further development. We don't want to spend that much on overhaul alone. But, say, 25 BTC can go into it... If you're interested, please contact me so we can discuss it further.

2. ArmoryX TerraCoin port (?? BTC) Once we do an overhaul, we can enable TerraCoin support in ArmoryX. It is easy to do, and it would be really great because Armory would require much less resources to run on TerraCoin network, so it would be feasible to run it on cheapo laptops and whatnot.

(Currently I cannot run ArmoryX for Bitcoin mainnet on my laptop, I kid you not.)

3. Standard development and research (25+ BTC). So far only a part of colored coin tech is properly documented. Other parts either exist in code without any documentation in English, or exist only in our imagination, with discussions scattered over dozens of forum posts. So we need to develop standards, and to solve all pending problems.

4. Bounties for thin clients (200+ BTC). See here: https://bitcointalk.org/index.php?topic=141858.0
100 BTC is allocated for development of JS-based web client, 12 BTC is already paid in bounties.
However, we want mobile and/or thin desktop clients too. Particularly, we consider Electrum, MultiBit and a wallet for Android. (However, only one or two will be implemented.)

Perhaps the easiest way to do it is blockchain.info-style web wallet provided by service... It doesn't make it any more complex for users, basically for them it looks like a page which shows how much money they have on account and which allows deposits/withdrawals. But it won't allow service to run away with the money.

Arbitrage between futures price and spot price is basically free money, but it isn't really risk-free when you use a third-party service. I think that's why futures prices on icbit.se differ so much from spot prices. Use of escrow removes a decent amount of risk. (Well, depending on how it is implemented... Quite likely it won't be perfect...) So this can encourage arbitrages to trade more, which is a good thing.

They definitely ask NOT to use their deposit addresses for mining.

I don't quite get why... Perhaps it is because mined coins need 120 blocks to mature and their software cannot handle that for some reason.

Have you thought about using an "escrow"?

Please check this: http://www.reddit.com/r/Bitcoin/comments/1a6ewu/ive_been_waiting_for_a_usable_blockchain_escrow/c8ui49g

And this: https://bitcointalk.org/index.php?topic=141536.msg1507614#msg1507614

There are several other implementations. Particularly, bitcoinjs-server is a full, verifying Bitcoin node, so it obviously has all the necessary cryptography... I'm not sure whether it is possible to port it to browser env, though.


Yes, this was the original plan (more-or-less), and people started implementing it back in November 2012... But the only result is bitcoin-tx-spent-db, which is far from a complete coloring server.

So I thought it's better to start with something simpler and started investigating the possibility of doing coloring on client side, as it is fairly hard to do it on server-side.

The priority is to get something demonstrable. Security and performance are secondary targets for now.

No, choice of traversal order is orthogonal to choice of traversal direction.

In context of coloring, the difference between DFS and BFS is in how fast they detect uncolored outputs. There is no performance difference for colored outputs, they need to go through all transactions in history anyway.

DFS can detect uncolored outputs faster, basically it just goes to nearest coinbase transaction, which is by definition uncolored.


When implemented properly SPV requires no trust. If it requires trust, it isn't SPV. See here: https://en.bitcoin.it/wiki/Thin_Client_Security


We can use servers, but we don't need to trust them.


You can issue maximum authorized number of shares via single genesis, but park them on issuer's address and distribute as needed.

This way accounting is same as with "issuing address": number of outstanding shares = number of issued shares - number of shares held on issuer's address.

However, it is just easier to track shares back to one genesis transaction output... Also it limits maximal number of shares.

I think "issuing address" makes sense only if you absolutely cannot issue shares in one batch. For example, if shares have large "metal value" so issuing them costs money.


The usual Bitcoin output script (https://en.bitcoin.it/wiki/Script) pays to a single address.
But there are many other possibilities. Say, m-of-n multi-signature scripts. (They are standard now.)

Also, contracts: https://en.bitcoin.it/wiki/Contracts

When you have something other than simplest transaction you cannot associate a single address with it.


Yes, Merkle trees... Basically you send a bunch of hashes to prove that transaction is linked to a block. But the whole scheme is rather contrived.


Yes, it is definitely doable, but blockchain will grow in future, so it isn't clear how it can work in future.

This is an updated version of code: https://github.com/bitcoinx/colored-coin-tools/blob/master/color.js
compute_colors() are much easier to follow in this version because validation was moved to separate functions.


Yes, 'mixed' is same as uncolored, implementation in ArmoryX does not distinguish between mixed and uncolored. So just forget about them

It looks like there is a problem with the site, it definitely was a banner.

Yes, that's the only way to make it secure.


Well, all JS wallet implementations can do that... Kind of...

For example, Brainwallet can give you a signed raw transaction ( http://brainwallet.org/#tx ), and it is very simple.

So I don't think it is monstrous at all... Just glue some pieces together.


Not quite... We can estimate how hard it is to make a fake block from this block alone. If we have some reasonable estimation of current difficulty, we can estimate opportunity cost of attack.

Note that one needs to mine a fake block after transaction was submitted... You cannot pre-mine some fake blocks and insert transactions there, it would change Merkle root.

So, all in all, if you know current difficulty, you can estimate that faking one block costs about 50 BTC.


I don't think it is a problem: server can collect all information needed by client in one blob. Client will then parse this blob to get block headers, Merkle branches, transactions etc. Size of this blob? Maybe a couple of megabytes... It isn't big by internet standards.


Yeah, I think we will leave juicy crypto parts for later

DFS is just a specific form of backward scan, i.e we go back in history.


Well... We'll optimize it later The thing is that performance should be acceptable as long as coin's history is small.


Well, that creates far more problems than it solves.

One thing is that it is a fundamentally flawed model w.r.t. security: client cannot and shouldn't trust server to do coloring properly, it should check on its own.

Another thing is that opens server to DoS attacks because this scan can be very computationally expensive.

It makes sense to do recursion on server to send all the data in one batch, but it's just a performance optimization and it isn't a priority right now. We can do it later.


I think if we do coloring on server, we should use database and whatnot.


There are two models: "genesis" and "issuing address". "Genesis" is simpler, easier and more secure.

I'm not even sure we should do "issuing address", but the reference implementation, ArmoryX, does both.


Yes, "issuing address" allows one to create more coins... Which is both a good and a bad thing.

In genesis model, it is possible to issue more coins by adding more genesis tx outputs, duh. However that would require color definition update protocol, which isn't implemented/standardized yet.


Have you seen this: http://killerstorm.xen.prgmr.com/alex/color.html
It is a demo from colored-coin-tools.


Thanks, that would be cool!

So that was a general plan (which might change). As for immediate target, I'm going to make sure that DFS coloring is indeed usable, and to look into how to integrate coloring into block explorer, brainwallet, bitcoinjs-gui etc.

If somebody wants to into it instead of me, that would be cool. :-)

Here is coloring code: https://github.com/Zeilap/colors/blob/master/color.js

You can just run test via node:
Basically these things (block explorer, brainwallet, bitcoinjs-gui) can just call getColor function:


whenever for transaction outputs they see. Perhaps we'll modify this API later, but for now it's OK.

E.g. block explorer will just show color, other things can use it to filter outputs etc.

DFS-based coloring will used distance-to-coinbase db built on server to make sure that scanning uncolored outputs does not take too much time. It's just not ready, requires a bit more work.

It works now. Perhaps I just forgot about orders I already had...

Further development of web client:

Here is a preliminary list of tasks. It is preliminary because it lacks some details and might change a bit. (I'm going to test things a bit before finalizing it.)
So it is not actionable, but it gives you an idea, and whoever wants to work on these things can already 'book' a spot.

Improvements on server side:
1. Merge bitcoinjs-color, bitcoin-tx-spent-db and, later, node-bitcoin-exit. There is no reason to have them separate, I think.
2. tx data access API (called bitcoinjs-color) needs to be updated:
    * JSON API needs to return values correctly is satoshi, not in floating point values.
    * provide raw transaction data
    * provide cryptographic proof, i.e. Merkle branches which link transaction to block and block headers
    * support for batch queries
3. Make sure it continuously gets new data from blocks and can work with transactions in mempool.

Development on client side:
1. Coloring: Use distance-to-coinbase data to guide DFS to get optimal performance on uncolored outputs.)
    (This is what I'm doing now, but there is a problem with dtocoinbase db, so I cannot proceed.)
2. Make it so client verifies crypto stuff rather than simply trusts server
3. Hook coloring algo to front-ends:
    * block explorer
    * brainwallet
    * bitcoinjs-gui
4. Improve front-ends until they are usable

There is also an admin task: install all the crap on a powerful server, populate dbs etc.
Currently it runs on my VPS which is enough for testnet, but populating spent-db on mainnet will be really painful.

There is at least 50 BTC in bounties for this list of tasks.

It doesn't. I currently have -0.05 BTC on account, and it was negative for a week or so.

As I have negative initial margin it doesn't allow me to send orders which would close my position.

So to close it I'll have to deposit some money.

Suppose I have negative amount of money on account on ICBIT.se...

Should I feel morally obligated to settle this debt, or can I just walk away from it?

What are possible consequences?

Can exchange operators go after people who owe to ICBIT.se and label them as scammers on forum, for example?

What's more worrying is that my position is still open while I have negative amount... So I'm getting more and more debt as Bitcoin goes up. But I can also get back into profit if exchange rate plummets =)

DoS attack: somebody sends you lots of fake transactions with non-existent inputs. To dismiss such transaction you need to confirm that input is indeed non-existent, and it requires one or more read operations.

If you store UTXO set on hard disk drives, it would be pretty much trivial to DoS attack you because one HDD can do something like 100 random reads per second.

This is why people think that there should be a limit on UTXO set. For example, via introduction of minimal viable transaction output value. (Say, if TXO value is 1 satoshi it might be seen as spam.)

Please understand me correctly, this is just what I saw in discussions here, it appears to be a prevalent opinion.

Of course, it is possible to design system in such a way that UTXO set size won't be a problem and won't affect costs, this is what I'm talking about here...

5 BTC is a typical bounty we give (at current exchange rate). I'm not sure how much effort is required. Also we can pay more for bigger overhaul and further development.

Again, the main topic of my post was bandwidth-storage trade-off which is independent of security model you use. Actually I've outlined very conservative approach which changes nothing about security model, i.e. you still scan whole blockchain, you just don't store UTXO set locally.

But, of course, it's also possible to use UTXO set referenced by blocks instead of computing your own.

I'm not sure that "SPV UTXO security" is the right term because what I'm talking about is applicable to miners, but SPV is used in context of client systems, no?



This attack is possible right now, N equals current blockchain height.

What changes if we make N less than current blockchain height?


Same thing happens if you mine starting from genesis.

If you do history-rewriting attack of a limited depth you can steal coins of some people.


No, it is possible to verify supply having only UTXO set.


I think you get it wrong: history-rewriting attack is fundamentally not different from UTXO manipulation attack in terms of severity.

If you have enough computational power and checkpointing is not a problem, you can do either of attacks, with same consequences.

If you don't have enough computational power, you can't do either of attacks. If centralized checkpoints are present in clients, you can't do either of attacks.