ZK Workshop #2 - Representación de afirmaciones

Transcript

Perfecto ahí estamos grabando AC les les Confieso que no no mejor mucho el mecanismo de admitir gente Así que lo único que ahora tengo dos espacios Así que es un poco más rápido pero no sea podría podría no no pero si en realidad no quiero mutear las notificaciones lo que quería era que no tuviera que salir de la presentación Pero no importa no importa vamos vamos arriba Vamos arriba

saldrá como sale bueno bienvenidos de nuevo esta es la segunda sesión de este workshop de Z as que bueno retomamos directamente lo que dejamos el otro día y y vamos a que y vamos a hacer algunas cositas más usando como base Estas ideas que vinimos discutiendo particularmente la idea de los campos finitos que estuvimos hablando si estos conjuntos sobre los cuales tenemos definida la suma multiplicación la resta la división entonces rápido

que vimos la clase pasada un poco sobre la anatomía una spr tenemos que hay este ciclo tipo zigzag no se acuerdan que partíamos me dijeron que el pizarrón se ve bien la grabación de la clase pasada Así que vamos a ver si ahí si yo dibujo tipo acá se ve se acuerdan que teníamos un probador y un verificador y como que hacían una especie de zigzag de comunicación s y en eso se mandaban algunas cosas y este al final hacía un check no Franco sí una cosa porque la clase pasada Vos como que habías partido la pantalla cuando estabas esend el pizarrón ahora ahora te ves muy chiquito antes era como no sé se

te veía más grande de alguna forma No sé cómo hiciste eh No creo que lo que hice fue dejar de compartir pero Ah bueno pues puedo hacerlo no no pasa nada eh No no me parece mal no me parece mal eh hacer esas pausas vamos de vuelta Ah ahí ven bien hay un reflejo ahí no sé si perfecto lo que habíamos visto era esto no la idea de que había como una especie de ida de vuelta que podía ocurrir varias veces y eso terminado convenciendo un verificador de al alguna información privada que se había probado bien esto yo no les conté pero se llaman protocolos

Sigma por sig es por esta onda zigzag y ma es por un un tema viejo de estas cosas que que se hablaba antes m de merlí y a de Arthur por có cómo se identificaban estos protocolos antes pero no importa Son detalles históricas Pero bueno vimos esto y vimos que podíamos transformar toda esta de vuelta en una en un solo paso a través de una transformación que involucraba jes acuerdan entonces un poco por ahí s y terminamos la clase pasada diciendo volo compartir terminamos la clase pasada

diciendo que el mecanismo que habíamos estudiado no era muy general y que de alguna manera queríamos Buscar formas de nada de poder escribir afirmaciones de forma más general No aparte bueno vimos herramientas como campo finito sin hases y un poquito hablamos de grupos pero no entramos en profundidad Está bien entonces esto mismo dijimos que no teníamos una forma de representar afirmaciones generales esto era muy específico y la pregunta es un poquito Qué podemos hacer para mejorar eso Porque todo lo demás de este día de vuelta meo que que calza va a estar en las pruebas hacia las que vamos pero la

parte qué quiero demostrar está como medio floja todavía no es un logaritmo se acuerdan que era un valor solo como medio flojo por ese lado entonces un poco la propuesta es la siguiente cuando queramos afirmar algo eh statements acá es un poco confuso en realidad no se preocupen cuá esa parte tanto pero cuando queramos afirmar algo sí lo interesante va a ser tratar de representar ese algo como una expresión matemática Entonces ustedes me dirán representar que mi nombre es Franco Es medio extraño decir bueno es una expresión matemática no pero vamos a ver que capaz que con algunas herramientas

podemos empezar a construir algo está bien acá puse una imagen como esto ya van a ver que es medio Wow pero es es asible sí bien entonces ejemplo básico no no pregunté Pero se escucha bien en la llamada no sí perfecto perfecto bien Entonces vamos a hacer un ejemplo bien básico todos alguna vez jugaron O saben de la existencia del sudoku no y si no jugaron No pasa nada pero se hac una idea no el sudoku eh Cómo es Es un cuadrado grandote normalmente es de 9

por 9 y resolver un sudoku alguien me cuenta cómo cómo se resuelve que tienen que todas las filas tienen que tener todos los números del uno al nueve todas las columnas también y cada uno de estos cuadraditos también así se se resuelve su entonces uno Podría empezar y decir bueno empiezo a jugar no sé Miren esta fila de acá ya tiene un uno esta también esta columna ya tiene un uno entonces este cuadrado no puede tener uno acá acá acá acá acá o acá por lo tanto el uno va acá y así sucesivamente voy voy voy hasta que lo lleno no entonces capaz que

resolver un suo difícil le lleva 15 minutos ahí sentados haciendo eh No verificando que está está bien lo que están haciendo tachando cosas pero verificar que una solución es válida si yo les doy un sudoku resuelto y les digo se animan a ver si está bien es fácil porque yo lo único que hago es chequear cada fila cada columna claro y cada cuadradito es más rápido no entonces un poco esto resolver un suku puede ser difícil pero verificarlo es una pavada es chequear no más en realidad lo lo que chequeamos es que cada fila por ejemplo tenga una suma total de 45 sabiendo que todos los

números son del un al 9 cada columna también cada cuadradito también es son como restricciones no que tenemos que chequear si esas restricciones alguna de ellas falla ya el sub uno es válido está bien interesante no o sea es como una mirada un poco distinta de algo que que es bastante cotidiano yo que sé normal acá les dejé un link dentro de la misma presentación a una pequeña pregunta picante porque esta idea de que verificar algo es más rápido que eh encontrar una solución suena trivial pero está asociado a un problema bastante complejo y todavía no no resuelto que se llama p

versus np es un problema del milenio hasta hay un premio un millón de dólares por resolverlo Así que si les copa ya saben bien Vamos a hacer otro ejemplo que es un poco tal vez no tan natural pero va a ser como una herramienta medio básica Entonces veámoslo inclusion en un conjunto no quiero decir con esto dado un conjunto de elementos s1 hasta sn sí queremos evaluar saber si hay un un valor cierto valor pertenece a este grupo o sea yo te quiero demostrar que este valor pertenece a este

