Zero-Knowledge Proofs: Co jsou zk-STARK a jak fungují?

1. Co je to?

Systém zk-STARK Proof of Reserves (PoR) využívá teorii STARK, což je komplexní matematické řešení. zk-STARK znamená: „Zero-Knowledge Scalable Transparent Argument of Knowledge“. Jde o kryptografickou technologii dokazování, která stojí na Vitalikově myšlence vynucení integrity a soukromí výpočtů na blockchainech. V tomto článku vám představíme, jak to funguje, a vysvětlíme si obecný matematický koncept. Pokud se ale o problematiku zajímáte více do hloubky, začněte zde nebo zde.

Jak to funguje?

Obrázek 1. Tabulka sledování provádění a Merklův strom vytvořený pro zk-STARK PoR

1. krok: omezení při vytváření

Abychom prokázali odpovědnost naší burzy, máme tři tvrzení:

1. tvrzení: Správně jsme získali hodnoty pro každého uživatele, včetně hodnoty každé kryptoměny a čisté hodnoty každého uživatele.

2. tvrzení: Burza nezfalšovala virtuálního uživatele, jehož čistá hodnota je záporná, aby snížila celkovou odpovědnost burzy. (Jakýkoli uživatel se zápornými zůstatky je přijatelný pouze v případě, že je jeho čistá hodnota vyšší než 0)

3. tvrzení: Celková hodnota, kterou si burza uvádí, se vztahuje na každého jednotlivého uživatele, takže každý uživatel by měl mít možnost ověřit, zda je jeho čistá hodnota zahrnuta do celkové hodnoty

Abychom mohli výše uvedená tvrzení otestovat a ověřit, musíme vytvořit omezení, jako jsou:

1. tvrzení: Omezení celkového zůstatku (Omezení správného celkového zůstatku)

uts: míra sledování uživatele (user trace size), což je počet řádků sledování zahrnutých v datech každého uživatele.

součet: celkový zůstatek uživatele

N: počet uživatelů

2. tvrzení: Omezení o nezápornosti (omezení kladného čistého kapitálu)

3. tvrzení: Omezení zahrnutí (Omezení zahrnutí veškerého zůstatku na účtu zákazníka)

Podle výše uvedených omezení vytváříme tabulku sledování, abychom potvrdili a ověřili celkové zůstatky a nezápornost kontrolou vybraných vzorků. Zde je uveden způsob sestavení tabulky sledování (pro zjednodušení příkladu: 3 uživatelé, jejichž maximální hodnota USD je menší než 4^6 = 4 096):

1. Tabulku začneme s 32 řádky a 5 sloupci a vyplníme hodnoty a ID uživatele do

řádku, kde k % 8 = 6, a

. Každých 8 řádků je blok a informace o uživatelských aktivech jsou teď v

vzadu v každém bloku. První uživatel má virtuální zůstatky 0, takže je můžeme zveřejnit, abychom dokázali, že kumulace hodnot nezačíná od záporné hodnoty.

2. Sčítáme postupně hodnoty uživatelských aktiv a výsledek vyplníme do řádků

, kde k % 8 = 7, a

, což jsou poslední řádky každého bloku.

3. Dále dělíme celkovou hodnotu každého uživatele hodnotou 4 řádek po řádku od

zpětně pro každý blok. Děláme to proto, aby čistá hodnota uživatele nebyla záporná, a to tak, že kontrolujeme, zda jsou první řádky pro každý blok nulové. Pokud má někdo zápornou čistou hodnotu, první řádek jeho bloku nebude nulový, protože záporná hodnota (-x) se v konečném poli

ukáže jako (p − x), což je velmi vysoká kladná hodnota.

4. Pro každého uživatele zadáváme náhodná čísla a prázdná místa v tabulce vyplníme 0

2. krok: Rozšíření polynomu nízkého stupně Pomocí výše uvedených polynomických omezení můžeme získat polynom pro sledování délky uts * N. Z bezpečnostních důvodů provádíme vazbu na polynom na větší doméně vyhodnocení, kdy faktor zesílení domény slouží jako faktor rozšíření extension_factor.

