Allegory & AllPay protocol suite

‘Allegory’ generic naming protocol & ‘AllPay’ user-friendly payment addressing

Index

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

Preface

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.

Other specialized solutions such as Namecoin required explicit consensus rules to enforce uniqueness of names but inherently lacked economic security and thus limited to merge mining (with Bitcoin). Other native decentralized naming solutions have been developed for public blockchains that offer global state (Ethereum), but unfortunately the underlying Layer-1 does not scale well. Allegory protocol as described in this paper is the first and only solution that is designed to natively work on Bitcoin's highly scalable UTxO model without needing the slightest change to the Bitcoin protocol. AllPay is an application protocol which builds on the underlying Allegory protocol to offer user friendly self-sovereign payment addressing.

Allegory Naming Protocol

Allegory is an application protocol that works supplementary to the existing Bitcoin protocol, and does not demand a Bitcoin consensus change (no hard/soft-fork). Also the protocol allows efficient SPV based name resolution (Simplified Name Verification) in the absence of a trusted full node, which is an important requirement for the widespread adoption of any naming protocol.

The Allegory protocol is set in motion by a single genesis transaction, just another ordinary Tx for Bitcoin, but a pivotal one for Allegory protocol . All the Allegory naming protocol system participants, which include light (SPV) clients, name lookup nodes, name resellers/miners etc will recognise the genesis transaction, moreover the reference server & client software will be open-sourced on an OpenBSV type license, which grants essential freedom for the ecosystem to adopt while protecting unethical imitation.

The fundamental underpinning of the Allegory protocol is the name-UTXO (nUTXO). A nUTXO is just a regular UTXO with additional name property bestowed upon it discernable by the higher layer Allegory protocol.

A nUTXO can be spent (effectively transferring the name) towards other Bitcoin addresses just like a regular UTXO, but it comes with certain additional implicit properties.

  • nUTXOs with certain privileges can spawn new child names. The nUTXOs form a 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 name 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 up to name-genesis UTXO.
  • A nUTXO can create one or more child names (Extensions) 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.
  • A child name can be created by the parent Producer at any future point as long as the child name was never created earlier.
  • The chain of signatures from the genesis TXO to the particular name's UTXO will help validate the name.

Allegory-name-genesis

A nUTXO spending transaction can produce the following derivatives under given conditions:

  • Producer nUTXO, 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.
  • Proxy-Provider UTXO meant to be shared with a 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 user friendly payment addressing.
  • Zero or more child nUTXOs (Extensions). A sparse need-based spawning approach is adopted that helps prevent unnecessary growth of UTXO database.
  • A new Owner nUTXO which now possesses the name, and can be used to subsequently transfer associated name to a new user.

The transaction is expected to contain an accompanying OP_RETURN output (unspendable with 0-value), which has encoded metadata containing the name operation privileges and corresponding references to the transaction's inputs & outputs, along with certain other ancillary information. 

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.

The naming system & the OP_RETURN template specification is as below.

Naming system

A name in a namespace consists of a namespace identifier and a local name.

in augmented Backus–Naur form:

name = <namespace identifier> separator <local name>
separator = "/"

A namespace is a group of related elements that each have a unique name or identifier. A namespace ensures that all the identifiers within it have unique names so that they can be easily identified without name conflicts. A namespace-identifier is used to indicate namespaces to be exclusively used for a given application.

Each element within a namespace has a local name that serves as a unique identifier. The namespace identifier is separated from the local name by a '/' (forward slash) delimiter.

The below namespace-identifiers are reserved as following:
- namespace-identifier for the AllPay application will be 'ap'.
- namespace-identifier for the Global Identity application will be 'id'.

For instance if an user named Alice decides to obtain an unique name 'alice' for AllPay use, her fully qualified AllPay handle will be ap/alice

Allegory Version 1.0, allows names (or namespace) to be extended by one level at a time i.e. in a single transaction. Although, under a single level extension rule, multiple child code-point (character) extensions can be added to a given parent atomically. Multi-level names can be generated trivially by chaining transactions, the rationale behind is to keep the protocol logic simple and robust. While in future protocol spec revisions multilevel support can be added.

The above naming system is merely a convention and not a protocol rule. The protocol itself directly deals with names as arbitrary strings (Unicode code-points) and hence remains oblivious to namespace-ids & separators (in fact these are optional).

Namespaces are created organically with the same fundamental protocol rules, and no special treatment is needed/given for namespaces (as compared to local-names) within the base protocol. So merely generating a namespace identifier (sequence of code-points) followed by the '/' (forward slash) delimiter qualifies as a valid namespace prefix which can now contain unique local names under it. 

Internationalization

