إثبات الالتزامات

يدين الحافظ (custodian) لكل عميل برصيد. يثبت هذا البرنامج أن مجموع الأرصدة لا يتجاوز رقم الاحتياطي الذي نشره الحافظ، دون نشر أي رصيد منفرد أو المجموع الكلي. ويستطيع كل عميل أن يتحقق، ببضعة أسطر من Python ودون أي أدوات خاصة، من أن رصيده قد احتُسب.

تتضمن صفحة Example programs الإعداد المشترك بين صفحات الأمثلة الأربع.

1. ما الذي يثبته

يبني الحافظ شجرة Merkle للمجاميع. الورقة هي حساب واحد: تجزئة (hash) لمعرّف العميل ورصيده، ومعها الرصيد إلى جانبها. والعقدة هي تجزئة لطفليها ومجموعيهما، ومعها حاصل جمع المجموعين إلى جانبها. فيحمل الجذر بذلك مجموع كل الأرصدة التي تحته.

تُبنى الشجرة داخل البرنامج، من القائمة الخاصة بالحسابات. ويثبت الاستدعاء ما يلي:

1. أن الجذر المنشور في الإيصال هو جذر شجرة مجاميع على الحسابات التي قدّمها الحافظ؛
2. أن كل مجموع فيها هو المجموع الصحيح للمجموعين اللذين تحته، دون تجاوز للسعة (overflow)؛
3. أن المجموع عند الجذر لا يزيد على رقم الاحتياطي المثبّت عند النشر.

النقطة 2 هي ما لا تستطيع شجرة مجاميع منشورة دون إثبات أن توفره. فالهجوم المعروف على شجرة مجاميع مجرّدة هو أن يكتب الحافظ مجموع العقدة الأب أصغر من مجموع طفليها، وهو ما لا يستطيع أي عميل كشفه من مسار واحد. أما هنا فالبرنامج هو الذي يحسب المجاميع، ولا يوجد إثبات لأي حساب آخر.

ما لا يغطيه الإثبات هو الاكتمال: فالحافظ هو من يختار الحسابات التي تدخل. وهذه الفجوة يسدّها العملاء. إذ يتحقق كل واحد منهم من وجود ورقة بمعرّفه ورصيده تحت الجذر المنشور (القسم 7). والحساب المتروك يكتشفه صاحبه.

2. الواجهة

يقع رقم الاحتياطي في المقطع العام لا في المخرجات لسببين. الأول أنه لا يوجد متسع: فالحالة والعدد وجذر من 160 بتًا تملأ الخانات. والثاني أنه يعلن الادعاء قبل وجود الإثبات: فنشر البرنامج يعلن «احتياطيات بمقدار R، لقطة S»، ثم يثبت الاستدعاء إما أن الأرصدة تتسع تحت R أو يعيد الحالة 2.

التجزئتان، بالضبط:

leaf  = SHA-256( be32(0) ‖ id (16 bytes) ‖ be64(balance) )                                  28 bytes
node  = SHA-256( be32(1) ‖ left hash ‖ be64(left sum) ‖ right hash ‖ be64(right sum) )      84 bytes
empty = leaf with id 0 and balance 0

للشجرة دائمًا 32 ورقة. تملؤها الحسابات من اليسار وتملأ الأوراق الفارغة الباقي. ويمنع 0 و1 في البداية أن تُقرأ ورقة على أنها عقدة.

ترتيب البايتات. SHA-256 هي big-endian في كل موضع، ويأخذ استدعاء النظام SHA256 كتلته ذات الـ 64 بايت على هيئة ست عشرة كلمة big-endian. لذا يقرأ هذا البرنامج المعرّف على هيئة أربع كلمات big-endian وينشر الجذر على هيئة كلمات big-endian: فالمخرج 2 مطبوعًا بالست عشري هو أول ثماني خانات ست عشرية من الجذر. وهذا عكس اصطلاح برنامج Keccak، لأن التجزئتين معرّفتان على ترتيبين متعاكسين للبايتات.

