Develop with pleasure!

福岡でCloudとかBlockchainとか。

Ristretto Group

Cryptography ECC

最近、よく見かけるRistrettoについて調べてみた↓

https://ristretto.group/

Ristrettoが解決すること

Ristrettoは、楕円曲線の内、曲線上の有効な点の総数（位数）が素数ではない楕円曲線から、位数が素数となる群を構築する抽象化レイヤーを提供するための手法。

位数が素数だと何が嬉しいのか？

  • 楕円曲線暗号の安全性は、楕円曲線上の離散対数問題（ECDLP）の困難さに基づいており、この難易度は曲線の計算に使用する群の位数が素数である場合に最大になる。
  • 単位元を除く群内のすべての点が生成元になり得る。
  • 群の演算（点の加算や、スカラー乗算）が比較的単純になる。
  • 安全な楕円曲線のパラメーターを選択するのが比較的単純になる。
  • 部分群（サブグループ）が存在しないので、t小さな部分群を利用した攻撃を回避できる。

最後の部分群を利用した攻撃について、暗号通貨で有名なのはMoneroに存在した脆弱性（実際に悪用されてはいない）↓

techmedia-think.hatenablog.com

といったことから、素数位数を持つ楕円曲線が多くの暗号プロトコルなどで推奨されている。Bitcoinで使用されている楕円曲線secp256k1も、位数は素数。

素数位数でない曲線

一方で最近の楕円曲線の実装では、位数が素数ではないことが多い（MoneroのCurve25519もそう）。なぜ位数が素数ではない曲線を使うのか？というと、演算がとても高速に行えるから。

これらの楕円曲線の位数Nは、素数位数の部分群の位数を {l}とした場合、 {N = h \cdot l}となる。hは余因子（cofactor）と呼ばれる値で、部分群と曲線全体の群の比率を表す値。 {l}が巨大な素数であるのに対して、hは通常1とか4とか8とか小さな値になる。secp256k1など素数位数の曲線の場合、h = 1となる（つまり曲線の群＝部分群）。

このような曲線上で暗号学的な演算を行う場合、それらの演算は基本的に素数位数 {l}の部分群において行われる必要がある。通常、群内の点に対する演算（スカラー乗算や、点の加算など）は、その結果得られる点も同じ群内に留まる（つまり群の演算は閉じている）。ただ、外部から不正な入力が与えられるような場合（例えば他のユーザーの公開鍵とか署名など）、与えられた点が期待する部分群内に属さない点であることがあり得る。

たとえば、↑のMoneroの件では、素数位数の部分群に属さない点をキーイメージとして提供することで不正を行う。この件ではキーイメージが素数位数の部分群内の点か検証する追加チェックを導入して対応しているけど、どのプロトコルでも単に位数lの乗算チェックを適用すればいい（適用できる）とは限らず、複雑なプロトコルの場合に元の安全性の証明が適用されなくなってしまう可能性もある。

上位プロトコルにおいて、このような脆弱性が発生しないように適切に余因子を処理していくのは、難易度の高いものになる。そこで、高速な演算の恩恵を受けつつ、余因子による煩雑さを考慮しなくても済むようにしようというのがRistrettoの目的。

Ristretto

RistrettoはMike HamburgのDecafという提案がベースになっている。Decafは、余因子 = 4のエドワーズ曲線とモンゴメリ曲線について、曲線上の点を特定の方法でエンコード/デコードすることで余因子の影響を受けない安全な素数位数の部分群を提供する。そしてDecafをベースとして余因子が8の曲線（Curve25519とか）をサポートしたのがRistretto。

