Lambda Creates First Open-Source Proof of Space Time Algorithm Now Available on Github
After a decade, Bitcoin has gradually become one of the world’s largest peer-to-peer network payment systems from the concept of a whitepaper. With the development of Bitcoin, blockchain technology has also received increasing attention.
The blockchain is essentially a distributed application software, and the primary problem of distributed systems is to solve for consistency and reach a consensus. The consensus algorithm is the “soul” of the blockchain. From BFT to PoW to PoS, consensus algorithms have been invented, improved and applied. Today, in the core area of blockchain-distributed storage, the Lambda team has initially implemented the most core algorithm in the field, namely the PoST space-time proof algorithm. The core class library part of the algorithm is open-source on GitHub. The agreement is in compliance with GPL V3.
Data integrity verification mechanism
In recent years, cloud computing has been widely used and applied. Its core concept is resource leasing, application hosting and service outsourcing. It uses virtualization technology to form distributed computing nodes into a shared virtualized pool to provide services for users. However, when users choose to deploy a large number of applications and data to the cloud computing platform, the cloud computing system becomes a cloud storage system accordingly, but the highly centralized computing resources present serious security challenges for the cloud storage.
For example, the Tencent cloud data loss issue prompted us to question the future of storage service as there are still many problems in the security, reliability and service level of centralized cloud storage. While most enterprise data resides in the cloud, there are still many gaps in security, being able to recover data in its exact original form is imperative. This is called the “data integrity verification mechanism” often mentioned in decentralized storage.
The data integrity verification mechanism is divided into a data possession proof PDP mechanism (PDP, Provable Data Possession) and a data recoverable proof POR mechanism (POR, Proofs of Retrievability) according to whether or not the data file is subjected to fault-tolerant preprocessing. The PDP mechanism can quickly determine whether the data on the remote node is damaged with more efficiency. The POR mechanism not only identifies whether the data is corrupted, but also recovers the corrupted data. These two mechanisms have different application requirements. The PDP mechanism is mainly used to detect the integrity of big data files, while the POR mechanism is used to ensure the integrity of important data and the recoverability after data loss.
Data possession proof PDP mechanism
First let’s look at an application scenario of the PDP solution:
(1) Alice asks Bob to remember a set of information;
(2) Alice does not record this set of information;
(3) Alice asks Chris to confirm if Bob still remembers this group of information;
(4) Chris does not understand the content of this group of information.
We replace these roles: Alice is the user, Bob is the storage completion, and Chris is the third-party auditor (hereinafter referred to as TPA).
The verification process is as follows:
(1) The user generates a tag for each piece of data to be outsourced, and the tag is signed by the user;
(2) The TPA randomly initiates a Challenge to the user outsourcing data, and the Challenge contains a random number generated by the TPA;
(3) The storage completion is based on the challenged data block content, the Tag information, the Challenge information, and a random calculation generated by itself to obtain a Proof;
(4) The TPA uses the challenge function e(u, v) bilinear property to check whether
the storage completion holds data by using the challenge, proof, and user public key as parameters.
Among them:
Time and Space Proof: Proof of Space Time
Proof of Space Time (PoST) is a concept introduced by FileCoin for the blockchain field. The definition of “time and space” is to measure and calculate the data storage time and space stored in the network. Both FileCoin and Lambda are designed to provide decentralized distributed storage. Miners receive customer fees through storage and retrieval processes, and receive block rewards through space-time proof algorithms. Since the entire network is a P2P network without a centralized node, some mechanism are needed to ensure the integrity and recoverability of the data stored by the user, and thus some related algorithms in this field are born.
Time and space proof PoST, which allows the verifier to check if the storage provider has stored his/her outsourced data for a period of time. The requirements for this provider are:
(1) Generate a stored proof of the order as a method of determining the time.
(2) Composing recursive execution to generate a simple proof.
In fact, the PoST algorithm is an improvement on POR. The POR algorithm was first elaborated by Juels et al. in a paper called Proofs of Retrievability For Large Files. The core of the file is to store the files in pieces. The label information of the fragments are periodically challenged and proven. But usually the operation of the POR defined by the academic world depends on the centralization of the third-party nodes, and each time the operation is pre-processed, the relative Space Time (PoST) is a POR sequence generated in a certain period of time to prove the retention time of useful storage.
As shown in the following figure, the main difference between PoST and POR is the repetition of the execution of the challenge without re-running the initialization phase, which greatly improves the execution efficiency.
About IPFS and FileCoin
Many people in the blockchain field confuse the IPFS and FileCoin projects, believing that the IPFS project has solved the problem of the integrity of stored data, which is a misunderstanding. People mistakenly believe that IPFS can guarantee that the data cannot be tampered with after hashing the data. However, this is a misconception of any IPFS network node as they only store data of interest to them and not user specified data. Therefore, an incentive and inspection layer is required to ensure that the user-specified data is stored and not tampered with. To make a simple comparison, IPFS is similar to open-source Ceph software, and FileCoin and Lambda are more similar to AWS’s S3. A pure storage system without digital currency incentives are impossible to solve for the data holding problem.
FileCoin’s definition of space-time proof PoST is:
- The space-time proof PoST scheme enables a valid prover P to persuade a verifier V to believe that P has stored some data D for a period of time. PoSt is characterized by a tuple of polynomial time algorithms: (Setup, Prove, Verify).
- PoSt.Setup(1λ,D)->Sp,Sv, where SP and SV are setting variables for the characteristic schemes of P and V, and λ is a safety parameter. PoSt.Setup is used to give P and V the necessary information to run PoSt.Prove and PoSt.Prove. Some programs may require a prover or an interactive third party to operate PoSt.Setup.
- PoSt.Prove(Sp , D, c, t) → πc, where c is the random verification issued by the verifier V, and πc is the proof that the person can access the data D for a period of time. PoSt.Prove generates πc from P (certifier) running for V (verifier).
- PoSt.Verify(Sv, c, t, πc)→ {0,1} is used to check if the proof is correct. PoSt.Verify is run by V and persuaded V believes that P has stored R for a while.
Logically speaking, the proof of data holding is a game that is completed by two characters and four steps. The first character is Challenger, the second character is the person who completes Proof, the first step of Challenger is to generate the file and some puzzles, and then put it on the server; the second step is to generate a certain information of Challenger, some of the required Data; the third step storage node completes a Proof and sends it back to Challenger; the fourth step is that Challenger uses some of the information left by itself to generate a Verify. Use Verify and Proof to verify that this is correct; this is Verify with two roles and four steps.
Decentralized storage projects need to solve a lot of problems, but we need to avoid long project cycles and too large a goal. In the field of software, there is a famous book called “The Moon and the Moon Myth,” which describes a famous software project failure process. In fact, any software that is too ambitious in design goals can’t escape the fate of failure, and the right way to develop should be done through agile and iterative.
FileCoin is a long-established project. The technical solutions adopted in its whitepaper have been changed many times. The core consensus algorithm PoST v1 has completely overthrown the V1 design from the earliest PoW-like consensus to 2017, and switched to the VRF algorithm similar to Algorand. Poreps’s VDE implementation, the introduction of new VDF algorithms, and the retrieval of the market, micropayments and other issues have not yet been well-designed. FileCoin has been involved in too many technical and academic problems making the development cycle very uncontrollable.
Lambda’s solution
Lambda’s idea is to iteratively implement a blockchain-based PDP and POR system through the prototype system and realize all the advantages of PoST, such as continuous challenges and random challenges on the chain. Lambda believes that in the case of non-Blockchain, in another verification algorithm different from POR, a PDP algorithm can be constructed; assuming a trusted third party, through a certain probability, to verify the data holding, and The verification results are stored in an explicit and non-tamperable manner. Then this credible third-party audit, also known as TPA, must be able to pass the verification results through the chain to achieve non-tamperable results and a single-point trusted verification process must also pass a set of semi-trusted Validator nodes. Wherein consensus is completed.
The main differentiator from FileCoin is Lambda’s use of Validator nodes and roles, which streamlines the project development. Today, Lambda’s open PoST implementation using the Validator node provides new ideas and research directions for distributed storage and blockchain storage.
GitHub open-source address: https://github.com/LambdaIM/
He Xiaoyang, founder of Lambda
A well-known Chinese technology expert, a member of the JVM community, worked as a research and development engineer at BEA Systems and Oracle. He Xiaoyang himself was also known as “the first person in China’s APM industry.”
Li Munan, co-founder of Lambda
One of China’s top programmers — one of the founders of Coreseek and Log Insight.
As a search engine and file system, storage system, and journaling system expert, Li Monan’s CoreSeek Chinese word segmentation system has been widely used in the Chinese Internet BBS community.
Lambda’s core team and partners originate from technical backgrounds and have many years of experience in basic software development and participation in open-source projects. Additionally they have contributed code to various projects of the Apache Foundation, such as Camel, Akka, Druid, etc. Lambda’s open-source is very strong and it’s the team’s first time contributing their own open-source code in the blockchain field.
Chinese version:
Official links
🔹 Official website: http://www.lambda.im
🔹Facebook: https://www.facebook.com/Lambdaim
🔹LinkedIn: https://www.linkedin.com/company/lambdaim/
🔹Twitter: https://twitter.com/Lambdaim
🔹White Paper : http://www.lambda.im/doc/Lambda-WhitePaper-en.pdf
Join us on
🇬🇧 English: @hellolambda
🇨🇳 Chinese: @lambdachina
🇵🇹🇧🇷 Portuguese: @LambdaPortugueseOfficial
🇰🇷 Korean: @LambdaKoreanOfficial
🇮🇳 India: @LambdaIndianOfficial
🇻🇳 Vietnamese: @LambdaVietnamOfficial
🇷🇺 Russian : @LambdaRussianOfficial
