Sing-song: 長い数字やキーのための発音可能なエンコーディング

Sing-song: 長い数字やキーのための発話可能なエンコーディング

これは、Nostrのnpubキー（最後のセクション参照）の決定論的な「ユーザー名」を生成する方法として始まった楽しい実験です。

単純な音節でさえ英語は非常に扱いにくいため、結果は私が望むほど良くはありません（電話で他の人に伝えても正確に理解してもらえるような文字列）、しかし、悪くもないです――もし誰もがイタリア語を歌うように話せば、Sing-songはもっと価値があるでしょう :-)

---

ステータス: ドラフト、v0.1.2 --- コメント歓迎

概要

Sing-songは、任意のバイト文字列を、発音可能なCV音節に双方向にエンコードするものです。その64音節のアルファベットは、各6ビット値を直接1つの音節にマッピングします。完全なエンコーディングはバイト長と先頭のゼロバイトを保持し、外部の長さメタデータは不要で、正規化されています。

このエンコーディングはプレフィックス安定です。共通の入力プレフィックスは共通の音節プレフィックスを生成します。オプションのバリアント接尾辞は、同じバイト文字列の代替の双方向表現を提供します。

動機

HexやBase58のような機械指向のエンコーディングはコンパクトですが、話したり、書き取ったり、覚えたりするのが困難です。Sing-songは、決定論的、可逆的、計算上単純でありながら、書き込み密度を犠牲にして、小さく規則的な発音文法を獲得します。

設計目標

エンコーディングは、決定論的、可逆的、プレフィックス安定、訓練なしで発話・書き取り可能、完全なバイト文字列に対して自己サイズ調整、そして負荷を担う句読点なしで自己区切りであるべきです。

エンコーディング

アルファベット

子音と母音は厳密に交互になり、クラスターやコーダのない64個の開CV音節を生成します。位置の偶奇性がシンボルテーブルを決定します。h、y、e は、それらの発音が比較的不安定なため省略されています。

音節とグループ化

各音節は正確に6ビットをエンコードします。表示グループは、化粧的なハイフンで区切られた2つの音節（zila、sibo）を含みます。

パーサーはハイフンを無視しなければなりません: zilasibotivajuzu と zila-sibo-tiva-juzu は同一です。グループは自然な発話のチェックポイントを提供します。

発音

Sing-songは、すべての文字に対して固定の発音を使用します。スペルは音韻的です。各文字は1つの音を表し、同じ文字は常に同じように発音されます。

以下のIPA値が規範的です:

母音は純粋な母音であり、英語のスペル規則に従って解釈されてはなりません。特に、i は /i/、o は /o/、u は /u/ であり、/aɪ/、/oʊ/、または /juː/ とは発音されません。

各文字は独立して発音されます。無音の文字、二重字、または文脈依存の発音はありません。

単語は、各子音-母音ペアで音節に分割され、ストレスは最初の音節にかかります。

例:

わずかなアクセント依存の発音の違いは、エンコードされた文字が区別可能である限り許容されます。

アルゴリズム

入力をビットストリームとして扱い、最も重要なビットを最初に6ビットチャンクに分割します。各チャンクは直接1つの音節にマッピングされます:

ビット 5..2  → 子音インデックス 0..15
ビット 1..0  → 母音インデックス 0..3

入力バイトが L 個の場合、n = ceil(8·L / 6) 個の音節が出力されます。最後のチャンクが6ビット未満の場合、その下位ビットはゼロで埋められます。これらのゼロは正規のパディングであり、情報を含みません。

完全なエンコーディングは自己サイズ調整可能です: L = floor(6·n / 8)。デコーダーは6ビットチャンクを再構築し、L を推測し、最初の 8·L ビットを返します。非正規の音節数または非ゼロのパディングは拒否しなければなりません。先頭のゼロバイトは保持されます。

これは完全なエンコーディングに適用されます。切り詰められたプレフィックスは、それ以上の音節が続くかどうかを示しません。

