search

woshidama323 / LearnRust

2 stars 0 forks source link

ZKS #5

Open woshidama323 opened 2 years ago

woshidama323 commented 2 years ago

零知识证明数学理解

starks-vs-snarks

从零开始学习 zk-SNARK

ZKS当前的进展 zkevm

密码学最新研究论文网站

https://eprint.iacr.org/

woshidama323 commented 2 years ago

群论

image

  1. https://medium.com/intuition/group-theory-for-beginners-an-intuitive-approach-2b730227f1a8
woshidama323 commented 2 years ago

群论的直观理解

  1. 等边三角形 旋转 镜像之后还是等边三角形， D3
  2. 只有3个点的时钟，加法之后，依然是{0,1,2} 这三个数 Z3
woshidama323 commented 2 years ago

. v 神的文章

https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627

woshidama323 commented 2 years ago

ECC 比较好的文章

https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

This means that for numbers of the same size, solving elliptic curve discrete logarithms is significantly harder than factoring

相同size的大数，解决ECC 离散对数问题，要比解决 分解素数的难度要大很多。

这也就是为什么ECC 要比 RSA更为安全的原因 

By this measure, breaking a 228-bit RSA key requires less energy to than it takes to boil a teaspoon of water. Comparatively, breaking a 228-bit elliptic curve key requires enough energy to boil all the water on earth. For this level of security with RSA, you'd need a key with 2,380-bits.

意思就是说 ecc更为强大

## v 神关于pairing 的一些理解
https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627

## 中文 ecc的一些公式
https://zhuanlan.zhihu.com/p/42629724

## 其他
https://eprint.iacr.org/2004/064
woshidama323 commented 2 years ago

one-way function 与P != NP 之间的关系

Thus, the existence of a one-way function implies that FP≠FNP, which in turn implies that P≠NP. However, P≠NP does not imply the existence of one-way functions

image

[来源] https://www.wikiwand.com/en/One-way_function

woshidama323 commented 2 years ago

RSA

image

woshidama323 commented 2 years ago

image

woshidama323 commented 2 years ago

初探零知识证明_0217.pdf 初探零知识证明_0217.pptx

woshidama323 commented 2 years ago

julia 关于抽象代数

https://nemocas.github.io/AbstractAlgebra.jl/dev/index.html
woshidama323 commented 2 years ago

merkle树

##

merkel tree

image

woshidama323 commented 2 years ago

filecoin 零知识证明理解

  1. rust-fil-proofs 介绍
  2. audit 文档1

关键概念笔记

zcash的bellman 修改而来，
实现groth16 协议

笔记随摘

image

什么是R1CS （rank-1 constrait system）

https://crypto.stackexchange.com/questions/67857/what-is-a-rank-1-constraint-system 矩阵中的秩

witness 在zks中的意义

https://crypto.stackexchange.com/questions/43462/what-is-a-witness-in-zero-knowledge-proof

How Constraints Work

http://coders-errand.com/constraint-systems-for-zk-snarks/

woshidama323 commented 2 years ago

graph相关算法理论介绍

https://neo4j.com/blog/top-13-resources-graph-theory-algorithms/

woshidama323 commented 2 years ago

学习rust-fil-proofs过程中遇到的问题与笔记

1. 什么是Vector Commitments[1]


Commitment schemes are one of the most important primitives in cryptography
Vector Commitments(VC) is a new primitive in cryptography

2. filecoin的 porep是如何工作的

相关论文 Tight Proofs of Space and Replication[2] 论文作者 （Ben Fisch）

1. 主要贡献： 提出两种方法Stacked DRGs  和 ZigZag Expander DRGs
前者 抽取数据效率低了些，后者 兼顾前者的优势的情况下，抽取数据也高效

相关论文 Proofs of Replication[3]

1. 主要贡献
This paper establishes a foundation for PoReps, exploring
both their capabilities and their limitations

3. graph labeling[4]

woshidama323 commented 2 years ago

6. 图论中基本概念

论文 Proof of Space from Stacked Expanders[1]

5. , the in-degree of the vertex (指向顶点的箭头数)

pebble game on DAG

  1. Source(没有边指向的顶点 )
  2. Sink(没有出去的边的顶点) image

游戏的具体构造方法

image

image

偶图的定义 （bipartite graph）

A bipartite graph G with regular left degree d. Each vertex in A has exactly d neighbors in B (here d = 2). image

Expander code[2]

Expander graph[3]

image

Bipartite Expanders[3]

image

woshidama323 commented 2 years ago

重新阅读 论文[1]

##note
Basic PoRep from Sequential Encodings

### 基本的思想是
The first basic PoRep we describe applies a slow encoding to a file F to transform it into a
format F˜, which can be quickly decoded back to F.
一般的方法是：

VDE

Verifiable Delay Encodings The primitive we use to implement slow encodings in our most basic PoRep is called a verifiable delay encoding (VDE). 

### 特点是：
1.  this is an encoding that is slow to compute
yet fast to decode

### Basic-VDE-PoRep

###

depth robust graph

论文来源[Depth-Robust Graphs and Their Cumulative Memory Complexity]

Thus, in some sense we cheated, as the Basic-PoRep achieves arbitrarily small -rational security for a fixed replication time

## 这个是怎么得到的？
 a degree d = 8 expander graph
  = 1%
 then we can safely set L = 10

## 关键笔记
there is an “even” and “odd” mode of selecting the expander edges.

![image](https://user-images.githubusercontent.com/11014169/159437632-29c4deb0-831b-447a-a1e4-76cfb53c9cf6.png)
woshidama323 commented 2 years ago

ZKrollup

https://research.paradigm.xyz/optimism