3. البرنامج الضيف (guest)

my-guests/solvency/src/main.rs، كاملًا:

#![no_std]
#![no_main]

use guest_sdk::{halt, read_input, read_public, sha256_compress, write_output};

/// The tree always has 32 leaves. Accounts fill it from the left; the rest are empty leaves.
const LEAVES: usize = 32;

const SOLVENT: u32 = 1;
const INSOLVENT: u32 = 2;
const TOO_MANY: u32 = 3;
const OVERFLOW: u32 = 4;

const LEAF_TAG: u32 = 0;
const NODE_TAG: u32 = 1;

/// SHA-256's initial state (FIPS 180-4 §5.3.3).
const IV: [u32; 8] = [
    0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19,
];

#[derive(Clone, Copy)]
struct Node {
    hash: [u32; 8],
    sum: u64,
}

/// SHA-256 of the 28 bytes `be32(0) ‖ id (16 bytes) ‖ be64(balance)`. The message, its `0x80`
/// terminator and its bit length fit one 64-byte block, so a leaf is one compression.
fn leaf(id: &[u32; 4], balance: u64) -> Node {
    let mut buf = [0u32; 24];
    buf[0] = LEAF_TAG;
    buf[1..5].copy_from_slice(id);
    buf[5] = (balance >> 32) as u32;
    buf[6] = balance as u32;
    buf[7] = 0x8000_0000;
    buf[15] = 28 * 8;
    buf[16..].copy_from_slice(&IV);
    sha256_compress(&mut buf);
    let mut hash = [0u32; 8];
    hash.copy_from_slice(&buf[16..]);
    Node { hash, sum: balance }
}

/// SHA-256 of the 84 bytes `be32(1) ‖ left hash ‖ be64(left sum) ‖ right hash ‖ be64(right sum)`:
/// two compressions. `None` when the two sums do not fit a u64.
fn parent(l: &Node, r: &Node) -> Option<Node> {
    let sum = l.sum.checked_add(r.sum)?;
    let mut buf = [0u32; 24];
    buf[16..].copy_from_slice(&IV);
    // Block 1: words 0..16 of the message.
    buf[0] = NODE_TAG;
    buf[1..9].copy_from_slice(&l.hash);
    buf[9] = (l.sum >> 32) as u32;
    buf[10] = l.sum as u32;
    buf[11..16].copy_from_slice(&r.hash[..5]);
    sha256_compress(&mut buf);
    // Block 2: the last five words, the terminator, zeros, the bit length.
    buf[..3].copy_from_slice(&r.hash[5..]);
    buf[3] = (r.sum >> 32) as u32;
    buf[4] = r.sum as u32;
    buf[5] = 0x8000_0000;
    buf[6..15].fill(0);
    buf[15] = 84 * 8;
    sha256_compress(&mut buf);
    let mut hash = [0u32; 8];
    hash.copy_from_slice(&buf[16..]);
    Some(Node { hash, sum })
}

/// Public segment, fixed at deploy: [reserves low word, reserves high word, snapshot label].
/// Private input: [n, then n accounts of (id: 4 words, balance low, balance high)].
/// Outputs: [status, n, root (first 5 words), 0].
#[no_mangle]
pub extern "C" fn main() -> ! {
    let reserves = read_public(0) as u64 | (read_public(1) as u64) << 32;

    let n = read_input(0) as usize;
    if n > LEAVES {
        write_output(0, TOO_MANY);
        halt();
    }

    let empty = leaf(&[0; 4], 0);
    let mut row = [empty; LEAVES];
    for (i, slot) in row.iter_mut().enumerate().take(n) {
        let at = 1 + 6 * i as u32;
        let id = [read_input(at), read_input(at + 1), read_input(at + 2), read_input(at + 3)];
        let balance = read_input(at + 4) as u64 | (read_input(at + 5) as u64) << 32;
        *slot = leaf(&id, balance);
    }

    // Fold the row in place, a level at a time, until one node is left.
    let mut width = LEAVES;
    while width > 1 {
        width /= 2;
        for i in 0..width {
            match parent(&row[2 * i], &row[2 * i + 1]) {
                Some(p) => row[i] = p,
                None => {
                    write_output(0, OVERFLOW);
                    halt();
                }
            }
        }
    }
    let root = row[0];

    write_output(0, if root.sum <= reserves { SOLVENT } else { INSOLVENT });
    write_output(1, n as u32);
    for k in 0..5 {
        write_output(2 + k as u32, root.hash[k]);
    }
    halt();
}