k 個の音節のプレフィックスは、エンコードされた値の最初の 6k ビットをコミットし、デコードではなく再計算によって検証されます。

バリアント

バリアントは、同じバイト文字列の代替の双方向表現です。バリアント識別子は表現自体にエンコードされるため、デコードに外部メタデータは不要です。

入力 X とバリアント v = 0…15 に対して:

M(0, n) = 0^n
M(v, n) = SHAKE-256("sing-song/variant" ‖ byte(v), n)    for v > 0
Y       = X XOR M(v, len(X))

通常のSing-songコーデックで Y をエンコードします。XORは自己逆なので:

X = Y XOR M(v, len(Y))

マスクは公開されており、機密性を提供しません。SHAKE-256は決定論的なストリームを生成し、前述のプレフィックス安定性のプロパティを保持します。バリアント0は直接エンコーディングです。

バリアント識別子は、2文字の接尾辞としてレンダリングされます。1つの母音の後に l m n r のいずれかが続きます:

v = 4·i + j   ここで母音 = "aiou"[i]、子音 = "lmnr"[j]

 0=al  1=am  2=an  3=ar    4=il  5=im  6=in  7=ir
 8=ol  9=om 10=on 11=or   12=ul 13=um 14=un 15=ur

バリアント0は接尾辞なしでレンダリングされるべきです。パーサーは明示的な al を同等として受け入れる必要があります。

偶奇性により接尾辞が曖昧でなくなります。コンテンツの子音は奇数位置を占めるため、奇数位置の母音はバリアント接尾辞の開始にのみなり得ます。パーサーは正確に2つの末尾文字（母音の後に l/m/n/r）を要求し、他の偶奇性の違反は拒否しなければなりません。

プレフィックス安定性

各完全な音節は、正確に6つの連続する入力ビットを表します。したがって、2つのバイト文字列が最初の 6k ビットを共有する場合、それらの直接のSing-songエンコーディングは最初の k 音節を共有します。

バイトアラインされたプレフィックスの場合、境界は24ビットごとにバイト境界と音節境界の両方になります:

3 バイト = 24 ビット = 4 音節

それらの境界では、エンコーディングの切り詰めは、切り詰められたバイト文字列のエンコーディングと正確に等価です:

SingSong(X)[0:4k 音節] = SingSong(X[0:3k バイト])

同じプロパティはバリアントにも当てはまります。SHAKE-256マスクは出力ストリームとして生成されるため、短いマスクは長いマスクのプレフィックスです:

M(v, 3k) = M(v, len(X))[0:3k]

したがって:

body(SingSong(X, v))[0:4k 音節] + suffix(v)
    = SingSong(X[0:3k バイト], v)

プレフィックスが存在する任意の k に対して。

バイト境界と音節境界の両方で終了しないプレフィックスの場合、共有された先頭の音節は同じ先頭ビットを表しますが、切り詰められたテキスト自体はバイト文字列の完全な正規エンコーディングではありません。

書き取りとエラー処理

CV文法は基本的な構文チェックを提供します。奇数位置には子音、偶数位置には母音が含まれている必要があります。対応するアルファベット外の文字は拒否されなければなりません。

パーサーは、位置によって意図されたシンボルが決まる、曖昧でない書き取り置換を正規化してもよいです:

• 母音位置での 0 → o
• 子音位置での 1 → l
• 母音位置での e → i

これらの置換は、表現エラーのみを修正します。Sing-songには誤り訂正コードやチェックサムは含まれていません。有効な音節が別の有効な音節に置換された場合、エンコーディング自体からは検出できません。

検討された代替案

ベースとなる文法は、記録する価値のある3つの代替案を生き残りました。

キュレーションされた音節辞書

