እርስ በርሳችን ካልተተማመንን የዘፈቀደ ቁጥሮች ማመንጨት ይቻላል? ክፍል 2

ሃይ ሀብር!

В የመጀመሪያው ክፍል። በዚህ ጽሑፍ ውስጥ እርስ በእርሳቸው የማይተማመኑ ተሳታፊዎች ለምን የዘፈቀደ ቁጥሮችን ማመንጨት እንደሚያስፈልግ፣ ለእንደዚህ አይነት የዘፈቀደ ቁጥር ማመንጫዎች ምን ዓይነት መስፈርቶች እንደተቀመጡ እና ለትግበራቸው ሁለት አቀራረቦችን ተመልክተናል።

በዚህ የጽሁፉ ክፍል፣ የመግቢያ ፊርማዎችን የሚጠቀም ሌላ አቀራረብን በዝርዝር እንመለከታለን።

ትንሽ ምስጠራ

የመግቢያ ፊርማዎች እንዴት እንደሚሠሩ ለመረዳት ትንሽ መሠረታዊ ምስጠራን መረዳት ያስፈልግዎታል። ሁለት ፅንሰ-ሀሳቦችን እንጠቀማለን-scalars ፣ ወይም በቀላሉ ቁጥሮች ፣ እነሱም በትንሽ ፊደላት እንጠቁማለን (x, y) እና በኤሊፕቲክ ከርቭ ላይ ያሉ ነጥቦች፣ ይህም በትላልቅ ፊደላት እንጠቁማለን።

የመነሻ ፊርማዎችን መሰረታዊ ነገሮች ለመረዳት ከጥቂት መሰረታዊ ነገሮች በስተቀር ሞላላ ኩርባዎች እንዴት እንደሚሠሩ መረዳት አያስፈልግዎትም።

1. በሞላላ ኩርባ ላይ ያሉ ነጥቦች በ scalar ሊጨመሩ እና ሊባዙ ይችላሉ (በ scalar ማባዛትን እናሳያለን እንደ xGምንም እንኳን ማስታወሻው ቢሆንም Gx በሥነ-ጽሑፍ ውስጥ ብዙ ጊዜ ጥቅም ላይ ይውላል)። በ scalar የመደመር እና የማባዛት ውጤት በሞላላ ኩርባ ላይ ያለ ነጥብ ነው።

2. ነጥቡን ብቻ ማወቅ G እና ምርቱ ከ scalar ጋር xG ሊሰላ አይችልም x.

እንዲሁም የፖሊኖሚል ጽንሰ-ሐሳብን እንጠቀማለን p(x) ዲግሪዎች k-1. በተለይም, የሚከተለውን የ polynomials ንብረትን እንጠቀማለን: እሴቱን ካወቅን p(x) ለማንኛውም k ልዩ x (እና ተጨማሪ መረጃ የለንም። p(x)), ማስላት እንችላለን p(x) ለሌላ ለማንም x.

ለማንኛውም ፖሊኖሚል ትኩረት የሚስብ ነው p(x) እና በመጠምዘዣው ላይ የተወሰነ ነጥብ Gትርጉሙን ማወቅ p(x)ጂ ለማንኛውም k የተለያዩ ትርጉሞች x, እኛ ደግሞ ማስላት እንችላለን p(x)ጂ ለማንኛውም x.

ይህ የመግቢያ ፊርማዎች እንዴት እንደሚሠሩ እና የዘፈቀደ ቁጥሮችን ለመፍጠር እንዴት እንደሚጠቀሙባቸው ዝርዝሮችን ለመፈተሽ በቂ መረጃ ነው።

በመግቢያው ፊርማዎች ላይ የዘፈቀደ ቁጥር ጀነሬተር

እንዲህ እንበል n ተሳታፊዎች የዘፈቀደ ቁጥር ማመንጨት ይፈልጋሉ፣ እና ማንም እንዲሳተፍ እንፈልጋለን k ቁጥር ለማመንጨት ከነሱ በቂ ነበሩ ነገር ግን የሚቆጣጠሩት አጥቂዎች k-1 ወይም ያነሱ ተሳታፊዎች የተፈጠረውን ቁጥር መተንበይ ወይም ተጽዕኖ ማድረግ አይችሉም።

