ZK Workshop #3 - Aritmetización

Transcript

igual si si entra alguien más En todo caso después no hay problema Bueno eso nada como les decía este vamos arrancamos un poquito con un repaso rápido los que estamos acá presencial Ya estuvimos Charlando un poco pero simplemente para estar todos alineados un poco lo que hablamos la clase pasada fue sobre circuitos aritméticos que de alguna manera son una extensión de los circuitos lógicos entonces como que es un bastante natural en vez de tener inputs que pueden ser c un pueden ser 0 un o cualquier elemento de un campo finito y un poco surgió la duda de Por qué este modelo no O sea por qué Vamos nos ponemos tan tan pesados en

en tratar de entender Este modelo que es como un poco como overkill vamos a decir no para para calcular algo lo puedo programar mucho más fácil si se quiere pero lo que vamos a ver Es que para Nuestro objetivo Este modelo de circuitos aritméticos Tiene ciertas bondades entonces un poco d ver si un poco lo que estuvimos hablando antes de de empezar y les repaso acá es que nosotros tenemos Este modelo no Don tenemos una serie de inputs ahí se ve bien o loo más grande ve bien perfecto tenemos una serie de

inputs no que entran en diferentes compuertas eh No cre que s un circuito digo podemos imaginar cualquier cosa y voy a dibujar uno por acá tenemos compuertas de de adición icación adición multiplicación y tenemos y tenemos un output o varios Sí y lo que requerimos es que este output

tenga algún valor esperado normalmente para hacerlo como estándar se espera que ese valor sea cero después pueden pensar Cómo transformar eh un circuito que ustedes tengan para que el valor de final de cer0 es es bastante sencillo el ejercicio pero un poco la idea es bueno todo esto que está acá sí es como una caja que hace un cómputo o sea siempre que nosotros le damos los mismos inputs va a dar el mismo output es determinístico Está bien entonces de alguna manera esto es una función de de algunos inputs Yo le voy a llamar ahora vamos a ver por

qué pero vamos a separarlo en dos dos inputs le llamo x y W ahora vamos a entrar en esto y un poco la pregunta que me hicieron acá es bueno pero por qué hacemos todo este modelado de con con un circuito y todo cuando en realidad si esto es una función yo lo que quiero es demostrar que un input da un cierto output lo puedo hacer de otra forma Bueno pero la gracia de todo esto es que algunos inputs yo no quiero revelarlos y cuando pensamos una fun la única forma que tenemos pensar cómo validar que algo da un output es haciendo el cálculo no teniendo estos input metiéndolos acá y

viendo si el output está OK pero nosotros no queremos eso porque lo que no queremos hacer es dar información sobre los input ahí está el vimos hasta ahora vi ent en preparación a todo esto y algunas cosas que vienen en la clase que viene sabemos un poco Cómo se estructura una proof proof se acuerdan que en la primera clase vimos un protocolo Donde había y y vuelta después vimos un poco sobre campo finito jes cosas como preparando la cancha Y ahora de la clase pasada tenemos esto de hay formas de representar afirmaciones con

circuitos son cosas que parecen desagregadas por ahora entonces un poco nos falta esto cómo transformamos lo que sabemos en pruebas Y acá es donde empezamos a atar los caos y a llegar a los resultados finales Sí entonces Admito que esta clase no la preparé tanto como las anteriores Así que si ven que que dudo un poquito ahí es por eso Entonces está estamos Entonces cuál es Nuestro objetivo de hoy que es un poco relacionado con esto que decía acá vamos a probar que una cierta evaluación de un circuito es correcta O

sea que dado una serie de inputs y un output o varios yo voy a demostrar que todo lo que pasa en el medio está bien Sí que yo puedo mirar cualquiera de estas compuertas o cualquiera de estas restricciones y decir ah Están Okay entonces empiezo a sondear un poco y al final me convenzo que si hay muchas que están okay Bueno entonces asumo que está Okay la evaluación Ah viene por ahí y un poco la idea es es lo que les decía recién en todo este proceso lo que hacemos Es ocultar esto no Y eso es el corazón de todo este asunto está bien tenemos dudas hasta acá el objetivo es claro

no vamos ahí entonces me acuerdo del ejemplo que puse Ah bien entonces escribí este circuito ahí no circuito simple hay tres compuertas de multiplicación dos de adición y vieron que ya separé de alguna manera en los x y los W Ah que eso tiene una razón de ser la razón de ser es que los X van a ser como la información pública se llama enunciado o statement en inglés por eso en la clase pasada hablé que statement era un poco no no bien usado en el contexto en el que lo usé para no confundir y después tenemos cierta información privada que le llamamos

testigo o witness en inglés y Estas son las dos cosas que van a ser inputs al circuito obviamente la info pública va a ser parte de las cosas que yo puedo darle a quien va a verificar o que mejor dicho Quien puede quien verifica puede preguntar y yo le puedo decir esto es así o va a ser información pública directamente y la pueden usar os está entonces con estos inputs digamos estudiamos un poco Cómo funcionan estos circuitos y demás Pero ahora tenemos que empezar a a como ponerle un poco más el el foco a cada parte y empezar a ver qué dan las cosas está entonces cómo hacemos eso lo primero que hacemos Es numerar

las compuertas Sí entonces una vez que las numeramos podemos empezar a a bueno como que tienen nombre no podemos empezar a decir bueno esta la un Y entonces los input de la un son estos el output es este entonces n tiene un identificador Okay después lo que había escrito acá en vez de escribir todo el circuito de alguna manera lo que yo quiero demostrar es que conozco x y W tal que el output de todo esto es cero podría ser el output fuera otra cosa y está bien la forma estándar digamos es preparar el circuito para que de cer Exacto para que de cero es como una

forma estándar porque le quitamos un chequeo más al verificador siempre va a ver que sea cer bien entonces detalle ahí Obviamente el X como es público no hay nada que demostrar sobre el X pero si sobre el Do yo quiero demostrar que conozco un testigo tal que la evaluación de circuito da cero está hasta acá Venimos bien Entonces vamos a poner un ejemplo no ponemos esto como lo vimos recién y vieron que yo le puse unos números ahí a los inputs no supónganse que un y nu son públicos y dos y cco son información mía

privada la voy a mostrar lo primero que hacemos suponemos que trabajamos en en módulo 17 un campo finito de 17 elementos por por decir algo hago las cuentas no entonces muy simple 1 * 9 da 9 2 * 9 da 18 eh No esto es Perdón 2 + 9 da 11 Está bien después tenemos 5 * 11 da 55 módulo 17 la tres está Sí porque 52 es múltiplo de 17 50

y un cuent si me equivo bien 5 por puede ser que ha solo yo no veo la otra parte que está mirando no no O sea pued hacer as ahí perfecto capaz que le AC con las cuentas Disculpen pero después arreglo y lo subo Ah no Estoy compartiendo pantalla nad me avisó muchachos nosotr somos un

poco como las cabezas de Futurama si no nos mov estamos esit claro voy a volver un poquito para atrás chicos tienen que avisar esas cosas Si no después aparte queda mal en la grabación cómo hacemos para volver para atrás acá Bueno voy a pasar hacer speedrun esto no lo primero que dijimos fue hicimos un recap de las cosas que ya hablamos después lo que hablamos fue esto de que vamos a demostrar que una evaluación es correcta y lo vamos a hacer de una manera en la que se ocultan los inputs Por eso nos molestamos en ver circuitos después mostré Este ejemplo

y hice una diferenciación entre la info pública y la info privada no les puse números a las compuertas para después poder hacer algunas cositas y después un poco la notación la cambi un poquito para para no escribir un circuito cada vez porque justamente La idea es que a toda esta función que escribimos acá le llamamos C y C se divide en dos inputs x y W que son vectores no o sea son son una serie de valores y el output estándar es cero que eso lo lo comentaba para que no tengamos

que aparte decirle al verificador que el output esperado es tanto convenimos que el output esperado es cero y preparamos el circuito para que de eso está eh acá fue donde estábamos hablando recién que creo que le epif yo con las cuentas capaz que estaba un poco dormido ese día es muy probable eh Pero bueno de alguna manera y si quieren lo que podríamos pensar es esto esto creo que da cuatro el el este valor mejor señalo así Creo que da cuatro no porque 11 * 5 55 y módulo 17 son 34 51 a 4 Está bien entonces esto es cu acá le pifi y de repente para que de cero

podríamos hacer que eh hubiera una compuerta más de pronto y dos compuertas más y le restamos uno y está bien yo que s no s está dando porque 13 no 13 má 17 listo claro por eso digo yo ahí laf pero después arreglo las cuentas hagamos de cuenta que están bien porque igual La idea es la misma entonces un poco con esto lo que hacemos Es Yo como como probador como persona que conoce el input privado puedo hacer todas las cuentas sí alguien que es eh un verificador que no va a conocer Esto no puede hacer las cuentas está y ahí

