פרוטוקול הקונצנזוס של Stellar תואר לראשונה ב מאמר מדעי דוד מזייר ב-2015. זוהי "מערכת הסכם ביזנטי פדרלית" המאפשרת לרשתות מחשוב מבוזרות וחסרות מנהיג להגיע ביעילות לקונצנזוס על החלטה. רשת התשלומים של Stellar משתמשת ב- Stellar Consensus Protocol (SCP) כדי לשמור על היסטוריית עסקאות עקבית שגלויה לכל המשתתפים.

פרוטוקולי קונצנזוס נחשבים קשים להבנה. SCP פשוט יותר מרובם, אך עדיין חולק את המוניטין הזה - בין היתר בשל הרעיון המוטעה ש"הצבעה פדרציה", שהיא נושא המחצית הראשונה של המאמר המדעי, היא SCP. אבל זה לא נכון! זהו רק אבן בניין חשובה שהמחצית השנייה של המאמר משתמשת בה כדי ליצור של בפועל פרוטוקול קונצנזוס של כוכבים.

במאמר זה נסביר בקצרה מהי "מערכת הסכמים", מה יכול להפוך אותה ל"ביזנטית" ומדוע להפוך את השיטה הביזנטית ל"פדרלית". לאחר מכן נסביר את הליך ההצבעה המאוחד המתואר במאמר SCP, ולבסוף נסביר את פרוטוקול SCP עצמו.

מערכות הסכמים

מערכת הסכמים מאפשרת לקבוצת משתתפים להגיע להסכמה בנושא, כמו למשל מה להזמין לארוחת צהריים.

ב-Interstellar, הטמענו מערכת הסכמי אוכל משלנו: אנחנו מזמינים את מה שמנהל התפעול שלנו, ג'ון, אומר. זוהי מערכת הסכמים פשוטה ויעילה. כולנו סומכים על ג'ון ומאמינים שהוא ימצא משהו מעניין ומזין בכל יום.

אבל מה אם ג'ון ינצל לרעה את האמון שלנו? הוא יכול להחליט לבד שכולנו צריכים להפוך לטבעונים. בעוד שבוע-שבועיים, כנראה נפיל אותו ונמסור את השלטון לאליזבת. אבל פתאום היא אוהבת אבוקדו עם אנשובי וחושבת שכולם צריכים להיות כאלה. כוח משחית. אז עדיף למצוא שיטה דמוקרטית יותר: דרך כלשהי לוודא שהעדפות שונות נלקחות בחשבון, תוך הבטחת תוצאה בזמן וחד משמעי, כך שאף אחד לא יזמין צהריים, או שחמישה אנשים יבצעו הזמנות שונות, או הדיון נמשך עד הערב.

נראה שהפתרון פשוט: ערכו הצבעה! אבל זה רושם מטעה. מי יאסוף את פתקי ההצבעה וידווח על התוצאות? ולמה שאחרים יאמינו למה שהוא אומר? אולי אנחנו יכולים בהתחלה הצביעו למנהיג שאנו סומכים עליו שיוביל את ההצבעה - אבל שיוביל אותה הראשון בהצבעה? מה אם אנחנו לא יכולים להסכים על מנהיג? או מה אם נגיע להסכמה, אבל המנהיג הזה נתקע בפגישה או יוצא לחופשת מחלה?

בעיות דומות מתרחשות ברשתות מחשבים מבוזרות. כל המשתתפים או הצמתים חייבים להסכים על החלטה כלשהי, כגון תורו של מי לעדכן קובץ משותף או להסיר משימה מהתור לעיבוד. ברשת מטבעות קריפטוגרפיים, צמתים צריכים שוב ושוב לבחור איך נראה הסיפור המלא מתוך כמה גרסאות אפשריות, שלפעמים מתנגשות. הסכם רשת זה מספק ביטחון למקבל שהמטבע (א) תקף (לא מזויף) ו-(ב) עדיין לא הוצא במקום אחר. זה גם מבטיח שהוא יוכל לבזבז את המטבעות בעתיד מכיוון שלמקבל החדש יהיו אותן ערבויות מאותן סיבות.

כל מערכת קונצנזוס ברשת מחשוב מבוזרת חייבת להיות סובלנית לתקלות: עליה לייצר תוצאות עקביות למרות שגיאות כמו קישורים איטיים, צמתים לא מגיבים וסידור הודעות שגוי. ביזנטי מערכת ההסכם עמידה בנוסף לשגיאות "ביזנטיות": צמתים שנותנים מידע כוזב, בין אם בשל טעות ובין אם בניסיון מכוון לערער את המערכת או להשיג יתרון כלשהו. סובלנות תקלות "ביזנטית" - היכולת לסמוך על החלטה קבוצתית גם כאשר חלק מחברי הקבוצה עשויים לשקר או לא לציית לכללי קבלת ההחלטות - נקראת משל על הגנרלים של האימפריה הביזנטיתשניסה לתאם את הפיגוע. תיאור טוב אצל אנתוני סטיבנס.