grupo se les Ocurre algo para poder hacer esto hay funciones hay funciones alguna función en particular pertenece pero claro claro claro claro está bien o sea tenemos como que pensar en vez de en función de de estas cosas tipo esto pertenece a esto si hay alguna cosa que podamos evaluar y que nos dé un resultado que nos diga sí o no está ahí ha hay una pregunta los conjuntos siempre eh están ordenados de menor o mayor o pueden estar desordenados pueden estar desordenados

hay problema Ok podrías chequear si es igual alguno Es verdad que puse sl a propósito porque ya vamos a tener que empezar a cambiar la forma que tenemos de pensar los problemas como programadores nosotos deos bueno Esto mis and si Pero eso no nos sirve en este contexto porque vamos a tener que usar expresiones matemáticas vieron que acá esto es una sumatoria no y yo estoy chequeando que la sumatoria sea igual a

45 o sea sumo y evaluo que sea igual a 45 Claro que sea como una especie de bueno miro algo calculo algo y me fijo si esto es lo que yo quiero Entonces les voy a decir cómo es esto porque es interesante es útil aparte podemos hacerlo evaluando esta expresión y ahora Les explico qu es esto porque parece medio tirado de los pelos esto es un polinomio tenemos una variable que es x y después tenemos una una expresión para ese polinomio que es X Men s1 por x- s2 por x- S3 todo así hasta sn

La idea es que vamos a sustituir x por nuestro k y chequear algo saben qué es lo interesante de esto que si cualquiera de estos valores da cer0 todo da cer y Si evidentemente ninguno da cero esto no va a dar cero va a dar algún número que no es cero í esto quiere decir que lo que son s1 s2 y C3 son raíces de este polinomio se acuerdan cuando teníamos un capaz que me ven chiquito ahí pero a ver dejo de compartir cuando de repente en el Liceo o lo que fuera no sé estudiamos una

parábola pónganle x cu + 1 no Y la dibujamos eh saben qué menos un mejor fíjense Cuando esto es cer0 da esto es 0 da -1 y después esto sube para acá esto sube para acá y en 1 y -1 tiene sus raíces Por qué Porque cuando x es 1 No si esto es FX cuando claro cuando eso acá arriba no cuando tenemos F = 1 esto es 0 Cuando tenemos F = -1 esto también es 0 bien o

sea que son raí y de hecho esto lo podemos escribir como x + 1 por x - 1 Ah por un teorem mit de un señor que se llama Descartes sí bastante conocido y fíjense que esta esta expresión este tipo de expresión es lo que tenemos ahí no O sea que no no es nada muy misterioso en realidad parece Porque no es como la forma en la que estamos acostumbrados a pensar en estos problemas pero no no es nada loco está bien y después nada aclarar ese símbolo de ese pi enorme es el símbolo de un producto así como está la sumatoria esto es un producto de

elementos se es x- s por x- s y así hasta llegar a n entonces de vuelta si creo que acá lo escribí F de K vale 0 si K está en el conjunto si no no si K es igual a s2 todo esto vale cer porque s2 men s2 0 se cancela todo está bien son las raíces s claro esto O sea si lo desarrollamos empezamos a hacer acá distributiva y vamos a llegar algo parecido a esto no

lo vamos a hacer porque no nos importa acá y ahora vamos a ver que tampoco nos importa en general pero bien se entendió esta idea es como un cambio un poco en la forma de pensar acerca de de lo que queremos representar bien la llamada no veo si ponen manito eso no veo porque no estoy no estoy en la pantalla de la llamada así que se me auda bien bueno bien bien Perfecto entonces de alguna manera este vemos que en estos dos ejemplos Por más

que son simples hay como una estrategia de representar ciertas cosas con expresiones matemáticas Entonces sería bueno que digamos podamos construir algún tipo de maquinaria que nos permita crear estas expresiones está bien medio abstracto así como lo digo ahora pero van a ver que en un momento va a empezar a parecer natural Yo quiero encontrar alguna forma de construir estos polinomios está de alguna forma que sea bien estructurada y que no tenga que escribir yo x cu + 1 + x a la 3 o sea como que no quiero usar es como imagínense

que no quiero tener que estar pareando algo a un formato que quiero tener algo estándar formato claro medio abstracta como un modelo simple que nos permita construir cualquier polinomio y ya conocemos algo interesante que es de ese estilo No imagino que muchos de ustedes habrán visto más o menos cómo funciona una computadora y saben que atrás de todo lo que hace una computadora hay con puertas lógicas no entonces capaz que analicemos por ahí vamos a ver qué paralelos podemos encontrar Entonces les puse acá una expresión siempre me confundo Cuál es el

I y el o creo que el I es este y el o es este pero por las dudas de si está mal digo no me linchen sino que sepan que me los confundo entonces acá estoy diciendo Bueno si yo quiero escribir la afirmación lógica a y b o c o Perdón yid Tengo una forma de construirlo a partir de componentes chicos no que es Armando un circuito así eneng una compuerta and donde entran a y b bueno no puse las entradas pero se imaginan Cuáles son a y b que el resultado lo combino con c y el resultado de eso lo combino con d y la señal que obtengo es la respuesta de

toda esta expresión lógica O sea que yo le puedo poner cualquier input acá como si fuera una función Sí y me va a retornar un resultado cer o uno Está bien entonces vean interesante es como que estamos construyendo una función acá en realidad donde tenemos cuatro variables y una salida que es el valor funcional bien no s si lo han pensado así alguna vez pero es eso en realidad no es una función estamos evando una función entonces aparte y creo que bien importante hay dos componentes que son muy interesantes que representan la la suma y

multiplicación que son el xor y el and está vamos a ver la tabla un segundito no en el caso del xor si a es 0 y b es 0 0 + 0 0 No si a es 0 y b es 1 0 + 1 1 si a es 1 y b es 0 1 + 0 1 y si a es 1 y b es 1 1 + 1 10 no cero está eso ahora lo vemos un segundito y en el caso de l bueno lo hago más rápido No pero tenemos que si alguno de los input es cero es absorvente nos da cero si los dos son uno es el único caso

donde nos da un O sea que and y or representan dos operaciones bien conocidas suma y multiplicación pero falta el tema del carry acá sea si sumamos un y un 10 y el Car Acá no está les hace sentido que la suma de 1 + 1 sea 0o en algún contexto el módulo en el módulo qué módulo dos Exacto Entonces si nosotros tenemos el campo finito f2 tiene elementos 0 1 1 + 1