está la gracia Entonces qué es lo que voy a hacer Voy a trabajar un poquito con estos valores intermedios está Y ahí se va a desprender la forma de crear estas pruebas está entonces podemos armar como una especie de tabla tenemos los inputs por un lado y una tabla donde tenemos por cada compuerta numerada como les había contado por cada compuerta tenemos el input de la izquierda el input de la derecha y el output son operaciones binarias O sea que tienen dos inputs y un output acá vale la pena destacar que esto es algo que quedó como implícito en la clase pasada que las compuertas están

ordenadas s o sea siempre es input de la izquierda más input de la derecha de la izquierda por input de la derecha Esto es así porque justamente para hacer sustracción es importante que estén ordenadas entonces tiene un sentido bien entonces eh Más allá de que están mal las cuentas que eso lo lo arreglo para para cuando les mandé las slides el objetivo va a ser codificar toda esta cosa que está acá sí y olvidarnos del circuito una vez que hicimos todo ese cálculo nos vamos a olvidar del circuito y vamos a ocuparnos de en codificar esto de alguna manera tal que a partir de esa codificación

podamos a hacer una Zero knowledge proof está por ahora suena medio abstracto pero vamos de poco entonces y acá Cuál es el plan para hoy vamos a hablar de una cosa que se llama R1 cs que ahora les digo Qué es vamos a hablar de polinomios y vamos a hablar de una aritmetización más se llama plonk que es la que está atrás de plonk que es uno de los métodos de que se usan hoy y acá puse nada esto tener no sé sieron Master Chef alguna vez pero este loco Mar no ha que tener miedo hay que tener miedo vamos a ir a poquito así que creo que que podemos

podemos hacerlo tranqui bueno vamos a empezar por acá RS les dejé acá un paper es pinoquio que es un método sin que tiene creo que tiene unos años ya pero es donde creo que por primera vez se habla este sistema y es como su introducción al mundo Hoy hay varias cosas que lo usan y está ahí como atrás algunos sistemas y bueno quiere decir rank constra una pregunta picante ahí porque la explicación de por se llama así tiene su su que ver pueden verla después están si

tocan ahí los lleva final de las preguntas picantes y bueno entonces poco la gracia es observar esto no el circuito se compone de sumas y multiplicaciones sencillo entonces podríamos como pensar que cada compuerta tiene una cierta forma que podría incorporar o suma o multiplicación y tal vez como que hasta podríamos condensar algunas compuertas entonces la forma es esta no se asusten lo único que estoy diciendo acá es que estoy multiplicando sumas de de algunos inputs por sumas de algunos otros inputs Ahora cuando lo veamos vamos a ver que de

hecho es más simple la representación todavía pero Digamos como que podemos ir escribiendo todo nuestro sistema como pasos de este estilo no porque acá está la multiplicaciones del medio Acá está la suma está suma multiplicación es lo único que hay en esta expresión Entonces vamos a ver un ejemplo como el de recién lo que voy a hacer después es Buscar algunos valores posta que den cero porque me he equivocado pero el circuito es el mismo y ahí ven un poco la gracia justamente esto el circuito es el mismo los input cambian entonces

ent nosotros tenemos esto fíjense que yo le llamé a cada uno de estos inputs a cada uno de estos cables llamé W I ahora que pienso es un poco confuso porque W le había llamado a los otros pero W es de wire Entonces como cabado no tiene nada que ver o sea a pesar de que estos dos eran W Olvidos un segundo Le cambia la anotación eh Le cambia la anotación cuando haa la grabación me voy a acordar de que tengo que hacer esto entonces olvidémonos un segundo de de como habíamos nombrado antes cada cable acá va a ser un W total hay nueve cables distintos y noten desde

ya que este de acá por ejemplo es un valor solo para esto esto y esto Sí y eso está bien Sí para dos para tres para este para este input o sea este output este input y este input son tres valores que tienen que ser iguales Okay está por qué les digo esto porque está bueno que empecemos a pensar en el circuito como una serie de restricciones que se tienen que cumplir está yo para para decir que este circuito es válido que una evaluación es válida yo tengo que poder mirar esta compuerta que es de suma por ejemplo esta y decir sí w2 má w3 da w6 si yo

puedo veo eso digo Ah ok esta parte del circuito está OK pero también hay otras otras restricciones que son por ejemplo el output de la dos y el input derecho de la 3 y el input izquierdo de la 4 son iguales si yo chequeo eso y dan todos iguales digo Ah esta parte del circuito está bien y así puedo hacer con varias partes si de muestreo imaginarlo s esta esta compta está bien Okay está bien Y esta está bien y esto Ah esto no está bien No te creo va por ahí está Sí si tienen preguntas preguntan no no pasa nada pero eso o sea en qué

escenario lo usarías vos eso eh porque vos se supone que vos armaste el circuito y por por definición dijiste que W sea igual para es porque yo soy honesto Yo soy un probador honesto justamente en criptografía Por ejemplo si vos querés falsificar una firma vos tenés que encontrar un cierto valor que cumpla con cierta verificación y cuál es la premisa que es extremadamente difícil hacer eso si vos no conocés una clave privada un poco la idea es la misma yo soy honesto entonces encontrar la codificación correcta de todo esto es fácil porque conozco los inputs está bien Ahora encontrar la codificación una

codificación falsificada que que a mí me beneficie de alguna manera es un huevo Esa es la gracia Entonces cómo nos protegemos de eso justamente empezando a ver que las restricciones se cumplan es muy improbable que alguien que está falsificando una prueba pueda cumplir con todas las restricciones esa es como la premisa atrás de todo esto ya vamos a ver cómo se llega eso pero la idea es es los circuitos por lo general deberían justamente para protegerse de eso tener en varios puntos varios input que sean combinado no O sea No necesariamente o

sea vos podrías chequear por ejemplo si miras w5 no una de las restricciones que se tienen que cumplir es que el output de la compuerta un sea el input izquierdo de la TR Y eso no no implica que haya elaciones pero es una restricción y en cualquier punto Yo podría chequear una restricción que no fuera verdad y un probador deshonesto podría haber hecho trampa Entonces yo lo puedo agarrar en esa trampa Sí el verificador o va a necesitar un in público no es cero cero no tiene nada que ver que noer no podr no darle nada nada de nada

podría ser todo privado eh Y y en realidad lo que conoce es el circuito está o sea vos justamente tenés información del circuito y ahora vamos a eso para poder sondear para poder saber qué es lo que tenés que ver está Y a vos te importa que el computo esté bien hecho tener cero inut podes tener Ninguno de los inputs y aún así ser convencido de algo está bien Quiero quiero ir trabajando sobre esta idea porque es como lo que está atrás de todo esto y por eso hicimos todo este esfuerzo de plantear como un circuito Y ahora van a ver dónde dónde viene la magia imaginemos que los primeros cu W son privados Vos cómo sabés si está

bien o sea si son válidos los inputs los dos primeros porque vos ahí en teoría no podes abrir el circuito bueno Es verdad Es verdad eso es es una buena observación eh hay ciertas partes del circuito que no no podes pedir Y eso es una una limitación eh Supongo que ahí en realidad el argumento Es que de todas maneras vos tenés que hacer que todo lo demás sea correcto Entonces es difícil encontrar un input privado que cumpla con todo el circuito por lo tanto puedes chequear las restricciones interiores y está Okay pero es verdad que está bueno en realidad que la cantidad de de compuerta y valores que tengo que chequear acá sea baja con respecto a

todo lo que pasa dentro porque ahí yo tengo como muchas más condiciones para chequear yo no puedo revelar los inputs privados es parte de la premisa podríamos llegar a hacer alguna otra magia que no vamos a entrar en detalle Supongo desp lo derigo y les cuento porque si no capaz que un bazo Así que priero no bien entonces cuál es la idea si nosotros vemos esta primera compuerta podemos escribir lo que pasa como una cuentita No qué es lo que pasa esto w1 por w2 es w5 está eso es una restricción s sea Esto es algo que se

tiene que cumplir En un circuito cuya evaluación es válida o en una evaluación válida de un circuito está si vemos la compuerta dos ustedes me dirán Cómo se escribe eso w2 + w3 = w6 Exacto pero ahí le agrego una cosita para escribirlo en esta forma que que lo vimos la slide pasada que era una multiplicación para que siempre haya una multiplicación le agrego un un no w2 w3 es ig w6 todo eso por un también y ahora ahora Les explico por qué la si multiplicas esos dos o sea w1