እንደዚህ አይነት ፖሊኖሚል አለ እንበል p(x) ዲግሪዎች k-1 የመጀመሪያው ተሳታፊ የሚያውቀው p (1)፣ ሁለተኛው ያውቃል ገጽ (2)፣ እናም ይቀጥላል (n- ያውቃል p(n)). እኛ ደግሞ ለተወሰነ የተወሰነ ነጥብ እንገምታለን። G ሁሉም ያውቃል p(x)ጂ ለሁሉም እሴቶች x. እንጠራዋለን p(i) "የግል አካል" iተሳታፊ (ምክንያቱም ብቻ) iተሳታፊው ያውቃታል) እና p(i)ጂ "የህዝብ አካል" i- ተሳታፊ (ሁሉም ተሳታፊዎች ስለሚያውቋት)። እንደምታስታውሰው, እውቀት p(i)ጂ ወደነበረበት ለመመለስ በቂ አይደለም p(i)

እንደዚህ አይነት ፖሊኖሚል መፍጠር ስለዚህ ብቻ i-የመጀመሪያው ተሳታፊ እና ማንም ሰው የራሱን የግል አካል አያውቅም - ይህ የፕሮቶኮሉ በጣም ውስብስብ እና አስደሳች ክፍል ነው, እና ከዚህ በታች እንመረምራለን. ለጊዜው, እንደዚህ አይነት ፖሊኖሚል እንዳለን እናስብ እና ሁሉም ተሳታፊዎች የግል ክፍሎቻቸውን ያውቃሉ.

የዘፈቀደ ቁጥር ለማመንጨት እንዴት እንደዚህ አይነት ፖሊኖሚል መጠቀም እንችላለን? ለመጀመር፣ ከዚህ ቀደም ለጄነሬተሩ እንደ ግብአት ጥቅም ላይ ያልዋለ አንዳንድ ሕብረቁምፊዎች እንፈልጋለን። በብሎክቼን ጉዳይ ላይ የመጨረሻው የማገጃ ሃሽ h ለእንደዚህ አይነት መስመር ጥሩ እጩ ነው. ተሳታፊዎች በዘፈቀደ ቁጥር መፍጠር ይፈልጋሉ h እንደ ዘር. ተሳታፊዎች መጀመሪያ ይለወጣሉ። h ማንኛውንም አስቀድሞ የተገለጸ ተግባር በመጠቀም ከርቭ ላይ እስከ አንድ ነጥብ ድረስ፡-

H = scalarToPoint(ሰ)

ከዚያም እያንዳንዱ ተሳታፊ i ያሰላል እና ያትማል ሰላም = p(i)H, እነሱ ስለሚያውቁ ምን ማድረግ ይችላሉ p(i) እና ኤች. ይፋ ማድረግ Hሌሎች ተሳታፊዎች የግሉን አካል እንዲመልሱ አልፈቅድም። iኛ ተሳታፊ, እና ስለዚህ አንድ የግል ክፍሎች ስብስብ ከአግድ ወደ ማገድ ጥቅም ላይ ሊውል ይችላል. ስለዚህ ከዚህ በታች የተገለፀው ውድ ፖሊኖሚል ትውልድ ስልተ ቀመር አንድ ጊዜ ብቻ ነው የሚያስፈልገው።

መቼ k ተሳታፊዎች አስከሬን ታይተዋል። ሰላም = p(i)H, ሁሉም ሰው ማስላት ይችላል Hx = p (x) ኤች ለሁሉም x በመጨረሻው ክፍል ውስጥ ስለተነጋገርነው የፖሊኖሚሎች ንብረት ምስጋና ይግባው. በዚህ ጊዜ ሁሉም ተሳታፊዎች ያሰላሉ H0 = p(0) ሸ፣ እና ይህ የተገኘው የዘፈቀደ ቁጥር ነው። እባክዎን ማንም አያውቅም ገጽ (0)፣ እና ስለዚህ ለማስላት ብቸኛው መንገድ ገጽ (0) ኤች - ይህ መጠላለፍ ነው። p(x)H፣ የሚቻለው መቼ ነው k እሴቶች p (i) ኤች የሚታወቅ። ማንኛውንም አነስተኛ መጠን በመክፈት ላይ p (i) ኤች ስለ ምንም መረጃ አይሰጥም ገጽ (0) ኤች.