שקול את בעלת מטבע הקריפטו אליס, שחייבת לבחור בין רכישת גלידה טעימה מבוב לבין תשלום חובה של קרול. אולי אליס רוצה לשלם לשניהם בבת אחת על ידי הוצאת אותו מטבע במרמה. כדי לעשות זאת, עליה לשכנע את המחשב של בוב שהמטבע מעולם לא שולם לקרול, ולשכנע את המחשב של קרול שהמטבע מעולם לא שולם לבוב. מערכת ההסכמים הביזנטית הופכת את זה כמעט לבלתי אפשרי, באמצעות צורה של שלטון רוב שנקרא מִניָן. צומת ברשת כזו מסרב לעבור לגרסה מסוימת של ההיסטוריה עד שהוא רואה שמספר מספיק של עמיתים - מניין - מסכימים למעבר כזה. ברגע שזה יקרה, הם יהוו גוש הצבעה גדול מספיק כדי לאלץ את צמתי הרשת הנותרים להסכים עם החלטתם. אליס יכולה להכריח כמה צמתים לשקר בשמה, אבל אם הרשת תהיה גדולה מספיק, הניסיון שלה יוכרע בהצבעות של צמתים כנים.

כמה צמתים נדרשים למניין? לכל הפחות, רוב, או יותר נכון, רוב מיוחס למאבק בטעויות והונאות. אבל כדי לספור את הרוב, אתה צריך לדעת את המספר הכולל של המשתתפים. במשרד Interstellar או בבחירות המחוזיות, קל לגלות את המספרים הללו. אבל אם הקבוצה שלך היא רשת מוגדרת באופן רופף שבה צמתים יכולים להיכנס ולצאת כרצונם ללא אישור מהמרכז, אז אתה צריך פדרלי מערכת הסכמים ביזנטית המסוגלת לקבוע מניינים לא מתוך רשימה קבועה מראש של צמתים, אלא באופן דינמי, מתוך תמונת מצב משתנה ללא הרף ובלתי נמנעת של צמתים בנקודת זמן נתונה.

זה אולי נראה בלתי אפשרי ליצור מניין מנקודת מבט של צומת בודד ברשת עצומה, אבל זה אפשרי. מניין כזה יכול אפילו להבטיח את תוצאות ההצבעה המבוזרת. הספר הלבן של SCP מראה כיצד לעשות זאת באמצעות הליך שנקרא בהצבעה פדרלית.

לחסרי סבלנות

שאר המאמר מתאר את ההצבעה הפדרלית ואת פרוטוקול הקונצנזוס של Stellar ביתר פירוט. אם אינך מעוניין בפרטים, הנה סקירה כללית של התהליך.

הצמתים עורכים סבבי הצבעה פדרליים על "מועמדים". סבב הצבעה פדרלי פירושו:
- הצומת מצביע עבור אמירה כלשהי, למשל, "אני מציע את הערך של V";
- הצומת מקשיב לקולות העמיתים עד שהוא מוצא אחד שיכול "לקבל";
- הצומת מחפש "קוורום" עבור קביעה זו. מניין "מאשר" את המועמד.
ברגע שצומת יכול לאשר מועמד אחד או יותר, הוא מנסה "להכין" את ה"קלפי" באמצעות מספר סבבים של הצבעה פדרית.
ברגע שצומת מסוגל לאמת שהקלפי מוכן, הוא מנסה לבצע אותו באמצעות סבבי הצבעה פדרליים נוספים.
ברגע שצומת יכול לאשר התחייבות של פתק הצבעה, הוא יכול "להחצין" את הערך של אותה הצבעה על ידי שימוש בו כתוצאת קונצנזוס.

שלבים אלה כוללים סבבי הצבעה מרובים של הפדרציה, אשר יוצרים ביחד סבב SCP אחד. בואו נסתכל מקרוב על מה שקורה בכל שלב.

הצבעה פדרית

הצבעה פדרית היא הליך לקביעה אם הרשת יכולה להסכים על הצעה. בסבב ההצבעה, כל צומת חייב לבחור אחד מבין ערכים אפשריים רבים. זה לא יכול לעשות זאת אלא אם כן הוא בטוח שצמתים אחרים ברשת לא יבחרו בתוצאה אחרת. כדי לוודא זאת, צמתים מחליפים מטח הודעות הלוך ושוב כך שכולם אישרכי מִניָן קשרים לוקח אותו דבר החלטה. שאר חלק זה מסביר את המונחים במשפט זה וכיצד מתרחש ההליך כולו.

קוורום ופרוסות מניין