por w2 por 1 por w2 + w3 es w7 si multiplicas esto Ahí va Perfecto esa es una observación clave de hecho eh que no la ané en las slid pero me alegra que lo hayas mencionado eh todos entendieron eso si ustedes miran la compuerta 3es está la comporta 3 es w6 por w5 no pero w6 es w2 + w3 Entonces nosotros podríamos escribir w2 + w3 por d5 ig w7 y ahí en esencia nos estamos sacando el chequeo de una compuerta está

o sea juntamos dos restricciones y Y eso no nos no nos hace no cumplir con esta forma que les había planteado No eso es interesante ahora ahora vamos a ver por qué pero es como una especie de optimización está para tener menos cosas que chequear eh buena observación Sí bueno Y acá medio rápido podemos escribir todas las demás de la misma manera y está OK no y un detalle más es que si hay cosas que si por ejemplo tuviéramos inputs no cuyo valor es conocido y por ejemplo entran acá Este w1 por w2 sería por ejemplo si

esto vale dos no sé sería 2 por w2 entonces también haí condens eso y lo podríamos juntar con otra compuerta eso son detalles no quiero andar mucho en eso pero pueden verlo después y hay material linkado para para bien como les decía transformamos acá no O sea pasamos de esta visual que es el circuito a un set de restricciones a un set de de cuentas que lo pueden ver como un un conjunto de Eh sí de restricciones que que tienen que cumplirse Y eso es lo mismo es la misma cosa no o sea es el circuito escrito de otra manera es como que lo lo

achat a una forma bien sí Entonces ahora y y vamos a poco con esto porque quiero quiero que lo observan bien esta representación que hicimos acá la vamos a pasar a una representación vectorial está Sí primero vamos a definir este vector que incluye a todos los cables y el uno y el uno justamente es por eso de que les decía que en esa representación reducida el uno es una constante la podemos sumar multiplicar lo que fuera y

tiene que estar ahí como como parte de nuestro conjunto de variables está y ahora va a quedar clarísimo Por qué Y luego tomamos el producto interno bueno que se me fue el Ah bueno tenía una imagen más la perdí la perdí vamos a hacer así Si me acuerdo no sé qué pasó con esto después la después la listo y qué quiero decir con el

producto interno ya que no lo puse ahí les digo acá Todos saben lo que es el producto interno no de dos vectores es una especie de multiplicación eh les voy a mostrar les voy a mostrar así lo lo tenemos Si nosotros tenemos dos vectores B1 Y b2 sí eh Y ambos tienen un largo un largo n Sí o sea tienen n elementos el producto

entre B1 y b2 es la suma elemento a elemento de la multiplicación de cada componente o sea B1 1 por b2 1 el primer elemento más B1 2 por B 2 2 + b13 * b23 y así sucesivamente o lo que es lo mismo la sumatoria de esos elementos multiplicados no

Sí o sea es la eso la multiplicación elemento elemento también lo pueden ver si si se acuerdan algo capaz de de cálculo lo que fuera eh si escriben los vectores como fila sí esto sería equivalente a transponer el segundo y multiplicarlos así y si si los escriben como columna es al revés bien Eso es el producto interno Entonces por ejemplo para representar esta restricción la tres fíjense que tenemos w5 por w6 es igual a w7 lo que vamos a hacer es tomar este

vector sí que son nuestras nuestras variables y vamos a tomar este vector Sí qué es lo que va a pasar acá fíjense que si multiplicamos y hacemos el producto interno no de W y L esto por esto 1 por 0 es 0 w1 por 0 es 0 w2 por 0 0 y así hasta que llegamos a w5 que hay un 1 y esto dado W 5 después estos se cancelan estos se cancelan estos se cancelan Y estos se cancelan o sea cuál es el resultado de w w por por l en este caso W

d5 Está bien entonces es como una especie de vector selector vamos a decir no como que nos selecciona solo ese elemento podemos plantear otro así que selecciona w6 y podemos plantear otro Así que selecciona w7 Ok entonces fíjense que si tomamos todo esto no y lo pasamos a una expresión no se asusten con esto lo que estoy diciendo acá es esto por esto w5 no w por r da w6 y w por o w Entonces esto de acá abajo es exactamente lo

mismo que esto yo mir de costado eso o sea es como hay que hacer el ejercicio cualquiera secreto entre comillas noando todav acá Estoy construyendo la maquinaria que vamos a usar Entonces tranquil entonces si hacemos esto para

acada compuerta hacer el vector r l y o en realidad l r y o se vuelven matrices no porque tenemos de aluna manera de alguna manera lo que estamos haciendo es tenemos W de este lado s voy lo voy a transponer para acuérdense que es como la multiplicación así y este lado tenemos una matriz que tiene el L de la primera compuerta no el L de la segunda compuerta y así

hasta la última no Entonces cuando multiplicamos todos estos vectores por todo esto lo que nos da esto es un vector que tiene el valor de la compuerta un el dos el 3 y así a la n no hasta N O sea estos valores son esto de acá no de cada compuerto lo mismo con la otra y lo mismo con la otro está entonces a esto le voy a llamar l una matriz l está bien Entonces en realidad lo que nos

queda es esto nos queda l * W es ese o quiere decir que es la multiplicación elemento a elemento que no no existe Digamos como operación matricial normal o sea es fíjense que es esto de acá no voy a reescribir acá abajo lo que queremos hacer es l1 L2 hasta Ln por eh R1 r2 hasta rn y esto da o1 o2 o n entonces como hao la multiplicación elemento a

elemento es lo mismo que se escribiera l1 R1 L2 r2 y así no el vector resultante bien me siguen hasta acá sí yo sé que es medio en quilombo pero está bueno que que lo tengan presente Entonces lo último que tenemos que hacer con esto es transformar esto en un polinomio y ahí es donde pasa un poco la la magia si ustedes leen yo creo que les dejo ahora un link eh a un post de vitalic que explica todo esto está bueno si lo quieren leer como material complementario Ahora les muestro el link lo que vamos a hacer es transformar esto en un polinomio está me

puse esto para un polinomio muchachos o sea estamos trabajando con matrices cosas no sé qué bueno Vamos siempre a ir hacia polinomios en en este tipo de aplicaciones porque los polinomios tienen pero la gran sí me quedó mal la animación los polinomios tienen algunas bondades interesantes que ahora vamos a ver entonces Qué es un polinomio antes está hacemos un pequeño desvío un polinomio es una expresión de este tipo Sí donde básicamente tenemos una sumatoria de potencias de El input está multiplicadas por coeficientes hasta un cierto valor entonces decimos

que el grado del polinomio es n en ese caso un grado de polinomio n no puede tener elementos cuy potenci sean mayores a n está y Acá hay algo interesante que es que no sé no me acuerdo cómo lo puse Pero hay una cosa que es una especie de teorema sí o o teema de la gr creo pero no importa hay una cosa algo que podemos hacer sí que resulta que para un polinomio de grado M - 1 Mejor dicho teniendo un set de m puntos siempre hay un único polinomio de grado m -1 que pasa por

ellos ahora lo vamos a ver Esto es interesante y es la herramienta con la que vamos a trabajar muchas veces en en este tipo de aplicaciones y cuando la herramienta Es literal es algo que siempre tenemos que hacer interpolar cosas está entonces voy a ponerles un ejemplo bien tonto y creo que Esto va a ser ilustrativo tenemos dos puntos No qué Qué función pasa por esos dos puntos claro o sea vamos a dibujarlos acá no puede pasar por ejemplo esta función

no O podría pasar esta función pero lo que tiene es que estas curvaturas sí son asociadas a ciertos grados de polinomios por ejemplo esta de acá vamos a ponerla en rojo Sí esta De acá Parece ser digo si lo vemos así un polinomio de grado dos no O sea que va a ser tipo a0 más a1x + a2x cu s si se ve ahí ven esta de acá es un poco más compleja

será una función de un grado un poco más alto no podría ser cco por ejemplo Pero si yo dibujo una recta qué pasa hay otra recta que pase por esos dos puntos no no hay ninguna otra recta o sea esa recta es la única recta que pasa por dos puntos entonces Si volvemos un segundo acá al enunciado este existe un único polinomio de grado M - 1 que interpola m puntos cuánto vale m en este caso uno dos hay dos puntos claro m en este caso vale dos no sé

quién ahí habló pero hay dos puntos no Ah m Perdón pensé que x tranqui tranqui tranqui o sea y en ese caso justamente el grado del polinomio que es el único polinomio que interpola estos dos puntos es uno y es esa recta no ninguna otra entonces eh acá les ponía ese ejemplo de que no no hay otra recta que pasa por esos dos puntos está por más que intentemos entonces Cuál es la gracia que si tenemos más puntos esto no lo puse así que lo voy a dibujar si nosotros tenemos en vez de

dos puntos tres no de qué grado es el polinomio que es el único polinomio que pasa por estos tres puntos cuánto de dos o sea que es una parábola no una parábola es es algo así pónganle no obviamente no hay ninguna recta que pase por esto Aunque podría ser si los tres puntos estuvieran alineados no y seguro que un polinomio de más grado puede pasar pero no es único entonces ahí hay un detalle que no lo puse en la transparencia que es