Ve výše uvedeném případě bychom mohli vypočítat polynom p(x) z I(x). Pokud použijeme faktor rozšíření extension_factor 8, vypočítáme dalších 32(8−1)* bodů na p(x).

Protože dva různé polynomy o stupni D budou sdílet nejvýše D bodů, bude mít dvojice polynomů s platným polynomem (který splňuje výše uvedená omezení) a falešným polynomem o stupni D (který nesplňuje výše uvedená omezení) v našem příkladu společných nejvýše D bodů. To znamená, že falešný polynom má šanci

projít kontrolou namátkového získávání vzorků. Pokud provedeme kontrolu vzorků nkrát, šance se sníží na

.

Použijeme faktor rozšíření extension_factor ve výchozí hodnotě 16 a výchozí čas kontroly vzorku 16, takže úroveň zabezpečení bude 80 bitů.

3. krok: Vazba polynomu Vypočítáme hodnotu hash trasování výpočtu a odpovídající zůstatek uživatele, ID uživatele a hodnotu odpovídajícího polynomu omezení pro každý řádek a vygenerujeme strom Merkle. Merklův kořen je hodnota vazby polynomu.

4. krok: Vygenerování důkazu na základě vzorku Pomocí Merklova kořene jako náhodného zdroje získáme vzorek dat. Abychom se vyhnuli úniku dat sledování výpočtu, vyhýbáme se datům s indexem *k *× extension_factor během získávání vzorku a vygenerujeme cestu Merkle proof odpovídající indexu vzorku.

Provedeme kontroly vzorků, abychom ověřili, zda odevzdaný polynom je platný polynom splňující omezení uvedená v 1. kroku. Jak je uvedeno v 2. kroku, časy kontrol při získávání vzorků ovlivňují pravděpodobnost úspěšnosti pozměňování nebo neoprávněné manipulace.

5. krok: Vygenerování důkazu nízkého stupně

Pravděpodobnost úspěšnosti pozměňování nebo neoprávněné manipulace můžeme kontrolovat díky kontrole vzorků. Existuje však podmínka, jak bylo uvedeno v 2. kroku, že musíme zajistit, aby stupeň ověřovaného polynomu nebyl vyšší než stupeň platného polynomu. Abychom zvýšili efektivitu důkazu, spojíme lineárně všechny polynomy omezení do jednoho polynomu a vytvoříme pro něj důkaz nízkého stupně. Kombinační koeficienty se také generují pomocí Merklova kořene jako náhodného zdroje.

Pokud chceme například dokázat, že p0(x), p1(x) a p2(x) nemají více než D stupňů, můžeme z Merklova kořene vygenerovaného v 3. kroku vygenerovat 2 náhodné koeficienty a vypočítat lineární polynom l(x) jako:

k0 = hash(root + "0") k1 = hash(root + "1") l(x) = k0 * p0(x) + k1 * p1(x) + p2(x)

Pokud lze dokázat, že stupeň l(x) není větší než D, pak šance, že stupeň některého z p0(x), p1(x) a p2(x) je větší než D, bude blízká 0

6. krok: ověření celkového zůstatku Nejprve ověříme důkaz nízkého stupně vygenerovaný v 5. kroku.

Následně se provede další otevřené ověření na datech vzorku vygenerovaných ve 4. kroku. Za prvé ověřit, zda jsou data konzistentní s vazbou polynomu, a za druhé ověřit, zda data splňují omezení uvedené v 1. kroku. Nakonec jsou ověřeny kombinační koeficienty testovacího polynomu nízkého stupně.

7. krok: Vygenerování důkazu o zahrnutí uživatele Abychom prokázali, že konkrétní uživatel je zahrnut v celkové částce uvedené burzou, uvádíme vypočítané sledování uživatele, zůstatek uživatele, ID uživatele a náhodné číslo odpovídající indexu uživatele. Uvádíme také Merklovu cestu odpovídající těmto datům.

8. krok: Ověření důkazu o zahrnutí uživatelem Uživatel zkontroluje svůj zůstatek, ID, vypočítá hodnotu hash dat odpovídající jeho indexu a ověří hodnotu hash na uzlu listu Merklova stromu s využitím uvedené Merlovy cesty.