Allegory aims to be globally adopted across languages, applications and platforms, it leverages the Unicode Standard to support internationalization. Unicode can be very complex in principle as it attempts to address different notions of a character with constructs such as code-unit, code-point, character-sequence and grapheme clusters. Allegory has a simplified approach to adopting the Unicode standard without delving into the semantics of the different language constructs. Allegory only recognizes code-points, and strictly permits the name extension based on code-point units alone. It does not attempt to discern or validate the grapheme or character sequences which are recognized by other human interface applications.

The name and code-point fields can hold Unicode values. Allegory only recognizes Unicode code-points and no higher constructs, hence the characters/code-points are represented in HTML entities as 'Numeric character references'. 

The Allegory meta-data contained in the OP_RETURN (index-0 output) is YAML encoded, the content can undergo simple ASCII encoding, without affecting the Unicode numeric character references contained within. As a side effect a user could legitimately obtain an Allegory name that is otherwise invalid (syntactically) in the real world. However, this does not affect functionality or security in any way.

The naming protocol is fundamentally case-sensitive. Although the Unicode standard contains explicit labelling of code-points as upper or lower case, no automatic case mapping from lower-> uppercase or vice-versa is allowed in Allegory. The case-folding feature of the Unicode standard is also omitted. Although, the individual namespaces may explicitly choose to follow case-insensitive naming, clients for such applications/namespaces would be expected to limit use of a particular case. e.g. AllPay wallets would disallow names containing upper-case characters (typical in Latin & Cyrillic scripts). This flexible design allows the base protocol to remain agnostic to casing constraints and remains simple and intuitive.

Note: The below template is shown in YAML format for readability purpose, but the actual data encoding will be in CBOR (binary) format. Subsequently an unambiguous schema format will be published in CDDL. Also, Haskell working code example would be provided.

---
version: 1
name:
- 97
- 112
action:
  producer-input:
    index: 1
  producer-output:
    producer:
      index: 2
    endpoint:
      uri: arivi:b74de4211d758560e8ee523396b74de4211d758560e8ee5233963e716a5b99fe8657503a0cb74a13e716a5b99fe8657503a0cb74a1
  owner-output:
    owner:
      index: 3
    endpoint:
      uri: arivi:8560e8503a0e421ee5233a0cb74a13e3963b74de8ee523396b760cb74a14de4211d75e716a5b99fe865750716a5b99fe86571d7585
  extensions:
  - code-point: 96
    producer-output:
      producer:
        index: 2
      endpoint:
        uri: arivi:b74de4211d758560e8ee523396b74de4211d758560e8ee5233963e716a5b99fe8657503a0cb74a13e716a5b99fe8657503a0cb74a1
  - code-point: 102
    owner-output:
      owner:
        index: 3
      endpoint:
        uri: arivi:8560e8503a0e421ee5233a0cb74a13e3963b74de8ee523396b760cb74a14de4211d75e716a5b99fe865750716a5b99fe86571d7585
  • The proxy-providers section allows users to register a service proxy provider explicitly, the service endpoints and access network protocols are included. Additionally such registrations can be time bound, denoted by expiry timestamp, the commitment hash is a privacy & scalability feature which will be covered in subsequent sections.
  • owner section reference a particular output index and declare it as successor nUTXO, which indicates name ownership.

The nUTXOs should hold value above the dust threshold so its accepted by miners. Although nUTXOs serve the naming function and not primarily meant to store 'value' they could still hold arbitrarily large number of Satoshis. Also, nUTXOs can be combined with plain UTXOs to produce one or more nUTXOs, this could be useful if a parent nUTXO does not currently hold enough Satoshis to spawn required children.

