[BOUNTY] 200 BTC for lightweight colored coin client(s)

[nyusternie]

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.

ok, i see. i don't know that much about dfs, but from what i've read it doesn't seem possible on a key-value db like leveldb (which is what bitcoinjs uses by default). have you implemented a custom/separate db for the coloring? coincidentally, i just spent this past weekend experimenting with an rdbms backend for the coloring features i'm working on. the database is built "lazily" after a new color definition is requested. works okay, but i'm concerned about scalability (more experimentation is needed).

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:

Code:

node color.js

Basically these things (block explorer, brainwallet, bitcoinjs-gui) can just call getColor function:

Code:

function getColor(txHash, outputIdx, callback) 

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.

color.js works perfect ... but ... it does a recursive query using http. to me that seems a bit ... insane. at the very least sockets would seem more efficient.  but why not just do all the recursion work on the server-side? (is that the eventual goal?? -- plug the color.js module into bitcoinjs -- sorry if i missed this somewhere .. suffering from information overload)

also, i'm confused, because i'm pretty sure the color definitions are based on addressHash160. but your code seems to key on specific transactions. i assumed you would query back to each address' "first appearance" as the origin. mainly because then you can easily distribute more coins of the same color (how can this be done with tx origins?)

i've mentioined before that i'm trying to keep my own work in line with your "official" coloring implementation. my biggest problem right now is multiple-color txs (using ordered ins and outs).  i'm sure i just need more time & understanding working with the bitcoin protocol (so this will come eventually).

i've got too many distractions this week (family-related) to realistically make any significant progress, but i'm really-Really-REALLY hoping to be able to publish something within the next 2 weeks. i've been testing my current implementation with friends & family for about a week now ... so far so good

[1714147496]

1714147496

[1714147496]

1714147496

[1714147496]

1714147496

[1714147496]

1714147496

[1714147496]

1714147496

[1714147496]

1714147496

[Zeilap]

Development on client side:
2. Make it so client verifies crypto stuff rather than simply trusts server

This is a monster of a task - it equates to implementing most of the functionality of an SPV node in the browser. The crypto is intimately tied to the binary representation of the transaction data, so you need to implement full parsing of the raw transaction and block header structures.

Also, without having the blockchain headers in the browser (say in local storage) and verifying them, the cryptographic proof is meaningless - you don't have verification of the block header that the transactions are linked to. So you additionally need to have a way for the server to provide a full header chain download and verification code in the browser.

Anyway, I think if this is your plan, I can do this (assuming I have the time), but it's a lot of work, so can you break it down and assign individual bounties.

[killerstorm]

ok, i see. i don't know that much about dfs, but from what i've read it doesn't seem possible on a key-value db like leveldb

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

color.js works perfect ... but ... it does a recursive query using http. to me that seems a bit ... insane. at the very least sockets would seem more efficient.

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

but why not just do all the recursion work on the server-side?

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.

(is that the eventual goal?? -- plug the color.js module into bitcoinjs -- sorry if i missed this somewhere .. suffering from information overload)

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

also, i'm confused, because i'm pretty sure the color definitions are based on addressHash160. but your code seems to key on specific transactions. i assumed you would query back to each address' "first appearance" as the origin.

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.

mainly because then you can easily distribute more coins of the same color (how can this be done with tx origins?)

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.

my biggest problem right now is multiple-color txs (using ordered ins and outs).  i'm sure i just need more time & understanding working with the bitcoin protocol (so this will come eventually).

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

i'm really-Really-REALLY hoping to be able to publish something within the next 2 weeks. i've been testing my current implementation with friends & family for about a week now ... so far so good

Thanks, that would be cool!

[Zeilap]

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.

ok, i see. i don't know that much about dfs, but from what i've read it doesn't seem possible on a key-value db like leveldb (which is what bitcoinjs uses by default). have you implemented a custom/separate db for the coloring?

Currently the algorithm finds the matching inputs for the given output and then visits each of these inputs. It is depth first because the order in which the inputs are put on and taken off of the queue is last-in, first-out. What killerstorm wants is to pre-calculate the depth of each output and store this depth with the output itself. This way, when adding the transaction inputs to the queue, you sort them in order so that the one with the smallest depth is always the last item in the queue, and thus is the next output that will be visited.

