Эй Хабр!
В Бул макалада биз бири-бирине ишенбеген катышуучулар үчүн кокус сандарды түзүү эмне үчүн зарыл болушу мүмкүн экенин, мындай кокус сандар генераторлоруна кандай талаптар коюларын талкууладык жана аларды ишке ашыруунун эки ыкмасын карап чыктык.
Макаланын бул бөлүгүндө биз босого кол тамгаларды колдонгон дагы бир ыкманы кененирээк карап чыгабыз.
Бир аз криптография
Босого кол тамгалар кантип иштээрин түшүнүү үчүн, сиз бир аз негизги криптографияны түшүнүшүңүз керек. Биз эки түшүнүктү колдонобуз: скалярлар же жөн эле сандар, аларды кичине тамгалар менен белгилейбиз (х, ж) жана эллиптикалык ийри сызыктагы чекиттерди биз баш тамгалар менен белгилейбиз.
Босого кол тамгалардын негиздерин түшүнүү үчүн, бир нече негизги нерселерден башка эллиптикалык ийри сызыктар кантип иштээрин түшүнүүнүн кереги жок:
-
Эллиптикалык ийри сызыктагы чекиттерди скалярга кошууга жана көбөйтүүгө болот (биз скалярга көбөйтүүнү төмөнкүдөй белгилейбиз) xG, белги болсо да Gx адабиятта да көп колдонулат). Скалярга кошуунун жана көбөйтүүнүн натыйжасы эллиптикалык ийри сызыктагы чекит болуп саналат.
-
Кепти гана билип 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 биринчи катышуучу эмнени билет б (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 эсептеп чыгарат жана жарыялайт Hi = p(i)H, алар эмне кыла алышат, анткени алар билишет p(i) жана H. Ачыкка чыгаруу Hi башка катышуучуларга жеке компонентти калыбына келтирүүгө уруксат бербейм ith катышуучусу, ошондуктан жеке компоненттердин бир топтомун блоктон блокко колдонсо болот. Ошентип, төмөндө сүрөттөлгөн кымбат баалуу полиномдук генерация алгоритми бир гана жолу аткарылышы керек.
качан k катышуучулар экспертизадан өткөрүлдү Hi = 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 чындыгында туура эсептелген жана эч кандай криптографиялык далилсиз Hi чабуулчу каалаган маанини жарыялай алат Салам, жана кокус сандар генераторунун чыгышына ээнбаштык менен таасир этет:
Биринчи катышуучу жөнөткөн H_1 ар кандай маанилери ар кандай натыйжадагы H_0 алып келет
Тууралыгын далилдөөнүн жок дегенде эки жолу бар Hi, биз аларды көп мүчөнүн мууну анализдегенден кийин карап чыгабыз.
Полиномдук муун
Акыркы бөлүмдө биз ушундай көп мүчө бар деп ойлогонбуз p(x) даража k-1 ошол катышуучу i билет p(i), жана башка эч кимде бул баалуулук жөнүндө эч кандай маалымат жок. Кийинки бөлүмдө бизге алдын ала белгиленген пункт үчүн да керек болот G баары билчү p(x)G баары үчүн x.
Бул бөлүмдө биз жергиликтүү ар бир катышуучунун жеке ачкычы бар деп ойлойбуз xi, ар бир адам тиешелүү ачык ачкычты билет Xi.
Мүмкүн болгон полиномдук генерация протоколу төмөнкүдөй:
-
Ар бир катышуучу i локалдуу түрдө ыктыярдуу көп мүчөнү түзөт pi(x) даражасы k-1. Андан кийин алар ар бир катышуучуну жөнөтүшөт j маани pi(j), ачык ачкыч менен шифрленген Xj. Ошентип гана i-чи и j-чи катышуучу билет pi(j). Катышуучу i ошондой эле коомчулукка жарыялайт pi(j)G баары үчүн j от 1 үчүн k кошо алганда.
-
Бардык катышуучулар тандоо үчүн кандайдыр бир консенсус колдонушат k көп мүчөлөр колдонула турган катышуучулар. Кээ бир катышуучулар оффлайнда болушу мүмкүн болгондуктан, биз бардыгын күтө албайбыз n катышуучулар полиномдорду жарыялайт. Бул кадамдын натыйжасы топтому болуп саналат Z жок дегенде турат k (1) кадамда түзүлгөн көп мүчөлөр.
-
Катышуучулар алар билген баалуулуктарды текшерет pi(j) ачык жарыяланганга туура келет pi(j)G. Бул кадамдан кийин Z жеке берилген көп мүчөлөр гана pi(j) ачык жарыяланганга туура келет pi(j)G.
-
Ар бир катышуучу j анын жеке компонентин эсептейт p(j) сумма катары pi(j) бардыгы үчүн i в Z. Ар бир катышуучу бардык баалуулуктарды эсептейт p(x)G сумма катары pi(x)G бардыгы үчүн i в 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, а также proofi(j) и pi(j)G, муну жергиликтүү түрдө текшере алат e - чын эле pi(j), катышуучунун ачкычы менен шифрленген j. Тилекке каршы, мындай далилдердин көлөмү укмуштуудай чоң жана аны жарыялоо зарыл экендигин эске алганда О(nk) Мындай далилдер бул максатта колдонулушу мүмкүн эмес.
Муну далилдегендин ордуна пи(ж) туура келет pi(j)G биз полиномдук генерациялоо протоколунда өтө узак убакытты бөлө алабыз, анын жүрүшүндө бардык катышуучулар алынган шифрленген маалыматтарды текшеришет. pi(j), жана эгер дешифрленген билдирүү коомчулукка туура келбесе pi(j)G, алар кабыл алган шифрленген билдирүүнүн туура эмес экендигинин криптографиялык далилин жарыялашат. Билдирүү экенин далилде жок туура келет пи(G) дал келгендигин далилдөөдөн алда канча жеңил. Белгилей кетчү нерсе, бул ар бир катышуучудан мындай далилдерди түзүү үчүн бөлүнгөн убакыттын ичинде жок дегенде бир жолу онлайн режиминде болушун талап кылат жана эгерде алар мындай далилди жарыяласа, ал ошол эле бөлүнгөн убакыттын ичинде бардык башка катышуучуларга жетет деген божомолго таянат.
Эгер катышуучу бул убакыттын ичинде онлайнга чыкпаса жана анын жок дегенде бир туура эмес компоненти болсо, анда ал катышуучу кийинки сандарды түзүүгө катыша албайт. Протокол, бирок, жок дегенде, эгерде бар болсо дагы иштей берет k туура компоненттерди жаңы эле алган же берилген убакыттын ичинде туура эместигин далилдеген катышуучулар.
H_i тууралыгынын далилдери
Жарыялангандардын тууралыгын кантип далилдөө керектиги талкуулана турган акыркы бөлүк Hмен, тактап айтканда Hi = 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). Мындай далилдер үчүн курулуштар, мисалы, бар.
Бул дизайн менен, ар бир катышуучу менен бирге Hi долбоорго ылайык тууралыгынын далилин жиберет.
Кокус сан түзүлгөндөн кийин, аны көбүнчө аны түзгөндөрдөн башка катышуучулар колдонушу керек. Мындай катышуучулар номери менен бирге баарын жөнөтүшү керек Hi жана ага байланыштуу далилдер.
Кызыккан окурман сурашы мүмкүн: акыркы кокустук сан болгондуктан H0, жана p(0)G - Бул ачык маалымат, эмне үчүн бизге ар бир инсанга далил керек Hi, эмне үчүн анын ордуна далилди жөнөтүүгө болбойт
dlog(p(0)G, G) = dlog(H0, H)
Маселе мындай далилди Шнорр протоколун колдонуу менен түзүү мүмкүн эмес, анткени эч ким баасын билбейт б (0), далилди түзүү үчүн зарыл, жана андан тышкары, бүт кокустук сан генератору бул маанини эч ким билбегендигине негизделген. Ошондуктан бардык баалуулуктарга ээ болуу зарыл Hi жана тууралыгын далилдөө үчүн алардын жеке далилдери H0.
Бирок, эллиптикалык ийри сызыктардагы чекиттерге семантикалык жактан көбөйтүүгө окшош операция болгон болсо, анда тууралыктын далили H0 маанисиз болмок, биз жөн гана ишенебиз
H0 × G = p(0)G × H
Тандалган ийри сызык колдосо , бул далил иштейт. Бул учурда H0 кокустук сандар генераторунун гана чыгарылышы эмес, аны каалаган катышуучу текшере алат Г, Х и p(0)G. Х0 да урук катары колдонулган билдирүүгө кол коюлган, ошону тастыктап турат k и n катышуучулар бул билдирүүгө кол коюшту. Ошентип, эгерде үрөн - анда блокчейн протоколундагы блоктун хэши болуп саналат H0 блоктогу көп кол тамга жана абдан жакшы кокустук сан да.
Жыйынтык
Бул макала техникалык блог сериясынын бир бөлүгү болуп саналат . NEAR - бул блокчейн протоколу жана борбордон ажыратылган тиркемелерди иштеп чыгуу үчүн платформа, иштеп чыгуунун оңойлугуна жана акыркы колдонуучулар үчүн колдонуунун оңойлугуна басым жасайт.
Протоколдун коду ачык, биздин ишке ашыруу Rust менен жазылган, аны тапса болот .
Сиз онлайн IDEде NEAR үчүн кандай иштеп чыгууну жана экспериментти көрө аласыз .
Бардык жаңылыктарды орус тилинде төмөнкү сайттан көрө аласыз жана , жана англис тилинде расмий түрдө .
Жакында көрүшкөнчө!
Source: www.habr.com