الحشو (padding) مكتوب يدويًا. تأخذ guest_sdk::sha256 أي سلسلة بايتات وتنسخها بايتًا بايتًا. أما كل رسالة هنا فهي كلمات كاملة بطول معروف، فيملأ البرنامج كتلة الست عشرة كلمة مباشرة: كلمات الرسالة، ثم 0x80000000، ثم أصفار، ثم طول الرسالة بالبتات في الكلمة الأخيرة. فالورقة ضغطة (compression) واحدة. أما العقدة فتتجاوز بايتاتها الأربعة والثمانون كتلة أولى إلى كتلة ثانية، فهي ضغطتان.

الأرصدة u64 والمجاميع مفحوصة. لا يمكن للرصيد أن يكون سالبًا لأن النوع لا يحتوي قيمًا سالبة، وهذا يزيل الطريقة الكلاسيكية الأخرى لتقليص المجموع. وchecked_add تحوّل تجاوز السعة إلى الحالة 4 بدلًا من مجموع ملتفّ.

النتيجة العاجزة عن الوفاء تظل نتيجة. الحالة 2 توقف عادي مع نشر الجذر. فلا يستطيع الحافظ الحصول على إيصال بالحالة 1 لأرصدة تفوق رقم الاحتياطي، وإيصال الحالة 2 هو إثبات لذلك تحديدًا.

4. جانب المضيف (host)

يستخدم solvency.py المكتبة القياسية لـ Python فقط:

solvency.py setup   <accounts.csv> <reserves> <snapshot label>   writes public.txt, prints the root
solvency.py witness <accounts.csv>                 prints the private words
solvency.py path    <accounts.csv> <row>           prints that account's inclusion proof (JSON)
solvency.py verify  <proof.json> <root prefix hex> checks a proof against a receipt's root

التجزئتان فيه هما المواصفة الكاملة التي يحتاجها العميل:

def leaf(ident: bytes, balance: int):
    return hashlib.sha256(struct.pack(">I", 0) + ident + struct.pack(">Q", balance)).digest(), balance

def parent(l, r):
    h = hashlib.sha256(struct.pack(">I", 1) + l[0] + struct.pack(">Q", l[1]) + r[0] + struct.pack(">Q", r[1]))
    return h.digest(), l[1] + r[1]

يضم العرض التجريبي اثني عشر حسابًا في demo-accounts.csv، بواقع id,balance في كل سطر، والأرصدة بوحدات 10⁻⁸ (الدقة التي يستخدمها رمز مُجسَّر مثل zUSD). ومجموعها 100,215.185678. ويدّعي الحافظ احتياطيات قدرها 101,000:

$ python3 solvency.py setup demo-accounts.csv 10100000000000 20260930
root 46b78564d60f75bdc9552d8ad1c4aadf411354054be3ffb80337b8549471a82c
root prefix 46b78564d60f75bdc9552d8ad1c4aadf41135405
root words 1186432356 3591337405 3377802634 3519326943 1091785733
liabilities 10021518567800
wrote public.txt
$ cat public.txt
2531887104 2351 20260930

2351 × 2³² + 2531887104 تساوي 10,100,000,000,000. وسطر liabilities هو منظور الحافظ نفسه. ولا يُنشر أبدًا.