Atomic Swaps

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 plain UTXOs (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.

Simplified Name Verification

Allegory allows SPV name resolution wherein 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 nTXO 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 clients/wallets with Allegory protocol functionality will incorporate a marketplace to buy/register names, and to lookup potential recipients based on their user friendly names. 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. To prevent accidental misuse of nUTXOs, it is recommended clients use non-standard key-derivation paths (BIP44, BIP32) for address generation, it could either use a reserved 'account' index like m/44'/0'/509' or they could opt for an exclusive 'coin_type' such as m/44'/509'/1'

AllPay

AllPay allows self-sovereign user friendly payment addressing on Bitcoin. Its fundamental focus is user autonomy and trust-less security, owing to AllPay's unique feature of producing 'provably correct' payment addresses. It eliminates the need for a trusted 3rd party.

Unlike email-id based federated solutions, which offer a user friendly identifier that is permanently locked-in with its service provider (denoted by domain name), the AllPay username is completely user owned and can effortlessly switch service providers, this could be for a variety of reasons - enhanced privacy, flexibility, price, QoS.

Wallets can seamlessly register to proxy services that offer payment address generation service, and these registrations can be short or long-lived and left to user discretion. 

The crux of this protocol involves atomically spending two sets of UTxOs in a single atomic transaction.

- the UTXO set that effectively transfers a certain amount of Bitcoin to the recipient.

- a proxy-provider nUTXO that validates (to the sender) the proxy service provider is currently authorized to generate payment addresses for a given 'name'. The rationale behind being - "The only way to prove an Output is unspent to a SPV client on Bitcoin is by actually spending it on demand."

User's client loans the secondary UTXO to the proxy-provider for the duration of the service, and at termination the user revokes the sames from the 3rd party, who is obliged to provide the same. It can subsequently issue a newly created secondary UTXO (per Allegory protocol) to a different service provider. The sender's SPV wallet can rest assured this Tx (atomically) would only be accepted by miners if its truly an unspent TXO (latest secondary). There is no risk that a SPV wallet might be defrauded by a previous service provider (when name has new owner) as the old service provider does not possess a spendable secondary TXO, as it was revoked by user (primary) before reissuing the next secondary UTXO or selling the name.

Although explained using a linear UTXO chain, the Secondary UTXO logic will actually work as an indirect UTXO set commitment / reference featuring multi level hierarchy & hence reduce SPV validation complexity while drastically improving privacy. This is addressed in the 'Privacy' section below.

Note: The below template is shown in YAML format for readability purpose, but the actual data encoding will be in CBOR (binary) format.

---
version: 1
name:
- 97
- 112
action:
  owner-input:
    index: 1
  owner-output:
    owner:
      index: 2
    endpoint:
      uri: arivi:b74de4211d758560e8ee523396b74de4211d758560e8ee5233963e716a5b99fe8657503a0cb74a13e716a5b99fe8657503a0cb74a1
  proxy-providers:
  - service: AllPay
    mode: standard
    endpoint:
      uri: arivi:90d4fd48e7fb3a4eb150155e2b40e60b6b74de4211d758560e8ee5233963e716a5b99fe8657503a0cb74a120f99e3ee312caeef003972937c77632b27ec4f62d
    registration:
      address-commitment: 2f7ab0c73441456b40779fb028b77829f8ba551fd2f7ab0c73441456b404283e
      provider-utxo-set-commitment: 2640dda58fe6c17f36ac965e89acd278e95e72d5dea1ae0b7cd011421859f8e6
      signature: 779fb028b77829f8ba551fd2f7ab0c73441456b40779fb028b77829f8ba551fd2f7ab0c73441456b40779fb028b77829f8ba551fd2f7ab0c73441456b40
      expiry: 1609459200
  - service: AllPay
    mode: standard
    endpoint:
      uri: https://somedomain.com/allpay-proxy-service
    registration:
      address-commitment: 2f7ab0c73441456b40779fb028b77829f8ba551fd2f7ab0c73441456b404283e
      provider-utxo-set-commitment: 90a603a58fee577f33e7995a393cd6b899523c54d8a5d20373de114245a8f823
      signature: 3441456b40779fb56b40779f29f8ba551fd2f7ab0c734414b073441456b4028028b779fb028b77829f8ba551fd2f7ab0c7778b77829f8ba551fd2f7ab0c
      expiry: 1609459200
Use-Cases / Call flows

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.

Standard mode

As the name implies, this is the standard mode. While the protocol is simple its effective and likely will be the default choice.

  • 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.
  • At proxy registration the wallet includes a Merkle commitment with the pre-compiled list of consecutive HD addresses (address-commitment). 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 deemed safe even for high value transactions.
Authorized Contacts Mode

This involves a slightly more elaborate call flow giving the user greater autonomy and privacy. This should be likely preferred by most individuals & businesses who expect to receive bitcoin transactions from authorized senders.

The basic flow is as follows,

  • 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 destination address under xPub scheme.
  • It allows the global on-chain storage of contact-book along with the registration information, 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 is pre-authorized (by the recipient) so that subsequent transactions can take place directly i.e. by circumventing the AllPay proxy service as seen in 'Standard' 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 Standard mode) i.e. the Tx includes the UTxO that helps sender validate the service provider.
  • The sender issues an "add contact" request - on chain - to the recipient's 'Invite' address. 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), 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 Standard 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

Typically with on-chain model Privacy takes the back-seat, but with Allegory/AllPay special care has been take to preserve it, and in fact it is superior to other federated solutions.

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 proxy-provider 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, where the totally obvious linear chain of proxy-provider UTXOs will need to be obscured so that data analysis yields a negligible success rate if at all.

The proxy service during registration negotiation offers a Merkle commitment of a set of UTXOs (provider-utxo-set-commitment), 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 proxy-provider UTXO is 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 (larger the set higher the privacy). When the contract is being terminated, the proxy service needs to spend all the UTXOs in the contract’s commitment (and/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.