Pages:
Author

Topic: FirstBits.com - remember and share Bitcoin addresses - page 2. (Read 26282 times)

Jan
legendary
Activity: 1043
Merit: 1002
Looks pretty good Jan.  My only comment is that the line "The order of appearance..." is largely irrelevant.  We have agreed that order in a block doesn't matter - all addresses with matching firstbits in the same block will have characters added until they each have unique firstbits.

As I wrote just above:
...
Regarding this:
...  If it is possible (is it?) for an earlier tx to spend the output of a later tx in the same block, we would have to be careful about whether the earlier one's input script triggers "appearance" of the address in case a competing address appears in a third transaction between those two.  The rule about "all addresses appearing in the same block" avoids that issue, while unfortunately making some address prefixes ineligible ever to become firstbits.
...

I am pretty sure that an earlier tx cannot spend outputs from a later output in the same block (the other way around happens all the time). I had the same worry when I did my block chain loader back in october last year and included some hefty logging in case it appeared. It never did. The specification and implementation will be cleaner without this corner case.
...

This adds unnecessary complexity, potentially invalidates old firstbits addresses, and is incompatible with what other implementations do today.
I really think it is a bad idea.
legendary
Activity: 1400
Merit: 1005
Looks pretty good Jan.  My only comment is that the line "The order of appearance..." is largely irrelevant.  We have agreed that order in a block doesn't matter - all addresses with matching firstbits in the same block will have characters added until they each have unique firstbits.
Jan
legendary
Activity: 1043
Merit: 1002
Firstbits Definition (Draft)

Firstbits Base Representation
All Bitcoin addresses that appear in the block chain using a well defined set of recognized transaction output formats have a unique firstbits base representation. The firstbits base representation of a bitcoin address is the shortest non-empty substring starting with the first character of the Bitcoin address and converted to lower-case, which does not collide with the firstbits base representation of another address appearing in a transaction output earlier in the block chain. Thus, a firstbits base representation is always in lower-case.

The order of appearance for addresses in transaction outputs in the same block follows the order of transaction outputs in the raw block data.

Firstbits Addresses
A Bitcoin address can several valid firstbits addresses. A firstbits address can be derived from a firstbits base representation by appending additional characters from the Bitcoin address up to and including the last character of the Bitcoin address. A firstbits address can have any combination of upper and lower case.

Example 1
Bitcoin address:               1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa
Firstbits base representation: 1
Firstbits address examples:    1, 1a, 1A, 1a1z, 1A1z, 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa


Example 2
Bitcoin address:               1SgTspiKe5HHkjdSeD72q9WsiJhRiaxf9
Firstbits base representation: 1sgtsp
Firstbits address examples:    1sgtsp, 1SgTsp, 1SgTspiKe5HHkjdSeD72q9WsiJhRiaxf9


Recognized Transaction Output Formats
An address is said to appear in a block when it appears in one of the block's transactions' pubkey, pubkey hash, or script hash outputs.

Pubkey Output
A pubkey output is a transaction output with a script of the form:
Code:
OP_CHECKSIG
An address is said to appear in a pubkey output when its version byte is 0 and its key hash equals the 160-bit hash of the output script's push operand (pubKey).

Pubkey Hash Output
A pubkey hash output is a transaction output with a script of the form:
Code:
OP_DUP OP_HASH160 OP_EQUALVERIFY OP_CHECKSIG
An address is said to appear in a pubkey hash output when its version byte is 0 and its 160-bit key hash equals the output script's push operand (pubKeyHash).

Script Hash Output
A script hash output is a transaction output with a script of the form:
Code:
OP_HASH160 OP_EQUAL
An address is said to appear in a script hash output when its version byte is 5 and its 160-bit key hash equals the output script's push operand (scriptHash).

In particular, output scripts not matching the above three cases can not affect whether an address appears in a block, nor can input scripts.  For example, a script containing OP_DROP or OP_NOP can not match the cases, but the push operand in a pubkey output may have any length.
Jan
legendary
Activity: 1043
Merit: 1002
SgtSpike, can you share the precise definition of a firstbits address?

Jan, given SgtSpike's and my openness to change, would you care to work on a precise definition?