يجب أن تكون المعرّفات فريدة وغير قابلة للتخمين. فلو أُعطي عميلان برصيد متساوٍ الورقة نفسها، لأمكن للحافظ احتساب التزام واحد لكليهما. ومعرّف لا يتعرّف عليه بوصفه معرّفه إلا صاحبه يمنع ذلك، ومعرّف لا يمكن تخمينه يمنع العميل الذي يرى تجزئة شقيقة من تجربة تخمينات لرصيد جاره. ويستخدم العرض التجريبي أول 16 بايتًا من تجزئة. أما النشر الحقيقي فيشتق المعرّف من حساب العميل ومن nonce خاص بكل لقطة، ويُظهره للعميل.

5. البناء والتشغيل

$ rand-guest build my-guests/solvency --max-words 65535
994 words against a cap of 65535 (fits); 0 ecall(s) with a non-static a7
OK
wrote my-guests/solvency/image.bin and its .sha256 (994 words, hc 5559791a05bd9269bf7fc4e893c05e8b21defe5ef966d831b49ea463fb4552d3, program id 697412b5db65647164c21b27e4b4feb0b5f0b9fce2381157cd0786bfecf1769f)
$ cd my-guests/solvency
$ python3 solvency.py witness demo-accounts.csv > witness.txt
$ rand-guest run image.bin --public $(cat public.txt) --input $(cat witness.txt) --tier 14
out[0] = 1
out[1] = 12
out[2] = 1186432356
out[3] = 3591337405
out[4] = 3377802634
out[5] = 3519326943
out[6] = 1091785733
out[7] = 0
cycles 7492
tier 14
tier 14: fits (cycles 7762 of 16383, Poseidon2 permutations 270 of 2048)

الحالة 1، واثنا عشر حسابًا، والكلمات الخمس للجذر التي طبعها النص البرمجي. والشاهد (witness) من 73 كلمة: العدد وست كلمات لكل حساب.

وإذا خُفّض رقم الاحتياطي إلى 100 وحدة (--public 100 0 1) تعطي الحسابات نفسها out[0] = 2. والعدد 33 يعطي out[0] = 3. وحسابان يتجاوز مجموع رصيديهما 2⁶⁴ يعطيان out[0] = 4.

6. الميزانية

عدد الضغطات هو n من الأوراق، وورقة فارغة واحدة (تُحسب مرة وتُنسخ)، وضغطتان لكل عقدة من العقد الـ 31. ويجوز للاستدعاء أن يستخدم 128 ضغطة على الأكثر، والطبقة 14 هي أعلى طبقة يجوز لاستدعاء استخدامها، لذا فإن 32 حسابًا قريب مما يستطيع استدعاء واحد إثباته في هذا التصميم. أما شجرة من 64 ورقة فتحتاج 190 ضغطة ولا تتسع.

وهذا حجم للعرض التوضيحي. ومجاوزته تعني تقسيم الشجرة على عدة استدعاءات وحمل التزام بجذر كل شجرة فرعية ومجموعها إلى استدعاء نهائي، وهو النمط الذي تصفه صفحة Write a program لأي عمل يتجاوز الميزانية. ولا يفعل هذا المثال ذلك.

منذ chain 18 تكلّف الضغطة 64 gas، مقابل 1 للدورة العادية. وتطبع المحفظة الـ gas الدقيق للتشغيل والحد الذي تصرّح به:

gas: 12489 (declaring 16384, tier 14)

كل صف يكلّف 1 gas وتكلّف الضغطة 63 إضافية: 7,764 صفًا زائد 75 × 63 تساوي 12,489. وأكثر من ثلث الـ gas يذهب إلى التجزئة. (تحسب المحفظة صفين أكثر مما يحسبه rand-guest run، بسبب ربط المعاملة الذي تضيفه chain 18 إلى المقطع العام للاستدعاء.)

7. تحقق العميل

يعطي الحافظ كل عميل مساره: تجزئة الشقيق ومجموع الشقيق عند كل مستوى من المستويات الخمسة.

