Хэрэв бид бие биедээ итгэхгүй бол санамсаргүй тоо үүсгэх боломжтой юу? 2-р хэсэг

Хөөе Хабр!

В эхний хэсэг Энэ нийтлэлд бид бие биедээ итгэдэггүй оролцогчдод яагаад санамсаргүй тоо үүсгэх шаардлагатай байж болох, ийм санамсаргүй тоо үүсгэгчдэд ямар шаардлага тавьдаг талаар ярилцаж, тэдгээрийг хэрэгжүүлэх хоёр аргыг авч үзсэн.

Өгүүллийн энэ хэсэгт бид босго гарын үсгийг ашигладаг өөр аргыг нарийвчлан авч үзэх болно.

Бага зэрэг криптограф

Босго гарын үсэг хэрхэн ажилладагийг ойлгохын тулд бага зэрэг үндсэн криптографийг ойлгох хэрэгтэй. Бид хоёр ойлголтыг ашиглах болно: скаляр эсвэл энгийн тоо, бид үүнийг жижиг үсгээр тэмдэглэнэ (х, у) ба зууван муруй дээрх цэгүүдийг бид том үсгээр тэмдэглэнэ.

Босгоны гарын үсгийн үндсийг ойлгохын тулд хэд хэдэн үндсэн зүйлээс бусад тохиолдолд зууван муруй хэрхэн ажилладагийг ойлгох шаардлагагүй:

1. Зууван муруй дээрх цэгүүдийг нэмж, скаляраар үржүүлж болно (бид скаляраар үржүүлэхийг дараах байдлаар тэмдэглэнэ. xG, хэдийгээр тэмдэглэгээ Gx Мөн уран зохиолд ихэвчлэн ашиглагддаг). Скаляраар нэмэх ба үржүүлэх үр дүн нь эллипс муруй дээрх цэг юм.

2. Зөвхөн санааг нь мэддэг G ба түүний бүтээгдэхүүн нь скаляр xG тооцох боломжгүй x.

Мөн бид олон гишүүнтийн тухай ойлголтыг ашиглах болно p(x) зэрэг k-1. Ялангуяа олон гишүүнтийн дараах шинж чанарыг ашиглах болно: хэрэв бид утгыг мэдэж байвал p(x) ямар ч хувьд k өөр өөр x (мөн бидэнд өөр мэдээлэл алга p(x)), бид тооцоолж болно p(x) өөр хэний ч төлөө x.

Аливаа олон гишүүнтийн хувьд энэ нь сонирхолтой юм p(x) мөн муруй дээрх зарим цэг Gутгыг мэдэх p(x)G ямар ч хувьд k өөр өөр утгатай x, бид бас тооцоолж болно p(x)G ямар ч хувьд x.

Энэ нь босго гарын үсэг хэрхэн ажилладаг, тэдгээрийг санамсаргүй тоо үүсгэхэд хэрхэн ашиглах талаар нарийвчлан судлахад хангалттай мэдээлэл юм.

Босго гарын үсэг дээр санамсаргүй тоо үүсгэгч

Ингэж хэлье n оролцогчид санамсаргүй тоо үүсгэхийг хүсч байгаа бөгөөд бид хэн ч оролцохыг хүсч байна k тоо бий болгохын тулд тэдний хангалттай байсан, харин хянаж байгаа халдагчдыг тийм k-1 буюу түүнээс цөөн тооны оролцогчид бий болсон тоог урьдчилан таамаглах эсвэл нөлөөлж чадахгүй.

Ийм олон гишүүн байна гэж бодъё p(x) зэрэг k-1 эхний оролцогч юу мэддэг p (1), хоёр дахь нь мэднэ p(2), гэх мэт (n-Мэднэ p(n)). Урьдчилан тодорхойлсон цэгийн хувьд бид үүнийг бас таамаглаж байна G хүн бүр мэддэг p(x)G бүх үнэт зүйлсийн хувьд x. Бид залгах болно p(i) "хувийн бүрэлдэхүүн хэсэг" iоролцогч (зөвхөн iОролцогч түүнийг таньдаг), мөн p(i)G "нийтийн бүрэлдэхүүн хэсэг" i-р оролцогч (бүх оролцогчид түүнийг мэддэг учраас). Таны санаж байгаагаар мэдлэг p(i)G сэргээхэд хангалтгүй p(i).