es 2 pero 2 módulo 2 es c0 y dos es primo aparte Entonces es un esto es un campo finito Entonces miren interesante no como que tenemos eh la suma y la multiplicación definidas como circuitos bien conocidos genial pero estamos limitados a este campo está entonces Acá está la idea gigante gin como el mem este que es por qué no extendemos esta idea de estas dos compuertas que nos permiten representar cualquier polinomio

a campo finito más grande entonces qué es lo que tenemos que cambiar que los inputs y en los outputs no van a ser 0 un pueden ser 0 1 o más números entonces surge esta idea que ahora la vamos a bautizar y vemos un ejemplo no pónganle Si queremos calcular i o p dex x + a * x + B esto podría ser un circuito para eso no a + x y x + b y el output de esas dos cosas lo multiplico está bien obviamente estas estas compuertas no son compuertas

lógicas hechas con circuitos como los conocemos pero sirven como modelo mental no es un modelo mental son cajitas que suman cajitas que multiplican Y si las combinamos llegamos a expresiones más complejas Sí entonces acabamos de construir nuestro primer circuito aritmético así se llaman justamente no son circuitos lógicos son circuitos aritméticos habilitan a que se usen más valores está bien ehom V Solo dos V Solo dos sí sí sí no Solo dos Solo dos porque no hay ningún equivalente que yo sepa por lo menos de otras compuertas a a operaciones Matemáticas simples así entre números o

sea si queres pensar cómo jugaría un n ponele podés pero me parece que no hay un mapeo muy claro está pero este caso sí parece bastante natural no está bien Eh entonces les presento a nuestra nueva herramienta los circuitos aritméticos y realmente cuando hagamos Zero knowledge proof eh más avanzados completas vamos a decir la primer parte de todo el problema es definir un circuito aritmético que pueda computar algo que que demuestre que yo

sé algo está sí lleva un momentito capaz como absorber esa idea pero a ver si no hay nadie más acá eh No estamos bien Sí pero eso es lo que vamos a hacer Tenemos que primero que nada encontrar formas de representar afirmaciones y después hay otros mecanismos que hacen ese s que habíamos visto el otro día entonces este es el principio del cuento y vamos a de alguna manera ejercitar un poco Cómo hacer estas cosas está solo modo de repaso acá un poco lo que les decía hoy eh los circuitos permiten representar

expresiones que son polinomios Sí con suma y multiplicación podemos construir polinomios no podemos construir una exponencial por ejemplo sí no podemos Elevar la algo está bien eh y bueno además de ser una forma de de representar expresiones también son una receta de cómo cómo las evaluamos no O sea tenemos inputs y para llegar al output primero pasamos por esta compuerta después pasamos por esta después por esta Y así sucesivamente O sea que también tienen una propiedad interesante que es que son como los podemos desagregar en sus partes e incluso podemos paralelizar el cálculo es es un detalle pero es

Interesante como modelo s y después comentar que este es como el modelo más básico hay algunas cosas que que son mejoras a esto que que no creo que me dé el tiempo el curso para cubrir Pero hay veces que podemos precomputed hacer un montón Así que vamos con esto sí y bueno lo último a mencionar es que tenemos que entender Este modelo mental pero no es que vamos a escribir circuitos nosotros a mano vamos a escribir primero esta compuerta después

esta compuerta después esto no vamos a escribirlo de otra forma y van a haber compiladores que lo transforman en la forma que nos interese O sea que no necesariamente vamos a estar escribiendo el circuito en sí pero si algo que compila a un circuito está bien esa es la idea así Bueno vamos vamos a construir alguna cosita y por eso creo que está divertida la clase porque vamos a empezar como unir partecitas Y eso creo que es más didáctico cero checker Bueno vamos a empezar por este que no es el componente más intuitivo pero es uno de los más básicos y es Eh muchas veces queremos evaluar si algo

es Cero en programación Muchas veces tenemos que chequear eso pero recuerden que esto no no es el mismo tipo de programación a que estamos habituados en esto tenemos que construir un polinomio o una expresión que nos diga si esto es cero o Esto no es cero entonces no es tan simple como hay que pensarlo un poco más y justo Este es un poco rebuscado hay otros que son un poco más rebuscados después si nos da el tiempo les cuento hay uno que es para chequear si un número es más grande que otro y se hace algo medio Místico pero bueno entonces qué podemos hacer para chequear esto ocurre Me encantaría a mí no se me ocurrió lo tuve que buscar pero alguna

idea con uno de estos no con un s si vos le tiras Un s y te devuelve algo diferente a cero o por ahí eh o no es el otro es el and Sí pero claro pero que tenés un solo input acá no Ah Es uno solo no tenías ah no pero si vos ten ah no dije nada pensé que tenías dos valores No pasa nada puedes realizar dos pruebas como las que vimos en la clase pasada y comparar entre ambas quizás Cómo cómo cómo realizas dos pruebas vos sabes que realizando lo que hicimos la clase pasada vos sabes si el otro conoce un número validas los dos números y después el resultado de la división o de

una operación entre ellos te aseguras que pueda ser cero o no Claro pero para porque ahí ya estamos entrando en la parte de la prueba en sí mismo o sea acá todavía no hay no hay dos partes hay una sola parte que quiere computar una cosa quiere modelar un sistema que pueda computar si algo es cero o no es cero no sé si si se entiende eso pero Ah perdón todava No está perfecto no pasa nada todavía no llegamos a la parte de la interacción yo primero tengo que Construir mi modelo que es un modelo de cómputo que va a representar algo está o sea yo voy a decir conozco cierto input que da esto pasando por este circuito aritmético eso

es como lo que vamos a construir una función que tome c y tenga como output 1 si es c y C si no es c vamos escribir quiero construir una función que x y C si x no es c se ve ahí o lo pongo no porque justamente checker es

eso decime si esto es cer como si hicieras un variable Igual igual cer te da true eso eso sería lo que capaz que tendríamos pensar en cosas más tipo bueno programación como estamos acostumbrado pero acá necesitamos lo interesante de esto es necesitamos expresar esto como una una restricción que es un polinomio eso es lo complicado Entonces miren esto Si nosotros tenemos un número x y calculamos su inversa Qué pasa la inversa multiplicado por el