ከላይ ያለው ጀነሬተር እኛ የምንፈልጋቸው ሁሉም ንብረቶች አሉት፡ አጥቂዎች ብቻ ይቆጣጠራሉ። k-1 ተሳታፊዎች ወይም ከዚያ በታች ምንም መረጃ ወይም መደምደሚያ ላይ ተጽዕኖ የላቸውም, ማንኛውም ሳለ k ተሳታፊዎች የተገኘውን ቁጥር እና ማንኛውንም ንዑስ ስብስብ ማስላት ይችላሉ። k ተሳታፊዎች ለተመሳሳይ ዘር ሁልጊዜ ወደ ተመሳሳይ ውጤት ይመጣሉ.

ከላይ በጥንቃቄ ያስወገድነው አንድ ችግር አለ። interpolation እንዲሰራ, ይህ ዋጋ መሆኑን አስፈላጊ ነው Hእኔ በእያንዳንዱ ተሳታፊ የታተመ i በእርግጥም ተመሳሳይ ነበር። p (i) ኤች. በስተቀር ማንም ስለሌለ i- ተሳታፊው አያውቅም p(i)፣ በስተቀር ማንም የለም። i-ተሳታፊው ያንን ማረጋገጥ አይችልም። Hi በትክክል በትክክል ይሰላል፣ እና ያለ ምንም ምስጢራዊ የትክክለኛነት ማረጋገጫ Hእኔ አጥቂ ማንኛውንም ዋጋ ማተም እችላለሁ ታዲያስ, እና በዘፈቀደ ቁጥር አመንጪው ውጤት ላይ በዘፈቀደ ተጽዕኖ ያሳድራል።:

በመጀመሪያው ተሳታፊ የተላኩ የተለያዩ የH_1 እሴቶች ወደተለየ ውጤት H_0 ይመራሉ

ትክክለኛነትን ለማረጋገጥ ቢያንስ ሁለት መንገዶች አሉ። Hእኔ, የፖሊኖሚል ማመንጨትን ከተመለከትን በኋላ እንመለከታቸዋለን.

ፖሊኖሚል ትውልድ

በመጨረሻው ክፍል ውስጥ እንዲህ ዓይነት ፖሊኖሚል እንዳለን ገምተናል p(x) ዲግሪዎች k-1 ተሳታፊው i ያውቃል p(i), እና ማንም ሌላ ስለዚህ ዋጋ ምንም መረጃ የለውም. በሚቀጥለው ክፍል ደግሞ ለተወሰነ የተወሰነ ነጥብ እንፈልጋለን G ሁሉም ያውቅ ነበር። p(x)ጂ ለሁሉም x.

በዚህ ክፍል ውስጥ እያንዳንዱ ተሳታፊ በአካባቢው አንዳንድ የግል ቁልፍ እንዳለው እንገምታለን። xi የሚዛመደውን የህዝብ ቁልፍ ሁሉም ሰው እንዲያውቅ Xi.

አንድ ሊሆን የሚችል ፖሊኖሚል ትውልድ ፕሮቶኮል እንደሚከተለው ነው።

1. እያንዳንዱ ተሳታፊ i በአካባቢው የዘፈቀደ ፖሊኖሚል ይፈጥራል ፒ (x) ዲግሪ k-1. ከዚያም እያንዳንዱን ተሳታፊ ይልካሉ j ትርጉም pi(j)፣ በወል ቁልፍ የተመሰጠረ Xj. ስለዚህ ብቻ i-ም и j-ም ተሳታፊ ያውቃል pi (j) ተሳታፊ i በይፋም ያስታውቃል ፒ (ጄ) ጂ ለሁሉም j от 1 ወደ k ሁሉን ያካተተ.