eh En realidad el polinomio o mejor dicho vamos a volver al enunciado este que existe un único polinomio de grado hasta m-1 que interpola los puntos porque si están alineados estos tres puntos el grado es uno si están no están alineados el grado es dos alineado uno de los elementos hace Cero en algún momento es o sea están alineados entonces simplemente pasa por acá eh Pon grado hasta M men1 es una pequeña corrección vamos hacerlo ya que estamos

menor menor o igual sería s vamos que después lo lo reviso bien me quedó claro esto o sea es algo importante y es algo que tenemos que tener claro de de cómo vamos a operar ahora si tenemos m puntos hay un polinomio único de grado hasta m -1 que es único la vuelta que interpola estos puntos Sí con interpolación de laran está entonces cuál es la gracia y acá está el kit del asunto podemos usar estos polinomios interpolantes para

codificar cosas está fantástico La pregunta es cómo O sea qué qué tenemos que hacer vamos aar acá codificar de alguna manera implica que vamos a tomar algunos valores conocidos Sí y lo vamos a meter en un polinomio no O sea vamos a tratar de meterlo de alguna manera en un polinomio se les ocurre De antemano Cuál es la estrategia para hacer eso O sea no tenemos ciertos valores que se acuerdan que yo le puse w1 w2 w3 y esto lo queremos meter en un

polinomio que codifique esos valores y extraer extraer un valor que sea constante a todos a ver cómo vos habías separado y los W y después habías puesto se un no recuerdo w w1 por recuerdo era la secuencia pero algo así no recuerdo matemática hace tiempo que no tranqui tranqui tranqui sí no no no sé si está no sé si imagino por dónde va Lo que estás pensando pero quédatelo en la cabeza a ver si ahora cuando lo veamos a ver si si iba por ahí eh perdón pero como que no no sé

si no sé si seguí e Pero eso fíjate y ahora me decís está alguna otra idea capaz o si revelo de la magia acá no sé si me acuerdo algo que era IB como haciendo polinomios más pequeños y después los iba sumando era como hacer un spine no me acuerdo bien la frase pero era algo así queb haciendo conectando polinomios de grado más pequeño y así ias interpolando sí había una técnica que hacía eso pero acu era spine no era spine algo así no esa es otra cosa que también no se usa para estas aplicaciones pero las SP son

formas erol fin no va interpolando de apartes pero nosotros queremos un único polinomio que interpole todo igual hay algo sumar cosas Per bueno les digo cómo es el asunto a ver si alguno lo estaba pensando y no se decir acuerdan que teníamos esto no Este era nuestro circuito que lo habíamos pasado a un set de restricciones y nos habíamos olvidado del circuito en sí mismo no dijimos que esto lo habíamos separado en en left right y output es l r y o no entonces lo que Les propongo es lo

siguiente tomemos todos los valores de l Sí y digamos que son el valor funcional del de un polinomio O sea si este polinomio por ejemplo es l de X es igual I no Sí o sea da un valor yo lo que digo es bueno elijo por ejemplo como como como x el número de puerta entonces por ejemplo l1 y evaluar este polinomio me va a decir cuál es el el valor input izquierdo de esa

puerte eso eso es lo que estoy diciendo ahí si yo evaluo l este polinomio que voy a interpolar en el número de puerta me da el valor del input en esa puerta lo mismo con la dos lo mismo con la 3 lo mismo con la cu vieron que esto mapea no w1 a este valor uno a este valor y así sucesivamente puedo hacer con los valores de r no el input de la puerta uno es eso el input de la do es eso técnicamente no no es así porque los ordenamos de esta manera y se acuerdan que en realidad

este es input izquierdo y este es derecho pero con la forma que lo ordenamos queda queda de esta manera O sea no estamos hablando técnicamente de inputs ahora que pienso pero creo que como para hacerse una idea Por lo menos tenemos los out que son lo que está a la derecha piénsenlo más que como input de las puertas como término izquierdo y término derecho de estas ecu entonces son claro son est ahí esperando para entrar no no

está hasta acá Venimos bien Sí yo sé que que es pesado pero Entonces miren lo que voy a hacer cada uno de esos sets verticales son cinco puntos no fíjense que en realidad en realidad puedo escribir esto Por ejemplo si tomo L2 otro vamos l3 no l3 es igual a w 5

bien estas dos cosas constituyen un punto acuérdense que w5 va a tener un valor asociado por ejemplo imagínense que dio 7 en la evaluación cuando yo estaba viendo todo el circuito Entonces estamos diciendo que tenemos un punto que es 37 y para cada uno de aquellos voy a tener valores no voy a tener por ejemplo dos 1 ya está ahí voy a tener 4 No sé w6 bueno no 4 pónganle no Estos son puntos no fico Son

puntos sea que lo voy a interpolar está bien Tengo cinco puntos polinomio de qué grado voy a obtener cu o menos no entonces Interpol cada uno de esos sets obtengo un polinomio que representa esos puntos esos valores que yo estoy and si yo le pregunto al polinomio Cuál es el valor del término izquierdo de la compuerta un me va a escupir w1 no Esa esa es la gracia justamente yo estoy calculando un polinomio que cuyos valores funcionales yo conozco en

ciertos valores no pero como es una función por ejemplo en seis Esto va a dar otra cosa no voy a evaluar l6 me va a dar faa frita No sé no importa pero yo sé que en 1 2 3 4 y 5 me da exactamente los valores del circuito Y eso es importante porque está codificando la información y otras cosas más que no nos importan está bien Y estos polinomios tienen un una propiedad interesante no fíjense que yo puedo escribir ese polinomio ahí sí

l x * RX - o x está antes de decir no hay que tener miedo vamos a pensarlo un segundo Por qué por qué Qué tiene interesante escribir eso de esa manera Esto es para que de cero no está ahí estás básicamente haciendo lo mismo que cuando las compuestas exactamente voy a escribirlo acá grande p igual L por r men o esto no quiero

no ven ahí bien el pizarrón intencionalmente puse no puse las x porque lo que quiero hacer es el ejercio justamente Qué pasa si yo acá pongo por ejemplo 3 no evalúo px en 3 Y eso es lo mismo que evaluar todos en TR No qué da esto cero Claro porque esto es exactamente lo mismo que estos valores como está codificando estas cosas evaluar esto acá es lo mismo que ver la restricción 3

y lo podemos ver no porque l3 que es w5 r3 que es w6 no y o3 es w7 y Nosotros sabemos que w5 por w6 es igual a w7 Entonces w5 por w6 men w7 sencill Y esto es interesante porque lo que nos quiere decir esto es que en los valores que usamos para codificar que son 1 2 3 4 y 5 p tiene

raíces vale Cero en esos valores y en otros lugares bueno no sabemos pero podría tener raíces Pero sabemos que en estos Sí o sí tiene raíces está bien s eso es interesante porque vieron que sacamos del medio la matriz no s qué y ahora tenemos unos polinomios que van a ser unas expresiones tipo No sé px ig a0 + a1 x capaz que no tiene término 3 entonces digo y hasta a Bueno ya que son así no dijimos que el máximo grado era cu

entonces detalle si sumamos saben que está mal es acabo decir porque hay una multiplicación de polinomios entonces puede subir el grado esto llega H x6 no tenemos este polinomio que yo lo miro y esto no tiene nada que ver con el circuito van a ser valores que no sabemos acá hasta que lo calculemos sin embargo este polinomio lo evalúo en esos valores particulares y da cero O sea que algo dice sobre el circuito Sí entonces había puesto esto que tiene especial pero en realidad justamente

Esto es lo que tiene especial Sí y después dejé una pregunta acá nunca hablamos del Cómo se interpola solo les dije que se puede hacer no creo que está un poco por fuera del scope de hoy porque si no nos vamos los locos Pero hay dos algoritmos uno es el normal o el digamos el estándar que es la interpolación de la grange y después hay un método rápido que se llama la transformada discreta de furie que es lo que se usa porque es mucho más rápida No importa está ahí si quieren verlo después lo dich bien cómo vamos venimos

bien son las s no sé que es pesado pero es es clave esto porque en esta técnica particular que que vemos que empieza por R1 cs usamos polinomios pero en todas las demás O sea la forma de codificar cosas va ser usando polinomios va a ser agarrar un set de cosas y decir voy a hacer un polinomio que encode estas cosas esta manera y el verificador va a chequear viendo valores de polinomios que es clave y de hecho es una herramienta interesante o sea que para el circuito en sí o para para el tema de de zk es