número númer siempre da un A menos que el número sea cero entonces multiplicado por cualquier número es cer la inversa de cer0 se define como cero aparte entonces fíjense que esto es interesante Porque si nosotros multiplicamos un número por su inversa y después hacemos uno menos eso llegamos exactamente a lo que queremos s porque x * x a la men 1 es 1 entonces 1 - 1 es 0 y después si x es 0 1 - 0 es 1 entonces la idea sería podemos tratar de construir un circuito aritmético que represente

esto vieron que va cambiando la forma de pensar esto esto empezaría así vamos a construirlo por partes primero el X por ese x- 1 x -1 lo multiplicamos después multiplicamos por men1 no porque es - x por x la men1 está bien y después tomamos Perdón tomamos 1 y le sumamos -1 por x por x men1 o sea dicho de otra forma Dónde está dicho de otra forma o escrito un

poco más explícito si se qui no no borra nada este borrador Si se quiere un poco más explícito lo que estamos haciendo es 1 más -1 por x por x a la men1 No claro est fue el primero después Esto fue lo segundo yo tercero alguien que que entra ahora es como que va a aterrizar en la luna más o menos Pero bueno vamos arriba

buenas Sí entonces ahí construimos un circuito que permite calcular esa expresión que tenemos Ahí está ahora ven algún problema con esto de la potencia no lo de la potencia no no no podemos No entendí claro No podí yo lo puse como un input viste es es un número es un input la observación es correcta la potencia es un problema Y qué otra cosa es un problema tal vez Hallar el inverso no sabes cuál es momento claro eso ahí va eso mismo comentaban acá que el inverso no no lo podemos calcular con solo con

puertas lógicas así no O aritméticas es verdad el el inverso es un problema está y ahora vamos a ver qué hacemos con eso y y hay otro problema acá a ver si se dan cuenta gra tanto muy borr qué qué otro número es medio raro ahí fíjense el menos un Exacto vamos a estar trabajando con un campo finito se acuerdan que los campos finit

Entonces si trabajamos con este campo finito o cualquiera el -1 no está acá no es Es raro Entonces por cómo voy a estar multiplicando por un os1 que no está ahí no entonces son exactamente esos dos problemas está pero tiene solución tien solución vamos a ver cómo lo solucionamos quedó claro por esas dos cosas son problemas o o alguien le genera duda capaz estamos bien perfecto bien y puse bueno de recalculando tenda ha puesto al mismo

tiempo se Per la oportunidad del ch fácil Sí o sea lo único que necesito es algún número en este campo que tenga como el mismo efecto que -1 sí si lo piensan un segundito y acá obviamente se aplican reglas de módulo pero - x mod p es lo mismo que -1 * x mod p y acá una reglita de módulo podemos tomar el módulo de cada uno de los dos números Entonces el módulo de -1 es este de acá es como que me voy uno para allá y lleo

acá si quieren lo podemos pensar no O sea el módulo no sé si se verá ahí Supongo que s se se ve si nosotros tenemos tenemos tenemos nuestro número p y queremos calcular men1 mod p se acuerdan que teníamos que encontrar vamos a poner esto

x tenamos que encontrar un número x tal que -1 por [Música] p hay que bajar un poquito la cámara per vo justo c el reflejo Ah tenemos que encontrar algún par de números estoy lento se acuerdan que la idea era que esto era resto y acá había que encontrar un cociente y aparte requeríamos que este

cociente estuviera en fp no Entonces cuál es el número dig digamos que si lo ponemos acá y aparte Perdón me estoy yendo un poquito pero fíjense que si nosotros si nosotros pem acá -1 sí Y esto es p - 1 no entonces todo esto nos queda - p - p con p cancelan y nos queda

-1 entonces -1 mod p es p- 1 disculpen que pero es bastante sencillo no O sea siempre el el representante de este este conjunto finito este campo finito que equivale a men1 es el último sí se entendió bien vamos partir la vuelta ahí

está Y esto es interesante porque esto va a ser verdad para cualquier campo finito sí O sea que multiplicar por -1 es lo mismo que multiplicar por p-1 bien eso está Está bueno Es una herramienta ya que sumamos a a nuestro Arsenal eh Y otro es que tenemos un problema con la inversa modular dijimos O sea no podemos calcularla en nuestro circuito pero lo que si podemos hacer es dar un valor inversa o sea yo te puedo decir x es 2 la inversa es 9 vos me podes creer o no puedo estar mintiendo entonces lo que puedo hacer es

tratar de construir algún mecanismo que haga que de aluna manera ver ificar que 9 es la inversa de 2 es un poco entregado Este pero me noté acá para para seguir un poquito pero fíjense que dijimos que nuestro circuito este de acá si x era 0 esto iba a dar 1 no Y si x no era c iba a dar cero siempre y cuando la inversa modular efectivamente sea la que tiene que ser claro si no es válida fíjense que esta cuenta O sea si esto está Okay todo esto

va a ser menos eh va a ser uno no 1 - 1 c pero si esto no está Okay todo esto no va a ser uno por lo tanto todo esto no va a ser cero está bien si esta no está okay entonces fíjense que como pasa eso si si el output no es cero O sea que la inversa está mal si yo multiplico el input por el output y no da cer Tengo un problema sea Me Do cuenta que hay un problema si quieren lo repito porque son son como algunos casos medad pero si x es 0 el output da 1 por lo

tanto este chequeo de acá es 1 por 0 0 O sea que está bien si x no es cer Entonces el output es es un es cer Perdón bien Entonces eso va a ser verdad si el X a la men1 es correcto y yo cuando multiplique cualquier input por 0 va dar c0 Pero si x a la men1 no es el verdadero valor el output no dar cero y como no da cero y x no es cer dos valores que no son cero van a dar algo que no es cer0 y este chequeo va a

fallar entonces de alguna manera lo que les estoy diciendo acá es como no podemos calcular inversas tengo que hacer una especie de claim si tengo que decir esta es la inversa te doy est esta verificación o sea Chequea este valor si este valor es cero estamos Okay yo lo que tengo que fijarme es que el valor es cero y aparte tengo que poder validar que los compus están bien hechos no que eso va a ser la otra parte que después pero acá me surge una pregunta si si habíamos definido dentro del del mismo grupo que solo capaz que capaz me estoy confundiendo no pero eh que eran solo tomamos números enteros