手作業で選ばれたコードブックは、b/p、d/t、g/k、f/v、s/z、m/n、l/rのような音を同等クラスにマージすることによって、紛らわしい最小ペアを除外できます。約10個の開始クラス × 4つの母音 × 3つのコーダクラスで、約120個の堅牢な音節（各約6.9ビット）が得られます。これはSing-songより約17%少ない音節ですが、エラー耐性は向上します。コストは、大きなルックアップテーブル、より長い書き込み形式、およびより重い閉音節です。

例:

ban-fok-rim-tus-gal-nom-pik-sur

この利点は、単純な生成文法と軽快で開いた響きを失う価値はありませんでした。

交替をクラスター禁止制約に緩和する

CV、VC、CVCを許可し、子音の隣接のみを禁止することで、理論的な容量を2.95ビット/文字から3.32ビット/文字に引き上げます。二重母音を禁止し、母音の連続を制限し、明確な二重母音（ai、au、oi、ou、ui）のみを許可すると、実用的な利得は書き込み長で約3%、発話密度では実質ゼロに低下します。

例:

zilai-sibo-tauva-juzu

このわずかな利得は、偶奇性ルールをオートマトンに置き換え、エラー回復を弱め、バリアント解析を複雑にする価値はありませんでした。

選択された子音クラスター開始音

音節を開いたままにしつつ、選択された英語のCC開始音を許可すると、(C | selected CC)V、例えば ba、gro、pli、tru が得られます。現在の16個の単純な開始音に12個のクラスター（br、bl、dr、fr、fl、gr、gl、kr、kl、pr、pl、tr）を加えると、アルファベットは112音節、つまり約6.81ビット/音節になります。256ビットの値には約38音節が必要です。

例:

zila-grovi-pluma-triso-fraku-silo-bruna-koti

これはSing-songの開いたメロディックなキャラクターの多くを保持しますが、均一なCV文法と偶奇性解析を犠牲にして、発話長をわずかに削減します。

16 × 4のCVアルファベットは有用な境界です。音節あたり正確に6ビットで、単純なコーデックでありながら、小さな文法、開いた響き、位置解析を保持します。

他のエンコーディングとの比較

Sing-songは書き込み密度と発話密度の間でトレードオフを行います。文字あたり3ビット、音節あたり正確に6ビットを運びます。Hexは文字あたり4ビット、Base58は約5.9ビットを運びます。

値が発話されると、このトレードオフは逆転します。16進数の文字名は長く、強い韻クラスを含みますが、Sing-songは各短いCV音節に6ビットを運びます。完全な256ビットの値は43音節かかります。

人間のチャネルが存在しない場合は、HexまたはBase58が短く、より好ましいです。Sing-songは、人間が読み取り、言い、入力し、または記憶する必要がある値のために意図されています。

テストベクトル

コーデックはバイトに意味を割り当てることなく動作します。

入力 = 32 × 00:

入力       0000000000000000000000000000000000000000000000000000000000000000
sing-song   baba-baba-baba-baba-baba-baba-baba-baba-baba-baba-baba-baba-baba-baba-baba-baba-baba-baba-baba-baba-baba-ba

入力 = SHA-256(sing-song):

入力       7910c06577ab67de51fed45ba18f27fc28eb618ebc1b78f9bced0f47fcefec2d
sing-song   moji-buba-liku-moru-lizi-wiji-zusi-jilu-rala-zapu-zubo-nuru-lala-woza-dovu-nuwi-sugo-vagu-jizu-tusu-wubo-va

別の256ビット入力:

入力       d16997955b621dde4e0debc35fbbd3497eeb641008787903fea57437665399fa
sing-song   vako-poku-piki-sino-dumi-wigo-bumo-subu-kuwu-suju-joku-wuru-libi-bafa-modu-pabu-zuro-kiva-givo-liju-pomu-ra

入力 = 32 × 00 のバリアント導出:

v           1
マスク        607aa3412838d5ebff0ae2b8521c453e0bf24d48d5438217dbee1dcb39991be7
導出値        607aa3412838d5ebff0ae2b8521c453e0bf24d48d5438217dbee1dcb39991be7
sing-song   ladu-ronu-jajo-nawa-vimo-suzu-boso-fowa-kani-tidi-guna-suto-juka-nuki-jawa-faku-vozo-wami-totu-poli-dozo-ma-am