Ristrettoが提供する機能は↓

  • 元の曲線の点を含む素数位数群の提供：
    これは、元の楕円曲線上の点に対して同じ暗号学的情報を持つ点を等価性クラスとして分類し、各等価性クラス内の1つの点を代表点として選択し、その代表点を使って素数位数の群を形成する。構成される素数位数群の位数は、元の曲線の素数位数の部分群の位数と一致する。
  • 点の等価性チェック：
    Ristrettoでは点の情報は内部的に元の曲線の点を使用している。この等価性チェックでは、内部表現の異なる2つの点の等価性をチェックする（内部表現が違っても同じ等価性クラスに分類されていれば等価とみなされる）。
  • エンコード関数：
    内部表現が等価な点についてはすべて同じビット列としてエンコードするエンコード関数
  • デコード関数：
    有効な点の正規のエンコードのみが受け入れられるよう、検証処理が組み込まれたデコード関数
  • Hash to Point演算に適したビット文字列からRistrettoの点へのマッピング

点の演算に関しては、内部表現を利用して高速な既存の曲線の計算をそのまま利用する。

既存の曲線の実装に対して、新しい型と上記関数を追加する薄い抽象化レイヤーによって必要な抽象化を利用者に提供している。

↑の関数の具体的な群の演算については、RFC9496に記載されているristretto255（Curve25519）とdecaf448（edwards448）の疑似コードが参考になる↓

RFC 9496: The ristretto255 and decaf448 Groups

また、エンコード/デコードについては、最初のサイトにそれぞれアフィン座標で行う方法と拡張座標で行う方法の説明がある↓

等価性の検証方法は↓

Hash to Pointの演算は、それぞれアフィン座標と拡張座標用に↓

この曲線上の点へのハッシュは、以前書いたHash to Curveなんかでも使用されているElligator 2を使ってまず要素をヤコビ四次曲線*1にマッピングして、同種写像を使ってエドワーズ/モンゴメリ曲線の点にマッピングするらしい。だから同種写像を用いた変換の説明がサイトの最初にあったのか。

間にこの曲線を挟むのは、直接マッピングするより特定の攻撃ベクトル（サイドチャネル攻撃や、点の判別攻撃、特定の数学的構造を利用した攻撃など）に対する耐性が上がりより安全性が高まるためとか。また、同種写像による変換も計算効率が良いので、コストも高くないそうな。

*1:方程式y2 = x4 + ax2 + bで定義される曲線。

v3トランザクションリレー

Bitcoin

最近Bitcoin Coreにv3トランザクションリレーポリシーのPRがマージされたので↓

github.com

v3トランザクションリレーについてまとめてみた。

トランザクションの手数料引き上げ方法と課題

Bitcoinでブロードキャスト済みのトランザクションの手数料を引き上げる方法は、主に以下の2つ。

制限とPinning攻撃

RBFやCPFPのような手数料を引き上げる仕組みは用意されているものの、無条件に実行できるとネットワークに対するDoS攻撃が可能になるため、それぞれ制限が設けられている。主な制限は、

  • BIP125 RBFルール：
  • 最大パッケージサイズの制限：
    CPFPを行う場合、mempool内に101KvBを超える子孫持つ場合、または25個を超える子孫/祖先を持つようなトランザクションはCPFPできない。

LNなどのマルチパーティコントラクトでは、上記の制限を悪用して低手数料のトランザクションをずっとmempoolに留めさせようとするPinning攻撃が問題になる。

RBFのルール3については、攻撃者は高手数料だがサイズが大きく手数料率は低い置換トランザクションを作成する。この場合、手数料率は低いのでマイニングされづらいが、誠実な相手がさらにそのトランザクションを置換しようとすると、高額な手数料の支払いが必要になる。誠実なユーザーのトランザクションがマイニングされると置換により攻撃者のコスト負担はゼロになり、誠実なユーザーのみが高額な手数料を負担した結果だけが残る。

ルール5については、子孫トランザクションも含まれるため、Pinningしたいトランザクションに多数の子孫トランザクションを作成することで、置換を困難にする。

CPFPの場合は、攻撃者が先に制限に達する大量の子トランザクションを作成することで（もしくはサイズ制限を超えるような）、それ以上CPFPできなくする。