muy importante el orden en el que entran las cosas al circuito que armamos sí es importante que ordenemos de alguna manera las cosas o sea si yo miro el circuito y le pongo puerta uno a a una puerta y después Mira otro el mismo circuito pero esa la toma como la puerta 5 tiene problemas sea no van a coincidir las las codificaciones O sea que esto de numerar identificar las puertas es clave en en digamos la representación del circuito para que el mismo circuito el circuito que estamos viendo sea

exactamente el mismo no basta solo con que los cables estén bien sino que el orden de las puertas sea el mismo en en cuanto Cómo se numeran está sí perfecto bien bueno respiramos profundo trancamos los dientes y seguimos bien Esto es lo que les decía las raíces son interesante y esto si bien está muy bueno no es suficiente eh Acá hay hay algunas preguntas que podrían surgir que no no Espero que surjan pero tienen temitas ahí pero es un

pasito que dimos o sea tenemos un un polinomio que en los valores de las compuertas como dijimos recién sabemos que tiene raíces Y eso es porque codifica al al circuito y acá les dejo el link a eso que les decía de vitalic después lo en la presentación lo buscan si quieren leen está bueno el artículo está explicado por él y sus formas que es bastante estricto vamos a decir yo que riguroso es la palabra entonces bien antes de seguir acá eh vamos a hacer una mini

pausa para explicar algo que es muy importante es muy importante y que ayuda a poder hacer un par de cosas un par de magias eh un momentito más adelante vieron que nosotros codificamos en los valores de las puertas no en 1 2 3 4 5 ya eh si bien eso está bien Es válido también podría elegir cualquier otro número no es decir la puerta un le asocio el valor 17 de entrada y bueno eso es d pongo el valor del inut lo que

fuera en realidad hay como otro dominio que es más útil en vez de usar números consecutivos que son las raíces de la unidad No me maten pero son estas que están AC es qué será bien las raíces las de Raíces de la unidad son valores en en nuestro conjunto campo finito tales que cualquiera de esos valores a la d da uno está entonces yo antes de venir iba a mostrarles un ejemplo o sea Iba a preparar un ejemplo pero no llegué Así

que capaz que puedo usar algo que les mandé por WhatsApp que estamos eh lo tengo acá se acuerdan que cuando cuando me pidieron un ejemplo del protocolo de yo les escribí una hojita la banda de grupo y una de las cosas que hacía era cuando nosotros trabajábamos en F7 No yo les había dicho Bueno si ustedes arrancan G = 3 no y empiezan a hacer g a la 2 mod 17 y lo calculan esto da 9 No porque 3 a

la 2 es 9 y mod 17 si hacen g a la 3 mod 17 Esto es lo mismo que 9 por 3 27 esto da 10 no está bien s estoy y así puedo seguir No yo seguía y seguía y seguía tiene la ojita en WhatsApp Si quieren verlo y una vez que llegaba a g a la 16 16 esto a un sí se acuerdan entonces fíjense que yo voy a reescribir esto de otra forma está

voy a reescribirlo como H es igual a 1 3 9 10 13 y así hasta el final los valores que están en en cosa no ven la similitud esto es 3 a la 1 esto es 3 a la 2 esto es 3 a la 3 No sí te tapa ahí la la Entonces qué estoy diciendo que 3 en este caso es una 16 raíz de la unidad hay un conjunto de 16 elementos sí que cualquiera de ellos

elevado a la d da uno pueden hacer la prueba si hacen 3 a la 16 da uno ya saben si hacen 9 a la 16 17 también da un eso es una propiedad de módulo y potencias está entonces Más allá de de entender Este ejemplo que creo que está bueno ustedes me dirán Por qué no si es mucho más sencillo decir bueno uso un dos 3 está todo bien bueno resulta que usar este conjunto es bastante más cómodo borrar todo es bastante más

cómodo no por comodidad y por que te permite hacer cosas más cómodo porque justamente poco más laxo relajado las raíces de la unidad como un detalle fíjense si pueden encontrar otras de Raíces de la unidad o sea Por ejemplo si tuvieran que encontrar tres raíces de la unidad o sea un conjunto de esta forma h2 h3 fuera 1 así tal que W a la 3 es 1 o mejor

dicho cualquier H la 3 sea entrar uno así en en módulo 17 si quieren está un pequeño ejercicio o prueben con tres o con cuatro lo que fuera si están muy embolados en estos días Si no no lo hagan no se preocupen pero es un lindo ejercicio porque también se desprenden algunas cosas que de hecho están comentadas en la pregunta esta picante entonces Ah mira que el link abo entonces una de las cosas interesantes de todo esto es que pizarrón

no y recapitulando un poco lo que decía recién se acuerdan que nosotros teníamos la expresión esta p es igual L por r men o no y hoy dijimos que si la evaluamos en por ejemplo vamos a ver el otro color en uno esto tenía una raíz no porque esto por esto menos esto era lo mismo que la restricción entonces todo se cancelaba Qué pasa ahora los puntos en donde voy a codificar no van a ser 1 2 3 4 van a ser por ejemplo W al cuadrado

está por eso fue el conjunto que este que definí sí o w a la 3 o w a la lo que fuera en este caso preciso las raíces quintas de la unidad o sea voy a codificar en w0 w1 w2 w3 en realidad es Omega estoy diciendo W pero es Omega voy a codificar en estos cinco valores y fíjense Que obviamente Esto va a estar acá no va a ser así y Esto va a dar cero también porque voy a elegir todos estos valores para

que codifiquen a las restricciones me siguen bien H acá o estoy sí Y esos valores de W son los mismos que teníamos inicialmente o o no tienen ningún tipo de relación con no tienen relación Yo sé que capaz que el símbolo le decía esto es Omega eh confundo un poco es el símbolo que se usa normalmente pero vamos a ponerle otro símbolo vamos a en vez de usar Omega voy a usar otra letra griega las raí estas exao o sea lo que estoy diciendo en

realidad es Si volvemos un poquito para atrás vieron que L2 es 1 no entonces o sea originalmente teníamos que l 2 es 1 que quiere decir que estamos codificando el 1 en el valor 2 esto lo voy a cambiar por l de Omega 1 = 1on es como que se corre uno para atrás porque empieza cero esto como los ar en vez de l3 igual a w5 voy a tener l bueno dijimos l de mu 2 es igual a

w5 esto es un número no sea mu2 en el ejemplo que les había dado era se acuerdan lo que cambia básicamente entonces que ahora tenemos una interrelación entre todos los números que elijamos para nuestro set no son un siguiente el otro sino que están tod rel por esa condición exacto y de hecho es interesante porque están relacionados de una manera muy copada que es si yo tengo por ejemplo W a la 4 o Omega dale con el Omega mu a la cu no y yo tengo mu a la 3 lo único que tengo que hacer es multiplicarlo por mu para llegar al siguiente valor O sea la interrelación es

esta y para ir al valor anterior lo que hago es multiplico por la inversa entonces Está bueno porque mismo podemos podemos saber si queremos establecer alguna relación entre esta raíz y la siguiente a nivel de los valores codificados la forma de hacerlo muy fácil es multiplicando esto Ahora vamos a dar un ejemplo si es que me da hoy esas operaciones son operaciones normales ahí módulo siempre módulo mó todo es módulo que men1 era la transformación esa que el -1 es la inversa

modular exactamente si si lo pensas justamente se acuerdan que mu a la cero mu cer obviamente es 1 entonces lo que estamos haciendo acá al multiplicar por la inversa modular es usar la definición no O sea mu por su inversa da uno está bien se va notando cabitos No creo que de a poquito todo entonces volvamos para adelante volvamos al futuro

Entonces qué es lo interesante de esto vamos a borrar todas estas cosas hay un teorema que lo mencionamos en clases anteriores que es de un señor que se llama Descartes sí que es que cualquier polinomio es divisible por un polinomio de la multiplicación de las raíces en esta forma no donde Estos son las raíces sí Entonces como nosotros tenemos eh que que los omegas a la

d siempre dan uno Sí en realidad este polinomio que les escribí ahí que es Omega o x a la d - 1 Cuáles son las raíces de este polinomio la que tenía el H es el conjunto H Sí entonces este polinomio como se puede expresar Si se quiere como esa multiplicación no de X eh menos bueno -1 por x- mu por x- mu a la 2 y así sucesivamente como sabemos que esto es

divisible por los elementos de H seguramente hay se relaciona acá más menos algún término probablemente pero la gracia es que como esto es divisible entre estas cosas también el polinomio cuyas raíces son el conjunto H es divisible por ese polinomio que está ahí está entonces cuando dividimos polinomios nos queda un cociente y un resto no O sea si si nosotros dividimos dos polinomios voy a escribir como notación de división normal no lo

dividimos entre un polinomio divisor esto da un cociente que es otro polinomio y un resto no lo que hacemos Es al decir que es divisible Es decir que esto es cer no lo que quiere decir que es igual a q por d es igual a q por d cociente por como si fueran números No imag yo lo que hice ahí fue reescribir un poco sustituí d por el polinomio y lo pasé para el otro

