Develop with pleasure!

福岡でCloudとかBlockchainとか。

Cryptography

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…

TumbleBitに代わる新しいPayment Channel Hubプロトコル「Anonymous Atomic Locks」

Scaling Bitcoin 2019復習シリーズ第二弾は、Payment Channelの最近の研究といえばこの人、Pedro Moreno-Sanchezの「A2L: Anonymous Atomic Locks for Scalability and Interoperability in Payment Channel Hubs」 動画:https://youtu.be/Uh6Ywxrobzw?t=44…

MoneroでスクリプトレスなPayment Channelを実現するためのDLSAGリング署名スキーム Part2

Part1でDLSAGの仕組みについて整理したので↓ techmedia-think.hatenablog.com 続いて、DLSAGを利用して、Payment Channel Networkを構築する際に必要な構成要素を順番に見ていく。 MoneroでPayment Channel 上記のDual-Keyアウトプットを使った払い戻しトラ…

MoneroでスクリプトレスなPayment Channelを実現するためのDLSAGリング署名スキーム Part1

ベースの考え方であるLSAGについて整理したので↓ techmedia-think.hatenablog.com 本丸のDLSAGとDLSAGを利用したPayment Channelの仕組みについて見ていく。 https://eprint.iacr.org/2019/595.pdf Moneroの課題 BitcoinがBitcoin ScriptをEthereumがSolidit…

Linkable Spontaneous Anonymous Group(LSAG)リング署名の仕組み

こないだ開催されてたMonero Conference 2019でPedro Moreno-Sanchez*1がMoneroでPayment Channel Networkを実現するためのプロトコルについて発表していた↓ https://youtu.be/AsJaMw-3gGE?t=30157 ホワイトペーパーは↓ https://eprint.iacr.org/2019/595.pd…

マークルツリーを利用したハッシュベースのアキュムレータ「Utreexo」

BitcoinのUTXOセットを管理するにあたって、そのストレージ要件を大幅に削減すると期待されているアキュムレータ。昨年のScaling Bitcoinでは、スタンフォード大学のBenedikt BünzがRSAを利用したアキュムレータを紹介した↓ techmedia-think.hatenablog.com …

A scalable drop-in replacement for merkle trees at Scaling Bitcoin 2018

Scaling Bitcoin 2018復習シリーズ。今回は、昨年もBullet Proofsなど発表したスタンフォード大学のBenedikt Bünzによる「A scalable drop-in replacement for merkle trees」の発表で、内容的にはマークルツリーの代わりにRSAアキュムレータを利用したUTXO…

自称サトシになる方法

最近また自称サトシが登場してるみたいだったので、自称サトシになるために必要なことを調べてみた。 ecdsa - If someone wanted to pretend to be Satoshi by posting a fake signature to defraud people how could they? - Bitcoin Stack Exchange 自称サ…

離散対数仮定が崩れた際にConfidential Transactionチェーンのコインを保護するSwitch Commitment

Stanford Blockchain Conference 2019のGrinのセッションで、Grinの構成要素として挙げられていたSwitch Commitmentについて↓ https://eprint.iacr.org/2017/237.pdf Bitcoinなどの多くの暗号通貨では楕円曲線暗号を導入しており、楕円曲線暗号の安全性は離…

2017年に起きたMoneroのキーイメージを細工したコイン無限生成の脆弱性の内容

2017年2月に発覚したMonero(正確にはCryptoNoteのプロトコルを採用している暗号通貨)でコインを無限生成できる脆弱性について、原因が曲線の特性に起因するもので興味深かったので調べてみた。 ww.getmonero.org この脆弱性自体は実際にMoneroでは悪用され…

The GHOSTDAG Protocol at Scaling Bitcoin 2018

Scaling Bitcoin 2018 復習シリーズ。今回はヘブライ大学のYonatan Sompolinskyによる「The GHOSTDAG Protocol」の発表↓(30分あたりから) youtu.be 書き起こしは↓ ghostdag ホワイトペーパーは↓ https://eprint.iacr.org/2018/104.pdf Bitcoinのオンチェー…

