IETF Logo Mail Archive

[MLS] Proposals for handling concurrent messages

"M.A.L. Weidner" <malw2@cam.ac.uk> Tue, 19 March 2019 22:33 UTC

Return-Path: <malw2@cam.ac.uk>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 9F1FB12788F for <mls@ietfa.amsl.com>; Tue, 19 Mar 2019 15:33:20 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.158
X-Spam-Level:
X-Spam-Status: No, score=0.158 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_MED=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_IMAGE_ONLY_12=2.059, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=universityofcambridgecloud.onmicrosoft.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id YNjkyCP0zCr8 for <mls@ietfa.amsl.com>; Tue, 19 Mar 2019 15:33:18 -0700 (PDT)
Received: from EUR04-HE1-obe.outbound.protection.outlook.com (mail-eopbgr70123.outbound.protection.outlook.com [40.107.7.123]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E75EE130DC4 for <mls@ietf.org>; Tue, 19 Mar 2019 15:33:15 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=UniversityOfCambridgeCloud.onmicrosoft.com; s=selector1-cam-ac-uk; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=gx5t3z/1xLPdCs5NEaZaVB/D/lAy6q5rZWvH38hSct8=; b=i9XnCsRQkqrUdLsay0Htn7MjfeSy3AecGKNjfw0PlV+uExNotnsKwl8IyQAJVAm12CTPUoamiOw7SY8ozwpe57nzlzsu2dsl1trOHLp8Y7vIcJKQjTjt9/PvP0Q8S6YsJdiGThoI791oRbhnNMKtmxylnYj7/x0/48rWOGPf/o4=
Received: from VI1PR0801MB1296.eurprd08.prod.outlook.com (10.167.197.146) by VI1PR0801MB1792.eurprd08.prod.outlook.com (10.168.67.145) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1709.13; Tue, 19 Mar 2019 22:33:11 +0000
Received: from VI1PR0801MB1296.eurprd08.prod.outlook.com ([fe80::115c:1de1:f2ba:690c]) by VI1PR0801MB1296.eurprd08.prod.outlook.com ([fe80::115c:1de1:f2ba:690c%2]) with mapi id 15.20.1709.015; Tue, 19 Mar 2019 22:33:10 +0000
From: "M.A.L. Weidner" <malw2@cam.ac.uk>
To: "mls@ietf.org" <mls@ietf.org>
Thread-Topic: Proposals for handling concurrent messages
Thread-Index: AQHU3qO7vFsPft27yE62tRLT8TpCKw==
Date: Tue, 19 Mar 2019 22:33:10 +0000
Message-ID: <CADSARUtSRJGW=z=9Spi=D87mOG34NCTswEcQMeeftv9x6gathQ@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-clientproxiedby: AM6PR10CA0059.EURPRD10.PROD.OUTLOOK.COM (2603:10a6:209:80::36) To VI1PR0801MB1296.eurprd08.prod.outlook.com (2603:10a6:800:3a::18)
x-ms-exchange-messagesentrepresentingtype: 1
x-gm-message-state: APjAAAUohzZ7gG69SBjSg6oaUfvSxBNS9vfZbybcIf41WUJ8z/KPa8W7 OAN1GEf2ENx844Jy0yO50fSpG4iwy9/DPuEvnZc=
x-google-smtp-source: APXvYqxtxPn8Ii5nybGW2YVAQBZP32zfAqiWU6EX/8Y6Ct2m3nstEj2UhfRndmHA83I3McvOflWPOpIiEds1Ryww5u4=
x-received: by 2002:a1c:1c5:: with SMTP id 188mr1862766wmb.52.1553034788211; Tue, 19 Mar 2019 15:33:08 -0700 (PDT)
x-gmail-original-message-id: <CADSARUtSRJGW=z=9Spi=D87mOG34NCTswEcQMeeftv9x6gathQ@mail.gmail.com>
x-originating-ip: [209.85.128.41]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 94faaddd-6584-4ace-23d0-08d6acbadd71
x-microsoft-antispam: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600127)(711020)(4605104)(2017052603328)(7153060)(49563074)(7193020); SRVR:VI1PR0801MB1792;
x-ms-traffictypediagnostic: VI1PR0801MB1792:
authentication-results: spf=none (sender IP is ) smtp.mailfrom=malw2@cam.ac.uk;
x-microsoft-antispam-prvs: <VI1PR0801MB1792F964A4ABC9A993DD831BAC400@VI1PR0801MB1792.eurprd08.prod.outlook.com>
x-forefront-prvs: 0981815F2F
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(376002)(346002)(366004)(136003)(396003)(39860400002)(189003)(199004)(3846002)(9686003)(5660300002)(256004)(786003)(2351001)(55446002)(8676002)(71200400001)(8936002)(4744005)(66066001)(478600001)(186003)(316002)(71190400001)(2906002)(68736007)(1730700003)(6916009)(81156014)(61266001)(15650500001)(81166006)(2501003)(6436002)(86362001)(305945005)(733005)(498394004)(5640700003)(476003)(102836004)(7736002)(25786009)(97736004)(26005)(6116002)(95326003)(52116002)(486006)(6506007)(386003)(6486002)(106356001)(105586002)(98316002)(5024004)(14454004)(54896002)(53936002)(99936001)(54556002)(99286004)(61726006)(74482002)(6512007); DIR:OUT; SFP:1102; SCL:1; SRVR:VI1PR0801MB1792; H:VI1PR0801MB1296.eurprd08.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; MX:1; A:1;
received-spf: None (protection.outlook.com: cam.ac.uk does not designate permitted sender hosts)
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam-message-info: tW2Do177GIF0cLO+kMHO3jug72cftLtvBl21QSWGlYE/Rpbplbneabmof4EMF7Tc3jwTs46fQmYo4RvmZGdp6AnM7Hk5Z6kcIbSmdzGVfLrvZ9b/JRLzDBUV1e3eAzMh+wMvu2eL/EbIXk6DpUX9IudBv7bVvk8jfEi/C52pL9Duf6msokNq14n+3TYfuibrAtR/YC3pcavPO0SoDxRIwmlNrExG5MlF9XeOFCZa66hkhOagwx72yiTp1CzGu2o2hmz9cGx4ns5giE+Cibmgsy7JJE74u8z5EbxbaBY/1Vvg6lc2ScVuuQ83K7ceyiL1H3xfqwNClP58ok3qQxmsxB63dINYj0lQPmaiK5aBSa6O9LXpvxuTgjGqIYItkOtONe6j6ZieNhjy2oimEXQXGWCosCZXF9GojpqhyuIjcVA=
Content-Type: multipart/mixed; boundary="_006_CADSARUtSRJGWz9SpiD87mOG34NCTswEcQMeeftv9x6gathQmailgma_"
MIME-Version: 1.0
X-OriginatorOrg: cam.ac.uk
X-MS-Exchange-CrossTenant-Network-Message-Id: 94faaddd-6584-4ace-23d0-08d6acbadd71
X-MS-Exchange-CrossTenant-originalarrivaltime: 19 Mar 2019 22:33:10.4522 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 49a50445-bdfa-4b79-ade3-547b4f3986e9
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR0801MB1792
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/jmKTiBaP-O2vHCHLWNOeAcdodPA>
Subject: [MLS] Proposals for handling concurrent messages
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Messaging Layer Security <mls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/mls>, <mailto:mls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/mls/>
List-Post: <mailto:mls@ietf.org>
List-Help: <mailto:mls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/mls>, <mailto:mls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 19 Mar 2019 22:33:21 -0000

Dear MLS Working Group,

I've attached a document that details some proposals for how to better handle concurrent messages; see mainly Section 2.

The basic idea is to use some operator * which "combines" key pairs.  E.g., for Diffie-Hellman keys, (x, g^x) * (y, g^y) = (x + y (mod |g|), g^x g^y).

With this operator, we can combine concurrent updates.  E.g., if a updates with x and b updates with y, then the tree changes by: (embedded image)
[causal_fig2.png]
With some extra effort, I believe we can even support concurrent Adds (Section 3.3).

My apologies if there are mistakes or if this has been discussed before.

Best,
Matthew Weidner
MPhil Student
Computer Laboratory, Cambridge

v2.23.0 | Report a Bug | By Email