Develop with pleasure!

福岡でCloudとかBlockchainとか。

Cryptography

FROSTを利用したマルチシグの設定変更

FROSTはSchnorrベースの閾値署名方式で、プロトコルの内容については過去の記事↓やGBEC動画参照。 techmedia-think.hatenablog.com このFROSTを利用してBitcoinでマルチシグウォレットの開発を進めているFrostsnapというプロジェクト↓ https://frostsnap.com…

Repairable Threshold Scheme

最近、Schnorrベースの閾値署名スキームFROSTをベースにして、暗号技術だけでt-of-nのマルチシグの設定を動的に調整可能にする提案が行われている。その中で、母数nの数を増やす際に利用されているのが、RTS(Repairable Threshold Scheme)。 RTSは、シャミ…

IPAを利用した多項式コミットメントスキーム

Inner Product Argument(IPA)は、内積の関係を証明するプリミティブで、いくつかの証明システムに組み込まれて使用されている。IPAの解説については、GBEC動画 or 過去記事参照↓ goblockchain.network techmedia-think.hatenablog.com IPAは、多項式コミッ…

コンテンツを復号可能な鍵をアトミックに交換できるBitStream

BitVMやZeroSyncの開発者であるRobin Linusが先日公開したBitStreamのペーパー↓ https://robinlinus.com/bitstream.pdf 分散型のコンテンツホスティングネットワークに対して(最近ユーザーが増えてるNostrとか)、持続可能なインセンティブを持たせるため、…

GG18/20で発見された脆弱性CVE-2023-33241

GG18のプロトコルについて、ざっと確認したので↓ techmedia-think.hatenablog.com 秘密鍵を抽出できるという脆弱性CVE-2023-33241の内容について見ていく。ペーパーは↓ https://eprint.iacr.org/2023/1234.pdf 攻撃を成功するためには、攻撃者は署名プロセス…

閾値ECDSA署名プロトコルGG18

GG18/GG20の脆弱性CVE-2023-33241が今年の夏くらいに公開されていた模様↓ www.fireblocks.com GG18/GG20は閾値ECDSA署名をサポートするMPCプロトコルで、ブロックチェーン界隈のMPC系のウォレット実装でよく利用されているらしい。CVE-2023-33241は、この2つ…

BLS12-381の点のシリアライゼーションフォーマット

ペアリングに適した楕円曲線の1つであるBLS12-381の各曲線E, E'上の点のシリアライゼーションフォーマットについて(もともとZcashで定義された仕様)↓ https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-pairing-friendly-curves-11#appendix-C BLS12…

FROSTの署名作成時の最適化

FROSTは、Schnorrベースの閾値署名方式↓ techmedia-think.hatenablog.com GBECの解説動画はこちら。 最近、Zcash Foundationから、FROSTの署名生成時のスカラー乗算処理を最適化した記事が公開されてたので見てみる↓ zfnd.org 最適化のポイント FROSTでは、…

KZG commitmentをRubyで実装してみた

多項式コミットメントの1つであるKZG commitmentについて↓ techmedia-think.hatenablog.com より詳しく理解するためにRubyで実装してみた↓ https://github.com/azuchi/kzg/ セットアップ KZG commitmentはまず最初に公開パラメーターを生成する。これは基本…

楕円曲線上の点を出力するハッシュ関数の標準化 Hash to Curves

楕円曲線を使用したPedersen CommitmentやBLS署名など、誰もその離散対数を知らない点を利用する暗号プロトコルを最近よく見かける。ただ、プロトコルの説明では、そのような点の導出方法があまり詳しく書かれていなかったりすることもあり、アルゴリズムの…

2つの集合の対称差を求めるアルゴリズムを実装したMinisketch

Bitcoinの新しいトランザクションリレープロトコルの提案Erlay↓ techmedia-think.hatenablog.com のコアとなる実装の1つがMinisketch。 Minisketchは、2つの集合の対称差を求めるアルゴリズムPinsketchを実装したライブラリ。つまりAとBという2つの集合があ…

BLS署名を利用した検証可能なwitness encryption

検証可能なwitness encryptionという新しい暗号プリミティブを利用してDLCを構成する新しい提案のペーパーが発表されてたので↓ https://eprint.iacr.org/2022/499.pdf 「II. TECHNICAL OVERVIEW」の内容を見てみた(まだ一部よく分かってない)。 BLS署名 ペ…

非対話型のSchnorr署名のハーフアグリゲーション

先日、Blockstreamのブログ記事↓で、非対話型のSchnorrの署名集約スキームについて知ったので、 medium.com ↑にリンクされているドラフトBIPに記載されていた↓のペーパーを斜め読みしてみた。 https://eprint.iacr.org/2022/222.pdf Schnorr署名の集約と言え…

Fiat-Shamir変換の安全でない適用による脆弱性Frozen Heart

最近公開された、Fiat-Shamir変換を正しく適用できていないプロトコルや実装において、証明システムの偽造が可能になる脆弱性「Frozen Heart」について↓ blog.trailofbits.com Fiat-Shamir変換とは? Fiat-Shamir変換は、証明システムを非対話型にするために…

Ed25519で決定論的な鍵導出をサポートするBIP32-Ed25519

