Contact

【CTO Tech Blog】現状のBitcoinでコベナンツを可能にするColliderScript

  • CTO Tech blog

2010年にOP_CATを含む複数のopcodeがBitcoinで無効になり、その後の研究でこの時無効になったopcodeがあれば、実はBitcoinコベナンツを実現できることが判明するも、無効化された現状のBitcoinコベナンツを実現する方法はこれまでなかった。ところが最近、現状のBitcoinのままでコベナンツを実現するColliderScriptという仕組みが発表された↓

https://eprint.iacr.org/2024/1802

※ ただ、この仕組みで作成されたコベナンツを使用する(アンロックする)際に、約5000万ドルという法外なコストがかかるので、気軽に使えるようなものではない。*1

ペーパーでは、Bitcoin Scriptのopcodeを2つに分類している:

  • Big Script:署名やハッシュ計算など、暗号オブジェクトを操作するためのopcodeのセット。
  • Small Script:32bitの算術演算を行うopcodeのセット。サイズ的に暗号系の演算には使用できない。

シンプルにコベナンツをサポートするには、トランザクションのイントロスペクションを可能にするようBig Scriptを拡張する必要がある。間接的な方法としては、OP_CATを再導入してSchnorrトリックなどと組み合わせてBig ScriptとSmall Script間を連携するという方法がある。今回の提案は、Big ScriptとSmall Script間の連携を別の方法で実現しようというもの。

概要を理解するのは、↓のBitcoin-Devメーリングリストの投稿の方が分かりやすい。

https://groups.google.com/g/bitcoindev/c/cLiwlH6sC3o/m/4sSBUyYEBAAJ

ColliderScript

OP_CATとSchnorrトリックでは、スタック上でトランザクションデータを構成するのにOP_CATを使用していた。そのようにして構成したトランザクションデータをスタック上でハッシュし(sighashの導出)、その値+1が有効なSchnorr署名の値であることを検証する。

このトランザクションデータの作成とそのハッシュの計算を代替するために、ColliderScriptでは、Small ScriptをベースにBitcoin Scriptを使って実装するハッシュ関数を利用する。この時使用されるSHA-256については、既にBitVM用に用意された実装がある↓

https://github.com/BitVM/BitVM/blob/main/src/hash/sha256.rs

Big ScriptであればOP_SHA256 opcodeで1 byteのスクリプトハッシュ値は求められるけど、↑の場合、344KBのスクリプトになる。

このSmall Scriptベースのハッシュ関数を利用することで、指定されたトランザクションハッシュ値を求めることができ、OP_CATの代わりになる。

こうやって計算したハッシュ値をSchnorrトリックを使ってSchnorr署名として検証することでコベナンツを適用できるが問題が残る。OP_SHA256の場合、ハッシュ値は256 bitだけど、32 bit演算しかサポートされないSmall Scriptの場合、ハッシュ値は32bitずつのチャンクに分割された値のリストになる。

たとえば、Big Scriptで計算したハッシュ値

428a2f9871374491b5c0fbcfe9b5dba53956c25b59f111f1923f82a4ab1c5ed5

は、Small Scriptで表現すると

[0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5]

という形式になる。

署名検証はBig Scriptで行われるので、Small Scriptで計算したデータをそのまま署名検証に使うことができない。そして、これらのチャンクデータが、Big Scriptの256 bitのハッシュ値と一致することを直接確認するための方法もないので、このままでは署名検証に使えないという問題が発生する。

ハッシュの衝突を利用した等価性の証明

この問題を解決するのが、ColliderScriptのキーとなるアイディアで、ハッシュの衝突を利用して32 bitのSmall Script要素のベクトルとしてエンコードされた署名とBig Scriptで扱う署名が同じ署名であることを示すというもの。

Bitcoin Scriptの値(A)とSmall Scriptの値(B:実際には32bitチャンクのベクトル)の等価性の証明は、以下のチェックが成立するようなXの値を見つけることで実現できる。

まずBig Scriptで

OP_SHA1(A) = OP_SHA1(X)

をチェックし、Small Scriptで↑のSHA256のようにBig Scriptで実装したSHA1の実装(仮にSmall_SHA1とする)を使って、

Small_SHA1(B) = Small_SHA1(X)
OP_SIZE(X) = 32 bit

をチェックする。これら式が成立するためには、前提としてAとBのハッシュ値と衝突する要素Xを見つける必要ががある。SHA1は160 bitのハッシュ関数なので、衝突を見つけるのに286286の計算が必要になる。これは法外なコストがかかるものの計算自体は不可能なものではない。

これが成立する場合、AとBの値は等しいとみなすことができる。もしAとBの値が異なる場合、ハッシュ値に対して3つの衝突(A, B, X)を見つける必要があり、このような衝突を見つける場合、21102110の計算が必要で、現状は計算不可能だから。

ただ、X = 32 bitの範囲で上記を満たす衝突を見つけるのは困難で、160 bitのハッシュ関数で衝突を見つける場合80 bit以上の入力が必要になる。この課題に対処するために、Xの代わりに入力をπ = (t, w)とし(wは33bitのデータ要素、tは32bitのビットのリスト)、以下を実行する関数D.Genを使用する。

  1. res = SHA1(w)を計算し、
  2. tの各bit値について
    • bit = 0の場合、res = SHA1(res)を実行し、
    • bit = 1の場合、res = RIPEMD160(res)を実行
  3. resを返す

なお、この等価性のチェックに使用するSHA1とRIPEMD160は、Big ScriptにはそれぞれOP_SHA1OP_RIPEMD160という専用のopcodeがあるけど、Small Scriptでは↑と同様にBitcoin Scriptでそれぞれのハッシュ関数を実装する必要がある。

この等価性の証明を利用して、Big Scriptの値とSmall Scriptの値の一致を保証することで、OP_CATのないSchnorrトリックによるコベナンツが可能になる。

というのがColliderScriptの仕組み。衝突を見つけるための法外なコストと、Small Scriptで各ハッシュ関数を実装することによるトランザクションサイズの肥大化がネックになるが、ただ不可能ではない。

よくこんなの考えつくなー。

*1:コベナンツのUTXOを作成する=ロックするのは通常のトランザクション手数料で済む

本記事の元ページ

https://techmedia-think.hatenablog.com/entry/2024/12/18/222711

話題のキーワード