2. Jak provést vlastní ověření Proof of Reserves (PoR)?

2.1 Ověřte omezení zahrnutí zk-STARK

Teorie ověření

Podle postupu STARK vypočítáme tabulku sledování provádění všech aktiv uživatelů, jak je uvedeno níže, a informace o každém uživateli zahashujeme jako tabulku sledování, která se stane listem Merklova stromu. Listy poté zadáme do kořene Merklova stromu, který bude zveřejněn během každého kola auditu PoR.

Pro ověření, zda jsou vaše aktiva zahrnuta v kořeni, vám sdělíme Merklovu cestu k ověření. Nejprve můžete vypočítat svůj list hašováním informací o vašich aktivech a poté ověřit, jestli je váš list platným listem Merklova stromu a kořenu, který jsme zveřejnili.

Například na obrázku 1 uživatel s ID id_k vypočítá „hashk = hash("20" + "15" + "5" + "id_k" + "99821")“ a další údaje v červeném rámečku budou ověření Merklovy cesty. K tomuto ověření je uživatelům k dispozici opesourcový nástroj.

Protože listy Merklova stromu jsou hashe, žádné vaše soukromé informace se nedostanou k ostatním.

Jak provést ověření:

1. Pokud si chcete ověřit, zda byl zůstatek aktiv na vašem účtu zahrnut v podobě zk-STARK Merklova listu, přihlaste se ke svému účtu OKX, zvolením možnosti Audity si zobrazte poslední audity a kliknutím na Podrobnosti si zobrazte údaje o auditu.

2. Data, která budete pro ruční ověření potřebovat, získáte kliknutím na Kopírovat data.

3. Po kliknutí na Kopírovat data otevřete textový editor (například poznámkový blok) vložte je a řetězec uložte jako soubor JSON. Soubor musí končit „_inclusion_proof.json“. Řetězec JSON obsahuje zůstatek na účtu a snímek Merklovy cesty a pak soubor uloží do nové složky.

Text JSON je uveden níže:

{ "batch_inclusion_proof": { "batch_mtree_root": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5", "user_id": "47db1d296a7c146eab653591583a9a4873c626d8de47ae11393edd153e40f1ed", "total_value": 138312291, "BTC": 2152907, "ETH": 909757, "USDT": 2319557, "random_number": "e7b7a5a6fdba87a58559aed4fca66fb63d3d9395ce0d51bda40fcd35893391ac", "merkle_path": [ "5e3dd0ad776b15743076405d53e12af8fdac85c446bcc6c2eb8cab0e0e0c24f9", "9dd5fcb0f3835b10772a7baabe7a074ed0b6947f7284e2d7ce5a84c3b5b394da", "973186c5ea69bdc06c0c786cfae76173a89e0989bd759e1b2c37fdd317c70fe2", "0c7ea3dd9bc0a15019b9ace6cf003befa31133ee84728d21bf67aa984ef1b60a", "2adf4a58ccec7a44ed3a3f8bd365c61eac7d25c55524e69a31c6665769b7962a", "4cddf667adbfa51e1b999e39a2009dcc9786385d9f3e240919f763e4db6f3609", "4e841f9b5c2641759572fdfaf66c518b191e89b7a4745f179c046fef1eb9c374", "cc12d77e7d13ee3c57064697dfef230064efaaf5b6ccf22a5ef5b7a2602632ab", "ead6745e91b88021aeecddd8d014ea26ba26f42c4d5286ef8e196085d3757f62", "1a583279e243ddc0a36bf870b5af70f2e52f059faeb5f3757d0d1903770371e8", "5c1729384a2f2c8c434f3b34e99d6152aab42093c4f68aab638eaa212e799933", "e154c1011883b2cea377c6bc820a21ac01d9d792ce3e1f376f35c1b29df04167" ] }, "trunk_inclusion_proof": { "trunk_mtree_root": "9b61d44f4f3de6b284d95a844dee9327d5e2091ac7e6b6f67ca10bd866617290", "batch_id": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5", "total_value": 2007657936, "BTC": 18915744, "ETH": 21522734, "USDT": 21268768, "random_number": "c93d3517d691564f3cc8e1eee6634ba7e0f59125aa89cd6984677459ac5f8164", "merkle_path": [ "1082ec62ad0bd2b2b2c38a08f4b0de2f9aa77b387c611b927d203deb9bc97376", "a57a391c137877993cd61ca4ad57bb1754bf8776fd207e630c362b8560fbb34b", "413cba43d7f7236b5ce21fe951583660277507250ecbabca6a1ac6e9ac66bb5b", "d87e2c64c34700195e322967ebbbb282810671320d083029fb9e46f92474d47b", "85438a308f8d668779dbdb462437434f8f9d551229e8ebb2235605fe18cf97f6", "d1cbf91c33b4cb0366877c4c805548401887f2a428c7297d0c4d97fa0f936cec", "147fccf20ff7010d2ba162333f62200dce116d337230ee73f7c8bc2abcba148e", "0901034401e6b6fa7de911d658ebc9b10c6a64c16a5450a22e390859ae87e1c4", "b2e3525d853749ca2edfa718cd4f12ba26a0f645dfb0d5512d42c67fc74d0a1a", "ad34d5acf98f7e6234d132d578f823e7bd8410d1850db76a55dd794ce388b2c2", "7e81326a45550eea02398a8459dbd5d73d6d90b58268ce4453231cf3077f4fdf", "239263d4cf31258c7910fe7abe8cc23d1b71cf73e796a958e60d3fafe095e49d", "bb44ebaed47333c967f79c48cb3e0106fe64f55411f94181daa4c55f2a563e43" ] } }

