search

blockchaininnovation / zkzkrollup

1 stars 0 forks source link

リーフのハッシュ計算のリサーチ #2

Open ashWhiteHat opened 2 years ago

ashWhiteHat commented 2 years ago

https://eprint.iacr.org/2019/458.pdf

ashWhiteHat commented 2 years ago

楕円曲線から有限体上へのハッシュ(参照のH2) https://crypto.stackexchange.com/questions/60904/right-way-to-hash-elliptic-curve-points-into-finite-field

ashWhiteHat commented 2 years ago

x座標のみを用いると-Pの逆元はxの値が同じであるため衝突する そのため以下のようなスキームになる

ハッシュ関数を以下のように定義する $h: E(F_p) \rightarrow F_p$

ハッシュ関数内ではSHA256に加えて $H_{cw}$の関数が定義される

$H{cw}$は以下のように定義される $H{cw}(x) = ((ax + b) \mod q) \mod p $

スキーム全体は以下のように定義される

任意の楕円曲線の有理点 $P \in E(Fp)$ に対して $h: P \rightarrow H{cw}(SHA256(P_x | P_y))$

ashWhiteHat commented 2 years ago

なぜ、xではなくax + bにするのかわからない SHA256をポセイドンに置き換えることができるのかわからない

ashWhiteHat commented 2 years ago

$a$, $b$, $q$はランダムな値

ashWhiteHat commented 2 years ago

理由はここに https://en.wikipedia.org/wiki/Universal_hashing#Constructions

ashWhiteHat commented 2 years ago

スポンジ構造の理解は必要 https://link.springer.com/content/pdf/10.1007/978-3-540-78967-3_11.pdf 簡単でわかりやすい方 https://keccak.team/sponge_duplex.html

ashWhiteHat commented 2 years ago

ポセイドンハッシュの実装 https://github.com/privacy-scaling-explorations/poseidon

ashWhiteHat commented 2 years ago

スポンジ構造

ashWhiteHat commented 2 years ago
ashWhiteHat commented 2 years ago

keccakに使われているのはmulti-rate paddingというpadding rule。

ashWhiteHat commented 2 years ago

内部で行われている処理が全部見られる関数 https://github.com/debris/tiny-keccak/blob/master/src/lib.rs#L59

ashWhiteHat commented 2 years ago

multirate padding https://github.com/ctz/keccak/blob/master/keccak.py#L46 わかりやすいpadding解説 https://cryptologie.net/article/387/byte-ordering-and-bit-numbering-in-keccak-and-sha-3/ paddingの実装 https://github.com/debris/tiny-keccak/blob/master/src/lib.rs#L352 https://github.com/debris/tiny-keccak/blob/master/src/lib.rs#L432

ashWhiteHat commented 2 years ago

LSBのbit numberingの後にpadding https://www.computerhope.com/jargon/l/leastsb.htm

ashWhiteHat commented 1 year ago
ashWhiteHat commented 1 year ago

具体的な値での例 https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Standards-and-Guidelines/documents/examples/SHA256.pdf

ashWhiteHat commented 1 year ago

入力の変換とpadding

Conversion Functions

入力の文字列をkeccakの形式に変換する。 入力のメッセージをMとし、kaccakの形式をKとすると $h2b: M \rightarrow K$

B.1 Conversion Functions p26 https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf

Padding

入力の文字列KをPaddingする。

B.2 Hexadecimal Form of Padding Bits p27 https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf

ashWhiteHat commented 1 year ago

Keccak256の全体像

参考

Algorithm 1 https://keccak.team/obsolete/Keccak-specifications.pdf

概要

  1. 入力としてビット文字列のMが与えられる
  2. Mに対してmultirate paddingを行う
  3. Hash Stateを初期化する
  4. paddingされたMに対してKeccak-f[r + c]のabsorbを実行し、Hash Stateを更新
  5. Hash StateにKeccak-f[r + c]のsqueezeを実行し、出力Zを得る

p: multirate padding function H: Hash State i: Hash State init function a: absorb function s: squeeze function

$p(M) \rightarrow M'$ $i() \rightarrow H$ $a(H, M') \rightarrow H'$ $s(H, M') \rightarrow Z$

詳細

1と2はこちら https://github.com/blockchaininnovation/zkzkrollup/issues/2#issuecomment-1311134728

3と4はKeccak-f[r + c]に依存する absorbと呼ばれているフェーズと思われる

5はHash Stateを出力する squeezeと呼ばれているフェーズと思われる

Keccak-f[r + c]

入力MによりHash Stateを書き換える置換関数。 rとcにより決定される。 rはrate。fはfixed-lenght。cはcapacity。r + c = fになる。 keccak256の場合はr = 1088、c = 512、f = 1600となりKeccak-1600と呼ばれる。

θ, ρ, π, χ, ιの置換によりHash Stateを入力Mで書き換えていく（absorb）

Hash State

x, y, zの3次元空間で表される状態。 入力Mからこの空間にabsorbされ、squeezeすると出力Zが与えられる。 x, y, zは上記のrとcから導かれる。

r + c = b wはb/25、lはlog(b/25) Keccak-1600の場合は、w = 64、l = 6

x = 5 y = 5 z = w となる

ashWhiteHat commented 1 year ago

Sponge Constructionから https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf

ashWhiteHat commented 1 year ago

ポセイドンハッシュのパラメータ設定 https://www.poseidon-hash.info/

ashWhiteHat commented 1 year ago

ポセイドンハッシュの概要 https://www.usenix.org/conference/usenixsecurity21/presentation/grassi

ashWhiteHat commented 1 year ago

HADE Strategy https://eprint.iacr.org/2020/179.pdf

ashWhiteHat commented 1 year ago

M ◦ S ◦ ARK(·)の過程になる

ashWhiteHat commented 1 year ago

HADE Strategyの元の論文 https://eprint.iacr.org/2019/1107.pdf

ashWhiteHat commented 1 year ago

http://professor.unisinos.br/linds/teoinfo/Keccak.pdf

  1. Pre-Processing

    • メッセージをブロックに分ける
    • paddingの関数を呼ぶ

  2. Sponge Construction

    • メッセージブロックをアルゴリズム(Permutation)に渡し、処理をする
    • 特定の長さの出力をする

  3. Permutation

    • 内部状態を変更する関数。
    • 特定のラウンド数が決まっている。

  4. The Round Function

    • それぞれのラウンドで呼ばれる関数 poseidon permutationの場合は、ARC(·), SB(·), M(·)の3つになる。 ARC(·)とM(·)はどのラウンドでも同じだが、SB(·)は変化する。

poseidonの基本的な考え方はHADESMiMCと同じ https://eprint.iacr.org/2019/1107.pdf