ASICパズルの結果
Results from the ASIC puzzle (blog.janestreet.com)
要約
Jane Streetが公開したASICパズルでは、参加者は提供されたチップのGDSレイアウトからその機能をリバースエンジニアリングすることが求められました。約400件の応募があり、多くの参加者が様々なツールやプログラミング言語を駆使しました。このチップは、11x11のスターバトルパズル(ツー・ノット・タッチ)のハードウェアチェッカーであることが判明しました。
全文翻訳
記事一覧
[1] タイトル: Results from the ASIC puzzle
URL: https://blog.janestreet.com/asic-puzzle-results/
本文:
[画像: パズルASICの物理レイアウトと、JSCという文字を象る22個の星と領域を持つ11x11のスターバトルグリッドが完成した様子]
8月に、私たちはパズルを公開しました。これは、小さなチップの最終的なGDSレイアウトを与え、その機能が何であるかを逆解析するように求めるものでした。物理レイアウトは提供しましたが、ネットリストや内部信号名は提供せず、参加者に内部を逆解析してもらいました。
この記事では、チップが何をするのかを明らかにし、あなたがそれを解決したさまざまな方法を探求し、お気に入りの提出物の一部に言及します。
提出物
米国、インド、英国、オーストラリアからの応募が大部分を占め、30カ国以上から約400件の提出がありました。参加者には、高校生、研究者、現役エンジニア、退職者などが含まれていました。ほとんどのソルバーは、KLayout、Yosys、Z3に加え、Python、Rust、C++、OCaml、Haskell、さらにはOdinで実装されたカスタムツール(多くはAIで作成)を使用しました。
解法
多くの皆さんが発見したように、このチップは11x11のスターバトルパズル、別名「Two Not Touch」のハードウェアチェッカーです。目標は、各行、各列、および各色分けされた領域に正確に2つの星を配置することです。2つの星は、対角線上であっても、互いに触れてはなりません!
チップは121サイクルの入力を受け付け、各入力は対応するマスに星を配置するかどうかを示します。その後、これらの入力に対して複数の並列チェックを実行します。
- 各行および各列の2ビットカウンタ。それぞれが正確に2つの星を持つことを要求します。
- マスを領域にマッピングする121ビットROMと、各領域の2ビットカウンタ。それぞれが正確に2つの星を持つことを要求します。
- 近くのマスを追跡するための遅延線。これにより、2つの星が対角線上であっても決して触れないようにします。
- 特定のイースターエッグ出力を生成するために使用される、星の総数をカウントするカウンタ。
これらのパズルチェックはANDされ、成功信号を生成します。
出力ジェネレータはROMに文字列を格納します。解決策がプレーンテキストとして表示されないように、ゲームボードに基づいた小さなLFSRによって難読化されています(ただし、LFSRを攻撃するのを止めることはできませんでした!)。
成功が達成されると、出力ロジックは解決策文字列を難読化解除して出力します!
(* TWO STARS *)
[画像: シミュレートされたクロック、イネーブル、成功、および出力信号。成功は121番目の入力ビットの後に上昇し、出力は1クロックあたり1バイトで(* TWO STARS *)と表示されます]
ほとんどの不正解は「TRY AGAIN」という文字列を出力しますが、いくつかはこの後述するイースターエッグをトリガーしました。
このパズルチップは、SKY130オープンソース標準セルライブラリを使用し、LibreLaneツールチェーンで設計されました。
皆さんがどのように解いたか
以下では、パズルを解くのに伴うステップを、お気に入りの解説の一部からの例とともに説明します。
最初のステップは、GDSレイアウトからゲートレベルのネットリストを抽出することでした。開始を容易にするために、セル名(sky130_fd_sc_hd__nand2_2など)をGDSファイルに残しました。これにより、MagicやKLayoutなどのツールでLVS[1]パスを使用して、生のゲートレベルネットリストを抽出することができました。
しかし、一部の人々は、独自のネットリスト抽出ツールを作成するという追加の課題に取り組みました。Vladislav Shapovalovの解説は、彼がC++で独自の抽出パイプラインをどのように作成し、GDSを解析し、各セルの形状を抽出し、セル名と組み合わせて完全な論理ネットリストを生成したかを示しています。その後、ウォームアップデザインで試行錯誤を行い、パイプラインをデバッグしてから、メインのパズルGDSの抽出に使用しました。
[画像: 同じローカルチップジオメトリが、左はマスクレイヤーで、右は復元された電気ネットで色分けされており、電源レール、コンタクト、セル境界がラベル付けされています]
(Vladislav Shapovalovの解説の図1よりトリミング)
ネットリストのシミュレーション
ネットリストを復元すると回路グラフが得られますが、それをシミュレートするには、各セルがどのように動作するかを知る必要もあります。一部のソルバーはVerilogを生成し、SKY130セルモデルを既存のシミュレータで使用しました。一方、Stephen Ebertのような他の人々は、レジスタ間のロジックを計算し、各クロックエッジでレジスタを更新する独自の評価器を構築しました。
提供された波形は、入力シーケンスを再生し、比較対象となる期待される出力を与えました。同じシミュレータを使用して、候補ボードをテストし、出力ジェネレータを実行して回答を読み取ることができました。
しかし、その波形に一致したからといって、シミュレータが正しいとは限りません。Alejandro Soto Francoは、すべてのタイハイセルを間違って評価したにもかかわらず、提供されたトレースを再現したPythonモデルについて説明しています。これらのセルは定数1を供給すべきですが、モデルはそれらを評価しなかったため、出力はゼロのままでした。
この間違いは、隣接チェックを事実上無効にしました。そのモデルを使用したソルバーは、隣接する星を持つ、一見有効なボードを見つけることができました。Alejandroは、追加の入力に対する別のIcarus Verilogシミュレーションと比較することで、この問題を発見しました。
ロジックのウォークスルー
一般的なアプローチ、そして私たちが最も期待していたのは、「成功」出力から始めて、ネットリストを逆にたどって、有効な入力の条件を特定することでした。フロアプランにいくつかのヒントを残しました。レイアウトの各「島」は、元のRTLデザインの単一モジュールに対応していました。
Sanjay Ravishankarはこれを最大限に活用し、各領域の上に境界ボックスを描き、次に回路図をこれらの境界ボックスに分割しました。彼は、この作業の素晴らしい視覚化を彼の解説に含めています。彼の解説の素晴らしい視覚化。モジュール間の接続を見てモジュール境界を確認した後、各モジュールをシミュレートしてその機能と、それが全体像にどのように適合するかを理解しました。
[画像: Sanjay Ravishankarの注釈付きチップレイアウト。破線ボックスはカウンタ、ルールチェッカー、領域マップ、および出力ジェネレータを識別しています]
Sanjay Ravishankarの注釈付きレイアウト。論理の島が機能別にラベル付けされています。彼の解説からの図。
動的探索
別のアプローチは、さまざまな入力でチップをシミュレートし、ロジック関数自体をあまり気にせずに、中間信号がどのように変化するかを観察することでした。
Aaron Shiは、信号とシステムクラスで学んだことを活用し、「ネットリストをシステムとして扱い、さまざまな位置にインパルスを与えました…その後、すべてのフリップフロップをゼロベースラインと比較しました。変化するフリップフロップは、その1ビットへの応答です」と彼の解説に書いています。彼の解説。彼はその後、フリップフロップが行、列、領域に対応していることを観察し、それぞれが正確に2に集計する必要があることに気付きました。そこから、成功に必要な条件を満たすソリューショングリッドを構築しました。
[画像: チップ上のレジスタ位置。すべて1の実行中に最初にハイになったサイクルで色分けされています。行カウントと隣接拒否フラグが強調表示されています]
Aaron Shiのシミュレータ。レジスタは、すべて1の実行中に最初にハイになったサイクルで色分けされています。このすべて1の実行は、行カウントと隣接チェックをトリガーします。彼の解説からの画像。
SATソルバー
私たちが目にしたもう一つのアプローチは、回路が何をするのかを知る必要なしに、SATソルバーを使用して正しい解を見つけることでした。ある意味で、SATソルバーはこの種の課題に完全に適しています。固定数のクロックサイクルでエンコードされた回路を受け取り、特定の条件(この場合は成功出力)を真にするために必要な入力を計算できます。このようなツールは、ハードウェア検証でも頻繁に使用されます。SATソルバーを使用して、チップが望ましくない出力動作を持つ入力のセットが存在するかどうかを証明します。
しかし、このような課題にSATソルバーを使用する欠点は、チップの内部構造についてはあまり明らかにならず、望ましい出力状態に到達するために必要な入力だけがわかることです。しかし、Lokesh Aravapalliは、両方の世界の最良の部分を見つけました。彼は最初にSATソルバーを使用して有効な入力セットを取得しましたが、その後、それらの入力を使用して実際に回路の目的を分析および理解し、回路のクールな視覚化を構築しました!
出力ジェネレータのクラッキング
このようなパズルでは、常に予期しない解決策と非正統的な思考が存在します。人々は、私たちが作成中に考慮しなかった方法でパズルを解決する方法を見つけました!
一部の人々が試みたのは、出力モジュールから直接解決策文字列を抽出することでした。チップには、LFSR[2]の形式で基本的な難読化が含まれており、ボードの「チェックサム」を計算し、それを解決策文字列とXORしてからROMに格納していました(これにより、回路を編集して「成功」入力を出力ジェネレータに直接供給しても、スクランブルされた出力が得られるだけでした)。しかし、Gabriel Taboadaは、これがどのように機能するかに興味を持ち、最終的に出力回路を逆解析しました。解決策がどのようにエンコードされているか、そして正しい出力を得るためにどのシードが必要かを正確に理解しました。
素敵な視覚化
逆解析について私たちが好きなことの一つは、このような課題に取り組むためのユニークな方法がどれほどたくさんあるかということです。さまざまな人々がどのように課題に取り組んだかを見る最良の方法の一つは、彼らが構築した視覚化を介してです!
- Joshua Stapletonは、ネットリストレイアウトビューアを構築しました。これは、回路図とレイアウトを並べて表示し、セルが階層モジュール間でどのように接続されているかを示します。
- José Vargasは、チップがPMOSとNMOSトランジスタからどのように構築され、レイアウトからそれらを抽出して各セルの論理関数を特定したかのクールな視覚的なウォークスルーを作成しました。
- 手動でスターバトルパズルを解くのが好きな人のために、Amruth Gulawaniは、チップにエンコードされたパズルのオンラインプレイ可能なバージョンを作成しました。不正解の特別なイースターエッグ出力も含まれています。
- おそらく私たちのお気に入りの視覚化:Kjartan van Drielは、チップがどのように構築され、パズルチップのすべての機能がどのように組み合わされているかの美しいインタラクティブなアニメーションウォークスルーを設計しました。
その他見たクールなもの
- Alexander Smallwoodは、抽出されたネットリストをFPGAに合成し、スイッチとLEDを使用してチップのI/Oを表すことで、パズルでさらに楽しむことにしました!
- Nikhil Kaniyeriは、ネットリストをMinecraftコマンドブロックにコンパイルして、ゲーム内でパズルのプレイ可能なバージョンを再現するという課題に取り組みました。
- David Garnerは、チップ全体をアナログSPICEシミュレーションに変換して、アナログドメインで最終的なソリューションを検証しました。
- Marcin Wójcikは異なるアプローチを試しました。彼は、解決策を明らかにすることなく、解決策を持っていることを証明できるGroth16ゼロ知識証明を構築しました。
——————————–
イースターエッグ!
追加の楽しみとして、パズルにイースターエッグを追加しました。その多くは、人々が見つけることができました!提出物の中で、2人が意図された6つすべてを見つけました。7つ目(最後のフローティングワイヤバグを含む)を見つけた人は6人でした。
[画像: 1,366個のmetal-2形状でできたJane Streetロゴと、PER ARENAM AD ASTRAと書かれたレイヤー200のモース符号]
example_inputs.vcdの2つの失敗した試行を7ビットASCIIとしてデコードすると、「THE NIGHT SKY AWAITS」になります。- VCDヘッダーは
Sat Dec 31 23:59:60 2016という実際のうるう秒の日付になっており、$version文字列は波形ビューアでファイルを見るように促します。 - ダイの下にある、通常は使用されないレイヤー上のマークの列は、モース符号で
PER ARENAM AD ASTRA(「砂漠を通り、星へ」)と書かれています。 - いくつかの失敗メッセージがあります。すべてゼロは
EMPTY SKYを、すべて1はBIG BANGを与えます。カウントはパスするが隣接する星があるボードはTWO NOT TOUCHヒントを選択します。他の拒否された入力はTRY AGAINを受け取ります。 - met2上の約1,400個の孤立した正方形が57x57ピクセルのJane Streetロゴを形成しています(上の画像で見ることができます)。
- 11個の領域をレンダリングすると、その形状は「JSC」と書かれています。
TWO NOT TOUCH出力パスには未接続のワイヤがあり、シミュレーションでTWO"NOT TOUCHが見られた理由です。これは元々レイアウトのバグでした。LVSパスで捕捉しましたが、 extra easter eggとして残しておき、誰がそれを捕捉するかを見ました!多くの人がそれをフローティングa31oi入力まで診断し、数人が親切にバグとして報告してくれました。
まとめ
AIはこのような課題の一部となり、解析、ネットリスト表示、デバッグツールの構築においてゲームチェンジャーとなるでしょう。一部の参加者は、それを小さなスクリプトに使用したと説明しました。他の人はエージェントにパズル全体を与えました。私たちが最初にパズルを思いついたとき、最新のモデルに単一のプロンプトを与えれば、30分以内に最終的な解決策を思いつくことができることもわかりました。しかし、これはパズルを解く楽しみと学習の多くを奪ってしまいます!
いくつかのソルバーは、すでに答えを見つけた後も調査を続けました。SATソルバーは勝利の入力を提供できますが、彼らはまだチップが何を数えており、その配線がパズルのルールをどのようにエンコードしているかを理解したいと思っていました。その好奇心が、私たちの好きな解説のいくつかに繋がりました。回路がどのように機能したかを説明するもので、正しい文字列が表示されたら止まるものではありませんでした。
デバッグの最も良い話のいくつかは、ソルバーが意図的に自分のツールを壊そうとしたことから来ています。サンプル波形を完全に再現したモデルでも間違いが含まれていました。個別の実装を比較し、失敗すべき入力を構築することで、例を再生しても捕捉できなかったエラーが露呈しました。これは、AIがツールをチェックするよりも速く構築することを容易にするため、パズルを超えて役立つ習慣です。
チップを分解する時間を割いてくれたすべての人に感謝します。特に、次の人が参考にできるようにプロセスを詳細に記述してくれた人々に感謝します。非常に多くの素晴らしい解説があったため、すべてを紹介することはできませんでしたが、皆さんが行った努力に本当に感謝しています!
チップの分解を楽しんだなら、私たちのプロトコルエミュレータASICコンペティションで独自のチップ設計に挑戦してみてください。この課題は、UART、SPI、I2Cなどのプロトコルを処理できるオープンソースのプログラム可能なチップを構築し、製造後に新しいプロトコルをサポートするのに十分な柔軟性を持たせることです。お気に入りのデザインは製造費用を負担し、受賞者には実際のシリコンでテストするためのチップと開発ボードが提供されます。応募締め切りは2027年1月18日です。
Jane Streetのハードウェア
Jane Streetのハードウェアチームは、世界最速の取引システムのいくつかを実行するFPGAとASICを設計しており、日々の仕事は、ゲートの海、タイミングレポート、または波形を見つめ、何が本当に起こっているのかをゆっくりと解き明かす、このようなパズルに満ちています。これらの問題は、解決することに深い満足感を与えるような難しさがあり、正直なところ、それが私たちがここで働くのが好きな大きな理由です。
それが魅力的だと感じるなら、さらに学ぶためのいくつかの方法があります。
- 私たちのハードウェア(FPGAおよびASIC)のインターンシップとフルタイムの募集をご覧ください。
- Hardcaml(私たちのオープンソースOCamlハードウェア設計ライブラリ)について読んでください。
- 学術面では、私たちの客員研究員および大学院フェローシッププログラムについて読んでください。
連絡を取り続けたい場合は、このフォームに記入してください。
- LVSは「Layout vs Schematic」の略で、通常、チップ設計フローの最後に、最終的なレイアウトが初期RTL設計と論理的に同等であることを検証するために使用されます(例:ルーティングプロセス中にワイヤがドロップまたは誤接続されなかったこと)。しかし、既存のレイアウトファイルからネットリストを抽出するためだけに使用することもできます。↩
- Linear Feedback Shift Register(線形帰還シフトレジスタ)は、入力ビットストリームに基づいて擬似乱数出力を生成する非常に小さな回路です。データの整合性のためのチェックサムの計算によく使用されますが、ここではソリューションボードのチェックサムに基づいて出力文字列をスクランブルするために使用しました。↩