נתחיל בהגדרת מניין. כפי שדיברנו למעלה, ברשת מבוזרת עם חברות דינמית, אי אפשר לדעת מראש את מספר הצמתים ולכן כמה דרושים לרוב. הצבעה פדרית פותרת בעיה זו על ידי הצגת רעיון חדש קיצוץ מניין (נתח מניין): קבוצה קטנה של עמיתים שצומת סומך עליהם כדי להעביר מידע על מצב ההצבעה לשאר הרשת. כל צומת מגדיר את פרוסת המניין שלו (שהוא הופך לחבר דה פקטו).

גיבוש הקוורום מתחיל בקיצוץ מניין. עבור כל צומת, מתווספים הצמתים החתוכים שלו. לאחר מכן מוסיפים את מונחי הפרוסה הצמתים הללו וכולי. ככל שתמשיך, יש יותר ויותר צמתים שאינך יכול להוסיף כי הם כבר כלולים בפרוסה. כאשר אין יותר צמתים חדשים להוסיף, התהליך נעצר: יצרנו מניין על ידי "סגירה טרנזיטיבית" של פרוסת המניין של הצומת הראשוני.

כדי למצוא מניין מצומת נתון...

... הוסף חברים מהנתח שלו...

...לאחר מכן נוסיף איברי פרוסה של הצמתים האלה.

אנו ממשיכים עד שלא נותרו צמתים להוסיף.

לא נותרו צמתים להוסיף. זהו מניין.

למעשה, כל צומת יכול להופיע ביותר מפרוסה אחת. כדי ליצור מניין, בחר רק אחת מהפרוסות והוסף חברים; לאחר מכן בחר כל פרוסה עבור כל אחד מהחברים והוסף חברים זה לחתוך וכן הלאה. המשמעות היא שכל צומת חבר במניינים אפשריים רבים.

בחר רק פרוסת מניין אחת בכל שלב.

מניין אפשרי אחד. או אלטרנטיבה...

...בחר פרוסות אחרות...

…(כאשר זה אפשרי)…

... יוצרת מניין נוסף.

איך צומת יודע באילו פרוסות נמצאים צמתים אחרים? באותו אופן כמו מידע אחר על צמתים אחרים: מהשידורים שכל צומת משדר לרשת כאשר מצב ההצבעה שלו משתנה. כל שידור כולל מידע על הפרוסות של הצומת השולח. המסמך הלבן של SCP אינו מציין מנגנון תקשורת. בדרך כלל משתמשים ביישומים פרוטוקול רכילות לשידור מובטח של הודעות ברחבי הרשת.

נזכיר כי במערכת ההסכמים הביזנטית הלא פדרלית, מניין מוגדר כרוב של כל הצמתים. מערכת ההסכמה הביזנטית מתוכננת מנקודת מבט של השאלה: כמה צמתים לא ישרים יכולה המערכת לסבול? במערכת של N צמתים שנועדה לשרוד כשלים ב-f, צומת אמור להיות מסוגל להתקדם על ידי קבלת משוב מעמיתים N-f מאחר ש-f מהם עשוי להיות מושבת. אבל לאחר שקיבלנו תגובה מעמיתים N−f, אנו יכולים להניח שכל העמיתים f (מהם הצומת לא קיבל תגובה) הם למעשה כנים. לפיכך, f מתוך N−f עמיתים (מהם התקבלה התגובה) הם זדוניים. כדי שצמתים יגיעו לאותו קונצנזוס, רוב הצמתים הנותרים חייבים להיות כנים, כלומר, אנחנו צריכים ש-N−f יהיה גדול מ-2f או N > 3f. כך שבדרך כלל למערכת שתוכננה לשרוד כשלי f תהיה סך של צמתים N=3f+1 וגודל מניין של 2f+1. ברגע שהצעה עוברת את רף המניין, שאר חברי הרשת משוכנעים שכל הצעה מתחרה תיכשל. כך הרשת מתכנסת לתוצאה.

אבל במערכת הפדרלית של הסכמים ביזנטיים, לא רק שלא יכול להיות רוב (כי אף אחד לא יודע את הגודל הכולל של הרשת), אלא שהמושג של רוב הוא חסר תועלת לחלוטין! אם החברות במערכת פתוחה, אז מישהו יכול להשיג רוב פשוט על ידי ביצוע מה שנקרא התקפת Sybil: הצטרפות שוב ושוב לרשת על פני מספר צמתים. אז למה אפשר לקרוא לסגירת פרוסה טרנזיטיבית מִניָן, וכיצד היא מסוגלת לדכא הצעות מתחרות?

טכנית, אין מצב! תארו לעצמכם רשת של שישה צמתים, שבה שתי שלישיות מבודדות אחת בפרוסות המניין של זו. תת-הקבוצה הראשונה עשויה לקבל החלטה שהשנייה לעולם לא תשמע עליה, ולהיפך. אין דרך לרשת זו להגיע לקונצנזוס (אלא במקרה).