lado bueno y ahora edes me dirán esto para qué cor no sirve o sea es como venimos dando vueltas y vuelas bueno porque esta expresión en particular es super útil porque se puede aplicar un lema sobre ella que es el lema de sch ahora Les explico bien que no se preocupen pero quiero asegurarme de que venimos bien porque no quiero tampoco como tirarles con todo y que sea mucha información cuéntenme cómo vienen y si hay dudas hasta acá si precisamos minuto de respiro tampoco quiero subestimar a nadie si quieren seguir yo voy hasta el final pero cómo están ahí en el chat miedo sin miedo me encanta que Ten

miedo no hay que tener miedo bien quedó el mensaje me encanta Perfecto entonces recapitulando medio rápido teníamos el circuito lo evaluamos teníamos que se llama la la traza computacional que son esas tablitas Y empezamos a codificar las tablas en polinomios armamos los polinomios para que tengan raíces en los valores de input y después armamos esto ahí que parece que todavía nos ayuda mucho está pero este aquí que sí porque está el lema de shart simp curiosamente No no supe el nombre del lema hasta mucho Después de haberlo aprendido y me empezaron a hablar él y no sabía de que

me hablaba y desp Ah pero claro bueno así que les presento a schart de a poco tenemos un polinomio de grado d que lo vamos a trabajar en un campo finito como venimos haciendo Entonces si yo tengo el polinomio no vamos a dibujar AC obviamente en un campo finito la el polinomio Son puntos no está que si lo extendi a los números reales

sería una cosa así tal vez no pónganle pero no son puntos porque solo lo evaluamos en puntos discretos entonces si yo les digo tengo un polinomio de grado eh m acá no pregunta Cuál es la probabilidad de si yo elijo un valor cualquiera del todo el campo finito de que justo p de ese valor sea cero la la probabilidad elado eso no sería la cardinalidad de aj bueno abajo abajo tienes de P O sea

todos los posibles valores arriba de las raíces no ex exactamente el un polinomio de grado d tiene hasta de Raíces cl y obviamente puedo elegir uno entre p elementos por lo tanto es tal cual lo que dice leel la probabilidad de elegir un valor al azar y que justo haya elegido una raíz es d sobre p o menor o igual a d sobre d sobre p porque puedo tener menos de D raíces no Entonces está parece un como algo inofensivo No pero lo interesante es que si p es muy grande que normalmente pasa porque los campos

finitos son bastante grandes y las raíces son pocas si p es mucho mayor a d esto es casi que imposible está o sea realmente es una probabilidad muy chica Sí entonces lo que dice el lema deip es que si yo elijo un valor al azar está y justo ese valor da cero es muy probable que el polinomio sea exactamente cero O sea que sea el polinomio este o dicho de otra manera no para cualquier valor de X el polinomio es cer0 porque es muy improbable o sea lo lo más probable es

que si el polinomio no es este y yo elijo un valor azar no me de cero es lo que estamos viendo ahí s entonces si yo elijo un punto al azar y no y me da cero puedo decir con alta probabilidad que ese polinomio es exactamente el polinomio nulo no Y también ustedes me dirán Para qué sirve eso bueno sirve para comparar polinomios Porque si yo tengo que F es igual a g paso G para el otro lado sí Y si yo le llamo a esto H si son iguales estos

polinomios sí esto tiene que dar cero Entonces miren esa expresión y miren la expresión de recién ven la similitud sirve para comparar polinomios entonces la conclusión acá es si al elegir un punto al azar resulta que F es igual a g entonces con muy alta probabilidad F y g son la misma función y ahí transformamos algo que parecía bastante inocente en algo que

ahora nos va a servir y no hay entonces volvemos a lo que teníamos recién yo lo que quiero demostrar de alguna manera es que conozco un q conozco un p y conozco un q tal que se cumle esta relación pasar Yo soy el probador yo sé cómo codificar no como codifiquen correctamente también puedo calcular muy fácilmente

q sí bien entonces si vos venís no y me decís Che decime cuánto vale p en en un punto No y me decís y aparte decime cuánto vale Q en un punto cualquiera yo con esa información puedo chequear esto Y de alguna manera lo que me estás diciendo vos acá es que conocés un p y un q tal que se cumple esta

relación y fíjense que ni siquiera esto tiene que ser en las raíces de la unidad esto se cumple en todo El dominio está entonces si vos podés calcular bien estos p y q porque conocés la traza de verdad chequear esto Debería ser algo que vos podes hacer fácilmente o sea yo te puedo dar dos valores que cumplan esto porque conozco p y q si yo no soy realmente no soy honesto y no tengo la traza y no puedo calcular p y no puedo calcular q tampoco Cuando vos me pidas estos valores yo voy a tener que inventarme valores que generen este resultado

está y lo voy a tener que hacer repetidas veces porque se acuerdan que en en el protocolo había comunidad y vuelta suena como que va tomando forma lo que les acabo de decir igual no es suficiente no es suficiente pero va encaminándose no quiero tampoco discutir porque no es suficiente Pero bueno vamos discutir verificador puede evaluar PS

y y mandárselos a este y este Elo si esto hacer el chequeo que escribimos recién Si eso da igual con alta probabilidad podemos decir que estos realmente están bien calculados si lo piensan un rato después esto capaz que les surgen algunas preguntas Como por ejemplo por qué vos no me podes inventar dos valores acá cualquiera que cumplan eso que se puede eso es la

clase que viene pero empieza a tomar cierta forma empieza a ver como una estructura acá que tiene sentido y este p no olvidemos nunca que está codificando de alguna manera al circuito se que nos da información del circuito aparte de todo acá les puse un poquito el cuentito el probador va a evaluar el circuito y va a calcular usx y q y qx pero en realidad lo está haciendo en un valor que es un challenge del verificador y Bueno un poco lo que puse el hecho de cómo hace para ver si esto es válido y no me está tirando fruta

tiene que ver con algo medio Místico que vamos la clase que viene vamos de tiempo Bueno nos queda media hora Cómo estamos Yo di que iba a ser pesada no me dian que no bien entonces lo que queda es si no me equivoco Ahí le dejé un tema para analizar si quieren también pero me imaginé que medio destru hay una buena noticia ual o sea todo esto que estamos aprendiendo es como el trasfondo posta de todo esto

Pero esto nunca lo hacemos nosotros Nunca lo hacemos nosotros esto obviamente alguien lo programó s pero en realidad lo hacen los compiladores Está bueno entender que es lo que pasa Porque pueden aparecer también errores o ataques en ciertos protocolos Y eso va a estar a este nivel no a nivel de lo que hay más arriba y nosotros sin pruebas confiamos en que ellos lo hicieron bien Ah bueno claro ahí tenes que ir a auditar el código No pero confias en ellos con sir no exo clo bien los polos en la vida real est

son una locura o son de grados no no son de grados coherentes o sea no no s no sé si decirte números porque tampoco he visto mucho como para tener tanta certeza pero no creo que tengan grados de más de cient no creo que sea más que eso o a lo mejor 1000 pero te averiguo para prximo igual los los campos finitos que usamos por lo general son Campos grandotes O sea no es algo que rondan los miles de elementos rondan los ni se decir el número entend o sea de cantidad de elementos eh si

pueden después busquen un número primo Que Se use para generar un campo normalmente van a ver que es un chorizo enorme enorme De hecho yo después le pongo uno pero es O sea imagínate que si lo empiezo a escribir así No capaz que me ocupa todo esto el número o sea es grande el circuito visualmente no se puede tampoco eh si el circuito s o sea es manejable o sea lo puedes representar y está todo bien estos son los posibles valores de los inputs y outputs que están dentro de

este Rango Bien voy a borrar mientras que la complejidad Entonces no radica en el circuito en eso sino en la probabilidad que vos tengas encontrar un número dentro de ese dataset que al azar exactamente exactamente incluso a Fuerza bruta Tal vez no sea tan fácil eh encontrar ese número si yo lo tengo que que inventar No pero si yo conozco los los polinomios y demás y realmente conozco el circuito es trivial encontrar ese valor Más allá de hacer el cálculo no

bien bueno bien Vamos arriba lo último que vamos a ver es clonk eh la aritmetización O sea lo que les mostré recién de tomar este circuito y escribirlo como multiplicación igual a algo Y pasarlo a a a esa multiplicación de polinomios o lo que fuera es lo que se llama una aritmetización está es tomar el circuito sus valores la traza y transformarlos en polinomios que representen ese circuito o que codifiquen su información Eso es arit metiz es circuito paso a