2. ሁሉም ተሳታፊዎች ለመምረጥ የተወሰነ ስምምነት ይጠቀማሉ k ፖሊኖሚሎች ጥቅም ላይ የሚውሉ ተሳታፊዎች። አንዳንድ ተሳታፊዎች ከመስመር ውጭ ሊሆኑ ስለሚችሉ፣ ሁሉም ሰው እስኪደርስ መጠበቅ አንችልም። n ተሳታፊዎች ፖሊኖሚሎችን ያትማሉ። የዚህ እርምጃ ውጤት ስብስብ ነው Z ቢያንስ ያካተተ k በደረጃ (1) ውስጥ የተፈጠሩ ፖሊኖሚሎች.

3. ተሳታፊዎች የሚያውቋቸውን እሴቶች ያረጋግጣሉ pi(j) በይፋ ከተገለጸው ጋር ይዛመዳል ፒ (ጄ) ጂ. ከዚህ እርምጃ በኋላ Z በግል የሚተላለፉባቸው ፖሊኖሚሎች ብቻ pi(j) በይፋ ከተገለጸው ጋር ይዛመዳል ፒ (ጄ) ጂ.

4. እያንዳንዱ ተሳታፊ j የግል ክፍሉን ያሰላል p(j) እንደ ድምር pi (j) ለሁሉም i в Z. እያንዳንዱ ተሳታፊ እንዲሁ ሁሉንም ዋጋዎች ያሰላል p(x)ጂ እንደ ድምር pi(x) G ለሁሉም i в Z.

አስታውስ አትርሳ ገጽ (x) - እሱ በእርግጥ ፖሊኖሚል ነው። k-1፣ ምክንያቱም የግለሰቡ ድምር ነው። pi(x)፣ እያንዳንዳቸው የዲግሪ ፖሊኖሚል ናቸው። k-1. ከዚያም, እያንዳንዱ ተሳታፊ ሳለ መሆኑን ልብ ይበሉ j ያውቃል p(j)፣ ስለ እነሱ ምንም መረጃ የላቸውም p(x) ለ x ≠ j. በእርግጥ, ይህንን ዋጋ ለማስላት ሁሉንም ነገር ማወቅ አለባቸው ፒ(x)፣ እና እስከ ተሳታፊው ድረስ j ከተመረጡት ፖሊኖሚሎች ውስጥ ቢያንስ አንዱን አያውቅም, ስለ እነሱ በቂ መረጃ የላቸውም p(x)።

ይህ በመጨረሻው ክፍል ውስጥ የሚያስፈልገው አጠቃላይ ፖሊኖሚል የማመንጨት ሂደት ነው። ከላይ ያሉት ደረጃዎች 1፣ 2 እና 4 በትክክል ግልጽ የሆነ አተገባበር አላቸው። ደረጃ 3 ግን ያን ያህል ቀላል አይደለም።

በተለይ ኢንክሪፕት የተደረገ መሆኑን ማረጋገጥ መቻል አለብን pi (j) በእውነቱ ከታተሙት ጋር ይዛመዳል ፒ (ጄ) ጂ. ማረጋገጥ ካልቻልን አጥቂው። i በምትኩ ቆሻሻን ሊልክ ይችላል። pi(j) ወደ ተሳታፊ j, እና ተሳታፊ j ትክክለኛውን ዋጋ ማግኘት አይችሉም ፒ (ጄ) እና የግል ክፍሉን ማስላት አይችልም.

ተጨማሪ መልእክት እንዲፈጥሩ የሚያስችልዎ ምስጠራ ፕሮቶኮል አለ። ማስረጃi(j)፣ እንደ ማንኛውም ተሳታፊ፣ የተወሰነ ዋጋ ያለው e, እንዲሁም ማስረጃ (j) и pi(j)G፣ ያንን በአካባቢው ማረጋገጥ ይችላል። e - በእርግጥ ነው ፒ (ጄ) ከተሳታፊው ቁልፍ ጋር የተመሰጠረ j. እንደ አለመታደል ሆኖ የእንደዚህ አይነት ማስረጃዎች መጠን በሚያስደንቅ ሁኔታ ትልቅ ነው, እና ለማተም አስፈላጊ ሆኖ ሲገኝ ኦ(nk) እንደዚህ ያሉ ማስረጃዎች ለዚህ ዓላማ ጥቅም ላይ ሊውሉ አይችሉም.