Ийм олон гишүүнт үүсгэх нь зөвхөн i-Эхний оролцогч, өөр хэн ч түүний хувийн бүрэлдэхүүн хэсгийг мэддэггүй - энэ бол протоколын хамгийн төвөгтэй, сонирхолтой хэсэг бөгөөд бид үүнийг доор шинжлэх болно. Одоогоор бидэнд ийм олон гишүүнт байгаа бөгөөд бүх оролцогчид өөрсдийн хувийн бүрэлдэхүүн хэсгүүдийг мэддэг гэж бодъё.

Бид санамсаргүй тоо үүсгэхийн тулд ийм олон гишүүнтийг хэрхэн ашиглах вэ? Эхлэхийн тулд бидэнд генераторын оролт болгон ашиглагдаагүй мөр хэрэгтэй. Блокчейн хувьд сүүлийн блокийн хэш h ийм шугаманд сайн нэр дэвшигч юм. Оролцогчдыг ашиглан санамсаргүй тоо үүсгэхийг хүснэ үү h үр шиг. Оролцогчид эхлээд хөрвүүлдэг h Урьдчилан тодорхойлсон функцийг ашиглан муруй дээрх цэг рүү:

H = scalarToPoint(h)

Дараа нь оролцогч бүр i тооцоолж нийтэлдэг Сайн байна уу = p(i)H, мэдэж байгаа болохоор юу хийж чадах юм p(i) ба H. Ил тод болгох HБи бусад оролцогчдод хувийн бүрэлдэхүүн хэсгийг сэргээхийг зөвшөөрөхгүй ith оролцогч, тиймээс нэг багц хувийн бүрэлдэхүүн хэсгүүдийг блокоос блок руу ашиглаж болно. Тиймээс доор тайлбарласан үнэтэй олон гишүүнт үүсгэх алгоритмыг зөвхөн нэг удаа гүйцэтгэх шаардлагатай.

Хэзээ k оролцогчдод задлан шинжилгээ хийсэн Сайн байна уу = p(i)H, хүн бүр тооцоолж чадна Hx = p(x)H бүгдэд нь x Сүүлийн хэсэгт авч үзсэн олон гишүүнтүүдийн өмчийн ачаар. Энэ мөчид бүх оролцогчид тооцоолж байна H0 = p(0)H, бөгөөд энэ нь үр дүнд нь санамсаргүй тоо юм. Хэн ч мэдэхгүй гэдгийг анхаарна уу p(0), тиймээс тооцоолох цорын ганц арга зам юм p(0)H - энэ бол интерполяци юм p(x)H, Энэ нь зөвхөн үед л боломжтой юм k үнэт зүйлс p(i)H мэдэгдэж байна. Илүү бага хэмжээгээр нээх p(i)H талаар ямар ч мэдээлэл өгөхгүй байна p(0)H.

Дээрх генератор нь бидний хүссэн бүх шинж чанартай: зөвхөн халдагчид удирддаг k-1 буюу түүнээс бага оролцогч нь дүгнэлтэд ямар ч мэдээлэл, нөлөө үзүүлэхгүй k оролцогчид үр дүнгийн тоо болон ямар ч дэд багцыг тооцоолж болно k оролцогчид нэг үрийн хувьд үргэлж ижил үр дүнд хүрнэ.