polinomios a través de aritmetización pero no es la única aritmetización que hay O sea hay otras estrategias para codificar el polinomio Perdón para codificar el circuito en polinomios hay varias estrategias y hay otras formas de aritmetik que yo creo que les comenté también o sea otra aritmetización pero es como lo mismo no O sea tenemos que un cálculo lo

aritmetización hago algo más para terminar de cerrar la sir queo eso es la clase que viene por eso va en orden va tomando forma entonces en plon que viene bueno viene pl que es la técnica en donde se usó este esta aritmetización que vamos a ver por primera vez es otra manera de aritmetik que creo que a pesar de que es compleja es como más natural los pasos que vamos a tomar está tenemos que hacer

lo siguiente tenemos que codificar las variables de entrada de alguna manera después codificar todos los cables en el medio y después empezar a codificar las puertas si si son de multiplicación o suma y después estas restricciones que hablamos de que este cable sale para dos lugares Entonces todos estos valores tienen que ser iguales parece más natural es como una construcción más natural de cada restricción Entonces vamos a hacerlo ya que estamos por ejemplo tomamos este circuito que tiene los valores mal vamos a necesitar en total 19 raíces de

la unidad porque vamos a tener que codificar cada uno de los valores de allá y son 19 Si los cuentan que es 5 por 3 por cada compuerta más los cu inputs y bueno vamos a encaminarnos en esta Aventura que nos queda sí En inglés cómo es encoding coding tal cual s capaz que no sé si es la traducción correcta peroo creo que sí Entonces vamos por partes en los inputs

sí O sea fíjense que tenemos este conjunto H sí que va a ser w 0 W A la 1 W a la 2 hasta W a la 18 en este caso no eh Y obviamente tenemos que W a la 19 es 1 para o mejor dicho h a la 19 es 1 para cualquier H de este conjunto entonces un detallecito es que podemos usar potencia negas y está bien si

nosotros hacemos W a la men1 qu piensan que va a dar esto como que Vu pasar men2 es y así sucesivamente eso es una propiedad unidad pueden investigar despu sieren entonces lo que vamos a hacer es como ser un poco inteligentes en Cómo manejamos estos estos valores No si Nosotros tomamos se acuerdan que hay en total en

total hay cuatro inputs y después hay 15 cables no entonces podríamos hacer que w0 w1 w2 y w3 fueran los inputs o sea los valores que usamos para codificar y después para acá o algo que podemos hacer que está bueno y que nos ayuda por lo que ahora vamos a ver es hacer que W a la men1 W la men2 3 y cu sean los inputs y después para allá tengamos w0 w1 w2 w3 w4 sigo diciendo W esto es

omega y estos van a ir en grupitos de A3 que esto es la compuerta un esto es la compuerta dos y así sucesivamente Esa es la forma en la que vamos a hacer esto por eso los inputs van con potencias negativas acuerdan que teníamos input públicos los X inputs privados los W están ordenados de esa manera simplemente estamos codificando acá en este polinomio que va a resultar los inputs también usamos el mismo en el mismo polinomio vamos a poner las

compuertas y fíjense que las compuertas son de la forma que pongo acá tienen dos inputs y un output por lo tanto lo que podemos hacer es en est grupito da 3 ir poniéndolos eso se escribe como Omega a la 3k y Omega a la 3k + 1 y om 3+ 2 K es un entero Entonces si K es 0 fíjense que eso es Omega la 0 Omega la 1 y Omega la 2 si es un eso es Omega 3 om 4 om 5 con estos valores lo que hicimos efectivamente fue codificar todo eso que está ahí todos

esos valores pero la traza en sí mismo o sea toda esa tabla no significa nada si no se cumplen las restricciones del circuito no O sea si esto más esto no da esto lo señalo acá si esto más esto no da Esto entonces el circuito no está bien evaluado no Por lo tanto lo que nos falta es aparte de en de codificar todas esas esos valores nos falta codificar las restricciones las restricciones que son que cada compuerta esté bien evaluada sí Y que aparte los cables que tienen que

valer lo mismo valgan lo mismo Está eh un poco lo que acabo de decir adelante para eso vamos a precisar más polinomios Entonces primero las compuertas ya hay un problema con las compuertas que pueden ser adicion o multiplicación sí O sea que si pudiéramos distinguir entre ellas podríamos de alguna manera codificar esto o o pedir que eh eso se cumpla sí o si fueran de multiplicación podríamos pedir Esto está naturalmente

si si mi circuito está bien evaluado naturalmente esto se va a cumplir me sigen O sea si mi circuito Está bien evaluado entonces en una compuerta de adición p a a la Omega 3k + p evaluado en Omega a la 3k + 1 que son los inputs va a ser igual al output que es p evaluado en Omega la 3k + 2 si mi circuito está bien evaluado Por lo tanto eso se va a cumplir siempre y cuando el circuito esté Ok son

iguales si la compuerta vamos vamos a poner dos dos compuertas la compuerta número uno o número cero vamos a poner porque así arranca bien y la compuerta uno Esta es de suma y esta es de multiplicación está bien en este caso este input Cuál va a ser el p a la Omega que o Omega de qué cer

c y después Esto va a ser p om1 Esto va a ser p Omega 2 Esto va a ser p Omega la cuánto 3 p om la 4 y p Omega la 5 si mi circuito Está bien evaluado entonces en est compuerta naturalmente se va a cumplir que p Omega a la 0 + p Omega a la 1 va a ser p omega2 no Y si mi circuito está bien evaluado en este en esta compuerta se va a cumplir que p

Omega a la 3 * p Omega a la 4 es p Omega a la 5 no porque es la restricción sí misma o sea esto multiplica y esto suma está bien Ahora si yo quiero digamos poner todas las restricciones de cada compuerta como en una sola expresión o sea en en un solo polinomio tengo un problema porque tengo esta dualidad está entonces esta parte y la parte que viene ahora no no voy a tampoco entrar mucho en detalle pero si quieren

después la la miran de vuelta y la clase que viene podemos discutirlo más porque sé que estamos cansados Entonces no quiero tampoco pero lo que se puede hacer para codificar esto en un solo polinomio es usar un polinomio selector que es que si la compuerta k es de adición entonces hay un polinomio en el cual pedimos esto está Este es otro polinomio ese es un polinomio nuevo selector Y si la compuerta es de multiplicación pedimos esto podrían

estar al revés es arbitrario pero fíjense que esto también nos da una serie de puntos y podemos interpolar el polinomio s no O sea s por ejemplo en este caso s en w0 es 1 s en w3 no es c eso nos da una serie de puntos y vamos a poder interpolar un polinomio de grado menor que p que son cinco compuertas Así que grado cu que codifica la información del tipo de compuerta y ahí lo que podemos hacer

para usar el teorema este particip de alguna manera es escribir esta expresión después la la miran tranquilos ya pero acá lo que está diciendo de alguna manera es si ese Omega a la 3k es o todo este término se va que es la suma y si ese Omega a la 3k es 1 todo este término se va entonces es uno u otro y claro lo interesante de esto es que acá estamos codificando la restricción de suma multiplicación para todo el circuito entonces con schar siple lo que

podemos hacer es primero calculamos todo este polinomio que va a ser un chocotroco de cosas está igual que los demás en realidad pero todo toda la expresión esa una vez que la procesemos va a ser un único polinomio y lo que podemos demostrar es que todo este polinomio de la izquierda es igual a este polinomio de la derecha usando que fi muy rápido ahí pero sí O sea que con una evaluación de esto estamos chequeando la correcta el correcto cálculo de alguna compuerta y acá un detalle es que estos cositos de acá también se

pueden escribir como Omega la 3k por Omega un detallecito Pero eso también es cómodo por eso hablaba de la comodidad bien última las restricciones deado en esta les voy a pedir un poco de fe porque es un poco entado pero y de hecho esto es como la parte interesante de plon o sea del argumento Que ellos hacen pero fíjense que lo que pasa acá es esto no miren los que están pintados en rojo deberían ser el mismo valor en el caso del nu9 estamos hablando del input 2 que tiene que ser el mismo que el input derecho de la puerta cero y el

input izquierdo izquierdo de la uno que veo que le falta el número está y lo mismo con el 11 que tiene que ser el output de la 1 Ah no no le faltan números est abo eh tiene que ser el output de la un pero a la vez tiene que ser el input derecho de la dos y el input izquierdo de la 3 o sea que tengo que verificar que todas esas cositas son iguales no ahí hay un ejemplo no cómo hago Esto bueno esto Esto sí realmente lo voy a pasar rápido porque ya ya est bando yo en pobre tranqu igual sé que estamos estamos cansados eh las igualdades son de este estilo no O sea Hay ciertos valores que tienen que