Yep, working on a first draft. A significant part was already done by you  Wink

...  If it is possible (is it?) for an earlier tx to spend the output of a later tx in the same block, we would have to be careful about whether the earlier one's input script triggers "appearance" of the address in case a competing address appears in a third transaction between those two.  The rule about "all addresses appearing in the same block" avoids that issue, while unfortunately making some address prefixes ineligible ever to become firstbits.
...

I am pretty sure that an earlier tx cannot spend outputs from a later output in the same block (the other way around happens all the time). I had the same worry when I did my block chain loader back in october last year and included some hefty logging in case it appeared. It never did. The specification and implementation will be cleaner without this corner case.

I'll have something for you to review later today
hero member
Activity: 481
Merit: 529
SgtSpike, can you share the precise definition of a firstbits address?

Jan, given SgtSpike's and my openness to change, would you care to work on a precise definition?
legendary
Activity: 1400
Merit: 1005
Yes, and I fear that "what the protocol accepts" and what future users will consider an "appearance of an address" may be computationally infeasible for an unvarying standard such as firstbits should be.  For example, each normal address (starting with 1) has a unique corresponding, standard 1-of-1 P2SH output script and address starting with 3.  If you know the 1-address, you can find the 3-address, but not vice versa, at least until the output is spent.  Does the spending of such an output constitute appearance of the 1-address?  Some might say yes, others no.  The firstbits standard must give an answer for every possible case like that that may appear in the future.

Firstbits must be derived only from the blockchain, obviously.  "Bitcoin addresses" never occur directly in the blockchain; rather, they are extracted by matching scripts against templates and associating script types with well-known "version bytes".  If your address were spelled out in the block whenever it sent or received coins, we could trivially define first appearance.  Since that is not the case, it is up to us to cope with the complexity.

It is still an open question to me, whether to ignore non-functional trailing script fragments such as Eligius's OP_NOP.  The whole class of them would have to be easily identified, or if a special case for the single OP_NOP would yield better backward compatibility, I would consider just that.  I do not have time right now to find out the answers, but if someone more interested than I comes up with the data, I will comment on it.  Smiley
Essentially what you are saying is, there are a potentially infinite number of ways that operations can be arranged and used, and each one could require special handling to resolve firstbits.  In order to eliminate inconsistencies between different firstbits implementations, we need to stick to commonly-used scripts and operation combinations, as one would find in widely-distributed Bitcoin clients.  Otherwise, all firstbits implementations must continually update to account for odd transactions, or risk providing different firstbits information than other implementations.  Implementations in this case would also have to agree to some set of handling rules for new odd transactions that appear, in cases where there might be ambiguity (such as the P2SH case you presented above).

This makes sense, and I now agree that we should stick to providing firstbits only for those transactions deemed "regular".  Said transaction types should be well-defined and listed, so that all implementations can easily follow the same rule set.
hero member
Activity: 481
Merit: 529
Touche on the about page.  Cheesy  I know we specifically didn't mention it there because we didn't want to go into too much detail, but it sounds like we should have anyway.

That's okay, perhaps we'll get it done here now... Smiley

Yes, you are correct about making that change for addresses in the same block - the distinction would only invalidate some firstbits, it wouldn't actually change any of them from pointing at one address to pointing at another.  I wouldn't have a problem with making this change then.

Regarding the OP_NOP transactions, I read that some people used them to donate transaction fees to a certain pool.  It's a bit beyond my level of comprehension as to how exactly that works, but essentially, only Eligus could take the fee for these transaction:  https://bitcointalksearch.org/topic/opnop-appended-transactions-how-long-do-non-standard-transactions-wait-11481

Thanks for digging that up.  It looks as if the transactions are indeed generated by end users (of a modified client) who do see the affected addresses.  I don't have a full database handy, but I am curious how many OP_NOPs are in the chain and whether they still occur.  If it's a tiny percentage and none recently, I'm less concerned.  But here, a firstbits assigned in an OP_NOP output would indeed be reassigned to another address, so I suggest we consider it carefully.

I suppose I would still lean towards what the Bitcoin protocol accepts, not what various clients do and do not accept and can and cannot generate.  If the protocol allows it to be placed in the blockchain, then it should be given a firstbits.  OP_NOP transactions are not normal, and cannot be generated with the default client, but they are still valid Bitcoin transactions.  I don't see any reason to disclude any valid scripts that anyone wants to run from being included in firstbits calculations.

You certainly know a great deal more about the inner workings of Bitcoin than I do.  I'd just like to see why you don't want these non-normal transactions to be included.  You mentioned having to modify your code slightly to be able to handle these special transactions - are you concerned about having to continue to modify your code in order to deal with new combinations of operations?

Yes, and I fear that "what the protocol accepts" and what future users will consider an "appearance of an address" may be computationally infeasible for an unvarying standard such as firstbits should be.  For example, each normal address (starting with 1) has a unique corresponding, standard 1-of-1 P2SH output script and address starting with 3.  If you know the 1-address, you can find the 3-address, but not vice versa, at least until the output is spent.  Does the spending of such an output constitute appearance of the 1-address?  Some might say yes, others no.  The firstbits standard must give an answer for every possible case like that that may appear in the future.

Firstbits must be derived only from the blockchain, obviously.  "Bitcoin addresses" never occur directly in the blockchain; rather, they are extracted by matching scripts against templates and associating script types with well-known "version bytes".  If your address were spelled out in the block whenever it sent or received coins, we could trivially define first appearance.  Since that is not the case, it is up to us to cope with the complexity.

It is still an open question to me, whether to ignore non-functional trailing script fragments such as Eligius's OP_NOP.  The whole class of them would have to be easily identified, or if a special case for the single OP_NOP would yield better backward compatibility, I would consider just that.  I do not have time right now to find out the answers, but if someone more interested than I comes up with the data, I will comment on it.  Smiley
legendary
Activity: 1400
Merit: 1005
Touche on the about page.  Cheesy  I know we specifically didn't mention it there because we didn't want to go into too much detail, but it sounds like we should have anyway.

Yes, you are correct about making that change for addresses in the same block - the distinction would only invalidate some firstbits, it wouldn't actually change any of them from pointing at one address to pointing at another.  I wouldn't have a problem with making this change then.

Regarding the OP_NOP transactions, I read that some people used them to donate transaction fees to a certain pool.  It's a bit beyond my level of comprehension as to how exactly that works, but essentially, only Eligus could take the fee for these transaction:  https://bitcointalksearch.org/topic/opnop-appended-transactions-how-long-do-non-standard-transactions-wait-11481

I suppose I would still lean towards what the Bitcoin protocol accepts, not what various clients do and do not accept and can and cannot generate.  If the protocol allows it to be placed in the blockchain, then it should be given a firstbits.  OP_NOP transactions are not normal, and cannot be generated with the default client, but they are still valid Bitcoin transactions.  I don't see any reason to disclude any valid scripts that anyone wants to run from being included in firstbits calculations.

You certainly know a great deal more about the inner workings of Bitcoin than I do.  I'd just like to see why you don't want these non-normal transactions to be included.  You mentioned having to modify your code slightly to be able to handle these special transactions - are you concerned about having to continue to modify your code in order to deal with new combinations of operations?
hero member
Activity: 481
Merit: 529
Hello again John!

Firstbits.com had always differentiated by order of appearance in the raw block data, and given the first appearance the shorter firstbits.  I'm not sure who stated otherwise, but for firstbits.com, that's always been the case.

Perhaps I read it here:

I am not sure what standard blockchain.info follows on that front, but I assumed it followed the same.  We should find out.  Regardless, giving enough firstbits to distinguish both addresses in the same block is certainly cleaner.

Cleaner, I suppose, although I, too, originally based it on order within the block.  If it is possible (is it?) for an earlier tx to spend the output of a later tx in the same block, we would have to be careful about whether the earlier one's input script triggers "appearance" of the address in case a competing address appears in a third transaction between those two.  The rule about "all addresses appearing in the same block" avoids that issue, while unfortunately making some address prefixes ineligible ever to become firstbits.