Бидний дээр дурдсан болгоомжтойгоор зайлсхийсэн нэг асуудал бий. Интерполяци ажиллахын тулд утга нь чухал юм HОролцогч бүрийн нийтэлсэн i i үнэхээр адилхан байсан p(i)H. Учир нь өөр хэн ч биш i-Оролцогч мэдэхгүй байна p(i), өөр хэн ч биш i-Оролцогч үүнийг баталгаажуулж чадахгүй Hi Үнэн хэрэгтээ зөв тооцоолсон бөгөөд ямар ч криптографийн нотолгоогүйгээр HБи халдагчид дурын утгыг нийтлэх боломжтой Сайн байна уу, санамсаргүй тоо үүсгэгчийн гаралтад дур мэдэн нөлөөлөх:

Эхний оролцогчийн илгээсэн H_1-ийн өөр утгууд нь өөр H_0 үр дүнд хүргэдэг

Зөв гэдгийг батлах дор хаяж хоёр арга бий Hi, бид олон гишүүнт үүсэхэд дүн шинжилгээ хийсний дараа тэдгээрийг авч үзэх болно.

Олон гишүүнт үүсэх

Сүүлийн хэсэгт бид ийм олон гишүүнттэй гэж үзсэн p(x) зэрэг k-1 оролцогч i мэдэж байгаа p(i), мөн өөр хэн ч энэ утгын талаар ямар ч мэдээлэлгүй байна. Дараагийн хэсэгт энэ нь урьдчилан тодорхойлсон цэгийн хувьд бидэнд хэрэгтэй болно G бүгд мэдэж байсан p(x)G бүгдэд нь x.

Энэ хэсэгт бид оролцогч бүр орон нутгийн хувийн түлхүүртэй гэж үзэх болно xi, Ингэснээр хүн бүр холбогдох нийтийн түлхүүрийг мэддэг Xi.

Олон гишүүнт үүсгэх боломжтой нэг протокол дараах байдалтай байна.

1. Оролцогч бүр i орон нутагт дурын олон гишүүнт үүсгэдэг pi(x) зэрэг k-1. Дараа нь тэд оролцогч бүрийг илгээдэг j утга pi(j), нийтийн түлхүүрээр шифрлэгдсэн Xj. Зөвхөн ийм байдлаар i-р и j-р оролцогч мэднэ pi(j). Оролцогч i мөн олон нийтэд зарладаг pi(j)G бүгдэд нь j нь 1 нь k багтаасан.

2. Бүх оролцогчид зөвшилцөлд тулгуурлан сонголтоо хийдэг k олон гишүүнтийг ашиглах оролцогчид. Зарим оролцогчид офлайн байж болзошгүй тул бид бүгд хүлээж чадахгүй n оролцогчид олон гишүүнтийг нийтлэх болно. Энэ алхамын үр дүн нь багц юм Z наад зах нь бүрдэнэ k (1) алхамд үүсгэсэн олон гишүүнтүүд.

3. Оролцогчид өөрсдийн мэддэг үнэт зүйлсээ баталгаажуулдаг pi(j) олон нийтэд зарласантай тохирч байна pi(j)G. Энэ алхамын дараа Z зөвхөн хувийн дамжуулсан олон гишүүнт pi(j) олон нийтэд зарласантай тохирч байна pi(j)G.

4. Оролцогч бүр j түүний хувийн бүрэлдэхүүн хэсгийг тооцоолно p(j) нийлбэр байдлаар pi(j) бүгдэд нь i в Z. Оролцогч бүр бүх утгыг тооцдог p(x)G нийлбэр байдлаар бүх i-д зориулсан pi(x)G в Z.

тэрийг тэмдэглэ p(x) - энэ бол үнэхээр олон гишүүнт юм k-1, Учир нь энэ нь хувь хүний ​​нийлбэр юм pi(x), тус бүр нь градусын олон гишүүнт юм k-1. Дараа нь оролцогч бүрийг байх хугацаандаа гэдгийг анхаарна уу j мэдэж байгаа p(j), талаар тэдэнд ямар ч мэдээлэл байхгүй p(x) нь x ≠ j. Үнэн хэрэгтээ энэ утгыг тооцоолохын тулд тэд бүгдийг мэддэг байх ёстой pi(x), мөн оролцогчийн хувьд j Сонгогдсон олон гишүүнтүүдийн ядаж нэгийг нь мэддэггүй, тэдэнд хангалттай мэдээлэл байхгүй p(x).