ser iguales que se se corresponden con ciertas raíces de la unidad pueden ser más pueden haber más cables que tengan que ser iguales O sea que estas igualdades pueden crecer exacto y tenemos que encontrar una forma de codificar todo este set de igualdades entonces pero me quedaron mal las animaciones un poco la idea es construimos el el conjunto de los puntos donde Las evaluaciones tienen que ser iguales no fíjense que esto mapea con esto si miramos la primera Omega 4 omega y Omega a la 3 Perdón Omega la-4 omega y Omega la 3 todos esos inputs tienen que

evaluar el mismo valor Porque son el mismo cable entonces lo que hacemos Es construimos otro polinomio W que lo que hace es permutar los valores está O sea fíjense que W de Omega a la -4 es w w de Omega es oma a la 3 w om la 3 es -4 es como que los los gira no Ah como lo gira lo que pasa es que podemos verificar para todos los valores de H que se cumple esto O sea que p h p evaluado en H es lo mismo que p evaluado

en dh y como son permutaciones son tres cosas que se tienen que cumplir eh 15 TR O sea que que son 1es es por el caso que agarraste ahí No necesariamente pueden ser cinco pueden ser 10 claro puede ser cualquier cantidad lo interesante es que tenemos que hacer esto para cada uno de esos casos incluso cuando son dos Cuando tenemos el output de otra cosa que va al input de otra también pasa esto no O sea que hay un montón de estas restricciones pero Eh bueno en el caso general pueden ser más y hay un tema acá computacional que esto no es muy rápido y todavía no hablamos

de velocidad ni nada porque esto puede ser bastante bastante complejo entonces hay una forma un poco más rápida de hacerlo que es realmente el corazón de El paper ese eh que se llama el argumento del producto no lo vamos a hablar ahora pero está en la pregunta pante si quieren es un poco entregado pero muy interesante quieren verlo sí no Y esto no se arma nunca gráficamente no gráficamente para que seenda pero no no no son terminan siendo números no más O sea lo interesante Sí es que yo para

poder saber qué restricciones chequear Tengo que leer el circuito si yo no conozco el circuito no sé se me fue Sí sí ya nad quiere más nada si yo no conozco el circuito no sé Cuáles valores tengo que permutar entendés o si yo no conozco el circuito no sé dónde están las compuertas que tengo que chequear la codificación sí y en la práctica nunca va a gráficamente va estar Qué cosa el sí está o sea de vuelta para poder chequear estas

cosas yo necesito Entonces como verificador necesito poder leer el circuito puedo pued en realidad necesito leerlo todo para poder saber en qué partes quiero verificar cosas o para tener la chance de hacerlo donde yo quiera más que nada con este argumento de permutación Pero el punto es el probador una vez que está Armando la prueba primero computa Esa traza computacional que son tablas esas que vimos y después se olvida del circuito Bueno más o menos porque tiene que armar estas restricciones pero lo que tiene son números de ese de esa traza no solamente y después empieza a armar estas restricciones y lo único que

termina el output de todo esto son una serie de polinomios que representan cosas y sobre esos polinomios el el verificador Empieza a preguntar cosas está el verificador lo que hace es decir s Dame el valor de p en Omega 3 p en Omega yp en Omega a la-4 suponiendo que este lo puede pedir porque es un input y puede ser secreto y va a chequear esto de la permutación con alguna cosita más que está en la pregunta no eh pero él tiene que saber que tiene que pedir estos valores y para eso tuvo que

haber leído el circuito porque acá está diciendo Yo espero que estos tres cables sean iguales porque el circuito lo estoy viendo tiene que ser igual en lo que manda el probador la evaluación del circuito s pero no olvidemos que el circuito es como un modelo que es una función deuna manera dependiendo de los inputs Yo tengo un output y te puedo dar la función y te puedo decir mira yo yo hice una evaluación con información secreta y este es el resultado que está codificado en estos polinomios Pregúntame lo que

quieras yo te voy a responder con información válida y ahí te voy a convencer de que yo calcule bien el el output está ahí está el asunto sí Bueno terminamos entonces eh nada un poco a modo de resumen s que estamos muertos lo que vimos es esto no O sea que el verificador va a leer el circuito va a pedir estas evaluaciones s y con conocimiento de dónde están las restricciones va a empezar a chequear estas igualdades usando el teorema este de sch para chequear que Las evaluaciones dan la misma

cosa Va a estar grabado esto lo pueden ver de vuelta pre Sí y bueno Esto lo charlamos un poco por así por arriba pero mapea con esta idea de hay un challenge y una respuesta no el challenge es Che Dame la evaluación en estos puntos si la tenés Sí cómo no te doy la evaluación toma Y vos después verificas no pero se acuerdan que se acuerdan que en el protocolo el

primer protocolo que vimos teníamos el probador el verificador y primero había una etapa de comit se acuerdan que é mandaba un número primero no sé qué después Este elegía ese valor Random que le llamamos el challenge y después venía la respuesta y después Este verificado no Bueno qué vimos esta clase esto Qué nos faltó la parte del comit Dónde juega la parte del comit en algo

que mencioné hace un rato que es en Cómo el verificador sabe que cuando yo le respondo esto no le estoy mandando frut eso es la parte donde el comit es importante lo que va a pasar Es que me va a mandar esto y yo antes de chequear nada voy a decir este PS y que me mandaste pasan alguna verificación que vamos a ver si pasan voy a decir que esto es válido y Voy a proceder a hacer los chequeos que vimos hoy si no no está y una vez que tengamos eso vamos a

tener todo el camino y todos los elementos para construir una prueba de conocimiento cero programable foto en el ejemplo el ejemplo de Willy El ejemplo de va servir mucho no se me ocur es que el comite en este caso es comoo s que no estás poniendo otro libro por así decir entonces como que no ahí el ejemplo no

nos sirve mucho porque capaz que tiene otro libro y me enchufa ahí no pero capaz que si hubiera alguna manera de de verificar que el libro que está ahí bueno por ejemplo Imagínate que vos pones el libro abajo del agujerito vos mostrás y después sacas el libro y se lo das y ve efectivamente que era el libro que est eso sería como un tema Bueno hay un commitment que es el uso de ese libro acá capaz que no no es tan directo ese esa relación pero vamos a ver que hay una forma también de armar eso está O sea que más allá de que de que esto es un poco un quilombo vamos decir la verdad es bastante

información llegamos a algunas cosas que nos empiezan a permitir ver cómo cómo verificar que un cómputo está bien hecho que era el objetivo de hoy eh bueno lo que vimos fueron dos técnicas hay más técnicas hay optimizaciones hay un mundo de cosas esto Una vez que terminemos pueden Investigar un poco lo charlamos hay mucho por ver Pero van todas por ahí y todas todas usan Pol as no vuelta el valor de p en los valores oma infinito eso implica que p tiene que en

algún momento ha visto todo el circuito o no No es que en realidad el que vio todo el circuito es este no este el circuito computado no sea este ve el circuito sin valores este ve el cómputo que claro las tablas por eso pudo calcular p pero después Este cuando le le manda tablas a p no le manda valores sueltos pensa esto no por ejemplo Imagínate la compuerta no que veíamos hoy que tiene p no

sé p6 p7 y p8 no lo que va a ha ser el el pib en este caso el verificador o una cosa que podría ser es pedirle estos tres valores y verificar que son una suma Más allá de que está el polinomio selector y toda la eso que vimos digamos el enfoque más naiv sería bueno te pido estos tres valores y me y chequeo que efectivamente esto se cumple no O sea que lo que revela esto son valores sueltos no a pesar de que ve el circuito sin sin los valores no como que este es el

template sí este tiene los valores de la evaluación p hace para llegar a calcular los valores circuito sin haberlo visto no no pero es el creador clo es el creador claro [Música] Ah este calculó todo el circuito y después construyó toda esta maquinaria para poder expresar cosas de cuentagotas a b pero este conoce toda la evaluación

y un detalle más que no mencioné acá aparte de no revelar los input secretos porque justamente si me piden el la evaluación de p omega men2 y eso resulta que es unut secreto yo le voy a decir no no te voy a dar est porque si no no sería Pero aparte de eso hay otro tema que a ver si los pensar que es si p Tiene grado t vamos a decir no se fue otra vez si p Tiene grado d me puede pedir Todas Las evaluaciones que

quiera tengo que poner una restricción Pues si le doy d má un valor lo puede te puede interpolar y puede obtener p de vuelta y eso no lo queremos entonces hay un límite también En cuántas veces vos me puedes preguntar Sí el otro también supone de cuá grado es Sí podría podría podría inferir cosas pero igual hasta que no tenga suficientes puntos no puedes saber nada Sí entonces por eso también es knowledge porque al no poder volver a interpolar no tiene forma de como atacarte para reconstruir el la traza original A menos que vos le des demasiados puntos y bueno Esto fue la clase de hoy

Espero que no se quieran hacer de jar kiri en este momento pero se fue gente pero bueno está nada eh voy a dejar de grabar y bueno