Develop with pleasure!

福岡でCloudとかBlockchainとか。

Cryptography

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…

RingCTでMLSAGを必要とした理由

Moneroでは、送信者の情報を秘匿するためにトランザクションインプットにデコイとなるUTXOを含めて、UTXOセットの中のいずれかが実際にトランザクションで使用されることを証明するためにリング署名を採用している。Moneroが以前採用していたSchnorr署名の変…

2ラウンドで安全なマルチシグを生成する署名スキームMuSig2

MuSigはもともとSchnorr署名の鍵の集約特性を活かして多重署名(マルチシグ)を単一のSchnorr署名で行う署名スキームで、Rogue-key攻撃に対して堅牢な署名スキーム↓ techmedia-think.hatenablog.com ただ、署名の生成に以下の3ラウンドの通信が必要になる。…

Dual_EC_DRBGのバックドアの仕組み

japan.zdnet.com こんなニュースもあり、バックドアと言えばエドワード・スノーデンの告発でも話題になったNSA(米国家安全保障局)のバックドアを思い出した。当時は仕組みについて調べてなかったけど、どんな仕組みのバックドアだったのか今になって気にな…

決定性nonceを利用したMuSigの脆弱性に対処したMuSig-DN

Blockstreamは以前、Schnorr署名を利用したマルチシグを構成する際にKey-Rogue攻撃への耐性を持たせる署名スキームMuSigを発表していた。Key-Rogue攻撃やMuSigの内容について以前解説した↓を参照。 goblockchain.network techmedia-think.hatenablog.com そ…

GrinのPoWアルゴリズムCuckoo cycleとその実装の脆弱性CVE-2020-15899

最近公開されたGrinの脆弱性CVE-2020-15899↓について見てみる。 https://github.com/mimblewimble/grin-security/blob/master/CVEs/CVE-2020-15899.md Cuckoo cycle GrinはDual Proof of Workという仕組みを採用している。これは1つはASICフレンドリーなPoW…

CVE-2017-12842とトランザクションサイズ

こないだのBitcoin Optechのニュースレターで取り上げられていたトランザクションサイズに関するトピックについて↓、本筋とは直接関係ないけど2017年に発見された脆弱性CVE-2017-12842について触れられていたので、どういった脆弱性だったのか見てみる。 bit…

Bulletproofのrange proofに任意のデータを埋め込む方法と復元する(rewind)方法

先日、Grinがウォレットリストアの際に自身のUTXOを識別するのにBulletproofsのrange proofにヒントを隠している記事を書いたけど、↓ techmedia-think.hatenablog.com 今回の記事では、リストアという限定的な利用方法だけでなく任意のデータをrange proofに…

Verifiable Delay Function

最近ブロックチェーン関連のペーパーでよく話題に上がる新しい暗号プリミティブVerifiable Delay Function(VDF)について調べてみた。 VDFに関する研究は、以下のサイトでまとめられている。 https://vdfresearch.org/ 今回はVDF Day 2019のDan Bonehのセッ…

未使用のUTXOを所有していることをUTXOを明らかにせず証明するプロトコルPoDLE

BitcoinトランザクションのプライバシーやFungibilityの向上のためCoinJoinを実装しているJoinmarketで提案されているPoDLEというプロトコルが面白かったので見てみる↓ joinmarket.me PoDLEプロトコル PoDLEが解決するのは、自分があるUTXOを所有していて、…

Bulletproofsを利用したrange proofの仕組み

techmedia-think.hatenablog.com ↑でBulletproofsの基本となる内積の証明の仕組みについて書いたので、今回はこれがCTやMimblewimbleなどで必要とされるrange proofにどう適用されるのか見ていく。 range proofとは? CTと同様Mimblewimbleなどでもコインの…

Bulletproofsにおける内積の証明

Bulletproofsは2017年にBünzらが発表したゼロ知識証明システムの一種で、Trusted Setupを必要とせず、プルーフが非常に短く、その集約が可能であるという特性を持っている。最初はConfidential Transactionの秘匿した値がある範囲内にあることを証明するrang…