$ python3 solvency.py path demo-accounts.csv 6 > proof6.json
$ head -12 proof6.json
{
 "id": "f8f4e4a0c855aad0d0f9ae5bab108333",
 "balance": 1820025000000,
 "path": [
  {
   "hash": "e39eaaabec5cca1fe4c76ce656692be631a39e807876f93bdd7baf8b057d6997",
   "sum": 6600000000,
   "sibling_is_left": false
  },
  {
   "hash": "4732f069886c966e6429ee9063f73429bf153eb2575cf2a28f00f27b7d0d89c6",
   "sum": 31500000000,

يعيد العميل حساب الجذر من معرّفه ورصيده، ويقارن أول 20 بايتًا منه بمخرجات الإيصال من 2 إلى 6:

$ python3 solvency.py verify proof6.json 46b78564d60f75bdc9552d8ad1c4aadf41135405
root prefix 46b78564d60f75bdc9552d8ad1c4aadf41135405 MATCH

والمسار لرصيد أعلى بوحدة واحدة من الرصيد الموجود في الشجرة لا يصل إلى الجذر:

$ python3 solvency.py verify tampered.json 46b78564d60f75bdc9552d8ad1c4aadf41135405
root prefix e9a1b4cbe49e412214b97afe73348fa7c555fa7a DOES NOT MATCH

التحقق كله هو الدالتان leaf وparent أعلاه مطبّقتين خمس مرات. والعميل الذي لا يريد تشغيل النص البرمجي للحافظ يستطيع كتابته بنفسه.

يُظهر المسار للعميل مجاميع أشقائه. فالخطوة الأولى من المسار أعلاه تكشف أن الورقة المجاورة تحمل 6,600,000,000 وحدة، وتكشف كل خطوة أعلى مجموع شجرة فرعية. وهذا ملازم لشجرة المجاميع البسيطة. وخلط الأوراق في كل لقطة يحدّ مما يستطيع العميل تعلّمه مع الوقت، وإخفاء المجاميع تمامًا يحتاج التزامات (commitments) بدلًا من الأرقام الصريحة، وهو ما لا يفعله هذا المثال.

8. النشر

$ rand fee deploy 994 --public-words 3
0.1007 RAND
$ rand program deploy image.bin --public public.txt
program id: fce8474dfdf80b9733e04fb72d4d8d19c40ba5ab646b3d867322daf4b9b599c0 (994 words, hc 1a7959556992bd05e8c47fbf8b5ec0935efede2131d866f963a49eb4d35245fb, public input 3 words, digest 70d5ae8935d646f7a0dd426c30aaf68e9bc382534d8a6ced90e363e129403608)
proving the spend authorisation on this machine (tier 10; seconds)…
authorisation proved in 6.8s: tier 10, 1368908 bytes
proving the bundle (tier 14; about a minute and a half on a laptop)…
proved in 116.7s: tier 14, 1500710 bytes
submitted deploy 39e8f35e0bdc7bc105ce942dc492b52f7a5efbb682ab6ebecc17cb310a161ada
  0 RAND out, 59.8545 RAND change, fee 0.1007 RAND, anchored at height 97831, proved in 116.7s (bundle) + 6.8s (auth)

يربط معرّف البرنامج رقم الاحتياطي ووسم اللقطة بالشيفرة. واللقطة الجديدة نشر جديد، بتكلفة نحو عُشر RAND، ومعرّفها هو البيان العلني للادعاء الجديد.

9. الاستدعاء

$ rand call fce8474dfdf80b9733e04fb72d4d8d19c40ba5ab646b3d867322daf4b9b599c0 \
    $(sed 's/[0-9][0-9]*/--input &/g' witness.txt)

proving the call locally (73 inputs stay private, over the program's 3-word public input)…
gas: 12489 (declaring 16384, tier 14)
fee 0.007487437 RAND (incl. two price steps of headroom)
proved in 122.9s: tier 14, 1911152 bytes, outputs [1, 12, 1186432356, 3591337405, 3377802634, 3519326943, 1091785733, 0]
proving the spend authorisation on this machine (tier 10; seconds)…
authorisation proved in 6.8s: tier 10, 1375371 bytes
proving the bundle (tier 14; about a minute and a half on a laptop)…
proved in 111.9s: tier 14, 1500198 bytes
submitted call 5d276bf7cb65cfcd2244ffd05baceaf6cb8082aeed6129a5e87e8737b3374e17
  0 RAND out, 59.709221126 RAND change, fee 0.007487437 RAND, anchored at height 98336, proved in 111.9s (bundle) + 6.8s (auth)
{
  "h_in": "b151f38fbbefd08c9f36e65da89f016ba7fc0ccdb52bddda6544e3d86372d331",
  "h_pub": "70d5ae8935d646f7a0dd426c30aaf68e9bc382534d8a6ced90e363e129403608",
  "height": 98574,
  "index": 0,
  "outputs": [
    1,
    12,
    1186432356,
    3591337405,
    3377802634,
    3519326943,
    1091785733,
    0
  ],
  "program": "fce8474dfdf80b9733e04fb72d4d8d19c40ba5ab646b3d867322daf4b9b599c0",
  "tier": 14,
  "tx": "5d276bf7cb65cfcd2244ffd05baceaf6cb8082aeed6129a5e87e8737b3374e17"
}
input transcript published; open it with `rand open-call 5d276bf7cb65cfcd2244ffd05baceaf6cb8082aeed6129a5e87e8737b3374e17`

الحالة 1، واثنا عشر حسابًا، والجذر 46b78564 d60f75bd c9552d8a d1c4aadf 41135405 بالست عشري. ولا شيء في المعاملة يذكر رصيدًا أو المجموع.

هذه استدعاء من المستوى 14، لذا فإن إثبات الاستدعاء هو الجزء البطيء: 123 ثانية، ثم 7 ثوانٍ لتفويض الإنفاق و112 ثانية للحزمة، أي خمس دقائق في المجموع، بذروة قدرها 6.6 GB. حجم الإثبات 1,911,152 بايت. ويمثّل جدول SHA-256 نحو 0.4 MB من ذلك.

10. تحقّق بنفسك

1. الادعاء. تعيد rand_getProgramPublic على معرّف البرنامج رقم الاحتياطي والوسم. أما هل يحتفظ الأمين فعلاً بهذا الاحتياطي فهو خارج نطاق هذا الإثبات: يُثبَت برصيد على السلسلة، أو بخطاب من مدقّق حسابات، أو في حالة الأصل المنقول عبر الجسر بدالة rand_getTokenSupply الخاصة بالسلسلة نفسها.
2. الشيفرة. أعد بناء my-guests/solvency عند إيداع الدوائر نفسه وقارن hc مع code_hash الخاص بالبرنامج.
3. الإيصال. الحالة 1، والخانة 7 لا تساوي 3735928559، وprogram يساوي المعرّف. المخرجات من 2 إلى 6 هي الجذر الذي يتحقق منه كل عميل.
4. ورقتك الخاصة، كما في القسم 7.

يمكن لأي شخص تكرار الاستدعاء بالحسابات التجريبية، أو تغيير رصيد ومشاهدة الجذر يتحرك.

ما لا يمنحك إياه الإثبات

• الاحتياطيات نفسها. الإثبات يخص الالتزامات مقابل رقم. والرقم يحتاج إلى دليله الخاص.
• الاكتمال من دون العملاء. الحساب الذي أغفله الأمين لا يكتشفه إلا العميل الذي يعود إليه. وكلما زاد عدد العملاء الذين يتحققون، ضاق المجال.
• لحظة زمنية تطابق لحظة الاحتياطيات. يستطيع الأمين اقتراض أموال لساعة اللقطة. واللقطات المتكررة في أوقات غير معلنة تقلّص ذلك.
• الجيران المخفيون. يُظهر مسار العميل مجاميع العقد المجاورة (القسم 7).
• أكثر من 32 حساباً في استدعاء واحد. انظر الميزانية.