このようなPinning攻撃は、タイムロックなどの条件が設定されているマルチパーティプロトコルにとっては厄介な問題になる。LNのような二者間のプロトコルにおいては、Bitcoin Core v0.19.0で追加されたCPFP carve outというポリシーによって、CPFPにおいて上記制限を超える場合も例外的に子の追加が可能になり、これを利用してPinning攻撃への対策を行ったアンカーアウトプットを導入している*1↓

techmedia-think.hatenablog.com

このような状況から、マルチパーティプロトコルではRBFではなくCPFP carve outベースの手数料の引き上げを採用している。

v3トランザクション

上記のようなPinning攻撃を回避して手数料の引き上げをより堅牢にするために提案されているのがv3トランザクションリレー。

これまでトランザクションのバージョンは、デフォルトのバージョン１と、OP_CSVのタイムロック機能を利用可能にするバージョン２が利用可能だったけど、今回導入した新しいリレーポリシーを利用可能にするのがバージョン３になる。

ただ、v3はトランザクションのあくまでBitcoin Coreのリレーポリシーに関する仕様であって、コンセンサスルールではない。v3トランザクションは、v2トランザクションと同じコンセンサスルールで評価される。

v3ルール

具体的には、バージョン3のトランザクションには以下のルールが適用される。

  1. BIP-125の置換可能性のシグナリングをしていない場合でも置換可能なトランザクションとして扱われる。
  2. 未承認のv3トランザクションの子孫について、子孫もv3トランザクションである必要がある（承認済みのv3トランザクションの子はv3でなくても良い）。
  3. v3トランザクションは未承認の祖先はすべてv3トランザクションである必要がある。
  4. v3トランザクションは複数の未承認の子孫を持つことはできない。なお、CPFP carve outポリシーはv3トランザクションには適用されない。
  5. v3トランザクションは複数の未承認の祖先を持つことはできない。
  6. 未承認のv3の祖先を持つv3トランザクションは、sigops調整後のトランザクションサイズが1000vB以下であること。
  7. 個々のv3トランザクションについて、パッケージ*2としての手数料率の要件を満たす場合、最小リレー手数料率を下回ることができる。

この結果、mempool内にあるv3トランザクションは子トランザクションを1つだけ持つことができ、v3子トランザクションは未承認の親を1つだけ持つことできる。そして、親子トランザクションはいずれもRBFによる置換が可能。その際、親子トランザクションの数の制限と、子トランザクションのサイズ制限により、RBFのルール3，5を悪用したPinning攻撃を回避できる。

v3リレーが可能になると、マルチパーティプロトコルでもRBFが利用可能になるため、LNの仕様変更も検討されている↓

https://bitcoinops.org/ja/newsletters/2024/01/24/#v3-ln

*1:carve outの例外は、参加者が2人より多いマルチパーティプロトコルでは機能しない。

*2:親子関係のあるトランザクションの順序付きリスト。通常は、トランザクション単体をネットワークにブロードキャストするけど、未承認の親子トランザクションを一緒にブロードキャストしたい場合に、それらをパッケージとしてブロードキャストできるようにしようという現在開発中の機能。どうしてパッケージが必要になるかというと、たとえばLNで、チャネルを閉鎖するのにコミットメントトランザクションをブロードキャストしようとするものの、手数料率が向上し、コミットメントトランザクション作成時の手数料ではmempoolに入らないような場合。CPFPで手数料上げようにも対象の親がmempoolに入らないことには使えないといった状況が起こる。そのため、高手数料な子と親を一緒にリレーできるパッケージのような仕組みが必要になる。

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

Cryptography 秘密分散

FROSTはSchnorrベースの閾値署名方式で、プロトコルの内容については過去の記事↓やGBEC動画参照。

techmedia-think.hatenablog.com

このFROSTを利用してBitcoinでマルチシグウォレットの開発を進めているFrostsnapというプロジェクト↓

https://frostsnap.com/introducing-frostsnap.html

の説明の中で、

With FROST you can add or remove signers after key generation while keeping the key the same. FROSTを利用すると、鍵生成後に同じ鍵のまま署名者の追加/削除ができる。

とあったので、具体的にどうやるのか調べてみた。

FROST

マルチシグの参加者数をn、閾値をtとして↑の記事に書いた分散鍵生成を実行すると、各参加者 {P_i}は、秘密鍵のシェア（定数項 {a_{i, 0}}）が含まれる多項式

{f(x)_i = a_{i, t-1}x^{t-1} + a_{i, t-2}x^{t-2} + ... + a_{i, 0}}

を保持し、各係数に対して楕円曲線上のベースポイントを乗算したコミットメント {a_{i, j}G}のリストを他の参加者と共有している状態になる。

また、他の参加者向けに、各参加者のIDで多項式を評価した結果 {(ID, f(ID)_i)}をシェアとして送信し、各参加者は他の全参加者の多項式のシェアを保持している状態になる。

マルチシグの公開鍵は、全参加者の秘密鍵のシェア {a_{i, 0}G}を合算した点＝ {P = \sum_{i=1}^{n}a_{i, 0}G}になる。

署名生成フェーズでは、↑のシェアを利用して多項式補間を実行して最終的に有効なSchnorr署名を生成する（詳細なプロトコルについては、↑の記事or動画参照）。

FROSTを利用したダイナミックなマルチシグ設定

Frostsnapのリポジトリをみたところ、それっぽいプロトコルの説明はなかったけど、FrostsnapチームのNickのGistにそれっぽい説明があった↓

https://gist.github.com/nickfarrow/64c2e65191cde6a1a47bbd4572bf8cf8

署名者の削除

n人のマルチシグ参加者から、1人削減する（t of nからt of n - 1に変更する）場合。削除されるユーザーがその後の署名プロセスに関与できないようにする必要がある。

この場合、n - 1人で再度シェアを生成し直す。この時、各参加者が保持する元のマルチシグの公開鍵Pに対して有効なシークレットシェアは変わらないようにする必要がある。これは分散鍵生成において、各参加者が再生成する多項式の定数項（ {a_{i, 0}}）については元の値を使用し、それ以外の項の係数は新たに生成しなおし、更新した多項式で生成したシェアを他の参加者に配布することで実現できる。

この場合、n - 1人の参加者が保持する各参加者のコミットメント値およびシェアの値は異なるものになるが、元の公開鍵Pに対して有効なシークレットシェアは有効なままになる。

上記のようにシェアを定期的に再生成するようなプロアクティブな秘密分散法を用いると、シェア更新後は古いシェアを攻撃に使うことはできなくなる。

閾値の削減

続いて、閾値tを削減する（t of nからt - 1 of n - 1に変更する）場合。

この場合は、削除する参加者のシークレットシェアを他の全参加者に開示する。各参加者はそのシェアを使って署名シェアを作成する。

※ nを減らさずにtだけ減らす場合、つまりt - 1 of n - 1ではなくt - 1 of nにする場合は、後述する方法で署名者を新たに追加する必要がある。

この方法の場合、削除対象の参加者のシークレットシェアが必要になるため、デバイスの紛失などでシークレットシェア自体にアクセスできないようなケースでは機能しない。

署名者の追加

署名者を追加して、n + 1にする（t of nからt of n + 1に変更する）場合は、削除より少し複雑になる。↑のGistでは、二通りの方法が説明されている：

Repairable Threshold Scheme

１つめは、シェアの修復を可能にする修復可能な閾値スキーム（Repairable Threshold Scheme＝RTS）の一種を利用するアプローチ↓

techmedia-think.hatenablog.com

フラグメントの共有

