Uchangamano Usio na Mpangilio Kutoka kwa Makubaliano ya Takriban: Itifaki Zenye Uvumilivu za Kikatili za Byzantine Zisizo na Muda Sawa

1 Utangulizi

Ubadilishaji nasibu ni zana muhimu katika kubuni mifumo iliyogawanyika. Msingi wa sarafu ya kawaida, unaowazuia wanachama wa mfumo kukubaliana kuhusu nambari isiyotabirika ya nasibu, umeonekana kuwa muhimu sana kwa itifaki kama vile Makubaliano ya Byzantine, Uundaji wa Ufunguo Ulio Gawanyika, na Uchaguzi wa Kiongozi. Hata hivyo, kutekeleza itifaki halisi ya sarafu ya kawaida ya nasibu katika mifumo isiyo na muda na yenye dosari haiwezekani kutokana na matokeo yasiyowezekana ya FLP.

Makala hii inaleta matumizi mawabainifu ya sarafu kamili ya kawaida: (1) sarafu ya kawaida ya takriban inayozalisha nambari za nasibu zilizo karibu kwa kila mmoja, na (2) sarafu ya kawaida ya Monte Carlo inayozalisha nambari ya kawaida ya nasibu yenye uwezekano mdogo wa kushindwa, lakini sio sifuri. Itifaki zetu hujengwa juu ya msingi wa makubaliano ya takriban na huvumilia hadi theluthi moja ya michakato ya Byzantine bila usanidi unaoaminika au miundombinu ya ufunguo wa umma.

2 Usuli na Kazi Inayohusiana

3 Ubunifu wa Itifaki

4 Uchambuzi wa Kiufundi

5 Matokeo ya Majaribio

Tulitathmini itifaki zetu katika mitandao ya kuigwa isiyo na muda na idadi tofauti ya michakato (n = 10 hadi 100) na viwango vya kushindwa vya Byzantine (f < n/3). Matokeo yanaonyesha:

• Muunganiko wa kielelezo kwa makubaliano ndani ya duru 5-10 kwa vigezo vya kawaida
• Utata wa mawasiliano wa O(n³log n) kwa makubaliano ya binary Byzantine
• Uboreshaji mkubwa zaidi ya suluhisho za awali za O(n⁴)

Msimbo ufuatao wa uwongo unaonyesha duru ya msingi ya makubaliano ya takriban:

function ApproximateAgreementRound(value, round):
    broadcast("PROPOSE", value, round)
    received = wait_for_messages(n - f, round)
    valid_values = filter_within_range(received, value - ε, value + ε)
    new_value = median(valid_values)  // or average for continuous domains
    return new_value

6 Maelezo ya Utekelezaji

Utekelezaji wetu hutumia misingi ya kawaida ya kriptografia ikiwemo kazi za hash na saini za kidijitali. Muundo wa msingi wa algorithm:

class MonteCarloCommonCoin:
    def __init__(self, n, f, delta):
        self.n = n  # jumla ya michakato
        self.f = f  # kushindwa kwa kiwango cha juu cha Byzantine
        self.delta = delta  # uwezekano wa kushindwa
        self.round = 0
        
    def generate_coin(self):
        while True:
            self.round += 1
            estimate = self.approximate_agreement_round()
            if self.consensus_achieved(estimate):
                return self.finalize_output(estimate)
            if self.round > self.required_rounds():
                return self.fallback_output()

7 Matumizi na Mwelekeo wa Baadaye

Matumizi ya Sasa:

• Makubaliano ya Byzantine na utata wa mawasiliano wa O(n³log n)
• Tatizo la Vipindi Vya Nasibu Vinavyokatika kwa kutumia sarafu ya kawaida ya takriban na msimbo wa Gray
• Uchaguzi wa kiongozi katika mifumo ya blockchain isiyo na ruhusa

Mwelekeo wa Utafiti wa Baadaye:

• Kubadilisha itifaki kwa kriptografia isiyoathiriwa na kompyuta za quanta
• Kupanua kwa mipangilio ya uanachishi inayobadilika
• Kuboresha kwa hali halisi za mtandao zenye mshikamano wa sehemu
• Unganisho na usanifu wa blockchain uliogawanyika

8 Marejeo

1. Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM.
2. Rabin, M. O. (1983). Randomized Byzantine generals. Symposium on Foundations of Computer Science.
3. Cachin, C., Kursawe, K., & Shoup, V. (2000). Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography. PODC.
4. Miller, A., Xia, Y., Croman, K., Shi, E., & Song, D. (2016). The honey badger of BFT protocols. CCS.
5. Abraham, I., Malkhi, D., & Spiegelman, A. (2019). Asymptotically optimal validated asynchronous Byzantine agreement. PODC.