לכן, SCP דורש שכדי להצביע מאוחדת (וכדי שהמשפטים החשובים של המאמר יתחילו), לרשת חייב להיות מאפיין שנקרא צומת המניינים. ברשת עם מאפיין זה, כל שני קוורום שניתן לבנות תמיד חופפים בצומת אחד לפחות. לקביעת הסנטימנט הרווח של הרשת, זה טוב כמו שיש רוב. אינטואיטיבית, זה אומר שאם מניין כלשהו מסכים להצהרה X, שום מניין אחר לא יוכל לעולם להסכים לשום דבר אחר, כי הוא יכלול בהכרח צומת כלשהו מהמניין הראשון שכבר הצביע בעד X.

אם יש צומת של מניינים ברשת...

...ואז כל שני מניינים שאתה יכול לבנות...

...תמיד יצטלב.

(כמובן שצמתים חופפים עלולים להתברר כשקרנים ביזנטיים או גרועים בדרך אחרת. במקרה זה, צומת הקוורום אינו עוזר כלל לרשת להסכים. מסיבה זו, רבות מהתוצאות במסמך הלבן של SCP מבוססות על הנחות מפורשות, כמו מה שנותר במעבר המניין ברשת גם לאחר הסרת צמתים רעים. לשם הפשטות, נעזוב את ההנחות הללו משתמע בהמשך המאמר).

זה אולי נראה לא הגיוני לצפות שמעבר מניין אמין אפשרי ברשת של צמתים עצמאיים. אבל יש שתי סיבות למה זה כך.

הסיבה הראשונה היא קיומו של האינטרנט עצמו. האינטרנט הוא דוגמה מושלמת לרשת של צמתים עצמאיים עם מניינים מצטלבים. רוב הצמתים באינטרנט מתחברים רק לכמה צמתים מקומיים אחרים, אבל הקבוצות הקטנות הללו חופפות מספיק כדי שניתן יהיה להגיע לכל צומת מכל צומת אחר לאורך מסלול כלשהו.

הסיבה השנייה היא ספציפית לרשת התשלומים Stellar (השימוש הנפוץ ביותר ב-SCP). לכל נכס ברשת Stellar יש מנפיק, וההנחיות של Stellar מחייבות כל מנפיק לייעד צמתים אחד או יותר ברשת לעיבוד בקשות מימוש. זה האינטרס שלך לכלול באופן ישיר או עקיף את הצמתים האלה בפרוסות המניין עבור כל נכס שאתה מעוניין בו. המניינים של כל הצמתים המעוניינים בנכס נתון יחפפו אז לפחות באותם צמתי מימוש. צמתים המעוניינים במספר נכסים יכללו את כל צמתי הפדיון של המנפיקים בהתאמה בפרוסות המניין שלהם, והם יבקשו לאגד את כל הנכסים יחד. בנוסף, כל הנכסים שאינם מקושרים בדרך זו לאחרים ברשת, וכן לא צריך להיות מחובר - זה מתוכנן כך שלא תהיה חפיפה מניינית עבור רשת זו (לדוגמה, בנקים מאזור הדולר רוצים לפעמים לסחור עם בנקים מגוש האירו ובנקים מאזור הפסו, אז הם נמצאים באותה רשת, אבל אף אחד מהם לא מהם אכפת מהרשת הנפרדת של ילדים שמוכרים כרטיסי בייסבול).

כמובן, ожидание מעבר הקוורום אינו להבטיח. מערכות אחרות של הסכמים ביזנטיים חבות רבות מהמורכבות שלהן להבטחת המניינים. חידוש חשוב של SCP הוא שהוא מסיר את האחריות ליצירת מניינים מאלגוריתם הקונצנזוס עצמו ומביא אותו לרמת היישום. לפיכך, למרות שהצבעה פדרית כללית מספיק כדי להצביע על כל נושא, מהימנותה תלויה למעשה באופן קריטי במשמעות הרחבה יותר של משמעויות אלו. שימושים היפותטיים מסוימים עשויים שלא להיות מועילים ליצירת רשתות מקושרות היטב כמו אחרים.

הצבעה, קבלה ואישור

בסבב הצבעה מאוחד, צומת מתחיל להצביע באופן אופציונלי עבור ערך V כלשהו. משמעות הדבר היא שידור הודעה לרשת: "אני צומת N, פרוסות הקוורום שלי הן Q, ואני מצביע עבור V." כאשר צומת מצביע בצורה זו, הוא מבטיח שהוא מעולם לא הצביע נגד V ולעולם לא יצביע.