ያንን ከማረጋገጥ ይልቅ ፒ (ጄ) ጋር ይዛመዳል pi(j)G በፖሊኖሚል ትውልድ ፕሮቶኮል ውስጥ በጣም ረጅም ጊዜ መመደብ እንችላለን፣ በዚህ ጊዜ ሁሉም ተሳታፊዎች የተቀበሉትን ኢንክሪፕት የተደረገውን ያረጋግጡ። ፒ (ጄ) እና ዲክሪፕት የተደረገው መልእክት ከህዝብ ጋር የማይገናኝ ከሆነ pi(j)G፣ የተቀበሉት ኢንክሪፕትድ የተደረገ መልእክት ትክክል እንዳልሆነ የሚያሳይ ምስጠራ ያትማሉ። መልእክቱን አረጋግጡ አይደለም ጋር ይዛመዳል ፒ(ጂ) የሚዛመድ መሆኑን ከማረጋገጥ ይልቅ በጣም ቀላል። ይህ እያንዳንዱ ተሳታፊ እንደነዚህ ያሉ ማስረጃዎችን ለመፍጠር በተመደበው ጊዜ ውስጥ ቢያንስ አንድ ጊዜ በመስመር ላይ እንዲታይ እንደሚያስፈልግ እና እንደዚህ ዓይነቱን ማስረጃ ከታተመ በተመሳሳይ ጊዜ ውስጥ ለሁሉም ተሳታፊዎች ይደርሳል በሚለው ግምት ላይ የተመሠረተ መሆኑን ልብ ሊባል ይገባል።

በዚህ ጊዜ ውስጥ አንድ ተሳታፊ በመስመር ላይ ካልታየ እና ቢያንስ አንድ የተሳሳተ አካል ካለው፣ ያ የተለየ ተሳታፊ ተጨማሪ ቁጥር ማመንጨት ላይ መሳተፍ አይችልም። ፕሮቶኮሉ ግን ቢያንስ ካለ አሁንም ይሠራል k ትክክለኛ ክፍሎችን የተቀበሉ ወይም የተሳሳተ የመሆኑን ማረጋገጫ በተመደበው ጊዜ ውስጥ ለመተው የቻሉ ተሳታፊዎች።

የ H_i ትክክለኛነት ማረጋገጫዎች

ለመወያየት የሚቀረው የመጨረሻው ክፍል የታተመውን ትክክለኛነት እንዴት ማረጋገጥ እንደሚቻል ነው Hእኔ ማለትም ያ ሰላም = p(i)H, ሳይከፍት p(i)

እሴቶቹን እናስታውስ H፣ G፣ p(i)ጂ ይፋዊ እና ለሁሉም የሚታወቅ። ክወና ተቀበል p(i) ማወቅ p(i)ጂ и G discrete ሎጋሪዝም ይባላል፣ ወይም ድሎግ፣ እና ያንን ማረጋገጥ እንፈልጋለን-

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

ሳይገለጽ p(i). ለእንደዚህ አይነት ማረጋገጫዎች ግንባታዎች አሉ, ለምሳሌ Schnorr ፕሮቶኮል.

በዚህ ንድፍ, እያንዳንዱ ተሳታፊ, አብሮ Hi በንድፍ መሰረት ትክክለኛነት ማረጋገጫ ይልካል.

አንድ ጊዜ የዘፈቀደ ቁጥር ከተፈጠረ፣ ብዙ ጊዜ ካመነጩት በስተቀር ሌሎች ተሳታፊዎች ሊጠቀሙበት ይገባል። እንደነዚህ ያሉ ተሳታፊዎች ከቁጥሩ ጋር, ሁሉንም መላክ አለባቸው Hi እና ተዛማጅ ማስረጃዎች.