y positivos como hay inversas no Esto no es un grupo esto es un Okay okay está me lo mezclé yo ahí Entonces es que Entiendo entiendo que es un poco entreverado a veces pero en este contexto estamos trabajando Siempre con Campos finitos O sea que tienen el cero también lo único que pasa es que todos los números del campo que no son cero tienen una inversa que no es cero salvo cero cuya inversa es cero está Sí y bueno después es cuestión de de operar Pero admitiendo el resultado cero como posible Ah Perfecto Bueno un momentito ahí para contemplar esto no mirenlo a ver si si hay alguna

cosita el inverso tú lo tienes o te lo te va a venir lado yo lo conozco porque el final de la historia de todo esto es que x es un número privado privado yo lo conozco pero el verificador no Entonces yo puedo calcular la inversa El problema es que yo no se la quiero revelar al al verificador y vamos a ver esto la clase que viene que podemos construir ciertos mecanismos que pueden no revelar esos inputs está bien Sí pero si pueden revelar todo lo demás o sea pueden revelar cualquier

cálculo en particular de este circuito y viene por ahí el asunto pero vamos a dejarlo para que viene primero necesitamos poder construir circuitos después vemos cómo los validamos alguna duda más sobre esta parte bien es el circuito para chequear un valor es cero Claro sí eh De hecho sí el que estaba anterior el que estaba anterior era solo esta parte

o sea faltaba chequear una condición me explico y el p y y el p men1 porque el anterior tenía solo -1 Sí bueno también sustituimos el -1 por p a la men1 p-1 Exacto se hicimos algunas hicimos dos modificaciones esencialmente cambiamos el os1 por un elemento del campo y después agregamos una condición más para validar la inversa y la situación es es la siguiente nuestro esto efectivamente representa un un sistema que es un polinomio por un lado pero también

restricciones está Yo acá estoy imponiendo que el output este tiene que ser cero entonces lo que representamos acá son restricciones que se tienen que cumplir tengan eso en la cabeza porque lo vamos a volver a a hablar la clase que viene pero si yo no restrinjo lo suficiente estoy admitiendo resultados que tienen pueden estar mal si por ejemplo que me den una inversa que no es la inversa Sí pero que cumple con esto puede ser bien una pregunta sí no no me termina de quedar claro o sea cómo cómo funciona la salida de este circuito sí eh lo podemos ver de vuelta

pero o sea suponete que el el el valor sí termina no siendo cero cuál o sea el el el el el output sí qué Qué pasaría ahí si el output a ver hay hay dos escenarios que considera un escenario correcto y uno incorrecto sí como los input son x y su inversa el escenario correcto es que x a la men-1 sea la inversa de X en ese escenario los output son uno o cero punto o sea son los los únicos dos resultados admisibles porque son los

únicos que podes obtener está bien claro ahora sí Ah perfecto lo que tenés que pensar acá es que te pueden estar dando un valor que no es la inversa y ahí se te toda esa suposición se te va por la borda y tenés que chequear algo más para ver que no te están dando algo que no tiene sentido está bien bien bien gracias por favor bien después lo vamos a ver este escrito en un lenguaje de programa bien algo interesante si es que este circuito o sea así como lo ven es como

no sé vieron vieron como de repente nosotros armamos una compuerta xor con varios componentes no que creo que es Eh no me equivoco era Era un eh algo así era no había not acá un and acá un or acá no y acá esto venía con un not algo así era creo pero todo esto lo lo empacamos no O sea todo esto decimos esto es xor y nos olvidamos de los componentes que están adentro no O sea no nos

importan más bueno acá podemos hacer lo mismo podemos agarrar y decir todo este cosito lo empaco en un componente se llama iero o cero check entonces en cualquier circuito que yo necesite chequear que algo es cero puedo usar esto y está bien porque es el mismo componente y no no lo voy a tener que reinventar eso es interesante Porque le da el modelo Este modelo de circuito cierta robustez porque podemos crear cosas reutilizables eso es interesante bien e acá no puse que la condición de output perdón que la condición esa inversas tiene que ser cero Pero también es algo que sale acá como algo que Hay que

chequear y bueno una utilidad de esto es chequear que dos números son iguales por ejemplo no porque lo restamos Y si el output es cero son iguales bien después inclusion en un conjunto se acuerdan que hablamos hace un ratito de esto se acuerdan Cómo era la la expresión Ahí va una un producto sí era lo habíamos escrito así con con la productoria y bueno vamos a ver si podemos transformar esto En un circuito sí no no parece muy complejo parece más más fácil que el otro capaz incluso Cómo

harían entr los c serían entradas o sea es la conjunción de o sea usas muchos ier y es la conjunción de todos los outputs usas muchos y cer con eso que construiste recién básicamente si alguno da cero ya sabes que pertenece es interesante lo que plante después multiplicas todos y chequeas si es cero

Claro porque productorio en realidad es un es hacer todos los Sí sí de acual eh Está bien está bien pero ahí va Lo que primero que tenemos que construir es las expresiones que nos llevan a ese resultado final que lo chequeamos con i cer no Ah bueno Claro claro entonces La pregunta es cómo harías esa parte anterior para ver si entendí o sea es lo que quieres construir ahora es la resta la multiplicación Ah va se lo voy mostrando se lo voy mostrando y vemos si si hace sentido por un lado tenemos los ses que son entradas no pero a la vez tenemos

que están multiplicados por -1 ya sabemos que multiplicar por -1 lo vamos multiplicar por p -1 no tenemos x es nuestro input y asumiendo que estas puertas tienen un orden no sea que es el output el input de arriba más el input de abajo entonces si el primer input es x y el segundo es s1 por p- 1 Esto va a ser x- s1 no y después lo único que tenemos que hacer es todos estos resultados multiplicarlos y este output Ahí es

donde Podrías poner ese cero checker si quisieras ya eh podemos también dejarlo así pado y y ver que nos retorne algo O sea que nos retorne cero simplemente eh Pero bueno cualquiera de las opciones puede ser útil dependiendo del caso y vamos a ver que el el dependiendo del caso ahí tiene que ver con la composición de cosas Sí pero vieron que es bastante lineal este circuito o sea multiplico unas cosas la sumo y la multiplico y ya está o sea llevo a esta expresión que ya me permite chequear que algo está en un conjunto

No acá pasa algo que es que estos valores de s y son conocidos pero tal vez quisiéramos ocultar esos valores imagínense que por ejemplo tenemos una lista de personas sí que tienen una clave privada imagínense y queremos demostrar que nosotros pertenecemos a ese grupo está cualquier persona capaz que puede ver el grupo Ese es pública la información de Quiénes son los miembros pero no queremos revelar las identidades de los miembros pónganlo entonces podríamos tratar de ocultar esos valores y una forma de