Bitcoinのウォレットなどが、単一のマスターシードから多数の鍵ペアを決定論的に導出する仕様を定義したのがBIP-32↓ techmedia-think.hatenablog.com これは、Bitcoinが採用している楕円曲線secp256k1とECDSAを前提に作られた仕様になる。 これに対して、EdD…

Merkle Sum Sparse Merkle Tree

先日、Olaoluwa Osuntokunが発表したTaprootを利用したアセットオーバーレイプロトコルTaro↓ https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-April/020196.html 今回はその構成要素の1つであるMerkle Sum Sparse Merkle Tree(MS-SMT)の仕…

通信ラウンドの効率性を重視したSchnorrベースの閾値署名スキームFROST

TaprootのアクティベートによりBitcoinでもSchnorr署名が利用可能になったけど、Schnorr署名をメリットの1つはマルチシグの署名を単一の署名に集約できる集約特性があることで、この恩恵を受けるためにはこのようなマルチシグを扱うウォレットの開発が必要に…

KZGコミットメントのマルチプルーフ

多項式コミットメントスキームの1つであるKZGコミットメントの仕組みについて調べた↓ techmedia-think.hatenablog.com ↑では、ベクトルを多項式に変換することでベクトルにコミットし、その多項式での評価値と単一の楕円曲線のグループ要素をプルーフとして…

KZGコミットメントを計算して理解する

以前ペアリングが可能な楕円曲線を利用するコミットメントスキームであるKZGコミットメントについて書いた↓ techmedia-think.hatenablog.com 楕円曲線を利用したコミットメントスキームとしては、Pedersenコミットメントが有名だが、Pedersenコミットメント…

Generalized taproot(G'root)

Generalized taproot(G'root)は、2018年にAnthony Townsによって提案されたPedersen Commitmentを使ってTaprootを実現するプロトコルの提案。 Taprootのscript-pathは、アンロック条件をマークルツリーにエンコードするMAST(Merklized Alternative Script…

楕円曲線のスカラー倍算アルゴリズム Part 2

前回の投稿では、楕円曲線のスカラー倍算のアルゴリズムとしてバイナリ法やWindow法のアルゴリズムについて、また射影座標を用いた高速化手法について解説した↓ techmedia-think.hatenablog.com 今回は、もともとスカラー倍算の高速化について調査するきっか…

異なる楕円曲線間の離散対数の等価性の証明

MoneroからBitcoinとMoneroでAtomic Swapが利用可能になったというアナウンスが出ていて↓ https://www.getmonero.org/2021/08/20/atomic-swaps.html そのプロトコルの一部で使用されているのが、異なる楕円曲線間の離散対数の等価性の証明。開発をしているの…

Bitcoin Scriptを使ったランポート署名の検証と量子耐性

最近Bitcoin-Devメーリングリストに、OP_CATを使ってBitcoinに量子耐性をもたせる方法について投稿されてたのが興味深かったので見てみる↓ [bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values] アイディアは…

SafegcdによるECDSA署名検証の高速化

2019年に発表された拡張ユークリッド互除法の新しいアルゴリズムを使った、ECDSA署名の生成/検証の高速化について↓ medium.com libsecp256k1にもマージされたので、どういった内容か見てみる。 ユークリッド互除法 まず基本的なユークリッド互除法について。…

署名データを利用したコミットメントスキームSign to contract

ブロックチェーンでよく使われる技術要素の1つとしてコミットメントスキームが挙げられる。シンプルなコミットメントスキームのユースケースとしては、OpenTimestampなど。BitcoinであればOP_RETURN opcodeを使ってファイルのハッシュを記録することで、そ…

ステートレスクライアントのためのVerkle Trie

Ethereumのスケーラビリティを考えた際にネックになるのが巨大なステートストレージ。利用者は1回だけ手数料を積んだトランザクションを発行するだけだけど、ネットワークに参加するフルノードは以降ずっとそのデータを維持しなければならず、ステートの成…

Merkle Patricia Trieの構造とボトルネック

Ethereumのステートを管理する上で重要な構成要素の1つがMerkle Patricia Trie。ビットコイナーならマークルツリーはお馴染みだが、Merkle Patricia Trieはマークルツリーとはだいぶ勝手が違うデータ構造なので、どんな仕組みで構築されて、特定のアイテム…

多項式コミットメントスキーム Kate(KZG) commitment

コミットメントスキーム自体は、いろんなスキームがあり、さまざまなところで使われている(Confidential Transactionなどで登場するPedersen Commitmentや、ゼロ知識で範囲証明を提供するBulletproofsなど)。身近なところだと、ブロックチェーンでよく使用…

楕円曲線のスカラー倍算アルゴリズム Part 1

昨年9月にパテントロックが外れたことで、Bitcoin Coreでもスカラー倍算アルゴリズムの高速化オプションが有効化された↓ github.com もともと、パテントの存在を知らずHal Finneyによって2013年にlibsecp256k1には実装されてたものの無効化されていたものが…

Moneroに導入された新しいリング署名スキームCLSAG

MoneroでRingCT導入時に採用されたMLSAGについて書いた↓ techmedia-think.hatenablog.com ので、続いて、2020年10月17日のアップグレードで新しく導入されたリング署名スキームCLSAGについて↓ https://eprint.iacr.org/2019/654.pdf CLSAG CLSAGはConcise Li…