בשידורי עמית לעמית, כל צומת רואה כיצד האחרים מצביעים. ברגע שצומת אסף מספיק מההודעות האלה, הוא יכול לעקוב אחר פרוסות המניין ולנסות למצוא מניינים. אם הוא רואה מניין של עמיתים שגם מצביעים ל-V, הוא יכול להמשיך אימוץ V ושדר את ההודעה החדשה הזו לרשת: "אני צומת N, פרוסות המניין שלי הן Q, ואני מקבל V." הקבלה מספקת ערובה חזקה יותר מהצבעה פשוטה. כאשר צומת מצביע עבור V, הוא לעולם לא יכול להצביע עבור אפשרויות אחרות. אבל אם צומת מקבל V, אף צומת ברשת לא יקבל לעולם את האפשרות האחרת (משפט 8 במאמר הלבן של SCP מוכיח זאת).

כמובן שקיימת סבירות גבוהה שלא יהיה מיד מניין של צמתים שמסכים עם V. צמתים אחרים עשויים להצביע עבור ערכים אחרים. אבל יש דרך נוספת לצומת לעבור מהצבעה פשוטה לקבלה. נ' רשאי לקבל ערך אחר ל-W, גם אם לא הצביע בעדו, וגם אם אינו רואה בכך מניין. כדי להחליט לשנות את ההצבעה שלך, פשוט ראה סט חסימה צמתים שקיבלו W. מערך חסימה הוא צומת אחד מכל אחת מפרוסות המניין N. כפי שהשם מרמז, הוא יכול לחסום כל משמעות אחרת. אם כל הצמתים בקבוצה כזו יקבלו W, אז (לפי משפט 8) לעולם לא ניתן יהיה ליצור מניין שלוקח ערך שונה, ולכן בטוח גם ש-N יקבל W.

צומת N עם שלוש פרוסות מניין.

BDF הוא ערכת חסימה עבור N: היא כוללת צומת אחד מכל אחת מהפרוסות של N.

BE הוא גם קבוצת חסימה עבור N מכיוון ש-E מופיע בשתי פרוסות של N.

אבל מערך החסימה אינו מניין. זה יהיה קל מדי להערים על צומת N לקבל את הערך הרצוי אם זה היה מספיק לפרוץ רק צומת אחד בכל אחת מהפרוסות של N. לכן, קבלת הערך אינה סוף ההצבעה. במקום זאת, N חייב לאשר את הערך, כלומר לראות מניין של צמתים המקבלים אותו. אם זה יגיע כל כך רחוק, אז, כפי שמוכיח הספר הלבן של SCP (במשפט 11), גם שאר הרשת תאשר בסופו של דבר את אותו ערך, אז N תסיים את ההצבעה הפדרציה עם ערך מסוים כתוצאה מכך.

הצבעה פדרית.

תהליך ההצבעה, הקבלה והאישור מהווה סבב שלם אחד של הצבעה פדרציה. פרוטוקול הקונצנזוס של Stellar משלב רבים מהסבבים הללו כדי ליצור מערכת קונצנזוס מלאה.

פרוטוקול קונצנזוס כוכבים

שני המאפיינים החשובים ביותר של מערכת קונצנזוס הם - אבטחה и שְׂרִידוּת. אלגוריתם קונצנזוס הוא "בטוח" אם הוא לעולם לא יכול לתת תוצאות שונות למשתתפים שונים (עותק ההיסטוריה של בוב לעולם לא יסתור את קרול). "חיות" פירושה שהאלגוריתם תמיד יפיק תוצאה, כלומר, הוא לא ייתקע.

הליך ההצבעה הפדרלי תואר בטוח במובן זה שאם צומת מאשר את הערך של V, אף צומת אחר לא יאשר את הערך האחר. אבל "לא יאשר משמעות אחרת" לא אומר שזה בהכרח יאשר משהו. המשתתפים יכולים להצביע על כל כך הרבה ערכים שונים ששום דבר לא יגיע לסף הקבלה. זה אומר שבהצבעה פדרלית אין שְׂרִידוּת.

פרוטוקול הקונצנזוס של Stellar משתמש בהצבעה מאוחדת באופן שמבטיח גם ביטחון וגם שרידות. (לבטחון והישרדות של SCP יש גבול תיאורטי. התכנון בוחר בערבות אבטחה חזקה מאוד, מוותרת על הפחתת שרידות קטנה, אבל בהינתן מספיק זמן, יש סבירות גבוהה להגיע להסכמה). בקצרה, הרעיון הוא שיהיו מספר הצבעות פדרציה על מספר ערכים עד שאחד מהם יעבור את כל שלבי ההצבעה של SCP המתוארים להלן.

הערכים עליהם SCP מבקשת הסכמה יכולים להיות היסטוריית עסקאות או הזמנת ארוחת צהריים או משהו אחר, אך חשוב לציין כי אלו אינם הערכים שמתקבלים או מאושרים. במקום זאת, ההצבעה הפדרלית מתרחשת על פי הצהרות על ערכים אלו.