1. Stáhněte si opensourcový ověřovací nástroj OKX zk-STARKValidator

2. Uložte opensourcový ověřovací nástroj OKX zk-STARKValidator a soubor JSON společně v nové složce z 3. kroku. V našem případě: Uložíme nástroj i datový soubor do složky Stažené soubory a pojmenujeme je proof-of-reserves, jak je uvedeno níže:

1. Otevřete zk-STARKValidator, který automaticky spustí soubor JSON, který jste uložili do složky.

2. Zkontrolujte výsledek

– Pokud ověření proběhne úspěšně, zobrazí se výsledek „Ověření omezení zahrnutí bylo úspěšné“:

– Pokud ověření proběhne neúspěšně, zobrazí se výsledek „Ověření omezení zahrnutí se nezdařilo“:

<p><img src="/cdn/assets/plugins/announcements/contentful/15303691813261.jpg"</p>

2.2 Ověřte celkový zůstatek zk-STARK a omezení nezápornosti

Jak provést ověření:

Pokud chcete ověřit a prokázat, že aktiva, o kterých tvrdíme, že jsou skutečná, a že žádný uživatel nemá záporný čistý vlastní kapitál, navštivte naši stránku „Soubory pro audit“ a stáhněte si soubory „zk-STARK“ v části Zpráva o závazcích a poté je uložte do nové složky.

Stažený soubor rozbalte a najdete v něm složku „sum proof data“, která obsahuje tisíce složek větví a jednu složku kmene. Každá složka obsahuje dva soubory JSON s názvy „sum_proof.json! a „sum_value.json“.

Stáhněte si opensourcový ověřovací nástroj OKX zk-STARKValidator

Uložte opensourcový ověřovací nástroj OKX zk-STARKValidator a složku „sum proof data“ společně do nově vytvořené složky z 1. kroku. V našem případě uložíme nástroj a datový soubor do složky Stažené soubory a pojmenujeme je proof-of-reserves, jak je uvedeno níže:

Otevřete zk-STARKValidator, který automaticky spustí „sum proof data“, který jste uložili do složky.

Zkontrolujte výsledek:

– Pokud ověření proběhne úspěšně, zobrazí se výsledek „Ověření celkového součtu a omezení nezápornosti bylo úspěšné“:

– Pokud ověření proběhne neúspěšně, zobrazí se výsledek „Ověření celkového součtu a omezení nezápornosti bylo neúspěšné“: