Recently, DAS founder TimYang (Yang Min) developed DAS decentralized account service on Nervos CKB. With this product development, TimYang will explain his design ideas and development process through the series of articles titled “From DAS to CKB Application Development”, so that you can learn how to build product-level applications on the world’s first UTXO-BASED public chain CKB.
In the first article, Tim will introduce you to the first big problem they faced when designing a DAS — how to ensure that DAS accounts are unique. Welcome to read and experience.
The opening
DAS is not a conceptual product. It is currently running on the CKB test network and is expected to be launched on the main network in the near future. You can test the version with da.services.
DAS is a blockchain application based on CKB. Of all the public chains, why do we choose to develop based on CKB? There are two reasons:
- PoW consensus + Cell (UTXO) model
- Custom cryptography primitives (highly open architectures), based on which we can implement DAS accounts that can be held by any public chain address.
CKB is the rare public chain platform that builds smart contract environment on UTXO model and advocates “off-chain calculation, on-chain verification”. These propositions and designs are well thought out and forward-looking, but they also bring a new paradigm of decentralized application development. Developers who are used to centralized application development and ethereum smart contract development will feel uncomfortable when they first start CKB development. This, combined with the fact that there are no benchmarking apps yet, leaves developers wondering what CKB can do and whether learning CKB is really worth the effort.
This is the purpose of the CKB Application Development from DAS series. We put together a series of articles about our problems, thoughts, and solutions in DAS practice to give you an idea of how we built production-level applications based on CKB. Hopefully this will inspire more developers to understand what CKB can do and how it should be done.
To be clear:
In the face of a problem, the idea and solution we adopt may not be the optimal solution, or even most likely not. But if the ideas and solutions that fit our scenario can inspire you, then the goal will have been achieved. This series of articles assumes that the reader has a good understanding of the Cell model and the “off-chain calculation, on-chain validation” model.
How to ensure the uniqueness of DAS accounts
In this first article, we will explore the first thorny problem facing DAS:
Each DAS account needs a Cell to store its data. The Cell is created through different transactions, which means that the global state data of the DAS system is stored in various corners. At the same time, each DAS account must be unique. So, when a DAS account registration occurs, how do we determine whether the account already exists?
Let’s generalize this question: for distributed data sets, how can we ensure that each piece of data is unique when inserting data?
Are accustomed to the centralized application development contracts and etheric fang intelligence development of developers, not to repeat, to ensure the account registered this thing almost without thinking, you can put all the data in the storage space of the contract, because these data are stored in concentrated, so before inserting data, you only need to retrieve the data exists.
However, due to CKB’s Cell model, the data is distributed in the user’s own space, so we cannot retrieve all the data on the chain. After all, it is impossible to drop all existing cells in the input of a transaction. Even if it does, the on-chain script has no way of knowing whether the transaction originator actually put all the required cells into the input when the transaction was constructed.
We’ll list all the options we’ve considered to ensure uniqueness. The reason why we analyzed all the solutions that were not adopted in the end is that we hope that by observing the “detours” we have taken, we can begin to adapt to the DEVELOPMENT paradigm of CKB and avoid the “detours” in the future.
Before we discuss the scheme, we should define our design principles. It is these principles that ultimately determine what kind of solution we adopt. These principles, in descending order of priority, are:
- Degree of decentralization: Decentralization is the most fundamental principle for the goal DAS wants to achieve
- User experience, technical solutions are not allowed to bring bad user experience
- In engineering complexity, simpler architectures tend to be more effective
- Low cost, can save as much as possible
If you only care about the final plan, you can jump straight to plan 6 and start reading.
Plan 1: Store all accounts in one Cell
This is the most intuitive solution, since ethereum’s smart contracts can do just that. Create a GlobalStatusCell to store all registered accounts in the GlobalStatusCell’s data. When a new registration occurs, this GlobalStatusCell is used as the input and the modified GlobalStatusCell as the output in the transaction. The type script checks whether the newly registered account already exists. If it does, it returns a non-zero value and the transaction fails. If not, check if the output GlobalStatusCell contains the new account, and return 0, the transaction is successful and the registration is complete.
Here’s why this doesn’t work:
- Cell race issues. Each new account registration requires the GlobalStatusCell to be spent as input, whereas a Live Cell can only be spent once, meaning that only one registration request can ever be processed at a time. Users who failed to compete for the Cell had to sign up for the transaction over and over again until they successfully competed for the Cell.
- In terms of space cost, CKB is a layered architecture, and the final state space on Layer 1 is limited to about 80 GB. Storage space on Layer 1 needs to be purchased by CKB. Assuming that 100W DAS accounts are eventually registered, the capacity required by this GlobalStatusCell will be enormous. Of course, since this storage space is gradually increased with the number of registrations, for a single user, the cost of a single user is acceptable by paying CKB for the incremental space corresponding to this registration.
In fact, the “Cell race problem” is something to be aware of when developing applications on CKB. Its impact on the user experience can be fatal.
Plan 2: Then spread all accounts into multiple cells
Since one GlobalStatusCell would lead to competition for all accounts, what if we split accounts across multiple accounts? For example, to hash account names, add all registered accounts with the same first three hash values to the same SubStatusCell. When a new registration is created, the corresponding SubStatusCell must be consumed to modify its internal data.
There are still some problems with this plan:
-
If the first three bits of the hash are used to create substatuscells, 4096 substatuscells need to be created in advance. Assume that there are 50 concurrent registration requests in a period. According to “drawer principle”, There is still a 26% chance of a Cell race. Although concurrent requests of 50 are a little more demanding and may not be achieved at all early on, it should be recognized that:
- Since the number of substatuscells is fixed, the probability of this competition is the same at any stage. The “probability” itself implies uncertainty, and its impact on the user experience may not be, or may be very large.
-
There are costs associated with initialization. Assuming that a SubStatusCell needs only 100 CKBS for its capacity at initialization, 409,600 CKBS are required to initialize all subStatuscells.
Again: When developing on CKB, always be aware of how much CKB storage your application is taking up, because the total state space is extremely limited.
Plan 3: DAS officials will judge whether an account has been registered
All registration should be carried out through the official DAS service. After the OFFICIAL DAS determines that it can be registered, it will sign a transaction with the official private key and issue the DAS account Cell to the user. This scheme is very simple to implement, but the problem is obvious:
- Without decentralization, how to ensure the correct judgment of the uniqueness of DAS official services? What if the authorities take the initiative? What if the authorities, because of a glitch in the program or the poor safekeeping of the private key, are passive villains?
- Dirty data problem, no matter what form of evil, centralized judgment is a kind of off-chain judgment, cannot guarantee the uniqueness absolutely effectively, therefore, may produce dirty data on the chain at any time. How do you clean up the dirty data? A mechanism for cleaning up dirty data must be introduced.
- Derived from availability issues, if the official service goes down, the entire registration service becomes unavailable.
Plan 4: Then multi-centralize, use multiple sub-chain nodes together to determine whether an account has been registered
For example, find seven “trusted” organizations to act as supernodes and manage their private keys. The supernodes run the supernode service, which stores all registered accounts in their own centralized database. When a registration request is made, each supernode determines whether it has been registered. If not, sign a transaction with the private key and release a Cell indicating that “this super node considers this account can be registered”. When more than 4 super nodes release such cells, one of the nodes will gather all these cells and use them as a basis to create a DAS account.
This idea seems to be a good solution to some of the problems in solution 3, but it introduces more problems:
- Trust issues, “trustworthy” organizations, how to count as trustworthy organizations, how we should select these seven nodes. Just because an organization’s ethics may be trustworthy does not mean its behavior can be. We can find the most credible organization to do the nodes, but in the early stages of a project, the most credible organization is hardly motivated to maintain the nodes.
- With dirty data, it is entirely possible for these supernodes to make consistent misjudgments due to “inevitable” bugs. There is also a dirty data cleanup logic when consistency errors occur
- Node rotation problem. Due to the loss of the private key or other reasons, nodes inevitably need to be rotated. How does the rotation work? Through off-chain consultation or on-chain consensus? Off-chain consultation means an open and transparent governance process; On-chain consensus means complex engineering to implement.
- Complexity, which includes both engineering and governance complexity. A lot of this work has gone beyond the business logic of a dApp itself. Imagine if every application developer had to think about so many problems that are not related to business logic, then the application could not be created efficiently. This also means that a multicentric approach must not be a best practice.
Scheme 5: Registration is not heavy, resolve heavy
Since it is so complicated to implement de-duplication at registration, it is not necessary to de-duplication at registration. Anyone can “register” any account at any time, and when the user wants to query the resolution record of an account, the resolver will find the earliest “registered” account and return it to the user as a legitimate account.
The problem with this unique approach is how to ensure that the client runs a “reasonable” parser:
- Will developers all run the same parser?
- For those developers who choose to run official parsers when they are updated, will they, and can they, do so in a timely manner?
If you can’t ensure that everyone is always running the same up-to-date parser, the entire system is bound to be inconsistent at the application level. It leads to all kinds of fraud and eventually people lose confidence in the system.
Scheme 6: ordered linked list
Finally, we introduce the final solution adopted by DAS – ordered linked lists.
Let’s make a more general statement about the problem we’re trying to solve:
For distributed data sets, how to ensure the uniqueness of each piece of data when inserting data?
The answer is to use logically ordered linked lists. Thanks @Guiqing for the inspiration.
Each registered DAS account has a Cell to store its related information, called an AccountCell. We require all accountCells to be sorted in some order, such as lexicographical ascending by account name. When registering a new DAS account, its AccountCell must be inserted in place to ensure that this order is not broken.
The simplified structure of AccountCell is as follows:
Note: The account_id value is the account name, just for convenience, but the DAS actually uses the first 10 digits of the hash of its account name.
Let’s assume that there are already a. bitt,b. bitt in the chain, and now a user wants to register d.bitt.
What happens if the registration program accidentally (or the user maliciously) constructs a transaction, tries to create duplicate accounts, or inserts accounts in the wrong location. This is where our Type script comes into play, causing such transactions to fail without being packaged into the block (see, on-chain validation).
The type script for the Cell runs when the Cell is both input and output. Our type script can make some judgments, such as:
- Check whether the account_id of the imported parent AccountCell is smaller than the account_id of the newly registered account in inputs
- Check whether the next_account_id of the imported parent AccountCell is greater than the account_id of the newly registered account in inputs
- Outputs whether the next_account_id of the new parent AccountCell is equal to the account_ID of the newly registered account
- Outputs whether the next_account_id of the newly registered account is equal to the next_account_id of the parent AccountCell imported in inputs
Therefore, if all of the above judgments are true and the entire transaction structure meets other necessary conditions, the Type script will return 0, indicating that it is a legitimate transaction. When the transaction is included in the block, the account is registered and the status of the DAS system is updated. And for the transaction that does not meet these conditions, it is not legal transaction at all, and will not register successfully.
As you can see, this solution meets the four design principles we set out earlier.
Further derivation
Judging repeatability of data is so complicated in CKB?
We need to understand that the essential reason behind the “complexity” is the UTXO model, which leads to the decentralized storage of data.
Then why does CKB adopt UTXO model? Isn’t the account model of ETH very good?
Both UTXO model and account model have their advantages and disadvantages. Some advantages of UTXO model are as follows:
- Parallel computing. All transactions under a single account of ETH must be serial, one transaction is stuck and all subsequent transactions cannot be carried out.
- Isn’t it more in the spirit of decentralization that user data is stored in users’ own UTXO (cells) rather than centrally stored in contracts?
We should understand that the “complexity” of our feelings comes more from our maladjustment to the new paradigm.
Think of on-chain validation as a protocol
As you can see, the type script constraint is more like a protocol. He prescribes what inputs and outputs a transaction should have, but who creates the transaction, and how, is not the concern of the agreement.
Option 6 also has Cell competition problem?
Yes, if multiple newly registered accounts are supposed to be plugged directly after an AccountCell, you have Cell contention issues. So, in the next article, we will show you how to completely solve the problem of Cell contention based on Scenario 6 through a mechanism we call “Keeper.” Finally, as we mentioned at the beginning:
In the face of a problem, the idea and solution we adopt may not be the optimal solution, or even most likely not. But if the ideas and solutions that fit our scenario can inspire you, then the goal will have been achieved.
To be continued…
In the next article, Tim will introduce a mechanism called “Keeper” to deal with Cell contention. Welcome to talk.nervos.org/t/das-ckb-d… Push more.
If you have more information about using DAS products and developing ideas on CKB, please visit the Nervos Talk forum: talk.nervos.org/
