flyq

@liquan

https://twitter.com/flyq_crypto

Joined on Sep 7, 2018

Nova and its Implementation:A Deep Dive

  • 目前,Examples 里面提供了 3 种机械手臂的选择,前三个都是 5 自由度(DoF) + 爪子。LeKiwi 是一个三轮移动底座结合 SO-100. HOPEJr 是一个人型机器人项目。glove 是“手套”,用于获取机器手抓握数据,或者通过抓取手部动作来遥控机器手。aloha 是 Trossen 推出的机器人学习套件,单价$29,999.95。stretch3 是A Fully Integrated Mobile Manipulator,单价 $24,950。teleoperation 是遥控相关的硬件。open duck Koch v1.1 Leader Arm 电机: 品牌:Dynamixel XL330-M077-T 参数: 数量:6 价格:255
     Like  Bookmark
  • https://dankradfeist.de/ethereum/2021/11/18/inner-product-arguments-mandarin.html https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html https://eprint.iacr.org/2017/1066.pdf 符号约定 定义在 $\mathbb{F}_p$ 上的椭圆曲线群 $\mathbb{G}$,标量域为 $\mathbb{F}_r$,从 $\mathbb{G}$ 中选取两组独立的点作为 base: $\vec{G} = (G_1, G_2, \dots, G_n)$ $\vec{H} = (H_1, H_2, \dots, H_n)$
     Like  Bookmark
  • $[\tau]_1$ stand for $\tau G_1$ Public Parameters: $\text{srs} = ([1]_1, [\tau]_1, [\tau^2]_1, [\tau^3]_1, \dots, [\tau^{n-1}]_1, [1]_2, [\tau]_2)$, where the $\tau$ is a random, and will be deleted to make sure no one knows it after set up. Prover knows: $f(X) = a_0 + a_1X + a_2 X^2 + \cdots + a_{n-1} X^{n-1}$ for a Polynomial $f(X)$, its KZG10 Commitment is $C_{f(X)} = f(\tau)G = a_0G + a_1\tau G + a_2\tau^2 G + \cdots a_{n-1} \tau^{n-1} G = a_0[1]_1 + a_1[\tau]_1 + a_2[\tau^2]1 + \dots + a^{n-1}[\tau^{n-1}]1$, so the Prover can calculate $C{f(X)}$ according to the srs, and public the $C{f(X)}$ at first. The verifier provides the challenge value $\zeta$ to prover, where $\zeta$ is a random value. the prover calculate $f(\zeta) = y$. the prover calculate $q(X)$ according to $f(X) - y = q(X)\cdot (X-\zeta) \quad X\in \mathbb{F}_n$ the prover calculate $C_{q(X)} = q(\tau)G$ according to the srs.
     Like  Bookmark
  • https://github.com/crate-crypto/rust-verkle English Version Verkle tree motivation Stateless client is a key milestone in the Ethereum roadmap. The state of the existing Ethereum execution layer is stored in the MPT structure. Although MPT can also implement Stateless client, the corresponding Proof size is too large and cannot be used in one area. The block interval is broadcast to all nodes: Verkle trees solve a key problem standing in the way of Ethereum being stateless-client-friendly: witness sizes. A witness accessing an account in today’s hexary Patricia tree is, in the average case, close to 3 kB, and in the worst case it may be three times larger. Assuming a worst case of 6000 accesses per block (15m gas / 2500 gas per access), this corresponds to a witness size of ~18 MB, which is too large to safely broadcast through a p2p network within a 12-second slot. Verkle trees reduce witness sizes to ~200 bytes per account in the average case, allowing stateless client witnesses to be acceptably small. from https://eips.ethereum.org/EIPS/eip-6800
     Like  Bookmark
  • rust verkle 的实现 https://github.com/crate-crypto/rust-verkle 使用了 multiproof 来优化。因此也需要了解相关的内容。 PCS 至少有两个方案,一个是 KZG,一个是 IPA。 KZG 可以参考 https://hackmd.io/@liquan/r1xt93zft6 IPA 可以参考 https://hackmd.io/@liquan/Bk6m487-A 并且它们都是支持加法同态,它们都可以应用 Multiproof。 因此这里我会分别介绍 KZG 和 IPA 的 Multiproofs。其中 KZG 的直接参考的:https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html ,IPA 是我自己的理解。
     Like  Bookmark
  • Public setup: 对某椭圆曲线群 $\mathbb{G}$,随机生成 $n$ 个点 $(G_0, G_1, \dots G_{n-1})$ 承诺阶段 Prover: 假设要对向量 $\vec{a} = (a_0, a_1, \dots, a_{n-1})$ 其中 $a_i \in \mathbb{F}r$,进行承诺,$C = \sum{i=0}^{n-1} a_i \cdot G_i$ 将 $C$ 发送给 Verifier 一般承诺方案会作为一个组件嵌入到更大的一个协议中,因此接下来 Prover 将使用 $\vec{a}$ 生成其他的证明。
     Like  Bookmark
  • https://github.com/0xPARC/zk-bug-tracker/tree/main https://arxiv.org/pdf/2402.15293.pdf https://eprint.iacr.org/2023/190 https://github.com/D-Squared70/Reading-Room/blob/main/Zero-Knowledge/Common_ZK_Vulns_Bug_Tracker/Common_ZK_Vulns.md https://www.zksecurity.xyz/blog/posts/underconstrain-bugs/
     Like  Bookmark
  • The canister is already running on the chain https://p6xvw-7iaaa-aaaap-aaana-cai.raw.ic0.app/ On April 9th, the A16z crypto team released the fastest zkVM for prover: Jolt, including code, examples, documents, blogs, and papers(Lasso and Jolt). (The blogs contains a lot of insider information about the zk industry) After running the examples, I tried integrating its verifier into the IC Canister.This thing is very meaningful and is actually an official todo list. IC is a high-performance blockchain Layer 1 that can use Rust to write smart contracts and compile them into WASM, and then deploy them to IC. Therefore, choosing IC has a high probability of success. Find verifier
     Like 2 Bookmark
  • $g(x_1, x_2, \dots, x_v),\ x_i \in \mathbb{F}$ Prover 需要计算并证明 $g$ 在布尔输入上的值求和的结果是 $H$:$H := \sum_{x_1 \in {0,1}} \sum_{x_2 \in {0,1}}\cdots\sum_{x_v \in {0, 1}}g(x_1, x_2, \cdots, x_v)$ 完全展开后会产生 $2^v$ 个常数项,并求和 Sumcheck 可以计算任意 $B \subseteq \mathbb{F}$ 时 $\sum_{x_1 \in B} \sum_{x_2 \in B}\cdots\sum_{x_v \in B}g(x_1, x_2, \cdots, x_v)$ 的值,完全展开后会产生 $\left | B \right |^v$ 个常数项。 证明者的计算时间 $\mathcal{O}(2^v) + c$,$c$ 是证明过程需要用到的额外步骤,一个常数因子。 验证者的计算时间 $\mathcal{O}(v+d)$,$d$ 为 $g$ 在单个输入上的计算成本。
     Like  Bookmark
  • 给定某个子群 $\mathbb{G}_1$,但是 $\mathbb{G}_1$ 的 order 很大,不利于求解 ECDLP,怎么将该过程映射到较小的子群里面。 给定一个椭圆曲线群: $y^2 = x^3 + 4 \mod 11$ With the help of this excellent interactive tool we can explicitly view its composition: image
     Like  Bookmark
  • Solution from https://twitter.com/developeruche The Goal is to release merkle proof system used for airdrop verification with KZG commitment. This is how I implemented it and got stuck when trying to implement the solidity verifier. I get all the address of the valid address and amount, concat it and obtain the hash of the concat. I map each of these hashes to a field element... giving me a vector of field element. I interpolated each of this field elements to get a polynomial. (this polynomial's degree is very huge, for the Optimism Airdrop I used as a case study, I was a 268K degree polynomial. Commit to the polynomial
     Like  Bookmark
  • Puzzle: https://zkhack.dev/events/puzzle2.html sage: field_modulus = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787 desired_curve_order = 52435875175126190479447740508185965837690552500527637822603658699938581184513 Fp = GF(field_modulus)
     Like  Bookmark
  • English Version Ethreal is a puzzle in zkctf hosted by scalebit. At that time, I understood the code of this puzzle quickly, but I couldn't find its vulnerability. I was stuck and couldn't solve it in the end, so I will give a comprehensive summary here. The original code of this puzzle is on github, which contains Solidity and Golang codes. Solidity is the topic, and we need to call the register and mint of the contract. golang is auxiliary code that helps us generate proofs and call contracts. I am not familiar with the Go language. I can only understand the logic, but rewriting it is more troublesome. The problem is that if we follow the default settings in Golang, we can only mint 9. To finally solve the problem, we need to mint 20. Let’s take a look at the contract logic first: Pairing.sol
     Like  Bookmark
  • https://eips.ethereum.org/EIPS/eip-4844 https://www.eip4844.com/ Parameters BLOB_TX_TYPE: 0x03 BYTES_PER_FIELD_ELEMENT: 32 2^5 FIELD_ELEMENTS_PER_BLOB: 4096 2^12 there 2^17 bytes per blob, 131071 bytes
     Like  Bookmark
  • BLS Signature There are $P_0$, $P_1$, $P_2$, $P_3$ four parties. $P_0$: secret key $sk_0$, message $m_0$, public key $P_0 = sk_0 \cdot G$, signature $S_0 = H(m_0) \cdot sk_0$ $P_1$: secret key $sk_1$, message $m_1$, public key $P_1 = sk_1 \cdot G$, signature $S_1 = H(m_1) \cdot sk_1$ $P_2$: secret key $sk_2$, message $m_2$, public key $P_2 = sk_2 \cdot G$, signature $S_2 = H(m_2) \cdot sk_2$ $P_3$: secret key $sk_3$, message $m_3$, public key $P_3 = sk_3 \cdot G$, signature $S_3 = H(m_3) \cdot sk_3$
     Like  Bookmark
  • Puzzle: https://zkhack.dev/zkhackIV/puzzleF3.html Solution: https://github.com/flyq/puzzle-chaos-theory ElGamal encryption Key generation Alice: secret key: $x$ public key: $H = x\cdot G$
     Like  Bookmark
  • https://zkhack.dev/events/puzzle1.html private key $sk$ public key $P = sk\cdot G_2$ message $m$ message's blake2s hash $h_m = \text{blake2s}(m)$, $h_m$ is a scalar field element with $256$ bits size. according to WINDOW_SIZE = 1;NUM_WINDOWS = 256, CRH will generate $256$ Points according to the rng. Let's use $Q_0, Q_1, \dots, Q_{255}$ present them. hash to curve $H(h_m) = h_m[0] \cdot Q_0 + h_m[1] \cdot Q_1 + \cdots + h_m[255] \cdot Q_{255}$ signature $S = sk \cdot H(h_m)$ $e(S, G_2) = e(H(h_m), P)$
     Like  Bookmark
  • $$\begin{align*} x & \equiv a_1 \mod n_1 \ x & \equiv a_2 \mod n_2 \ \cdots \ x & \equiv a_k \mod n_k \end{align*}$$ $$N = \prod_{i=1}^k n_i$$ Where the $n_i$ are pairwise coprime. then there is one and only one integer $x, 0\leq x < N$ satisfy them. $$\begin{align*} x & \equiv a_1 \mod n_1 \ x & \equiv a_2 \mod n_2 \end{align*}$$ $n_1 m_1 + n_2 m_2 = 1$ calculate $m_1, m_2$ by Extended Euclidean algorithm
     Like  Bookmark
  • https://zkhack.dev/zkhackIV/puzzleF2.html Early attempts When I got this question, I didn't know where to start. I tried running cargo run --release, and as expected, an assert error occurred. Then I browsed the source code and found that it mainly used things related to the ark_bls12_381 curve, and then looked at the relevant information provided, two English papers. I couldn't read it after just looking at the title and abstract. Unfortunately, cryptography papers are often too long for me and I can't grasp the key points. But I vaguely know that this is something related to BLS signature aggregation and rogue key attacks. I'm starting to feel the pain. When I was learning ECC in the past, the difficulty of Pairing-related topics was too high for me, so I skipped it. As a result, my current understanding of BLS pairing is only a black box that that can provide method like $e(a G_1, b G_2) = e( G_1, G_2)^{ab}$, I have no idea what's under the hood.
     Like  Bookmark
  • Given a Merkle tree and a secret corresponding to a leaf. First it will prove that the leaf is on the Merkle tree, and then ask for a new secret to ensure that its corresponding leaf is also on the Merkle tree. Origin Problem: https://github.com/ZK-Hack/puzzle-gamma-ray background It is assumed that you already know about elliptic curve, such as its point addition, scalar multiplication, ECDLP, Generator, order. See these four articles for detail. There is a fact that, in affine space the graph of the elliptic curve $y^2= x^3 + ax +b$ is symmetrical about the $x$-axis. For a certain point $P_0(x_0,y_0)$ above, there must be a point $P_1(x_0,-y_0)$ on the curve. After$\mod q$, the $y$ value of points below the $x$-axis will be added to $q$, and the points of their elliptic curves are symmetrical about $y = \frac{q}{2}$. In the definition of elliptic curve group, they are inverse elements of each other. Here we introduce CycleCurve. As an example, this is the parameter of Secp256k1: $y^2 \equiv x^3 + 7 \mod q$, where q=0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F, the generator is point G, the amount of elements is order, and order=0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141. The Fields generated by mod q is the base field, related to $(x,y)$, and by mod order is the scalar field, which is related to the coefficient of the point, such as $aG$. $a$ is in the scalar field.
     Like  Bookmark