I didn't want to change it for fear it could screw up someone relying on the original implementation.  The likelihood of someone using one of those addresses is slim, but the possibility still exists.  Now would be a good time to change it, if we are also nailing down other portions of the specification.

Thanks for the willingness to clean up.  I think in this case, the change would never result in a firstbits becoming the firstbits of another address.  Rather, some (rare) firstbits would become non-firstbits, ineligible due to appearing first in two or more addresses within a block.

Yes, let's indeed finish the standard.  I suppose I dropped out of that original discussion because I am not familiar enough with the different OP functions of Bitcoin and what they mean/do.  Is there some reading I can do somewhere that explains more about these?

The wiki describes the original two standard transactions: https://en.bitcoin.it/wiki/Script#Scripts.  P2SH is in BIP 16: https://en.bitcoin.it/wiki/BIP_0016.  The authoritative reference is the IsStandard and Solver functions in src/script.cpp.

I suppose I would say that as long as a transaction is valid and included in the blockchain, there is no reason it shouldn't also be included in firstbits.  Will the average person know what a transaction with OP_NOP means, or how to know if a transaction has it or not?

For example, transaction 5492a05f1edfbd29c525a3dbf45f654d0fc45a805ccd620d0a4dff47de63f90b has an OP_NOP appended to one of the addresses.  Blockexplorer decodes the address correctly, but blockchain.info doesn't seem to have a handle on it:
http://blockexplorer.com/tx/5492a05f1edfbd29c525a3dbf45f654d0fc45a805ccd620d0a4dff47de63f90b
https://blockchain.info/tx/5492a05f1edfbd29c525a3dbf45f654d0fc45a805ccd620d0a4dff47de63f90b

So you are arguing that these OP_NOP transactions should be discluded, despite the fact that they are included in the blockchain?

I am not disagreeing with you, I just want to understand more about what the disclusions are and how easy it will be for the average person to understand why a particular address doesn't have firstbits.

Yes.  In fact, here is a case where Abe does the other thing, and the standard that I propose will require a change.

I assume that the reference client does not generate these OP_NOP transactions, nor does any client designed with interoperability in mind.  The last time I checked, there were only a handful of them.  I can only speculate why someone went to the trouble of making them.  I remember first seeing them in Abe, checking BlockExplorer, and adding a tiny change to make Abe handle them compatibly.  The problem is, if we allow OP_NOP at the end, where do we draw the line?  Do we allow multiple OP_NOPs or other operations?  I guess we could just as easily define the script types by how scripts start, and if firstbits.com has always done this, that might convince me.  I consider a full, exact match cleaner.  In practice, I think anything after the standard portion gets ignored, unless it would make the script or block too big.  I haven't checked whether IsStandard allows trailing junk, but I have the impression that developers mostly frown on it.

Thanks for your comments.
legendary
Activity: 1400
Merit: 1005
I wasn't even aware that Abe even performed firstbits resolution.

Let me refresh your memory. Smiley  https://bitcointalksearch.org/topic/m.957933

The definition is mostly displayed in layman's terms here: http://firstbits.net/about.php
Also there's the basic SQL statement used here:  http://firstbits.net/logic.html

Thank you, but this is not a precise specification.

Whatever address appears first in the blockchain claims the Firstbits for every previously unused combination up to the full address.  For example, 1SgTspiKe5HHkjdSeD72q9WsiJhRiaxf9 doesn't have the firstbits 1s, 1sg, 1sgt, or 1sgts because other addresses used prior to this one already started with those combinations, but it DOES have the firstbits 1sgtsp, 1sgtspi, 1sgtspik, 1sgtspike, 1sgtspike5, etc, all the way up to 1SgTspiKe5HHkjdSeD72q9WsiJhRiaxf.

If two addresses with the same firstbits appear in the same block, then the addresses are given firstbits in the order they are seen in the raw block data (i.e., the first one would be given 1sgtspike, and the second would be given 1sgtspikeX, where X is the next character in the address).

IIRC, this contradicts information given earlier, that neither address would get 1sgtspike: both new firstbits would contain enough characters to distinguish them from each other, regardless of their ordering within the block.

This is always how firstbits have been resolved.  If Abe resolves firstbits in a different manner than the above, then it should not be calling them firstbits.