הסיבובים הראשונים של ההצבעה הפדרלית מתקיימים ביום שלב המינוי (שלב המינוי), על קבוצה של הצהרות כמו "אני ממנה V", אולי עבור ערכים רבים ושונים של V. מטרת המינוי היא למצוא הצהרה אחת או יותר שעוברות קבלה ואישור.

לאחר מציאת מועמדים הניתנים לאימות, SCP עוברת לשלב ההצבעה, כאשר המטרה היא למצוא עָלוֹן (כלומר, מיכל לערך המוצע) ומניין שיכול להכריז לְבַצֵעַ בשביל זה (להתחייב). אם מניין מחייב פתק הצבעה, ערכו מתקבל כקונצנזוס. אבל לפני שצומת יוכל להצביע על התחייבות לקלפי, עליו לאשר תחילה ביטול כל פתקי ההצבעה עם ערך נגד נמוך יותר. הצעדים הללו - ביטול פתקי הצבעה כדי למצוא אחד שניתן לבצע - כוללים סבבים מרובים של הצבעה פדרית על תביעות מרובות לקלפי.

הסעיפים הבאים מתארים מועמדות והצבעה ביתר פירוט.

הְתמַנוּת

בתחילת שלב המועמדות, כל צומת יכול לבחור באופן ספונטני ערך ל-V ולהצביע עבור ההצהרה "אני מונה V". המטרה בשלב זה היא לאשר מינוי של ערך כלשהו באמצעות הצבעה פדרציה.

אולי מספיק צמתים מצביעים על הצעות שונות מספיק כדי שאף מועמדות לא תוכל להגיע לסף הקבלה. לכן, בנוסף לשידור הצבעות המועמדות שלהם, צמתים "משקפים" את המועמדויות של עמיתיהם. הד פירושו שאם צומת מצביע עבור מועמדות V, אך רואה הודעה משכן המצביע עבור מועמדות W, הוא יצביע כעת גם עבור V ו-W. (לא כל הצבעות עמיתים מהדהדות במהלך המינוי מכיוון שהדבר עלול להוביל לפיצוץ של מועמדים שונים. SCP כולל מנגנון להסדרת הצבעות אלו. בקיצור, יש נוסחה לקביעת ה"עדיפות" של עמית מנקודת מבט של צומת, ורק ההצבעות של צמתים בעדיפות גבוהה באות לידי ביטוי. ככל שהמינוי ארוך יותר לוקח, ככל שהסף נמוך יותר, כך שהצומת מרחיב את קבוצת עמיתים שאת ההצבעות שלהם הוא ישקף. נוסחת העדיפות כוללת את מספר המשבצת כאחת מהכניסות שלה, כך שעמית בעדיפות גבוהה למשבצת אחת עשויה להיות עמית בעדיפות נמוכה עבור אחר, ולהיפך).

מבחינה קונספטואלית, המינוי מקביל, גם V וגם W הם קולות פדרליים נפרדים, שכל אחד בנפרד מסוגל להשיג קבלה או אישור. בפועל, הודעות פרוטוקול SCP אורזות את ההצבעות האישיות הללו יחד.

למרות שהצבעה בעד המינוי של V היא הבטחה לעולם לא להצביע נגד המינוי של V, ברמת היישום - במקרה זה SCP - נקבע מה המשמעות של "נגד". SCP לא רואה הצהרה שסותרת את הצבעת "אני מזמין X", כלומר, אין הודעת "אני נגד מינוי X", כך שהצומת יכול להצביע כדי למנות ערכים כלשהם. רבים מהמועמדויות הללו לא ילכו לשום מקום, אבל בסופו של דבר הצומת יוכל לקבל או לאשר ערך אחד או יותר. לאחר אישור מועמד, הוא הופך מוּעֲמָד.

מועמדות ל-SCP באמצעות הצבעה מאוחדת. יכולים להיות ערכי "B" רבים שהועלו על ידי עמיתים ו"משתקפים" על ידי הצומת.

מועמדויות עשויות להביא למספר מועמדים מאושרים. לכן, SCP דורש משכבת היישום לספק שיטה כלשהי לשילוב המועמדים לאחד מרוכבים (מרוכבים). שיטת ההצטרפות יכולה להיות כל דבר. העיקר הוא שאם שיטה זו דטרמיניסטית, אז כל צומת ישלב את אותם מועמדים. במערכת הצבעת צהריים, "איחוד" עשוי להיות פשוט דחיית אחד משני מועמדים. (אבל בצורה דטרמיניסטית: כל צומת חייב לבחור את אותו ערך לאיפוס. למשל, הבחירה המוקדמת יותר בסדר אלפביתי). ברשת התשלומים Stellar, שבה מצביעים על היסטוריית העסקאות, מיזוג שני מועמדים מוצעים כרוך במיזוג העסקאות שהם מכילים והאחרון מבין שני חותמות הזמן שלהם.

