Click link for the updated protocol specification: https://www.xoken.org/technology/allegory-allpay-protocol-suite/
‘Allegory’ a generic naming protocol with a fundamental focus on user autonomy that integrates seamlessly with Bitcoin.
‘AllPay’, a user friendly payment addressing protocol that works on Allegory supporting self-sovereign payment usernames.
Advantages of AllPay over paymail, with trade-offs considerations
This document is not a protocol specification for Allegory/ AllPay; and outlines some open problems.
The problem of decentralized namespaces has long been recognized as an important one. The three desirable properties namely security, human-meaningful names, and decentralization form a trilemma in the context of network protocols and is known as Zooko’s triangle. Until blockchain (Bitcoin) came along, designing a system that exhibited all three was conjectured to be impossible.
The Namecoin protocol is based on Bitcoin with relatively minor changes and additional functionality built on top on it. The mining procedure is identical but the block chain is separate, thus creating its own native currency. Because of the different intended use cases between the Namecoin & Bitcoin, consensus and protocol rules might make sense in one but not the other,
Namecoin’s consensus rules need to enforce uniqueness of names. While it is possible to store data in Bitcoin (e.g. key/value pairs in OP_RETURN outputs), uniqueness is not enforced by Bitcoin. It would be theoretically possible to build a layer on top of Bitcoin that discards OP_RETURN outputs that don’t respect uniqueness (e.g. a name operation that steals someone else’s name), but any such layer would not be enforced by miners. If transaction validity rules are not enforced by miners, then they are not backed by PoW, which means that SPV-based lightweight clients will fail to enforce those validity rules.
Coinbase commitments to the name database could be enforced by Namecoin consensus rules, allowing SPV proofs of a name’s nonexistence to be created.
Although it is theoretically possible to use Namecoin as a general-purpose currency, it is not encouraged and is limited to being a sidechain (merge-mined with Bitcoin), which has its own set of problems and limitations.
Handshake focuses on the DNS problem and intends to replace centralized trusted internet infrastructure, with a decentralized Certificate Authority and globally unique namespace composed of a decentralized blockchain and cryptographic proofs backed by crypto-economic mechanisms.
Provides canonical ownership records by recording the order of each record, even with canonical ordering, the problem of namespace allocation remains. A currency native to the blockchain is necessary to create a cost function for the names and hence prevent spam registrations. When a name is auctioned and sold, the coins are permanently destroyed from the system. Transaction outputs inherently enforce order of transactions within a block. Order-enforcement in particular is necessary for the protocol to function with the utmost security. The naming system requires on-chain smart-contract-like behavior. It deals in outputs which need to update a global state. This is atypical of UTXO systems. But as such, it requires that these operations occur in a predictable order.
In order to be free of the full node requirement, the Handshake protocol requires an authenticated data structure. In particular, a data structure which can efficiently map keys to values. The data structure stores colliding prefix bits on internal nodes, resulting in a base-2 merkelized radix tree similar to the Merklix Tree. Involves additions and removals in the radix tree Proofs of existance or non-existance of names involve providing the hashes of nodes in the merkle path. Proof sizes vary depending on the tree structure.
The primary downside is its an independent chain with its own native coin, and is unsuitable for Bitcoin purposes. Also it is purpose built for DNS and not available for general purpose use.
Similar to how Bitcoin prevents double spending, a naming protocol’s objective is to ensure names remain unique, and no two users/addresses can acquire the same name. The Namecoin protocol, which is recommended to be merge-mined with Bitcoin has its own consensus rule to enforce name uniqueness. So the Namecoin nodes have to maintain a database of all acquired names and must ensure they are not simultaneously owned by another address.
Bitcoin system already prevents UTXOs from being double spent, so if we were to associate unique names to UTXOs, the names would now inherit the uniqueness property. A naive transaction design would have an explicit claim/stake for a particular name, but such a system would need elaborate name databases and changes to transaction validation (reject duplicate name claims). This can be vastly improved by having a deterministic key-’word’ derivation function that works over a radix tree data structure, where for any given input always leads to a unique new name registration (based on current global state) and this updated global state is committed to Coinbase with a Merklix root. Although the implicit name staking mechanism is efficient, it does not justify pursuing this naive approach, as it still needs a Bitcoin consensus change for including Merklix root commitment in the Coinbase.
The Allegory protocol works supplementary to the existing Bitcoin protocol, and does not not demand Bitcoin consensus change (no hard-fork or soft-fork). Also the protocol allows efficient SPV name resolution in the absence of a trusted full node, which is an important requirement for the widespread adoption of any naming protocol.
The protocol is set in motion by a name-genesis event, the legitimacy of which is accepted by all the Allegory naming protocol system participants, which include light (SPV) clients, name lookup nodes, name resellers & miners.
The name-genesis is a marathon mining event (adhering to democratic & capitalistic tenets of Bitcoin), that will conclude with miners acquiring all the earmarked name branches. Instead of a single genesis block that birthed Bitcoin, the name-genesis will be a series of blocks likely spanning a few days, to ensure the root name distribution is fair and wide and is not subverted by a concentrated attack.
The name-genesis event is preceded by social consensus, which decides on the following,
- The starting block height that will kick-off the name-genesis event
- The earmarking of primary name branches (nomenclature) and their ordering (say lexicographical order i.e. ‘aa’, ‘ab’,...)
It might be naive to lexicographically order and allocate a fixed number of the primary name branches to each upcoming block, as the Lexicographical Preferences associated with real world names means some blocks may attract higher hash power over others, this may affect the miner economics as Bitcoin block reward is not the sole incentive during this phase. In expectation lexicographical preferences would have to taken into account for finalizing the name branches and their respective block-heights through social consensus.
A name can be simply defined as a finite sequence of alpha-numeric characters (with some select special characters allowed i.e. hyphen, dot & underscore), also names are case insensitive.
Just like Bitcoins can be lost forever, the Allegory names can be lost forever as well. An attacker might seek to sabotage the system by permanently destroying names, but the high economic cost of attack should refrain an rational attacker from doing so.
Names originate as primary name branches from the name-genesis event and are represented by the Coinbase transaction outputs (multiple) of the corresponding miners. A Name-UTXO (nUTXO) is just like any other TXO, but it has an additional name property bestowed besides the traditional Satoshi value. A nUTXO can be spent (effectively transferring the name) to other Bitcoin users/addresses just like a plain old UTXO, but it comes with certain additional implicit properties.
- A nUTXO can spawn new child names. The n*TXOs form an Trie (prefix tree) like structure of name nodes, with a name-genesis TXO at the root. There is no explicit limit to the depth of the tree. A node's position in the tree defines the keyword with which it is associated. All the descendants of a node have a common prefix of the string associated with that node leading all the way upto name-genesis UTXO.
- A nUTXO can create one or more child names selectively at each spawning transaction, there is no compaction involved as in the case of Radix trees, and every name will have a legitimate fully qualified name parent (except for origin name branches from name-genesis)
- A child name can be created by the parent name owner at any future point as long as the child name was never created earlier.
- The chain of signatures from the primary name branch TXO to the particular name's UTXO will help validate the name.
A nUTXO spending transaction can produce the following derivatives (under given conditions):
- A progenitor UTXO, which provides the unconditional right to spawn next immediate unique child names anytime in future. This can be produced only once, typically done on the first name transaction. This allows a name merchant to sell a name to another user by withholding the name spawning rights. Similar to how pedigree puppies are sold with limited registration papers which deny breeding rights to the buyer.
- A secondary UTXO meant to be shared with a trusted 3rd party service which acts as your proxy by offering certain services. E.g A new HD address generation service(output script in actual) for senders. More on this in subsequent sections.
- Zero or more child nUTXOs. If every nUTXO transaction spawned all its potential children eagerly, as we have about 40 valid characters, if we assumed a future state where all name branches grew beyond 10 characters long, then the UTXO address space would be well above 40^10 = 10485760000000000, to avoid this unnecessary growth of UTXO DB and corresponding over-consumption of limited Satoshis, we adopt a sparse need based spawning approach.
- A new successor nUTXO which now possesses the name, and can be used to subsequently sell associated name to a different user, or even generate new secondary nUTXOs.
Thus every transaction spending an nUTXO, produces a new successor nUTXO (name will be considered permanently destroyed if missing) and zero or more child nUTXOs. Also conditionally the corresponding secondary UTXO & progenitor UTXOs can be included. These are identified by adding an additional OP_RETURN output (unspendable with 0-value) to the transaction, which contains the template with references (index) to the sibling outputs and defines their type and other details. The actual template notation is skipped for simplicity, but the following describes the crux of it.
- User can explicitly register a service provider by including the 'proxy' keyword, the service URL (REST) and the index of referenced output. Additionally such registrations can be time bound, denoted by expiry timestamp, and will subsequently expire.
- Shall reference a particular output index and declare it as a progenitor UTXO, if not previously done for this particular name.
- Shall reference a particular output index and declare it at a child nUTXO with a particular unique name. This is achieved by including a single new valid character against the output index. It is recommended to include only the next character in the name Trie, and not the full name explicitly to avoid lazy/buggy implementations of SPV clients that may incorrectly go with the explicit name instead of deriving/validating name for oneself.
- Shall reference a particular output index and declare it as successor nUTXO, which indicates name ownership.
It is desirable to establish a lower and upper bound on the verification complexity for the chain of signatures, if all children are spawned at one go, and if we assume the name branch string length of 2 (name-genesis) then the signature chain length is n-2 for a name of length n. The upper-bound case is when only one child name is spawned at a time, and our name validation has a worst case scenario of involving letters that were all spawned last in order, then the complexity is 40 * (n-2). In both cases we are assuming the spawning rights were retained by the original miner, which is a reasonable assumption as there will be name resellers who will consolidate the function of name spawning / selling. Although the lower bound calculations seems impractical due to the huge growth of UTXO DB, its likely the most used/desirable character sequences will be spawned early and together due to demand. The lower, average & upper bounds shown above make it a practical viable solution.
It is important to note the above Allegory naming protocol consensus rules are NOT validated and enforced by Bitcoin miners, the miners operate oblivious to the naming protocol. The consensus on the name's validity is at the light client and name lookup node level. In the event a duplicate child is created the naming protocol participants reject this nUTXO and reduce it to a plain old UTXO. The name resolution remains unambiguous to all the protocol participants.
Typically nUTXOs are not meant to store value as they serve a different (naming) function, and could typically hold a few Satoshis, but there is nothing restricting an UTXO from storing large arbitrary number of Satoshis. Similarly there is no Bitcoin protocol level restrictions on merging two nUTXOs as inputs of a given transaction in effect producing fewer outputs(than inputs). In this case Allegory will discern the joined output to represent the collective names of its inputs and proxy rights. To avoid ambiguity, the child spawning are restricted on combined nUTXOs, until they are split to their individual states. Also, a nUTXO can be combined with a plain old UTXO to produce a nUTXO of same/different value, this could be useful if a parent nUTXO does not currently hold enough Satoshis to spawn required children.
A nUTXO's perceived market value comes from its implicit name/keyword association and it typically holds insignificant/minimal Satoshi value. The marketplace would need a mechanism to seamlessly exchange such nUTXOs with relatively higher value UTXOs (likely with no name) with no counterparty risk. This can be achieved on-chain by atomic swaps, where the buyer and seller draft a transaction mutually with signed inputs from both parties and the agreed outputs, this transaction when broadcast and eventually accepted in a block atomically commits the trade.
The SPV clients can resolve names independently without having to trust a 3rd party name lookup node, or even having to query multiple such nodes to reduce risk of fraud. This involves validating the chain of signatures leading from the name-genesis TXO to the appropriate node/position in the n*TXO Trie. Since the SPV client lacks the full set of blocks & transactions the name lookup node would have to assist SPVs with the Merkle path for validating each of the internal UTXO nodes in the Trie. Although SPV name validation involves relatively higher processing complexity than a traditional transaction validation, this is typically done only once while adding a recipient in the wallet or when buying /acquiring a name for use.
SPV wallets with Allegory protocol functionality will incorporate a marketplace to buy/register names (possibly even sell), and to lookup potential recipients based on their user friendly names/handles. More importantly they need to have the additional naming logic to be prudent about correct usage of nUTXOs, as basic wallets could unwittingly mistake nUTXOs to dust UTXOs.
A namespace is simply a container for a set of names, so that names in a single namespace are unique but the same name can exist in different namespaces. To achieve this, namespaces can be classified by name prefixes meant for exclusive use of each application. Namespaces help prevent multiple applications from conflicting with each other. The Allegory protocol itself isn’t aware of namespaces, and namespaces don’t have any effect on validation rules; they are only used by higher-level applications that use the protocol.
E.g.
- d/com.example.api represents the domain name api.example.com
- id/alice ‘id’ stands for global identity namespace; ‘alice’ is unique user identity.
- a/ap/carol ‘a’ stands for generic application namespace; ‘ap’ for AllPay application; ‘carol’ unique user.
AllPay allows self-sovereign user friendly payment addressing on Bitcoin. It serves similar functionality as Paymail, but with a fundamental focus on user autonomy, and is superior and flexible in many other regards as well.
The user friendly payment addressing problem is a common problem for the below,
- Always Online wallet use-cases (merchants: always online & In-store QR scan driven transactions)
- Intermittently Online wallet use-cases. (individual wallets which is mostly offline, but appear online intermittently driven by user action)
Interesting they have a common solution, wherein the user registers a proxy service for the destination address generation (output script to be precise), as part of the Allegory naming protocol described above.
These proxy service registrations can be short or long-lived and left to user’s choice. Unlike Paymail protocol’s email like identifier, which is permanently locked-in with its service provider (denoted by domain name), the AllPay username is completely user owned and can frequently switch service providers voluntarily for a variety of reasons enhanced privacy, flexibility, price, QoS etc.
The crux of this protocol involves atomically accomplishing the below in a single transaction
- sending Bitcoin to the recipient
- validating the authority of the service provider by demanding the claimed Unspent TXO to be included in the transaction.
Thus - The only way to prove your Txout is unspent to a SPV client on Bitcoin is by actually spending it.
Before we go into the use-case call flow details, I would like to address a potential scalability concern that might have occurred to a careful reader, owing to the dependence on UTXOs and the complexity of validating chains of signatures especially in the AllPay (proxy service) scenario.
Once a user ‘A’ has handed over his secondary UTXO to a 3rd party service, the service continues to propagate this UTXO further down the chain for each AllPay address generated (for each inward transaction to user ‘A’). This at first seems unsustainable as the chain for sender validation could grow exceedingly large. But interestingly, the user ‘A’ can revoke the latest secondary UTXO from the 3rd party, who is obliged to provide the same, and issue a newly created secondary UTXO (per Allegory protocol) to either same or different service provider. This action might not even involve user input and can happen behind the scenes once a certain secondary TXO chain limit is reached and is triggered the next time the user’s wallet appears online. A SPV wallet only ever needs to validate the latest secondary UTXO chain, as the User (primary) has over ridden and closed the loop on the previously issued secondary UTXO chain. There is no risk that a SPV wallet might ever be misled by a previous service provider (now turned malicious) as the service provider does not possess a spendable secondary TXO, as it was revoked by user (primary) before reissuing the next secondary UTXO. Although explained using a linear UTXO chain, the Secondary UTXO logic will actually work as a multi level hierarchy & hence drastically reduce SPV validation complexity. This is addressed in the final 'Privacy' section.
The below two modes are to be simultaneously offered to users with different benefits and trade-offs. Users/wallets can make the protocol choice based on their needs.
- This mode is basic and relatively simple.
- In this mode proxy registrations are made directly on the Bitcoin blockchain per Allegory protocol by providing the service provider URI.
- The wallet(SPV) will negotiate fees, period etc. and procure the registration commitment (digital signature) from the service provider (interactive/ offline) before producing the proxy registration transaction for inclusion in the next block/s.
- Even though the xPub extended public key derivation would be done at provider end, the user privacy is minimally sacrificed as the wallet can trivially change service providers by issuing a new child public key (for xPub). This diversification logic may or may not need user input depending on wallet configuration and would improve privacy.
- To safeguard from spoofing, DNS/DNSSEC/TLS vulnerabilities, service provider breach by hacker or going rogue etc., additional security measure is included in the protocol.
- During proxy registration the name wallet includes a merkle commitment from a pre-compiled list of consecutive HD addresses(leaf nodes). The address list length optimization can be left to wallet implementation and user configuration.
- The sender can validate that the recipient's service provider is indeed producing a genuine unique receive address by verifying the Merkle path against the commitment.
- This completely removes the need to trust the 3rd party service provider, and hence deeemed safe even for super high value transactions.
This involves a slightly more elaborate call flow giving user greater autonomy and privacy. This should be likely preferred by most individuals & businesses who expect to receive bitcoin transactions from authorized senders.
In essence it it this,
- Incoming add/ approve contact requests are registered on-chain or delegated to service provider (proxy)
- Next time the wallet comes online, the pending approve-contact requests can be confirmed based on user input.
- This will involve an asynchronous flow of messages (authenticated with signatures) mostly on-chain where a freshly generated child public key can be provided to the sender/contact for subsequent transactions. Each transaction can be using a different To address under xPub scheme.
- Allows the global on-chain storage of contact-book along with the registration info, without compromising privacy. Even if the user device is lost and he/she restores a new wallet from the original seed, all contacts and exchanged xPub keys will be restored and fully operational.
To add more detail:
- In this mode the sender gets pre-authorized (by the recipient) so that subsequent transactions can take place directly i.e. by circumventing the AllPay proxy service as shown in 'Public' mode.
- Initially (only once) the recipient interacts (via API) with the recipient's AllPay proxy service to obtain the unique 'Invite' address (so the recipient contact book can remain private). This works on the same atomic Tx principle (as in Public mode) i.e. the Tx includes the unspent TxO that helps sender validate the service provider.
- The sender issues an "add contact" request - on chain - to the recipient's 'Invite' address (needs a few Satoshis). The pending Invite can be subsequently (asynchronously) accepted by the recipient's wallet, i.e. by a return Tx which includes an encrypted xPub (decipherable by recipient) in OP_RETURN.
- To ensure the ‘Invite’ address is not compromised (spoofing , breach etc.), the proxy registration includes a Merkle commitment of pre-compiled address list, which can be trivially validated by the sender. This offers unparalleled security guarantees, and peace of mind for the user.
- This process is half-duplex i.e. allows one-way authorization, a recipient can share his xPub with a recipient. Likewise the vice-versa is also needed if both parties wish to transact bi-directionally in a secure and private manner using their AllPay identities.
- It is also possible to eagerly instruct a potential future sender to use the pre-authorized xPub (without waiting for the "Invite" request). This "Refer" push request can be initiated by the recipient typically after the first Tx via the Public mode.
- The protocol also likely warrants a xPub re-issue feature in the event of a compromise for continued privacy. This should be simple to design and is omitted in this document.
AllPay ensures the username is ones own, and allows users to freely change service providers seamlessly and stands to benefit the user with no major downsides. Registrations and other on chain transactions are left to the miners discretion and should be very cost effective.
Privacy is a very important feature, which is lacking in 'paymail' and hence we set out to address it with Allegory/AllPay. But from the description above the on-chain nature of AllPay address generation (by proxies), makes every single transaction transparent and unambiguously ties them all to its AllPay recipient. This is because all the successor UTXOs corresponding to the subsequently generated AllPay addresses are linearly connected and visible to everyone.
Thankfully there is a rather simple solution to restore privacy despite generating the AllPay addresses on-chain. We take the ‘privacy by obscurity‘ approach, the totally obvious linear chain of successor UTXOs will need to be obscured so that data analysis yields very low (negligible) success rate if at all.
The proxy service during registration negotiation offers a Merkle commitment of a set of UTXOs, this token represents a promise to prove all the UTXOs of the set are spent, when the AllPay ID owner decides to revoke the contract with service provider.
Also the new successor nUTXO (which possesses the name) is now not the direct child of the previously spent output, instead it will be one of the randomly picked UTXOs from the Merkle committed pool. The sender’s SPV wallet will simply need to validate that the UTXO was either - (a) directly included in the Merkle commitment or - (b) the UTXO is a direct descendant of '(a)'. This can be validated with the help of Merkle path & commitment root from the providers.
An AllPay subscriber can set a threshold on UTXO set size of the commitment, depending on its privacy needs. When the contract is being terminated, the proxy service needs to spend all the UTXOs in the contract’s commitment (or their descendants) to the subscriber.
It seems a brute force attack on the entire UTXO set of the service provider (if one can obtain this at all!) can be used as an exploit to decode the recipient’s transactions i.e. by finding the matching the commitment Merkle root hash. But this is trivial to prevent, by simply salting the leaf nodes of the Merkle tree and revealing the salt values along with the Merkle paths as necessary.
There is another potential problem of exhausting the UTXOs of the registration commitment by an attacker, it is trivial to set a minimum inward deposit that will be accepted by the service provider, this will require an attacker to spend potentially a few thousand times the minimum inward deposit threshold . But even if the attacker is willing to spend large amounts out of pocket just to break the privacy, this attack can still be prevented by making the spendable UTXO set dynamically grow off of the static Merkle commitment yet maintain privacy. These elaborate solutions are out of scope for this paper.