holos lo que hago es publico una lista de hashes y esos hases son los hases de las identidades de los miembros si yo quiero demostrar que estoy en ese grupo con que fuera voy a tener que armar un circuito que demuestre que estoy incluido en ese grupo pero los inputs son secretos Ya de por si pero sonados entonces si yo quiero hacer eso fíjense que en un circuito necesitamos también jar no porque voy a tener un input que es mi identidad vo tener quear y después lo voy a tener que comparar con el conjunto como hicimos recién entonces precisamos una especie

de componente Así que sea un Hash esto es un circuito adentro como vimos con el xor pero es un circuito bastante más complejo no lo vamos a abrir acá des pueden buscar noer pero es interesante porque son funciones de friendly para circuitos capaz que no es un ya pero no hay ot hay un que se llama Poseidón otro que se llama m spong creo ot que sh no me acuerdo pero son son varios que ya están planteados como circuito ustedes los pueden importar una Li sí tienen tienen garantías

también de seguridad Bueno pero no no son iguales o sea operan un poquito e bien o sea que existen circuitos para jar cosas entonces podríamos agarrar y en vez de escribir la expresión como la escribimos recién expresar lo mismo pero con el Hash del input menos los elementos del conjunto jados sí Entonces lo único que hacemos Es al circuito de recién le enchufamos este componente acá entre el input es hasado el output es el Hash de x y después multiplicamos todos estos hashes que son

los nuevos inputs aparte por -1 sumamos multiplicamos todo y eso es nuestra expresión sieron acá o sea lo único que hice fue agregar un un un Hash un componente que es el Hash bien matemáticamente se representa sin misterio Solo eso bien estoy haciendo esto paso a paso para ir construyendo algo Alo que haga un poquito más de sentido y que lleguemos ao que digamos Ah bueno puede

empezar a funcionar para entonces lo siguiente es vamos a usar esto vamos a hacer un mini sistema de votación el circuito para un minisistema de votación entonces lo que les decía hoy tenemos un conjunto de claves públicas que están habilitadas a votar Entonces por ejemplo acá somos tres somos nosotros tres que estamos en ese grupo estamos habilitados a votar Y tenemos una clave privada que es nuestra entidad bueno los incluyo también en la llamada no sé cuántos son pero son nu O sea que somos 12 en total 12 personas estamos todos en esa en esa bolsa de claves

públicas obviamente hay una forma de calcular una clave pública a partir de Una privada y no vamos a entrar en detalle en eso solo Vamos a decir que hay una función que permite pasar de una a otra Entonces tenemos un conjunto le llamé fi ahí pero es Ese Conjunto del que estamos hablando hoy y Son un montón de claves públicas son nuestras claves públicas 12 sí eh No 12 no 11 porque yo cuento en la llamada también entonces Entonces qué queremos asegurarnos no primero que el votante que está enviando una prueba que después

vemos cómo se conforma la prueba eso la clase que viene Realmente está en esa lista de claves públicas no entonces bien tenemos eso por un lado y aparte tenemos que validar que el votante vota una sola vez que no puede emitir muchos votos no entonces como que acá hay algunos elementos que ya conocemos y otros que que son como cuestiones nuevas que tenemos que resolver qué qué harían O sea Sabiendo lo que ya saben que más o menos por dónde ven que va este problema lo que hiciste Recién con el circuito

Pero al final del proceso agregarle algo para validar que si la próxima vez intenta hacerlo y tiene ese agregado del final de distinto a cero o a uno algo así Ahí está claro o sea lo que tenemos que demostrar es que estamos incluidos en ese con junto claro y aparte que estamos habilitados a votar no entonces bien está opado no O sea parece algo que podemos construir entonces la inclusión en el grupo La chequeamos con con esto que mencionaban recién no tenemos que verificar que la clave pública del que está votando está en el conjunto de habilitadas por otro lado tenemos el

cálculo de la es una función que toma la privada y la convierte en una pública despés sieren hablamos es una clave públ privada y no falta resolver el tema de la votación una única vez se les ocurre marcarlo lo marcar modificar no y no eh podrías llegar a modificarlo pero idealmente querríamos tener uno único para esta aplicación lo que genera un problema porque capaz que tu idea iba

por ir agregando valores no marcados o algo así claro claro eh Hay una forma más simple que implica mover ese registro afuera del del circuito sí que es usando un anulador nullifier que es esto de marcarlo no O sea tenemos el output del circuito va a contener un valor que es un nullifier sí que es el Hash de la clave secreta en este caso Entonces eso va a ser otro output Sí entonces yo voy a tener mi circuito acá te voy a decir esta es mi clave privada sí Y acá va a

salir si si estoy en el conjunto si puedo votar y va a salir un nullifier yo este nullifier lo voy a ir a anotar no sé si se ve ahí lo voy a ir a anotar a una lista de votos emitidos sí voy a poner acá Bueno Este nullif Entonces cuando si yo quiero votar de vuelta con esta Clave privada Yo te voy a mandar una prueba que va a decir mira estoy habilitado y mi nullifier es este Y vos vas a venir acá y vas a decir mira no sé quién sos pero no puedes votar de vuelta porque ya votaste

Ah sí se entiende o sea oculto la identidad porque esto es un Hash pero lo listo acá Entonces ya lo lo lo contabilizo sí sencillo en realidad es bastante sencillo y esto podría estar en un contrato inteligente podría estar en analista en cualquier lado s retrases pea verif gando no porque el

verificador o sea acá que adelantamos un poco a la jugada pero Qué es un verificador es una persona que recibe una prueba y verifica es un programa un programa que sabe cómo verificar pero aparte puede fijarse en uno de los valores y chequearlo contra otra cosa o sea Ahí sí es un programa tradicional no es valido que esto de esto y aparte si tengo que hacer alguna otra manipulación puedo no hay problema Está bien o sea es esoo yendo la idea de que Qué es un verificador ahí lo lo que no me termin