Энэ бол сүүлийн хэсэгт шаардлагатай олон гишүүнт үүсгэх процесс юм. Дээрх 1, 2, 4-р алхмууд нь нэлээд тодорхой хэрэгжилттэй байна. Гэхдээ 3-р алхам нь тийм ч энгийн зүйл биш юм.

Тодруулбал, бид үүнийг шифрлэсэн гэдгийг батлах чадвартай байх ёстой pi(j) нийтлэгдсэнтэй үнэхээр таарч байна pi(j)G. Хэрэв бид үүнийг баталж чадахгүй бол халдагч i оронд нь хог илгээж болно pi(j) оролцогчид j, болон оролцогч j жинхэнэ утгыг нь олж авч чадахгүй pi(j), мөн түүний хувийн бүрэлдэхүүн хэсгийг тооцоолох боломжгүй болно.

Нэмэлт мессеж үүсгэх боломжийг олгодог криптографийн протокол байдаг нотолгооi(j), ямар ч оролцогч ямар нэг үнэ цэнтэй байхаар e, а также баталгаа(j) и pi(j)G, үүнийг дотооддоо баталгаажуулж чадна e - энэ үнэхээр pi(j), оролцогчийн түлхүүрээр шифрлэгдсэн j. Харамсалтай нь ийм нотлох баримтын хэмжээ үнэхээр том бөгөөд үүнийг нийтлэх шаардлагатай байна. О(nk) Ийм нотлох баримтыг энэ зорилгоор ашиглах боломжгүй.

Үүнийг батлахын оронд пи(ж) харгалзана pi(j)G бид олон гишүүнт үүсгэх протоколд маш том хугацааг хуваарилж болох бөгөөд энэ хугацаанд бүх оролцогчид хүлээн авсан шифрлэгдсэн мэдээллийг шалгадаг. pi(j), мөн шифрлэгдсэн мессеж нь олон нийтэд тохирохгүй байвал pi(j)G, тэд хүлээн авсан шифрлэгдсэн мессеж буруу болохыг криптографийн нотолгоог нийтэлдэг. Зурвас гэдгийг нотлох үгүй харгалзана пи(G) таарч байгааг нотлохоос хамаагүй амархан. Энэ нь оролцогч бүр ийм нотлох баримт үүсгэхийн тулд дор хаяж нэг удаа онлайн байх шаардлагатай гэдгийг тэмдэглэх нь зүйтэй бөгөөд хэрэв тэд ийм нотлох баримтыг нийтлэх юм бол бусад бүх оролцогчдод ижил хугацаанд хүрнэ гэсэн таамаглал дээр тулгуурладаг.

Хэрэв оролцогч энэ хугацаанд онлайнаар гарч ирээгүй бөгөөд тэр дор хаяж нэг буруу бүрэлдэхүүн хэсэгтэй байсан бол тухайн оролцогч дараагийн дугаар үүсгэхэд оролцох боломжгүй болно. Гэсэн хэдий ч хэрэв дор хаяж байгаа бол протокол ажиллах болно k Зөвхөн зөв бүрэлдэхүүн хэсгүүдийг хүлээн авсан эсвэл заасан хугацаанд буруугийн нотолгоог үлдээж чадсан оролцогчид.

H_i-ийн зөв байдлын баталгаа

Хэлэлцэх үлдсэн сүүлчийн хэсэг бол хэвлэгдсэн мэдээллийн үнэн зөвийг хэрхэн батлах тухай юм Hби, тухайлбал тэр Сайн байна уу = p(i)H, нээхгүйгээр p(i).

Үнэт зүйл гэдгийг санаарай H, G, p(i)G олон нийтийн болон хүн бүрт мэдэгддэг. Үйлдлийг хүлээн авах p(i) мэдэх p(i)G и G дискрет логарифм гэж нэрлэдэг, эсвэл dlog, мөн бид үүнийг батлахыг хүсч байна:

dlog(p(i)G, G) = dlog(Hi, H)

задлахгүйгээр p(i). Жишээлбэл, ийм нотлох баримтууд байдаг Schnorr протокол.

Энэ загвараар оролцогч бүр, хамт Hi загварын дагуу зөв эсэхийг нотлох баримтыг илгээдэг.

Санамсаргүй тоог үүсгэсний дараа түүнийг үүсгэсэн хүмүүсээс бусад оролцогчид ашиглах шаардлагатай болдог. Ийм оролцогчид дугаарын хамт бүгдийг нь илгээх ёстой Hi болон холбогдох нотлох баримтууд.

Сонирхолтой уншигч асууж магадгүй: учир нь эцсийн санамсаргүй тоо H0, ба p(0)G - Энэ бол олон нийтийн мэдээлэл, яагаад бидэнд хувь хүн бүрт нотлох баримт хэрэгтэй байна вэ? HБи, үүний оронд яагаад нотлох баримтыг илгээж болохгүй гэж

dlog(p(0)G, G) = dlog(H0, H)

Асуудал нь хэн ч үнэ цэнийг мэддэггүй тул Schnorr протоколыг ашиглан ийм нотолгоо үүсгэх боломжгүй юм p (0), нотлох баримтыг бий болгоход зайлшгүй шаардлагатай бөгөөд үүнээс гадна санамсаргүй тоо үүсгэгч бүхэлдээ энэ утгыг хэн ч мэдэхгүй гэсэн баримт дээр суурилдаг. Тиймээс бүх үнэт зүйлтэй байх шаардлагатай Hi мөн тэдний үнэн зөвийг нотлох бие даасан нотолгоо H0.

Гэсэн хэдий ч, зууван муруй дээрх цэгүүд дээр үржүүлэхтэй утгын хувьд төстэй үйл ажиллагаа байсан бол зөвийг батлах баталгаа болно. H0 өчүүхэн зүйл байх болно, бид зүгээр л үүнийг батлах болно

H0 × хэмжээтэй G = p(0)G × H

Сонгосон муруйг дэмжсэн бол зууван муруй хосолсон, энэ нотолгоо ажилладаг. Энэ тохиолдолд H0 гэдэг нь зөвхөн санамсаргүй тоо үүсгэгчийн гаралт биш бөгөөд үүнийг мэддэг ямар ч оролцогч шалгаж болно Г, Х и p(0)G. Х0 гэдэг нь мөн үр болгон ашиглаж байсан мессеж дээрх гарын үсэг бөгөөд үүнийг баталж байна k и n оролцогчид энэ зурваст гарын үсэг зурав. Тиймээс, хэрэв үр - нь блокчейн протокол дахь блокийн хэш юм, тэгвэл H0 аль аль нь блок дээрх олон гарын үсэг, маш сайн санамсаргүй тоо юм.

Эцэст нь хэлэхэд

Энэ нийтлэл нь техникийн цуврал блогийн нэг хэсэг юм НЭГ. NEAR нь төвлөрсөн бус программуудыг хөгжүүлэхэд зориулагдсан блокчейн протокол ба платформ бөгөөд эцсийн хэрэглэгчдэд хялбар хөгжүүлэлт, ашиглахад хялбар байдлыг чухалчилдаг.

Протоколын код нь нээлттэй, бидний хэрэгжилт Rust дээр бичигдсэн, үүнийг олж болно энд.

Та NEAR-д зориулсан хөгжүүлэлт ямар байгааг харж, онлайн IDE дээр туршиж үзэх боломжтой энд.

Та бүх мэдээг орос хэл дээр үзэх боломжтой телеграм групп болон дотор ВКонтакте дахь бүлэг, албан ёсны англи хэл дээр twitter.

Удахгүй уулзацгаая!

Эх сурвалж: www.habr.com