color.js works perfect ... but ... it does a recursive query using http. to me that seems a bit ... insane. at the very least sockets would seem more efficient.  but why not just do all the recursion work on the server-side? (is that the eventual goal?? -- plug the color.js module into bitcoinjs -- sorry if i missed this somewhere .. suffering from information overload)

I think the plan is that the code I wrote will actually end up browser side, replacing the node specific http requests with jquery ajax or something. The idea is that the server knows nothing about colored coins or any color definitions. Instead, all it provides is transaction data so that the client can store color definitions and perform the color-matching algorithm itself. This way you do not have to trust the server.

I wrote the code with the idea that it was probably going to be cannibalized and modified later when it gets integrated into the rest of the work. It is mostly a proof of concept that the idea works and that the performance is acceptable for an end user.

also, i'm confused, because i'm pretty sure the color definitions are based on addressHash160. but your code seems to key on specific transactions. i assumed you would query back to each address' "first appearance" as the origin. mainly because then you can easily distribute more coins of the same color (how can this be done with tx origins?)

i've mentioined before that i'm trying to keep my own work in line with your "official" coloring implementation. my biggest problem right now is multiple-color txs (using ordered ins and outs).  i'm sure i just need more time & understanding working with the bitcoin protocol (so this will come eventually).

A color definition is a pair of transaction hash and output index. This uniquely specifies a given output. When an address receives funds, what it actually means is that there was a transaction where the output specified that address as the receiver. The inputs of each transaction are simply the outputs of a previous transaction (or reward for mining a block). This way, you can trace all the bitcoins back to their creation, or similarly, trace all the created coins forward to where they are now.

The colored coins idea is that we simply label a given transaction output and then we can trace the location of this output forward as it gets transferred and split up between other people. By using addresses rather than outputs, you would limit the ability to use colored coins with non-standard transactions, and really, colored coins are much more interesting if you combine them with exotic transactions.

[killerstorm]

This is a monster of a task - it equates to implementing most of the functionality of an SPV node in the browser.

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

The crypto is intimately tied to the binary representation of the transaction data, so you need to implement full parsing of the raw transaction and block header structures.

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.

Also, without having the blockchain headers in the browser (say in local storage) and verifying them, the cryptographic proof is meaningless  - you don't have verification of the block header that the transactions are linked to.

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.

So you additionally need to have a way for the server to provide a full header chain download and verification code in the browser.

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.

Anyway, I think if this is your plan, I can do this (assuming I have the time), but it's a lot of work, so can you break it down and assign individual bounties.

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

[Zeilap]

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.

Ah, I wasn't aware of this.

Also, without having the blockchain headers in the browser (say in local storage) and verifying them, the cryptographic proof is meaningless  - you don't have verification of the block header that the transactions are linked to.

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.

Ok, fair enough, but that assumes that you are trying to fake a recent block. If you want to fake an old block, the difficulty is much lower.

So you additionally need to have a way for the server to provide a full header chain download and verification code in the browser.

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.

If you do this, then wouldn't it be simpler not to do backwards scan in the client at all? Instead, the client provides the server with the definition and the output he wants to test, the server then does a forward or backward scan and determines whether the output is colored, constructing a proof as it goes. Then it sends the proof to the client. Maybe this was your idea all along?

[nyusternie]

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

seems simple enough, but just so that i'm clear, would that mean that bfs would go forward (oldest -> recent)? (my knowledge thus far come from here and here)

Have you seen this: http://killerstorm.xen.prgmr.com/alex/color.html

this is VERY helpful. i'll take some time to work through the code, however, just a quick question .. why is "mixed" a drop-down option? how can you have a "single" mixed input (wouldn't those colors have be destroyed)?

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.

this may come from being a bitcoin n00b, but i'm 100% in favor of spv over full node. i just can't see how having the full blockchain is practical for "most" users and given the amount of complaining about latent SD "dust spam", i don't think it should be. my belief is that "most" users should find node(s) that they TRUST (like they would a traditional bank) and simply run a thin-client. given the strength of cloud-computing, SAAS and the like, heavy "client-side" processing (especially in the browser -- which is where i like to live) seems imo outdated. but, i can certainly appreciate the security advantages, which have many use-cases.

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.