True, but if so, it is not for lack of trying.  Rather than rename the function in Abe, why don't we finish the standard and bring ourselves into agreement.  Here is where we left off: https://bitcointalksearch.org/topic/m.960077
Hello again John!

Firstbits.com had always differentiated by order of appearance in the raw block data, and given the first appearance the shorter firstbits.  I'm not sure who stated otherwise, but for firstbits.com, that's always been the case.  I am not sure what standard blockchain.info follows on that front, but I assumed it followed the same.  We should find out.  Regardless, giving enough firstbits to distinguish both addresses in the same block is certainly cleaner.  I didn't want to change it for fear it could screw up someone relying on the original implementation.  The likelihood of someone using one of those addresses is slim, but the possibility still exists.  Now would be a good time to change it, if we are also nailing down other portions of the specification.

Yes, let's indeed finish the standard.  I suppose I dropped out of that original discussion because I am not familiar enough with the different OP functions of Bitcoin and what they mean/do.  Is there some reading I can do somewhere that explains more about these?

I suppose I would say that as long as a transaction is valid and included in the blockchain, there is no reason it shouldn't also be included in firstbits.  Will the average person know what a transaction with OP_NOP means, or how to know if a transaction has it or not?

For example, transaction 5492a05f1edfbd29c525a3dbf45f654d0fc45a805ccd620d0a4dff47de63f90b has an OP_NOP appended to one of the addresses.  Blockexplorer decodes the address correctly, but blockchain.info doesn't seem to have a handle on it:
http://blockexplorer.com/tx/5492a05f1edfbd29c525a3dbf45f654d0fc45a805ccd620d0a4dff47de63f90b
https://blockchain.info/tx/5492a05f1edfbd29c525a3dbf45f654d0fc45a805ccd620d0a4dff47de63f90b

So you are arguing that these OP_NOP transactions should be discluded, despite the fact that they are included in the blockchain?

I am not disagreeing with you, I just want to understand more about what the disclusions are and how easy it will be for the average person to understand why a particular address doesn't have firstbits.
hero member
Activity: 481
Merit: 529
I wasn't even aware that Abe even performed firstbits resolution.

Let me refresh your memory. Smiley  https://bitcointalksearch.org/topic/m.957933

The definition is mostly displayed in layman's terms here: http://firstbits.net/about.php
Also there's the basic SQL statement used here:  http://firstbits.net/logic.html

Thank you, but this is not a precise specification.

Whatever address appears first in the blockchain claims the Firstbits for every previously unused combination up to the full address.  For example, 1SgTspiKe5HHkjdSeD72q9WsiJhRiaxf9 doesn't have the firstbits 1s, 1sg, 1sgt, or 1sgts because other addresses used prior to this one already started with those combinations, but it DOES have the firstbits 1sgtsp, 1sgtspi, 1sgtspik, 1sgtspike, 1sgtspike5, etc, all the way up to 1SgTspiKe5HHkjdSeD72q9WsiJhRiaxf.

If two addresses with the same firstbits appear in the same block, then the addresses are given firstbits in the order they are seen in the raw block data (i.e., the first one would be given 1sgtspike, and the second would be given 1sgtspikeX, where X is the next character in the address).

IIRC, this contradicts information given earlier, that neither address would get 1sgtspike: both new firstbits would contain enough characters to distinguish them from each other, regardless of their ordering within the block.

This is always how firstbits have been resolved.  If Abe resolves firstbits in a different manner than the above, then it should not be calling them firstbits.

True, but if so, it is not for lack of trying.  Rather than rename the function in Abe, why don't we finish the standard and bring ourselves into agreement.  Here is where we left off: https://bitcointalksearch.org/topic/m.960077
Jan
legendary
Activity: 1043
Merit: 1002
Thanks.

Regarding Abe read here: https://bitcointalksearch.org/topic/m.960077
and here: https://bitcointalksearch.org/topic/m.1044812
Just a few posts upstream :-)
legendary
Activity: 1400
Merit: 1005
Alright, I quickly put firstbits.net up, but right now it just reads from blockchain.info's API.  I need to rewrite the engine for calculating them, because the original one was simply too slow.

