Hei Habr!
В Yn yr erthygl hon, buom yn trafod pam y gallai fod angen cynhyrchu rhifau ar hap ar gyfer cyfranogwyr nad ydynt yn ymddiried yn ei gilydd, pa ofynion a gyflwynir ar gyfer generaduron rhif ar hap o'r fath, ac ystyriom ddau ddull o'u gweithredu.
Yn y rhan hon o'r erthygl, byddwn yn edrych yn agosach ar ddull arall sy'n defnyddio llofnodion trothwy.
Ychydig o cryptograffeg
Er mwyn deall sut mae llofnodion trothwy yn gweithio, mae angen i chi ddeall ychydig o cryptograffeg sylfaenol. Byddwn yn defnyddio dau gysyniad: sgalar, neu rifau yn unig, y byddwn yn eu dynodi â llythrennau bach (x, y) a phwyntiau ar y gromlin eliptig, y byddwn yn eu dynodi â phrif lythrennau.
I ddeall hanfodion llofnodion trothwy, nid oes angen i chi ddeall sut mae cromliniau eliptig yn gweithio, ac eithrio ychydig o bethau sylfaenol:
-
Gellir ychwanegu pwyntiau ar gromlin eliptig a'u lluosi â sgalar (byddwn yn dynodi lluosi â sgalar fel xG, er bod y nodiant Gx a ddefnyddir yn aml hefyd yn y llenyddiaeth). Canlyniad adio a lluosi â sgalar yw pwynt ar gromlin eliptig.
-
Gwybod y pwynt yn unig G a'i gynnyrch â sgalar xG ni ellir ei gyfrifo x.
Byddwn hefyd yn defnyddio'r cysyniad o polynomial p (x) graddau k-1. Yn benodol, byddwn yn defnyddio priodweddau polynomialau canlynol: os ydym yn gwybod y gwerth p (x) ar gyfer unrhyw k gwahanol x (ac nid oes gennym ragor o wybodaeth am p (x)), gallwn gyfrifo p (x) i unrhyw un arall x.
Mae'n ddiddorol bod ar gyfer unrhyw polynomial p (x) a rhyw bwynt ar y gromlin Ggwybod yr ystyr p(x)G ar gyfer unrhyw k gwahanol ystyron x, gallwn hefyd gyfrifo p(x)G ar gyfer unrhyw x.
Mae hyn yn ddigon o wybodaeth i gloddio i mewn i fanylion sut mae llofnodion trothwy'n gweithio a sut i'w defnyddio i gynhyrchu rhifau ar hap.
Cynhyrchydd rhif ar hap ar lofnodion trothwy
Gadewch i ni ddweud hynny n mae cyfranogwyr eisiau cynhyrchu rhif ar hap, ac rydym am i unrhyw un gymryd rhan k roedd digon ohonyn nhw i gynhyrchu nifer, ond fel bod yr ymosodwyr sy'n rheoli k-1 neu lai o gyfranogwyr ddim yn gallu rhagweld na dylanwadu ar y nifer a gynhyrchir.
Tybiwch fod yna polynomial o'r fath p (x) graddau k-1 beth mae'r cyfranogwr cyntaf yn ei wybod p (1), mae'r ail yn gwybod p(2), ac yn y blaen (n-th yn gwybod p(n)). Rydym hefyd yn tybio hynny ar gyfer rhyw bwynt a bennwyd ymlaen llaw G mae pawb yn gwybod p(x)G ar gyfer pob gwerth x. Byddwn yn galw p(i) “elfen breifat” ifed cyfranogwr (oherwydd yn unig imae'r fed cyfranogwr yn ei hadnabod), a p(i)G “elfen gyhoeddus” i-fed cyfranogwr (oherwydd bod yr holl gyfranogwyr yn ei hadnabod). Fel y cofiwch, gwybodaeth p(i)G dim digon i'w adfer p(i).
Creu polynomial o'r fath fel mai dim ond i-Roedd y cyfranogwr cyntaf a neb arall yn gwybod ei gydran breifat - dyma'r rhan fwyaf cymhleth a diddorol o'r protocol, a byddwn yn ei ddadansoddi isod. Am y tro, gadewch i ni dybio bod gennym ni polynomial o'r fath a bod yr holl gyfranogwyr yn gwybod eu cydrannau preifat.
Sut gallwn ni ddefnyddio polynomial o'r fath i gynhyrchu rhif ar hap? I ddechrau, mae angen rhywfaint o linyn arnom nad yw wedi'i ddefnyddio o'r blaen fel mewnbwn i'r generadur. Yn achos blockchain, hash y bloc olaf h yn ymgeisydd da ar gyfer llinell o'r fath. Gadewch i gyfranogwyr fod eisiau creu rhif ar hap gan ddefnyddio h fel had. Mae cyfranogwyr yn trosi gyntaf h i bwynt ar y gromlin gan ddefnyddio unrhyw swyddogaeth a ddiffiniwyd ymlaen llaw:
H = sgalarToPoint(h)
Yna pob cyfranogwr i yn cyfrifo ac yn cyhoeddi Helo = p(i)H, beth allant ei wneud oherwydd eu bod yn gwybod p(i) a H. Datgeliad Hi nid yw'n caniatáu i gyfranogwyr eraill adfer y gydran breifat ifed cyfranogwr, ac felly gellir defnyddio un set o gydrannau preifat o floc i floc. Felly, dim ond unwaith y mae angen gweithredu'r algorithm cynhyrchu polynomaidd drud a ddisgrifir isod.
Pan fydd k cafodd y cyfranogwyr eu awtopsi Helo = p(i)H, gall pawb gyfrifo Hx = p(x)H i bawb x diolch i eiddo polynomialau a drafodwyd gennym yn yr adran ddiwethaf. Ar hyn o bryd, mae'r holl gyfranogwyr yn cyfrifo H0 = p(0)H, a dyma'r haprif canlyniadol. Sylwch nad oes neb yn gwybod p(0), ac felly yr unig ffordd i gyfrifo p(0)H – rhyngosod yw hwn p(x)H, sydd ond yn bosibl pan k gwerthoedd p(i)H hysbys. Agor unrhyw swm llai p(i)H ddim yn darparu unrhyw wybodaeth am p(0)H.
Mae gan y generadur uchod yr holl briodweddau yr ydym eu heisiau: ymosodwyr sy'n rheoli yn unig k-Nid oes gan 1 cyfranogwr neu lai unrhyw wybodaeth na dylanwad ar y casgliad, tra bod rhai k gall cyfranogwyr gyfrifo'r nifer canlyniadol, ac unrhyw is-set o k bydd cyfranogwyr bob amser yn dod i'r un canlyniad ar gyfer yr un hedyn.
Mae un broblem y gwnaethom ei hosgoi uchod yn ofalus. Ar gyfer rhyngosod i weithio, mae'n bwysig bod y gwerth Hi a gyhoeddwyd gan bob cyfranogwr i yr un oedd mewn gwirionedd p(i)H. Gan nad oes neb heblaw i-th cyfranogwr ddim yn gwybod p(i), neb heblaw i-ni all y cyfranogwr wirio hynny Hi wedi'i gyfrifo'n gywir mewn gwirionedd, a heb unrhyw brawf cryptograffig o gywirdeb Hi gall ymosodwr gyhoeddi unrhyw werth fel Heia, a dylanwadu'n fympwyol ar allbwn y generadur haprifau:
Mae gwahanol werthoedd H_1 a anfonwyd gan y cyfranogwr cyntaf yn arwain at H_0 canlyniadol gwahanol
Mae o leiaf dwy ffordd i brofi cywirdeb Hi, byddwn yn eu hystyried ar ôl i ni ddadansoddi cenhedlaeth y polynomial.
Cenhedlaeth polynomaidd
Yn yr adran ddiweddaf tybiwn fod genym y fath amrysoniaeth p (x) graddau k-1 fod y cyfranogwr i yn gwybod p(i), ac nid oes gan neb arall unrhyw wybodaeth am y gwerth hwn. Yn yr adran nesaf bydd angen hynny arnom hefyd ar gyfer rhyw bwynt a bennwyd ymlaen llaw G gwyddai pawb p(x)G i bawb x.
Yn yr adran hon byddwn yn cymryd yn ganiataol bod gan bob cyfranogwr yn lleol rywfaint o allwedd breifat xi, fel bod pawb yn gwybod yr allwedd gyhoeddus gyfatebol Xi.
Mae un protocol cynhyrchu polynomaidd posibl fel a ganlyn:
-
Pob cyfranogwr i yn lleol yn creu polynomial mympwyol pi(x) gradd k-1. Yna maent yn anfon pob cyfranogwr j значение pi(j), wedi'i amgryptio ag allwedd gyhoeddus Xj. Felly yn unig i-th и j-th cyfranogwr yn gwybod pff(j). Cyfranogwr i hefyd yn cyhoeddi'n gyhoeddus pi(j)G i bawb j o 1 i k cynwysedig.
-
Mae pob cyfranogwr yn defnyddio rhywfaint o gonsensws i ddewis k cyfranogwyr y bydd eu polynomals yn cael eu defnyddio. Gan y gall rhai cyfranogwyr fod all-lein, ni allwn aros tan bawb n bydd cyfranogwyr yn cyhoeddi polynomals. Canlyniad y cam hwn yw set Z yn cynnwys o leiaf k polynomialau wedi'u creu yng ngham (1).
-
Mae cyfranogwyr yn gwneud yn siŵr bod y gwerthoedd y maent yn eu gwybod pi(j) yn cyfateb i a gyhoeddwyd yn gyhoeddus pi(j)G. Ar ôl y cam hwn i mewn Z dim ond polynomialau y trosglwyddir yn breifat ar eu cyfer pi(j) yn cyfateb i a gyhoeddwyd yn gyhoeddus pi(j)G.
-
Pob cyfranogwr j yn cyfrifo ei gydran breifat p(j) fel swm pi(j) i bawb i в Z. Mae pob cyfranogwr hefyd yn cyfrifo'r holl werthoedd p(x)G fel swm pi(x)G i bawb i в Z.
nodi hynny p(x) - polynomial ydyw mewn gwirionedd k-1, oherwydd ei fod yn swm yr unigolyn pi(x), y mae pob un yn polynomaidd o ran gradd k-1. Yna, yn nodi bod tra bod pob cyfranogwr j yn gwybod p(j), nid oes ganddynt unrhyw wybodaeth amdano p (x) gyfer x ≠ j. Yn wir, i gyfrifo'r gwerth hwn, mae angen iddynt wybod popeth pi(x), a chyhyd ag y cyfranogwr j nad yw'n gwybod o leiaf un o'r polynomialau a ddewiswyd, nid oes ganddynt ddigon o wybodaeth amdanynt p(x).
Dyma'r broses gynhyrchu aml-ynomaidd gyfan yr oedd ei hangen yn yr adran ddiwethaf. Mae gweithrediad gweddol amlwg i gamau 1, 2 a 4 uchod. Ond nid yw cam 3 mor ddibwys.
Yn benodol, mae angen i ni allu profi bod wedi'i amgryptio pi(j) yn cyfateb mewn gwirionedd i'r rhai cyhoeddedig pi(j)G. Os na allwn ei brofi, yr ymosodwr i gall anfon sbwriel yn lle hynny pi(j) i'r cyfranogwr j, a chyfranogwr j Ni fydd yn gallu cael y gwir ystyr pi(j), ac ni fydd yn gallu cyfrifo ei gydran breifat.
Mae protocol cryptograffig sy'n eich galluogi i greu neges ychwanegol prawfi(j), fel bod unrhyw gyfranogwr, â rhywfaint o werth e, yn ogystal ag prawf(j) и pi(j)G, yn gallu gwirio hynny’n lleol e - mae'n wir pi(j), wedi'i amgryptio ag allwedd y cyfranogwr j. Yn anffodus, mae maint tystiolaeth o’r fath yn anhygoel o fawr, ac o ystyried bod angen ei chyhoeddi O(nk) Ni ellir defnyddio tystiolaeth o'r fath at y diben hwn.
Yn lle profi hynny pi(j) соответствуетт pi(j)G gallwn ddyrannu cyfnod mawr iawn o amser yn y protocol cynhyrchu aml-enwog, pan fydd yr holl gyfranogwyr yn gwirio'r amgryptio a dderbyniwyd pi(j), ac os nad yw'r neges wedi'i dadgryptio yn cyfateb i'r cyhoedd pi(j)G, maent yn cyhoeddi prawf cryptograffig bod y neges wedi'i hamgryptio a gawsant yn anghywir. Profwch fod y neges dim соответствуетт pi(G) haws o lawer na phrofi ei fod yn cyfateb. Dylid nodi bod hyn yn ei gwneud yn ofynnol i bob cyfranogwr ymddangos ar-lein o leiaf unwaith yn ystod yr amser a neilltuwyd i greu tystiolaeth o’r fath, ac mae’n dibynnu ar y dybiaeth, os bydd yn cyhoeddi prawf o’r fath, y bydd yn cyrraedd yr holl gyfranogwyr eraill o fewn yr un amser penodedig.
Os nad oedd cyfranogwr yn ymddangos ar-lein yn ystod y cyfnod hwn, a bod ganddo o leiaf un gydran anghywir, yna ni fydd y cyfranogwr penodol hwnnw'n gallu cymryd rhan mewn cynhyrchu rhifau pellach. Fodd bynnag, bydd y protocol yn dal i weithredu os oes o leiaf k cyfranogwyr sydd naill ai newydd dderbyn y cydrannau cywir neu wedi llwyddo i adael prawf o anghywirdeb o fewn yr amser penodedig.
Prawf o gywirdeb H_i
Y rhan olaf sydd ar ôl i'w thrafod yw sut i brofi cywirdeb cyhoeddi Hi, sef bod Helo = p(i)H, heb agor p(i).
Gadewch inni gofio bod y gwerthoedd H, G, p(i)G yn gyhoeddus ac yn hysbys i bawb. Derbyn llawdriniaeth p(i) gwybod p(i)G и G a elwir yn logarithm arwahanol, neu dlog, ac rydym am brofi bod:
dlog(p(i)G, G) = dlog(Hi, H)
heb ddatgelu p(i). Mae strwythurau ar gyfer proflenni o'r fath yn bodoli, er enghraifft.
Gyda'r dyluniad hwn, mae pob cyfranogwr, ynghyd â Hi yn anfon prawf o gywirdeb yn ôl y dyluniad.
Unwaith y bydd rhif ar hap yn cael ei gynhyrchu, yn aml mae angen ei ddefnyddio gan gyfranogwyr heblaw'r rhai a'i cynhyrchodd. Rhaid i gyfranogwyr o'r fath, ynghyd â'r nifer, anfon pob un Hi a thystiolaeth gysylltiedig.
Gall darllenydd chwilfrydig ofyn: gan mai'r haprif terfynol yw H0, a p(0)G – Gwybodaeth gyhoeddus yw hon, pam mae angen prawf arnom ar gyfer pob unigolyn Hi, beth am anfon prawf o hynny yn lle
dlog (p(0)G, G) = dlog(H0, H)
Y broblem yw na ellir creu prawf o'r fath gan ddefnyddio Protocol Schnorr oherwydd nad oes neb yn gwybod y gwerth p (0), sy'n angenrheidiol i greu'r prawf, a beth sy'n fwy, mae'r generadur rhif hap cyfan yn seiliedig ar y ffaith nad oes neb yn gwybod y gwerth hwn. Felly mae angen cael yr holl werthoedd Hi a'u tystiolaeth unigol i brofi cywirdeb H0.
Fodd bynnag, pe bai rhywfaint o weithrediad ar bwyntiau ar gromliniau eliptig sy'n debyg yn semantig i luosi, y prawf o gywirdeb H0 yn ddibwys, yn syml iawn y byddem yn gwneud yn siŵr hynny
H0 × G = p(0)G × H
Os yw'r gromlin a ddewiswyd yn cefnogi , mae y prawf hwn yn gweithio. Yn yr achos hwn HMae 0 nid yn unig yn allbwn generadur haprif, y gall unrhyw gyfranogwr sy'n gwybod ei wirio G,H и p(0)G. HMae 0 hefyd yn llofnod ar y neges a ddefnyddiwyd fel hedyn, yn cadarnhau hynny k и n llofnododd y cyfranogwyr y neges hon. Felly, os Hedyn - yw hash y bloc yn y protocol blockchain, felly H0 yn aml-lofnod ar floc ac yn rhif hap da iawn.
I gloi
Mae'r erthygl hon yn rhan o gyfres blog technegol . Mae NEAR yn brotocol blockchain a llwyfan ar gyfer datblygu cymwysiadau datganoledig gyda phwyslais ar rwyddineb datblygiad a rhwyddineb defnydd ar gyfer defnyddwyr terfynol.
Mae'r cod protocol ar agor, mae ein gweithrediad wedi'i ysgrifennu yn Rust, gellir ei ddarganfod .
Gallwch weld sut olwg sydd ar ddatblygiad ar gyfer NEAR ac arbrofi yn y DRhA ar-lein .
Gallwch ddilyn yr holl newyddion yn Rwsieg yn a , ac yn Saesneg yn y swyddogol .
Welwn ni chi cyn bo hir!
Ffynhonnell: hab.com