de cerrar es Está bien es lo que vo decí termin haciendo un programa si podes hacer eso mediante un programa porque no haces todo lo otro mediante un programa también y no te complicas con circuito como todo el otro que claro o sea básicamente estás yendo no sé a una tabla o algún lado a ver si ese si ese Hash está o no está Sí eso no no es a través de un circuito como lo vimos ahora está bien pero y es totalmente válida tu pregunta el el tema acá es que nosotros nos estamos preparando para la parte de siro knowledge o sea estamos buscando una forma de representar afirmaciones que después vamos a a través de ciertos mecanismos que vamos a dar la clase que viene transformar en

algo que no revela información la respuesta de esto es por qué hacemos un circuito porque es un modelo que es bastante amigable para lo que viene después bien entonces sí podríamos escribir un programa pero ese programa revelaría información normalmente porque vos precis harías todos los inputs está bien claro fue como el disparador inicial creo que fue la pregunta de cómo lo hacíamos para hacerlo genérico sin a que fuera como abstracto para que sirviera para cualquier caso Claro claro entonces creo que va por ese lado que fuera lógico y no computacional digamos no Claro se pramos como Este modelo para para representar

eh estas afirmaciones que perfectamente podría ser un programa que que chequear a cosas pero el tema es que nos limitaría ahí en Cómo podemos Cómo podemos procesar eso de alguna manera para que nos sirva para algo entonces todo el el el tema Zero knowledge proof tiene que ver con Cuál es el mecanismo de representación de nuestras afirmaciones y después Cómo se procede está va todo va a terminar de cerrar les prometo la clase que viene pero por ahora confíen en mí de que esto es un modelo útil bien quedó con eso te convencí sí se entendió se entendió

perfecto bien AC puse lo que ya dijimos la lista esa de anuladores sones no son reversibles identidad no entonces el circuito es algo así tenemos nuestra Clave privada es el input una función de Hash que calcula el nullifier el anulador una función de keen que no vamos a entrar adentro a ver qué hace pero vamos a suponer que existe y después Qué falta acá un chequeo de inclusión Entonces el output tiene que ser cero y ahí se puede poner un cero

checker si quisieran por por digamos llevarlo a otra forma pero lo único que cambia el cer checker al final es que el output esperado es uno si nosotros dejamos este circuito así decimos yo requiero que el output sea cero bien claro Así como puede ir a leer el nullifier leer el output la forma de validar y de hecho esto es bastante estándar la forma de validar que la prueba es correcta es que vos me diste un input secreto que hace que todo de cero es como estandarizado es la forma canónica está algo acá no bueno bien se entendió vieron como como acá vamos componiendo

cosas ya no y en circuitos más complejos vamos a seguir componiendo más cosas y así iremos hasta al infinito sí bien AC ag Ya lo hablamos hay que validar que este anulador no esté en la lista de anuladores usados ahí una una pregunta sí O sea básicamente es esa clave privada va a poder votar si lo de abajo deedad que está incluido y el el Hash el nullifier te da que nunca votó Exacto o sea te fijas en las dos condiciones Claro claro que de vuelta eso es lógica del validador está bien o sea el validador puede nutrirse de

distintos outputs lo que hace el circuito es asegurarse que el nullifier está bien calculado está y tal vez como adelantándonos a la clase que viene lo que vamos a hacer en en muchos mecanismos de Zero knowledge es validar que algún paso del circuito esté bien tipo yo hago como una especie de Random sampling y digo esta compuerta acá Está bien no me estás mintiendo No no estás diciendo que el output de Esto es algo que no es Ah okay No me mentiste entonces y así vas como haciendo un sondeo Y vos validas que el cálculo Está correcto entonces después confías en los outputs ya ahí lo vamos lo vamos a ver s creo que sirve igual explicarlo un

poquito para que no se me pierdan de esas cosas bien Esto fue un ejemplo simple Hay un montón de ejemplos más Pero bueno eso lo dejo un poco a criterio de ustedes para que busquen podemos tener circuitos que Que obviamente como son cosas que que partimos de circuitos lógicos podríamos incluso implementar condiciones lógicas si podríamos podríamos hacer esto de la representación binaria de un número podríamos romper un número en su representación binaria y chequear cosas chequear que el tercer bit es uno porque sí sirve en particular para algo que se llama pruebas de Rango porque en el en

el contexto de Campos finitos no el contexto de Campos finitos y vamos a poner hasta p- 1 el concepto de mayor o menor a es medio porque p a la men p-1 es claramente más grande que 4 pero p es cer en realidad en el campo finito porque es p mod p no entonces p que parece más grande que Cero en realidad es más chico que Cero en valor absoluto cuando lo mapeamos acá Entonces el concepto de de mayor o menor no está muy bien definido de

hecho es un tema no hay un lo que se llama una relación de orden que sea muy correcta pero sin entrar mucho en temas matemáticos pero lo que voy es que es medio complicado hacer pruebas o circuitos para estas cosas entonces una cosa que se hace es se dice si la representación mi número mi número x la puedo meter en 4 bits Claro si yo puedo tomar esta representación y decir que este número se representa así yo puedo asegurar que este número es menor a 2 a la

4 o sea que esto es como una técnica esto se llama pruebas de Rango sí Y es interesante porque para eso podemos construir circuitos Ah Podemos haar cosas que sean bueno poder demostrar que una transferencia es válida por ejemplo que una transferencia tiene balance para hacer esa transferencia y que después de la transferencia vas a seguir teniendo balance o sea como demostrar algunas cosas eh podríamos hablar de presentación de credenciales de identidades como vimos recién demostración de una lo puse ahí porque fue lo que se me ocurrió Pero hay muchas cosas realmente que se pueden hacer acá los dejo un poco a a su criterio y si el fin de semana están

aburridos pueden buscar un poquito y ver qué onda que que hay un montón de cosas realmente eh Y bueno nada estos son los circuitos aritméticos es una forma modelo mental con el cual nos tenemos que empezar a acercar a estos estos problemas y acá en realidad yo esto ya lo comenté pero lo voy a repetir que no no normalmente no vamos a escribir los circuitos así como los estamos viendo No no vamos a decir Acá hay una una puerta de multiplicación y después una suma y etcétera porque eso sería un kilombo y aparte sería bastante complicado de

serializar y como un montón de cosas que que serían jodidas entonces eh lo que se hace normalmente es se usan algunos lenguajes específicos que son compiladores de circuitos sí O sea que escribimos escribimos nuestras restricciones en alguna forma que sea fácil de interpretar y después ellos van a tomar eso van a calcular el circuito y con el circuito van a hacer nuestra prueba que ya la vamos a ver está bienc matemático Eh sí no es declarativo tiene matemática también o sea si lo V parece javascript o parece un Java o parece lo que fuera depende del lenguaje