2P-ECDSA: Fungible 2-of-2 MultiSigs for Today's Bitcoin at Scaling Bitcoin 2018

Scaling Bitcoin 2018 復習シリーズ。今回はLightning LabsのConner Fromknechtによる「2P-ECDSA: Fungible 2-of-2 MultiSigs for Today's Bitcoin」の発表↓ youtu.be 書き起こしは↓ scriptless-ecdsa 前半はLindellベースの2者間のECDSA署名プロトコル↓の解…

SchnorrベースのScriptlessな「Multi-Hop Locks」の実現方法

techmedia-think.hatenablog.com techmedia-think.hatenablog.com と書いたので、残ったSchnorrベースのMulti-Hop Locksについても書いておく。 (Multi-Hop Locksのコンセプトについては最初の記事参照) SchnorrベースのMulti-Hop Locksは署名アルゴリズム…

ECDSAベースのScriptlessな「Multi-Hop Locks」の実現方法

Scaling Bitcoin 2018のセッションの1つでもある、LNなどで利用されているペイメントチャネルネットワークの新しいプリミティブである「Multi-Hop Locks」について、以前一方向準同型関数を使った実装方法について書いたが↓ techmedia-think.hatenablog.com…

Schnorr署名と検証可能な秘密分散法を利用したm-of-nのマルチシグスキーム

SchnorrのBIPドラフト↓ https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki に応用例の1つとして記載されているのが、Scnorr署名とペダーセンの検証可能な秘密分散法を利用してm-of-nのマルチシグを構成するというもので、参照論文↓ htt…

DLCでオラクルが公開した署名からシークレットを生成するコードを書いてみた

去年発表されたDiscreet Log Contractsについて↓ https://adiabat.github.io/dlc.pdf techmedia-think.hatenablog.com オラクルが作成するのがSchnorr署名だったので、最初読んだとき現状のBitcoinでは実装できないと勘違いしてたんだけど、オラクルが公開す…

効率的な二者間のECDSAプロトコル

以前、Andrew PoelstraがBitcoinスクリプトを書くことなくスマートコントラクトを実現するScriptless Scriptsについて紹介されていたが、これはいずれもSchnorr署名を必要とする仕組みだった。現在のBitcoinのプロトコルでサポートしているのはECDSAのみであ…

Schnorrベースのマルチシグネチャスキーム「MuSig」

先日、Gregory MaxwellとAndrew Poelstra、Yannick SeurinとPieter Wuilleらによって、Schnorr署名を使ったマルチシグスキームのホワイトペーパーが発表された↓ https://eprint.iacr.org/2018/068.pdf これに関する記事をPeiter WuilleがBlockstreamのブログ…

どうしてECDSA署名から公開鍵が復元できるのか?

ECDSAの署名からどうして公開鍵が取得できるの?という聞かれて何でだろうねって話になったので調べてみた。 署名から公開鍵のセットを復元 Rubyではecdsaのgemを使えば以下のように署名と署名対象のメッセージから公開鍵を取得できる。(署名対象のメッセー…

取引所の支払い能力を証明する(Proof of Solvency)Provisionsプロトコル

Mt.Goxの破綻後に発表された取引所の支払い能力を証明するプロトコルProvisionsのホワイトペーパー↓ http://www.jbonneau.com/doc/DBBCB15-CCS-provisions.pdf 仮想通貨を取り扱う取引所では、一般的な銀行の仕組みである部分準備金銀行のようなアプローチは…

Proofs of Proof of Work

Scaling Bitcoin 2017のFlyClientの内容を追っていったら前提としてNiPoPoWs(Noninteractive-Proofs-of-Proof-of-Work)→ PoPoWs(Proofs of Proof of Work)と関連研究が続くので、まず最初にProofs of Proof of Workのプロトコルについて調べてみる。 Pro…

Confidential Assetsの概要

Blockstreamが新しくConfidential Assetsなる機能をリリースしていたので、どういったものなのか見てみる。 blockstream.com Open Assets ProtocolやCounterpartyやColuなどBitcoinのブロックチェーン上で、Bitcoin以外のアセットを発行・送付するプロトコル…