もう1つの方法は、予め決めた数（kとする）だけ後から署名者を追加するアプローチ。

  1. 鍵生成プロセスにおいて、各参加者は生成した多項式を使って、通常n個のインデックスに対してn個をシェアを作成する代わりに、n + k個のシェアを作成する。つまりk個の追加のシェアを計算する。このk個の追加シェアは後から署名者を追加するのに使用される。
  2. 各参加者はk個の追加シェアに対して、閾値tでシャミアの秘密分散法を用いて、n個のフラグメントを生成する。つまり、k × n個のフラグメントが生成される。そして生成したフラグメントを他の参加者と共有する。
  3. 新しい参加者（インデックスをn + 1とする）を追加する場合、t人の参加者が対象のインデックス（n + 1）に属するすべてのフラグメント送信する必要がる。結果、n × t個のフラグメントが集められたら、それらから新しい参加者用のシークレットシェアが作成できる。

閾値tを増やす

閾値tを増やす場合は、各参加者が生成する多項式の次数を増やし、全員が古い多項式を削除することを信頼する必要がある。次数を増やした多項式を生成するのは↑の署名者の削除と同様のアプローチでできそうだけど、後者のトラストポイントは残ってしまう。

というのが、FROSTを利用したマルチシグの設定変更の概要みたい。まだ実装や安全性の評価は行われていないようなので、利用可能になるまではまだ時間がかかると思われるけど、暗号技術だけでマルチシグの設定が変更できるというのは、おもしろい技術だ。マルチパーティでUTXOを共有するようなプロトコルでも、活用できるかも？

Bitcoin Core v22.0未満に存在したブロック遅延バグの開示

vulnerability Bitcoin

Optechのニュースレターに掲載されていた、Delving Bitcoinフォーラムで開示されたBitcoin Core v22.0より前のバージョンに存在したブロック遅延攻撃を可能にする脆弱性↓

https://delvingbitcoin.org/t/block-stalling-issue-in-core-prior-to-v22-0/499

脆弱性自体は3年前に責任ある開示が行われv22で修正されているけど、まだv22未満のノードを実行しているユーザーがいることから開示されたみたい。

脆弱性を悪用するとLNなどのタイムロック系のコントラクトを狙った攻撃を行えるが、↓の攻撃内容を見る限り攻撃を成功させるのもハードル高そう。

ブロック受信の遅延

まず攻撃をするためには、コンパクトブロックリレーを最初に無効化する必要がある。

Bitcoin Coreはマイニングされたブロックの受信にBIP-152で定義されているコンパクトブロックリレーを使用している。BIP-152については、↓

techmedia-think.hatenablog.com

BIP-152には実装に関して以下の記述がある：

充分なインバウンドの帯域幅は持つノードの場合、３つまでのピアに対して最初の引数に1をセットしたsendcmpctメッセージを送信する（＝high-bandwidthモードで動作させる）ことを推奨する。可能であれば、ここで選択する３つのピアは過去の実績において素早くブロック情報を返すピアを選択することが推奨され、ノードはそれらのピアからほんの0.5*RTTでブロックを受信することが可能になる。

と

ノードは（アウトバウンドの帯域幅をムダに使用することになるため）３つ以上のピアにhigh-bandwidthモードのsendcmpctメッセージを送ってはならない。

この結果、Bitcoin Coredeha高帯域幅のコンパクトブロックリレーを行う対象として、ノードに迅速にブロックの情報を提供するピアを3つ選択するようになっていた。

つまり、攻撃者が誠実なノードよりも速くブロックを提供できれば、このコンパクトブロックリレーのスロットを占有できる。攻撃にあたっては、まずはこれを占有して、コンパクトブロックリレー経由のブロックの通知を実質無効にする。コンパクトブロックリレーが有効に機能しないと、他のピアから新しいブロックのアナウンスを受け取り、従来のBLOCKメッセージを使って新しいブロックを受け取るしかない。