v           5
マスク        6a0dea99f82a4d9776babb55ded1d9824fa22789bbcb0e95da7035a7df307946
導出値        6a0dea99f82a4d9776babb55ded1d9824fa22789bbcb0e95da7035a7df307946
sing-song   lona-vuro-pomu-naro-juli-mivo-soru-siki-vusi-duli-napa-zono-fiwa-powu-tota-woki-vopu-bavi-rizi-zata-moka-la-im

Sing-songボディをデコードすると derived が得られ、同じマスクでXORすると input が復元されます。

参考実装

import argparse
import hashlib

CONS   = "bdfgjklmnprstvwz"
VOWELS = "aiou"
VARC   = "lmnr"


def encode(data: bytes, group: int = 4) -> str:
    n_bits = 8 * len(data)
    n = (n_bits + 5) // 6
    pad = 6 * n - n_bits
    bits = int.from_bytes(data, "big") << pad

    syllables = []
    for i in range(n):
        x = (bits >> (6 * (n - i - 1))) & 0x3f
        syllables.append(CONS[x >> 2] + VOWELS[x & 3])

    s = "".join(syllables)
    return "-".join(s[i:i + group] for i in range(0, len(s), group))


def decode(s: str) -> bytes:
    s = s.replace("-", "")
    if len(s) % 2:
        raise ValueError("incomplete syllable")

    n = len(s) // 2
    n_bytes = (6 * n) // 8
    if (8 * n_bytes + 5) // 6 != n:
        raise ValueError("not a complete canonical byte-string encoding")

    bits = 0
    for i in range(0, len(s), 2):
        bits = (bits << 6) | (CONS.index(s[i]) << 2) | VOWELS.index(s[i + 1])

    pad = 6 * n - 8 * n_bytes
    if pad and bits & ((1 << pad) - 1):
        raise ValueError("non-zero padding")

    return (bits >> pad).to_bytes(n_bytes, "big")


def variant_mask(v: int, n: int) -> bytes:
    if not 0 <= v <= 15:
        raise ValueError("variant must be 0..15")
    if v == 0:
        return bytes(n)
    return hashlib.shake_256(
        b"sing-song/variant" + bytes([v])
    ).digest(n)


def apply_variant(data: bytes, v: int) -> bytes:
    return bytes(
        a ^ b
        for a, b in zip(data, variant_mask(v, len(data)))
    )