no hay otros que parecen más ras lo que fuera eh pero alg las operaciones o los operadores con los que trabajas no son los comunes o sea ves unas cosas que son así ponele lo vamos a ver esto en la quinta clase pero vas a ver unas cosas así que vas a decir y esto que que no parece nada porque no es menor o igual estas cosas tienen que ver con asignar variables como si fueran outputs de cosas y eso no se preocupen de poquito dej algunos ejemplos en el curso en el curso vamos a ver algunos

ejemplos con Circo pero están estas otras cosas también las pueden bichar y pueden ver a su conveniencia y también un poco a modo es rápid mejor eso lo dejo abierto su investigación eh cc es lo que yo manejo Así que vamos a ver ejemp claro es conocido después hay otras cosas está Halo 2 también Creo que que tiene su su mecanismo no no me acuerdo no quiero decir algo que no no es pero si sepan que están estas herramientas que permiten hacer esta transformación y bueno entonces lo que hablamos de las pruebas qué tiene que

ver esto con las pruebas no lo que vamos a hacer y esto es una respuesta que dieron en la primera clase es probar que un cierto cómputo es correcto entonces modelamos nuestro cómputo como un circuito y después yo voy a demostrar al verificador que ese cómputo está bien hecho sea el verificador puede leer el circuito y puede verificar que las cuentas que yo le pasé están bien entonces puede confiar en que los outputs que le dieron están bien y con eso ser convencido de que yo conozco algo en la entrada que hace que ese cómputo de un cierto resultado Ese es el corazón de la sir

Cruz se entendió si no lo repito y ese circuito no se puede duplicar en tiempo de ejecución es decir ese circuito no se puede muest este circuito pero no eh lo que pasa que el verificador va a tener el circuito O sea que puede puede lo que O sea imagínate que vos tenés un circuito que tiene unas pocas compuertas no vamos hacer así como teníamos hoy el verificador va a tener va a poder leer esto y va a decir mira yo lo que quiero es ver si V vos me vas a dar un valor acá otro acá otro acá no puse cualquier

cosa s y Esto va a dar otro valor y Esto va a dar otro y Esto va a dar otro el verificador Como probador te voy a decir todos estos valores de alguna manera que no importa menos estos Algunos porque no quiero que vos sepas las entradas la forma en la que te los digo la vamos a dar que porque no es Asís pero lo que va hacer el verificador es decir mira yo te voy a preguntar en este caso te voy a preguntar este valor este valor y este valor y voy a chequear que p + r da q si esto no da lo que lo que yo estoy viendo ahí entonces

vos me estás mintiendo claro entonces vos Puedes darme los números que quieras no hay problema pero si no pasa mi verificación está mal entonces yo no voy a confiar en vos está claro Ah lo que quiero el circuito es fijo el circuito está ahí C s o sea yo te paso el circuito Si se quiere como parte de la prueba es parte de la prueba eh Y lo tenés De antemano o no es otra historia pero yo te te lo puedo mandar o puedes pued estar publicado en algún lado el tema es que no una vez que lo tiene el verificador es inmutable o sea yo no te puedo decir no para el circuito no no el circuito es este o sea me estás dando valores para esto yo los estoy

validando Aparte también podrías chequear que el circuito tiene sentido o si quisieras es como leer un contrato en soli esta es como la idea que está de trasfondo Y por qué vamos a usar circuitos lo que nos falta es ver todo lo demás o sea cómo revelamos información de cuentagotas no O sea cómo yo te doy información de a poquito sin darte todo todo el circuito y acá lo que nada repasar es para evaluar que el circuito es correcto el verificador va a fijarse dos cosas que el resultado es el esperado Generalmente el resultado tiene que ser

cero como les decía si vos conocés una información de entrada cuyo resultado es cero Entonces yo confío en que la conoces como una forma de estandarizar y que no sea tipo Espero que el resultado sea 5 porque es medio Random cer como la convención y después que todos los pasos todas las G esas tienen sentido eso es lo que vamos a tratar de hacer para construir las pruebas y bueno obviamente no podemos revelar ciertos inputs que son secretos si no la parte de c no tendría sentido si no te doy los inputs Y verifico vos podría ser también una forma no

bien creo que fue más corta esta clase pero bueno de maneras ya estamos qué fue lo que aprendimos hoy que está este modelo que se llaman circuitos aritméticos que son una forma de modelar expresiones polinomiales y de armar chequeos de restricciones que nos permiten aparte después usarlos para empezar a construir nuestra entonces la gracia de todo esto es que como los circuitos los podemos crear nosotros y esto lo decía Francisco El otro día esto como fotografía programable está o sea tenemos una parte que la va a resolver el compilador y que va Lo vamos a ver después que no lo

vamos a hacer nosotros pero la parte de determinar qué es lo que queremos demostrar la hacemos nosotros Y eso es lo interesante nosotros vamos a escribir un programa que lo vamos a usar para demostrar algo con cierta aplicación y ahí obviamente esto deja el espacio para para la creatividad de ustedes la imaginación que es como lo lindo de este tema ya y bien eh un poco señalando esto no lo que nos falta es saber cómo armar una prueba a partir de esto pero ya tenemos la la primera parte que es la representación de afirmaci está y bueno eso fue la la segunda clase lo que sí les dejo acá un challenge si

quieren es eh buscar alguna aplicación esto golean yo que sé lo mismo hablan gpt le dicen Che Tírame una aplicación copada de decon El proof quiero armar un circuito cómo lo hago más o menos le va a plantear algunas cosas vean Cómo son las restricciones matemáticas cómo sería el circuito para eso y jueguen un poquito Si tienen ganas si no tranqui pero creo que es un buen ejercicio para empezar a irse familiarizando y Porque después lo vamos a escribir de otra forma pero lo que está de fondo es lo mismo es es esto Entonces es bueno interiorizarse está muy bien eso fue todo eh No sé si si tienen dudas o si si fue también otro

mazazo este tengo un par de de preguntas picantes que me dejé guardada si tenemos tiempo pero me parece que está bien está bien así y lo podemos charlar en otra ocasión se fue gente de la clase menos concurrencia Eh bueno muy bien entonces voy a voy aar la grabación ahí