攻撃手順

  1. 攻撃者は、被害者のノードに対して、他のピアよりも速く新しいブロックを提供することで、ノードのコンパクトブロックリレーの3つの接続スロットをすべて占有する。
  2. 被害ノードとの間に1とは別にN個の異なる接続を開く。LNを対象として攻撃する場合、LNノードのCLTV deltaが40の場合はN = 50。※ ただし、このN個の接続は被害者ノードのコネクションマネージャーのvNodesベクトル内で連続している必要がある。
  3. 新しいブロックがマイニングされたら、N個の接続の内、先頭の接続が、他の誠実なピアと競争して、新しいブロックを被害ノードにヘッダーファーストで通知する。成功したら、被害ノードのmapBlocksInFlightにエントリーが追加される。その後、BLOCKメッセージを使って新しいブロックを送信する必要があるが、ここでその送信を遅延させて対象ブロックを配信しない。この時、被害ノードがブロックを待つのは10分まで。
  4. その間、1で設定したコンパクトブロックリレーの接続は新しいブロックについて何もアナウンスしない。
  5. 10分経過する手前で、先頭の接続は、無効なブロックをBLOCK`メッセージで送信する or 接続を単に切断する。
  6. そうなると、被害ノードはvNodes内の次の接続を選択して、遅延しているブロックを要求する。
  7. この次の接続でも攻撃者は同様の振る舞いを行い、ブロックの送信を遅延させる。
  8. これを繰り返すことで、N×10分間（N = 50の場合は約500分）被害ノードには新しいブロックがリレーされなくなる。

LNでの影響

↑の攻撃では、攻撃者によりコンパクトブロックリレーが実質無効化され、さらにN個の接続が連続して被害ノードのvNodesに挿入される必要がある。

もしそういう状況になると、LNで支払いを転送している場合に、そのHTLCの金額を盗む攻撃が可能になる可能性がある。具体的には、被害者BのLNノードに対して、攻撃者のノードM1とM2がそれぞれチャネルを開いている状態で、以下の経路で支払いが転送されるケースが対象になる。

M1 -> 被害者B -> M2

各LNノードのHTLC deltaの設定値を40と仮定した場合、攻撃のシナリオは以下のようになる：

  1. M1が上記の経路でM2に支払いを送信する。現在のブロック高をTとした場合、B→M2のHTLCはT + 40でタイムアウトし、M1→BのHTLCはT + 80でタイムアウトする。
  2. T + 38くらいで（もっと前でもいい）M1とM2が上記のブロック遅延攻撃を開始する。
  3. まずM2がBとのチャネルを強制クローズするTxをブロードキャストし、それがT + 39で承認される。
  4. 続いて、M2はプリイメージを使ってHTLCを請求するTxをブロードキャストし、それがT + 40で承認される。
  5. 今度はM1はT + 40でBとのチャネルを強制クローズし、それがT + 41で承認される。
  6. M1はT + 80まで待って、HTLCのタイムアウトTxをブロードキャストし、それがT + 81で承認される。
  7. M1とM2がそれぞれHTLCの金額を入手したので攻撃を止める。

この攻撃でも、Bのノードがmempoolを監視していれば、4の後でプリイメージをmempoolから抽出してM1のHTLCを回収できる。ただ、攻撃者がマイナーと協力して4のトランザクションをP2Pネットワークにブロードキャストせずに直接ブロックに格納してもらって配信すると、Bにはブロックが届かないためプリイメージを知ることができず攻撃の影響を受ける。

修正内容

この問題に対する修正のPRは以下の2つ。

ということで、攻撃が成功する可能性は低いと思うけど、まだアップデートしていない場合は要アップデート。

Repairable Threshold Scheme

Cryptography 秘密分散

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

RTSは、シャミアの秘密分散法などを使って、複数のパーティでシェアを分散して保持するスキームにおいて、後から参加者のシェアを復元できるようにするスキーム。↑の提案では、既存のシェアの復元ではなく、新しい参加者用に新しいシェアを作るのにRTSを利用することで、母数を増やす。

今回は、↓サーベイ論文に掲載されている内の１つEnrollementスキームについて調べてみた。

https://eprint.iacr.org/2017/1155.pdf

RTS

論文は、ディーラーがいるモデルで書かれており、参加者の母数をn、閾値をtとした場合、ディーラーはシークレット値を含むt-1次の多項式f(x)を生成し、n人の参加者に対して、割り当てられたインデックス {ID_i}で多項式を評価した結果 {(ID_i, f(ID_i))}をシェアとして配布する。

この場合、多項式を知っているディーラーがいればシェアの復元は可能だが、ディーラーが利用できない場合でも、閾値数分の参加者がいればシェアを復元できるようにするのがこのスキームの目標。

※ RTSをt - 1人で実行できると追加のシェアが作成され閾値tを超えるシェアを入手できてしまうため、必ずt人以上で実行しないと再構築できないようなプロトコルになっている必要がある。

※ また、閾値分のシェアが集まれば多項式補間で多項式が復元できシェアを計算できるようになるが、シェアを集める参加者が登場することになり実質ディーラーとなれるので、そういうアプローチではない。

シェアの復元

シェアを復元したい参加者を {P_r}、復元を支援するt人の参加者を {P_1, ..., P_t}とする。各参加者が保持しているシェアを {\phi_i = f(ID_i)}とした場合、 {\phi_r = f(ID_r)}を求めるのが目標。

ラグランジュ補間公式を利用すると {f(ID_r)}は以下を計算することで入手できる。

{f(ID_r) = \lambda_1(ID_r)\phi_1 + ... + \lambda_t(ID_r)\phi_t}

ここで、各ラグランジュ係数 {\lambda_j(ID_r)}（1≦ j ≦ t）は、

{\displaystyle \lambda_j(ID_r) = \Pi_{0 \leq m \leq t, (m \neq j)} \frac{ID_r - ID_m}{ID_j - ID_m} = \frac{(ID_r - ID_1) \cdot \cdot \cdot (ID_r - ID_t)}{(ID_j - ID_1)\cdot \cdot \cdot (ID_j - ID_t)}}

であり、各参加者の識別子（ {ID_1, ..., ID_t}）が分かっていれば計算できる。

Enrollementプロトコルでは以下の手順で、 {P_r}が {\phi_r}の値を計算できるようにする。

  1. t人の各参加者 {P_i}は、 {\lambda_i(ID_r)\phi_i = \sum_{j=1}^{t}\delta_{i, j}}となるようなt個のランダム値 {\delta_{i, j}}（1≦ j ≦t ）を生成する。各参加者は自分のシェアと上記のラグランジュ係数から {\lambda_i(ID_r)\phi_i}を計算できるので、t - 1個の {\delta_{i, j}}をランダムに生成して、最後の値は {\lambda_i(ID_r)\phi_i - \sum_{j=1}^{t-1}\delta_{i, j}}で計算すればいい。
  2. 各参加者 {P_i}は、計算した {\delta_{i, j}}を他の支援者 {P_j}に送信する。
  3. 各参加者 {P_j}は、 {\sigma_{j} = \sum_{i=1}^{t}\delta_{i, j}}を計算し、 {\sigma_{j}}を新しい参加者 {P_r}に送信する。
  4. {P_r}は、 {\phi_r = \sum_{j=1}^{t}\sigma_j}を計算し、シェア {\phi_r}を入手する。

1〜4の計算結果は、求めたかった最初の {\displaystyle \phi_r = \sum_{i=1}^{t}\lambda_i(ID_r) \phi_i}と同じになる。

各参加者は自分のシェア（正確にはラグランジュ係数を掛けた {\lambda_i(ID_r)\phi_i}）をt個分割して、他の参加者に配布し、それを全参加者分集めたら {P_r}が自身のシェアを計算できるようにしてるっぽい。