FirstBits.com - remember and share Bitcoin addresses

[Jan]

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?

[1714106551]

1714106551

[1714106551]

1714106551

[1714106551]

1714106551

[1714106551]

1714106551

[1714106551]

1714106551

[1714106551]

1714106551

[SgtSpike]

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]

Thanks.

Regarding Abe read here: https://bitcointalk.org/index.php?topic=16217.msg960077#msg960077
and here: https://bitcointalk.org/index.php?topic=16217.msg1044812#msg1044812
Just a few posts upstream :-)

[John Tobey]

I wasn't even aware that Abe even performed firstbits resolution.

Let me refresh your memory.   https://bitcointalk.org/index.php?topic=16217.msg957933#msg957933

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://bitcointalk.org/index.php?topic=16217.msg960077#msg960077

[SgtSpike]

I wasn't even aware that Abe even performed firstbits resolution.

Let me refresh your memory.   https://bitcointalk.org/index.php?topic=16217.msg957933#msg957933

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://bitcointalk.org/index.php?topic=16217.msg960077#msg960077

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.

[John Tobey]

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:

- We compare your address to all addresses appearing in the same block or before yours in the block chain.
- We return as many characters as needed to differentiate your address from the others.

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.

[SgtSpike]

Touche on the about page.    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://bitcointalk.org/index.php?topic=11481.0

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?

[John Tobey]

Touche on the about page.    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...

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://bitcointalk.org/index.php?topic=11481.0

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. 

[SgtSpike]

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. 

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.

[John Tobey]

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?

[Jan]

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  

A pubkey output is a transaction output with a script of the form:

Code:

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

A pubkey hash output is a transaction output with a script of the form:

Code:

OP_DUP OP_HASH160 <pubKeyHash> 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).

A script hash output is a transaction output with a script of the form:

Code:

OP_HASH160 <scriptHash> 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).

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.

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.

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.

I'll have something for you to review later today

[Jan]

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:

<pubKey> 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 <pubKeyHash> 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 <scriptHash> 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.

[SgtSpike]

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]

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.

[SgtSpike]

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.

It would be interesting to find an example of such a case to compare how it is resolved on any services that work with firstbits.  I have a feeling they are not all resolved in the same manner.  I disagree regarding complexity - I think it actually makes implementation much simpler, which is why I like the change.  Yes, it will invalidate a few specific firstbits - perhaps we should run some sort of script to find out exactly which firstbits would be invalidated.

[Jan]

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.

It would be interesting to find an example of such a case to compare how it is resolved on any services that work with firstbits.  I have a feeling they are not all resolved in the same manner.  I disagree regarding complexity - I think it actually makes implementation much simpler, which is why I like the change.  Yes, it will invalidate a few specific firstbits - perhaps we should run some sort of script to find out exactly which firstbits would be invalidated.

It is actually more complex to regard all transactions in a block in a holistic way rather than just handling them one at a time.

However, here is the definition we got so far for transactions in the same block (which is actually used today):

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

If you make a less complex description that unambiguously describes your way of handling collisions I'll agree with you.

[John Tobey]

Thank you, and sorry for the delay!

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.

I don't think this is true or needed.  Some addresses have no firstbits base representation, because an address differing only by case appeared earlier.

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.

This is good but could be clearer.  How about:

The firstbits base representation of a Bitcoin address is the shortest non-empty, initial substring of the address, converted to lower case, which is not the firstbits base representation a firstbits address of another address appearing earlier in the block chain.

(Appearance implies "in a transaction output" as specified below.)

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:

<pubKey> 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 <pubKeyHash> 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 <scriptHash> 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.

It is actually more complex to regard all transactions in a block in a holistic way rather than just handling them one at a time.

However, here is the definition we got so far for transactions in the same block (which is actually used today):

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

If you make a less complex description that unambiguously describes your way of handling collisions I'll agree with you.

I don't have a strong preference.  Abe does use enough characters to distinguish from addresses later in the block.  I think the code was simpler before I did this.  I don't think conceptually either way is more complex; you choose between defining "order of appearance" and "same or earlier block".  I strongly suggest finding an example and checking blockchain.info's treatment of same-block collisions, since that site obviously has a lot of work put into it and may be unwilling to change.  And let's try to include piuk.

[John Tobey]

I edited my last reply to ensure that "collision" includes collision with longer substrings.  For example, 1SgtspiQ... has a substring 1Sgtspi which collides not with 1SgTspiK's base representation, but with a firstbits address derived from it.  So the base representation of 1SgtspiQ... must include the Q.

[SgtSpike]

I don't think this is true or needed.  Some addresses have no firstbits base representation, because an address differing only by case appeared earlier.

The chance of two addresses only differing by case is something like 1 in 34^34 (or 34^27 if you're looking at the shortest possible Bitcoin address), is it not?  If so, I'd say we can safely assume no two addresses have been, or will ever have, the same address differing only by case.  Even 24^27 is such an impossibly high number as to conclude it will not happen within the life of the earth.

I don't have a strong preference.  Abe does use enough characters to distinguish from addresses later in the block.  I think the code was simpler before I did this.  I don't think conceptually either way is more complex; you choose between defining "order of appearance" and "same or earlier block".  I strongly suggest finding an example and checking blockchain.info's treatment of same-block collisions, since that site obviously has a lot of work put into it and may be unwilling to change.  And let's try to include piuk.

I agree.  Since all three of us seem to be willing to change, let's see what blockchain.info is doing and go from there.

EDIT:  As luck would have it, Firstbits doesn't appear to currently be working on blockchain.info at the moment.

[John Tobey]

I don't think this is true or needed.  Some addresses have no firstbits base representation, because an address differing only by case appeared earlier.

The chance of two addresses only differing by case is something like 1 in 34^34 (or 34^27 if you're looking at the shortest possible Bitcoin address), is it not?  If so, I'd say we can safely assume no two addresses have been, or will ever have, the same address differing only by case.  Even 24^27 is such an impossibly high number as to conclude it will not happen within the life of the earth.

Nevertheless, if I recall correctly, examples do exist, presumably where one address is not generated in the usual way (and coins sent to it are therefore dead).