הערת העורך: ל-a16z crypto יש סדרה ארוכה של "רובים", משלנו DAO Canon בשנה שעברה שלנו NFT Canon קודם לכן (ולפני כן המקורי שלנו קריפטו קנון) - הקפד להירשם לשלנו ניוזלטר שבועי web3 לעדכונים נוספים כמו גם משאבים שנאספו אחרים.
אז בבהמשך, אספנו קבוצה של משאבים למי שמבקש להבין, להעמיק ולבנות עם כל הדברים אפס ידע: טכנולוגיות חזקות ובסיסיות שמחזיקות את המפתחות להרחבה בלוקצ'יין, ומייצגות את העתיד של יישומים שומרי פרטיות ואינספור חידושים נוספים שיבואו. אם יש לך הצעות לפריטים באיכות גבוהה להוסיף, הודע לנו @a16zcrypto.
מערכות הוכחת אפס ידע קיימות כבר עשרות שנים: הצגתן על ידי שאפי גולדווסר, סילביו מיקלי וצ'רלס רקוף ב-1985 השפיעה על תחום ההצפנה, והוכרה על ידי פרס ACM Turing שהוענק לגולדווסר ומיקלי בשנת 2012. מכיוון שעבודה זו - כולל המעבר שלה מתיאוריה לפרקטיקה ויישומים ב-crypto/web3 כיום - כבר עשרות שנים בהתהוות, אנו חולקים לראשונה בסדרת הקנונים שלנו חלק שני (לעת עתה, כלול כאן למטה): רשימת קריאה המוערת על ידי ג'סטין תאלר, בעקבות החלק הראשון למטה.
תודות: תודה גם למייקל בלאו, סם ראגסדייל וטים רוגארדן.
יסודות, רקע, אבולוציות
חלק מהמסמכים הללו עוסקים גם יותר בקריפטוגרפיה באופן כללי (לא כל ידע אפס כשלעצמו), כולל מתאר בעיות או התקדמות מפתח שמטופלות כיום על ידי אפס הוכחות ידע: כיצד להבטיח פרטיות ואימות ברשתות פתוחות.
כיוונים חדשים בקריפטוגרפיה (1976)
מאת ויטפילד דיפי ומרטין הלמן
https://ee.stanford.edu/~hellman/publications/24.pdf
שיטה להשגת חתימות דיגיטליות ומערכות קריפטו עם מפתח ציבורי
מאת רונלד ריבסט, עדי שמיר, לאונרד אדלמן
https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=856E21BC2F75800D37FD611032C30B9C?doi=10.1.1.40.5588&rep=rep1&type=pdf
פרוטוקולים למערכות קריפטו של מפתח ציבורי (1980)
מאת ראלף מרקל
http://www.merkle.com/papers/Protocols.pdf
תקשורת מאובטחת בערוצים לא מאובטחים (1978)
מאת ראלף מרקל
https://www.merkle.com/1974/PuzzlesAsPublished.pdf
שימוש בעקומות אליפטיות בקריפטוגרפיה (1988)
מאת ויקטור מילר
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf
מורכבות הידע של מערכות הוכחה אינטראקטיביות (1985)
מאת שפי גולדווסר, סילביו מיקאלי, צ'רלס רקוף
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf
הוכחות חישוביות (2000)
מאת סילביו מיקאלי
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf
מהתנגדות להתנגשות ניתנת לחילוץ ועד טיעונים תמציתיים לא אינטראקטיביים של ידע [SNARKs], ושוב (2011)
מאת ניר ביטנסקי, רן קנטי, אלסנדרו קיזה, ערן טרומר
https://eprint.iacr.org/2011/443.pdf
טיעון יעיל של אפס ידע לנכונות של ערבוב (2012)
מאת סטפני באייר וג'נס גרוט
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf
ידע אפס לא אינטראקטיבי תמציתי עבור ארכיטקטורת פון נוימן (2013)
מאת אלי בן ששון, אלסנדרו קיזה, ערן טרומר ומדרס וירצה
https://eprint.iacr.org/2013/879.pdf
שלמות חישובית ניתנת להרחבה, שקופה ופוסט-קוונטית מאובטחת (2018)
מאת אלי בן ששון, עידו בנטוב, ינון חורש ומיכאל ריאבזב
https://eprint.iacr.org/2018/046.pdf
טיעונים של אפס ידע של מטבעות ציבוריים עם (כמעט) תקורה מינימלית של זמן ומרחב (2020)
מאת אלכסנדר בלוק, ג'סטין הולמגרן, אלון רוזן, רון רוטבלום ופרטיק סוני
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645
סקירות ומבוא
הוכחות, טיעונים ואפס ידע - סקירה כללית של מחשוב ניתנים לאימות והוכחות וטיעונים אינטראקטיביים, פרוטוקולים קריפטוגרפיים המאפשרים למוכיח לספק ערובה למאמת שהמוכיח ביצע חישוב מבוקש כהלכה, כולל אפס ידע (כאשר הוכחות לא חושפות מידע מלבד תקפותן) . לטיעוני Zk יש מספר עצום של יישומים בקריפטוגרפיה והם עשו את הקפיצה מתיאוריה לפרקטיקה בעשור האחרון.
מאת ג'סטין תאלר
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf
אבולוציה של מודלים להוכחות אפס ידע - סקירה של הוכחות אפס ידע, שבה מייקלג'ון (אוניברסיטת קולג' בלונדון, גוגל) בוחן את היישומים המניעים את הפיתוח שלהם, המודלים השונים שהופיעו כדי ללכוד את האינטראקציות החדשות הללו, המבנים שאנו יכולים להשיג, והעבודה נשאר לעשות.
מאת שרה מייקלג'ון
https://www.youtube.com/watch?v=HO97kVMI3SE
מפגשי לוח לבן של ZK - מודולי מבוא
עם דן בונה וחב'
https://zkhack.dev/whiteboard/
אבטחה ופרטיות עבור קריפטו עם zkps - חלוצי הוכחת אפס הידע בפועל; מה הם zkps ואיך הם עובדים... כולל "הדגמה" של שלב חי
מאת Zooko Wilcox
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/
נושאים טכנולוגיים מובילים, מוסבר - כולל הגדרות והשלכות של אפס ידע באופן כללי
מאת ג'ו בונאו, טים רוגארדן, סקוט קומינרס, עלי יחיא, כריס דיקסון
https://web3-with-a16z.simplecast.com/episodes/hot-research-summer-blockchain-crypto-tech-topics-explainers-overviews-seminar-videos
כיצד שכבת הפרטיות הקרובה תתקן אינטרנט שבור
מאת הווארד וו
https://future.com/a-privacy-layer-for-the-web-can-change-everything/
מבוא ל-zkSNARKs
עם הווארד וו, אנה רוז
https://zeroknowledge.fm/38-2/
למה ואיך zk-SNARK עובד: הסבר מוחלט
מאת מקסים פטקוס
https://arxiv.org/pdf/1906.07221.pdf
מבוא להוכחות אפס ידע
מאת פרדריק האריסון ואנה רוז
https://www.zeroknowledge.fm/21 [+ כתיבת סיכום במקום אחר כאן]
Zk-SNARKs: מתחת למכסה המנוע
מאת ויטליק בוטרין
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
חלק 1, חלק 2, חלק 3
מהירות מבוזרת - על התקדמות בהוכחות אפס ידע, חומרה מבוזרת
מאת אלנה בורגר
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/
מחקר חדשני ב-ZK - עם חוקר zk בקרן Ethereum
עם מרי מאלר, אנה רוז, קובי גורקן
https://zeroknowledge.fm/232-2/
חקר מחקר zk - עם מנהל המחקר ב-DFINITY; גם מאחורי התקדמות כמו Groth16
עם ג'נס גרוט, אנה רוז, קובי גורקן
https://zeroknowledge.fm/237-2/
SNARK מחקר ופדגוגיה - עם אחד ממייסדי ZCash ו-Starkware
עם אלסנדרו צ'יזה, אנה רוז
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/
צלילות עומק, מדריכי בנאים
יסודות של הוכחות הסתברותיות — קורס עם 5 יחידות מהוכחות אינטראקטיביות ועוד
מאת אלסנדרו צ'יזה
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC
STARKs - חלק I, II, III
מאת ויטליק בוטרין
https://vitalik.ca/general/2017/11/09/starks_part_1.html
https://vitalik.ca/general/2017/11/22/starks_part_2.html
https://vitalik.ca/general/2018/07/21/starks_part_3.html
אנטומיה של STARK - הדרכה בת שישה חלקים המסבירה את המכניקה של מערכת הוכחה STARK
מאת אלן ספנייץ'
https://aszepieniec.github.io/stark-anatomy/
עיצוב SNARK, חלק 1 - סקר, שימוש ברזולים ועוד
מאת ג'סטין תאלר
https://www.youtube.com/watch?v=tg6lKPdR_e4
עיצוב SNARK, חלק 2 - רולאפים, ביצועים, אבטחה
מאת ג'סטין תאלר
https://www.youtube.com/watch?v=cMAI7g3UcoI
מדידת ביצועי SNARK - חזיתות, קצה אחוריים ועוד
מאת ג'סטין תאלר
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/
הבנת PLONK
https://vitalik.ca/general/2019/09/22/plonk.html
מערכת הוכחת אפס ידע PLONK - סדרה של 12 סרטונים קצרים על איך PLONK עובד
מאת דיוויד וונג
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC
מ-AIRs ועד RAPs - איך עובד אריתמטיזציה בסגנון PLONK
מאת אריאל גביזון
https://hackmd.io/@aztec-network/plonk-arithmetiization-air
בדיקות Multiset ב-PLONK וב-Plookup
מאת אריאל גביזון
https://hackmd.io/@arielg/ByFgSDA7D
עיצוב Halo2 - מ-ECC
https://zcash.github.io/halo2/design.html
פלונקי2
https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf
יישומים ומדריכים: הוכחת מושגים, הדגמות, כלים ועוד
מיושם zk - משאבי למידה
מאת 0xPARC
https://learn.0xparc.org/materials/intro
סביבת פיתוח מקוונת עבור zkSNARKs - zkREPL, קבוצה חדשה של כלים לאינטראקציה עם ערימת הכלים של Circom בדפדפן
מאת קווין קוווק
https://zkrepl.dev (+ שרשור הסבר כאן)
תוכניות חשבון ריבועי מאפס לגיבור
מאת ויטליק בוטרין
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
על zkEVMs
עם אלכס גלוכובסקי ואנה רוז
https://zeroknowledge.fm/175-2/
סוגים שונים של zkEVMs
מאת ויטליק בוטרין
https://vitalik.ca/general/2022/08/04/zkevm.html
למידת מכונה של ZK - מדריך והדגמה להכנסת רשת עצבית לתוך SNARK
מאת הוראס פן, פרנסיס הו והנרי פאלאצ'י
https://0xparc.org/blog/zk-mnist
על שפות ZK
עם אלכס אוזדמיר ואנה רוז
https://zeroknowledge.fm/172-2/
Dark Forest - החלת הצפנה של zk למשחקים - משחק RTS (אסטרטגיה בזמן אמת) מבוזר ומתמיד
https://blog.zkga.me/announcing-darkforest
ZKPs למהנדסים - הצצה ל-ZKPs של היער האפל
https://blog.zkga.me/df-init-circuit
צלילה לתוך אפס ידע
עם אלנה נדולינקסקי, אנה רוז, ג'יימס פרסטוויץ'
https://zeroknowledge.fm/182-2/
zkDocs: שיתוף מידע אפס ידע
מאת סם ראגסדייל ודן בונה
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/
הגנה על פרטיות קריפטו אוויר טיפות עם אפס הוכחות ידע
מאת סם רגסדייל
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/
טקסי התקנה מהימנים על השרשרת -
מאת ולריה ניקולאנקו וסם ראגסדייל
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/
תקנות קריפטו, מימון לא חוקי, פרטיות ומעבר לכך - כולל סעיף על אפס ידע בהקשרי רגולציה/ציות; ההבדל בין "שימור הפרטיות" לעומת טכנולוגיות מטשטשות
עם מישל קורבר, ג'אי ראמסוואמי, סונאל צ'וקשי
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained
משאבים אחרים
ניוזלטר zkMesh - ניוזלטר חודשי המשתף את החידושים האחרונים בטכנולוגיות מבוזרות לשימור פרטיות, פיתוח פרוטוקולי פרטיות ומערכות אפס ידע
https://zkmesh.substack.com/
פודקאסט אפס ידע - על יישומי zk מחקר & zk העדכניים ביותר ומומחים בבניית טכנולוגיית פרטיות התומכת בהצפנה
עם אנה רוז
https://zeroknowledge.fm/
…רשימת קריאה מוערת, לפי נושא וכרונולוגיה, מאת ג'סטין תאלר:
SNARKs מ-PCP ליניאריים (המכונה גם SNARKs עם הגדרה ספציפית למעגל)
טיעונים יעילים ללא PCPs קצרים (2007)
מאת יובל ישי, אייל קושילוביץ ורפאיל אוסטרובסקי
לפני בערך 2007, SNARK תוכננו בעיקר באמצעות ה- קיליאן-מיקלי פרדיגמה, של לקיחת הוכחה "קצרה" הניתנת לבדיקה הסתברותית (PCP) ו"קומפילציה קריפטוגרפית" שלה לטיעון תמציתי באמצעות מרקל האשינג והטרנספורמציה של פיאט-שמיר. למרבה הצער, PCPs קצרים הם מסובכים ולא מעשיים, אפילו היום. מאמר זה (IKO) הראה כיצד להשתמש בהצפנה הומומורפית כדי להשיג טיעונים אינטראקטיביים תמציתיים (לא שקופים) מ-PCP "ארוכים אך מובנים". אלה יכולים להיות הרבה יותר פשוטים מאשר PCP קצרים, ול-SNARK המתקבלים יש הוכחות קצרות בהרבה ואימות מהיר יותר. טיעונים אלה הוכרו לראשונה כבעלי פוטנציאל ליעילות מעשית, ושוכללו ויושמו, ב פִּלְפֵּל. למרבה הצער, לטיעונים של IKO יש מוכיח זמן ריבועי ומחרוזת התייחסות מובנית בגודל ריבועי, כך שהם לא מתרחבים לחישובים גדולים.
תוכניות ריבועיות ו-NIZK תמציתיים ללא PCPs (2012)
מאת רוסריו ג'נארו, קרייג ג'נטרי, בריאן פרנו ומריאנה ראיקובה
נייר פריצת דרך זה (GGPR) הפחית את עלויות ההוכחה של הגישה של IKO ממרובע בגודל המעגל לקוזילינארית. בהתבסס על עבודה קודמת של גרוט ו ליפמאא, הוא גם נתן SNARKs באמצעות קריפטוגרפיה מבוססת זיווג, במקום טיעונים אינטראקטיביים כמו ב-IKO. הוא תיאר את ה-SNARKs שלו בהקשר של מה שמכונה כעת בעיות שביעות רצון מאילוץ דרגה 1 (R1CS), הכללה של סיפוק מעגל אריתמטי.
מאמר זה שימש גם כבסיס התיאורטי של ה-SNARKs הראשונים שראו פריסה מסחרית (למשל, ב-ZCash) והוביל ישירות ל-SNARKs שנשארו פופולריים כיום (למשל, Groth16). יישומים ראשוניים של הטיעונים של GGPR הגיעו זעתר ו פינוקיו, וגרסאות מאוחרות יותר כוללות SNARKs עבור C ו BCTV. BCIOP נתן מסגרת כללית שמבהירה את התמורות הלינאריות של PCPs-ל-SNARK (ראה גם נספח א' של זעתר) ומתאר מופעים שונים שלו.
בגודל של טיעונים לא אינטראקטיביים מבוססי זיווג (2016)
מאת Jens Groth
מאמר זה, המכונה בפי העם Groth16, הציג חידוד של SNARKs של GGPR המשיג עלויות אימות בטון עדכניות גם כיום (הוכחות הן 3 אלמנטים קבוצתיים, והאימות נשלט על ידי שלוש פעולות זיווג, לפחות בהנחה שהציבור הקלט קצר). האבטחה מוכחת במודל הקבוצתי הגנרי.
SNARKs עם התקנה מהימנה אוניברסלית
PlonK: תמורות על בסיסי לגראנז' עבור טיעונים אוקומניים לא אינטראקטיביים של ידע (2019)
מאת אריאל גביזון, זכרי וויליאמסון ואואנה צ'ובוטארו
Marlin: עיבוד מקדים של zkSNARKs עם SRS אוניברסלי וניתן לעדכון (2019)
מאת Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely, וניקולס וורד
גם PlonK וגם Marlin מחליפים את ההגדרה המהימנה הספציפית למעגל ב-Groth16 בהגדרה אוניברסלית. זה בא על חשבון הוכחות גדולות פי 4-6. אפשר לחשוב על PlonK ומרלין ככאלה שלוקחים את העבודה הספציפית למעגל במהלך ההגדרה המהימנה ב-Groth16 וקודמים ומעבירים אותה לשלב עיבוד מקדים שקורה לאחר ההגדרה המהימנה, כמו גם במהלך יצירת ההוכחה של SNARK.
היכולת לעבד מעגלים שרירותיים ומערכות R1CS באופן זה נקראת לפעמים הולוגרפיה או מחויבויות חישוב, ותוארה גם ב Spartan (נדון בהמשך האוסף הזה). מכיוון שמתרחשת יותר עבודה במהלך יצירת ההוכחה, ההוכחות של PlonK ומרלין איטיות יותר מ-Groth16 עבור מעגל נתון או מופע R1CS. עם זאת, בניגוד ל-Groth16, ניתן לגרום ל-PlonK ול-Marlin לעבוד עם ייצוגי ביניים כלליים יותר מאשר R1CS.
סכימות מחויבות פולינומיות, פרימיטיבי קריפטוגרפי מפתח ב- SNARKs
מחויבות בגודל קבוע לפולינומים והיישומים שלהם (2010)
מאת אניקט קייט, גרגורי זאוורוצ'ה ואיאן גולדברג
מאמר זה הציג את הרעיון של תוכניות מחויבות פולינומיות. זה נתן סכמה לפולינומים חד-משתנים (הנקראים בדרך כלל התחייבויות KZG) עם התחייבויות בגודל קבוע והוכחות הערכה. הסכימה משתמשת בהגדרה מהימנה (כלומר, מחרוזת התייחסות מובנית) ובקריפטוגרפיה מבוססת זיווג. זה נשאר פופולרי מאוד בפועל כיום, ומשמש ב-SNARKs כולל PlonK ומרלין שנדונו לעיל (וגרוט16 משתמש בטכניקות קריפטוגרפיות דומות ביותר).
Fast Reed-Solomon Interactive Oracle Proofs of Proximity (2017)
מאת אלי בן ששון, עידו בנטוב, ינון חורש, מיכאל ריאבזב
נותן הוכחת אורקל אינטראקטיבית (IOP) עבור בדיקות ריד-סולומון - כלומר, מוכיח שמחרוזת מחויבת קרובה לטבלת ההערכה של פולינום חד-משתני. בשילוב עם מרקל-האשינג והטרנספורמציה של פיאט-שמיר, זה מניב סכימת מחויבות פולינומית שקופה עם הוכחות הערכה בגודל פוליגריתמי (ראה VP19 לפרטים). כיום, זה נשאר הקצר ביותר מבין תוכניות התחייבות פולינומיות פוסט-קוונטיות.
Ligero: טענות תת-לינאריות קלות משקל ללא התקנה מהימנה (2017)
מאת סקוט איימס, כרמית חזאי, יובל ישי ומות'וראמאקרישנן ונקיטאסובראמניאם
בדומה ל-FRI, עבודה זו נותנת IOP לבדיקת ריד-סולומון, אך עם אורך הוכחה לשורש ריבועי ולא פולילוגריתמי. תיאורטית עובד הראה כי על ידי החלפת קוד ריד-סולומון בקוד שונה לתיקון שגיאות עם קידוד מהיר יותר, ניתן להשיג מוכיח זמן ליניארי שעובד באופן מקורי על כל שדה. גישה זו שוכללה ויושמה ב להישבר ו אוריון, מניב ביצועי מוכח עדכניים.
חסיני כדורים: הוכחות קצרות לעסקאות סודיות ועוד (2017)
מאת בנדיקט בנץ, ג'ונתן בוטל, דן בונה, אנדרו פולסטרה, פיטר וויל וגרג מקסוול
חידוד עבודה קודמת על ידי BCCGP, Bulletproofs נותן ערכת מחויבות פולינומית שקופה (למעשה, הכללה הנקראת ארגומנט מוצר פנימי) המבוססת על הקשיות של מחשוב לוגריתמים נפרדים עם גודל הוכחה לוגריתמית אך זמן אימות ליניארי. הסכימה נותרה פופולרית כיום בשל השקיפות וההוכחות הקצרות שלה (למשל, היא משמשת ב-ZCash Orchard וב-Monero).
דורי: טיעונים יעילים ושקופים עבור מוצרים פנימיים מוכללים והתחייבויות פולינומיות (2020)
מאת ג'ונתן לי
דורי מקטין את זמן המאמת ב-Bulletproofs מליניארי ללוגריתמי, תוך שמירה על שקיפות והוכחות בגודל לוגריתמי (אם כי גדול יותר מ-Balletproofs) ושקיפות. משתמש בהתאמות ומבוסס על הנחת SXDH.
הוכחות אינטראקטיביות, הוכחות אינטראקטיביות מרובות מוכיחים, ו-SNARKs משויכים
האצלת חישוב: הוכחות אינטראקטיביות למוגלגים (2008)
מאת שפי גולדווסר, יעל טאומן קלאי, וגיא רוטבלום
לפני מאמר זה, נדרשו הוכחות אינטראקטיביות למטרות כלליות א זמן סופרפולינומי מוכיח. מאמר זה נותן פרוטוקול הוכחה אינטראקטיבי, הנקרא בדרך כלל פרוטוקול GKR, עם מוכיח זמן פולינומי ומאמת זמן קווזילינארי, עבור כל בעיה שיש לה אלגוריתם מקביל יעיל (באופן שווה ערך, ההוכחה האינטראקטיבית חלה על כל מעגל אריתמטי עם עומק קטן).
חישוב מאומת מעשי עם הזרמת הוכחות אינטראקטיביות (2011)
מאת גרהם קורמוד, מייקל מיטזנמאכר, ג'סטין תאלר
מאמר זה (לפעמים נקרא CMT) צמצם את זמן ההוכחה בפרוטוקול GKR מקוואזילינר בגודל המעגל. הפיק את היישום הראשון של הוכחה אינטראקטיבית לשימוש כללי. שורה של עבודות עוקבות (הכל, תאלר13, ג'ִירָפָה, ו מאזנים) הפחית את זמן הריצה של המוכיח עוד יותר, מקווזילינארית ללינארית בגודל המעגל.
vSQL: אימות שאילתות SQL שרירותיות על גבי מסדי נתונים דינמיים במיקור חוץ (2017)
מאת Yupeng Zhang, Daniel Genkin, Jonathan Katz, Dimitrios Papadopoulos, ו-Charalampos Papamanthou
למרות שהכותרת מתייחסת לאזור יישום ספציפי (מאגרי מידע), התרומות של מאמר זה הן כלליות יותר. באופן ספציפי, הוא הבחין שניתן לקבל טיעונים תמציתיים לשביעות רצון המעגל על ידי שילוב של הוכחות אינטראקטיביות עם סכימות מחויבות פולינומיות (עבור פולינומים רב-לינארים).
מאוחר יותר עובד שניתנו הטיעונים אפס ידע והציגו סכימות מחויבות שונות עבור פולינומים רב-לינארים.
ספרטניים: zkSNARKs יעילים ותכליתיים ללא התקנה מהימנה (2019)
מאת Srinath Sety
משיג SNARKs לשביעות רצון מעגלים ו-R1CS על ידי שילוב של הוכחות אינטראקטיביות מרובות מוכיחות (MIPs) עם סכימות מחויבות פולינומיות, תוך בנייה על עבודה קודמת על MIPs יעילים באופן קונקרטי הנקראים תלתן. ההשפעה היא להשיג SNARKs עם הוכחות קצרות יותר מאלה שנגזרות מהוכחות אינטראקטיביות כגון פרוטוקול GKR שנדון לעיל. באנלוגיה ל-PlonK ול-Marlin, ספרטן מראה גם כיצד לעבד מעגלים שרירותיים ומערכות R1CS באמצעות עיבוד מקדים ו-SNARK הוכחה.
ספרטן השתמש בשיטת מחויבות פולינומית מ היירקס. העבודות הבאות נקראו להישבר ו אוריון שלב את ה-MIP של Spartan עם תוכניות מחויבות פולינומיות אחרות כדי להניב את ה-SNARKs המיושמים הראשונים עם מוכיח זמן ליניארי.
PCPs ו-IOPs קצרים
PCP קצרים עם מורכבות שאילתת Polylog (2005)
מאת אלי בן ששון ומדהו סודן
עבודה תיאורטית זו נתנה את ההוכחה הראשונה הניתנת לבדיקה (PCP) עם אורך ההוכחה קווזיליניארי בגודל החישוב שיש לאמת ועלות שאילתה פוליגריתמית (אם כי זמן אימות ליניארי). בעקבות הטרנספורמציה של Kilian-Micali של PCPs ל-SNARKs, זה היה צעד לקראת SNARKs עם מוכיח זמן כמו ליניארי ומאמת זמן פולילוגריתמי.
עבודה תיאורטית מאוחרת יותר הפחית את זמן המאמת לפולילוגריתמי. שבאו אחרי עבודה ממוקדת מעשית חידדה גישה זו, אך PCP קצרים נותרו בלתי מעשיים כיום. כדי להשיג SNARKs מעשיים, מאוחר יותר עובד פנה ל הכללה אינטראקטיבית של PCPs הנקראת הוכחות אינטראקטיביות של אורקל (IOPs). מאמצים אלו הובילו והתבססו עליהם FREE, סכימת מחויבות פולינומית פופולרית הנדונה בסעיף התחייבויות פולינום של אוסף זה.
עבודות אחרות בקטגוריה זו כוללות ZKBoo וצאצאיו. אלה אינם משיגים הוכחות תמציתית, אבל יש להם גורמים קבועים טובים ולכן הם אטרקטיביים להוכחת הצהרות קטנות. הם הובילו למשפחות של חתימות פוסט קוונטיות כגון פיקניק שיש לי היה אופטימיזציה in כמה עובד. ZKBoo מוצג בהתאם לפרדיגמה עיצובית מובהקת שנקראת MPC-בראש, אבל זה מניב IOP.
SNARKs רקורסיביים
חישוב הניתן לאימות הדרגתית או הוכחות ידע מרמזים על יעילות זמן/מרחב (2008)
מאת פול ואליאנט
עבודה זו הציגה את הרעיון הבסיסי של חישוב הניתן לאימות הדרגתית (IVC), שבו מוכיח מפעיל חישוב ושומר בכל עת על הוכחה שהחישוב עד כה היה נכון. הוא בנה IVC באמצעות הרכב רקורסיבי של SNARKs. הנה ה ידע-תקינות המאפיין של SNARKs חיוני לביסוס תקינותם של טיעונים שאינם אינטראקטיביים בעלי חיבור רקורסיבי. מאמר זה גם נתן מחלץ ידע יעיל ביותר עבור SNARKs שמקורם ב-PCP (לפי פרדיגמת Kilian-Micali).
ידע אפס ניתן להרחבה באמצעות מחזורי עקומות אליפטיות (2014)
מאת אלי בן ששון, אלסנדרו קיזה, ערן טרומר ומדרס וירצה
הבא עבודה תיאורטית, מאמר זה השתמש ביישום רקורסיבי של גרסה של SNARK של GGPR, כדי לספק את היישום הראשון של IVC עבור מכונה וירטואלית פשוטה (TinyRAM, מ- SNARKs עבור C עיתון).
הציג גם את הרעיון של מחזוריות של עקומות אליפטיות, אשר שימושיות לחיבור רקורסיבי של SNARKs שעושים שימוש בקריפטוגרפיה של עקומה אליפטית.
קומפוזיציה הוכחה רקורסיבית ללא התקנה מהימנה (2019)
מאת שון בואו, ג'ק גריג ודיירה הופווד
עבודה זו (שנקראת Halo) חוקרת כיצד לחבר באופן רקורסיבי SNARKs שקופים. זה מאתגר יותר מאשר חיבור לא שקוף מכיוון שהליך האימות ב- SNARKs שקוף יכול להיות הרבה יותר יקר.
זה עורר אז א קו of לעבוד שהגיע לשיאו במערכות כגון נובה השגת ביצועים מתקדמים של IVC, עדיפים אפילו על אלו המתקבלים על ידי הרכב של SNARKs לא שקופים כגון Groth16.
יישומים
Zerocash: תשלומים אנונימיים מבוזרים מביטקוין (2014)
מאת אלי בן ששון, אלסנדרו צ'יזה, כריסטינה גרמן, מתיו גרין, איאן מיירס, ערן טרומר, מדרס וירצה
בנייה על עבודות קודמות כולל זרוקוין (ועם מטבע פינוצ'יו כעבודה במקביל), מאמר זה משתמש ב- SNARK שמקורו ב-GGPR כדי לעצב מטבע קריפטוגרפי פרטי. הוביל ל-ZCash.
ג'פטו: חישוב רב-תכליתי הניתן לאימות (2014)
מאת קרייג קוסטלו, סדריק פורנט, ג'ון האוול, מרקולף קולווייס, בנג'מין קרויטר, מייקל נאהריג, בריאן פארנו, וסמי זאחור
אפשר לטעון שגפטו מתארך לפני פיצוץ העניין בביצוע חוזים חכמים פרטיים, לאחר שנכתב בערך שנה לאחר הקמת Ethereum. לפיכך, הוא אינו מוצג בהקשר של ביצוע חוזה חכם פרטי. עם זאת, הוא משתמש ברקורסיה מוגבלת לעומק של SNARKs כדי לאפשר למוכיח לא מהימן להפעיל כל תוכנת מחשב פרטית (מחויבת/חתומה) על נתונים פרטיים, מבלי לחשוף מידע על התוכנית המופעלת או על הנתונים שהיא מופעלת עליהם. בהתאם לכך, היא קודמת לעבודה בפלטפורמות פרטיות של חוזים חכמים, כגון Zexe [מתואר להלן].
ASICs הניתנים לאימות (2015)
מאת Riad Wahby, Max Howald, Siddharth Garg, Abhi shelat, Michael Walfish
מאמר זה מתייחס לבעיה כיצד להשתמש בצורה בטוחה ופורה ב-ASIC המיוצר במפעל יציקה לא מהימן (בשנת 2015, היו רק חמש מדינות עם בתי יציקה מובילים). הגישה היא שה-ASIC המהיר אך הלא מהימן יוכיח את נכונות הפלט שלו לאמת שפועל על ASIC איטי יותר אך מהימן. הפתרון מעניין כל עוד זמן הביצוע הכולל של המערכת (כלומר, סכום זמני הריצה של המוכיח והמאמת בתוספת עלויות העברת נתונים כלשהן) קטן מקו הבסיס הנאיבי: הזמן הדרוש להפעלת החישוב במלואו באיטיות יותר -אך מהימן ASIC. באמצעות גרסה של ההוכחות האינטראקטיביות GKR/CMT/Allspice, המאמר אכן מנצח את קו הבסיס הנאיבי עבור מספר בעיות יסוד, כולל טרנספורמציות תיאורטיות של מספרים, התאמת דפוסים ופעולות עקומה אליפטית. עבודה זו מציעה שמערכות הוכחה מסוימות מתאימות יותר ליישום חומרה מאחרות. אופטימיזציה של מערכות הוכחה ליישום חומרה מקבלת כעת רב תשומת לב, אבל נותר לחקור הרבה.
ניתן לאמת פונקציות השהייה (2018)
מאת דן בונה, ג'וזף בונאו, בנדיקט בונץ ובן פיש
הציג את הסימון של פונקציות השהיה הניתנות לאימות (VDFs), פרימיטיבי קריפטוגרפי ששימושי נרחב ביישומי בלוקצ'יין, למשל, בהפחתת מניפולציה אפשרית של פרוטוקולי קונצנזוס הוכחת הימור. SNARKs (במיוחד עבור חישוב ניתן לאימות מצטבר) מציעים מסלול ל-VDFs חדישים.
Zexe: הפעלת חישוב פרטי מבוזר (2018)
מאת שון בואו, אלסנדרו צ'יזה, מתיו גרין, איאן מיירס, פראטיוש מישרה והווארד וו
Zexe הוא עיצוב עבור פלטפורמת חוזה חכם פרטית. אפשר לראות את Zexe כהרחבה של Zerocash (מתואר לעיל). Zerocash מאפשרת להפעיל אפליקציה בודדת על השרשרת (המאפשרת למשתמשים להעביר אסימונים) תוך הגנה על פרטיות נתוני המשתמש, למשל למי הם שולחים אסימונים, מקבלים ממנו אסימונים, כמות האסימונים שהועברו וכו'. Zexe מאפשרת רבות יישומים שונים (חוזים חכמים) לרוץ על אותו בלוקצ'יין ולקיים אינטראקציה זה עם זה. עסקאות מבוצעות מחוץ לשרשרת, והוכחות לביצוע נכון מתפרסמות על השרשרת. לא רק פרטיות הנתונים מוגנת, כך גם פרטיות הפונקציה. המשמעות היא שההוכחה הקשורה לכל עסקה אפילו לא חושפת לאילו אפליקציות העסקה מתייחסת. תרומה הנדסית כללית יותר של Zexe היא שהיא הציגה את BLS12-377, קבוצת עקומה אליפטית שימושית להרכב עומק-1 יעיל של SNARKs מבוססי זיווג.
מכונות מצב משוכפלות ללא ביצוע משוכפל (2020)
מאת ג'ונתן לי, קיריל ניקיטין וסרינת סטי
זהו אחד המאמרים האקדמיים הבודדים על אוסף מדרגיות של בלוקצ'יין. הוא אינו משתמש במונח רול-אפים, משום שהוא מתארך מראש או בו-זמנית עם המושג שמוצג מחוץ לספרות האקדמית.
חזיתות (טרנספורמציות יעילות מתוכנות מחשב לייצוגי ביניים כגון שביעות רצון של מעגלים, R1CS ועוד)
הפחתה מהירה מזיכרון RAM לבעיות שביעות רצון של אילוצים ניתנים להאצלה (2012)
מאת אלי בן ששון, אלסנדרו קיזה, דניאל גנקין וערן טרומר
מנקודת מבט מודרנית, זוהי עבודה מוקדמת על טרנספורמציות מעשיות של מחשב-תוכנת-למעגל-SAT עבור הפשטה של מכונה וירטואלית (VM). בהתבסס על עבודות מסוף שנות ה-1970 עד שנות ה-1990 (למשל, עבודה של רובסון) מאמר זה מפרט הפחתה דטרמיניסטית מביצוע VM עבור שלבי T לשביעות רצונו של מעגל בגודל O(T*polylog(T)).
מאמרים הבאים, למשל, SNARKs עבור C ו BCTV, המשיך לפתח חזיתות באמצעות הפשטה VM, והמופעים המודרניים כוללים פרויקטים כגון בקהיר, RISC אפס, ו מצולע מידן.
נטילת חישוב מאומת מבוסס הוכחה כמה צעדים קרוב יותר למעשיות (2012)
מאת Srinath Setty, Victor Vu, Nikhil Panpalia, Benjamin Braun, Muqeet Ali, Andrew J. Blumberg, and Michael Walfish
מאמר זה, המכונה ג'ינג'ר, הוא תרומה מוקדמת נוספת לטכניקות פרקטיות פרקטיות. ג'ינג'ר הציגה גאדג'טים לפרימיטיבים תכנות כלליים כמו תנאים וביטויים לוגיים, השוואות וחשבון סיביות באמצעות פיצול סיביות, אריתמטיקה פרימיטיבית של נקודה צפה וכו'. היא השתמשה בגאדג'טים אלה כדי לספק את החזית המיושמה הראשונה משפה ברמה גבוהה לדרגה נמוכה אילוצים אריתמטיים (בדומה למה שמכונה כיום R1CS), ייצוג ביניים (IR) שעליו ניתן להחיל קצה אחורי של SNARK.
בעוד שהעיתון "הפחתות מהיר" וצאצאיו משתמשים בגישת "אימולטור מעבד" בהפקת IR (כלומר, ה-IR אוכף שהמוכיח הפעיל כהלכה תוכנית מסוימת על ידי יישום פונקציית המעבר של ה-CPU עבור מספר מוגדר של שלבים) , ג'ינג'ר וצאצאיו נוקטים בגישה דומה יותר ל-ASIC, ומייצרים IRs המותאמים לתוכנת המחשב שהמוכיח טוען להפעיל נכון.
לדוגמה, מזנון מראה שניתן לטפל בזרימת בקרה מורכבת במודל ASIC, על ידי הפיכת זרימת בקרה כזו למכונה במצב סופי המותאמת לתוכנית המתבצעת, וכי גישה זו יכולה להיות יעילה משמעותית מבניית אמולטור מעבד למטרות כלליות. xJsnark נותן בנייה יעילה לאריתמטיקה מרובת דיוק, אופטימיזציות עבור זיכרון RAM ו-ROM, וחושפת שפה ברמה גבוהה דמוית Java למתכנת, שנשארה פופולרית כיום. CirC מציין כי קומפילציה של תוכנות מחשב ל-R1CS קשורה קשר הדוק לטכניקות ידועות מניתוח תוכניות ובונה ערכת כלים לבניית מהדר המשלבת רעיונות משתי הקהילות ("LLVM לייצוגים דמויי מעגל"). עבודות קודמות שתרמו לחזיתות בסגנון ASIC כוללות פינוקיו ו ג'פטו.
העיתון "הפחתות מהיר" השתמש במבנה מסובך ויקר שנקרא "רשתות ניתוב" עבור מה שנקרא בדיקת זיכרון (כלומר, להבטיח שהמוכיח הלא מהימן שומר בצורה נכונה על זיכרון הגישה האקראית של ה-VM לאורך כל ביצוע ה-VM שנכונותו מוכחת). בחירה זו נעשתה מכיוון שעבודות מוקדמות כמו זו ביקשו להשיג PCP, מה שחייב את הקצה הקדמי להיות שניהם לא אינטראקטיבי ומאובטח מבחינה תאורטית. עבודה מאוחרת יותר התקשרה מְזָוֶה (קודם של ה מזנון העבודה שהוזכרה לעיל) השתמשה בעצי מרקל במקום רשתות ניתוב, תוך השגת יעילות על ידי הידור של פונקציית hash אלגברית (כלומר, "ידידותית ל-SNARK"), עקב אג'טאי, לתוך אילוצים. זה הביא לחזיתות "מאובטחות מבחינה חישובית". כיום, יש ספרות מחקרית גדולה על פונקציות hash ידידותיות ל-SNARK, עם דוגמאות כולל פוסידון, MiMC, בטון מזוין, להציל, ועוד.
טכניקות מתקדמות להבטחת שהמוכיח שומר על זיכרון RAM בצורה נכונה מסתמכות על מה שמכונה "טביעת אצבע ללא שינוי תמורה" המתוארכת לפחות ל ליפטון (1989) ומשמש לבדיקת זיכרון על ידי בלום וחב'. (1991). טכניקות אלו כרוכות מטבען באינטראקציה בין מוכיח ומאמת, אך ניתן להפוך אותן ללא אינטראקטיביות עם הטרנספורמציה של פיאט-שמיר. ככל הידוע לנו, הם הוכנסו לספרות על חזיתות SNARK מעשיות על ידי מערכת בשם vRAM.
טכניקות טביעת אצבעות ללא שינוי תמורה משמשות כעת בחזיתות רבות וב-SNARKs עבור הפשטות מכונות וירטואליות, כולל למשל בקהיר. רעיונות הקשורים קרובים הופיעו שוב בהקשרים קשורים בשתי העבודות שלהלן, שנמצאות בשימוש נרחב בפועל כיום.
הוכחות כמעט ליניארי זמן אפס ידע לביצוע נכון של תוכנית (2018)
מאת ג'ונתן בוטל, אנדריאה צ'רולי, ג'נס גרוט, סונה יאקובסן ומרי מאלר
Plookup: פרוטוקול פולינום פשוט לטבלאות חיפוש (2020)
מאת אריאל גביזון וזכרי וויליאמסון
עבודות מוקדמות בחזיתות ייצגו פעולות "לא אריתמטיות" (כגון בדיקות טווח, פעולות סיביות והשוואות מספרים שלמים) בתוך מעגלים ו-IRs קשורים על ידי פירוק רכיבי שדה לסיביות, ביצוע הפעולות על סיביות אלו, ולאחר מכן "אריזה" התוצאה חזרה לאלמנט שדה יחיד. מבחינת גודל המעגל המתקבל, זה מביא לתקורה לוגריתמית לכל פעולה.
שתי העבודות לעיל (BCGJM ו-Plookup) נותנות טכניקות משפיעות (המבוססות על מה שמכונה "טבלאות חיפוש") לייצוג יעיל יותר של פעולות אלו בתוך מעגלים, במובן מופחת. באופן גס, עבור פרמטר B כלשהו שנבחר על ידי מעצב הקצה, אלה מפחיתים את מספר השערים הנדרשים לייצג כל פעולה לא אריתמטית במעגל על ידי גורם לוגריתמי ב-B, במחיר של התחייבות קריפטוגרפית של המוכיח לתוספת וקטור "עצה" באורך בערך B.
