New Proof of Space directions (backup page. Outdated)

Creator

Matteo Campanelli

Created

May 23, 2023 2:32 PM

What is Proof of Space?

A Proof of Space (PoS, see for example: eprint 2013/796) is a protocol that allows a prover  to convince a verifier that he has a minimum specified amount of space (ie, used storage). More precisely in a PoS protocol we have two main sub-protocols:

🎯 Goals

1. New PoS Research
1. “more” tunable security
2. better retrievaility
1. faster retrievability
2. local retrievability (to retrieve D[j] at position j one should not necessarily look at the whole file D)
3. at least as much efficiency or better efficiency (or substantial tradeoffs) than current constructions in terms of, among others
1. sealing time
2. chain footprint
3. auditing time
4. verification time

If the above fails, build a strong understanding of what the challenges are and effectively communicate them to stakeholders.

2. Educational
1. Formalising PoS
2. Knowledge sharing
3. Outreach to community
4. State Open Problems

👥 Team

Team: Matteo&Anca (main effort)

Advisors (external): Leo Reyzin (Q2), Carla Rafols

Advisors (internal): Luca & Irene

🚩 Milestones and roadmap

‣

📖 Research Enablers

Name	Status	Quarter	DRI	Date	🎒 Team backlog ㊙️
Implement it (MVP)	✅	2023Q1	Kubuxu	February 20, 2023 → February 24, 2023
Integration with existing libraries	✅	2023Q2	Kubuxu
User Friendly API	✅	2023Q1	Kubuxu	February 27, 2023 → March 10, 2023
First prototype for inclusion proofs during computation of CommP	✅	2023Q1	Kubuxu	February 20, 2023 → February 24, 2023
Kuba will complete the two sections (security and design reasoning)	✅		Kubuxu
‣ Commitment Scheme format agreement	✅	2022Q4	Kubuxu	March 19, 2023 → March 19, 2023
‣ Software for generation of data segments inclusion proof	✅	2023Q2	Kubuxu	February 12, 2023 → March 24, 2023
‣ Support for verifying data segment inclusion proofs on-chain	✅	2023Q1	Kubuxu	February 12, 2023 → March 17, 2023
Data Prepapers API Standard	🔴	2023Q1	Kubuxu
SubPieceCID Registry smart contract with Merkle trees verification	🔴	2023Q2	Kubuxu
Built-in actors API for user-programmed actors	✅	2022Q4	Kubuxu
‣ (security) Short term fix for Cron	✅	2023Q1	Alex North
‣ Verifiable Off-chain Data Aggregation	✅	2023Q2	Kubuxu
‣ Replacement Sealing Forcing Function & PoRep Security Policy (FIP-47prime)	🔵	2023Q3	Kubuxu	October 1, 2022 → June 19, 2023
FIP for Synthetic PoRep	✅	2023Q1	Irene	March 31, 2023 → April 7, 2023
Draft ideas to make SnapDeal cheaper	✅	2023Q1	Luca	February 10, 2023
‣ 🦿Synthetic PoRep	✅	2023Q2	Irene	March 24, 2023 → June 30, 2023
‣ 🥁SnapDeal v2	🔴	2023Q2	Luca	March 31, 2023
FIP-0047 and code are ready	✅	2022Q4	Kubuxu	October 1, 2022 → December 22, 2022
Planning session to understand timeline	🔴	2023Q1	Kubuxu
‣ 🏦 Pledge Collateral Shortfall	🔴	2023Q2	Alex North	March 17, 2023 → June 30, 2023
Create the model for cost/profit to compare CC sector upgrade with deal sector strategy	✅	2023Q1	Luca	March 20, 2023 → April 1, 2023
Report about model and findings	✅	2023Q2	Luca	May 1, 2023 → June 12, 2023
‣ Data Onboarding Pipeline	🔴	2023Q2	Irene
FIP for Deal Pre-activation (based on ad-hoc collateral)	🔴	2023Q2	Irene
Gather initial feedback about the design for deals larger than sectors	✅	2023Q2	Irene	April 3, 2023 → May 1, 2023
Identify opportunities	✅	2023Q2	Irene	February 1, 2023 → May 22, 2023
‣ 🤝Filecoin cross-chain interoperability	🟡	2023Q4	Alex North
Background research on consensus/snapshot/finality options	🟡	2023Q2	Alex North
Design & analysis for consensus changes for interop	Not started	2023Q3	Alex North
‣ 🎯Direct data onboarding & FIL+ technical design	🔵	2023Q3	Alex North
‣ Repeatedly updatable storage ("Re-snap")	🔴	2023Q2	Kubuxu
(advising) 🍝 FilFil: PeSto and Filecoin Archive	🔴	2023Q2	Irene	March 31, 2023
Fil-PoA FIP out	Not started
Fil-PoA FIP discussion out	Not started
‣ Understand if Fil-PoA is worth Pursuing	Not started
Analyze of SaaS benefits	Not started
Estimate gas costs compared with today	Not started
Estimate proving costs wrt today considering SN improvements and NI Proving overhead	Not started
Estimate input blowup	🔵
Deploy NI-PoRep	Not started
Doc clarifying PoA and FIL+ interaction	Not started
CryptoEcon Feedback	🔵
Determine a killer application for PoA	Not started
NI-PoRep FIP	Not started
NI-PoRep FIP discussion	Not started
‣ Analyze NI-PoRep risks	🔵
‣ NI-PoRep technical analysis	Not started
Doc on NI-PoRep with Nova (by FilCrypto)	🔵
‣ Explore NI-PoRep w/ ad hoc circuits	🔵
Align with Fil-Crypto on circuit compatibility	🔵
Estimating Proving costs overhead	Not started
‣ Fil-PoA: Filecoin Proof of Access	🔵	2023Q4	Luca
‣ ⭕Non Interactive PoRep	🔵	2023Q4	Luca
Define the mechanism for charging fees	🔵	2023Q3	Kubuxu
Align on the purpose of batch balancer and onboarding fees	🔵	2023Q3	Kubuxu
Optimistic Commitment Translation	Not started	2023Q4	Kubuxu	August 1, 2023 → December 29, 2023
Strategy and roadmap update with Andrew and David	🔴	2023Q3	D Deleted User	July 25, 2023 → August 4, 2023
New dashboards and queries	🔴	2023Q3	D Deleted User	June 1, 2023 → July 31, 2023
Implement a first version for concrete benchmarks	🟣	2022Q3
Technical design for deal collateral / data termination	✅	2023Q2	Alex North
Technical design for direct FIL+	✅	2023Q2	Alex North
Proposal/FIP for direct FIL+	🔵	2023Q3	Alex North
‣ Removal of Batch Balancer through Onboarding Fees	🔵	2023Q3	Kubuxu	June 12, 2023 → July 25, 2023
Protocol Design and implementation	🔴
SP ROI calculator connected to data sources	✅	2023Q3	Nicola	March 20, 2023 → June 30, 2023
alignment on Broker ↔ SP side of the market	Not started	2023Q2	Kubuxu	June 5, 2023 → June 16, 2023
Document for L2 Deal Market	🔵	2023Q2	Kubuxu	May 15, 2023 → June 6, 2023
Publish blog post	✅	2023Q2	D Deleted User	May 8, 2023 → June 9, 2023
proposal	✅	2023Q2	D Deleted User	May 2, 2023 → June 2, 2023
Working group kickoff	✅	2023Q2	D Deleted User	May 29, 2023 → June 5, 2023
‣ 📡 Cryptonet intelligence - Observability	🔴	2023Q2	D Deleted User	May 2, 2023
Support Lighthouse integration	🔵	2023Q2	Kubuxu	May 29, 2023 → June 17, 2023
‣ Support integration of PoDSI	🔵	2023Q3	Kubuxu	May 15, 2023 → June 29, 2023
Support FVM via On-chain Aggregator	🔵	2023Q3	Kubuxu	May 15, 2023 → June 29, 2023
Support DagHouse integration	🔵	2023Q2	Kubuxu	March 15, 2023 → June 15, 2023
Support Delta (ex-Estuary) integration	✅	2023Q2	Kubuxu	May 29, 2023 → June 2, 2023
Implementation of direct FIL+	🔵	2023Q3	Alex North
Proposal/FIP for deal collateral (discuss #719)	✅	2023Q2	Alex North
‣ Scaling FIL+ VC Allocation	🟣	2023Q3		May 1, 2023 → June 30, 2023
Publish specs for public discussion	✅	2023Q2	Alex North	April 12, 2023 → May 20, 2023
‣ L2 Deal Market	🟡	2023Q4	Kubuxu	May 8, 2023 → October 31, 2023
Implement the model	✅	2023Q2	Luca	April 10, 2023 → May 1, 2023
Synthetic PoRep is ready to be deployed	✅	2023Q2	Irene	May 8, 2023 → June 30, 2023
Obtain cost estimation for the different solutions	✅	2023Q2	Luca	April 3, 2023
Documentation	✅	2023Q2	Kubuxu
Publish FIP-0047 replacement (FIP-47’)	✅	2023Q2	Kubuxu	April 10, 2023 → June 19, 2023
Figure out design to avoid FIP-0047 after all	✅	2023Q1	Kubuxu	January 10, 2023 → March 15, 2023
Code	✅	2023Q1	Alex North
Create the FIP for SnapDeal v2	🔴	2023Q2	Luca	April 2, 2023
Gather initial feedback from SPs	✅	2023Q2	Luca	March 31, 2023
Short-term FIP is shipped	✅	2023Q1	Alex North
Short-term FIP is in the public	✅	2023Q1	Alex North
Gather initial feedback from SP	✅	2023Q1	Alex North	May 17, 2023 → May 24, 2023
Resolve int overflow TODOs	✅	2023Q2	Kubuxu
Export Format	✅	2023Q2	Kubuxu
Storage Format	✅	2023Q2	Kubuxu	February 27, 2023 → March 10, 2023
Testing	✅	2023Q2	Kubuxu	February 27, 2023 → March 10, 2023
FRC merged (waiting on Kaitlyn to assign number and merge)	✅		Kubuxu	February 27, 2023 → March 3, 2023
Find parameters and alternative proposals and sync with CEL	✅	2023Q2	Alex North	March 19, 2023 → May 31, 2023

‣

🔮 Protocol Opportunities

Name	Status	Quarter	DRI	Date	🎒 Team backlog ㊙️
Have 5 Network Grants	✅	2022Q4	D Deleted User
Have 5 more Network Grants and 1 External Event	🔴	2023Q1	D Deleted User
Have 5 more Network Grants and 1 more External Event	🔴	2023Q2	D Deleted User
Have 5 more Network Grants	🔴	2023Q3	D Deleted User
‣ Testudo77 v0.1: Initial performance prediction	✅	2022Q4	D Deleted User
‣ Testudo77 v0.2: Basic research done	✅	2022Q4	D Deleted User
‣ Testudo81 v0.3: De-risking Filecoin deployment	✅	2023Q1	D Deleted User
‣ Testudo81 v1: Ready for writing proofs	🔴	2023Q2	D Deleted User
‣ Testudo81 Filecoin Proofs live on testnet	🔴	2023Q2	D Deleted User
‣ Testudo81 Filecoin Proofs live on mainnet	🔴	2023Q3	D Deleted User
Testudo is audited	🔴	2023Q4		August 31, 2023
Testudo is launched into Filecoin	🔴	2023Q4		September 30, 2023
Filecoin Proofs are written for Testudo	🔴			May 31, 2023
FIP for adding support to Testudo Proofs	🔴			May 31, 2023
Paper is public	✅	2023Q2	D Deleted User	March 1, 2023 → June 19, 2023
New proofs are live in Filecoin Testnet	🔴			June 30, 2023
Add Ability to support circuits	🔴	2023Q1		March 31, 2023
Verification circuit for Testudo	🔴	2023Q1		March 31, 2023
More optimizations if needed	🔴	2023Q2		April 30, 2023
Aggregation feature implemented	🔴	2023Q2		June 30, 2023
Trusted setup is finalized	🔴	2023Q2		May 31, 2023
Can we design a Trusted Setup for Testudo?	✅	2023Q1		February 28, 2023
Backward compatible solution BLS12-381 designed	✅	2023Q1		February 28, 2023
Can Bellperson speed ups make Testudo 4x faster than Groth16? (blst+GPU) (low risk)	✅	2023Q2	D Deleted User	February 28, 2023
Will the final proof size and verification time be acceptable for Filecoin?	🔴	2023Q2	D Deleted User	March 31, 2023
Small universal trusted setup	🔴	2023Q1		January 31, 2023
Establish if the protocol can be used to replace current FIL proofs	✅	2022Q4
Compare protocol to other SNARKS with universal trusted setup	✅	2022Q4
‣ Efficient SNARKs over Vector Committed data	🔴	2023Q2
Make portions of the Filecoin state proof friendly ❓	🔴	2023Q4
Efficient data updatability inside sectors ❓	🔴	2023Q4
Replace Merkle trees with VC in Filecoin PoRep ❓	🔴	2023Q4
Solve BDSC for Plonk with Caulk/Muppets/Baloo	🔴	2022Q4	Anca Nitulescu
Solve BDSC for Groth16(+Testudo) with Caulk	🔴	2022Q4
‣ Design of foundational Vector Commitment schemes	✅	2022Q3	Anca Nitulescu
	🔴	2023Q1	Anca Nitulescu
Implementation of the Lookup Table	🔴	2023Q2	Anca Nitulescu
Pebbling PoS: SDR and NSE improvements and tighter analysis	🔵	2023Q3	Matteo Campanelli	April 1, 2023 → June 30, 2023
PoS: new page for educational material	✅	2023Q2	Anca Nitulescu	May 8, 2023 → May 26, 2023
‣ 🛡️Testudo	✅	2023Q2	D Deleted User
‣ Vector Commitments for Proof of Space and Merkle Trees	🔴	2023Q4	Anca Nitulescu
‣ Network Grants Program paused	✅	2023Q1	D Deleted User
Linear-map VC: unify all the great properties of different VC	✅	2022Q2	Anca Nitulescu
Caulk: Vector commitments that can have linkability property	✅	2022Q2	Anca Nitulescu
Muppets: Vector commitment that has trade-offs between computation and space	✅	2022Q3	Anca Nitulescu
Blog post on Testudo	✅	2023Q1	D Deleted User	February 27, 2023 → March 27, 2023
‣ 🔍Lookup SNARK (for SHA)	🔴	2023Q4	Anca Nitulescu
‣ Privacy-Preserving Content Routing	🔴	2022Q4	Anca Nitulescu
Check future directions for how to apply VDF with Nicola	🟡			September 25, 2023 → October 5, 2023
Outreach: talk on Proofs of Space @ Latincrypt affiliated event	🔵	2023Q3	Matteo Campanelli	September 4, 2023 → October 3, 2023
Paper: more efficient rational proofs (grant)	🔵	2023Q3	Matteo Campanelli	June 1, 2023 → October 31, 2023
Minimal changes to Groth16 to make Signature of knowledge	Not started		Anca Nitulescu
Bring content from Proof of Space days online	Not started
Paper: Polynomial Evaluation for PoUS Execution Stage (grant)	🔵	2023Q3	Matteo Campanelli	April 1, 2023 → October 31, 2023
‣ Research explorations	🔵
Complete Background and Generic Proof of Space	🔵	2023Q3	Anca Nitulescu
	✅	2023Q3	D Deleted User	June 5, 2023 → July 21, 2023
	✅	2023Q2	D Deleted User	June 5, 2023 → July 6, 2023
Updated home page	✅	2023Q2	Anca Nitulescu	June 14, 2023 → July 6, 2023
Interviews planning and video production setup	🔵	2023Q2	D Deleted User	May 30, 2023 → July 31, 2023
Outreach	✅	2023Q2	Anca Nitulescu	May 22, 2023 → August 4, 2023
‣ 🛠️Enabling Filecoin Client Data Usage	🔴	2023Q3		May 20, 2023 → June 30, 2023
‣ Possible avenues to radical New PoS (and new space-hardness assumptions)	🔵	2023Q3	Matteo Campanelli	May 15, 2023 → July 31, 2023
2nd iteration of the PoS website	✅	2023Q2	Anca Nitulescu	May 29, 2023 → June 7, 2023
New paper with new results (includes Proof of Space Model and Technical Primer)	🔵	2023Q3	Matteo Campanelli	July 23, 2023 → October 15, 2023
🖇️ New Vector Commitment	🔴		D Deleted User
‣ 🔭 🛠️New Proof of Space Constructions	🔵	2023Q3	Matteo Campanelli	March 1, 2023 → September 30, 2023
‣ 🔭 Proof of Space: educational material	🔵	2023Q3	Anca Nitulescu	April 17, 2023 → May 26, 2023
Onboarding devs on Testudo	🔴	2023Q2	D Deleted User
➿ Curve Agnostic Hash Translation	✅	2023Q2	D Deleted User	April 24, 2023 → May 10, 2023
➰ Direct Translation Exploration	✅	2023Q2	D Deleted User	April 24, 2023 → May 10, 2023
‣ ⚖️ Translations Proofs	🔴	2023Q2	D Deleted User	March 24, 2023 → May 30, 2023
Paper	✅	2023Q2	D Deleted User	March 27, 2023 → May 31, 2023
‣ Outreach And Collaboration	✅	2023Q2	D Deleted User	March 26, 2023 → April 7, 2023
The new doc needs feedback https://drive.google.com/file/d/1cuOeos7MT7ZAJWtPB3OS8us0v25fsHdp/view?usp=sharing	🔴	2022Q3	Nicola
New formal Research Statement	✅	2022Q3	Anca Nitulescu
Testudo77: Implementation: Batching + Aggregation	🔴	2023Q2
Create open problem page to open the problem to the community	🔴	2023Q1	Matteo Campanelli	March 13, 2023 → March 13, 2023
Theory: Computational commitment de-risked	✅	2023Q1	Matteo Campanelli	February 24, 2023
Theory: Aggregation protocol	✅	2023Q2	D Deleted User
Code documentation	🔴	2023Q1	Mara Mihali	February 17, 2023

‣

🏗️ Product Builders

Name	Status	Quarter	DRI	Date	🎒 Team backlog ㊙️
Deploy a concrete Access Control application	✅	2022Q3	D Deleted User
‣ Feature complete with all cryptographic proofs	✅	2022Q4	D Deleted User
‣ Production ready testnet on Filecoin & Arbitrum (TBD)	✅	2023Q1	D Deleted User
‣ Spin off and real customers	✅	2023Q1	D Deleted User
Public Decryption (Timelock example) + Randomness Beacon	Not started	2023Q2	D Deleted User
Permissionless network	Not started	2023Q2	D Deleted User
Two storage products reach testnet (Retriev.org, Web3bounty.app)	✅	2022Q4	Irene
Onchain.Storage data wallet dashboard	🔴	2022Q4	D Deleted User
‣ Launch Retriev	🟡	2023Q2	D Deleted User
New cofounder	🔵	2023Q2	J Jonathan Easterman
Applications use Medusa	🔵	2023Q2	D Deleted User
Arbitrum testnet deployed	✅	2022Q4	D Deleted User
‣ Medusa is now on FVM Launch (Announced at Spacewarp)	✅	2023Q1	D Deleted User
‣ Public Launch Announcements (est. 10 Feb) with Branding + Documentation	✅	2023Q1	D Deleted User	February 15, 2023 → February 15, 2023
Medusa v0.1.1: Minor features (gas, revoke, etc)	🔵	2023Q1	D Deleted User	February 28, 2023 → February 28, 2023
Developers + Project documentation	✅	2023Q1	J Jonathan Easterman
Pitch deck v1	✅	2023Q1	D Deleted User
Pitch deck v2 in progress with external feedback	🔵	2023Q1	D Deleted User
New website with new production branding	🔵	2023Q1	D Deleted User
Rebrand demo application	Not started
Handle RPC outages gracefully	✅
Present a Medusa Workshop to Spacewarp builders	✅
At least 2 people are using Medusa in Spacewarp projects	✅
DKG proofs - testing phase now	✅
“Just” need to merge PR	✅
Derisking	🟡	2023Q2	D Deleted User
‣ 🗃️ Retriev.org	🔴	2023Q2	D Deleted User
‣ 🐙 Medusa	✅	2023Q1	D Deleted User
Entity formation	✅
Select partners to run independent nodes	Not started	2023Q2	D Deleted User
Security audit	Not started	2023Q2	D Deleted User
Secret Resharing (on pause)	Not started	2023Q2	D Deleted User
Cryptoeconomic model and implementation	Not started	2023Q2	D Deleted User
‣ Mainnet ready	Not started	2023Q2	D Deleted User
Improve network ops	🔵	2023Q1	J Jonathan Easterman
Nucleate Medusa	✅	2023Q2	D Deleted User