def variant_suffix(v: int) -> str:
    return VOWELS[v // 4] + VARC[v % 4]


def parse_variant_suffix(s: str) -> tuple[str, int]:
    s = s.replace("-", "")

    # Content always begins with a consonant and has even length.
    # A variant suffix begins with a vowel after the content body.
    if len(s) >= 2 and s[-2] in VOWELS and s[-1] in VARC:
        v = VOWELS.index(s[-2]) * 4 + VARC.index(s[-1])
        return s[:-2], v

    return s, 0


def encode_variant(data: bytes, v: int = 0) -> str:
    encoded = encode(apply_variant(data, v))

    if v == 0:
        return encoded

    return encoded + "-" + variant_suffix(v)


def decode_variant(s: str) -> tuple[bytes, int]:
    body, v = parse_variant_suffix(s)
    transformed = decode(body)
    return apply_variant(transformed, v), v


def main() -> None:
    parser = argparse.ArgumentParser(
        description="Encode hex as Sing-song or decode Sing-song to hex."
    )
    sub = parser.add_subparsers(dest="command", required=True)

    p_encode = sub.add_parser("encode", help="encode hex to Sing-song")
    p_encode.add_argument("hex", help="hex-encoded byte string")
    p_encode.add_argument(
        "-v", "--variant",
        type=int,
        choices=range(16),
        default=0,
        metavar="0..15",
        help="encoding variant (default: 0)",
    )

    p_decode = sub.add_parser("decode", help="decode Sing-song to hex")
    p_decode.add_argument("singsong", help="Sing-song string")

    args = parser.parse_args()

    if args.command == "encode":
        try:
            data = bytes.fromhex(args.hex)
            print(encode_variant(data, args.variant))
        except ValueError as e:
            parser.error(str(e))

    elif args.command == "decode":
        try:
            data, v = decode_variant(args.singsong)
            print(data.hex())
        except (ValueError, IndexError) as e:
            parser.error(f"invalid Sing-song: {e}")


if __name__ == "__main__":
    main()

例:

$ python singsong.py encode 7910c06577ab67de51fed45ba18f27fc28eb618ebc1b78f9bced0f47fcefec2d
moji-buba-liku-moru-lizi-wiji-zusi-jilu-rala-zapu-zubo-nuru-lala-woza-dovu-nuwi-sugo-vagu-jizu-tusu-wubo-va

$ python singsong.py decode moji-buba-liku-moru-lizi-wiji-zusi-jilu-rala-zapu-zubo-nuru-lala-woza-dovu-nuwi-sugo-vagu-jizu-tusu-wubo-va
7910c06577ab67de51fed45ba18f27fc28eb618ebc1b78f9bced0f47fcefec2d

apply_variant はそれ自身の逆です。同じバリアントを2回適用すると、元のバイトが復元されます。

応用: Nostr ユーザー名

Nostrの npub は、32バイトの公開鍵のBech32表現です。アプリケーションは、npub をデコードし、直接のSing-songエンコーディングの最初の8音節（4つの表示グループ）を取得することで、固定長のSing-songユーザー名を派生させることができます:

P = bech32_decode(npub)          # 32バイト公開鍵
username = SingSong(P) の最初の8音節

8音節は正確に48ビットを表すため、これは公開鍵の最初の6バイトをエンコードすることに相当します:

username = SingSong(P[0:6])

これはSing-songのプレフィックス安定性ルールから直接導かれます: 6 バイト = 48 ビット = 8 音節。

結果として得られるユーザー名は、ハッシュから派生したフィンガープリントではなく、公開鍵プレフィックスの読み取り可能な表現です。ユーザーはユーザー名を6バイトのHexにデコードし、公開鍵の先頭と直接比較できます。同様に、アプリケーションはハッシュなしでユーザー名を派生させ、デコードされたプレフィックスを比較することによって候補マッチを見つけることができます。

ユーザー名はグローバルに一意ではありません。多くの32バイト公開鍵が同じ最初の6バイトを共有できます。より強力な識別が必要なアプリケーションは、より多くの音節を使用できます。完全なSing-songエンコーディングまで使用すると、完全な32バイト公開鍵に双方向に逆変換されます。

しかし:

• アンナはボブに、彼女のユーザー名が kalo-tadu-komu-tigi であると伝えます。
• ボブはその文字列をNostrクライアントに入力します。
• クライアントはそれを 51ac0759fc4d に変換し、このHexの先頭で始まる npub を持つ既知のユーザーを検索します。
• クライアントはマッチをボブに提示し、ボブはアンナのアカウントを選択します。

先行技術

Sing-songは、S/Keyワードエンコーディング（RFC 1751）、PGPワードリスト、Bubble Babble、Oren Tiroshのニーモニックエンコーディング、proquints、BIP39、およびUrbit @p を含む、発話可能なエンコーディング作業に基づいています。

その特徴的な組み合わせは、64音節のCV文法、直接的な6ビットマッピング、自己サイズ調整可能な完全な形式、およびエンコードされた双方向バリアントを備えた、双方向のプレフィックス安定バイト文字列エンコーディングです。

特別な感謝

lobste.rs スレッドでコメントしてくれたすべての人々に特別な感謝を捧げます。皆様のコメントのおかげで、この投稿の多くの側面を修正・改善することができました。