הספר הלבן של SCP מוכיח (משפט 12) שבסופו של שלב ההרחבה, הרשת בסופו של דבר מתכנסת לרכיב אחד. אבל יש בעיה: הצבעה מאוחדת היא פרוטוקול אסינכרוני (כמו SCP). במילים אחרות, צמתים אינם מתואמים לפי זמן, אלא רק לפי ההודעות שהם שולחים. מנקודת המבט של הצומת, לא ברור מתי הסתיים שלב ההרחבה. ולמרות שכל הצמתים יגיעו בסופו של דבר לאותו רכיב, הם עשויים לקחת מסלולים שונים לאורך הדרך, וליצור מועמדים מרוכבים שונים לאורך הדרך, ולעולם לא יכולים לדעת מי מהם הוא הסופי.

אבל זה נורמלי. מועמדות היא רק הכנה. העיקר הוא להגביל את מספר המועמדים כדי להשיג קונצנזוס, המתרחש בתהליך הצבעה (הצבעה).

רץ

בולטין הוא זוג , כאשר counter הוא מספר שלם שמתחיל ב-1 והערך הוא מועמד משלב המינוי. זה יכול להיות מועמד של צומת עצמו או מועמד של צומת שכן שמתקבל על ידי אותו צומת. באופן גס, קלפי כרוכה בניסיונות חוזרים ונשנים לאלץ את הרשת להגיע לקונצנזוס על מועמד כלשהו בקלפי כלשהו על ידי קיום הצבעות פדרציה רבות על הצהרות בקלפי. מונים בפתקים עוקבים אחר ניסיונות שנעשו, ופתקים בעלי ספירה גבוהה יותר מקבלים עדיפות על פני פתקים עם ספירה נמוכה יותר. אם הניוזלטר נתקע, הצבעה חדשה מתחילה, עכשיו בקלפי .

חשוב להבדיל ערכים (לדוגמה, מה צריכה להיות הזמנת ארוחת הצהריים: פיצה או סלטים), ניוזלטרים (צמד ערך נגדי) ו הצהרות לגבי פתקי הצבעה. סבב ה-SCP כולל מספר סבבי הצבעה פדרליים, במיוחד על ההצהרות הבאות:

"אני מוכן לבצע הצבעה ב'" ו
"אני מכריז על ביצוע הצבעה ב'"

מנקודת מבט של צומת נתון, קונצנזוס מושג כאשר הוא מוצא קלפי ב' שעבורו הוא יכול לאשר (כלומר למצוא מניין שמקבל) את האמירה "אני מתחייב בקלפי ב'". מנקודה זו, בטוח לפעול על פי הערך הנקוב ב-B – למשל, ביצוע הזמנה זו לארוחת צהריים. זה נקרא הַחצָנָה משמעויות. לאחר קבלת אישור ההצבעה, צומת יכול להיות בטוח שכל צומת אחר החצין את אותו הערך או יעשה זאת בעתיד.

למרות שהצבעות פדרליות רבות נערכות מבחינה רעיונית על תביעות עבור פתקי הצבעה רבים ושונים, הן לא מחליפות הודעות רבות מכיוון שכל הודעה מכילה מספר פתקי הצבעה. הודעה אחת מקדמת אפוא את מצבם של קולות פדרציה רבים בבת אחת, למשל: "אני מקבל פתקי הצבעה החל מ לפני "

מה המשמעות של המונחים "מוכן" ו"התחייבות"?