I may be interested in adding firstbits functionality to the Mycelium backend system. To do this I need to know exactly what the rules for name resolution are. It seems that blockchain.info does not do it the same way that Abe does. Without a firm rule-set the purpose of firstbits is defeated.

SgtSpike, can you share the precise definition of a firstbits address?
I wasn't even aware that Abe even performed firstbits resolution.  Is there a running example you can point me to?

The definition is mostly displayed in layman's terms here: http://firstbits.net/about.php
Also there's the basic SQL statement used here:  http://firstbits.net/logic.html

Whatever address appears first in the blockchain claims the Firstbits for every previously unused combination up to the full address.  For example, 1SgTspiKe5HHkjdSeD72q9WsiJhRiaxf9 doesn't have the firstbits 1s, 1sg, 1sgt, or 1sgts because other addresses used prior to this one already started with those combinations, but it DOES have the firstbits 1sgtsp, 1sgtspi, 1sgtspik, 1sgtspike, 1sgtspike5, etc, all the way up to 1SgTspiKe5HHkjdSeD72q9WsiJhRiaxf.

If two addresses with the same firstbits appear in the same block, then the addresses are given firstbits in the order they are seen in the raw block data (i.e., the first one would be given 1sgtspike, and the second would be given 1sgtspikeX, where X is the next character in the address).  Blockexplorer.com shows the raw block data, and lists the transactions in the same order as they are seen in the raw block data, so it is a reliable source for determining which address should come first in the event that the same new firstbits combination is shared by two addresses in the same block.

This is always how firstbits have been resolved.  If Abe resolves firstbits in a different manner than the above, then it should not be calling them firstbits.
Jan
legendary
Activity: 1043
Merit: 1002
Alright, I quickly put firstbits.net up, but right now it just reads from blockchain.info's API.  I need to rewrite the engine for calculating them, because the original one was simply too slow.

I may be interested in adding firstbits functionality to the Mycelium backend system. To do this I need to know exactly what the rules for name resolution are. It seems that blockchain.info does not do it the same way that Abe does. Without a firm rule-set the purpose of firstbits is defeated.

SgtSpike, can you share the precise definition of a firstbits address?
legendary
Activity: 1400
Merit: 1005
Alright, I quickly put firstbits.net up, but right now it just reads from blockchain.info's API.  I need to rewrite the engine for calculating them, because the original one was simply too slow.
legendary
Activity: 1246
Merit: 1016
Strength in numbers
Free, is firstbits.com discontinued or just temporarily down? Thanks.
It's discontinued by him, but I plan to continue it at firstbits.net (and .com if I can get a hold of the domain).  In the meantime, there's this website: http://bitcoinfirstbits.com/.  I forgot who runs it.  Lookups can also be done at blockchain.info.

That's right. I'm going to give the domain to Spike if I'm able.
legendary
Activity: 1400
Merit: 1005
Free, is firstbits.com discontinued or just temporarily down? Thanks.
It's discontinued by him, but I plan to continue it at firstbits.net (and .com if I can get a hold of the domain).  In the meantime, there's this website: http://bitcoinfirstbits.com/.  I forgot who runs it.  Lookups can also be done at blockchain.info.
newbie
Activity: 33
Merit: 0
Free, is firstbits.com discontinued or just temporarily down? Thanks.
legendary
Activity: 1246
Merit: 1016
Strength in numbers
I think I fixed it, it seems to load instantly for me now.

It's odd because I hadn't changed a thing in months.

Please tell me if it works for you now Bkk.
Yup. Seems to be ok now. I'm deep in the rice fields of SE Asia so whatever caused it to be slow was exacerbated ten fold here.

Cool. Thanks a bunch for letting me know and following up.
hero member
Activity: 784
Merit: 1009
firstbits:1MinerQ
I think I fixed it, it seems to load instantly for me now.

It's odd because I hadn't changed a thing in months.

Please tell me if it works for you now Bkk.
Yup. Seems to be ok now. I'm deep in the rice fields of SE Asia so whatever caused it to be slow was exacerbated ten fold here.
Pages:
Jump to: