One particular case of the bitrot problem was the Microsoft Windows problem known as “DLL Hell”, DLLs being binary dynamically linked libraries in Microsoft Windows.
Over time these libraries tended to be upgraded, improved, and changed, and programs written for the old libraries would develop bugs with the new libraries, sometimes these bugs were crash and burn bugs, “bitrot”, sometimes there were unexpected interactions between programs using the same library, which caused one program to accidentally foul up another, or enabled one program to maliciously manipulate another.
This problem was solved. The solution was “COM”. In COM, dynamic linking necessarily involves version negotiation. Mandatory version negotiation largely relieves bitrot.
In COM, in accordance with Zooko’s triangle, each version of a library’s behavior, each library interface, has three names. Describing those names and their behavior from the point of view of Zooko’s triangle, which is not how most Microsoft programmers would describe them or think about them:
In order for a program to connect to any COM library (what Microsoft calls an ActiveX object), it has to do protocol negotiation in order to get an interface, has to ask for the interface by its globally unique identifier, so the library always knows what version of the library the program expects, and will provide that behavior, or, if it cannot provide that behavior, the program will fail immediately with an error message explaining the problem.
This solution worked. It solved DLL hell, solved bitrot.
Windows implementation of this solution was less successful in dealing with another problem – library calls often cross thread and process boundaries. They provided a general purpose threading solution, also part of COM, which was hideously complicated and failed dismally. But they fixed bitrot.
Cross thread and cross process interactions usually wind up being implemented as message streams and message queues. The correct approach is to make this explicit, to define the interface as a message protocol, rather than attempting to hide the underlying message queue behavior as Microsoft did and pretend it is an ordinary synchronous object method. Where COM runs on top of message queues, as it does whenever a call crosses thread or process boundaries, the result is intolerable obscurity, complexity, and inefficiency – which is still a lot better than the bitrot that it fixed.
A pool is a shared collection of transactions with a single schema and protocol, but no global transaction order.
A blockchain is a shared collection of transactions with a single schema and protocol with a global order and a sequence number for every transaction. Every blockchain has a pool, and transactions are added from the pool to the blockchain by a process for constructing consensus on order.
There will be many blockchains, though we would prefer only one. One is likely to emerge supreme, but there will always be forks and competing blockchains, and forks and competition have to be lived with until they are resolved, which is apt to take a long time.
Because establishing a global order is costly, there will be many pools without blockchains. If you don’t need a global order on transactions, don’t pay the costs of constructing one. Usenet was an immensely valuable pool without global order, and it was a great pity that it died. I want to replace it.
There will be necessarily be many schemas and many protocols. A blockchain should assign a globally unique arbitrary precision number to each pool, schema, and protocol, but there will be more than one blockchain, and pools outside any one blockchain.
Although the number is in principle arbitrary precision, each peer, host, and client will have an arbitrary limit to the precision of the identifiers that they will handle. They have to be able to handle at least sixty three bits, often sixty four bits, and have to be able to fail gracefully with identifiers that exceed their precision. Anything with an identifier that exceeds their precision limit will not exist for them. In practice, most identifiers are likely to less than eight bits.
A peer continually checks in full that its blockchain follows or follows from the blockchain of its peers, an operation that is costly. It terminates communication with any peer that is forking. A client treats its host peer’s version of the blockchain is the authoritative one true version of the blockchain.
A client necessarily has communications with many peer hosts. If one of its peer hosts has a block number and root hash for that block of the blockchain that is different from that of another peer host, it has to terminate communications with one peer host or the other, and terminate interactions concerning that blockchain with other clients that rely on a peer host with discrepant block for what is purportedly the same blockchain.
Every blockchain, every pool, every schema, and every protocol has a short human readable name, but this name is not necessarily globally unique. Indeed, for schemas and protocols, certainly not globally unique, because schemas and protocols are always being updated, and we don’t want to change the name every time, and pools are continually being updated, with no two peers on a pool necessarily having exactly the same pool.
A blockchain on one peer is the same as the blockchain on another peer if its root hash is the same, or follows, or follows from, the root hash on the other peer, but for pools, we have no definition of a pool being the same that a computer can check. But a pool has a schema and a protocol, and that the computer can check.
Schemas and protocols have version numbers, which are deweydecimal sequences of arbitrary precision integers, but even these are not guaranteed to be globally unique, though any one blockchain may choose to ensure that the list of schemas and protocols for which it provides unique arbitrary precision identifers have globally unique names and deweydecimal numbers.
The globally unique identifier of a schema or protocol is a thirty two byte probabilistically unique number, which may be the twenty byte globally unique identifier of a git commit, preceded by as much of the start of the name and the trailing end of the dewey decimal sequence as fits, albeit likely not much fits in twelve bytes.
When establishing communication, the setup relies on a hash value that employs the globally unique identifiers of everything relevant to the communication, so that communication will immediately and gracefully fail if the parties establishing communication are in disagreement about what protocols and and schemas they are employing. But first they have to figure out what protocols and schemas the other party is using, relying on identifiers that could potentially have conflicting meanings.
When establishing communication in a blockchain context, they rely on blockchain unique arbitrary precision integer identifying the schema or protocol. But there may be no such agreed context, or they may be communicating about a pool that is not on the blockchain, or not on any blockchain, for example a transient pool set up to establish a shared multiparty transaction to mingle crypto currency, which requires a blockchain context, but will not be identified by the blockchain, though it will rely on a schema and protocol that is identified by the blockchain.
A transient pool set up to organize a multiparty transaction has a nickname, petname, and deweydecimal number, which deweydecimal is likely to be the number of pools of that name the entity starting the pool has attempted, hence highly likely to not be globally unique, or even blockchain unique. Maybe not even unique to that entity.
To identify a pool, a schema, or a protocol in a context where there is no authortative guarantee of unique integer identifier, the parties send a fragment of the probabilistically unique thirty two byte identifier, consisting of a four bit multiple of sixteen bits of offset into that identifier, and sixty bits of the intentifier. Thus each full 256 bit identifier has sixteen possible 64 bit identifers. The parties systematically or randomly change which of the sixteen they use, in order to escape collisions.
The parties look up a hash table of recently used 64 bit identifiers, and if that fails, an associative array of sixty four bit identifers. If there is a collision between sixty four bit identifiers, neither of the colliding sixty four bit entries are entered into the associative array, but when a twofiftysix bit identifier is used that was not found in the hash table, all sixteen sixty four bit identifiers go into the hash table, so that a seldom used two hundred and fifty six bit identifier that has a colliding sixty four bit identifier has its colliding identifier masked by a frequently used two hundred and fifty six bit identifier.
In the unlikely event that a collision exists in the space of all sixtyfour bit identifiers known to a particular entity in the associative array, it cannot collide in the space of sixtyfour bit recently used identifiers in the hash table.
Thus a pool, a schema, a blockchain, or a protocol is identified by its far from unique nickname and petname, its name plus its usually but not necessarily unique deweydecimal number, its globally unique 256 bit identifier, and sixteen sixty four bit identifiers, which are overwhelmingly likely to be unique, but can fail (very very rarely). If the sixtyfour bit identifier fails then the communication fails that one time, but will succeed, with at least fifteen sixteenths probability, another time.
In the highly unlikely event that an identifier has a sixty four bit collision with a commonly used identifier, this is a a problem for the less commonly used identifier, since one in sixteen connections will fail. If a hash table has eight thousand entries, corresponding to five hundred commonly used entities, the likelihood of any one randomly generated long identifier having a collision of one of its sixteen short identiers with a commonly used identifier is one in 100 000 000 000 000, which is too low to worry about. Potential collisions between two rarely used identifiers do not matter, because if someone is using a rarely used identifier, it likely to be commonly used identifier for him and the people he is communicating with.
The worst case is a collision between two commonly used identifiers, but the more restrictively we define "common" the less likely such a collision. If a group of people are commonly using fifty entities, then the chance that two of those entities have a collision in one of their sixty four bit identifers, resulting in one of their entities leading to communication failure one sixteenth of the time, is one in 30 000 000 000 0000.
When setting up a pool for a multi party transaction, the parties initially communicate with each other in a namespace controlled by a single blockchain, hence have blockchain unique identifiers for protocols and schemas, hence the only collision possible is between pools, and there will not be all that many multiparty transactions going at any one time among the people a party is interacting with, though the number of possible multiparty transactions being organized at any one time is potentially very large.
If the user is looking for subscrbers to a particular pool among subscribers to a hundred thousand pools, each subscriber subscribing to a hundred pools, it will be enormously rare for him to misidentify a subscriber to a different pool as a subscriber to his own pool and then attempt to communicate with that subscriber, and such misidentification will merely slow things down imperceptibly, not halt things. The communication with that subscriber will simply fail. Failure for other reasons is enormously more probable.
Sixtyfour bit identifiers suffice for most practical purposes, provided that the communication protocol is such that misidentification of the corresponding twohundredfiftysix bit identifier results in immediate graceful communication failure.
There are some cases where sixty four bits do not suffice, for example identifying a transaction on the blockchain. In such cases, we use the blockchain transaction sequence number, which is globally unique to the blockchain, or the full twofiftysix bit identifier, which is proabilistically unique. An entity in the context of a blockchain is identified by its transaction number, and its output/input number within the transaction, though the blockchain itself is identified merely by a short human readable string, which in the presence of forks and competition, is likely to cause potential misidentification. The sequence number of inputs to a transaction follows, rather than precedes, the sequence number of inputs, which resolves potential ambiguity at an average waste of one bit in the rare case that one references an input, rather than an output.
If there was a consensus on what identifiers were common, we could get away with variable length identifiers. But this leads to the TLA problem. Hard to establish a consensus, hard to know what it is. If you have a system that drifts towards consensus, such as the english language, what drives the drift is that collision problems happen. But you don’t want collision problems to happen, because then you need rather complex code for handling that case, and a complex data structure to describe estimates of what the consensus likely is.
So, we have an identifer that establishes an explicit context, a map of probabilistically unique twofiftysix bit identifiers to indefinite precision integers and to short human readable strings. The blockchain provides such a mapping, and the pool references the blockchain. But a pool cannot contain such a mapping, unless it has its own blockchain.
These documents are licensed under the Creative Commons Attribution-Share Alike 3.0 License