צומת מצביע לביצוע פתק כאשר הוא בטוח שצמתים אחרים לא יבצעו פתקים בעלי ערכים שונים. משכנע שזו מטרת הכנת הבקשה. הצבעה שאומרת "אני מוכן לבצע הצבעה ב'" היא הבטחה לעולם לא לבצע פתק קטן מ-B, כלומר עם ספירה קטנה יותר (SCP דורש שהערכים בקלפי יהיו בסדר מסוים. לפיכך, ניוזלטר פָּחוֹת , אם N1

מדוע "אני מוכן להצביע ב'" פירושו "אני מבטיח לעולם לא לבצע פתקים קטנים מ-B"? כי SCP מגדיר הפלה כהיפך מ-commit. הצבעה להכנת פתק כרוכה גם בהצבעה לפסילת פתקים אחרים, וכפי שדיברנו קודם, הצבעה עבור דבר אחד היא הבטחה לעולם לא להצביע נגדו.

לפני שידור התחייבות, צומת חייב למצוא תחילה עלון שהוא יכול לאשר כמוכן. במילים אחרות, היא מבצעת הצבעה פדרית בנושא "אני מוכן לבצע הצבעה ב'", אולי בפתקי הצבעה רבים ושונים, עד שימצא אחד שמקבל מניין.

מהיכן מגיעים פתקי ההצבעה להכנת ההצבעה? ראשית, הצומת משדר הכנות להצבעה עבור <1,C>, כאשר C הוא המועמד המשולב שהופק בשלב המינוי. עם זאת, גם לאחר תחילת ההכנות להצבעה, מועמדויות עשויות לגרום לכך שמועמדים נוספים ייראו להפוך לפתקים חדשים. בינתיים, לעמיתים יכולים להיות מועמדים שונים והם יכולים ליצור מערך חסימה שמקבל את "אני מוכן לבצע את ההצבעה B2", מה שישכנע את הצומת לקבל גם את זה. לבסוף, ישנו מנגנון פסק זמן שיוצר סבבים חדשים של הצבעה פדרית על פתקים חדשים עם ספירה גבוהה יותר אם הפתקים הנוכחיים תקועים.

ברגע שהצומת מוצא פתק ב' שהוא יכול לאשר כמוכן, הוא משדר הודעה חדשה "תבצע הצבעה ב'". הצבעה זו אומרת לעמיתים שהצומת לעולם לא יוותר על B. למעשה, אם B הוא פתק הצבעה , ואז "תבצע הצבעה "פירושו ההסכמה הבלתי מותנית להצביע בעד המוכנות של כל פתק הצבעה מ אל <∞, s>. ערך נוסף זה עוזר לעמיתים אחרים להדביק את ה-commit peer אם הם עדיין בשלבים מוקדמים יותר של הפרוטוקול.

בשלב זה ראוי להדגיש שוב כי מדובר בפרוטוקולים אסינכרוניים. רק בגלל שצומת אחד שולח קולות בעד התחייבות, לא אומר שגם עמיתיו עושים זאת. ייתכן שחלקם עדיין מצביעים על הצהרות לקראת ההצבעה, ייתכן שאחרים כבר החצינו את המשמעות. SCP מסביר כיצד צומת צריך לעבד כל סוג של הודעת עמית ללא קשר לשלב שלו.

אם ההודעה "הודעתי על התחייבות » לא ניתן לקבל או לאשר, כלומר, ההסתברות שההודעה תתקבל או תאושר אוֹ - או, בכל מקרה, כל פתק עם הערך C, ולא כל פתק אחר, מכיוון שהצומת כבר הבטיח לעולם לא לבטל . עד שצומת ישדר הצבעות עבור התחייבות, זה יהיה C או כלום, תלוי כמה רחוק מגיע הקונצנזוס. עם זאת, זה עדיין לא מספיק כדי שהצומת יחצין את ג'. כמה עמיתים ביזנטיים (המהווים פחות ממניין, בהתבסס על הנחות הביטחון שלנו) עלולים לשקר לצומת. קבלה ולאחר מכן אישור של פתק הצבעה כלשהו (או מגוון פתקי הצבעה) הוא מה שנותן לצומת את הביטחון להחצין סוף סוף את C.

הצבעת SCP באמצעות הצבעה פדרית. לא מוצג: הטיימר עשוי לכבות בכל עת, ולהגדיל את הספירה בפתקי ההצבעה (ואולי לייצר קומפוזיציה חדשה של מועמדים מועמדים נוספים).

וזה הכל! ברגע שהרשת הגיעה לקונצנזוס, היא מוכנה לעשות זאת שוב ושוב. ברשת התשלומים של Stellar, זה קורה בערך אחת ל-5 שניות: הישג שדורש גם אבטחה וגם שרידות המובטחת על ידי SCP.

SCP יכול להשיג זאת על ידי הסתמכות על סבבי הצבעה מרובים. הצבעה מאוחדת מתאפשרת בזכות הרעיון של פרוסות המניין: קבוצות של עמיתים שכל צומת החליט לסמוך עליהם כחלק מהמניין (הסובייקטיבי) שלו. משמעות התצורה הזו היא שניתן להגיע לקונצנזוס גם ברשת עם חברות פתוחה והטעיות ביזנטיות.

לקריאה נוספת

ניתן למצוא את הנייר הלבן המקורי של SCP כאןו - כאן טיוטת מפרט ליישומו.
המחבר המקורי של פרוטוקול SCP, דיוויד מזייר, מסביר זאת בצורה פשוטה (אך עדיין טכנית). כאן.
אולי הופתעת שלא למצוא את המונחים "כרייה" או "הוכחת עבודה" במאמר זה. SCP לא משתמש בשיטות אלה, אבל כמה אלגוריתמים אחרים של קונצנזוס עושים זאת. זיין ווית'רספון כתב נגיש סקירה כללית של אלגוריתמי קונצנזוס.
תיאור שלב אחר שלב רשת פשוטה שמגיעה לקונצנזוס בסבב שלם אחד של SCP.
לקוראים המתעניינים ביישום SCP: ראה קוד C++, בשימוש על ידי רשת התשלומים Stellar, או לך קוד, שכתבתי כדי להבין טוב יותר את SCP.

מקור: www.habr.com

הבנת פרוטוקול הקונצנזוס של כוכבים