ጠያቂ አንባቢ ሊጠይቅ ይችላል፡ የመጨረሻው የዘፈቀደ ቁጥር ስለሆነ H0, እና ገጽ(0)ጂ - ይህ የህዝብ መረጃ ነው, ለምን ለእያንዳንዱ ግለሰብ ማረጋገጫ ያስፈልገናል Hእኔ፣ በምትኩ ለምን ማስረጃ አልላክም።

ድሎግ(p(0)ጂ፣ጂ) = dlog(H0, H)

ችግሩ የ Schnorr ፕሮቶኮልን በመጠቀም እንዲህ ዓይነቱ ማረጋገጫ ሊፈጠር አይችልም ምክንያቱም ማንም ዋጋውን አያውቅም p (0), ማስረጃውን ለመፍጠር አስፈላጊ ነው, እና ምን ተጨማሪ ነው, ሙሉውን የዘፈቀደ ቁጥር ጄኔሬተር ማንም ሰው ይህንን ዋጋ በማያውቅ እውነታ ላይ የተመሰረተ ነው. ስለዚህ ሁሉም እሴቶች ሊኖሩት ይገባል Hi እና ትክክለኛነትን ለማረጋገጥ የግለሰብ ማስረጃዎቻቸው H0.

ነገር ግን፣ በትርጓሜ ከማባዛት ጋር ተመሳሳይ በሆኑ ሞላላ ኩርባ ላይ ባሉ ነጥቦች ላይ አንዳንድ ክንዋኔዎች ካሉ፣ የትክክለኛነት ማረጋገጫው H0 ቀላል ይሆናል ፣ በቀላሉ ያንን እናረጋግጣለን

H0 × G = p(0)ጂ × ኤች

የተመረጠው ኩርባ የሚደግፍ ከሆነ ሞላላ ጥምዝ ጥንድ, ይህ ማስረጃ ይሠራል. በዚህ ጉዳይ ላይ H0 የዘፈቀደ ቁጥር ጄኔሬተር ውፅዓት ብቻ አይደለም፣ይህም በሚያውቅ ማንኛውም ተሳታፊ ሊረጋገጥ ይችላል። ጂ፣ ኤች и p(0)ጂ. ኤች0 ደግሞ እንደ ዘር ያገለገለው መልእክት ላይ ፊርማ ነው, ያንን ያረጋግጣል k и n ተሳታፊዎች ይህንን መልእክት ፈርመዋል። ስለዚህ, ከሆነ ዘር - በ blockchain ፕሮቶኮል ውስጥ ያለው የብሎክ ሃሽ ነው ፣ ከዚያ H0 ሁለቱም በብሎክ ላይ ባለ ብዙ ፊርማ እና በጣም ጥሩ የዘፈቀደ ቁጥር ነው።

በማጠቃለያው

ይህ መጣጥፍ የቴክኒካል ብሎግ ተከታታይ አካል ነው። ቅርብ. NEAR ለልማት ቀላልነት እና ለዋና ተጠቃሚዎች የአጠቃቀም ቀላልነት ላይ በማተኮር ያልተማከለ አፕሊኬሽኖችን ለማዘጋጀት የብሎክቼይን ፕሮቶኮል እና መድረክ ነው።

የፕሮቶኮል ኮድ ክፍት ነው, የእኛ ትግበራ በሩስት ውስጥ ተጽፏል, ሊገኝ ይችላል እዚህ.

የNEAR እድገት ምን እንደሚመስል ማየት እና በመስመር ላይ IDE ውስጥ መሞከር ትችላለህ እዚህ.

ሁሉንም ዜናዎች በሩሲያኛ መከታተል ይችላሉ። ቴሌግራም ቡድን እና ውስጥ ቡድን በ VKontakte, እና በእንግሊዝኛ በኦፊሴላዊው ውስጥ ትዊተር.

እስክንገናኝ!

ምንጭ: hab.com