that's the problem i would have. i'm looking to distribute shares in batches (maybe 20+ over time). "genesis" would force everyone to update their definitions after each batch.  "issuing address" would mean that i can even have private offerings and everyone would still be able to easily track the outstanding distribution.

By using addresses rather than outputs, you would limit the ability to use colored coins with non-standard transactions, and really, colored coins are much more interesting if you combine them with exotic transactions.

what do you mean by exotic transactions? unfortunately, my creative thinking seems stalled.

Instead, the client provides the server with the definition and the output he wants to test, the server then does a forward or backward scan and determines whether the output is colored, constructing a proof as it goes. Then it sends the proof to the client. Maybe this was your idea all along?

this is "almost" how my implementation works now (except without the proof-of-work).  obviously, this is not very good for client-side security, but its FAST-as-hell (and imo, more practical for the "average" user). could you please elaborate on HOW you could provide that proof? (i'm guessing it has something to do with merkle trees???)

this way, the burden then rests squarely on the server's implementation and capabilities.  i have this idea in my head that it would be ideal to have at least enough ram to hold the FULL blockchain. bitcoinjs is currently around 13GB (with my mods almost 20GB). so does a 32GB nodejs/event-driven server seem practical? too much? possibly not enough? (obviously load-balancing could also be used)

this is very exciting stuff.
cheers!

[killerstorm]

Have you seen this: http://killerstorm.xen.prgmr.com/alex/color.html

this is VERY helpful.

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.

i'll take some time to work through the code, however, just a quick question .. why is "mixed" a drop-down option? how can you have a "single" mixed input (wouldn't those colors have be destroyed)?

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

[killerstorm]

seems simple enough, but just so that i'm clear, would that mean that bfs would go forward (oldest -> recent)?

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.

this may come from being a bitcoin n00b, but i'm 100% in favor of spv over full node. i just can't see how having the full blockchain is practical for "most" users and given the amount of complaining about latent SD "dust spam", i don't think it should be. my belief is that "most" users should find node(s) that they TRUST

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

(like they would a traditional bank) and simply run a thin-client. given the strength of cloud-computing, SAAS and the like, heavy "client-side" processing (especially in the browser -- which is where i like to live)

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

that's the problem i would have. i'm looking to distribute shares in batches (maybe 20+ over time). "genesis" would force everyone to update their definitions after each batch.  "issuing address" would mean that i can even have private offerings and everyone would still be able to easily track the outstanding distribution.

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.

what do you mean by exotic transactions? unfortunately, my creative thinking seems stalled.

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.

could you please elaborate on HOW you could provide that proof? (i'm guessing it has something to do with merkle trees???)

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.

this way, the burden then rests squarely on the server's implementation and capabilities.  i have this idea in my head that it would be ideal to have at least enough ram to hold the FULL blockchain. bitcoinjs is currently around 13GB (with my mods almost 20GB). so does a 32GB nodejs/event-driven server seem practical? too much? possibly not enough? (obviously load-balancing could also be used)

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

[killerstorm]

Ah, I wasn't aware of this.

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.

If you do this, then wouldn't it be simpler not to do backwards scan in the client at all? Instead, the client provides the server with the definition and the output he wants to test, the server then does a forward or backward scan and determines whether the output is colored, constructing a proof as it goes. Then it sends the proof to the client. Maybe this was your idea all along?

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.

[nyusternie]

the difference between DFS and BFS is in how fast they detect uncolored outputs

dfs vs bfs i've obviously got a lot more reading to do

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

oh, i see. so i guess then a "proper" spv client is "required" to download all the block headers?  i think this is how the sd android app works. it takes a while to fully sync, but no where near as long as bitcoin-qt. and i think ultraprune in v0.8 is similar

but then how would you classify an app like BitcoinSpinner? You just start it up and it WORKS without any syncing? or for that matter any app that uses the blockchain.info api or how about bitcoinjs-gui?

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

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

makes sense. this is actually how i originally implemented my version of colored coins. i changed after i reviewed ArmoryX's use of the address definition as well as the whole idea of coins being destroyed. when accommodating users by allowing coins to be re-issued, address definition seems a hell of lot more convenient "for the user" (maintain total share count w/out the need to install/track new definitions). This does create additional burdens for the issuer, but i think it works well for my use-case (i certainly see the advantages of tx definitions -- as you described the various creative scripting options)

i should mention that i've implemented the firstSeen feature that was missing from bitcoinjs, which makes searching for issuing address just as fast as tx searches.

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.

there are limits on the amount of data you can save in local storage. so even a spv client may have problems.

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

absolutely! 

[killerstorm]

dfs vs bfs i've obviously got a lot more reading to do

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.

oh, i see. so i guess then a "proper" spv client is "required" to download all the block headers?

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.

i think this is how the sd android app works. it takes a while to fully sync, but no where near as long as bitcoin-qt.

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.

and i think ultraprune in v0.8 is similar

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

but then how would you classify an app like BitcoinSpinner? You just start it up and it WORKS without any syncing? or for that matter any app that uses the blockchain.info api or how about bitcoinjs-gui?

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 are limits on the amount of data you can save in local storage. so even a spv client may have problems.

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...

[killerstorm]

I've started with block explorer: http://178.33.22.12:3333/bexplo.html

[killerstorm]

color-aware block explorer kinda works now:

http://178.33.22.12:3334/bexplo.html

It is on testnet because there are performance issues with mainnet... Likely need to upgrade server to run it on mainnet... Also fix code, I guess.

Two color definitions are loaded: red and blue. (In future one could just point it to a color definition bundle of his choice.)

Genesis of blue:
b1586cd10b32f78795b86e9a3febe58dcb59189175fad884a7f4a6623b77486e
(loaded at start)

Genesis of red:
8f6c8751f39357cd42af97a67301127d497597ae699ad0670b4f649bd9e39abf

There is a bug: in some cases, colored input might be shows as having color 'none' at first, but when it shows same transaction again (click 'show' button) color is displayed correctly.

E.g. here: bd34141daf5138f62723009666b013e2682ac75a4264f088e75dbd6083fa2dba (4 blue inputs are merged into one).

Code is here: https://github.com/killerstorm/bitcoin-tx-spent-db (branch 'extra')

[nyusternie]

color-aware block explorer kinda works now:

http://178.33.22.12:3334/bexplo.html

very nice.
-----------------

just need to say that i really appreciate you taking the time recently to answer all of my questions.

since i started with bitcoin back in nov, i feel like i'm back in school doing math problems with paper and pen. when all i really want is a damn calculator.

thanks a million

[Zeilap]

color-aware block explorer kinda works now:

http://178.33.22.12:3334/bexplo.html

It is on testnet because there are performance issues with mainnet... Likely need to upgrade server to run it on mainnet... Also fix code, I guess.

Two color definitions are loaded: red and blue. (In future one could just point it to a color definition bundle of his choice.)

Genesis of blue:
b1586cd10b32f78795b86e9a3febe58dcb59189175fad884a7f4a6623b77486e
(loaded at start)

Genesis of red:
8f6c8751f39357cd42af97a67301127d497597ae699ad0670b4f649bd9e39abf

There is a bug: in some cases, colored input might be shows as having color 'none' at first, but when it shows same transaction again (click 'show' button) color is displayed correctly.

E.g. here: bd34141daf5138f62723009666b013e2682ac75a4264f088e75dbd6083fa2dba (4 blue inputs are merged into one).

Code is here: https://github.com/killerstorm/bitcoin-tx-spent-db (branch 'extra')

Fixed a bug (sounds like the one you describe) - check pull request.

[killerstorm]

Fixed a bug (sounds like the one you describe) - check pull request.

Yeah, works now. Thanks.

Your second patch didn't work though: it says no valueToBigInt function, or something like that.

[Zeilap]

Fixed a bug (sounds like the one you describe) - check pull request.

Yeah, works now. Thanks.

Your second patch didn't work though: it says no valueToBigInt function, or something like that.

Ah, sorry, the calls to valueToBigInt should have been to Util.valueToBigInt.

[alberthendriks]

I'm trying to get bitcoinjs-server working under Windows 7. Where is bin/bitcoinjs supposed to find module "step"?

[Zeilap]

I'm trying to get bitcoinjs-server working under Windows 7. Where is bin/bitcoinjs supposed to find module "step"?

in ../node_modules

Code:

npm install bitcoinjs

should pull in everything it needs though.